-#include <stdio.h>\r
-#include <stdlib.h>\r
-#include <limits.h>\r
-#include <math.h>\r
-#include "hfta_udaf.h"\r
-\r
-#define QUANT_LFTA1_SIZE 729\r
-#define QUANT_LFTA2_SIZE 181\r
-#define QUANT_LFTA3_SIZE 100\r
-\r
-#define QUANT_EPS 0.01\r
-#define SKIPDIR_SIZE 100\r
-#define SKIPDIR_HEIGHT_MAX 7\r
-#define max(a,b) ((a) > (b) ? (a) : (b))\r
-\r
-\r
-/****************************************************************/\r
-/* Data Structures */\r
-/****************************************************************/\r
-typedef struct tuple_t {\r
- gs_uint32_t val;\r
- gs_uint32_t gap;\r
- gs_uint32_t del;\r
- gs_uint32_t next;\r
-} tuple_t;\r
-\r
-typedef struct supertuple_t {\r
- gs_uint32_t val;\r
- gs_uint32_t gap;\r
- gs_uint32_t del;\r
- struct supertuple_t *next;\r
-} supertuple_t;\r
-\r
-/****************************************************************/\r
-typedef gs_uint32_t val_type;\r
-\r
-typedef struct skipnode {\r
- val_type val;\r
- gs_uint32_t next;\r
- gs_uint32_t down;\r
-} skipnode_t;\r
-\r
-typedef struct skipdir {\r
- gs_uint32_t height; // height of tree\r
- gs_uint32_t freeptr; // cursor space stack\r
- gs_uint32_t headptr[SKIPDIR_HEIGHT_MAX]; // ptrs to levels\r
- skipnode_t list[SKIPDIR_SIZE+1];\r
-} skipdir_t;\r
-\r
-/****************************************************************/\r
-\r
-typedef struct quant_udaf_hfta0_struct_t {\r
- gs_uint32_t nelts; // 4 bytes\r
- supertuple_t *t; // 8 bytes\r
-} quant_udaf_hfta0_struct_t;\r
-\r
-typedef struct quant_udaf_lfta1_struct_t {\r
- gs_uint32_t nelts;\r
- gs_uint32_t samples[QUANT_LFTA1_SIZE];\r
-} quant_udaf_lfta1_struct_t;\r
-\r
-typedef struct quant_udaf_hfta1_struct_t {\r
- gs_uint32_t nelts; // 4 bytes\r
- supertuple_t *t; // 8 bytes\r
-} quant_udaf_hfta1_struct_t;\r
-\r
-typedef struct quant_udaf_lfta2_struct_t {\r
- gs_uint32_t nelts;\r
- gs_uint32_t freeptr;\r
- gs_uint32_t usedptr;\r
- tuple_t t[QUANT_LFTA2_SIZE+1];\r
-} quant_udaf_lfta2_struct_t;\r
-\r
-typedef struct quant_udaf_hfta2_struct_t {\r
- gs_uint32_t nelts; // 4 bytes\r
- supertuple_t *t; // 8 bytes\r
-} quant_udaf_hfta2_struct_t;\r
-\r
-typedef struct quant_udaf_lfta3_struct_t {\r
- gs_uint32_t nelts;\r
- gs_uint32_t freeptr;\r
- gs_uint32_t usedptr;\r
- gs_uint32_t circptr;\r
- gs_uint32_t size;\r
- tuple_t t[QUANT_LFTA3_SIZE+1];\r
- skipdir_t sd;\r
-} quant_udaf_lfta3_struct_t;\r
-\r
-typedef struct quant_udaf_hfta3_struct_t {\r
- gs_uint32_t nelts; // 4 bytes\r
- supertuple_t *t; // 8 bytes\r
-} quant_udaf_hfta3_struct_t;\r
-\r
-\r
-\r
-/*************************** Version 0 **************************/\r
-/* Version 0: HFTA-only */\r
-/****************************************************************/\r
-void quant_udaf_hfta0_print(quant_udaf_hfta0_struct_t *s)\r
-{\r
- supertuple_t *t;\r
-\r
- gslog(LOG_DEBUG,"hfta nelts = %u\n",s->nelts);\r
- gslog(LOG_DEBUG,"HFTA tuples:\n");\r
- for (t=s->t; t != NULL; t=t->next) {\r
- gslog(LOG_DEBUG,"(%u, %u, %u)\n",t->val,t->gap,t->del);\r
- }\r
-}\r
-\r
-void quant_udaf_hfta0_compress(quant_udaf_hfta0_struct_t *s)\r
-{\r
- supertuple_t *t=s->t, *d;\r
- gs_uint32_t threshold;\r
-\r
- threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(s->nelts));\r
- if ((t == NULL) || (t->next == NULL)) return;\r
- d = t->next;\r
- while ((d != NULL) && (d->next != NULL)) {\r
- if (d->gap+d->next->gap+d->next->del < threshold) {\r
- d->next->gap += d->gap;\r
- t->next = d->next;\r
- free(d);\r
- }\r
- t = t->next;\r
- d = t->next;\r
- }\r
-}\r
-\r
-/****************************************************************/\r
-/* HFTA0 functions */\r
-/****************************************************************/\r
-void quant_udaf_hfta0_HFTA_AGGR_INIT_(gs_sp_t b)\r
-{\r
- quant_udaf_hfta0_struct_t *s = (quant_udaf_hfta0_struct_t *)b;\r
- s->nelts = 0;\r
- s->t = NULL;\r
-}\r
-\r
-void quant_udaf_hfta0_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_uint32_t v)\r
-{\r
- quant_udaf_hfta0_struct_t *s = (quant_udaf_hfta0_struct_t *)b;\r
- supertuple_t *t=s->t;\r
- supertuple_t *newptr;\r
- gs_uint32_t threshold;\r
- gs_uint32_t val, gap;\r
- gs_uint32_t obj;\r
-\r
- s->nelts++;\r
- // left boundary case\r
- if ((!t) || (v <= t->val)) {\r
- newptr = (supertuple_t *)malloc(sizeof(supertuple_t));\r
- if (!newptr) {\r
- gslog(LOG_ALERT, "Out of space.\n");\r
- return;\r
- }\r
- newptr->val = v;\r
- newptr->gap = 1;\r
- newptr->del = 0;\r
- newptr->next = s->t;\r
- s->t = newptr;\r
- return;\r
- }\r
-\r
- // locate position that sandwiches v\r
- while ((t->next) && (t->next->val < v))\r
- t = t->next;\r
-\r
- // right boundary case\r
- if (!t->next) {\r
- // create newptr node\r
- newptr = (supertuple_t *)malloc(sizeof(supertuple_t));\r
- newptr->val = v;\r
- newptr->gap = 1;\r
- newptr->del = 0;\r
- newptr->next = NULL;\r
- t->next = newptr;\r
- }\r
- // non-boundary case\r
- else {\r
- obj = t->gap+t->next->gap+t->next->del;\r
- threshold = (gs_uint32_t)ceil(2.0 * QUANT_EPS * (float)s->nelts);\r
- if (obj <= threshold) {\r
- // insert into existing bucket\r
- t->next->gap++;\r
- }\r
- else {\r
- newptr = (supertuple_t *)malloc(sizeof(supertuple_t));\r
- newptr->val = v;\r
- newptr->gap = 1;\r
- newptr->del = t->next->gap+t->next->del-1;\r
- newptr->next = t->next;\r
- t->next = newptr;\r
- }\r
- }\r
- quant_udaf_hfta0_compress(s);\r
-}\r
-\r
-void quant_udaf_hfta0_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b)\r
-{\r
- r->length = sizeof(quant_udaf_hfta0_struct_t);\r
- r->offset = (gs_p_t )b;\r
- r->reserved = SHALLOW_COPY;\r
-}\r
-\r
-void quant_udaf_hfta0_HFTA_AGGR_DESTROY_(gs_sp_t b)\r
-{\r
- quant_udaf_hfta0_struct_t *s = (quant_udaf_hfta0_struct_t *)b;\r
- supertuple_t *t=s->t, *n;\r
- while(t){\r
- n=t->next;\r
- free(t);\r
- t=n;\r
- }\r
-\r
- return;\r
-}\r
-\r
-\r
-/****************************************************************/\r
-/* HFTA0 Extraction functions */\r
-/****************************************************************/\r
-gs_uint32_t extr_quant_hfta0_fcn(vstring *v, gs_float_t phi)\r
-{\r
-//printf("In extr_quant_hfta0_fcn offset=%llx length=%d\n",v->offset, v->length);\r
- quant_udaf_hfta0_struct_t *vs = (quant_udaf_hfta0_struct_t *)(v->offset);\r
-//printf("nelts=%d t=%llx\n",vs->nelts, (unsigned long long int)(vs->t));\r
- supertuple_t *t, *p;\r
- gs_uint32_t nelts=0;\r
- gs_uint32_t rmin=0, rmax, rank, ropt=UINT_MAX;\r
- gs_uint32_t count=0;\r
-\r
- for (t=vs->t; t != NULL; t=t->next) {\r
-//printf("in loop.\n");\r
-//printf("gap is %d\n",t->gap);\r
- nelts += t->gap;\r
- count++;\r
- }\r
- rank = (gs_uint32_t) (phi*(float)nelts);\r
-\r
- for (t=vs->t; t != NULL; t=t->next) {\r
- rmin += t->gap;\r
- rmax = rmin+t->del;\r
- if (max(abs(rmin-rank), abs(rmax-rank)) < ropt) {\r
- p = t;\r
- ropt = max(abs(rmin-rank), abs(rmax-rank));\r
- }\r
- }\r
- return p->val;\r
-}\r
-\r
-gs_uint32_t extr_med_hfta0_fcn(vstring *v)\r
-{\r
- return extr_quant_hfta0_fcn(v, 0.5);\r
-}\r
-\r
-gs_uint32_t extr_quant_hfta0_space(vstring *v)\r
-{\r
- quant_udaf_hfta0_struct_t *vs = (quant_udaf_hfta0_struct_t *)(v->offset);\r
- supertuple_t *t;\r
- gs_uint32_t count=0;\r
-\r
- for (t=vs->t; t != NULL; t=t->next)\r
- count++;\r
- return count;\r
-}\r
-\r
-\r
-/*************************** Version 3 **************************/\r
-/* Version 3: LFTA-medium */\r
-/****************************************************************/\r
-void quant_hfta3_print(quant_udaf_hfta3_struct_t *s)\r
-{\r
- supertuple_t *t;\r
-\r
-//printf("In quant_hfta3_print, s=%llx, t=%llx\n",(unsigned long long int)s,(unsigned long long int)(s->t));\r
- gslog(LOG_DEBUG,"HFTA tuples:\n");\r
- for (t=s->t; t != NULL; t=t->next) {\r
- gslog(LOG_DEBUG,"(%u, %u, %u)\n",t->val,t->gap,t->del);\r
- }\r
-}\r
-\r
-void quant_hfta3_compress(quant_udaf_hfta3_struct_t *s)\r
-{\r
- supertuple_t *t=s->t, *d;\r
- gs_uint32_t threshold;\r
-\r
- threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(s->nelts));\r
- if ((t == NULL) || (t->next == NULL)) return;\r
- d = t->next;\r
- while ((d != NULL) && (d->next != NULL)) {\r
- if (d->gap+d->next->gap+d->next->del < threshold) {\r
- d->next->gap += d->gap;\r
- t->next = d->next;\r
- free(d);\r
- }\r
- t = t->next;\r
- d = t->next;\r
- }\r
-}\r
-\r
-\r
-/****************************************************************/\r
-/* HFTA3 functions */\r
-/****************************************************************/\r
-void quant_udaf_hfta3_HFTA_AGGR_INIT_(gs_sp_t b)\r
-{\r
- quant_udaf_hfta3_struct_t *s = (quant_udaf_hfta3_struct_t *)b;\r
- s->nelts = 0;\r
- s->t = NULL;\r
-}\r
-\r
-void quant_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v)\r
-{\r
- quant_udaf_hfta3_struct_t *s = (quant_udaf_hfta3_struct_t *)b;\r
- quant_udaf_lfta3_struct_t *vs = (quant_udaf_lfta3_struct_t *)(v->offset);\r
- supertuple_t *t=s->t, *tprev=NULL;\r
- tuple_t *u=vs->t;\r
- supertuple_t *newptr;\r
- gs_uint32_t uptr = vs->usedptr;\r
- gs_uint32_t threshold;\r
-\r
- if (uptr == 0) return;\r
- //if (v->length != sizeof(quant_udaf_lfta3_struct_t)) return;\r
-\r
- threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(vs->nelts));\r
- while (uptr != 0) {\r
- if ((u[uptr].next != 0) && (u[uptr].gap+u[u[uptr].next].gap+u[u[uptr].next].del < threshold)) {\r
- u[u[uptr].next].gap += u[uptr].gap;\r
- }\r
- else {\r
- // find position in superstructure\r
- while ((t != NULL) && (t->val <= u[uptr].val)) {\r
- if (t->val == u[uptr].val) {\r
- t->gap += u[uptr].gap;\r
- t->del += u[uptr].del;\r
- uptr = u[uptr].next;\r
- if (!uptr) break;\r
- }\r
- else {\r
- t->del += u[uptr].gap+u[uptr].del-1;\r
- }\r
- tprev = t;\r
- t = t->next;\r
- }\r
- if (!uptr) break;\r
- // create newptr node\r
- newptr = (supertuple_t *)malloc(sizeof(supertuple_t));\r
- newptr->val = u[uptr].val;\r
- newptr->gap = u[uptr].gap;\r
- newptr->del = u[uptr].del;\r
- if (t != NULL)\r
- newptr->del += t->gap + t->del - 1;\r
- // merge into superstructure\r
- newptr->next = t;\r
- if (tprev == NULL)\r
- s->t = newptr;\r
- else\r
- tprev->next = newptr;\r
- tprev = newptr;\r
- s->nelts += u[uptr].gap;\r
- }\r
- uptr = u[uptr].next;\r
- }\r
- quant_hfta3_compress(s);\r
-//quant_hfta3_print(s);\r
-//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
-}\r
-\r
-void quant_udaf_hfta3_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b)\r
-{\r
- r->length = sizeof(quant_udaf_hfta3_struct_t);\r
- r->offset = (gs_p_t )b;\r
- r->reserved = SHALLOW_COPY;\r
-\r
- quant_udaf_hfta3_struct_t *s = (quant_udaf_hfta3_struct_t *)b;\r
-//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
-}\r
-\r
-void quant_udaf_hfta3_HFTA_AGGR_DESTROY_(gs_sp_t b)\r
-{\r
- return;\r
-}\r
-\r
-/****************************************************************/\r
-/* HFTA3 Extraction functions */\r
-/****************************************************************/\r
-gs_uint32_t extr_quant_hfta3_fcn(vstring *v, gs_float_t phi)\r
-{\r
- quant_udaf_hfta3_struct_t *vs = (quant_udaf_hfta3_struct_t *)(v->offset);\r
- supertuple_t *t, *p;\r
- gs_uint32_t nelts=0;\r
- gs_uint32_t rmin=0, rmax, rank, ropt=UINT_MAX;\r
- gs_uint32_t count=0;\r
-\r
- for (t=vs->t; t != NULL; t=t->next) {\r
- nelts += t->gap;\r
- count++;\r
- }\r
- rank = (gs_uint32_t) (phi*(float)nelts);\r
-\r
- for (t=vs->t; t != NULL; t=t->next) {\r
- rmin += t->gap;\r
- rmax = rmin+t->del;\r
- if (max(abs(rmin-rank), abs(rmax-rank)) < ropt) {\r
- p = t;\r
- ropt = max(abs(rmin-rank), abs(rmax-rank));\r
- }\r
- }\r
- return p->val;\r
-}\r
-\r
-gs_uint32_t extr_med_hfta3_fcn(vstring *v)\r
-{\r
- return extr_quant_hfta3_fcn(v, 0.5);\r
-}\r
-\r
-gs_uint32_t extr_quant_hfta3_space(vstring *v)\r
-{\r
- quant_udaf_hfta3_struct_t *vs = (quant_udaf_hfta3_struct_t *)(v->offset);\r
- supertuple_t *t;\r
- gs_uint32_t count=0;\r
-\r
- for (t=vs->t; t != NULL; t=t->next)\r
- count++;\r
- return count;\r
-}\r
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+#include <math.h>
+#include "hfta_udaf.h"
+
+#define QUANT_LFTA1_SIZE 729
+#define QUANT_LFTA2_SIZE 181
+#define QUANT_LFTA3_SIZE 100
+
+#define QUANT_EPS 0.01
+#define SKIPDIR_SIZE 100
+#define SKIPDIR_HEIGHT_MAX 7
+#define max(a,b) ((a) > (b) ? (a) : (b))
+
+
+/****************************************************************/
+/* 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;
+
+typedef struct skipnode {
+ val_type val;
+ gs_uint32_t next;
+ gs_uint32_t down;
+} skipnode_t;
+
+typedef struct skipdir {
+ 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;
+
+/****************************************************************/
+
+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 {
+ 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);
+ }
+}
+
+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;
+}
+
+
+/****************************************************************/
+/* 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);
+
+ 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)
+{
+ supertuple_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");
+ for (t=s->t; t != NULL; t=t->next) {
+ gslog(LOG_DEBUG,"(%u, %u, %u)\n",t->val,t->gap,t->del);
+ }
+}
+
+void quant_hfta3_compress(quant_udaf_hfta3_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;
+ }
+}
+
+
+/****************************************************************/
+/* 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;
+ s->nelts = 0;
+ s->t = NULL;
+}
+
+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;
+ gs_uint32_t uptr = vs->usedptr;
+ gs_uint32_t threshold;
+
+ if (uptr == 0) return;
+ //if (v->length != sizeof(quant_udaf_lfta3_struct_t)) return;
+
+ threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(vs->nelts));
+ while (uptr != 0) {
+ 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;
+ }
+ else {
+ // find position in superstructure
+ while ((t != NULL) && (t->val <= u[uptr].val)) {
+ if (t->val == u[uptr].val) {
+ t->gap += u[uptr].gap;
+ t->del += u[uptr].del;
+ uptr = u[uptr].next;
+ if (!uptr) break;
+ }
+ else {
+ t->del += u[uptr].gap+u[uptr].del-1;
+ }
+ tprev = t;
+ t = t->next;
+ }
+ if (!uptr) break;
+ // create newptr node
+ newptr = (supertuple_t *)malloc(sizeof(supertuple_t));
+ newptr->val = u[uptr].val;
+ newptr->gap = u[uptr].gap;
+ newptr->del = u[uptr].del;
+ if (t != NULL)
+ newptr->del += t->gap + t->del - 1;
+ // merge into superstructure
+ newptr->next = t;
+ if (tprev == NULL)
+ s->t = newptr;
+ else
+ tprev->next = newptr;
+ tprev = newptr;
+ s->nelts += u[uptr].gap;
+ }
+ uptr = u[uptr].next;
+ }
+ 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);
+ r->offset = (gs_p_t )b;
+ r->reserved = SHALLOW_COPY;
+
+ quant_udaf_hfta3_struct_t *s = (quant_udaf_hfta3_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)
+{
+ return;
+}
+
+/****************************************************************/
+/* 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;
+ 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) {
+ nelts += t->gap;
+ count++;
+ }
+ rank = (gs_uint32_t) (phi*(float)nelts);
+
+ 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_hfta3_fcn(vstring *v)
+{
+ return extr_quant_hfta3_fcn(v, 0.5);
+}
+
+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;
+ gs_uint32_t count=0;
+
+ for (t=vs->t; t != NULL; t=t->next)
+ count++;
+ return count;
+}
Code Review / com / gs-lite.git / blobdiff