X-Git-Url: https://gerrit.o-ran-sc.org/r/gitweb?a=blobdiff_plain;f=src%2Flib%2Fgscphftaaux%2Fflip_udaf.cc;h=2d05f167d372063c7328e616a149b426bd229f18;hb=9f18e8186cda2367942d12a9750e00880f6cd97e;hp=a44f3e5b60b5fc3e2c78aa73ae5205dfe68b026a;hpb=3ff5c433efcaee8b01fbeed90ab848008f2e6278;p=com%2Fgs-lite.git diff --git a/src/lib/gscphftaaux/flip_udaf.cc b/src/lib/gscphftaaux/flip_udaf.cc index a44f3e5..2d05f16 100644 --- a/src/lib/gscphftaaux/flip_udaf.cc +++ b/src/lib/gscphftaaux/flip_udaf.cc @@ -4,273 +4,116 @@ #include #include "hfta_udaf.h" -#define QUANT_LFTA1_SIZE 729 -#define QUANT_LFTA2_SIZE 181 -#define QUANT_LFTA3_SIZE 100 +#include // std::sort -#define QUANT_EPS 0.01 -#define SKIPDIR_SIZE 100 -#define SKIPDIR_HEIGHT_MAX 7 -#define max(a,b) ((a) > (b) ? (a) : (b)) +#include +#include "udaf_common.h" +//#define QUANT_LFTA1_SIZE 729 +//#define QUANT_LFTA2_SIZE 181 +//#define QUANT_LFTA3_SIZE 50 +//#define QUANT_EPS 0.01 +//#define SKIPDIR_SIZE 100 +//#define SKIPDIR_HEIGHT_MAX 7 + + +//#define max(a,b) ((a) > (b) ? (a) : (b)) + +using namespace std; + +// current use +// hfta_only: quant_udaf_hfta0 +// extraction: extr_quant_hfta0_fcn extr_med_hfta0_fcn extr_quant_hfta0_space +// lfta/hfta: quant_udaf_lfta3 quant_udaf_hfta3 + +// TODO +// - Should the hfta part of the hfta/lfta split (hfta3) +// match the hfta-only implementation (hftaZ)? +// - On out-of-space conditions, try a compress before +// discarding the sample. If that happens, can the rate +// of compresses be decreased? +// - Can the lfta part be made to work with actual compression? +// if not, change the implementation to gather a collection +// of samples, then send them up. This should decrease +// lfta space use and reduce the cost of adding to the hfta. /****************************************************************/ /* Data Structures */ /****************************************************************/ -typedef struct tuple_t { - gs_uint32_t val; - gs_uint32_t gap; - gs_uint32_t del; - gs_uint32_t next; -} tuple_t; -typedef struct supertuple_t { - gs_uint32_t val; - gs_uint32_t gap; - gs_uint32_t del; - struct supertuple_t *next; -} supertuple_t; /****************************************************************/ -typedef gs_uint32_t val_type; +template struct tuple_t { + T val; + gs_uint32_t gap; + gs_uint32_t del; + gs_uint32_t next; +}; -typedef struct skipnode { - val_type val; +template struct skipnode_t { + T val; gs_uint32_t next; gs_uint32_t down; -} skipnode_t; +}; -typedef struct skipdir { +template struct skipdir_t { gs_uint32_t height; // height of tree gs_uint32_t freeptr; // cursor space stack gs_uint32_t headptr[SKIPDIR_HEIGHT_MAX]; // ptrs to levels - skipnode_t list[SKIPDIR_SIZE+1]; -} skipdir_t; + skipnode_t list[SKIPDIR_SIZE+1]; +}; /****************************************************************/ -typedef struct quant_udaf_hfta0_struct_t { - gs_uint32_t nelts; // 4 bytes - supertuple_t *t; // 8 bytes -} quant_udaf_hfta0_struct_t; - -typedef struct quant_udaf_lfta1_struct_t { - gs_uint32_t nelts; - gs_uint32_t samples[QUANT_LFTA1_SIZE]; -} quant_udaf_lfta1_struct_t; - -typedef struct quant_udaf_hfta1_struct_t { - gs_uint32_t nelts; // 4 bytes - supertuple_t *t; // 8 bytes -} quant_udaf_hfta1_struct_t; -typedef struct quant_udaf_lfta2_struct_t { - gs_uint32_t nelts; - gs_uint32_t freeptr; - gs_uint32_t usedptr; - tuple_t t[QUANT_LFTA2_SIZE+1]; -} quant_udaf_lfta2_struct_t; -typedef struct quant_udaf_hfta2_struct_t { - gs_uint32_t nelts; // 4 bytes - supertuple_t *t; // 8 bytes -} quant_udaf_hfta2_struct_t; -typedef struct quant_udaf_lfta3_struct_t { +template struct quant_udaf_lfta3_struct_t { gs_uint32_t nelts; gs_uint32_t freeptr; gs_uint32_t usedptr; gs_uint32_t circptr; gs_uint32_t size; - tuple_t t[QUANT_LFTA3_SIZE+1]; - skipdir_t sd; -} quant_udaf_lfta3_struct_t; - -typedef struct quant_udaf_hfta3_struct_t { - gs_uint32_t nelts; // 4 bytes - supertuple_t *t; // 8 bytes -} quant_udaf_hfta3_struct_t; - - - -/*************************** Version 0 **************************/ -/* Version 0: HFTA-only */ -/****************************************************************/ -void quant_udaf_hfta0_print(quant_udaf_hfta0_struct_t *s) -{ - supertuple_t *t; - - gslog(LOG_DEBUG,"hfta nelts = %u\n",s->nelts); - gslog(LOG_DEBUG,"HFTA tuples:\n"); - for (t=s->t; t != NULL; t=t->next) { - gslog(LOG_DEBUG,"(%u, %u, %u)\n",t->val,t->gap,t->del); - } -} + tuple_t t[QUANT_LFTA3_SIZE+1]; + skipdir_t sd; +}; -void quant_udaf_hfta0_compress(quant_udaf_hfta0_struct_t *s) -{ - supertuple_t *t=s->t, *d; - gs_uint32_t threshold; - threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(s->nelts)); - if ((t == NULL) || (t->next == NULL)) return; - d = t->next; - while ((d != NULL) && (d->next != NULL)) { - if (d->gap+d->next->gap+d->next->del < threshold) { - d->next->gap += d->gap; - t->next = d->next; - free(d); - } - t = t->next; - d = t->next; - } -} - -/****************************************************************/ -/* HFTA0 functions */ -/****************************************************************/ -void quant_udaf_hfta0_HFTA_AGGR_INIT_(gs_sp_t b) -{ - quant_udaf_hfta0_struct_t *s = (quant_udaf_hfta0_struct_t *)b; - s->nelts = 0; - s->t = NULL; -} - -void quant_udaf_hfta0_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_uint32_t v) -{ - quant_udaf_hfta0_struct_t *s = (quant_udaf_hfta0_struct_t *)b; - supertuple_t *t=s->t; - supertuple_t *newptr; - gs_uint32_t threshold; - gs_uint32_t val, gap; - gs_uint32_t obj; - - s->nelts++; - // left boundary case - if ((!t) || (v <= t->val)) { - newptr = (supertuple_t *)malloc(sizeof(supertuple_t)); - if (!newptr) { - gslog(LOG_ALERT, "Out of space.\n"); - return; - } - newptr->val = v; - newptr->gap = 1; - newptr->del = 0; - newptr->next = s->t; - s->t = newptr; - return; - } - - // locate position that sandwiches v - while ((t->next) && (t->next->val < v)) - t = t->next; - - // right boundary case - if (!t->next) { - // create newptr node - newptr = (supertuple_t *)malloc(sizeof(supertuple_t)); - newptr->val = v; - newptr->gap = 1; - newptr->del = 0; - newptr->next = NULL; - t->next = newptr; - } - // non-boundary case - else { - obj = t->gap+t->next->gap+t->next->del; - threshold = (gs_uint32_t)ceil(2.0 * QUANT_EPS * (float)s->nelts); - if (obj <= threshold) { - // insert into existing bucket - t->next->gap++; - } - else { - newptr = (supertuple_t *)malloc(sizeof(supertuple_t)); - newptr->val = v; - newptr->gap = 1; - newptr->del = t->next->gap+t->next->del-1; - newptr->next = t->next; - t->next = newptr; - } - } - quant_udaf_hfta0_compress(s); -} - -void quant_udaf_hfta0_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) -{ - r->length = sizeof(quant_udaf_hfta0_struct_t); - r->offset = (gs_p_t )b; - r->reserved = SHALLOW_COPY; -} - -void quant_udaf_hfta0_HFTA_AGGR_DESTROY_(gs_sp_t b) -{ - quant_udaf_hfta0_struct_t *s = (quant_udaf_hfta0_struct_t *)b; - supertuple_t *t=s->t, *n; - while(t){ - n=t->next; - free(t); - t=n; - } - - return; -} +template struct supertuple3_t{ // hfta/lfta + T val; + gs_uint32_t gap; + gs_uint32_t del; + struct supertuple3_t *next; +}; +template struct supertupleZ_t{ + T val; + gs_uint32_t gap; + gs_uint32_t del; + gs_int32_t next; +}; -/****************************************************************/ -/* HFTA0 Extraction functions */ -/****************************************************************/ -gs_uint32_t extr_quant_hfta0_fcn(vstring *v, gs_float_t phi) -{ -//printf("In extr_quant_hfta0_fcn offset=%llx length=%d\n",v->offset, v->length); - quant_udaf_hfta0_struct_t *vs = (quant_udaf_hfta0_struct_t *)(v->offset); -//printf("nelts=%d t=%llx\n",vs->nelts, (unsigned long long int)(vs->t)); - supertuple_t *t, *p; - gs_uint32_t nelts=0; - gs_uint32_t rmin=0, rmax, rank, ropt=UINT_MAX; - gs_uint32_t count=0; - for (t=vs->t; t != NULL; t=t->next) { -//printf("in loop.\n"); -//printf("gap is %d\n",t->gap); - nelts += t->gap; - count++; - } - rank = (gs_uint32_t) (phi*(float)nelts); +template struct quant_udaf_hfta_struct_t { + gs_uint32_t nelts; // 4 bytes + short int used_head; + short int free_head; + supertupleZ_t *st; + gs_uint32_t *vals; + supertuple3_t *t; // 8 bytes +}; - for (t=vs->t; t != NULL; t=t->next) { - rmin += t->gap; - rmax = rmin+t->del; - if (max(abs(rmin-rank), abs(rmax-rank)) < ropt) { - p = t; - ropt = max(abs(rmin-rank), abs(rmax-rank)); - } - } - return p->val; -} -gs_uint32_t extr_med_hfta0_fcn(vstring *v) -{ - return extr_quant_hfta0_fcn(v, 0.5); -} -gs_uint32_t extr_quant_hfta0_space(vstring *v) -{ - quant_udaf_hfta0_struct_t *vs = (quant_udaf_hfta0_struct_t *)(v->offset); - supertuple_t *t; - gs_uint32_t count=0; - for (t=vs->t; t != NULL; t=t->next) - count++; - return count; -} /*************************** Version 3 **************************/ /* Version 3: LFTA-medium */ /****************************************************************/ -void quant_hfta3_print(quant_udaf_hfta3_struct_t *s) +template void quant_hfta3_print(quant_udaf_hfta_struct_t *s) { - supertuple_t *t; + supertuple3_t *t; //printf("In quant_hfta3_print, s=%llx, t=%llx\n",(unsigned long long int)s,(unsigned long long int)(s->t)); gslog(LOG_DEBUG,"HFTA tuples:\n"); @@ -279,9 +122,9 @@ void quant_hfta3_print(quant_udaf_hfta3_struct_t *s) } } -void quant_hfta3_compress(quant_udaf_hfta3_struct_t *s) +template void quant_hfta3_compress(quant_udaf_hfta_struct_t *s) { - supertuple_t *t=s->t, *d; + supertuple3_t *t=s->t, *d; gs_uint32_t threshold; threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(s->nelts)); @@ -302,20 +145,43 @@ void quant_hfta3_compress(quant_udaf_hfta3_struct_t *s) /****************************************************************/ /* HFTA3 functions */ /****************************************************************/ -void quant_udaf_hfta3_HFTA_AGGR_INIT_(gs_sp_t b) -{ - quant_udaf_hfta3_struct_t *s = (quant_udaf_hfta3_struct_t *)b; + +// since it does mallocs instead of allocations in a fixed block of memory +template void quant_udaf_hfta3_HFTA_AGGR_INIT_(gs_sp_t b) { +//printf("sizeof quant_udaf_hfta_struct_t is %lu\n",sizeof(quant_udaf_hfta_struct_t)); +//printf("sizeof quant_udaf_lfta3_struct_t is %lu\n",sizeof(quant_udaf_lfta3_struct_t)); + quant_udaf_hfta_struct_t *s = (quant_udaf_hfta_struct_t *)b; +//printf("quant_udaf_hfta3_HFTA_AGGR_INIT_ size is %lu\n",sizeof(quant_udaf_hfta_struct_t)); s->nelts = 0; s->t = NULL; + s->vals = NULL; + s->st = NULL; + s->used_head = -1; + s->free_head = -1; } -void quant_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v) -{ - quant_udaf_hfta3_struct_t *s = (quant_udaf_hfta3_struct_t *)b; - quant_udaf_lfta3_struct_t *vs = (quant_udaf_lfta3_struct_t *)(v->offset); - supertuple_t *t=s->t, *tprev=NULL; - tuple_t *u=vs->t; - supertuple_t *newptr; +void quant_ui_udaf_hfta3_HFTA_AGGR_INIT_(gs_sp_t b){ + quant_udaf_hfta3_HFTA_AGGR_INIT_(b); +} +void quant_i_udaf_hfta3_HFTA_AGGR_INIT_(gs_sp_t b){ + quant_udaf_hfta3_HFTA_AGGR_INIT_(b); +} +void quant_ul_udaf_hfta3_HFTA_AGGR_INIT_(gs_sp_t b){ + quant_udaf_hfta3_HFTA_AGGR_INIT_(b); +} +void quant_l_udaf_hfta3_HFTA_AGGR_INIT_(gs_sp_t b){ + quant_udaf_hfta3_HFTA_AGGR_INIT_(b); +} +void quant_f_udaf_hfta3_HFTA_AGGR_INIT_(gs_sp_t b){ + quant_udaf_hfta3_HFTA_AGGR_INIT_(b); +} + +template void quant_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v) { + quant_udaf_hfta_struct_t *s = (quant_udaf_hfta_struct_t *)b; + quant_udaf_lfta3_struct_t *vs = (quant_udaf_lfta3_struct_t *)(v->offset); + supertuple3_t *t=s->t, *tprev=NULL; + tuple_t *u=vs->t; + supertuple3_t *newptr; gs_uint32_t uptr = vs->usedptr; gs_uint32_t threshold; @@ -324,6 +190,7 @@ void quant_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v) threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(vs->nelts)); while (uptr != 0) { +//printf("uptr=%d\n",uptr); if ((u[uptr].next != 0) && (u[uptr].gap+u[u[uptr].next].gap+u[u[uptr].next].del < threshold)) { u[u[uptr].next].gap += u[uptr].gap; } @@ -344,7 +211,7 @@ void quant_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v) } if (!uptr) break; // create newptr node - newptr = (supertuple_t *)malloc(sizeof(supertuple_t)); + newptr = (supertuple3_t *)malloc(sizeof(supertuple3_t)); newptr->val = u[uptr].val; newptr->gap = u[uptr].gap; newptr->del = u[uptr].del; @@ -361,42 +228,94 @@ void quant_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v) } uptr = u[uptr].next; } - quant_hfta3_compress(s); + quant_hfta3_compress(s); //quant_hfta3_print(s); //printf("exiting quant_udaf_hfta3_HFTA_AGGR_UPDATE_, s=%llx, t=%llx\n",(unsigned long long int)s,(unsigned long long int)(s->t)); } -void quant_udaf_hfta3_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) -{ - r->length = sizeof(quant_udaf_hfta3_struct_t); +void quant_ui_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v){ + quant_udaf_hfta3_HFTA_AGGR_UPDATE_(b, v); +} +void quant_i_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v){ + quant_udaf_hfta3_HFTA_AGGR_UPDATE_(b, v); +} +void quant_ul_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v){ + quant_udaf_hfta3_HFTA_AGGR_UPDATE_(b, v); +} +void quant_l_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v){ + quant_udaf_hfta3_HFTA_AGGR_UPDATE_(b, v); +} +void quant_f_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v){ + quant_udaf_hfta3_HFTA_AGGR_UPDATE_(b, v); +} + +template void quant_udaf_hfta3_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) { + r->length = sizeof(quant_udaf_hfta_struct_t); r->offset = (gs_p_t )b; r->reserved = SHALLOW_COPY; - quant_udaf_hfta3_struct_t *s = (quant_udaf_hfta3_struct_t *)b; + quant_udaf_hfta_struct_t *s = (quant_udaf_hfta_struct_t *)b; //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)); } -void quant_udaf_hfta3_HFTA_AGGR_DESTROY_(gs_sp_t b) -{ +void quant_ui_udaf_hfta3_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) { + quant_udaf_hfta3_HFTA_AGGR_OUTPUT_(r, b); +} +void quant_i_udaf_hfta3_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) { + quant_udaf_hfta3_HFTA_AGGR_OUTPUT_(r, b); +} +void quant_ul_udaf_hfta3_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) { + quant_udaf_hfta3_HFTA_AGGR_OUTPUT_(r, b); +} +void quant_l_udaf_hfta3_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) { + quant_udaf_hfta3_HFTA_AGGR_OUTPUT_(r, b); +} +void quant_f_udaf_hfta3_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) { + quant_udaf_hfta3_HFTA_AGGR_OUTPUT_(r, b); +} + +template void quant_udaf_hfta3_HFTA_AGGR_DESTROY_(gs_sp_t b) { + quant_udaf_hfta_struct_t *s = (quant_udaf_hfta_struct_t *)b; + supertuple3_t *t=s->t, *n; + while(t){ + n=t->next; + free(t); + t=n; + } return; } +void quant_ui_udaf_hfta3_HFTA_AGGR_DESTROY_(gs_sp_t b) { + quant_udaf_hfta3_HFTA_AGGR_DESTROY_(b); +} +void quant_i_udaf_hfta3_HFTA_AGGR_DESTROY_(gs_sp_t b) { + quant_udaf_hfta3_HFTA_AGGR_DESTROY_(b); +} +void quant_ul_udaf_hfta3_HFTA_AGGR_DESTROY_(gs_sp_t b) { + quant_udaf_hfta3_HFTA_AGGR_DESTROY_(b); +} +void quant_l_udaf_hfta3_HFTA_AGGR_DESTROY_(gs_sp_t b) { + quant_udaf_hfta3_HFTA_AGGR_DESTROY_(b); +} +void quant_f_udaf_hfta3_HFTA_AGGR_DESTROY_(gs_sp_t b) { + quant_udaf_hfta3_HFTA_AGGR_DESTROY_(b); +} + /****************************************************************/ /* HFTA3 Extraction functions */ /****************************************************************/ -gs_uint32_t extr_quant_hfta3_fcn(vstring *v, gs_float_t phi) -{ - quant_udaf_hfta3_struct_t *vs = (quant_udaf_hfta3_struct_t *)(v->offset); - supertuple_t *t, *p; +template T extr_quant_hfta3_fcn(vstring *v, gs_float_t phi) { + quant_udaf_hfta_struct_t *vs = (quant_udaf_hfta_struct_t *)(v->offset); + supertuple3_t *t, *p; gs_uint32_t nelts=0; - gs_uint32_t rmin=0, rmax, rank, ropt=UINT_MAX; + gs_int32_t rmin=0, rmax, rank, ropt=INT_MAX; gs_uint32_t count=0; for (t=vs->t; t != NULL; t=t->next) { nelts += t->gap; count++; } - rank = (gs_uint32_t) (phi*(float)nelts); + rank = (gs_int32_t) (phi*(float)nelts); for (t=vs->t; t != NULL; t=t->next) { rmin += t->gap; @@ -409,18 +328,421 @@ gs_uint32_t extr_quant_hfta3_fcn(vstring *v, gs_float_t phi) return p->val; } -gs_uint32_t extr_med_hfta3_fcn(vstring *v) +/* +gs_uint32_t extr_quant_ui_hfta3_fcn(vstring *v, gs_float_t phi){ + return extr_quant_hfta3_fcn(v, phi); +} +gs_int32_t extr_quant_i_hfta3_fcn(vstring *v, gs_float_t phi){ + return extr_quant_hfta3_fcn(v, phi); +} +gs_uint64_t extr_quant_ul_hfta3_fcn(vstring *v, gs_float_t phi){ + return extr_quant_hfta3_fcn(v, phi); +} +gs_int64_t extr_quant_l_hfta3_fcn(vstring *v, gs_float_t phi){ + return extr_quant_hfta3_fcn(v, phi); +} +gs_float_t extr_quant_f_hfta3_fcn(vstring *v, gs_float_t phi){ + return extr_quant_hfta3_fcn(v, phi); +} +*/ + +template T extr_med_hfta3_fcn(vstring *v) { - return extr_quant_hfta3_fcn(v, 0.5); + return extr_quant_hfta3_fcn(v, 0.5); } -gs_uint32_t extr_quant_hfta3_space(vstring *v) +gs_uint32_t extr_ui_med_hfta3_fcn(vstring *v){ + return extr_med_hfta3_fcn(v); +} +gs_int32_t extr_i_med_hfta3_fcn(vstring *v){ + return extr_med_hfta3_fcn(v); +} +gs_uint64_t extr_ul_med_hfta3_fcn(vstring *v){ + return extr_med_hfta3_fcn(v); +} +gs_int64_t extr_l_med_hfta3_fcn(vstring *v){ + return extr_med_hfta3_fcn(v); +} +gs_float_t extr_f_med_hfta3_fcn(vstring *v){ + return extr_med_hfta3_fcn(v); +} + +template gs_uint32_t extr_quant_hfta3_space(vstring *v) { - quant_udaf_hfta3_struct_t *vs = (quant_udaf_hfta3_struct_t *)(v->offset); - supertuple_t *t; + quant_udaf_hfta_struct_t *vs = (quant_udaf_hfta_struct_t *)(v->offset); + supertuple3_t *t; gs_uint32_t count=0; for (t=vs->t; t != NULL; t=t->next) count++; return count; } + + + +////////////////////////////////////////////////////////////////////// +// hfta-only code V3 + +// This approach stores values in a buffer until +// the buffer gets filled, and then puts the values into +// the approximate quantile udaf. +// +// Further, the code is templatized + +#define MAX_QUANT_ELEMS 128 +#define MAX_VAL_ELEMS 50 +// MAX_VAL_ELEMS must be less than MAX_QUANT_ELEMS, +// and probably somewhat less than 1/QUANT_EPS +// Another consideration is space use, as most groups are small, +// so you want MAX_VAL_ELEMS to be as small as possible +// and still capture most small groups. + +// To really optimize for space, use a doubling realloc +// strategy until the doubled size would be 2K bytes, +// and then instead of doubling, insert into the approx +// structure. +// + +/* +template struct supertupleZ_t{ + T val; + gs_uint32_t gap; + gs_uint32_t del; + gs_int32_t next; +}; +*/ + +/* +template struct quant_udaf_hftaZ_struct_t{ + gs_uint32_t nelts; + short int used_head; + short int free_head; + supertupleZ_t *st; + gs_uint32_t *vals; +}; +*/ + + +template void quant_udaf_hftaZ_compress(quant_udaf_hfta_struct_t *s) +{ + int t = s->used_head, d, d_next=-1; + gs_uint32_t threshold; + supertupleZ_t *st = s->st; + + threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(s->nelts)); + if ((t == -1) || (st[t].next == -1)) return; + d = st[t].next; + while ((d != -1) && (st[d].next != -1)) { + d_next = st[d].next; + if (st[d].gap + st[d_next].gap + st[d_next].del < threshold) { + st[d_next].gap += st[d].gap; + st[t].next = st[d].next; + st[d].next = s->free_head; + s->free_head = d; + } + t = st[t].next; + d = st[t].next; + } +} + +template void quant_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b) { + quant_udaf_hfta_struct_t *s = (quant_udaf_hfta_struct_t *)b; +//printf("quant_udaf_hftaZ_HFTA_AGGR_INIT_ size is %lu\n",sizeof(quant_udaf_hfta_struct_t)); + s->nelts = 0; + s->st=NULL; + s->vals = (gs_uint32_t *)malloc(MAX_VAL_ELEMS*sizeof(T)); + s->t = NULL; +} + +template void quant_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, T v) { + quant_udaf_hfta_struct_t *s = (quant_udaf_hfta_struct_t *)b; + if(s->neltsvals[s->nelts] = v; + s->nelts++; + return; + } + + if(s->nelts==MAX_VAL_ELEMS){ +// qsort(s->vals, MAX_VAL_ELEMS, sizeof(gs_uint32_t), compare_gs_uint32); + sort(s->vals,s->vals+s->nelts); + s->st = (supertupleZ_t *)malloc(MAX_QUANT_ELEMS*sizeof(quant_udaf_hfta_struct_t)); + for(int i=0;ist[i].val = s->vals[i]; + s->st[i].gap = 1; + s->st[i].del = 0; + s->st[i].next = i+1; + } + s->st[MAX_VAL_ELEMS-1].next = -1; + for(int i=MAX_VAL_ELEMS; ist[i].next = i+1; + } + s->st[MAX_QUANT_ELEMS-1].next = -1; + s->free_head = MAX_VAL_ELEMS; + s->used_head = 0; + free(s->vals); + s->vals = NULL; + } + +// s->nelts > MAX_VAL_ELEMS + int t=s->used_head; + int newptr; + gs_uint32_t threshold; + gs_uint32_t val, gap; + gs_uint32_t obj; + supertupleZ_t *st = s->st; + + s->nelts++; + // left boundary case + if ((t==-1) || (v <= st[t].val)) { + newptr = s->free_head; + if (newptr==-1) { + gslog(LOG_ALERT, "Out of space in quant_udaf_hftaZ_HFTA_AGGR_UPDATE_.\n"); + cout << v << endl; + quant_udaf_hftaZ_compress(s); + return; + } + s->free_head = st[newptr].next; + st[newptr].val = v; + st[newptr].gap = 1; + st[newptr].del = 0; + st[newptr].next = s->used_head; + s->used_head = newptr; + return; + } + + // locate position that sandwiches v + int ptr=t; + while ((st[ptr].next!=-1) && (st[st[ptr].next].val < v)) + ptr = st[ptr].next; + + // right boundary case + if (st[ptr].next==-1) { + // create newptr node + newptr = s->free_head; + if (newptr==-1) { + gslog(LOG_ALERT, "Out of space in quant_udaf_hftaZ_HFTA_AGGR_UPDATE_.\n"); + quant_udaf_hftaZ_compress(s); + return; + } + s->free_head = st[newptr].next; + st[newptr].val = v; + st[newptr].gap = 1; + st[newptr].del = 0; + st[newptr].next =-1; + st[ptr].next = newptr; + } + // non-boundary case + else { + int nextptr = st[ptr].next; + obj = st[ptr].gap + st[nextptr].gap + st[nextptr].del; + threshold = (gs_uint32_t)ceil(2.0 * QUANT_EPS * (float)s->nelts); + if (obj <= threshold) { + // insert into existing bucket + st[nextptr].gap++; + } + else { + newptr = s->free_head; + if (newptr==-1) { + gslog(LOG_ALERT, "Out of space in quant_udaf_hftaZ_HFTA_AGGR_UPDATE_.\n"); + quant_udaf_hftaZ_compress(s); + return; + } + s->free_head = st[newptr].next; + st[newptr].val = v; + st[newptr].gap = 1; + st[newptr].del = st[nextptr].gap + st[nextptr].del-1; + st[newptr].next = st[ptr].next; + st[ptr].next = newptr; + } + } + if(s->nelts>100 && (s->nelts & 0x03)==0) + quant_udaf_hftaZ_compress(s); +} + +template void quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) { + r->length = sizeof(quant_udaf_hfta_struct_t); + r->offset = (gs_p_t )b; + r->reserved = SHALLOW_COPY; +} + +template void quant_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){ + quant_udaf_hfta_struct_t *s = (quant_udaf_hfta_struct_t *)b; + if(s->vals != NULL) + free(s->vals); + if(s->st) + free(s->st); +} + + +template T extr_quant_hftaZ_fcn(vstring *v, gs_float_t phi) { + quant_udaf_hfta_struct_t *s = (quant_udaf_hfta_struct_t *)(v->offset); + int t, p; + + if(s->t != NULL){ // separate path for hfta/lfta split + return extr_quant_hfta3_fcn(v, phi); + } + + if(s->vals){ +// qsort(s->vals, s->nelts, sizeof(gs_uint32_t), compare_gs_uint32); + sort(s->vals,s->vals+s->nelts); + gs_int32_t rank = (gs_int32_t) (phi*(float)(s->nelts)); + if(rank>=s->nelts) + rank=s->nelts-1; + return s->vals[rank]; + } + + + gs_int32_t rmin=0, rmax, rank, ropt=INT_MAX; + gs_uint32_t count=0; + supertupleZ_t *st = s->st; + + rank = (gs_int32_t) (phi*(float)(s->nelts)); + + for (t=s->used_head; t != -1; t=st[t].next) { + rmin += st[t].gap; + rmax = rmin+st[t].del; + if (max(abs(rmin-rank), abs(rmax-rank)) < ropt) { + p = t; + ropt = max(abs(rmin-rank), abs(rmax-rank)); + } else break; + } + return st[p].val; +} +template T extr_med_hftaZ_fcn(vstring *v) { + return extr_quant_hftaZ_fcn(v, 0.5); +} + + +template int quant_udaf_hftaZ_nelem(gs_sp_t b) { + quant_udaf_hfta_struct_t *s = (quant_udaf_hfta_struct_t *)b; + supertupleZ_t *st = s->st; + + if(s->vals != NULL) + return s->nelts; + + int ctr=0; + int t=s->used_head; + while(t>=0){ + ctr++; + t=st[t].next; + } + return ctr; +} + +// Unsigned int +void quant_ui_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b){ + quant_udaf_hftaZ_HFTA_AGGR_INIT_(b); +} +void quant_ui_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_uint32_t v){ + quant_udaf_hftaZ_HFTA_AGGR_UPDATE_(b,v); +} +void quant_ui_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) { + quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_(r,b); +} +void quant_ui_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){ + quant_udaf_hftaZ_HFTA_AGGR_DESTROY_(b); +} +gs_uint32_t extr_quant_ui_hftaZ_fcn(vstring *v, gs_float_t phi) { + return extr_quant_hftaZ_fcn(v,phi); +} +gs_uint32_t extr_med_ui_hftaZ_fcn(vstring *v){ + return extr_med_hftaZ_fcn(v); +} +int quant_ui_udaf_hftaZ_nelem(gs_sp_t b) { + return quant_udaf_hftaZ_nelem(b); +} + +// int +void quant_i_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b){ + quant_udaf_hftaZ_HFTA_AGGR_INIT_(b); +} +void quant_i_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_int32_t v){ + quant_udaf_hftaZ_HFTA_AGGR_UPDATE_(b,v); +} +void quant_i_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) { + quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_(r,b); +} +void quant_i_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){ + quant_udaf_hftaZ_HFTA_AGGR_DESTROY_(b); +} +gs_int32_t extr_quant_i_hftaZ_fcn(vstring *v, gs_float_t phi) { + return extr_quant_hftaZ_fcn(v,phi); +} +gs_int32_t extr_med_i_hftaZ_fcn(vstring *v){ + return extr_med_hftaZ_fcn(v); +} +gs_int32_t quant_i_udaf_hftaZ_nelem(gs_sp_t b) { + return quant_udaf_hftaZ_nelem(b); +} + +// Unsigned long long int +void quant_ul_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b){ + quant_udaf_hftaZ_HFTA_AGGR_INIT_(b); +} +void quant_ul_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_uint64_t v){ + quant_udaf_hftaZ_HFTA_AGGR_UPDATE_(b,v); +} +void quant_ul_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) { + quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_(r,b); +} +void quant_ul_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){ + quant_udaf_hftaZ_HFTA_AGGR_DESTROY_(b); +} +gs_uint64_t extr_quant_ul_hftaZ_fcn(vstring *v, gs_float_t phi) { + return extr_quant_hftaZ_fcn(v,phi); +} +gs_uint64_t extr_med_ul_hftaZ_fcn(vstring *v){ + return extr_med_hftaZ_fcn(v); +} +int quant_ul_udaf_hftaZ_nelem(gs_sp_t b) { + return quant_udaf_hftaZ_nelem(b); +} + +// long long int +void quant_l_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b){ + quant_udaf_hftaZ_HFTA_AGGR_INIT_(b); +} +void quant_l_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_int64_t v){ + quant_udaf_hftaZ_HFTA_AGGR_UPDATE_(b,v); +} +void quant_l_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) { + quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_(r,b); +} +void quant_l_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){ + quant_udaf_hftaZ_HFTA_AGGR_DESTROY_(b); +} +gs_int64_t extr_quant_l_hftaZ_fcn(vstring *v, gs_float_t phi) { + return extr_quant_hftaZ_fcn(v,phi); +} +gs_int64_t extr_med_l_hftaZ_fcn(vstring *v){ + return extr_med_hftaZ_fcn(v); +} +int quant_l_udaf_hftaZ_nelem(gs_sp_t b) { + return quant_udaf_hftaZ_nelem(b); +} + + +// double +void quant_f_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b){ + quant_udaf_hftaZ_HFTA_AGGR_INIT_(b); +} +void quant_f_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_float_t v){ + quant_udaf_hftaZ_HFTA_AGGR_UPDATE_(b,v); +} +void quant_f_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) { + quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_(r,b); +} +void quant_f_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){ + quant_udaf_hftaZ_HFTA_AGGR_DESTROY_(b); +} +gs_float_t extr_quant_f_hftaZ_fcn(vstring *v, gs_float_t phi) { + return extr_quant_hftaZ_fcn(v,phi); +} +gs_float_t extr_med_f_hftaZ_fcn(vstring *v){ + return extr_med_hftaZ_fcn(v); +} +int quant_f_udaf_hftaZ_nelem(gs_sp_t b) { + return quant_udaf_hftaZ_nelem(b); +} + +