dht implementation first round tests pass

diff --git a/src/testston.c b/src/testston.c
index 32910b0..014a58c 100644 (file)
--- a/src/testston.c
+++ b/src/testston.c
@@ -36,9 +36,10 @@ int main(int argc, char* argv[])
   size_t    i;
   size_t    elements;
   uint16_t  columns;
+  int       fail;
 
   printf("up2pow [5] = [%i]\n",ston_up2pow(5));
-  for (i = 0; i < 255; i += 7)
+  for (i = 0; i < 77; i += 7)
     printf("trailing0 [%X] = [%x]\n",(uint32_t)i,ston_trailing0(i));
 
   columns = 2;
@@ -69,41 +70,184 @@ int main(int argc, char* argv[])
   elements = 20;
   ht = ston_ht32_new(columns,elements,0,malloc);
   check_ht(ht);
-  printf("Filling hashtable with entries\n");
+  printf("Filling hashtable with %i entries\n", (int)elements);
   for(key = 0xCEED; elements--; key *= 7)
     { val[0] = key;
       for(i = 1; i < columns; i++)
        val[i] = i * key;
       ston_ht32_insertx(ht,key,val,0,columns);
     }
-  printf("Reading entries\n");
   elements = 20;
+  printf("Reading entries: ");
+  fail = 0;
   for(key = 0xCEED; elements--; key *= 7)
     { htval = ston_ht32_row(ht,key);
-      printf("[%s%x"CLRC"]",(*htval == key) ? GREEN : RED,*htval);
+      if (*htval != key)
+       fail++;
       for(i = 1; i < columns; i++)
-       printf("[%s%x"CLRC"]",(htval[i] == (uint32_t)(i * key)) ? GREEN : RED,htval[i]);
-      putchar('\n');
+       if (htval[i] != (uint32_t)(i * key))
+         fail++;
     }
+  if (fail)
+    printf(RED"FAIL"CLRC"(%i)\n", fail);
+  else
+    printf(GREEN"PASS"CLRCN);
   int max_capacity = ston_up2pow(20 << 1) - 20;
-  printf("Overfilling hashtable with %i entries\n", max_capacity);
   int cap = max_capacity;
+  printf("Overfilling hashtable with %i entries\n", max_capacity);
   for(key = 0xCEED2; cap--; key *= 13)
     { val[0] = key;
       for(i = 1; i < columns; i++)
        val[i] = key * -i;
       ston_ht32_insertx(ht,key,val,0,columns);
     }
-  printf("Reading entries\n");
+  printf("Reading entries: ");
   cap = max_capacity;
+  fail = 0;
   for(key = 0xCEED2; cap--; key *= 13)
     { htval = ston_ht32_row(ht,key);
-      printf("[%s%x"CLRC"]",(*htval == key) ? GREEN : RED,*htval);
+      if (*htval != key)
+       fail++;
+      for(i = 1; i < columns; i++)
+       if (htval[i] != (uint32_t)(key * -i))
+         fail++;
+    }
+  if (fail)
+    printf(RED"FAIL"CLRC"(%i)\n", fail);
+  else
+    printf(GREEN"PASS"CLRCN);
+
+  cap = 20;
+  printf("Post-capacity insertion of %i\n",cap);
+  for (key = 0xCEED3; cap--; key *= 23)
+    { val[0] = key;
+      for(i = 1; i < columns; i++)
+       val[i] = key * -i;
+      size_t count = ston_ht32_insertx(ht,key,val,0,columns);
+      printf("Insertion %2i wrote %i bytes: %s"CLRCN, (int)cap, (int) count,
+            (count == 0) ? GREEN"PASS" : RED"FAIL");
+    }
+  
+
+  printf("Refilling hashtable with %i entries\n", max_capacity);
+  cap = max_capacity;
+  for(key = 0xCEED2; cap--; key *= 13)
+    { val[0] = key;
       for(i = 1; i < columns; i++)
-       printf("[%s%x"CLRC"]",(htval[i] == (uint32_t)(key * -i)) ? GREEN : RED,htval[i]);
-      printf("\n");
+       val[i] = key * i;
+      ston_ht32_insertx(ht,key,val,0,columns);
     }
+  printf("Reading entries: ");
+  cap = max_capacity;
+  fail = 0;
+  for(key = 0xCEED2; cap--; key *= 13)
+    { htval = ston_ht32_row(ht,key);
+      if (*htval != key)
+       fail ++;
+      for (i = 1; i < columns; i++)
+       if (htval[i] != (uint32_t)(key * i))
+         fail++;
+    }
+  if (fail)
+    printf(RED"FAIL"CLRC"(%i)\n", fail);
+  else
+    printf(GREEN"PASS"CLRCN);
 
   free(ht);
