-#include <stdio.h>\r
-#include <limits.h>\r
-#include <math.h>\r
-#include "rts_udaf.h"\r
-#include "gsconfig.h"\r
-#include "gstypes.h"\r
-\r
-/* Full size\r
-#define QUANT_LFTA1_SIZE 729\r
-#define QUANT_LFTA2_SIZE 181\r
-#define QUANT_LFTA3_SIZE 100\r
-*/\r
-\r
-/* half size\r
-*/\r
-#define QUANT_LFTA1_SIZE 378\r
-#define QUANT_LFTA2_SIZE 93\r
-#define QUANT_LFTA3_SIZE 50\r
-\r
-/* quarter size\r
-#define QUANT_LFTA1_SIZE 202\r
-#define QUANT_LFTA2_SIZE 49\r
-#define QUANT_LFTA3_SIZE 25\r
-*/\r
-\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
-#define COMPRESSED_XFER\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
-// For skip list\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+1]; // ptrs to levels\r
- skipnode_t list[SKIPDIR_SIZE+1];\r
-} skipdir_t;\r
-\r
-\r
-/****************************************************************/\r
-\r
-// fstring(5+(QUANT_LFTA3_SIZE+1)*4 +\r
-// (2+lg(QUANT_LFTA3_SIZE)+(QUANT_LFTA3_SIZE+1)*3)*4)\r
-typedef struct quant_udaf_lfta3_struct_t {\r
- gs_uint32_t nelts; // # stream elements\r
- gs_uint32_t freeptr; // ptr to cursor stack\r
- gs_uint32_t usedptr; // ptr to allocated memory\r
- gs_uint32_t circptr; // circulating ptr used for compression\r
- gs_uint32_t size;\r
- tuple_t t[QUANT_LFTA3_SIZE+1]; // samples + auxiliary info\r
- skipdir_t sd; // directory for searching tuples\r
-} quant_udaf_lfta3_struct_t;\r
-\r
-/****************************************************************/\r
-/* Skip List Functions */\r
-/****************************************************************/\r
-\r
-// Skip list cursor stack operations\r
-gs_uint32_t skipdir_alloc(skipdir_t *sd)\r
-{\r
- gs_uint32_t ptr = sd->freeptr;\r
- if (sd->freeptr != 0)\r
- sd->freeptr = sd->list[ptr].next;\r
- return ptr;\r
-}\r
-\r
-void skipdir_free(skipdir_t *sd, gs_uint32_t ptr)\r
-{\r
- sd->list[ptr].val = 0;\r
- sd->list[ptr].down = 0;\r
- sd->list[ptr].next = sd->freeptr;\r
- sd->freeptr = ptr;\r
-}\r
-\r
-\r
-void skipdir_create(skipdir_t *sd)\r
-{\r
- gs_int32_t i;\r
-\r
- sd->height = 0;\r
- sd->freeptr = 1;\r
- for (i=0; i < SKIPDIR_HEIGHT_MAX; i++)\r
- sd->headptr[i] = 0;\r
- for (i=1; i < SKIPDIR_SIZE; i++)\r
- sd->list[i].next = i+1;\r
- sd->list[SKIPDIR_SIZE].next = 0;\r
-}\r
-\r
-void skipdir_destroy(skipdir_t *sd)\r
-{\r
- sd->height = 0;\r
-}\r
-\r
-\r
-void skipdir_search(skipdir_t *sd, val_type val, gs_uint32_t *ptrstack)\r
-{\r
- gs_uint32_t ptr;\r
- gs_int32_t l;\r
-\r
- if (sd->height == 0) {\r
- ptrstack[0] = ptrstack[1] = 0;\r
- return;\r
- }\r
- // search nonleaf nodes\r
- ptr = sd->headptr[sd->height-1];\r
- for (l=sd->height-1; l >= 0; l--) {\r
- if (ptr == 0) {\r
- ptrstack[l+1] = 0;\r
- ptr = (l > 0) ? sd->headptr[l-1] : 0;\r
- }\r
- else if (val <= sd->list[ptr].val) {\r
- ptrstack[l+1] = 0;\r
- ptr = (l > 0) ? sd->headptr[l-1] : 0;\r
- }\r
- else {\r
- while ((sd->list[ptr].next != 0) &&\r
- (sd->list[sd->list[ptr].next].val < val))\r
- ptr = sd->list[ptr].next;\r
- ptrstack[l+1] = ptr;\r
- ptr = sd->list[ptr].down;\r
- }\r
- }\r
- ptrstack[0] = ptr;\r
-}\r
-\r
-\r
-void skipdir_insert(skipdir_t *sd, gs_uint32_t *ptrstack,\r
- gs_uint32_t leafptr, val_type val)\r
-{\r
- gs_uint32_t newptr, oldptr;\r
- gs_int32_t l;\r
-\r
- // if path already existed then point to new duplicate\r
- if ((ptrstack[1] == 0) && (sd->headptr[0] != 0)\r
- && (sd->list[sd->headptr[0]].val == val)) {\r
- sd->list[sd->headptr[0]].down = leafptr;\r
- return;\r
- }\r
- if ((ptrstack[1] != 0) && (sd->list[ptrstack[1]].next != 0)\r
- && (sd->list[sd->list[ptrstack[1]].next].val == val)) {\r
- sd->list[sd->list[ptrstack[1]].next].down = leafptr;\r
- return;\r
- }\r
-\r
- for (l=0; l < SKIPDIR_HEIGHT_MAX; l++) {\r
- if (random() % 2) break;\r
- newptr = skipdir_alloc(sd);\r
- if (!newptr) break; // out of memory\r
- sd->list[newptr].val = val;\r
- //copy(&val, &list[newptr[l]].val);\r
- // link new directory node to level below\r
- if (l > 0)\r
- sd->list[newptr].down = oldptr;\r
- else\r
- sd->list[newptr].down = leafptr;\r
- // insert node into current level\r
- if ((l >= sd->height) || (ptrstack[l+1] == 0)) {\r
- sd->list[newptr].next = sd->headptr[l];\r
- sd->headptr[l] = newptr;\r
- }\r
- else {\r
- sd->list[newptr].next = sd->list[ptrstack[l+1]].next;\r
- sd->list[ptrstack[l+1]].next = newptr;\r
- }\r
- oldptr = newptr;\r
- }\r
- if (l > sd->height) sd->height = l;\r
- //fprintf(stderr,"new height = %u\n",sd->height);\r
-}\r
-\r
-\r
-void skipdir_delete(skipdir_t *sd, gs_uint32_t *ptrstack, val_type val)\r
-{\r
- gs_uint32_t delptr;\r
- gs_int32_t l;\r
-\r
- for (l=0; l < sd->height; l++) {\r
- if (ptrstack[l+1] == 0) {\r
- delptr = sd->headptr[l];\r
- if (delptr == 0) break;\r
- if (sd->list[delptr].val == val) {\r
- sd->headptr[l] = sd->list[delptr].next;\r
- skipdir_free(sd, delptr);\r
- }\r
- else\r
- break;\r
- }\r
- else {\r
- delptr = sd->list[ptrstack[l+1]].next;\r
- if (delptr == 0) break;\r
- if (sd->list[delptr].val == val) {\r
- sd->list[ptrstack[l+1]].next = sd->list[delptr].next;\r
- skipdir_free(sd, delptr);\r
- }\r
- else\r
- break;\r
- }\r
- }\r
-}\r
-\r
-// For Debugging\r
-void skipdir_print(skipdir_t *sd)\r
-{\r
- gs_uint32_t ptr;\r
- gs_int32_t l;\r
-\r
- for (l=sd->height-1; l >= 0; l--) {\r
- for (ptr=sd->headptr[l]; ptr != 0; ptr=sd->list[ptr].next)\r
- fprintf(stderr,"%u ", sd->list[ptr].val);\r
- fprintf(stderr,"\n");\r
- }\r
- fprintf(stderr,"-------\n");\r
- for (l=sd->height-1; l > 0; l--) {\r
- for (ptr=sd->headptr[l]; ptr != 0; ptr=sd->list[ptr].next)\r
- fprintf(stderr,"%u ", sd->list[sd->list[ptr].down].val);\r
- fprintf(stderr,"\n");\r
- }\r
- fprintf(stderr,"-------\n");\r
-}\r
-\r
-\r
-\r
-\r
-/*************************** Version 3 **************************/\r
-/* Version 3: LFTA-medium */\r
-/* */\r
-/* NIC performs O(log n) operations at each update. */\r
-/****************************************************************/\r
-\r
-/****************************************************************/\r
-/* Helper functions */\r
-/****************************************************************/\r
-gs_uint32_t quant_udaf_lfta3_cursor_alloc(quant_udaf_lfta3_struct_t *s)\r
-{\r
- gs_uint32_t ptr = s->freeptr;\r
- if (s->freeptr != 0) s->freeptr = s->t[ptr].next;\r
- s->size++;\r
- return ptr;\r
-}\r
-\r
-void quant_udaf_lfta3_cursor_free(quant_udaf_lfta3_struct_t *s, gs_uint32_t ptr)\r
-{\r
- s->t[ptr].next = s->freeptr;\r
- s->freeptr = ptr;\r
- s->size--;\r
-}\r
-\r
-void quant_lfta3_print(quant_udaf_lfta3_struct_t *s)\r
-{\r
- tuple_t *t=s->t;\r
- gs_uint32_t ptr = s->usedptr;\r
-\r
- if (ptr == 0) {\r
- fprintf(stderr,"<empty>\n");\r
- return;\r
- }\r
- //skipdir_print(&s->sd);\r
- for (; ptr != 0; ptr=t[ptr].next) {\r
- fprintf(stderr,"(%u, %u, %u) ",t[ptr].val,t[ptr].gap,t[ptr].del);\r
- }\r
- fprintf(stderr,"\n");\r
-}\r
-\r
-void quant_lfta3_compress(quant_udaf_lfta3_struct_t *s)\r
-{\r
- tuple_t *t = s->t;\r
- gs_uint32_t delptr;\r
- gs_uint32_t threshold;\r
- gs_uint32_t ptrstack[SKIPDIR_HEIGHT_MAX+5];\r
-\r
- threshold = (gs_uint32_t)ceil(2.0 * QUANT_EPS * (gs_float_t)s->nelts);\r
-//if(s->circptr < 0 || s->circptr >= QUANT_LFTA3_SIZE)\r
-// printf("1) s->circptr = %d\n",s->circptr);\r
-//if(t[s->circptr].next < 0 || t[s->circptr].next >= QUANT_LFTA3_SIZE)\r
-// printf("t[s->circptr].next = %d\n",t[s->circptr].next);\r
- if ((s->circptr == 0) || (t[s->circptr].next == 0)\r
- || (t[t[s->circptr].next].next == 0))\r
- s->circptr = s->usedptr;\r
- //if ((s->size % 10) != 0) return;\r
- if (s->nelts > 2) {\r
-//if(s->circptr < 0 || s->circptr >= QUANT_LFTA3_SIZE)\r
-// printf("2) s->circptr = %d\n",s->circptr);\r
- delptr = t[s->circptr].next;\r
-//if(delptr < 0 || delptr >= QUANT_LFTA3_SIZE)\r
-// printf("delptr = %d\n",delptr);\r
-//if(t[delptr].next < 0 || t[delptr].next >= QUANT_LFTA3_SIZE)\r
-// printf("t[delptr].next = %d\n",t[delptr].next);\r
- if (t[delptr].gap+t[t[delptr].next].gap+t[t[delptr].next].del < threshold) {\r
- // delete from directory\r
- if (t[s->circptr].val != t[delptr].val) {\r
- // leftmost duplicate (if multiplicity)\r
- skipdir_search(&(s->sd), t[delptr].val, ptrstack);\r
- if (t[delptr].val == t[t[delptr].next].val) {\r
-//if(s->sd.headptr[0] < 0 || s->sd.headptr[0] >= QUANT_LFTA3_SIZE)\r
-// printf("s->sd.headptr[0] = %d\n",s->sd.headptr[0]);\r
- // duplicates case\r
- if ((ptrstack[1] == 0)\r
- && (s->sd.headptr[0] != 0)\r
- && (s->sd.list[s->sd.headptr[0]].val == t[delptr].val))\r
- s->sd.list[s->sd.headptr[0]].down = t[delptr].next;\r
- else if ((ptrstack[1] != 0)\r
- && (s->sd.list[ptrstack[1]].next != 0)\r
- && (s->sd.list[s->sd.list[ptrstack[1]].next].val == t[delptr].val))\r
- s->sd.list[s->sd.list[ptrstack[1]].next].down = t[delptr].next;\r
- }\r
- else {\r
- // non-duplicates case\r
- skipdir_delete(&(s->sd), ptrstack, t[delptr].val);\r
- }\r
- }\r
- // delete from list\r
- //fprintf(stderr,"DELETED %u\n", t[delptr].val);\r
- t[s->circptr].next = t[delptr].next;\r
- quant_udaf_lfta3_cursor_free(s, delptr);\r
- }\r
- else {\r
- s->circptr = t[s->circptr].next;\r
- }\r
- }\r
-}\r
-\r
-\r
-/****************************************************************/\r
-/* LFTA3 functions */\r
-/****************************************************************/\r
-void quant_udaf_lfta3_LFTA_AGGR_INIT_(gs_sp_t b)\r
-{\r
- gs_uint32_t i;\r
-\r
- quant_udaf_lfta3_struct_t *s = (quant_udaf_lfta3_struct_t *)b;\r
- s->nelts = 0;\r
- s->usedptr = 0; // NULL ptr\r
- s->circptr = 0;\r
- // initialize cursor stack\r
- s->freeptr = 1;\r
- s->size = 0;\r
- for (i=1; i < QUANT_LFTA3_SIZE; i++)\r
- s->t[i].next = i+1;\r
- s->t[QUANT_LFTA3_SIZE].next = 0;\r
- skipdir_create(&(s->sd));\r
-}\r
-\r
-void quant_udaf_lfta3_LFTA_AGGR_UPDATE_(gs_sp_t b, gs_uint32_t v)\r
-{\r
- quant_udaf_lfta3_struct_t *s = (quant_udaf_lfta3_struct_t *)b;\r
- tuple_t *t = s->t;\r
- gs_uint32_t ptr = s->usedptr;\r
- gs_uint32_t newptr, delptr;\r
- gs_uint32_t obj; // objective function\r
- gs_uint32_t threshold;\r
- gs_uint32_t ptrstack[SKIPDIR_HEIGHT_MAX+5];\r
- gs_uint32_t debugptr;\r
-\r
-//printf("AGGR_UPDATE start\n");\r
- s->nelts++;\r
- //fprintf(stderr,"nelts = %u\n",s->nelts);\r
- // left boundary case\r
- if ((ptr == 0) || (v < t[ptr].val)) {\r
- if (t[ptr].val == v) {\r
- t[ptr].gap++;\r
-//printf("AGGR_UPDATE END 1\n");\r
- return;\r
- }\r
- newptr = quant_udaf_lfta3_cursor_alloc(s);\r
- if (newptr == 0) {\r
- gslog(LOG_ALERT, "Out of space.\n");\r
- return;\r
- }\r
- t[newptr].val = v;\r
- t[newptr].gap = 1;\r
- t[newptr].del = 0;\r
- t[newptr].next = s->usedptr;\r
- s->usedptr = newptr;\r
-//printf("AGGR_UPDATE END 2\n");\r
- return;\r
- }\r
-\r
- // locate $i$ such that (v_i-1 < v <= v_i)\r
- skipdir_search(&(s->sd), v, ptrstack);\r
-\r
- //ptr = (ptrstack[0] == 0) ? s->usedptr : s->sd.list[ptrstack[0]].down;\r
- ptr = (ptrstack[0] == 0) ? s->usedptr : ptrstack[0];\r
- while ((t[ptr].next != 0) && (t[t[ptr].next].val < v))\r
- ptr = t[ptr].next;\r
-\r
-/*\r
- // duplicate value\r
- if ((t[ptr].next != 0) && (t[t[ptr].next].val == v)) {\r
- t[t[ptr].next].gap++;\r
-printf("AGGR_UPDATE END 3\n");\r
- return;\r
- }\r
-*/\r
-\r
- // right boundary case\r
- if (t[ptr].next == 0) {\r
- newptr = quant_udaf_lfta3_cursor_alloc(s);\r
- if (newptr == 0) {\r
- gslog(LOG_ALERT, "Out of space.\n");\r
- return;\r
- }\r
- t[newptr].val = v;\r
- t[newptr].gap = 1;\r
- t[newptr].del = 0;\r
- t[newptr].next = 0;\r
- t[ptr].next = newptr;\r
-//printf("AGGR_UPDATE END 4\n");\r
- return;\r
- }\r
-\r
- // non-boundary case\r
-//printf("1) t[ptr].next =%d, ptr=%d\n",t[ptr].next,ptr);\r
- obj = t[ptr].gap+t[t[ptr].next].gap+t[t[ptr].next].del;\r
- threshold = (gs_uint32_t)ceil(2.0 * QUANT_EPS * (gs_float_t)s->nelts);\r
- if (obj > threshold) {\r
- newptr = quant_udaf_lfta3_cursor_alloc(s);\r
- if (newptr == 0) {\r
- gslog(LOG_ALERT, "Out of memory.\n");\r
- return;\r
- }\r
-//printf("newptr=%d\n",newptr);\r
- t[newptr].val = v;\r
- t[newptr].gap = 1;\r
- t[newptr].del = t[t[ptr].next].gap+t[t[ptr].next].del - 1;\r
- t[newptr].next = t[ptr].next;\r
- t[ptr].next = newptr;\r
- skipdir_insert(&(s->sd), ptrstack, newptr, v);\r
- }\r
- else {\r
- // insert into existing bucket\r
-//printf("t[ptr].next =%d\n",t[ptr].next);\r
- t[t[ptr].next].gap++;\r
- }\r
- quant_lfta3_compress(s);\r
-//printf("AGGR_UPDATE END 5\n");\r
-}\r
-\r
-gs_int32_t quant_udaf_lfta3_LFTA_AGGR_FLUSHME_(gs_sp_t b)\r
-{\r
- quant_udaf_lfta3_struct_t *s = (quant_udaf_lfta3_struct_t *)b;\r
-\r
- if (s->freeptr == 0)\r
- return 1;\r
- else\r
- return 0;\r
-}\r
-\r
-void quant_udaf_lfta3_LFTA_AGGR_OUTPUT_(struct gs_string *r, gs_sp_t b)\r
-{\r
-#ifdef COMPRESSED_XFER\r
- quant_udaf_lfta3_struct_t *s = (quant_udaf_lfta3_struct_t *)b;\r
- tuple_t tmp[QUANT_LFTA3_SIZE+1];\r
- gs_uint32_t ptr=s->usedptr;\r
- gs_int32_t i=0,j;\r
-\r
- for (; ptr != 0; ptr=s->t[ptr].next) {\r
- tmp[i].val = s->t[ptr].val;\r
- tmp[i].gap = s->t[ptr].gap;\r
- tmp[i].del = s->t[ptr].del;\r
- i++;\r
- }\r
- for (j=1; j <= i; j++) {\r
- s->t[j].val = tmp[j-1].val;\r
- s->t[j].gap = tmp[j-1].gap;\r
- s->t[j].del = tmp[j-1].del;\r
- s->t[j].next = j+1;\r
- }\r
- s->t[i].next = 0;\r
- s->usedptr = 1;\r
-\r
- r->length = (5 + 4*(i+1))*sizeof(gs_uint32_t);\r
-#endif\r
-#ifndef COMPRESSED_XFER\r
- r->length = sizeof(quant_udaf_lfta3_struct_t);\r
-#endif\r
- r->data = b;\r
-}\r
-\r
-void quant_udaf_lfta3_LFTA_AGGR_DESTROY_(gs_sp_t b)\r
-{\r
- return;\r
-}\r
+#include <stdio.h>
+#include <limits.h>
+#include <math.h>
+#include "rts_udaf.h"
+#include "gsconfig.h"
+#include "gstypes.h"
+
+/* Full size
+#define QUANT_LFTA1_SIZE 729
+#define QUANT_LFTA2_SIZE 181
+#define QUANT_LFTA3_SIZE 100
+*/
+
+/* half size
+*/
+#define QUANT_LFTA1_SIZE 378
+#define QUANT_LFTA2_SIZE 93
+#define QUANT_LFTA3_SIZE 50
+
+/* quarter size
+#define QUANT_LFTA1_SIZE 202
+#define QUANT_LFTA2_SIZE 49
+#define QUANT_LFTA3_SIZE 25
+*/
+
+
+#define QUANT_EPS 0.01
+#define SKIPDIR_SIZE 100
+#define SKIPDIR_HEIGHT_MAX 7
+#define max(a,b) ((a) > (b) ? (a) : (b))
+#define COMPRESSED_XFER
+
+/****************************************************************/
+/* Data Structures */
+/****************************************************************/
+typedef struct tuple_t {
+ gs_uint32_t val;
+ gs_uint32_t gap;
+ gs_uint32_t del;
+ gs_uint32_t next;
+} tuple_t;
+
+// For skip list
+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+1]; // ptrs to levels
+ skipnode_t list[SKIPDIR_SIZE+1];
+} skipdir_t;
+
+
+/****************************************************************/
+
+// fstring(5+(QUANT_LFTA3_SIZE+1)*4 +
+// (2+lg(QUANT_LFTA3_SIZE)+(QUANT_LFTA3_SIZE+1)*3)*4)
+typedef struct quant_udaf_lfta3_struct_t {
+ gs_uint32_t nelts; // # stream elements
+ gs_uint32_t freeptr; // ptr to cursor stack
+ gs_uint32_t usedptr; // ptr to allocated memory
+ gs_uint32_t circptr; // circulating ptr used for compression
+ gs_uint32_t size;
+ tuple_t t[QUANT_LFTA3_SIZE+1]; // samples + auxiliary info
+ skipdir_t sd; // directory for searching tuples
+} quant_udaf_lfta3_struct_t;
+
+/****************************************************************/
+/* Skip List Functions */
+/****************************************************************/
+
+// Skip list cursor stack operations
+gs_uint32_t skipdir_alloc(skipdir_t *sd)
+{
+ gs_uint32_t ptr = sd->freeptr;
+ if (sd->freeptr != 0)
+ sd->freeptr = sd->list[ptr].next;
+ return ptr;
+}
+
+void skipdir_free(skipdir_t *sd, gs_uint32_t ptr)
+{
+ sd->list[ptr].val = 0;
+ sd->list[ptr].down = 0;
+ sd->list[ptr].next = sd->freeptr;
+ sd->freeptr = ptr;
+}
+
+
+void skipdir_create(skipdir_t *sd)
+{
+ gs_int32_t i;
+
+ sd->height = 0;
+ sd->freeptr = 1;
+ for (i=0; i < SKIPDIR_HEIGHT_MAX; i++)
+ sd->headptr[i] = 0;
+ for (i=1; i < SKIPDIR_SIZE; i++)
+ sd->list[i].next = i+1;
+ sd->list[SKIPDIR_SIZE].next = 0;
+}
+
+void skipdir_destroy(skipdir_t *sd)
+{
+ sd->height = 0;
+}
+
+
+void skipdir_search(skipdir_t *sd, val_type val, gs_uint32_t *ptrstack)
+{
+ gs_uint32_t ptr;
+ gs_int32_t l;
+
+ if (sd->height == 0) {
+ ptrstack[0] = ptrstack[1] = 0;
+ return;
+ }
+ // search nonleaf nodes
+ ptr = sd->headptr[sd->height-1];
+ for (l=sd->height-1; l >= 0; l--) {
+ if (ptr == 0) {
+ ptrstack[l+1] = 0;
+ ptr = (l > 0) ? sd->headptr[l-1] : 0;
+ }
+ else if (val <= sd->list[ptr].val) {
+ ptrstack[l+1] = 0;
+ ptr = (l > 0) ? sd->headptr[l-1] : 0;
+ }
+ else {
+ while ((sd->list[ptr].next != 0) &&
+ (sd->list[sd->list[ptr].next].val < val))
+ ptr = sd->list[ptr].next;
+ ptrstack[l+1] = ptr;
+ ptr = sd->list[ptr].down;
+ }
+ }
+ ptrstack[0] = ptr;
+}
+
+
+void skipdir_insert(skipdir_t *sd, gs_uint32_t *ptrstack,
+ gs_uint32_t leafptr, val_type val)
+{
+ gs_uint32_t newptr, oldptr;
+ gs_int32_t l;
+
+ // if path already existed then point to new duplicate
+ if ((ptrstack[1] == 0) && (sd->headptr[0] != 0)
+ && (sd->list[sd->headptr[0]].val == val)) {
+ sd->list[sd->headptr[0]].down = leafptr;
+ return;
+ }
+ if ((ptrstack[1] != 0) && (sd->list[ptrstack[1]].next != 0)
+ && (sd->list[sd->list[ptrstack[1]].next].val == val)) {
+ sd->list[sd->list[ptrstack[1]].next].down = leafptr;
+ return;
+ }
+
+ for (l=0; l < SKIPDIR_HEIGHT_MAX; l++) {
+ if (random() % 2) break;
+ newptr = skipdir_alloc(sd);
+ if (!newptr) break; // out of memory
+ sd->list[newptr].val = val;
+ //copy(&val, &list[newptr[l]].val);
+ // link new directory node to level below
+ if (l > 0)
+ sd->list[newptr].down = oldptr;
+ else
+ sd->list[newptr].down = leafptr;
+ // insert node into current level
+ if ((l >= sd->height) || (ptrstack[l+1] == 0)) {
+ sd->list[newptr].next = sd->headptr[l];
+ sd->headptr[l] = newptr;
+ }
+ else {
+ sd->list[newptr].next = sd->list[ptrstack[l+1]].next;
+ sd->list[ptrstack[l+1]].next = newptr;
+ }
+ oldptr = newptr;
+ }
+ if (l > sd->height) sd->height = l;
+ //fprintf(stderr,"new height = %u\n",sd->height);
+}
+
+
+void skipdir_delete(skipdir_t *sd, gs_uint32_t *ptrstack, val_type val)
+{
+ gs_uint32_t delptr;
+ gs_int32_t l;
+
+ for (l=0; l < sd->height; l++) {
+ if (ptrstack[l+1] == 0) {
+ delptr = sd->headptr[l];
+ if (delptr == 0) break;
+ if (sd->list[delptr].val == val) {
+ sd->headptr[l] = sd->list[delptr].next;
+ skipdir_free(sd, delptr);
+ }
+ else
+ break;
+ }
+ else {
+ delptr = sd->list[ptrstack[l+1]].next;
+ if (delptr == 0) break;
+ if (sd->list[delptr].val == val) {
+ sd->list[ptrstack[l+1]].next = sd->list[delptr].next;
+ skipdir_free(sd, delptr);
+ }
+ else
+ break;
+ }
+ }
+}
+
+// For Debugging
+void skipdir_print(skipdir_t *sd)
+{
+ gs_uint32_t ptr;
+ gs_int32_t l;
+
+ for (l=sd->height-1; l >= 0; l--) {
+ for (ptr=sd->headptr[l]; ptr != 0; ptr=sd->list[ptr].next)
+ fprintf(stderr,"%u ", sd->list[ptr].val);
+ fprintf(stderr,"\n");
+ }
+ fprintf(stderr,"-------\n");
+ for (l=sd->height-1; l > 0; l--) {
+ for (ptr=sd->headptr[l]; ptr != 0; ptr=sd->list[ptr].next)
+ fprintf(stderr,"%u ", sd->list[sd->list[ptr].down].val);
+ fprintf(stderr,"\n");
+ }
+ fprintf(stderr,"-------\n");
+}
+
+
+
+
+/*************************** Version 3 **************************/
+/* Version 3: LFTA-medium */
+/* */
+/* NIC performs O(log n) operations at each update. */
+/****************************************************************/
+
+/****************************************************************/
+/* Helper functions */
+/****************************************************************/
+gs_uint32_t quant_udaf_lfta3_cursor_alloc(quant_udaf_lfta3_struct_t *s)
+{
+ gs_uint32_t ptr = s->freeptr;
+ if (s->freeptr != 0) s->freeptr = s->t[ptr].next;
+ s->size++;
+ return ptr;
+}
+
+void quant_udaf_lfta3_cursor_free(quant_udaf_lfta3_struct_t *s, gs_uint32_t ptr)
+{
+ s->t[ptr].next = s->freeptr;
+ s->freeptr = ptr;
+ s->size--;
+}
+
+void quant_lfta3_print(quant_udaf_lfta3_struct_t *s)
+{
+ tuple_t *t=s->t;
+ gs_uint32_t ptr = s->usedptr;
+
+ if (ptr == 0) {
+ fprintf(stderr,"<empty>\n");
+ return;
+ }
+ //skipdir_print(&s->sd);
+ for (; ptr != 0; ptr=t[ptr].next) {
+ fprintf(stderr,"(%u, %u, %u) ",t[ptr].val,t[ptr].gap,t[ptr].del);
+ }
+ fprintf(stderr,"\n");
+}
+
+void quant_lfta3_compress(quant_udaf_lfta3_struct_t *s)
+{
+ tuple_t *t = s->t;
+ gs_uint32_t delptr;
+ gs_uint32_t threshold;
+ gs_uint32_t ptrstack[SKIPDIR_HEIGHT_MAX+5];
+
+ threshold = (gs_uint32_t)ceil(2.0 * QUANT_EPS * (gs_float_t)s->nelts);
+//if(s->circptr < 0 || s->circptr >= QUANT_LFTA3_SIZE)
+// printf("1) s->circptr = %d\n",s->circptr);
+//if(t[s->circptr].next < 0 || t[s->circptr].next >= QUANT_LFTA3_SIZE)
+// printf("t[s->circptr].next = %d\n",t[s->circptr].next);
+ if ((s->circptr == 0) || (t[s->circptr].next == 0)
+ || (t[t[s->circptr].next].next == 0))
+ s->circptr = s->usedptr;
+ //if ((s->size % 10) != 0) return;
+ if (s->nelts > 2) {
+//if(s->circptr < 0 || s->circptr >= QUANT_LFTA3_SIZE)
+// printf("2) s->circptr = %d\n",s->circptr);
+ delptr = t[s->circptr].next;
+//if(delptr < 0 || delptr >= QUANT_LFTA3_SIZE)
+// printf("delptr = %d\n",delptr);
+//if(t[delptr].next < 0 || t[delptr].next >= QUANT_LFTA3_SIZE)
+// printf("t[delptr].next = %d\n",t[delptr].next);
+ if (t[delptr].gap+t[t[delptr].next].gap+t[t[delptr].next].del < threshold) {
+ // delete from directory
+ if (t[s->circptr].val != t[delptr].val) {
+ // leftmost duplicate (if multiplicity)
+ skipdir_search(&(s->sd), t[delptr].val, ptrstack);
+ if (t[delptr].val == t[t[delptr].next].val) {
+//if(s->sd.headptr[0] < 0 || s->sd.headptr[0] >= QUANT_LFTA3_SIZE)
+// printf("s->sd.headptr[0] = %d\n",s->sd.headptr[0]);
+ // duplicates case
+ if ((ptrstack[1] == 0)
+ && (s->sd.headptr[0] != 0)
+ && (s->sd.list[s->sd.headptr[0]].val == t[delptr].val))
+ s->sd.list[s->sd.headptr[0]].down = t[delptr].next;
+ else if ((ptrstack[1] != 0)
+ && (s->sd.list[ptrstack[1]].next != 0)
+ && (s->sd.list[s->sd.list[ptrstack[1]].next].val == t[delptr].val))
+ s->sd.list[s->sd.list[ptrstack[1]].next].down = t[delptr].next;
+ }
+ else {
+ // non-duplicates case
+ skipdir_delete(&(s->sd), ptrstack, t[delptr].val);
+ }
+ }
+ // delete from list
+ //fprintf(stderr,"DELETED %u\n", t[delptr].val);
+ t[s->circptr].next = t[delptr].next;
+ quant_udaf_lfta3_cursor_free(s, delptr);
+ }
+ else {
+ s->circptr = t[s->circptr].next;
+ }
+ }
+}
+
+
+/****************************************************************/
+/* LFTA3 functions */
+/****************************************************************/
+void quant_udaf_lfta3_LFTA_AGGR_INIT_(gs_sp_t b)
+{
+ gs_uint32_t i;
+
+ quant_udaf_lfta3_struct_t *s = (quant_udaf_lfta3_struct_t *)b;
+ s->nelts = 0;
+ s->usedptr = 0; // NULL ptr
+ s->circptr = 0;
+ // initialize cursor stack
+ s->freeptr = 1;
+ s->size = 0;
+ for (i=1; i < QUANT_LFTA3_SIZE; i++)
+ s->t[i].next = i+1;
+ s->t[QUANT_LFTA3_SIZE].next = 0;
+ skipdir_create(&(s->sd));
+}
+
+void quant_udaf_lfta3_LFTA_AGGR_UPDATE_(gs_sp_t b, gs_uint32_t v)
+{
+ quant_udaf_lfta3_struct_t *s = (quant_udaf_lfta3_struct_t *)b;
+ tuple_t *t = s->t;
+ gs_uint32_t ptr = s->usedptr;
+ gs_uint32_t newptr, delptr;
+ gs_uint32_t obj; // objective function
+ gs_uint32_t threshold;
+ gs_uint32_t ptrstack[SKIPDIR_HEIGHT_MAX+5];
+ gs_uint32_t debugptr;
+
+//printf("AGGR_UPDATE start\n");
+ s->nelts++;
+ //fprintf(stderr,"nelts = %u\n",s->nelts);
+ // left boundary case
+ if ((ptr == 0) || (v < t[ptr].val)) {
+ if (t[ptr].val == v) {
+ t[ptr].gap++;
+//printf("AGGR_UPDATE END 1\n");
+ return;
+ }
+ newptr = quant_udaf_lfta3_cursor_alloc(s);
+ if (newptr == 0) {
+ gslog(LOG_ALERT, "Out of space.\n");
+ return;
+ }
+ t[newptr].val = v;
+ t[newptr].gap = 1;
+ t[newptr].del = 0;
+ t[newptr].next = s->usedptr;
+ s->usedptr = newptr;
+//printf("AGGR_UPDATE END 2\n");
+ return;
+ }
+
+ // locate $i$ such that (v_i-1 < v <= v_i)
+ skipdir_search(&(s->sd), v, ptrstack);
+
+ //ptr = (ptrstack[0] == 0) ? s->usedptr : s->sd.list[ptrstack[0]].down;
+ ptr = (ptrstack[0] == 0) ? s->usedptr : ptrstack[0];
+ while ((t[ptr].next != 0) && (t[t[ptr].next].val < v))
+ ptr = t[ptr].next;
+
+/*
+ // duplicate value
+ if ((t[ptr].next != 0) && (t[t[ptr].next].val == v)) {
+ t[t[ptr].next].gap++;
+printf("AGGR_UPDATE END 3\n");
+ return;
+ }
+*/
+
+ // right boundary case
+ if (t[ptr].next == 0) {
+ newptr = quant_udaf_lfta3_cursor_alloc(s);
+ if (newptr == 0) {
+ gslog(LOG_ALERT, "Out of space.\n");
+ return;
+ }
+ t[newptr].val = v;
+ t[newptr].gap = 1;
+ t[newptr].del = 0;
+ t[newptr].next = 0;
+ t[ptr].next = newptr;
+//printf("AGGR_UPDATE END 4\n");
+ return;
+ }
+
+ // non-boundary case
+//printf("1) t[ptr].next =%d, ptr=%d\n",t[ptr].next,ptr);
+ obj = t[ptr].gap+t[t[ptr].next].gap+t[t[ptr].next].del;
+ threshold = (gs_uint32_t)ceil(2.0 * QUANT_EPS * (gs_float_t)s->nelts);
+ if (obj > threshold) {
+ newptr = quant_udaf_lfta3_cursor_alloc(s);
+ if (newptr == 0) {
+ gslog(LOG_ALERT, "Out of memory.\n");
+ return;
+ }
+//printf("newptr=%d\n",newptr);
+ t[newptr].val = v;
+ t[newptr].gap = 1;
+ t[newptr].del = t[t[ptr].next].gap+t[t[ptr].next].del - 1;
+ t[newptr].next = t[ptr].next;
+ t[ptr].next = newptr;
+ skipdir_insert(&(s->sd), ptrstack, newptr, v);
+ }
+ else {
+ // insert into existing bucket
+//printf("t[ptr].next =%d\n",t[ptr].next);
+ t[t[ptr].next].gap++;
+ }
+ quant_lfta3_compress(s);
+//printf("AGGR_UPDATE END 5\n");
+}
+
+gs_int32_t quant_udaf_lfta3_LFTA_AGGR_FLUSHME_(gs_sp_t b)
+{
+ quant_udaf_lfta3_struct_t *s = (quant_udaf_lfta3_struct_t *)b;
+
+ if (s->freeptr == 0)
+ return 1;
+ else
+ return 0;
+}
+
+void quant_udaf_lfta3_LFTA_AGGR_OUTPUT_(struct gs_string *r, gs_sp_t b)
+{
+#ifdef COMPRESSED_XFER
+ quant_udaf_lfta3_struct_t *s = (quant_udaf_lfta3_struct_t *)b;
+ tuple_t tmp[QUANT_LFTA3_SIZE+1];
+ gs_uint32_t ptr=s->usedptr;
+ gs_int32_t i=0,j;
+
+ for (; ptr != 0; ptr=s->t[ptr].next) {
+ tmp[i].val = s->t[ptr].val;
+ tmp[i].gap = s->t[ptr].gap;
+ tmp[i].del = s->t[ptr].del;
+ i++;
+ }
+ for (j=1; j <= i; j++) {
+ s->t[j].val = tmp[j-1].val;
+ s->t[j].gap = tmp[j-1].gap;
+ s->t[j].del = tmp[j-1].del;
+ s->t[j].next = j+1;
+ }
+ s->t[i].next = 0;
+ s->usedptr = 1;
+
+ r->length = (5 + 4*(i+1))*sizeof(gs_uint32_t);
+#endif
+#ifndef COMPRESSED_XFER
+ r->length = sizeof(quant_udaf_lfta3_struct_t);
+#endif
+ r->data = b;
+}
+
+void quant_udaf_lfta3_LFTA_AGGR_DESTROY_(gs_sp_t b)
+{
+ return;
+}
Code Review / com / gs-lite.git / blobdiff