+
+
+
+//////////////////////////////////////////////////////////////////////
+// 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 <class T> struct supertupleZ_t{
+ T val;
+ gs_uint32_t gap;
+ gs_uint32_t del;
+ gs_int32_t next;
+};
+*/
+
+/*
+template <class T> struct quant_udaf_hftaZ_struct_t{
+ gs_uint32_t nelts;
+ short int used_head;
+ short int free_head;
+ supertupleZ_t<T> *st;
+ gs_uint32_t *vals;
+};
+*/
+
+
+template <class T> void quant_udaf_hftaZ_compress(quant_udaf_hfta_struct_t<T> *s)
+{
+ int t = s->used_head, d, d_next=-1;
+ gs_uint32_t threshold;
+ supertupleZ_t<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 <class T> void quant_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b) {
+ quant_udaf_hfta_struct_t<T> *s = (quant_udaf_hfta_struct_t<T> *)b;
+//printf("quant_udaf_hftaZ_HFTA_AGGR_INIT_ size is %lu\n",sizeof(quant_udaf_hfta_struct_t<T>));
+ s->nelts = 0;
+ s->st=NULL;
+ s->vals = (gs_uint32_t *)malloc(MAX_VAL_ELEMS*sizeof(T));
+ s->t = NULL;
+}
+
+template <class T> void quant_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, T v) {
+ quant_udaf_hfta_struct_t<T> *s = (quant_udaf_hfta_struct_t<T> *)b;
+ if(s->nelts<MAX_VAL_ELEMS){
+ s->vals[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<T> *)malloc(MAX_QUANT_ELEMS*sizeof(quant_udaf_hfta_struct_t<T>));
+ for(int i=0;i<MAX_VAL_ELEMS;++i){
+ s->st[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; i<MAX_QUANT_ELEMS; ++i){
+ s->st[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<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<T>(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<T>(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<T>(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<T>(s);
+}
+
+template <class T> void quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
+ r->length = sizeof(quant_udaf_hfta_struct_t<T>);
+ r->offset = (gs_p_t )b;
+ r->reserved = SHALLOW_COPY;
+}
+
+template <class T> void quant_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){
+ quant_udaf_hfta_struct_t<T> *s = (quant_udaf_hfta_struct_t<T> *)b;
+ if(s->vals != NULL)
+ free(s->vals);
+ if(s->st)
+ free(s->st);
+}
+
+
+template <class T> T extr_quant_hftaZ_fcn(vstring *v, gs_float_t phi) {
+ quant_udaf_hfta_struct_t<T> *s = (quant_udaf_hfta_struct_t<T> *)(v->offset);
+ int t, p;
+
+ if(s->t != NULL){ // separate path for hfta/lfta split
+ return extr_quant_hfta3_fcn<T>(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<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 <class T> T extr_med_hftaZ_fcn(vstring *v) {
+ return extr_quant_hftaZ_fcn<T>(v, 0.5);
+}
+
+
+template <class T> int quant_udaf_hftaZ_nelem(gs_sp_t b) {
+ quant_udaf_hfta_struct_t<T> *s = (quant_udaf_hfta_struct_t<T> *)b;
+ supertupleZ_t<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_<gs_uint32_t>(b);
+}
+void quant_ui_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_uint32_t v){
+ quant_udaf_hftaZ_HFTA_AGGR_UPDATE_<gs_uint32_t>(b,v);
+}
+void quant_ui_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
+ quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_<gs_uint32_t>(r,b);
+}
+void quant_ui_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){
+ quant_udaf_hftaZ_HFTA_AGGR_DESTROY_<gs_uint32_t>(b);
+}
+gs_uint32_t extr_quant_ui_hftaZ_fcn(vstring *v, gs_float_t phi) {
+ return extr_quant_hftaZ_fcn<gs_uint32_t>(v,phi);
+}
+gs_uint32_t extr_med_ui_hftaZ_fcn(vstring *v){
+ return extr_med_hftaZ_fcn<gs_uint32_t>(v);
+}
+int quant_ui_udaf_hftaZ_nelem(gs_sp_t b) {
+ return quant_udaf_hftaZ_nelem<gs_uint32_t>(b);
+}
+
+// int
+void quant_i_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b){
+ quant_udaf_hftaZ_HFTA_AGGR_INIT_<gs_int32_t>(b);
+}
+void quant_i_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_int32_t v){
+ quant_udaf_hftaZ_HFTA_AGGR_UPDATE_<gs_int32_t>(b,v);
+}
+void quant_i_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
+ quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_<gs_int32_t>(r,b);
+}
+void quant_i_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){
+ quant_udaf_hftaZ_HFTA_AGGR_DESTROY_<gs_int32_t>(b);
+}
+gs_int32_t extr_quant_i_hftaZ_fcn(vstring *v, gs_float_t phi) {
+ return extr_quant_hftaZ_fcn<gs_int32_t>(v,phi);
+}
+gs_int32_t extr_med_i_hftaZ_fcn(vstring *v){
+ return extr_med_hftaZ_fcn<gs_int32_t>(v);
+}
+gs_int32_t quant_i_udaf_hftaZ_nelem(gs_sp_t b) {
+ return quant_udaf_hftaZ_nelem<gs_int32_t>(b);
+}
+
+// Unsigned long long int
+void quant_ul_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b){
+ quant_udaf_hftaZ_HFTA_AGGR_INIT_<gs_uint64_t>(b);
+}
+void quant_ul_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_uint64_t v){
+ quant_udaf_hftaZ_HFTA_AGGR_UPDATE_<gs_uint64_t>(b,v);
+}
+void quant_ul_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
+ quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_<gs_uint64_t>(r,b);
+}
+void quant_ul_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){
+ quant_udaf_hftaZ_HFTA_AGGR_DESTROY_<gs_uint64_t>(b);
+}
+gs_uint64_t extr_quant_ul_hftaZ_fcn(vstring *v, gs_float_t phi) {
+ return extr_quant_hftaZ_fcn<gs_uint64_t>(v,phi);
+}
+gs_uint64_t extr_med_ul_hftaZ_fcn(vstring *v){
+ return extr_med_hftaZ_fcn<gs_uint64_t>(v);
+}
+int quant_ul_udaf_hftaZ_nelem(gs_sp_t b) {
+ return quant_udaf_hftaZ_nelem<gs_uint64_t>(b);
+}
+
+// long long int
+void quant_l_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b){
+ quant_udaf_hftaZ_HFTA_AGGR_INIT_<gs_int64_t>(b);
+}
+void quant_l_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_int64_t v){
+ quant_udaf_hftaZ_HFTA_AGGR_UPDATE_<gs_int64_t>(b,v);
+}
+void quant_l_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
+ quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_<gs_int64_t>(r,b);
+}
+void quant_l_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){
+ quant_udaf_hftaZ_HFTA_AGGR_DESTROY_<gs_int64_t>(b);
+}
+gs_int64_t extr_quant_l_hftaZ_fcn(vstring *v, gs_float_t phi) {
+ return extr_quant_hftaZ_fcn<gs_int64_t>(v,phi);
+}
+gs_int64_t extr_med_l_hftaZ_fcn(vstring *v){
+ return extr_med_hftaZ_fcn<gs_int64_t>(v);
+}
+int quant_l_udaf_hftaZ_nelem(gs_sp_t b) {
+ return quant_udaf_hftaZ_nelem<gs_int64_t>(b);
+}
+
+
+// double
+void quant_f_udaf_hftaZ_HFTA_AGGR_INIT_(gs_sp_t b){
+ quant_udaf_hftaZ_HFTA_AGGR_INIT_<gs_float_t>(b);
+}
+void quant_f_udaf_hftaZ_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_float_t v){
+ quant_udaf_hftaZ_HFTA_AGGR_UPDATE_<gs_float_t>(b,v);
+}
+void quant_f_udaf_hftaZ_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b) {
+ quant_udaf_hftaZ_HFTA_AGGR_OUTPUT_<gs_float_t>(r,b);
+}
+void quant_f_udaf_hftaZ_HFTA_AGGR_DESTROY_(gs_sp_t b){
+ quant_udaf_hftaZ_HFTA_AGGR_DESTROY_<gs_float_t>(b);
+}
+gs_float_t extr_quant_f_hftaZ_fcn(vstring *v, gs_float_t phi) {
+ return extr_quant_hftaZ_fcn<gs_float_t>(v,phi);
+}
+gs_float_t extr_med_f_hftaZ_fcn(vstring *v){
+ return extr_med_hftaZ_fcn<gs_float_t>(v);
+}
+int quant_f_udaf_hftaZ_nelem(gs_sp_t b) {
+ return quant_udaf_hftaZ_nelem<gs_float_t>(b);
+}
+
+