src/lib/gscphftaaux/flip_udaf.cc

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <limits.h>
   4 #include <math.h>
   5 #include "hfta_udaf.h"
   6
   7 #define QUANT_LFTA1_SIZE 729
   8 #define QUANT_LFTA2_SIZE 181
   9 #define QUANT_LFTA3_SIZE 100
  10
  11 #define QUANT_EPS 0.01
  12 #define SKIPDIR_SIZE 100
  13 #define SKIPDIR_HEIGHT_MAX 7
  14 #define max(a,b) ((a) > (b) ? (a) : (b))
  15
  16
  17 /****************************************************************/
  18 /* Data Structures                                              */
  19 /****************************************************************/
  20 typedef struct tuple_t {
  21         gs_uint32_t val;
  22         gs_uint32_t gap;
  23         gs_uint32_t del;
  24         gs_uint32_t next;
  25 } tuple_t;
  26
  27 typedef struct supertuple_t {
  28         gs_uint32_t val;
  29         gs_uint32_t gap;
  30         gs_uint32_t del;
  31         struct supertuple_t *next;
  32 } supertuple_t;
  33
  34 /****************************************************************/
  35 typedef gs_uint32_t val_type;
  36
  37 typedef struct skipnode {
  38         val_type val;
  39         gs_uint32_t next;
  40         gs_uint32_t down;
  41 } skipnode_t;
  42
  43 typedef struct skipdir {
  44         gs_uint32_t height;                             // height of tree
  45         gs_uint32_t freeptr;                            // cursor space stack
  46         gs_uint32_t headptr[SKIPDIR_HEIGHT_MAX];        // ptrs to levels
  47         skipnode_t list[SKIPDIR_SIZE+1];
  48 } skipdir_t;
  49
  50 /****************************************************************/
  51
  52 typedef struct quant_udaf_hfta0_struct_t {
  53         gs_uint32_t nelts;              // 4 bytes
  54         supertuple_t *t;                // 8 bytes
  55 } quant_udaf_hfta0_struct_t;
  56
  57 typedef struct quant_udaf_lfta1_struct_t {
  58         gs_uint32_t nelts;
  59         gs_uint32_t samples[QUANT_LFTA1_SIZE];
  60 } quant_udaf_lfta1_struct_t;
  61
  62 typedef struct quant_udaf_hfta1_struct_t {
  63         gs_uint32_t nelts;              // 4 bytes
  64         supertuple_t *t;                // 8 bytes
  65 } quant_udaf_hfta1_struct_t;
  66
  67 typedef struct quant_udaf_lfta2_struct_t {
  68         gs_uint32_t nelts;
  69         gs_uint32_t freeptr;
  70         gs_uint32_t usedptr;
  71         tuple_t t[QUANT_LFTA2_SIZE+1];
  72 } quant_udaf_lfta2_struct_t;
  73
  74 typedef struct quant_udaf_hfta2_struct_t {
  75         gs_uint32_t nelts;              // 4 bytes
  76         supertuple_t *t;                // 8 bytes
  77 } quant_udaf_hfta2_struct_t;
  78
  79 typedef struct quant_udaf_lfta3_struct_t {
  80         gs_uint32_t nelts;
  81         gs_uint32_t freeptr;
  82         gs_uint32_t usedptr;
  83         gs_uint32_t circptr;
  84         gs_uint32_t size;
  85         tuple_t t[QUANT_LFTA3_SIZE+1];
  86         skipdir_t sd;
  87 } quant_udaf_lfta3_struct_t;
  88
  89 typedef struct quant_udaf_hfta3_struct_t {
  90         gs_uint32_t nelts;              // 4 bytes
  91         supertuple_t *t;                // 8 bytes
  92 } quant_udaf_hfta3_struct_t;
  93
  94
  95
  96 /*************************** Version 0 **************************/
  97 /* Version 0: HFTA-only                                         */
  98 /****************************************************************/
  99 void quant_udaf_hfta0_print(quant_udaf_hfta0_struct_t *s)
 100 {
 101         supertuple_t *t;
 102
 103         gslog(LOG_DEBUG,"hfta nelts = %u\n",s->nelts);
 104         gslog(LOG_DEBUG,"HFTA tuples:\n");
 105         for (t=s->t; t != NULL; t=t->next) {
 106                 gslog(LOG_DEBUG,"(%u, %u, %u)\n",t->val,t->gap,t->del);
 107         }
 108 }
 109
 110 void quant_udaf_hfta0_compress(quant_udaf_hfta0_struct_t *s)
 111 {
 112         supertuple_t *t=s->t, *d;
 113         gs_uint32_t threshold;
 114
 115         threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(s->nelts));
 116         if ((t == NULL) || (t->next == NULL)) return;
 117         d = t->next;
 118         while ((d != NULL) && (d->next != NULL)) {
 119                 if (d->gap+d->next->gap+d->next->del < threshold) {
 120                         d->next->gap += d->gap;
 121                         t->next = d->next;
 122                         free(d);
 123                 }
 124                 t = t->next;
 125                 d = t->next;
 126         }
 127 }
 128
 129 /****************************************************************/
 130 /* HFTA0 functions                                              */
 131 /****************************************************************/
 132 void quant_udaf_hfta0_HFTA_AGGR_INIT_(gs_sp_t b)
 133 {
 134         quant_udaf_hfta0_struct_t *s = (quant_udaf_hfta0_struct_t *)b;
 135         s->nelts = 0;
 136         s->t = NULL;
 137 }
 138
 139 void quant_udaf_hfta0_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_uint32_t v)
 140 {
 141         quant_udaf_hfta0_struct_t *s = (quant_udaf_hfta0_struct_t *)b;
 142         supertuple_t *t=s->t;
 143         supertuple_t *newptr;
 144         gs_uint32_t threshold;
 145         gs_uint32_t val, gap;
 146         gs_uint32_t obj;
 147
 148         s->nelts++;
 149         // left boundary case
 150         if ((!t) || (v <= t->val)) {
 151                 newptr = (supertuple_t *)malloc(sizeof(supertuple_t));
 152                 if (!newptr) {
 153                         gslog(LOG_ALERT, "Out of space.\n");
 154                         return;
 155                 }
 156                 newptr->val = v;
 157                 newptr->gap = 1;
 158                 newptr->del = 0;
 159                 newptr->next = s->t;
 160                 s->t = newptr;
 161                 return;
 162         }
 163
 164         // locate position that sandwiches v
 165         while ((t->next) && (t->next->val < v))
 166                 t = t->next;
 167
 168         // right boundary case
 169         if (!t->next) {
 170                 // create newptr node
 171                 newptr = (supertuple_t *)malloc(sizeof(supertuple_t));
 172                 newptr->val = v;
 173                 newptr->gap = 1;
 174                 newptr->del = 0;
 175                 newptr->next = NULL;
 176                 t->next = newptr;
 177         }
 178         // non-boundary case
 179         else {
 180                 obj = t->gap+t->next->gap+t->next->del;
 181                 threshold = (gs_uint32_t)ceil(2.0 * QUANT_EPS * (float)s->nelts);
 182                 if (obj <= threshold) {
 183                         // insert into existing bucket
 184                         t->next->gap++;
 185                 }
 186                 else {
 187                         newptr = (supertuple_t *)malloc(sizeof(supertuple_t));
 188                         newptr->val = v;
 189                         newptr->gap = 1;
 190                         newptr->del = t->next->gap+t->next->del-1;
 191                         newptr->next = t->next;
 192                         t->next = newptr;
 193                 }
 194         }
 195         quant_udaf_hfta0_compress(s);
 196 }
 197
 198 void quant_udaf_hfta0_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b)
 199 {
 200         r->length = sizeof(quant_udaf_hfta0_struct_t);
 201         r->offset = (gs_p_t )b;
 202         r->reserved = SHALLOW_COPY;
 203 }
 204
 205 void quant_udaf_hfta0_HFTA_AGGR_DESTROY_(gs_sp_t b)
 206 {
 207         quant_udaf_hfta0_struct_t *s = (quant_udaf_hfta0_struct_t *)b;
 208         supertuple_t *t=s->t, *n;
 209         while(t){
 210                 n=t->next;
 211                 free(t);
 212                 t=n;
 213         }
 214
 215         return;
 216 }
 217
 218
 219 /****************************************************************/
 220 /* HFTA0 Extraction functions                                   */
 221 /****************************************************************/
 222 gs_uint32_t extr_quant_hfta0_fcn(vstring *v, gs_float_t phi)
 223 {
 224 //printf("In extr_quant_hfta0_fcn offset=%llx length=%d\n",v->offset, v->length);
 225         quant_udaf_hfta0_struct_t *vs = (quant_udaf_hfta0_struct_t *)(v->offset);
 226 //printf("nelts=%d t=%llx\n",vs->nelts, (unsigned long long int)(vs->t));
 227         supertuple_t *t, *p;
 228         gs_uint32_t nelts=0;
 229         gs_int32_t rmin=0, rmax, rank, ropt=INT_MAX;
 230         gs_uint32_t count=0;
 231
 232         for (t=vs->t; t != NULL; t=t->next) {
 233 //printf("in loop.\n");
 234 //printf("gap is %d\n",t->gap);
 235                 nelts += t->gap;
 236                 count++;
 237         }
 238         rank = (gs_int32_t) (phi*(float)nelts);
 239
 240         for (t=vs->t; t != NULL; t=t->next) {
 241                 rmin += t->gap;
 242                 rmax = rmin+t->del;
 243                 if (max(abs(rmin-rank), abs(rmax-rank)) < ropt) {
 244                         p = t;
 245                         ropt = max(abs(rmin-rank), abs(rmax-rank));
 246                 }
 247         }
 248         return p->val;
 249 }
 250
 251 gs_uint32_t extr_med_hfta0_fcn(vstring *v)
 252 {
 253         return extr_quant_hfta0_fcn(v, 0.5);
 254 }
 255
 256 gs_uint32_t extr_quant_hfta0_space(vstring *v)
 257 {
 258         quant_udaf_hfta0_struct_t *vs = (quant_udaf_hfta0_struct_t *)(v->offset);
 259         supertuple_t *t;
 260         gs_uint32_t count=0;
 261
 262         for (t=vs->t; t != NULL; t=t->next)
 263                 count++;
 264         return count;
 265 }
 266
 267
 268 /*************************** Version 3 **************************/
 269 /* Version 3: LFTA-medium                                       */
 270 /****************************************************************/
 271 void quant_hfta3_print(quant_udaf_hfta3_struct_t *s)
 272 {
 273         supertuple_t *t;
 274
 275 //printf("In quant_hfta3_print, s=%llx, t=%llx\n",(unsigned long long int)s,(unsigned long long int)(s->t));
 276         gslog(LOG_DEBUG,"HFTA tuples:\n");
 277         for (t=s->t; t != NULL; t=t->next) {
 278                 gslog(LOG_DEBUG,"(%u, %u, %u)\n",t->val,t->gap,t->del);
 279         }
 280 }
 281
 282 void quant_hfta3_compress(quant_udaf_hfta3_struct_t *s)
 283 {
 284         supertuple_t *t=s->t, *d;
 285         gs_uint32_t threshold;
 286
 287         threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(s->nelts));
 288         if ((t == NULL) || (t->next == NULL)) return;
 289         d = t->next;
 290         while ((d != NULL) && (d->next != NULL)) {
 291                 if (d->gap+d->next->gap+d->next->del < threshold) {
 292                         d->next->gap += d->gap;
 293                         t->next = d->next;
 294                         free(d);
 295                 }
 296                 t = t->next;
 297                 d = t->next;
 298         }
 299 }
 300
 301
 302 /****************************************************************/
 303 /* HFTA3 functions                                              */
 304 /****************************************************************/
 305 void quant_udaf_hfta3_HFTA_AGGR_INIT_(gs_sp_t b)
 306 {
 307         quant_udaf_hfta3_struct_t *s = (quant_udaf_hfta3_struct_t *)b;
 308         s->nelts = 0;
 309         s->t = NULL;
 310 }
 311
 312 void quant_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v)
 313 {
 314         quant_udaf_hfta3_struct_t *s = (quant_udaf_hfta3_struct_t *)b;
 315         quant_udaf_lfta3_struct_t *vs = (quant_udaf_lfta3_struct_t *)(v->offset);
 316         supertuple_t *t=s->t, *tprev=NULL;
 317         tuple_t *u=vs->t;
 318         supertuple_t *newptr;
 319         gs_uint32_t uptr = vs->usedptr;
 320         gs_uint32_t threshold;
 321
 322         if (uptr == 0) return;
 323         //if (v->length != sizeof(quant_udaf_lfta3_struct_t)) return;
 324
 325         threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(vs->nelts));
 326         while (uptr != 0) {
 327                 if ((u[uptr].next != 0) && (u[uptr].gap+u[u[uptr].next].gap+u[u[uptr].next].del < threshold)) {
 328                         u[u[uptr].next].gap += u[uptr].gap;
 329                 }
 330                 else {
 331                         // find position in superstructure
 332                         while ((t != NULL) && (t->val <= u[uptr].val)) {
 333                                 if (t->val == u[uptr].val) {
 334                                         t->gap += u[uptr].gap;
 335                                         t->del += u[uptr].del;
 336                                         uptr = u[uptr].next;
 337                                         if (!uptr) break;
 338                                 }
 339                                 else {
 340                                         t->del += u[uptr].gap+u[uptr].del-1;
 341                                 }
 342                                 tprev = t;
 343                                 t = t->next;
 344                         }
 345                         if (!uptr) break;
 346                         // create newptr node
 347                         newptr = (supertuple_t *)malloc(sizeof(supertuple_t));
 348                         newptr->val = u[uptr].val;
 349                         newptr->gap = u[uptr].gap;
 350                         newptr->del = u[uptr].del;
 351                         if (t != NULL)
 352                                 newptr->del += t->gap + t->del - 1;
 353                         // merge into superstructure
 354                         newptr->next = t;
 355                         if (tprev == NULL)
 356                                 s->t = newptr;
 357                         else
 358                                 tprev->next = newptr;
 359                         tprev = newptr;
 360                         s->nelts += u[uptr].gap;
 361                 }
 362                 uptr = u[uptr].next;
 363         }
 364         quant_hfta3_compress(s);
 365 //quant_hfta3_print(s);
 366 //printf("exiting quant_udaf_hfta3_HFTA_AGGR_UPDATE_, s=%llx, t=%llx\n",(unsigned long long int)s,(unsigned long long int)(s->t));
 367 }
 368
 369 void quant_udaf_hfta3_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b)
 370 {
 371         r->length = sizeof(quant_udaf_hfta3_struct_t);
 372         r->offset = (gs_p_t )b;
 373         r->reserved = SHALLOW_COPY;
 374
 375         quant_udaf_hfta3_struct_t *s = (quant_udaf_hfta3_struct_t *)b;
 376 //printf("In quant_udaf_hfta3_HFTA_AGGR_OUTPUT_, s=%llx, t=%llx\n\n",(unsigned long long int)s,(unsigned long long int)(s->t));
 377 }
 378
 379 void quant_udaf_hfta3_HFTA_AGGR_DESTROY_(gs_sp_t b)
 380 {
 381         return;
 382 }
 383
 384 /****************************************************************/
 385 /* HFTA3 Extraction functions                                   */
 386 /****************************************************************/
 387 gs_uint32_t extr_quant_hfta3_fcn(vstring *v, gs_float_t  phi)
 388 {
 389         quant_udaf_hfta3_struct_t *vs = (quant_udaf_hfta3_struct_t *)(v->offset);
 390         supertuple_t *t, *p;
 391         gs_uint32_t nelts=0;
 392         gs_int32_t rmin=0, rmax, rank, ropt=INT_MAX;
 393         gs_uint32_t count=0;
 394
 395         for (t=vs->t; t != NULL; t=t->next) {
 396                 nelts += t->gap;
 397                 count++;
 398         }
 399         rank = (gs_int32_t) (phi*(float)nelts);
 400
 401         for (t=vs->t; t != NULL; t=t->next) {
 402                 rmin += t->gap;
 403                 rmax = rmin+t->del;
 404                 if (max(abs(rmin-rank), abs(rmax-rank)) < ropt) {
 405                         p = t;
 406                         ropt = max(abs(rmin-rank), abs(rmax-rank));
 407                 }
 408         }
 409         return p->val;
 410 }
 411
 412 gs_uint32_t extr_med_hfta3_fcn(vstring *v)
 413 {
 414         return extr_quant_hfta3_fcn(v, 0.5);
 415 }
 416
 417 gs_uint32_t extr_quant_hfta3_space(vstring *v)
 418 {
 419         quant_udaf_hfta3_struct_t *vs = (quant_udaf_hfta3_struct_t *)(v->offset);
 420         supertuple_t *t;
 421         gs_uint32_t count=0;
 422
 423         for (t=vs->t; t != NULL; t=t->next)
 424                 count++;
 425         return count;
 426 }