src/lib/gscplftaaux/flip_udaf.c

   1 #include <stdio.h>
   2 #include <limits.h>
   3 #include <math.h>
   4 #include "rts_udaf.h"
   5 #include "gsconfig.h"
   6 #include "gstypes.h"
   7
   8 /*      Full size
   9 #define QUANT_LFTA1_SIZE 729
  10 #define QUANT_LFTA2_SIZE 181
  11 #define QUANT_LFTA3_SIZE 100
  12 */
  13
  14 /*      half size
  15 */
  16 #define QUANT_LFTA1_SIZE 378
  17 #define QUANT_LFTA2_SIZE 93
  18 #define QUANT_LFTA3_SIZE 50
  19
  20 /*      quarter size
  21 #define QUANT_LFTA1_SIZE 202
  22 #define QUANT_LFTA2_SIZE 49
  23 #define QUANT_LFTA3_SIZE 25
  24 */
  25
  26
  27 #define QUANT_EPS 0.01
  28 #define SKIPDIR_SIZE 100
  29 #define SKIPDIR_HEIGHT_MAX 7
  30 #define max(a,b) ((a) > (b) ? (a) : (b))
  31 #define COMPRESSED_XFER
  32
  33 /****************************************************************/
  34 /* Data Structures                                              */
  35 /****************************************************************/
  36 typedef struct tuple_t {
  37         gs_uint32_t val;
  38         gs_uint32_t gap;
  39         gs_uint32_t del;
  40         gs_uint32_t next;
  41 } tuple_t;
  42
  43 // For skip list
  44 typedef gs_uint32_t val_type;
  45
  46 typedef struct skipnode {
  47         val_type val;
  48         gs_uint32_t next;
  49         gs_uint32_t down;
  50 } skipnode_t;
  51
  52 typedef struct skipdir {
  53         gs_uint32_t height;                             // height of tree
  54         gs_uint32_t freeptr;                            // cursor space stack
  55         gs_uint32_t headptr[SKIPDIR_HEIGHT_MAX+1];      // ptrs to levels
  56         skipnode_t list[SKIPDIR_SIZE+1];
  57 } skipdir_t;
  58
  59
  60 /****************************************************************/
  61
  62 // fstring(5+(QUANT_LFTA3_SIZE+1)*4 +
  63 //         (2+lg(QUANT_LFTA3_SIZE)+(QUANT_LFTA3_SIZE+1)*3)*4)
  64 typedef struct quant_udaf_lfta3_struct_t {
  65         gs_uint32_t nelts;      // # stream elements
  66         gs_uint32_t freeptr;    // ptr to cursor stack
  67         gs_uint32_t usedptr;    // ptr to allocated memory
  68         gs_uint32_t circptr;    // circulating ptr used for compression
  69         gs_uint32_t size;
  70         tuple_t t[QUANT_LFTA3_SIZE+1];  // samples + auxiliary info
  71         skipdir_t sd;           // directory for searching tuples
  72 } quant_udaf_lfta3_struct_t;
  73
  74 /****************************************************************/
  75 /* Skip List Functions                                          */
  76 /****************************************************************/
  77
  78 // Skip list cursor stack operations
  79 gs_uint32_t skipdir_alloc(skipdir_t *sd)
  80 {
  81         gs_uint32_t ptr = sd->freeptr;
  82         if (sd->freeptr != 0)
  83                 sd->freeptr = sd->list[ptr].next;
  84         return ptr;
  85 }
  86
  87 void skipdir_free(skipdir_t *sd, gs_uint32_t ptr)
  88 {
  89         sd->list[ptr].val = 0;
  90         sd->list[ptr].down = 0;
  91         sd->list[ptr].next = sd->freeptr;
  92         sd->freeptr = ptr;
  93 }
  94
  95
  96 void skipdir_create(skipdir_t *sd)
  97 {
  98         gs_int32_t i;
  99
 100         sd->height = 0;
 101         sd->freeptr = 1;
 102         for (i=0; i < SKIPDIR_HEIGHT_MAX; i++)
 103                 sd->headptr[i] = 0;
 104         for (i=1; i < SKIPDIR_SIZE; i++)
 105                 sd->list[i].next = i+1;
 106         sd->list[SKIPDIR_SIZE].next = 0;
 107 }
 108
 109 void skipdir_destroy(skipdir_t *sd)
 110 {
 111         sd->height = 0;
 112 }
 113
 114
 115 void skipdir_search(skipdir_t *sd, val_type val, gs_uint32_t *ptrstack)
 116 {
 117         gs_uint32_t ptr;
 118         gs_int32_t l;
 119
 120         if (sd->height == 0) {
 121                 ptrstack[0] = ptrstack[1] = 0;
 122                 return;
 123         }
 124         // search nonleaf nodes
 125         ptr = sd->headptr[sd->height-1];
 126         for (l=sd->height-1; l >= 0; l--) {
 127                 if (ptr == 0) {
 128                         ptrstack[l+1] = 0;
 129                         ptr = (l > 0) ? sd->headptr[l-1] : 0;
 130                 }
 131                 else if (val <= sd->list[ptr].val) {
 132                         ptrstack[l+1] = 0;
 133                         ptr = (l > 0) ? sd->headptr[l-1] : 0;
 134                 }
 135                 else {
 136                         while ((sd->list[ptr].next != 0) &&
 137                         (sd->list[sd->list[ptr].next].val < val))
 138                                 ptr = sd->list[ptr].next;
 139                         ptrstack[l+1] = ptr;
 140                         ptr = sd->list[ptr].down;
 141                 }
 142         }
 143         ptrstack[0] = ptr;
 144 }
 145
 146
 147 void skipdir_insert(skipdir_t *sd, gs_uint32_t *ptrstack,
 148                         gs_uint32_t leafptr, val_type val)
 149 {
 150         gs_uint32_t newptr, oldptr;
 151         gs_int32_t l;
 152
 153         // if path already existed then point to new duplicate
 154         if ((ptrstack[1] == 0) && (sd->headptr[0] != 0)
 155         && (sd->list[sd->headptr[0]].val == val)) {
 156                 sd->list[sd->headptr[0]].down = leafptr;
 157                 return;
 158         }
 159         if ((ptrstack[1] != 0) && (sd->list[ptrstack[1]].next != 0)
 160         && (sd->list[sd->list[ptrstack[1]].next].val == val)) {
 161                 sd->list[sd->list[ptrstack[1]].next].down = leafptr;
 162                 return;
 163         }
 164
 165         for (l=0; l < SKIPDIR_HEIGHT_MAX; l++) {
 166                 if (random() % 2) break;
 167                 newptr = skipdir_alloc(sd);
 168                 if (!newptr) break;     // out of memory
 169                 sd->list[newptr].val = val;
 170                 //copy(&val, &list[newptr[l]].val);
 171                 // link new directory node to level below
 172                 if (l > 0)
 173                         sd->list[newptr].down = oldptr;
 174                 else
 175                         sd->list[newptr].down = leafptr;
 176                 // insert node into current level
 177                 if ((l >= sd->height) || (ptrstack[l+1] == 0)) {
 178                         sd->list[newptr].next = sd->headptr[l];
 179                         sd->headptr[l] = newptr;
 180                 }
 181                 else {
 182                         sd->list[newptr].next = sd->list[ptrstack[l+1]].next;
 183                         sd->list[ptrstack[l+1]].next = newptr;
 184                 }
 185                 oldptr = newptr;
 186         }
 187         if (l > sd->height) sd->height = l;
 188         //fprintf(stderr,"new height = %u\n",sd->height);
 189 }
 190
 191
 192 void skipdir_delete(skipdir_t *sd, gs_uint32_t *ptrstack, val_type val)
 193 {
 194         gs_uint32_t delptr;
 195         gs_int32_t l;
 196
 197         for (l=0; l < sd->height; l++) {
 198                 if (ptrstack[l+1] == 0) {
 199                         delptr = sd->headptr[l];
 200                         if (delptr == 0) break;
 201                         if (sd->list[delptr].val == val) {
 202                                 sd->headptr[l] = sd->list[delptr].next;
 203                                 skipdir_free(sd, delptr);
 204                         }
 205                         else
 206                                 break;
 207                 }
 208                 else {
 209                         delptr = sd->list[ptrstack[l+1]].next;
 210                         if (delptr == 0) break;
 211                         if (sd->list[delptr].val == val) {
 212                                 sd->list[ptrstack[l+1]].next = sd->list[delptr].next;
 213                                 skipdir_free(sd, delptr);
 214                         }
 215                         else
 216                                 break;
 217                 }
 218         }
 219 }
 220
 221 // For Debugging
 222 void skipdir_print(skipdir_t *sd)
 223 {
 224         gs_uint32_t ptr;
 225         gs_int32_t l;
 226
 227         for (l=sd->height-1; l >= 0; l--) {
 228                 for (ptr=sd->headptr[l]; ptr != 0; ptr=sd->list[ptr].next)
 229                         fprintf(stderr,"%u ", sd->list[ptr].val);
 230                 fprintf(stderr,"\n");
 231         }
 232         fprintf(stderr,"-------\n");
 233         for (l=sd->height-1; l > 0; l--) {
 234                 for (ptr=sd->headptr[l]; ptr != 0; ptr=sd->list[ptr].next)
 235                         fprintf(stderr,"%u ", sd->list[sd->list[ptr].down].val);
 236                 fprintf(stderr,"\n");
 237         }
 238         fprintf(stderr,"-------\n");
 239 }
 240
 241
 242
 243
 244 /*************************** Version 3 **************************/
 245 /* Version 3: LFTA-medium                                       */
 246 /*                                                              */
 247 /* NIC performs O(log n) operations at each update.             */
 248 /****************************************************************/
 249
 250 /****************************************************************/
 251 /* Helper functions                                             */
 252 /****************************************************************/
 253 gs_uint32_t quant_udaf_lfta3_cursor_alloc(quant_udaf_lfta3_struct_t *s)
 254 {
 255         gs_uint32_t ptr = s->freeptr;
 256         if (s->freeptr != 0) s->freeptr = s->t[ptr].next;
 257         s->size++;
 258         return ptr;
 259 }
 260
 261 void quant_udaf_lfta3_cursor_free(quant_udaf_lfta3_struct_t *s, gs_uint32_t ptr)
 262 {
 263         s->t[ptr].next = s->freeptr;
 264         s->freeptr = ptr;
 265         s->size--;
 266 }
 267
 268 void quant_lfta3_print(quant_udaf_lfta3_struct_t *s)
 269 {
 270         tuple_t *t=s->t;
 271         gs_uint32_t ptr = s->usedptr;
 272
 273         if (ptr == 0) {
 274                 fprintf(stderr,"<empty>\n");
 275                 return;
 276         }
 277         //skipdir_print(&s->sd);
 278         for (; ptr != 0; ptr=t[ptr].next) {
 279                 fprintf(stderr,"(%u, %u, %u) ",t[ptr].val,t[ptr].gap,t[ptr].del);
 280         }
 281         fprintf(stderr,"\n");
 282 }
 283
 284 void quant_lfta3_compress(quant_udaf_lfta3_struct_t *s)
 285 {
 286         tuple_t *t = s->t;
 287         gs_uint32_t delptr;
 288         gs_uint32_t threshold;
 289         gs_uint32_t ptrstack[SKIPDIR_HEIGHT_MAX+5];
 290
 291         threshold = (gs_uint32_t)ceil(2.0 * QUANT_EPS * (gs_float_t)s->nelts);
 292 //if(s->circptr < 0 || s->circptr >= QUANT_LFTA3_SIZE)
 293 // printf("1) s->circptr = %d\n",s->circptr);
 294 //if(t[s->circptr].next < 0 || t[s->circptr].next >= QUANT_LFTA3_SIZE)
 295 // printf("t[s->circptr].next = %d\n",t[s->circptr].next);
 296         if ((s->circptr == 0) || (t[s->circptr].next == 0)
 297         || (t[t[s->circptr].next].next == 0))
 298                 s->circptr = s->usedptr;
 299         //if ((s->size % 10) != 0) return;
 300         if (s->nelts > 2) {
 301 //if(s->circptr < 0 || s->circptr >= QUANT_LFTA3_SIZE)
 302 // printf("2) s->circptr = %d\n",s->circptr);
 303                 delptr = t[s->circptr].next;
 304 //if(delptr < 0 || delptr >= QUANT_LFTA3_SIZE)
 305 // printf("delptr = %d\n",delptr);
 306 //if(t[delptr].next < 0 || t[delptr].next >= QUANT_LFTA3_SIZE)
 307 // printf("t[delptr].next = %d\n",t[delptr].next);
 308                 if (t[delptr].gap+t[t[delptr].next].gap+t[t[delptr].next].del < threshold) {
 309                         // delete from directory
 310                         if (t[s->circptr].val != t[delptr].val) {
 311                                 // leftmost duplicate (if multiplicity)
 312                                 skipdir_search(&(s->sd), t[delptr].val, ptrstack);
 313                                 if (t[delptr].val == t[t[delptr].next].val) {
 314 //if(s->sd.headptr[0] < 0 || s->sd.headptr[0] >= QUANT_LFTA3_SIZE)
 315 // printf("s->sd.headptr[0] = %d\n",s->sd.headptr[0]);
 316                                         // duplicates case
 317                                         if ((ptrstack[1] == 0)
 318                                         && (s->sd.headptr[0] != 0)
 319                                         && (s->sd.list[s->sd.headptr[0]].val == t[delptr].val))
 320                                                 s->sd.list[s->sd.headptr[0]].down = t[delptr].next;
 321                                         else if ((ptrstack[1] != 0)
 322                                         && (s->sd.list[ptrstack[1]].next != 0)
 323                                         && (s->sd.list[s->sd.list[ptrstack[1]].next].val == t[delptr].val))
 324                                                 s->sd.list[s->sd.list[ptrstack[1]].next].down = t[delptr].next;
 325                                 }
 326                                 else {
 327                                         // non-duplicates case
 328                                         skipdir_delete(&(s->sd), ptrstack, t[delptr].val);
 329                                 }
 330                         }
 331                         // delete from list
 332                         //fprintf(stderr,"DELETED %u\n", t[delptr].val);
 333                         t[s->circptr].next = t[delptr].next;
 334                         quant_udaf_lfta3_cursor_free(s, delptr);
 335                 }
 336                 else {
 337                         s->circptr = t[s->circptr].next;
 338                 }
 339         }
 340 }
 341
 342
 343 /****************************************************************/
 344 /* LFTA3 functions                                              */
 345 /****************************************************************/
 346 void quant_udaf_lfta3_LFTA_AGGR_INIT_(gs_sp_t b)
 347 {
 348         gs_uint32_t i;
 349
 350         quant_udaf_lfta3_struct_t *s = (quant_udaf_lfta3_struct_t *)b;
 351         s->nelts = 0;
 352         s->usedptr = 0;         // NULL ptr
 353         s->circptr = 0;
 354         // initialize cursor stack
 355         s->freeptr = 1;
 356         s->size = 0;
 357         for (i=1; i < QUANT_LFTA3_SIZE; i++)
 358                 s->t[i].next = i+1;
 359         s->t[QUANT_LFTA3_SIZE].next = 0;
 360         skipdir_create(&(s->sd));
 361 }
 362
 363 void quant_udaf_lfta3_LFTA_AGGR_UPDATE_(gs_sp_t b, gs_uint32_t v)
 364 {
 365         quant_udaf_lfta3_struct_t *s = (quant_udaf_lfta3_struct_t *)b;
 366         tuple_t *t = s->t;
 367         gs_uint32_t ptr = s->usedptr;
 368         gs_uint32_t newptr, delptr;
 369         gs_uint32_t obj;        // objective function
 370         gs_uint32_t threshold;
 371         gs_uint32_t ptrstack[SKIPDIR_HEIGHT_MAX+5];
 372         gs_uint32_t debugptr;
 373
 374 //printf("AGGR_UPDATE start\n");
 375         s->nelts++;
 376         //fprintf(stderr,"nelts = %u\n",s->nelts);
 377         // left boundary case
 378         if ((ptr == 0) || (v < t[ptr].val)) {
 379                 if (t[ptr].val == v) {
 380                         t[ptr].gap++;
 381 //printf("AGGR_UPDATE END 1\n");
 382                         return;
 383                 }
 384                 newptr = quant_udaf_lfta3_cursor_alloc(s);
 385                 if (newptr == 0) {
 386                         gslog(LOG_ALERT, "Out of space.\n");
 387                         return;
 388                 }
 389                 t[newptr].val = v;
 390                 t[newptr].gap = 1;
 391                 t[newptr].del = 0;
 392                 t[newptr].next = s->usedptr;
 393                 s->usedptr = newptr;
 394 //printf("AGGR_UPDATE END 2\n");
 395                 return;
 396         }
 397
 398         // locate $i$ such that (v_i-1 < v <= v_i)
 399         skipdir_search(&(s->sd), v, ptrstack);
 400
 401         //ptr = (ptrstack[0] == 0) ? s->usedptr : s->sd.list[ptrstack[0]].down;
 402         ptr = (ptrstack[0] == 0) ? s->usedptr : ptrstack[0];
 403         while ((t[ptr].next != 0) && (t[t[ptr].next].val < v))
 404                 ptr = t[ptr].next;
 405
 406 /*
 407         // duplicate value
 408         if ((t[ptr].next != 0) && (t[t[ptr].next].val == v)) {
 409                 t[t[ptr].next].gap++;
 410 printf("AGGR_UPDATE END 3\n");
 411                 return;
 412         }
 413 */
 414
 415         // right boundary case
 416         if (t[ptr].next == 0) {
 417                 newptr = quant_udaf_lfta3_cursor_alloc(s);
 418                 if (newptr == 0) {
 419                         gslog(LOG_ALERT, "Out of space.\n");
 420                         return;
 421                 }
 422                 t[newptr].val = v;
 423                 t[newptr].gap = 1;
 424                 t[newptr].del = 0;
 425                 t[newptr].next = 0;
 426                 t[ptr].next = newptr;
 427 //printf("AGGR_UPDATE END 4\n");
 428                 return;
 429         }
 430
 431         // non-boundary case
 432 //printf("1) t[ptr].next =%d, ptr=%d\n",t[ptr].next,ptr);
 433         obj = t[ptr].gap+t[t[ptr].next].gap+t[t[ptr].next].del;
 434         threshold = (gs_uint32_t)ceil(2.0 * QUANT_EPS * (gs_float_t)s->nelts);
 435         if (obj > threshold) {
 436                 newptr = quant_udaf_lfta3_cursor_alloc(s);
 437                 if (newptr == 0) {
 438                         gslog(LOG_ALERT, "Out of memory.\n");
 439                         return;
 440                 }
 441 //printf("newptr=%d\n",newptr);
 442                 t[newptr].val = v;
 443                 t[newptr].gap = 1;
 444                 t[newptr].del = t[t[ptr].next].gap+t[t[ptr].next].del - 1;
 445                 t[newptr].next = t[ptr].next;
 446                 t[ptr].next = newptr;
 447                 skipdir_insert(&(s->sd), ptrstack, newptr, v);
 448         }
 449         else {
 450                 // insert into existing bucket
 451 //printf("t[ptr].next =%d\n",t[ptr].next);
 452                 t[t[ptr].next].gap++;
 453         }
 454         quant_lfta3_compress(s);
 455 //printf("AGGR_UPDATE END 5\n");
 456 }
 457
 458 gs_int32_t quant_udaf_lfta3_LFTA_AGGR_FLUSHME_(gs_sp_t b)
 459 {
 460         quant_udaf_lfta3_struct_t *s = (quant_udaf_lfta3_struct_t *)b;
 461
 462         if (s->freeptr == 0)
 463                 return 1;
 464         else
 465                 return 0;
 466 }
 467
 468 void quant_udaf_lfta3_LFTA_AGGR_OUTPUT_(struct gs_string *r, gs_sp_t b)
 469 {
 470 #ifdef COMPRESSED_XFER
 471         quant_udaf_lfta3_struct_t *s = (quant_udaf_lfta3_struct_t *)b;
 472         tuple_t tmp[QUANT_LFTA3_SIZE+1];
 473         gs_uint32_t ptr=s->usedptr;
 474         gs_int32_t i=0,j;
 475
 476         for (; ptr != 0; ptr=s->t[ptr].next) {
 477                 tmp[i].val = s->t[ptr].val;
 478                 tmp[i].gap = s->t[ptr].gap;
 479                 tmp[i].del = s->t[ptr].del;
 480                 i++;
 481         }
 482         for (j=1; j <= i; j++) {
 483                 s->t[j].val = tmp[j-1].val;
 484                 s->t[j].gap = tmp[j-1].gap;
 485                 s->t[j].del = tmp[j-1].del;
 486                 s->t[j].next = j+1;
 487         }
 488         s->t[i].next = 0;
 489         s->usedptr = 1;
 490
 491         r->length = (5 + 4*(i+1))*sizeof(gs_uint32_t);
 492 #endif
 493 #ifndef COMPRESSED_XFER
 494         r->length = sizeof(quant_udaf_lfta3_struct_t);
 495 #endif
 496         r->data = b;
 497 }
 498
 499 void quant_udaf_lfta3_LFTA_AGGR_DESTROY_(gs_sp_t b)
 500 {
 501         return;
 502 }