+
+
+  printf("\n--------- DHT ----------\n\n");
+
+  ston_dht dht;
+  elements = 50;
+  columns = 6;
+  dht = ston_dht32_new(columns, elements, 0, malloc, free);
+  check_ht(dht);
+  elements = 50000;
+  printf("Filling Dynamic hashtable with %i entries\n", (int)elements);
+  for(key = 0xCEED; elements--; key *= 7)
+    { val[0] = key;
+      for(i = 1; i < columns; i++)
+       val[i] = i * key;
+      ston_dht32_insertx(dht,key,val,0,columns);
+    }
+  elements = 50000;
+  printf("Reading entries: ");
+  fail = 0;
+  for(key = 0xCEED; elements--; key *= 7)
+    { htval = ston_dht32_row(dht,key);
+      if (*htval != key)
+       fail++;
+      for(i = 1; i < columns; i++)
+       if (htval[i] != (uint32_t)(i * key))
+         fail++;
+    }
+  if (fail)
+    printf(RED"FAIL"CLRC"(%i)\n", fail);
+  else
+    printf(GREEN"PASS"CLRCN);
+  max_capacity = (ston_up2pow(50 << 1) * (ston_dht_pagemax(dht) - ston_dht_pagestart(dht))) - 50000;
+  cap = max_capacity;
+  printf("Overfilling hashtable with %i entries\n", max_capacity);
+  for(key = 0xCEED2; cap--; key *= 13)
+    { val[0] = key;
+      for(i = 1; i < columns; i++)
+       val[i] = key * -i;
+      ston_dht32_insertx(dht,key,val,0,columns);
+    }
+  printf("Reading entries: ");
+  cap = max_capacity;
+  fail = 0;
+  for(key = 0xCEED2; cap--; key *= 13)
+    { htval = ston_dht32_row(dht,key);
+      if (*htval != key)
+       fail++;
+      for(i = 1; i < columns; i++)
+       if (htval[i] != (uint32_t)(key * -i))
+         fail++;
+    }
+  if (fail)
+    printf(RED"FAIL"CLRC"(%i)\n", fail);
+  else
+    printf(GREEN"PASS"CLRCN);
+
+  cap = 20;
+  printf("Post-capacity insertion of %i\n",cap);
+  for (key = 0xCEED3; cap--; key *= 23)
+    { val[0] = key;
+      for(i = 1; i < columns; i++)
+       val[i] = key * -i;
+      size_t count = ston_dht32_insertx(dht,key,val,0,columns);
+      printf("Insertion %2i wrote %i bytes: %s"CLRCN, (int)cap, (int) count,
+            (count == 0) ? GREEN"PASS" : RED"FAIL");
+    }
+  
+
+  printf("Refilling hashtable with %i entries\n", max_capacity);
+  cap = max_capacity;
+  for(key = 0xCEED2; cap--; key *= 13)
+    { val[0] = key;
+      for(i = 1; i < columns; i++)
+       val[i] = key * i;
+      ston_dht32_insertx(dht,key,val,0,columns);
+    }
+  printf("Reading entries: ");
+  cap = max_capacity;
+  fail = 0;
+  for(key = 0xCEED2; cap--; key *= 13)
+    { htval = ston_dht32_row(dht,key);
+      if (*htval != key)
+       fail ++;
+      for (i = 1; i < columns; i++)
+       if (htval[i] != (uint32_t)(key * i))
+         fail++;
+    }
+  if (fail)
+    printf(RED"FAIL"CLRC"(%i)\n", fail);
+  else
+    printf(GREEN"PASS"CLRCN);
+
+  ston_dht32_free(dht);
+  
   return 0;
 }

diff --git a/ston/ston_ht.h b/ston/ston_ht.h
index b17e18e..fb5d566 100644 (file)
--- a/ston/ston_ht.h
+++ b/ston/ston_ht.h
@@ -63,7 +63,7 @@ ston_ht   ston_ht32_fread(FILE*,long,void*(*)(size_t));
 typedef struct ston_ht_header_t
 { uint16_t ht_columns;
   uint8_t  ht_2pow, ht_flags;
-}* ston_ht;
+}ston_ht_h,* ston_ht;
 #define   STON_HT_HEADERSIZE (sizeof(struct ston_ht_header_t))
 
 STON_FUNC
@@ -79,7 +79,7 @@ uint32_t  ston_ht32_insert(ston_ht,uint32_t,uint16_t,uint32_t);
 STON_FUNC
 size_t    ston_ht32_insertx(ston_ht,uint32_t,uint32_t*,size_t,size_t);
 
-#define   ston_ht32_new(_COL,_N,_F,_FN) (ston_ht32_create((struct ston_ht_header_t){_COL,ston_trailing0(ston_up2pow(_N << 1)),_F},_FN))
+#define   ston_ht32_new(_COL,_N,_F,_FN) (ston_ht32_create((ston_ht_h){_COL,ston_trailing0(ston_up2pow(_N << 1)),_F},_FN))
 #define   ston_ht32_entry(_HT,_KEY,_COL) (ston_ht32_row(_HT,_KEY) + _COL)
 #define   ston_ht_size(_HT)            ((_HT)->ht_columns << (_HT)->ht_2pow)
 #define   ston_ht_rows(_HT)            (0x1 << (_HT)->ht_2pow)
@@ -271,21 +271,22 @@ typedef struct ston_dht_header_t
   void*     (*ht_alloc)(size_t);
   void      (*ht_free)(void*);
   void**    page_head;
