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 #include <algorithm>    // std::sort
   8
   9 #include<iostream>
  10
  11 #include "udaf_common.h"
  12 //#define QUANT_LFTA1_SIZE 729
  13 //#define QUANT_LFTA2_SIZE 181
  14 //#define QUANT_LFTA3_SIZE 50
  15 //#define QUANT_EPS 0.01
  16 //#define SKIPDIR_SIZE 100
  17 //#define SKIPDIR_HEIGHT_MAX 7
  18
  19
  20 //#define max(a,b) ((a) > (b) ? (a) : (b))
  21
  22 using namespace std;
  23
  24 // current use
  25 //      hfta_only: quant_udaf_hfta0
  26 //      extraction: extr_quant_hfta0_fcn extr_med_hfta0_fcn extr_quant_hfta0_space
  27 //      lfta/hfta: quant_udaf_lfta3 quant_udaf_hfta3
  28
  29 // TODO
  30 //              - Should the hfta part of the hfta/lfta split (hfta3)
  31 //                match the hfta-only implementation (hftaZ)?
  32 //              - On out-of-space conditions, try a compress before
  33 //                discarding the sample.  If that happens, can the rate
  34 //                of compresses be decreased?
  35 //              - Can the lfta part be made to work with actual compression?
  36 //                if not, change the implementation to gather a collection
  37 //                of samples, then send them up.  This should decrease
  38 //                lfta space use and reduce the cost of adding to the hfta.
  39
  40 /****************************************************************/
  41 /* Data Structures                                              */
  42 /****************************************************************/
  43
  44
  45 /****************************************************************/
  46 template <class T> struct tuple_t {
  47         T val;
  48         gs_uint32_t gap;
  49         gs_uint32_t del;
  50         gs_uint32_t next;
  51 };
  52
  53 template <class T> struct skipnode_t {
  54         T val;
  55         gs_uint32_t next;
  56         gs_uint32_t down;
  57 };
  58
  59 template <class T> struct skipdir_t {
  60         gs_uint32_t height;                             // height of tree
  61         gs_uint32_t freeptr;                            // cursor space stack
  62         gs_uint32_t headptr[SKIPDIR_HEIGHT_MAX];        // ptrs to levels
  63         skipnode_t<T> list[SKIPDIR_SIZE+1];
  64 };
  65
  66 /****************************************************************/
  67
  68
  69
  70
  71 template <class T> struct quant_udaf_lfta3_struct_t {
  72         gs_uint32_t nelts;
  73         gs_uint32_t freeptr;
  74         gs_uint32_t usedptr;
  75         gs_uint32_t circptr;
  76         gs_uint32_t size;
  77         tuple_t<T> t[QUANT_LFTA3_SIZE+1];
  78         skipdir_t<T> sd;
  79 };
  80
  81
  82 template <class T> struct supertuple3_t{        // hfta/lfta
  83         T val;
  84         gs_uint32_t gap;
  85         gs_uint32_t del;
  86         struct supertuple3_t<T> *next;
  87 };
  88
  89 template <class T> struct supertupleZ_t{
  90         T val;
  91         gs_uint32_t gap;
  92         gs_uint32_t del;
  93         gs_int32_t next;
  94 };
  95
  96
  97 template <class T> struct quant_udaf_hfta_struct_t {
  98         gs_uint32_t nelts;              // 4 bytes
  99         short int used_head;
 100         short int free_head;
 101         supertupleZ_t<T> *st;
 102         gs_uint32_t *vals;
 103         supertuple3_t<T> *t;            // 8 bytes
 104 };
 105
 106
 107
 108
 109
 110
 111 /*************************** Version 3 **************************/
 112 /* Version 3: LFTA-medium                                       */
 113 /****************************************************************/
 114 template <class T> void quant_hfta3_print(quant_udaf_hfta_struct_t<T> *s)
 115 {
 116         supertuple3_t<T> *t;
 117
 118 //printf("In quant_hfta3_print, s=%llx, t=%llx\n",(unsigned long long int)s,(unsigned long long int)(s->t));
 119         gslog(LOG_DEBUG,"HFTA tuples:\n");
 120         for (t=s->t; t != NULL; t=t->next) {
 121                 gslog(LOG_DEBUG,"(%u, %u, %u)\n",t->val,t->gap,t->del);
 122         }
 123 }
 124
 125 template <class T> void quant_hfta3_compress(quant_udaf_hfta_struct_t<T> *s)
 126 {
 127         supertuple3_t<T> *t=s->t, *d;
 128         gs_uint32_t threshold;
 129
 130         threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(s->nelts));
 131         if ((t == NULL) || (t->next == NULL)) return;
 132         d = t->next;
 133         while ((d != NULL) && (d->next != NULL)) {
 134                 if (d->gap+d->next->gap+d->next->del < threshold) {
 135                         d->next->gap += d->gap;
 136                         t->next = d->next;
 137                         free(d);
 138                 }
 139                 t = t->next;
 140                 d = t->next;
 141         }
 142 }
 143
 144
 145 /****************************************************************/
 146 /* HFTA3 functions                                              */
 147 /****************************************************************/
 148
 149 //              since it does mallocs instead of allocations in a fixed block of memory
 150 template <class T> void quant_udaf_hfta3_HFTA_AGGR_INIT_(gs_sp_t b) {
 151 //printf("sizeof quant_udaf_hfta_struct_t<T> is %lu\n",sizeof(quant_udaf_hfta_struct_t<T>));
 152 //printf("sizeof quant_udaf_lfta3_struct_t<T> is %lu\n",sizeof(quant_udaf_lfta3_struct_t<T>));
 153         quant_udaf_hfta_struct_t<T> *s = (quant_udaf_hfta_struct_t<T> *)b;
 154 //printf("quant_udaf_hfta3_HFTA_AGGR_INIT_ size is %lu\n",sizeof(quant_udaf_hfta_struct_t<T>));
 155         s->nelts = 0;
 156         s->t = NULL;
 157         s->vals = NULL;
 158         s->st = NULL;
 159         s->used_head = -1;
 160         s->free_head = -1;
 161 }
 162
 163 void quant_ui_udaf_hfta3_HFTA_AGGR_INIT_(gs_sp_t b){
 164         quant_udaf_hfta3_HFTA_AGGR_INIT_<gs_uint32_t>(b);
 165 }
 166 void quant_i_udaf_hfta3_HFTA_AGGR_INIT_(gs_sp_t b){
 167         quant_udaf_hfta3_HFTA_AGGR_INIT_<gs_int32_t>(b);
 168 }
 169 void quant_ul_udaf_hfta3_HFTA_AGGR_INIT_(gs_sp_t b){
 170         quant_udaf_hfta3_HFTA_AGGR_INIT_<gs_uint64_t>(b);
 171 }
 172 void quant_l_udaf_hfta3_HFTA_AGGR_INIT_(gs_sp_t b){
 173         quant_udaf_hfta3_HFTA_AGGR_INIT_<gs_int64_t>(b);
 174 }
 175 void quant_f_udaf_hfta3_HFTA_AGGR_INIT_(gs_sp_t b){
 176         quant_udaf_hfta3_HFTA_AGGR_INIT_<gs_float_t>(b);
 177 }
 178
 179 template <class T> void quant_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v) {
 180         quant_udaf_hfta_struct_t<T> *s = (quant_udaf_hfta_struct_t<T> *)b;
 181         quant_udaf_lfta3_struct_t<T> *vs = (quant_udaf_lfta3_struct_t<T> *)(v->offset);
 182         supertuple3_t<T> *t=s->t, *tprev=NULL;
 183         tuple_t<T> *u=vs->t;
 184         supertuple3_t<T> *newptr;
 185         gs_uint32_t uptr = vs->usedptr;
 186         gs_uint32_t threshold;
 187
 188         if (uptr == 0) return;
 189         //if (v->length != sizeof(quant_udaf_lfta3_struct_t)) return;
 190
 191         threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(vs->nelts));
 192         while (uptr != 0) {
 193 //printf("uptr=%d\n",uptr);
 194                 if ((u[uptr].next != 0) && (u[uptr].gap+u[u[uptr].next].gap+u[u[uptr].next].del < threshold)) {
 195                         u[u[uptr].next].gap += u[uptr].gap;
 196                 }
 197                 else {
 198                         // find position in superstructure
 199                         while ((t != NULL) && (t->val <= u[uptr].val)) {
 200                                 if (t->val == u[uptr].val) {
 201                                         t->gap += u[uptr].gap;
 202                                         t->del += u[uptr].del;
 203                                         uptr = u[uptr].next;
 204                                         if (!uptr) break;
 205                                 }
 206                                 else {
 207                                         t->del += u[uptr].gap+u[uptr].del-1;
 208                                 }
 209                                 tprev = t;
 210                                 t = t->next;
 211                         }
 212                         if (!uptr) break;
 213                         // create newptr node
 214                         newptr = (supertuple3_t<T> *)malloc(sizeof(supertuple3_t<T>));
 215                         newptr->val = u[uptr].val;
 216                         newptr->gap = u[uptr].gap;
 217                         newptr->del = u[uptr].del;
 218                         if (t != NULL)
 219                                 newptr->del += t->gap + t->del - 1;
 220                         // merge into superstructure
 221                         newptr->next = t;
 222                         if (tprev == NULL)
 223                                 s->t = newptr;
 224                         else
 225                                 tprev->next = newptr;
 226                         tprev = newptr;
 227                         s->nelts += u[uptr].gap;
 228                 }
 229                 uptr = u[uptr].next;
 230         }
 231         quant_hfta3_compress<T>(s);
 232 //quant_hfta3_print(s);
 233 //printf("exiting quant_udaf_hfta3_HFTA_AGGR_UPDATE_, s=%llx, t=%llx\n",(unsigned long long int)s,(unsigned long long int)(s->t));
 234 }
 235
 236 void quant_ui_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v){
 237         quant_udaf_hfta3_HFTA_AGGR_UPDATE_<gs_uint32_t>(b, v);
 238 }
 239 void quant_i_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v){
 240         quant_udaf_hfta3_HFTA_AGGR_UPDATE_<gs_int32_t>(b, v);
 241 }
 242 void quant_ul_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v){
 243         quant_udaf_hfta3_HFTA_AGGR_UPDATE_<gs_uint64_t>(b, v);
 244 }
 245 void quant_l_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v){
 246         quant_udaf_hfta3_HFTA_AGGR_UPDATE_<gs_int64_t>(b, v);
 247 }
 248 void quant_f_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v){
 249         quant_udaf_hfta3_HFTA_AGGR_UPDATE_<gs_float_t>(b, v);
 250 }
 251
 252 template <class T> void quant_udaf_hfta3_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
 253         r->length = sizeof(quant_udaf_hfta_struct_t<T>);
 254         r->offset = (gs_p_t )b;
 255         r->reserved = SHALLOW_COPY;
 256
 257         quant_udaf_hfta_struct_t<T> *s = (quant_udaf_hfta_struct_t<T> *)b;
 258 //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));
 259 }
 260
 261 void quant_ui_udaf_hfta3_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
 262         quant_udaf_hfta3_HFTA_AGGR_OUTPUT_<gs_uint32_t>(r, b);
 263 }
 264 void quant_i_udaf_hfta3_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
 265         quant_udaf_hfta3_HFTA_AGGR_OUTPUT_<gs_int32_t>(r, b);
 266 }
 267 void quant_ul_udaf_hfta3_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
 268         quant_udaf_hfta3_HFTA_AGGR_OUTPUT_<gs_uint64_t>(r, b);
 269 }
 270 void quant_l_udaf_hfta3_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
 271         quant_udaf_hfta3_HFTA_AGGR_OUTPUT_<gs_int64_t>(r, b);
 272 }
 273 void quant_f_udaf_hfta3_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
 274         quant_udaf_hfta3_HFTA_AGGR_OUTPUT_<gs_float_t>(r, b);
 275 }
 276
 277 template <class T> void quant_udaf_hfta3_HFTA_AGGR_DESTROY_(gs_sp_t b) {
 278     quant_udaf_hfta_struct_t<T> *s = (quant_udaf_hfta_struct_t<T> *)b;
 279         supertuple3_t<T> *t=s->t, *n;
 280         while(t){
 281                 n=t->next;
 282                 free(t);
 283                 t=n;
 284         }
 285         return;
 286 }
 287
 288 void quant_ui_udaf_hfta3_HFTA_AGGR_DESTROY_(gs_sp_t b) {
 289         quant_udaf_hfta3_HFTA_AGGR_DESTROY_<gs_uint32_t>(b);
 290 }
 291 void quant_i_udaf_hfta3_HFTA_AGGR_DESTROY_(gs_sp_t b) {
 292         quant_udaf_hfta3_HFTA_AGGR_DESTROY_<gs_int32_t>(b);
 293 }
 294 void quant_ul_udaf_hfta3_HFTA_AGGR_DESTROY_(gs_sp_t b) {
 295         quant_udaf_hfta3_HFTA_AGGR_DESTROY_<gs_uint64_t>(b);
 296 }
 297 void quant_l_udaf_hfta3_HFTA_AGGR_DESTROY_(gs_sp_t b) {
 298         quant_udaf_hfta3_HFTA_AGGR_DESTROY_<gs_int64_t>(b);
 299 }
 300 void quant_f_udaf_hfta3_HFTA_AGGR_DESTROY_(gs_sp_t b) {
 301         quant_udaf_hfta3_HFTA_AGGR_DESTROY_<gs_float_t>(b);
 302 }
 303
 304 /****************************************************************/
 305 /* HFTA3 Extraction functions                                   */
 306 /****************************************************************/
 307 template <class T> T extr_quant_hfta3_fcn(vstring *v, gs_float_t  phi) {
 308         quant_udaf_hfta_struct_t<T> *vs = (quant_udaf_hfta_struct_t<T> *)(v->offset);
 309         supertuple3_t<T> *t, *p;
 310         gs_uint32_t nelts=0;
 311         gs_int32_t rmin=0, rmax, rank, ropt=INT_MAX;
 312         gs_uint32_t count=0;
 313
 314         for (t=vs->t; t != NULL; t=t->next) {
 315                 nelts += t->gap;
 316                 count++;
 317         }
 318         rank = (gs_int32_t) (phi*(float)nelts);
 319
 320         for (t=vs->t; t != NULL; t=t->next) {
 321                 rmin += t->gap;
 322                 rmax = rmin+t->del;
 323                 if (max(abs(rmin-rank), abs(rmax-rank)) < ropt) {
 324                         p = t;
 325                         ropt = max(abs(rmin-rank), abs(rmax-rank));
 326                 }
 327         }
 328         return p->val;
 329 }
 330
 331 /*
 332 gs_uint32_t extr_quant_ui_hfta3_fcn(vstring *v, gs_float_t  phi){
 333         return extr_quant_hfta3_fcn<gs_uint32_t>(v, phi);
 334 }
 335 gs_int32_t extr_quant_i_hfta3_fcn(vstring *v, gs_float_t  phi){
 336         return extr_quant_hfta3_fcn<gs_int32_t>(v, phi);
 337 }
 338 gs_uint64_t extr_quant_ul_hfta3_fcn(vstring *v, gs_float_t  phi){
 339         return extr_quant_hfta3_fcn<gs_uint64_t>(v, phi);
 340 }
 341 gs_int64_t extr_quant_l_hfta3_fcn(vstring *v, gs_float_t  phi){
 342         return extr_quant_hfta3_fcn<gs_int64_t>(v, phi);
 343 }
 344 gs_float_t extr_quant_f_hfta3_fcn(vstring *v, gs_float_t  phi){
 345         return extr_quant_hfta3_fcn<gs_float_t>(v, phi);
 346 }
 347 */
 348
 349 template <class T> T extr_med_hfta3_fcn(vstring *v)
 350 {
 351         return extr_quant_hfta3_fcn<T>(v, 0.5);
 352 }
 353
 354 gs_uint32_t extr_ui_med_hfta3_fcn(vstring *v){
 355         return extr_med_hfta3_fcn<gs_uint32_t>(v);
 356 }
 357 gs_int32_t extr_i_med_hfta3_fcn(vstring *v){
 358         return extr_med_hfta3_fcn<gs_int32_t>(v);
 359 }
 360 gs_uint64_t extr_ul_med_hfta3_fcn(vstring *v){
 361         return extr_med_hfta3_fcn<gs_uint64_t>(v);
 362 }
 363 gs_int64_t extr_l_med_hfta3_fcn(vstring *v){
 364         return extr_med_hfta3_fcn<gs_int64_t>(v);
 365 }
 366 gs_float_t extr_f_med_hfta3_fcn(vstring *v){
 367         return extr_med_hfta3_fcn<gs_float_t>(v);
 368 }
 369
 370 template <class T> gs_uint32_t extr_quant_hfta3_space(vstring *v)
 371 {
 372         quant_udaf_hfta_struct_t<T> *vs = (quant_udaf_hfta_struct_t<T> *)(v->offset);
 373         supertuple3_t<T> *t;
 374         gs_uint32_t count=0;
 375
 376         for (t=vs->t; t != NULL; t=t->next)
 377                 count++;
 378         return count;
 379 }
 380
 381
 382
 383 //////////////////////////////////////////////////////////////////////
 384 //               hfta-only code V3
 385
 386 //      This approach stores values in a buffer until
 387 //      the buffer gets filled, and then puts the values into
 388 //      the approximate quantile udaf.
 389 //
 390 //      Further, the code is templatized
 391
 392 #define MAX_QUANT_ELEMS 128
 393 #define MAX_VAL_ELEMS 50
 394 //      MAX_VAL_ELEMS must be less than MAX_QUANT_ELEMS,
 395 //      and probably somewhat less than 1/QUANT_EPS
 396 //      Another consideration is space use, as most groups are small,
 397 //      so you want MAX_VAL_ELEMS to be as small as possible
 398 //      and still capture most small groups.
 399
 400 //      To really optimize for space, use a doubling realloc
 401 //      strategy until the doubled size would be 2K bytes,
 402 //      and then instead of doubling, insert into the approx
 403 //      structure.
 404 //
 405
 406 /*
 407 template <class T> struct supertupleZ_t{
 408         T val;
 409         gs_uint32_t gap;
 410         gs_uint32_t del;
 411         gs_int32_t next;
 412 };
 413 */
 414
 415 /*
 416 template <class T> struct quant_udaf_hftaZ_struct_t{
 417         gs_uint32_t nelts;
 418         short int used_head;
 419         short int free_head;
 420         supertupleZ_t<T> *st;
 421         gs_uint32_t *vals;
 422 };
 423 */
 424
 425
 426 template <class T> void quant_udaf_hftaZ_compress(quant_udaf_hfta_struct_t<T> *s)
 427 {
 428         int t = s->used_head, d, d_next=-1;
 429         gs_uint32_t threshold;
 430         supertupleZ_t<T> *st = s->st;
 431
 432         threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(s->nelts));
 433         if ((t == -1) || (st[t].next == -1)) return;
 434         d = st[t].next;
 435         while ((d != -1) && (st[d].next != -1)) {
 436                 d_next = st[d].next;
 437                 if (st[d].gap + st[d_next].gap + st[d_next].del < threshold) {
 438                         st[d_next].gap += st[d].gap;
 439                         st[t].next = st[d].next;
 440                         st[d].next = s->free_head;
 441                         s->free_head = d;
 442                 }
 443                 t = st[t].next;
 444                 d = st[t].next;
 445         }
 446 }
 447
 448 template <class T>  void quant_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b) {
 449         quant_udaf_hfta_struct_t<T> *s = (quant_udaf_hfta_struct_t<T> *)b;
 450 //printf("quant_udaf_hftaZ_HFTA_AGGR_INIT_ size is %lu\n",sizeof(quant_udaf_hfta_struct_t<T>));
 451         s->nelts = 0;
 452         s->st=NULL;
 453         s->vals = (gs_uint32_t *)malloc(MAX_VAL_ELEMS*sizeof(T));
 454         s->t = NULL;
 455 }
 456
 457 template <class T>  void quant_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, T v) {
 458         quant_udaf_hfta_struct_t<T> *s = (quant_udaf_hfta_struct_t<T> *)b;
 459         if(s->nelts<MAX_VAL_ELEMS){
 460                 s->vals[s->nelts] = v;
 461                 s->nelts++;
 462                 return;
 463         }
 464
 465         if(s->nelts==MAX_VAL_ELEMS){
 466 //              qsort(s->vals, MAX_VAL_ELEMS, sizeof(gs_uint32_t), compare_gs_uint32);
 467                 sort(s->vals,s->vals+s->nelts);
 468                 s->st = (supertupleZ_t<T> *)malloc(MAX_QUANT_ELEMS*sizeof(quant_udaf_hfta_struct_t<T>));
 469                 for(int i=0;i<MAX_VAL_ELEMS;++i){
 470                         s->st[i].val = s->vals[i];
 471                         s->st[i].gap = 1;
 472                         s->st[i].del = 0;
 473                         s->st[i].next = i+1;
 474                 }
 475                 s->st[MAX_VAL_ELEMS-1].next = -1;
 476                 for(int i=MAX_VAL_ELEMS; i<MAX_QUANT_ELEMS; ++i){
 477                         s->st[i].next = i+1;
 478                 }
 479                 s->st[MAX_QUANT_ELEMS-1].next = -1;
 480                 s->free_head = MAX_VAL_ELEMS;
 481                 s->used_head = 0;
 482                 free(s->vals);
 483                 s->vals = NULL;
 484         }
 485
 486 //              s->nelts > MAX_VAL_ELEMS
 487         int t=s->used_head;
 488         int newptr;
 489         gs_uint32_t threshold;
 490         gs_uint32_t val, gap;
 491         gs_uint32_t obj;
 492         supertupleZ_t<T> *st = s->st;
 493
 494         s->nelts++;
 495         // left boundary case
 496         if ((t==-1) || (v <= st[t].val)) {
 497                 newptr = s->free_head;
 498                 if (newptr==-1) {
 499                         gslog(LOG_ALERT, "Out of space in quant_udaf_hftaZ_HFTA_AGGR_UPDATE_.\n");
 500                         cout << v << endl;
 501                         quant_udaf_hftaZ_compress<T>(s);
 502                         return;
 503                 }
 504                 s->free_head = st[newptr].next;
 505                 st[newptr].val = v;
 506                 st[newptr].gap = 1;
 507                 st[newptr].del = 0;
 508                 st[newptr].next = s->used_head;
 509                 s->used_head = newptr;
 510                 return;
 511         }
 512
 513         // locate position that sandwiches v
 514         int ptr=t;
 515         while ((st[ptr].next!=-1) && (st[st[ptr].next].val < v))
 516                 ptr = st[ptr].next;
 517
 518         // right boundary case
 519         if (st[ptr].next==-1) {
 520                 // create newptr node
 521                 newptr = s->free_head;
 522                 if (newptr==-1) {
 523                         gslog(LOG_ALERT, "Out of space in quant_udaf_hftaZ_HFTA_AGGR_UPDATE_.\n");
 524                         quant_udaf_hftaZ_compress<T>(s);
 525                         return;
 526                 }
 527                 s->free_head = st[newptr].next;
 528                 st[newptr].val = v;
 529                 st[newptr].gap = 1;
 530                 st[newptr].del = 0;
 531                 st[newptr].next =-1;
 532                 st[ptr].next = newptr;
 533         }
 534         // non-boundary case
 535         else {
 536                 int nextptr = st[ptr].next;
 537                 obj = st[ptr].gap + st[nextptr].gap + st[nextptr].del;
 538                 threshold = (gs_uint32_t)ceil(2.0 * QUANT_EPS * (float)s->nelts);
 539                 if (obj <= threshold) {
 540                         // insert into existing bucket
 541                         st[nextptr].gap++;
 542                 }
 543                 else {
 544                         newptr = s->free_head;
 545                         if (newptr==-1) {
 546                                 gslog(LOG_ALERT, "Out of space in quant_udaf_hftaZ_HFTA_AGGR_UPDATE_.\n");
 547                                 quant_udaf_hftaZ_compress<T>(s);
 548                                 return;
 549                         }
 550                         s->free_head = st[newptr].next;
 551                         st[newptr].val = v;
 552                         st[newptr].gap = 1;
 553                         st[newptr].del = st[nextptr].gap + st[nextptr].del-1;
 554                         st[newptr].next = st[ptr].next;
 555                         st[ptr].next = newptr;
 556                 }
 557         }
 558         if(s->nelts>100 && (s->nelts & 0x03)==0)
 559                 quant_udaf_hftaZ_compress<T>(s);
 560 }
 561
 562 template <class T>  void quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
 563         r->length = sizeof(quant_udaf_hfta_struct_t<T>);
 564         r->offset = (gs_p_t )b;
 565         r->reserved = SHALLOW_COPY;
 566 }
 567
 568 template <class T>  void quant_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){
 569         quant_udaf_hfta_struct_t<T> *s = (quant_udaf_hfta_struct_t<T> *)b;
 570         if(s->vals != NULL)
 571                 free(s->vals);
 572         if(s->st)
 573                 free(s->st);
 574 }
 575
 576
 577 template <class T> T extr_quant_hftaZ_fcn(vstring *v, gs_float_t phi) {
 578         quant_udaf_hfta_struct_t<T> *s = (quant_udaf_hfta_struct_t<T> *)(v->offset);
 579         int t, p;
 580
 581         if(s->t != NULL){       // separate path for hfta/lfta split
 582                 return extr_quant_hfta3_fcn<T>(v, phi);
 583         }
 584
 585         if(s->vals){
 586 //              qsort(s->vals, s->nelts, sizeof(gs_uint32_t), compare_gs_uint32);
 587                 sort(s->vals,s->vals+s->nelts);
 588                 gs_int32_t rank = (gs_int32_t) (phi*(float)(s->nelts));
 589                 if(rank>=s->nelts)
 590                         rank=s->nelts-1;
 591                 return s->vals[rank];
 592         }
 593
 594
 595         gs_int32_t rmin=0, rmax, rank, ropt=INT_MAX;
 596         gs_uint32_t count=0;
 597         supertupleZ_t<T> *st = s->st;
 598
 599         rank = (gs_int32_t) (phi*(float)(s->nelts));
 600
 601         for (t=s->used_head; t != -1; t=st[t].next) {
 602                 rmin += st[t].gap;
 603                 rmax = rmin+st[t].del;
 604                 if (max(abs(rmin-rank), abs(rmax-rank)) < ropt) {
 605                         p = t;
 606                         ropt = max(abs(rmin-rank), abs(rmax-rank));
 607                 } else break;
 608         }
 609         return st[p].val;
 610 }
 611 template <class T> T extr_med_hftaZ_fcn(vstring *v) {
 612         return extr_quant_hftaZ_fcn<T>(v, 0.5);
 613 }
 614
 615
 616 template <class T> int quant_udaf_hftaZ_nelem(gs_sp_t b) {
 617         quant_udaf_hfta_struct_t<T> *s = (quant_udaf_hfta_struct_t<T> *)b;
 618         supertupleZ_t<T> *st = s->st;
 619
 620         if(s->vals != NULL)
 621                 return s->nelts;
 622
 623         int ctr=0;
 624         int t=s->used_head;
 625         while(t>=0){
 626                 ctr++;
 627                 t=st[t].next;
 628         }
 629         return ctr;
 630 }
 631
 632 //      Unsigned int
 633 void quant_ui_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b){
 634           quant_udaf_hftaZ_HFTA_AGGR_INIT_<gs_uint32_t>(b);
 635 }
 636 void quant_ui_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_uint32_t v){
 637         quant_udaf_hftaZ_HFTA_AGGR_UPDATE_<gs_uint32_t>(b,v);
 638 }
 639 void quant_ui_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
 640         quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_<gs_uint32_t>(r,b);
 641 }
 642 void quant_ui_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){
 643         quant_udaf_hftaZ_HFTA_AGGR_DESTROY_<gs_uint32_t>(b);
 644 }
 645 gs_uint32_t extr_quant_ui_hftaZ_fcn(vstring *v, gs_float_t phi) {
 646         return extr_quant_hftaZ_fcn<gs_uint32_t>(v,phi);
 647 }
 648 gs_uint32_t extr_med_ui_hftaZ_fcn(vstring *v){
 649         return extr_med_hftaZ_fcn<gs_uint32_t>(v);
 650 }
 651 int quant_ui_udaf_hftaZ_nelem(gs_sp_t b) {
 652         return quant_udaf_hftaZ_nelem<gs_uint32_t>(b);
 653 }
 654
 655 //      int
 656 void quant_i_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b){
 657           quant_udaf_hftaZ_HFTA_AGGR_INIT_<gs_int32_t>(b);
 658 }
 659 void quant_i_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_int32_t v){
 660         quant_udaf_hftaZ_HFTA_AGGR_UPDATE_<gs_int32_t>(b,v);
 661 }
 662 void quant_i_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
 663         quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_<gs_int32_t>(r,b);
 664 }
 665 void quant_i_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){
 666         quant_udaf_hftaZ_HFTA_AGGR_DESTROY_<gs_int32_t>(b);
 667 }
 668 gs_int32_t extr_quant_i_hftaZ_fcn(vstring *v, gs_float_t phi) {
 669         return extr_quant_hftaZ_fcn<gs_int32_t>(v,phi);
 670 }
 671 gs_int32_t extr_med_i_hftaZ_fcn(vstring *v){
 672         return extr_med_hftaZ_fcn<gs_int32_t>(v);
 673 }
 674 gs_int32_t quant_i_udaf_hftaZ_nelem(gs_sp_t b) {
 675         return quant_udaf_hftaZ_nelem<gs_int32_t>(b);
 676 }
 677
 678 //      Unsigned long long int
 679 void quant_ul_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b){
 680           quant_udaf_hftaZ_HFTA_AGGR_INIT_<gs_uint64_t>(b);
 681 }
 682 void quant_ul_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_uint64_t v){
 683         quant_udaf_hftaZ_HFTA_AGGR_UPDATE_<gs_uint64_t>(b,v);
 684 }
 685 void quant_ul_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
 686         quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_<gs_uint64_t>(r,b);
 687 }
 688 void quant_ul_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){
 689         quant_udaf_hftaZ_HFTA_AGGR_DESTROY_<gs_uint64_t>(b);
 690 }
 691 gs_uint64_t extr_quant_ul_hftaZ_fcn(vstring *v, gs_float_t phi) {
 692         return extr_quant_hftaZ_fcn<gs_uint64_t>(v,phi);
 693 }
 694 gs_uint64_t extr_med_ul_hftaZ_fcn(vstring *v){
 695         return extr_med_hftaZ_fcn<gs_uint64_t>(v);
 696 }
 697 int quant_ul_udaf_hftaZ_nelem(gs_sp_t b) {
 698         return quant_udaf_hftaZ_nelem<gs_uint64_t>(b);
 699 }
 700
 701 //      long long int
 702 void quant_l_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b){
 703           quant_udaf_hftaZ_HFTA_AGGR_INIT_<gs_int64_t>(b);
 704 }
 705 void quant_l_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_int64_t v){
 706         quant_udaf_hftaZ_HFTA_AGGR_UPDATE_<gs_int64_t>(b,v);
 707 }
 708 void quant_l_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
 709         quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_<gs_int64_t>(r,b);
 710 }
 711 void quant_l_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){
 712         quant_udaf_hftaZ_HFTA_AGGR_DESTROY_<gs_int64_t>(b);
 713 }
 714 gs_int64_t extr_quant_l_hftaZ_fcn(vstring *v, gs_float_t phi) {
 715         return extr_quant_hftaZ_fcn<gs_int64_t>(v,phi);
 716 }
 717 gs_int64_t extr_med_l_hftaZ_fcn(vstring *v){
 718         return extr_med_hftaZ_fcn<gs_int64_t>(v);
 719 }
 720 int quant_l_udaf_hftaZ_nelem(gs_sp_t b) {
 721         return quant_udaf_hftaZ_nelem<gs_int64_t>(b);
 722 }
 723
 724
 725 //      double
 726 void quant_f_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b){
 727           quant_udaf_hftaZ_HFTA_AGGR_INIT_<gs_float_t>(b);
 728 }
 729 void quant_f_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_float_t v){
 730         quant_udaf_hftaZ_HFTA_AGGR_UPDATE_<gs_float_t>(b,v);
 731 }
 732 void quant_f_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
 733         quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_<gs_float_t>(r,b);
 734 }
 735 void quant_f_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){
 736         quant_udaf_hftaZ_HFTA_AGGR_DESTROY_<gs_float_t>(b);
 737 }
 738 gs_float_t extr_quant_f_hftaZ_fcn(vstring *v, gs_float_t phi) {
 739         return extr_quant_hftaZ_fcn<gs_float_t>(v,phi);
 740 }
 741 gs_float_t extr_med_f_hftaZ_fcn(vstring *v){
 742         return extr_med_hftaZ_fcn<gs_float_t>(v);
 743 }
 744 int quant_f_udaf_hftaZ_nelem(gs_sp_t b) {
 745         return quant_udaf_hftaZ_nelem<gs_float_t>(b);
 746 }
 747
 748