#include <stdlib.h> //malloc
#include <stdio.h> //print
#include <string.h> //memcpy
+#include <time.h> //clock
#include "../ston/ston.h"
+#define XXH_PRIVATE_API
+#include "../xxHash/xxhash.h"
/* ansi terminal colors */
#define RED "\x1b[31m"
#define CLRC "\x1b[0m" //clear current color
#define CLRCN CLRC"\n"
-#define print_val(val) do { \
- for (i = 0; i < (size_t)columns; i++) \
- printf("["YELLOW"%x"CLRC"]",val[i]); \
- printf("\n"); \
- } while(0)
-
-#define check_ht(_HT) \
- if ((_HT) == NULL) \
- { fprintf(stderr,RED"Could not allocate ht32"CLRCN); \
- return -1; \
- } \
- else \
- printf("ht_size: [units:%i][bytes:%li]\n",ston_ht_size(ht),ston_ht32_size(ht)); \
-
-#define check_dht(_HT) \
- if ((_HT) == NULL) \
- { fprintf(stderr,RED"Could not allocate dht32"CLRCN); \
- return -1; \
- } \
- else \
- printf("ht_size: [units:%i][bytes:%i]\n",ston_dht_units(_HT,_HT->header.start_depth),ston_dht_bytes(_HT,_HT->header.start_depth)); \
+#define startclock(_STR) do { \
+ start = clock(); \
+ printf(_STR": "); \
+ } while (0)
+#define startclockf(_STR,...) do { \
+ start = clock(); \
+ printf(_STR": ",__VA_ARGS__); \
+ } while (0)
+
+#define endclock() do { \
+ end = clock(); \
+ printf("%5f",(end - start)/(double)CLOCKS_PER_SEC); \
+ } while (0)
+
+#define endclockn() do { \
+ end = clock(); \
+ printf("%5f\n",(end - start)/(double)CLOCKS_PER_SEC); \
+ } while (0)
+
+#define $($)#$
+#define do_test(_COL,_COUNT,_HT,_FREE,_HTNEW,_HTINSERT,_HTROW,_SEED) do { \
+ printf("[ " $(_HT) " ] "); \
+ columns = _COL; \
+ count = _COUNT; \
+ _HT = _HTNEW; \
+ startclockf("Filling " $(_HT) " with %i entries",count); \
+ while (count--) \
+ { key = XXH32(&count,4,_SEED); \
+ val[0] = key; \
+ for (i = 0; i < columns; i++) \
+ val[i] = key - i; \
+ _HTINSERT(_HT,key,val,0,columns); \
+ } \
+ endclockn(); \
+ count = _COUNT; \
+ fail = 0; \
+ startclock("Reading entries"); \
+ while (count--) \
+ { key = XXH32(&count,4,_SEED); \
+ htval = _HTROW(_HT,key); \
+ if (htval == NULL) \
+ { fail++; \
+ printf("Row returned null\n"); \
+ break; \
+ } \
+ if (*htval != key) \
+ fail++; \
+ for (i = 1; i < columns; i++) \
+ if (htval[i] != key - i) \
+ fail++; \
+ } \
+ endclock(); \
+ if (fail) \
+ printf(RED"\nFAIL"CLRC"(%i)\n", fail); \
+ else \
+ printf(GREEN"\nPASS"CLRCN); \
+ _FREE(_HT); \
+ } while (0)
int main(int argc, char* argv[])
{ static ston_ht ht;
- uint32_t* htval, previous_val;
+ static ston_dht dht;
uint32_t val[255], key;
- size_t idx;
+ uint32_t* htval;
size_t i;
- size_t elements;
uint16_t columns;
int fail;
-
- printf("up2pow [5] = [%i]\n",ston_up2pow(5));
- for (i = 0; i < 77; i += 7)
- printf("trailing0 [%X] = [%x]\n",(uint32_t)i,ston_trailing0(i));
-
- columns = 2;
- elements = 1;
- ht = ston_ht32_new(columns,elements,0,malloc);
- check_ht(ht);
- key = 0xFF;
- val[0] = key;
- val[1] = 0x5;
- printf("ht32_insertx: [%x] = ", key);
- print_val(val);
- ston_ht32_insertx(ht,key,val,0,columns);
- idx = 1;
- htval = ston_ht32_row(ht,key);
- printf("Read value [%x] matches: %s"CLRCN, htval[idx],
- (htval[idx] == val[idx]) ? GREEN"PASS" : RED"FAIL");
-
- val[1] = 0x2;
- previous_val = ston_ht32_insert(ht,key,1,val[1]);
- printf("ht32_insert: [%x] = ", key);
- print_val(val);
- printf("Previous value [%x] matches [5]: %s"CLRCN, previous_val,
- (previous_val == 0x5) ? GREEN"PASS" : RED"FAIL");
-
- free(ht);
-
- columns = 4;
- elements = 20;
- ht = ston_ht32_new(columns,elements,0,malloc);
- check_ht(ht);
- 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);
- }
- elements = 20;
- printf("Reading entries: ");
- fail = 0;
- for(key = 0xCEED; elements--; key *= 7)
- { htval = ston_ht32_row(ht,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);
- int max_capacity = ston_up2pow(20 << 1) - 20;
- 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: ");
- 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);
-
- 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++)
- 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 = 500;
- columns = 6;
- dht = ston_dht32_new(columns, malloc, free);
- check_dht(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 = 100000;
- 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);
-
- max_capacity = 5000000;
- 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_dht_free(dht);
-
- return 0;
+ clock_t start, end;
+ int count;
+ printf("\nLow usage:\n");
+ do_test(2,200,ht,free,ston_ht32_new(2,200,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED);
+ do_test(5,200,ht,free,ston_ht32_new(5,200,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED);
+ do_test(2,200,dht,ston_dht_free,ston_dht32_new(2,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED);
+ do_test(5,200,dht,ston_dht_free,ston_dht32_new(5,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED);
+
+ printf("\nLow-mid usage:\n");
+ do_test(2,10000,ht,free,ston_ht32_new(2,10000,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED);
+ do_test(5,10000,ht,free,ston_ht32_new(5,10000,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED);
+ do_test(2,10000,dht,ston_dht_free,ston_dht32_new(2,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED);
+ do_test(5,10000,dht,ston_dht_free,ston_dht32_new(5,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED);
+
+ printf("\nMid usage:\n");
+ do_test(2,500000,ht,free,ston_ht32_new(2,500000,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED);
+ do_test(5,500000,ht,free,ston_ht32_new(5,500000,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED);
+ do_test(2,500000,dht,ston_dht_free,ston_dht32_new(2,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED);
+ do_test(5,500000,dht,ston_dht_free,ston_dht32_new(5,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED);
+
+ printf("\nMid-high usage:\n");
+ do_test(2,9000000,ht,free,ston_ht32_new(2,9000000,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED);
+ do_test(5,9000000,ht,free,ston_ht32_new(5,9000000,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED);
+ do_test(2,9000000,dht,ston_dht_free,ston_dht32_new(2,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED);
+ do_test(2,9000000,dht,ston_dht_free,ston_dht32_new(5,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED);
+
+ /* printf("\nHigh usage:\n"); */
+ /* do_test(2,90000000,ht,free,ston_ht32_new(2,90000000,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED); */
+ /* do_test(2,90000000,dht,ston_dht_free,ston_dht32_new(2,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED); */
+
+ /* printf("\nHuge usage:\n"); */
+ /* do_test(2,100000000,ht,free,ston_ht32_new(2,100000000,0,malloc),ston_ht32_insertx,ston_ht32_row,0xCEED); */
+ /* do_test(2,100000000,dht,ston_dht_free,ston_dht32_new(2,malloc,free),ston_dht32_insertx,ston_dht32_row,0xCEED); */
+
+ printf("\nDONE\n");
}
STON_FUNC_STATIC
STON_FUNC_NOINLINE
ston_ht ston_ht32_fread(FILE*,long,void*(*)(size_t));
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
size_t ston_ht32_fwrite(ston_ht,FILE*,long);
#else
#include <stddef.h>
entire structure is verified, and all file operations are finished.
Returns NULL with properly set errno on failure.
*/
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
ston_ht ston_ht32_fread
( FILE* file,
long fpos,
/* Writes a 32-bit hash table from memory into a file at fpos. Returns the
number of bytes written to the file, errno is set on error. */
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
size_t ston_ht32_fwrite
( struct ston_ht_header_t* ht,
FILE* file,
}
-#ifndef STON_DHT_SIZE
-#define STON_DHT_SIZE 4096
-#endif
-
/* STON Dynamic Hashtable Structure
A dynamic form of the generic hashtable implementation above which uses
external allocation.
*/
typedef struct ston_dht_header_t
-{ uint16_t columns;
- uint8_t unit_bytes;
- uint8_t start_depth;
-}ston_dht_h;
-
-typedef struct ston_dht_t
-{ ston_dht_h header;
- void* pages[sizeof(void*) * 8];
- void* (*ht_alloc)(size_t);
- void (*ht_free)(void*);
-}* ston_dht;
-
-STON_FUNC
-ston_dht ston_dht_create(uint16_t,uint8_t,uint8_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
-size_t ston_dht32_insertx(ston_dht,uint32_t,uint32_t*,uint16_t,size_t);
-STON_FUNC
-ston_dht ston_dht_free(ston_dht);
-
-#define ston_dht_units(_HT,_DEPTH) ((_HT)->header.columns << _DEPTH)
-#define ston_dht_bytes(_HT,_DEPTH) (ston_dht_units(_HT,_DEPTH) * (_HT)->header.unit_bytes)
-#define ston_dht_new(_COL,_ALOC,_FRE) (ston_dht_create(_COL,3,sizeof(int),_ALOC,_FRE))
-#define ston_dht_sized(_COL,_N,_ALOC,_FRE) (ston_dht_create(_COL,ston_trailing0(ston_up2pow(_N),sizeof(int),_ALOC,_FRE)))
-#define ston_dht32_entry(_HT,_KEY,_COL) (ston_dht32_row(_HT,_KEY) + _COL)
-#define ston_dht32_new(_COL,_ALOC,_FRE) (ston_dht_create(_COL,0,sizeof(uint32_t),_ALOC,_FRE))
-#define ston_dht32_sized(_COL,_N,_ALOC,_FRE) (ston_dht_create(_COL,ston_trailing0(ston_up2pow(_N)),sizeof(uint32_t),_ALOC,_FRE))
-
-
-/* Creates a new bucketted hash table, provided a memory allocation function
- that takes a single size_t bytes, a memory free function, a column count, and
- a row count which determines the size of the buckets.
-*/
-STON_FUNC
-ston_dht ston_dht_create
-( uint16_t columns,
- uint8_t start_depth,
- uint8_t unit_bytes,
- void* (*ht_alloc)(size_t),
- void (*ht_free)(void*)
-)
-{ ston_dht ht = (ston_dht) ht_alloc(sizeof(struct ston_dht_t));
- if (ht != NULL)
- { ht->header.columns = columns;
- ht->header.start_depth = start_depth;
- ht->header.unit_bytes = unit_bytes;
- memset(ht->pages, 0, sizeof(void*) * sizeof(void*) * 8);
- ht->pages[start_depth] = ht_alloc(ston_dht_bytes(ht, start_depth));
- ht->ht_alloc = ht_alloc;
- ht->ht_free = ht_free;
- if (ht->pages[start_depth] == NULL && ht_free != NULL)
- ht_free(ht);
- else
- memset(ht->pages[start_depth], 0, ston_dht_bytes(ht, start_depth));
- }
- return ht;
-}
-
-/* Returns a pointer to the row of data in the hashtable containing the provided
- key, inserts if not found. Returns NULL on overflow.
-*/
-STON_FUNC
-uint32_t* ston_dht32_row
-( struct ston_dht_t* ht,
- uint32_t key
-)
-{ uint16_t columns = ht->header.columns;
- uint8_t depth = ht->header.start_depth;
- uint32_t mask = ((0x1 << depth) - 1) >> 1;
- void* page;
- uint32_t* row;
- uint32_t row_key;
- next_page:
- if (ht->pages[depth] == NULL)
- { ht->pages[depth] = ht->ht_alloc(ston_dht_bytes(ht, depth));
- if (ht->pages[depth] == NULL)
- return NULL;
- memset(ht->pages[depth], 0, ston_dht_bytes(ht, depth));
- }
- page = ht->pages[depth];
- row = (uint32_t*)page + ((key & mask) * columns);
- row_key = *row;
- if (row_key == key || row_key == 0)
- { row[0] = key;
- return row;
- }
- depth++;
- mask = (mask << 1) | 0x1;
- goto next_page;
-}
-
-/* Inserts a value into a hashtable at the specified column, returning the
- previous value */
-STON_FUNC
-uint32_t ston_dht32_insert
-( struct ston_dht_t* ht,
- uint32_t key,
- uint16_t column,
- uint32_t value
-)
-{ uint32_t* value_location, old_value;
- value_location = ston_dht32_entry(ht,key,column);
- old_value = *value_location;
- *value_location = value;
- return old_value;
-}
-
-/* Insert multiple values, returning the number of bytes written */
-STON_FUNC
-size_t
-ston_dht32_insertx
-( struct ston_dht_t* ht,
- uint32_t key,
- uint32_t* data_src,
- uint16_t start_column,
- size_t units
-)
-{ uint32_t* data_row = ston_dht32_row(ht,key);
- uint32_t* data_limit = data_row + ht->header.columns;
- 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);
-}
-
-/* Free the dynamic hash table */
-STON_FUNC
-struct ston_dht_t* ston_dht_free
-( struct ston_dht_t* ht )
-{ void (*ht_free)(void*) = ht->ht_free;
- uint8_t depth = ht->header.start_depth;
- void** pages = ht->pages;
- if (ht_free != NULL)
- { while (pages[depth] != NULL)
- ht_free(pages[depth++]);
- ht_free(ht);
- return NULL;
- }
- return ht;
-}
-
-/********************************************************************************
-*********************************************************************************
-*********************************************************************************
-********************************************************************************/
-typedef struct ston_dht2_header_t
{ uint16_t val_bytes;
uint8_t key_bytes;
uint8_t flags;
-}ston_dht2_h;
-
-typedef struct ston_dht2_bucket_t
-{ uint8_t depth;
- void* page;
- uint32_t count;
-}ston_dht2_bucket_h,* ston_dht2_bucket;
+}ston_dht_h;
-#define STON_DHT_BUCKETS_SIZE (sizeof(void*) * 8)
-typedef struct ston_dht2_t
-{ ston_dht2_h header;
- ston_dht2_bucket_h buckets[1 + STON_DHT_BUCKETS_SIZE];
- ston_dht2_bucket bsp;
- uint32_t row_bytes;
- uint8_t buckets_len;
+typedef struct ston_dht_t
+{ ston_dht_h header;
void* (*ht_alloc)(size_t);
void (*ht_free)(void*);
-}* ston_dht2;
+ void* bucket_root;
+ size_t rowsize, bucketsize;
+}* ston_dht;
STON_FUNC
-ston_dht2 ston_dht2_create(uint16_t,uint8_t,void*(*)(size_t),void(*)(void*));
+ston_dht ston_dht_new(uint16_t,uint8_t,void*(*)(size_t),void(*)(void*));
STON_FUNC
-uint32_t* ston_dht232_row(ston_dht2,uint32_t);
-STON_FUNC
-uint32_t ston_dht232_insert(ston_dht2,uint32_t,uint16_t,uint32_t);
-STON_FUNC
-size_t ston_dht232_insertx(ston_dht2,uint32_t,uint32_t*,uint16_t,size_t);
+ston_dht ston_dht_free(ston_dht);
STON_FUNC
-ston_dht2 ston_dht2_free(ston_dht2);
-
-#define ston_dht2_bytes(_HT,_DEPTH) ((_HT)->row_bytes << (_DEPTH))
-#define ston_dht2_new(_COL,_ALOC,_FRE) (ston_dht2_create(_COL,sizeof(int),_ALOC,_FRE))
-#define ston_dht232_new(_COL,_ALOC,_FRE) (ston_dht2_create(_COL,sizeof(uint32_t),_ALOC,_FRE))
-#define ston_dht232_entry(_HT,_KEY,_COL) (ston_dht232_row(_HT,_KEY) + _COL)
-
+void* ston_dht_data(ston_dht,void*);
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
+void ston_dht_free_bucket(ston_dht,void*);
+/* STON_FUNC */
+/* ston_dht ston_dht_iterate_start(ston_dht); */
+/* STON_FUNC */
+/* ston_dht ston_dht_iterate_next(ston_dht); */
+
+// Compatibility macros
+#define ston_dht32_new(_COL,_ALOC,_FRE) (ston_dht_new(4 * _COL, 4, _ALOC, _FRE))
+#define ston_dht32_row(_HT,_K) ((uint32_t*)((uint8_t*)ston_dht_data(_HT,&(_K)) - 4))
+#define ston_dht32_insertx(_HT,_K,_VP,_OFFS,_N) \
+ memcpy((uint32_t*)((uint8_t*)ston_dht_data(_HT,&(_K)) + ((_OFFS - 1) * 4)),_VP,_N * 4)
/* Creates a new bucketted hash table, provided a memory allocation function
that takes a single size_t bytes, a memory free function, a column count, and
a row count which determines the size of the buckets.
*/
-static ston_dht2_bucket_h dummy_bucket = { (uint8_t)-1, NULL, (uint32_t)-1 };
-
STON_FUNC
-ston_dht2 ston_dht2_create
+ston_dht ston_dht_new
( uint16_t val_bytes,
uint8_t key_bytes,
void* (*ht_alloc)(size_t),
void (*ht_free)(void*)
)
-{ ston_dht2 ht = (ston_dht2) ht_alloc(sizeof(struct ston_dht2_t));
+{ ston_dht ht = (ston_dht) ht_alloc(sizeof(struct ston_dht_t));
if (ht != NULL)
{ ht->header.val_bytes = val_bytes;
ht->header.key_bytes = key_bytes;
- ht->row_bytes = val_bytes + key_bytes;
+ ht->rowsize = sizeof(void*) + key_bytes + val_bytes;
+ ht->bucketsize = ht->rowsize * 0x100;
ht->ht_alloc = ht_alloc;
ht->ht_free = ht_free;
- size_t i;
- for (i = 0; i <= STON_DHT_BUCKETS_SIZE; i++)
- ht->buckets[i] = dummy_bucket;
- ht->bsp = ht->buckets + STON_DHT_BUCKETS_SIZE - 1;
- ht->bsp->page = ht_alloc(ston_dht2_bytes(ht, 4));
- if (ht->bsp->page == NULL && ht_free != NULL)
+ ht->bucket_root = ht_alloc(ht->bucketsize);
+ if (ht->bucket_root == NULL && ht_free != NULL)
ht_free(ht);
else
- { memset((ht->bsp->page), 0, ston_dht2_bytes(ht,4));
- ht->bsp->depth = 4;
- ht->bsp->count = 0;
- ht->buckets_len = 1;
- }
+ memset((ht->bucket_root), 0, ht->bucketsize);
}
return ht;
}
/* Returns a pointer to the row of data in the hashtable containing the provided
key, inserting if not found, or NULL if a memory error occurs */
STON_FUNC
-uint32_t* ston_dht232_row
-( struct ston_dht2_t* ht,
- uint32_t key
+void* ston_dht_data
+( struct ston_dht_t* ht,
+ void* key
)
-{ int8_t bucket_no = (int8_t)ht->buckets_len - 1;
- uint32_t* row, row_key, mask;
- size_t bytes;
- int8_t zero_bucket = (int8_t)-1;
- ston_dht2_bucket bsp = ht->bsp;
- ston_dht2_bucket_h bucket;
+{ size_t key_bytes = ht->header.key_bytes;
+ uint8_t* key_byte = (uint8_t*)key;
+ uint8_t* bucket = (uint8_t*)ht->bucket_root;
+ uint8_t** bucketp;
+ uint8_t* row,* a,* b;
+ uint8_t a_not_empty;
+ size_t i;
+ next_row:
+ row = bucket + (ht->rowsize * (*key_byte));
+ a = row + sizeof(void*);
+ b = (uint8_t*)key;
+ a_not_empty = 0;
+ for (i = 0; i < key_bytes; i++)
+ { a_not_empty |= a[i];
+ if (a_not_empty && a[i] != b[i])
+ goto next_bucket;
+ }
+ if (!a_not_empty)
+ memcpy(row + sizeof(void*),key,key_bytes);
+ goto done;
next_bucket:
- bucket = bsp[bucket_no];
- /* Find until out of allocated pages, then insert at last empty bucket position */
- if (bucket.page == NULL)
- { if (zero_bucket != (int8_t)-1)
- { bucket = bsp[zero_bucket];
- mask = (0x1 << bucket.depth) - 1;
- row = (uint32_t*)bucket.page + (key & mask);
- *row = key;
- bucket.count++;
- /* Swap the buckets up a level if the count has exceeded its parent's count */
- if (bucket.count > bsp[zero_bucket + 1].count)
- { bsp[zero_bucket] = bsp[zero_bucket + 1];
- bsp[zero_bucket + 1] = bucket;
- }
- else
- bsp[zero_bucket].count = bucket.count;
- return row;
- }
- /* No buckets with a slot, shift the key right by depth, try again add a new bucket */
- bsp--;
- bucket.depth = 4 + (ht->buckets_len >> 1);
- bucket.count = 1;
- bytes = ston_dht2_bytes(ht,bucket.depth);
- if ((bucket.page = ht->ht_alloc(bytes)) == NULL)
- { printf("Failed to allocate %lu bytes, bucket %i at with len %i\n",
- bytes, bucket_no, ht->buckets_len);
- return NULL;
- }
- memset(bucket.page,0,bytes);
- *bsp = bucket;
- ht->bsp = bsp;
- ht->buckets_len++;
- mask = (0x1 << bucket.depth) - 1;
- row = (uint32_t*)bucket.page + (key & mask);
- *row = key;
- return row;
+ key_byte++;
+ bucketp = (uint8_t**)row;
+ if (*bucketp == NULL)
+ { if ((*bucketp = ht->ht_alloc(ht->bucketsize)) == NULL)
+ return NULL;
+ else
+ memset(*bucketp,0,ht->bucketsize);
}
- /* Compute mask, and use it to find the row in the page */
- mask = (0x1 << bucket.depth) - 1;
- row = (uint32_t*)bucket.page + (key & mask);
- /* Look at the key at row[0], branch */
- row_key = *row;
- if (row_key == key)
- return row;
- if (row_key == 0)
- zero_bucket = bucket_no;
- bucket_no--;
- goto next_bucket;
+ bucket = *bucketp;
+ goto next_row;
+ done:
+ return (void*) row + sizeof(void*) + key_bytes;
}
-/* Inserts a value into a hashtable at the specified column, returning the
- previous value */
+/* Free the dynamic hash table */
STON_FUNC
-uint32_t ston_dht232_insert
-( struct ston_dht2_t* ht,
- uint32_t key,
- uint16_t column,
- uint32_t value
-)
-{ uint32_t* value_location, old_value;
- value_location = ston_dht232_entry(ht,key,column);
- old_value = *value_location;
- *value_location = value;
- return old_value;
+struct ston_dht_t* ston_dht_free
+( struct ston_dht_t* ht )
+{ void (*ht_free)(void*) = ht->ht_free;
+ if (ht_free == NULL)
+ return NULL;
+ ston_dht_free_bucket(ht, ht->bucket_root);
+ ht_free(ht);
+ return ht;
}
-/* Insert multiple values, returning the number of bytes written */
-STON_FUNC
-size_t
-ston_dht232_insertx
-( struct ston_dht2_t* ht,
- uint32_t key,
- uint32_t* data_src,
- uint16_t start_column,
- size_t units
+/* Recursively free pages by lookup */
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
+void ston_dht_free_bucket
+( struct ston_dht_t* ht,
+ void* bucket
)
-{ uint32_t* data_row = ston_dht232_row(ht,key);
- uint32_t* data_limit = data_row + ht->row_bytes;
- 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);
-}
-
-/* Free the dynamic hash table */
-STON_FUNC
-struct ston_dht2_t* ston_dht2_free
-( struct ston_dht2_t* ht )
-{ void (*ht_free)(void*) = ht->ht_free;
- uint8_t bucket = ht->buckets_len;
- if (ht_free != NULL)
- { while (bucket--)
- ht_free(ht->buckets[bucket].page);
- ht_free(ht);
- return NULL;
+{ size_t key_bytes = ht->header.key_bytes;
+ size_t val_bytes = ht->header.val_bytes;
+ void** bucket_cur = (void**)((uint8_t*)bucket);
+ void** bucket_max = (void**)((uint8_t*)bucket_cur + ((sizeof(void*) + key_bytes + val_bytes) * 0x100));
+ while (bucket_cur < bucket_max)
+ { if (*bucket_cur != NULL)
+ ston_dht_free_bucket(ht, *bucket_cur);
+ bucket_cur = (void**)((uint8_t*)bucket_cur + sizeof(void*) + key_bytes + val_bytes);
}
- return ht;
+ ht->ht_free(bucket);
}
projects / henge / apc.git / commitdiff