9 #define QUANT_LFTA1_SIZE 729
10 #define QUANT_LFTA2_SIZE 181
11 #define QUANT_LFTA3_SIZE 100
16 #define QUANT_LFTA1_SIZE 378
17 #define QUANT_LFTA2_SIZE 93
18 #define QUANT_LFTA3_SIZE 50
21 #define QUANT_LFTA1_SIZE 202
22 #define QUANT_LFTA2_SIZE 49
23 #define QUANT_LFTA3_SIZE 25
27 #define QUANT_EPS 0.01
28 #define SKIPDIR_SIZE 100
29 #define SKIPDIR_HEIGHT_MAX 7
30 #define max(a,b) ((a) > (b) ? (a) : (b))
31 #define COMPRESSED_XFER
33 /****************************************************************/
35 /****************************************************************/
36 typedef struct tuple_t {
44 typedef gs_uint32_t val_type;
46 typedef struct skipnode {
52 typedef struct skipdir {
53 gs_uint32_t height; // height of tree
54 gs_uint32_t freeptr; // cursor space stack
55 gs_uint32_t headptr[SKIPDIR_HEIGHT_MAX+1]; // ptrs to levels
56 skipnode_t list[SKIPDIR_SIZE+1];
60 /****************************************************************/
62 // fstring(5+(QUANT_LFTA3_SIZE+1)*4 +
63 // (2+lg(QUANT_LFTA3_SIZE)+(QUANT_LFTA3_SIZE+1)*3)*4)
64 typedef struct quant_udaf_lfta3_struct_t {
65 gs_uint32_t nelts; // # stream elements
66 gs_uint32_t freeptr; // ptr to cursor stack
67 gs_uint32_t usedptr; // ptr to allocated memory
68 gs_uint32_t circptr; // circulating ptr used for compression
70 tuple_t t[QUANT_LFTA3_SIZE+1]; // samples + auxiliary info
71 skipdir_t sd; // directory for searching tuples
72 } quant_udaf_lfta3_struct_t;
74 /****************************************************************/
75 /* Skip List Functions */
76 /****************************************************************/
78 // Skip list cursor stack operations
79 gs_uint32_t skipdir_alloc(skipdir_t *sd)
81 gs_uint32_t ptr = sd->freeptr;
83 sd->freeptr = sd->list[ptr].next;
87 void skipdir_free(skipdir_t *sd, gs_uint32_t ptr)
89 sd->list[ptr].val = 0;
90 sd->list[ptr].down = 0;
91 sd->list[ptr].next = sd->freeptr;
96 void skipdir_create(skipdir_t *sd)
102 for (i=0; i < SKIPDIR_HEIGHT_MAX; i++)
104 for (i=1; i < SKIPDIR_SIZE; i++)
105 sd->list[i].next = i+1;
106 sd->list[SKIPDIR_SIZE].next = 0;
109 void skipdir_destroy(skipdir_t *sd)
115 void skipdir_search(skipdir_t *sd, val_type val, gs_uint32_t *ptrstack)
120 if (sd->height == 0) {
121 ptrstack[0] = ptrstack[1] = 0;
124 // search nonleaf nodes
125 ptr = sd->headptr[sd->height-1];
126 for (l=sd->height-1; l >= 0; l--) {
129 ptr = (l > 0) ? sd->headptr[l-1] : 0;
131 else if (val <= sd->list[ptr].val) {
133 ptr = (l > 0) ? sd->headptr[l-1] : 0;
136 while ((sd->list[ptr].next != 0) &&
137 (sd->list[sd->list[ptr].next].val < val))
138 ptr = sd->list[ptr].next;
140 ptr = sd->list[ptr].down;
147 void skipdir_insert(skipdir_t *sd, gs_uint32_t *ptrstack,
148 gs_uint32_t leafptr, val_type val)
150 gs_uint32_t newptr, oldptr;
153 // if path already existed then point to new duplicate
154 if ((ptrstack[1] == 0) && (sd->headptr[0] != 0)
155 && (sd->list[sd->headptr[0]].val == val)) {
156 sd->list[sd->headptr[0]].down = leafptr;
159 if ((ptrstack[1] != 0) && (sd->list[ptrstack[1]].next != 0)
160 && (sd->list[sd->list[ptrstack[1]].next].val == val)) {
161 sd->list[sd->list[ptrstack[1]].next].down = leafptr;
165 for (l=0; l < SKIPDIR_HEIGHT_MAX; l++) {
166 if (random() % 2) break;
167 newptr = skipdir_alloc(sd);
168 if (!newptr) break; // out of memory
169 sd->list[newptr].val = val;
170 //copy(&val, &list[newptr[l]].val);
171 // link new directory node to level below
173 sd->list[newptr].down = oldptr;
175 sd->list[newptr].down = leafptr;
176 // insert node into current level
177 if ((l >= sd->height) || (ptrstack[l+1] == 0)) {
178 sd->list[newptr].next = sd->headptr[l];
179 sd->headptr[l] = newptr;
182 sd->list[newptr].next = sd->list[ptrstack[l+1]].next;
183 sd->list[ptrstack[l+1]].next = newptr;
187 if (l > sd->height) sd->height = l;
188 //fprintf(stderr,"new height = %u\n",sd->height);
192 void skipdir_delete(skipdir_t *sd, gs_uint32_t *ptrstack, val_type val)
197 for (l=0; l < sd->height; l++) {
198 if (ptrstack[l+1] == 0) {
199 delptr = sd->headptr[l];
200 if (delptr == 0) break;
201 if (sd->list[delptr].val == val) {
202 sd->headptr[l] = sd->list[delptr].next;
203 skipdir_free(sd, delptr);
209 delptr = sd->list[ptrstack[l+1]].next;
210 if (delptr == 0) break;
211 if (sd->list[delptr].val == val) {
212 sd->list[ptrstack[l+1]].next = sd->list[delptr].next;
213 skipdir_free(sd, delptr);
222 void skipdir_print(skipdir_t *sd)
227 for (l=sd->height-1; l >= 0; l--) {
228 for (ptr=sd->headptr[l]; ptr != 0; ptr=sd->list[ptr].next)
229 fprintf(stderr,"%u ", sd->list[ptr].val);
230 fprintf(stderr,"\n");
232 fprintf(stderr,"-------\n");
233 for (l=sd->height-1; l > 0; l--) {
234 for (ptr=sd->headptr[l]; ptr != 0; ptr=sd->list[ptr].next)
235 fprintf(stderr,"%u ", sd->list[sd->list[ptr].down].val);
236 fprintf(stderr,"\n");
238 fprintf(stderr,"-------\n");
244 /*************************** Version 3 **************************/
245 /* Version 3: LFTA-medium */
247 /* NIC performs O(log n) operations at each update. */
248 /****************************************************************/
250 /****************************************************************/
251 /* Helper functions */
252 /****************************************************************/
253 gs_uint32_t quant_udaf_lfta3_cursor_alloc(quant_udaf_lfta3_struct_t *s)
255 gs_uint32_t ptr = s->freeptr;
256 if (s->freeptr != 0) s->freeptr = s->t[ptr].next;
261 void quant_udaf_lfta3_cursor_free(quant_udaf_lfta3_struct_t *s, gs_uint32_t ptr)
263 s->t[ptr].next = s->freeptr;
268 void quant_lfta3_print(quant_udaf_lfta3_struct_t *s)
271 gs_uint32_t ptr = s->usedptr;
274 fprintf(stderr,"<empty>\n");
277 //skipdir_print(&s->sd);
278 for (; ptr != 0; ptr=t[ptr].next) {
279 fprintf(stderr,"(%u, %u, %u) ",t[ptr].val,t[ptr].gap,t[ptr].del);
281 fprintf(stderr,"\n");
284 void quant_lfta3_compress(quant_udaf_lfta3_struct_t *s)
288 gs_uint32_t threshold;
289 gs_uint32_t ptrstack[SKIPDIR_HEIGHT_MAX+5];
291 threshold = (gs_uint32_t)ceil(2.0 * QUANT_EPS * (gs_float_t)s->nelts);
292 //if(s->circptr < 0 || s->circptr >= QUANT_LFTA3_SIZE)
293 // printf("1) s->circptr = %d\n",s->circptr);
294 //if(t[s->circptr].next < 0 || t[s->circptr].next >= QUANT_LFTA3_SIZE)
295 // printf("t[s->circptr].next = %d\n",t[s->circptr].next);
296 if ((s->circptr == 0) || (t[s->circptr].next == 0)
297 || (t[t[s->circptr].next].next == 0))
298 s->circptr = s->usedptr;
299 //if ((s->size % 10) != 0) return;
301 //if(s->circptr < 0 || s->circptr >= QUANT_LFTA3_SIZE)
302 // printf("2) s->circptr = %d\n",s->circptr);
303 delptr = t[s->circptr].next;
304 //if(delptr < 0 || delptr >= QUANT_LFTA3_SIZE)
305 // printf("delptr = %d\n",delptr);
306 //if(t[delptr].next < 0 || t[delptr].next >= QUANT_LFTA3_SIZE)
307 // printf("t[delptr].next = %d\n",t[delptr].next);
308 if (t[delptr].gap+t[t[delptr].next].gap+t[t[delptr].next].del < threshold) {
309 // delete from directory
310 if (t[s->circptr].val != t[delptr].val) {
311 // leftmost duplicate (if multiplicity)
312 skipdir_search(&(s->sd), t[delptr].val, ptrstack);
313 if (t[delptr].val == t[t[delptr].next].val) {
314 //if(s->sd.headptr[0] < 0 || s->sd.headptr[0] >= QUANT_LFTA3_SIZE)
315 // printf("s->sd.headptr[0] = %d\n",s->sd.headptr[0]);
317 if ((ptrstack[1] == 0)
318 && (s->sd.headptr[0] != 0)
319 && (s->sd.list[s->sd.headptr[0]].val == t[delptr].val))
320 s->sd.list[s->sd.headptr[0]].down = t[delptr].next;
321 else if ((ptrstack[1] != 0)
322 && (s->sd.list[ptrstack[1]].next != 0)
323 && (s->sd.list[s->sd.list[ptrstack[1]].next].val == t[delptr].val))
324 s->sd.list[s->sd.list[ptrstack[1]].next].down = t[delptr].next;
327 // non-duplicates case
328 skipdir_delete(&(s->sd), ptrstack, t[delptr].val);
332 //fprintf(stderr,"DELETED %u\n", t[delptr].val);
333 t[s->circptr].next = t[delptr].next;
334 quant_udaf_lfta3_cursor_free(s, delptr);
337 s->circptr = t[s->circptr].next;
343 /****************************************************************/
344 /* LFTA3 functions */
345 /****************************************************************/
346 void quant_udaf_lfta3_LFTA_AGGR_INIT_(gs_sp_t b)
350 quant_udaf_lfta3_struct_t *s = (quant_udaf_lfta3_struct_t *)b;
352 s->usedptr = 0; // NULL ptr
354 // initialize cursor stack
357 for (i=1; i < QUANT_LFTA3_SIZE; i++)
359 s->t[QUANT_LFTA3_SIZE].next = 0;
360 skipdir_create(&(s->sd));
363 void quant_udaf_lfta3_LFTA_AGGR_UPDATE_(gs_sp_t b, gs_uint32_t v)
365 quant_udaf_lfta3_struct_t *s = (quant_udaf_lfta3_struct_t *)b;
367 gs_uint32_t ptr = s->usedptr;
368 gs_uint32_t newptr, delptr;
369 gs_uint32_t obj; // objective function
370 gs_uint32_t threshold;
371 gs_uint32_t ptrstack[SKIPDIR_HEIGHT_MAX+5];
372 gs_uint32_t debugptr;
374 //printf("AGGR_UPDATE start\n");
376 //fprintf(stderr,"nelts = %u\n",s->nelts);
377 // left boundary case
378 if ((ptr == 0) || (v < t[ptr].val)) {
379 if (t[ptr].val == v) {
381 //printf("AGGR_UPDATE END 1\n");
384 newptr = quant_udaf_lfta3_cursor_alloc(s);
386 gslog(LOG_ALERT, "Out of space.\n");
392 t[newptr].next = s->usedptr;
394 //printf("AGGR_UPDATE END 2\n");
398 // locate $i$ such that (v_i-1 < v <= v_i)
399 skipdir_search(&(s->sd), v, ptrstack);
401 //ptr = (ptrstack[0] == 0) ? s->usedptr : s->sd.list[ptrstack[0]].down;
402 ptr = (ptrstack[0] == 0) ? s->usedptr : ptrstack[0];
403 while ((t[ptr].next != 0) && (t[t[ptr].next].val < v))
408 if ((t[ptr].next != 0) && (t[t[ptr].next].val == v)) {
409 t[t[ptr].next].gap++;
410 printf("AGGR_UPDATE END 3\n");
415 // right boundary case
416 if (t[ptr].next == 0) {
417 newptr = quant_udaf_lfta3_cursor_alloc(s);
419 gslog(LOG_ALERT, "Out of space.\n");
426 t[ptr].next = newptr;
427 //printf("AGGR_UPDATE END 4\n");
432 //printf("1) t[ptr].next =%d, ptr=%d\n",t[ptr].next,ptr);
433 obj = t[ptr].gap+t[t[ptr].next].gap+t[t[ptr].next].del;
434 threshold = (gs_uint32_t)ceil(2.0 * QUANT_EPS * (gs_float_t)s->nelts);
435 if (obj > threshold) {
436 newptr = quant_udaf_lfta3_cursor_alloc(s);
438 gslog(LOG_ALERT, "Out of memory.\n");
441 //printf("newptr=%d\n",newptr);
444 t[newptr].del = t[t[ptr].next].gap+t[t[ptr].next].del - 1;
445 t[newptr].next = t[ptr].next;
446 t[ptr].next = newptr;
447 skipdir_insert(&(s->sd), ptrstack, newptr, v);
450 // insert into existing bucket
451 //printf("t[ptr].next =%d\n",t[ptr].next);
452 t[t[ptr].next].gap++;
454 quant_lfta3_compress(s);
455 //printf("AGGR_UPDATE END 5\n");
458 gs_int32_t quant_udaf_lfta3_LFTA_AGGR_FLUSHME_(gs_sp_t b)
460 quant_udaf_lfta3_struct_t *s = (quant_udaf_lfta3_struct_t *)b;
468 void quant_udaf_lfta3_LFTA_AGGR_OUTPUT_(struct gs_string *r, gs_sp_t b)
470 #ifdef COMPRESSED_XFER
471 quant_udaf_lfta3_struct_t *s = (quant_udaf_lfta3_struct_t *)b;
472 tuple_t tmp[QUANT_LFTA3_SIZE+1];
473 gs_uint32_t ptr=s->usedptr;
476 for (; ptr != 0; ptr=s->t[ptr].next) {
477 tmp[i].val = s->t[ptr].val;
478 tmp[i].gap = s->t[ptr].gap;
479 tmp[i].del = s->t[ptr].del;
482 for (j=1; j <= i; j++) {
483 s->t[j].val = tmp[j-1].val;
484 s->t[j].gap = tmp[j-1].gap;
485 s->t[j].del = tmp[j-1].del;
491 r->length = (5 + 4*(i+1))*sizeof(gs_uint32_t);
493 #ifndef COMPRESSED_XFER
494 r->length = sizeof(quant_udaf_lfta3_struct_t);
499 void quant_udaf_lfta3_LFTA_AGGR_DESTROY_(gs_sp_t b)