-}* ston_dht;
+}ston_dht_h,* ston_dht;
 #define   STON_DHT_HEADERSIZE (sizeof(struct ston_dht_header_t))
 
 STON_FUNC
-ston_dht  ston_dht32_create(uint16_t,size_t,uint8_t,void*(*)(size_t),void(*)(void*));
+ston_dht  ston_dht32_create(struct ston_ht_header_t,void*(*)(size_t),void(*)(void*));
 STON_FUNC
 uint32_t* ston_dht32_row(ston_dht,uint32_t);
 STON_FUNC
 uint32_t  ston_dht32_insert(ston_dht,uint32_t,uint16_t,uint32_t);
 STON_FUNC
-void      ston_dht32_free(ston_dht);
+size_t    ston_dht32_insertx(ston_dht,uint32_t,uint32_t*,size_t,size_t);
+STON_FUNC
+ston_dht  ston_dht32_free(ston_dht);
 
-#define   ston_dht32_new(_COL,_N,_F,_FN)         ston_dht32_create(_COLS,ston_up2pow(_N << 1),_F,_FN)
+#define   ston_dht32_new(_COL,_N,_F,_ALLOC,_FREE) (ston_dht32_create((ston_ht_h){_COL,ston_trailing0(ston_up2pow(_N << 1)),_F},_ALLOC,_FREE))
 #define   ston_dht32_entry(_HT,_KEY,_COL)        (ston_dht32_row(_HT,_KEY) + _COL)
-#define   ston_dht32_insertx(_HT,_KEY,_COL,_VAL) *ston_dht32_col(_HT,_KEY,_COL) = _VAL
 #define   ston_dht_size(_HT)           (ston_ht_size(_HT))
 #define   ston_dht_rows(_HT)           (ston_ht_rows(_HT))
 #define   ston_dht_cols(_HT)           (ston_ht_cols(_HT))
@@ -306,24 +307,20 @@ void      ston_dht32_free(ston_dht);
 */
 STON_FUNC
 ston_dht ston_dht32_create
-( uint16_t ht_columns,
-  size_t   ht_rows,
-  uint8_t  ht_flags,
-  void*   (*ht_alloc)(size_t),
-  void    (*ht_free)(void*)
+( struct ston_ht_header_t ht_header,
+  void*                   (*ht_alloc)(size_t),
+  void                    (*ht_free)(void*)
 )
-{ size_t   ht_size = ht_rows * ht_columns * sizeof(uint32_t);
+{ size_t   ht_bytes = ston_dht32_size(&ht_header);
   ston_dht ht = (ston_dht) ht_alloc(STON_DHT_SIZE);
   if (ht != NULL)
-    { for (ht->ht_2pow = 0; ht_size; ht->ht_2pow++)
-       ht_size = ht_size >> 1;
-      ht->ht_columns = ht_columns;
-      ht->ht_flags = ht_flags;
+    { memcpy(ht, &ht_header, sizeof(ht_header));
       ht->ht_alloc = ht_alloc;
       ht->ht_free = ht_free;
       ht->page_head = ston_dht_pagestart(ht);
-      if ((*(ht->page_head) = ht->ht_alloc(ston_dht_size(ht))) == NULL)
-       ht_free(ht);
+      if ((*(ht->page_head) = ht->ht_alloc(ht_bytes)) == NULL)
+       if (ht_free != NULL)
+         ht_free(ht);
     }
   return ht;
 }
@@ -370,7 +367,7 @@ uint32_t* ston_dht32_row
       page = (uint32_t**)ston_dht_pagestart(ht);
       goto next_row;
     }
-  if (row < row_end)
+  if (row + ht_cols < row_end)
     { row += ht_cols;
       goto next_row;
     }
@@ -405,14 +402,39 @@ uint32_t ston_dht32_insert
 
 /* Free the dynamic hash table */
 STON_FUNC
-void ston_dht32_free
+struct ston_dht_header_t* ston_dht32_free
 ( struct ston_dht_header_t* ht )
 { void (*ht_free)(void*) = ht->ht_free;
   if (ht_free != NULL)
     { while (ht->page_head >= ston_dht_pagestart(ht))
-       ht_free(ht->page_head--);
+       { ht_free(*(ht->page_head));
+         ht->page_head--;
+       }
       ht_free(ht);
+      return NULL;
     }
+  return ht;
+}
+
+/* Insert multiple values, returning the number of bytes written */
+STON_FUNC
+size_t
+ston_dht32_insertx
+( struct ston_dht_header_t* ht,
+  uint32_t                  key,
+  uint32_t*                 data_src,
+  size_t                    start_column,
+  size_t                    units
+)
+{ uint32_t* data_row = ston_dht32_row(ht,key);
+  uint32_t* data_limit = data_row + ston_dht_cols(ht);
+  uint32_t* data_trg = data_row + start_column;
+  if (data_row == NULL)
+    return 0;
+  while (units-- && data_trg < data_limit)
+    *data_trg++ = *data_src++;
+  return (size_t)(data_trg - data_row);
 }
 
+
 #endif //_STON_HT_H_