-{ 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