7 #define QUANT_LFTA1_SIZE 729
8 #define QUANT_LFTA2_SIZE 181
9 #define QUANT_LFTA3_SIZE 100
11 #define QUANT_EPS 0.01
12 #define SKIPDIR_SIZE 100
13 #define SKIPDIR_HEIGHT_MAX 7
14 #define max(a,b) ((a) > (b) ? (a) : (b))
17 /****************************************************************/
19 /****************************************************************/
20 typedef struct tuple_t {
27 typedef struct supertuple_t {
31 struct supertuple_t *next;
34 /****************************************************************/
35 typedef gs_uint32_t val_type;
37 typedef struct skipnode {
43 typedef struct skipdir {
44 gs_uint32_t height; // height of tree
45 gs_uint32_t freeptr; // cursor space stack
46 gs_uint32_t headptr[SKIPDIR_HEIGHT_MAX]; // ptrs to levels
47 skipnode_t list[SKIPDIR_SIZE+1];
50 /****************************************************************/
52 typedef struct quant_udaf_hfta0_struct_t {
53 gs_uint32_t nelts; // 4 bytes
54 supertuple_t *t; // 8 bytes
55 } quant_udaf_hfta0_struct_t;
57 typedef struct quant_udaf_lfta1_struct_t {
59 gs_uint32_t samples[QUANT_LFTA1_SIZE];
60 } quant_udaf_lfta1_struct_t;
62 typedef struct quant_udaf_hfta1_struct_t {
63 gs_uint32_t nelts; // 4 bytes
64 supertuple_t *t; // 8 bytes
65 } quant_udaf_hfta1_struct_t;
67 typedef struct quant_udaf_lfta2_struct_t {
71 tuple_t t[QUANT_LFTA2_SIZE+1];
72 } quant_udaf_lfta2_struct_t;
74 typedef struct quant_udaf_hfta2_struct_t {
75 gs_uint32_t nelts; // 4 bytes
76 supertuple_t *t; // 8 bytes
77 } quant_udaf_hfta2_struct_t;
79 typedef struct quant_udaf_lfta3_struct_t {
85 tuple_t t[QUANT_LFTA3_SIZE+1];
87 } quant_udaf_lfta3_struct_t;
89 typedef struct quant_udaf_hfta3_struct_t {
90 gs_uint32_t nelts; // 4 bytes
91 supertuple_t *t; // 8 bytes
92 } quant_udaf_hfta3_struct_t;
96 /*************************** Version 0 **************************/
97 /* Version 0: HFTA-only */
98 /****************************************************************/
99 void quant_udaf_hfta0_print(quant_udaf_hfta0_struct_t *s)
103 gslog(LOG_DEBUG,"hfta nelts = %u\n",s->nelts);
104 gslog(LOG_DEBUG,"HFTA tuples:\n");
105 for (t=s->t; t != NULL; t=t->next) {
106 gslog(LOG_DEBUG,"(%u, %u, %u)\n",t->val,t->gap,t->del);
110 void quant_udaf_hfta0_compress(quant_udaf_hfta0_struct_t *s)
112 supertuple_t *t=s->t, *d;
113 gs_uint32_t threshold;
115 threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(s->nelts));
116 if ((t == NULL) || (t->next == NULL)) return;
118 while ((d != NULL) && (d->next != NULL)) {
119 if (d->gap+d->next->gap+d->next->del < threshold) {
120 d->next->gap += d->gap;
129 /****************************************************************/
130 /* HFTA0 functions */
131 /****************************************************************/
132 void quant_udaf_hfta0_HFTA_AGGR_INIT_(gs_sp_t b)
134 quant_udaf_hfta0_struct_t *s = (quant_udaf_hfta0_struct_t *)b;
139 void quant_udaf_hfta0_HFTA_AGGR_UPDATE_(gs_sp_t b, gs_uint32_t v)
141 quant_udaf_hfta0_struct_t *s = (quant_udaf_hfta0_struct_t *)b;
142 supertuple_t *t=s->t;
143 supertuple_t *newptr;
144 gs_uint32_t threshold;
145 gs_uint32_t val, gap;
149 // left boundary case
150 if ((!t) || (v <= t->val)) {
151 newptr = (supertuple_t *)malloc(sizeof(supertuple_t));
153 gslog(LOG_ALERT, "Out of space.\n");
164 // locate position that sandwiches v
165 while ((t->next) && (t->next->val < v))
168 // right boundary case
170 // create newptr node
171 newptr = (supertuple_t *)malloc(sizeof(supertuple_t));
180 obj = t->gap+t->next->gap+t->next->del;
181 threshold = (gs_uint32_t)ceil(2.0 * QUANT_EPS * (float)s->nelts);
182 if (obj <= threshold) {
183 // insert into existing bucket
187 newptr = (supertuple_t *)malloc(sizeof(supertuple_t));
190 newptr->del = t->next->gap+t->next->del-1;
191 newptr->next = t->next;
195 quant_udaf_hfta0_compress(s);
198 void quant_udaf_hfta0_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b)
200 r->length = sizeof(quant_udaf_hfta0_struct_t);
201 r->offset = (gs_p_t )b;
202 r->reserved = SHALLOW_COPY;
205 void quant_udaf_hfta0_HFTA_AGGR_DESTROY_(gs_sp_t b)
207 quant_udaf_hfta0_struct_t *s = (quant_udaf_hfta0_struct_t *)b;
208 supertuple_t *t=s->t, *n;
219 /****************************************************************/
220 /* HFTA0 Extraction functions */
221 /****************************************************************/
222 gs_uint32_t extr_quant_hfta0_fcn(vstring *v, gs_float_t phi)
224 //printf("In extr_quant_hfta0_fcn offset=%llx length=%d\n",v->offset, v->length);
225 quant_udaf_hfta0_struct_t *vs = (quant_udaf_hfta0_struct_t *)(v->offset);
226 //printf("nelts=%d t=%llx\n",vs->nelts, (unsigned long long int)(vs->t));
229 gs_int32_t rmin=0, rmax, rank, ropt=INT_MAX;
232 for (t=vs->t; t != NULL; t=t->next) {
233 //printf("in loop.\n");
234 //printf("gap is %d\n",t->gap);
238 rank = (gs_int32_t) (phi*(float)nelts);
240 for (t=vs->t; t != NULL; t=t->next) {
243 if (max(abs(rmin-rank), abs(rmax-rank)) < ropt) {
245 ropt = max(abs(rmin-rank), abs(rmax-rank));
251 gs_uint32_t extr_med_hfta0_fcn(vstring *v)
253 return extr_quant_hfta0_fcn(v, 0.5);
256 gs_uint32_t extr_quant_hfta0_space(vstring *v)
258 quant_udaf_hfta0_struct_t *vs = (quant_udaf_hfta0_struct_t *)(v->offset);
262 for (t=vs->t; t != NULL; t=t->next)
268 /*************************** Version 3 **************************/
269 /* Version 3: LFTA-medium */
270 /****************************************************************/
271 void quant_hfta3_print(quant_udaf_hfta3_struct_t *s)
275 //printf("In quant_hfta3_print, s=%llx, t=%llx\n",(unsigned long long int)s,(unsigned long long int)(s->t));
276 gslog(LOG_DEBUG,"HFTA tuples:\n");
277 for (t=s->t; t != NULL; t=t->next) {
278 gslog(LOG_DEBUG,"(%u, %u, %u)\n",t->val,t->gap,t->del);
282 void quant_hfta3_compress(quant_udaf_hfta3_struct_t *s)
284 supertuple_t *t=s->t, *d;
285 gs_uint32_t threshold;
287 threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(s->nelts));
288 if ((t == NULL) || (t->next == NULL)) return;
290 while ((d != NULL) && (d->next != NULL)) {
291 if (d->gap+d->next->gap+d->next->del < threshold) {
292 d->next->gap += d->gap;
302 /****************************************************************/
303 /* HFTA3 functions */
304 /****************************************************************/
305 void quant_udaf_hfta3_HFTA_AGGR_INIT_(gs_sp_t b)
307 quant_udaf_hfta3_struct_t *s = (quant_udaf_hfta3_struct_t *)b;
312 void quant_udaf_hfta3_HFTA_AGGR_UPDATE_(gs_sp_t b, vstring *v)
314 quant_udaf_hfta3_struct_t *s = (quant_udaf_hfta3_struct_t *)b;
315 quant_udaf_lfta3_struct_t *vs = (quant_udaf_lfta3_struct_t *)(v->offset);
316 supertuple_t *t=s->t, *tprev=NULL;
318 supertuple_t *newptr;
319 gs_uint32_t uptr = vs->usedptr;
320 gs_uint32_t threshold;
322 if (uptr == 0) return;
323 //if (v->length != sizeof(quant_udaf_lfta3_struct_t)) return;
325 threshold = (gs_uint32_t)ceil((2.0 * QUANT_EPS) * (float)(vs->nelts));
327 if ((u[uptr].next != 0) && (u[uptr].gap+u[u[uptr].next].gap+u[u[uptr].next].del < threshold)) {
328 u[u[uptr].next].gap += u[uptr].gap;
331 // find position in superstructure
332 while ((t != NULL) && (t->val <= u[uptr].val)) {
333 if (t->val == u[uptr].val) {
334 t->gap += u[uptr].gap;
335 t->del += u[uptr].del;
340 t->del += u[uptr].gap+u[uptr].del-1;
346 // create newptr node
347 newptr = (supertuple_t *)malloc(sizeof(supertuple_t));
348 newptr->val = u[uptr].val;
349 newptr->gap = u[uptr].gap;
350 newptr->del = u[uptr].del;
352 newptr->del += t->gap + t->del - 1;
353 // merge into superstructure
358 tprev->next = newptr;
360 s->nelts += u[uptr].gap;
364 quant_hfta3_compress(s);
365 //quant_hfta3_print(s);
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));
369 void quant_udaf_hfta3_HFTA_AGGR_OUTPUT_(vstring *r, gs_sp_t b)
371 r->length = sizeof(quant_udaf_hfta3_struct_t);
372 r->offset = (gs_p_t )b;
373 r->reserved = SHALLOW_COPY;
375 quant_udaf_hfta3_struct_t *s = (quant_udaf_hfta3_struct_t *)b;
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));
379 void quant_udaf_hfta3_HFTA_AGGR_DESTROY_(gs_sp_t b)
384 /****************************************************************/
385 /* HFTA3 Extraction functions */
386 /****************************************************************/
387 gs_uint32_t extr_quant_hfta3_fcn(vstring *v, gs_float_t phi)
389 quant_udaf_hfta3_struct_t *vs = (quant_udaf_hfta3_struct_t *)(v->offset);
392 gs_int32_t rmin=0, rmax, rank, ropt=INT_MAX;
395 for (t=vs->t; t != NULL; t=t->next) {
399 rank = (gs_int32_t) (phi*(float)nelts);
401 for (t=vs->t; t != NULL; t=t->next) {
404 if (max(abs(rmin-rank), abs(rmax-rank)) < ropt) {
406 ropt = max(abs(rmin-rank), abs(rmax-rank));
412 gs_uint32_t extr_med_hfta3_fcn(vstring *v)
414 return extr_quant_hfta3_fcn(v, 0.5);
417 gs_uint32_t extr_quant_hfta3_space(vstring *v)
419 quant_udaf_hfta3_struct_t *vs = (quant_udaf_hfta3_struct_t *)(v->offset);
423 for (t=vs->t; t != NULL; t=t->next)