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;
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;
}
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
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)
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))
*/
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;
}
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;
}
/* 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_