src/lib/gscphftaaux/flip_udaf.cc

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