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>
#endif //STON_HT_FREAD
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,
errno = errno_local;
return NULL;
}
+
+/* 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,
+ long fpos
+)
+{ size_t bytes_written;
+ long fpos_start;
+ if ((fpos_start = ftell(file)) == NULL
+ || fseek(file, fpos, SEEK_SET) == 0
+ || (bytes_written = fwrite(file, 1, sizeof(ston_ht_h), file)) < sizeof(ston_ht_h)
+ || (bytes_written += fwrite(file, 1, ston_ht32_bytes(ht), file)) < (sizeof(ston_ht_h) + ston_ht32_bytes(ht))
+ || fseek(file, fpos_start, SEEK_SET) == 0)
+ return 0;
+ return bytes_written;
+}
#endif
/* Returns a pointer to the row of data in the hashtable containing the provided
}
-#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;
+{ uint16_t val_bytes;
+ uint8_t key_bytes;
+ uint8_t flags;
}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*);
+ void (*ht_iter)(void*,void*,void*);
+ void* ht_user_data;
+ void* bucket_root;
+ size_t rowsize, bucketsize;
}* ston_dht;
-
-STON_FUNC
-ston_dht ston_dht_create(uint16_t,uint8_t,uint8_t,void*(*)(size_t),void(*)(void*));
+/* STON DHT API
+ Primary functions for creating hashtables, retrieving pointers to values,
+ iterating over all keys and values, and destroying hashtables. */
STON_FUNC
-uint32_t* ston_dht32_row(ston_dht,uint32_t);
+ston_dht ston_dht_new(uint16_t,uint8_t,void*(*)(size_t),void(*)(void*));
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);
+void* ston_dht_val(ston_dht,void*);
STON_FUNC
ston_dht ston_dht_free(ston_dht);
+STON_FUNC
+void ston_dht_iterate(ston_dht,void(*)(void*,void*,void*),void*);
+/* Recursive functions intended to be called by other functions, above */
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
+void ston_dht_free_bucket(ston_dht,void*);
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
+void ston_dht_iterate_r(ston_dht,void*);
+// Compatibility macros - Deprecated
+#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_val(_HT,&(_K)) - 4))
+#define ston_dht32_insertx(_HT,_K,_VP,_OFFS,_N) \
+ memcpy((uint32_t*)((uint8_t*)ston_dht_val(_HT,&(_K)) + ((_OFFS - 1) * 4)),_VP,_N * 4)
-#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.
-*/
+/* New dynamic hashtable, provided value bytes, key bytes, allocator function,
+ and free function. Value bytes and key bytes are respectively constrained to
+ uint16 and uint8 so they can be aligned to hashtables encoded for
+ streaming */
STON_FUNC
-ston_dht ston_dht_create
-( uint16_t columns,
- uint8_t start_depth,
- uint8_t unit_bytes,
+ston_dht ston_dht_new
+( uint16_t val_bytes,
+ uint8_t key_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->header.val_bytes = val_bytes;
+ ht->header.key_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;
- if (ht->pages[start_depth] == 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->pages[start_depth], 0, ston_dht_bytes(ht, start_depth));
+ memset((ht->bucket_root), 0, ht->bucketsize);
}
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.
-*/
+
+/* Returns a pointer to the value in the hashtable matching the provided key,
+ inserting if not found, or NULL if a memory error occurs */
STON_FUNC
-uint32_t* ston_dht32_row
+void* ston_dht_val
( struct ston_dht_t* ht,
- uint32_t key
+ void* 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));
+{ 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;
}
- 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;
+ if (!a_not_empty)
+ memcpy(row + sizeof(void*),key,key_bytes);
+ goto done;
+ next_bucket:
+ 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);
}
- depth++;
- mask = (mask << 1) | 0x1;
- goto next_page;
+ 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 */
+/* Recursively frees all memory stored in the hashtable, and the hashtable
+ itself */
STON_FUNC
-uint32_t ston_dht32_insert
+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;
+}
+
+/* Recursive free function for nested buckets */
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
+void ston_dht_free_bucket
( struct ston_dht_t* ht,
- uint32_t key,
- uint16_t column,
- uint32_t value
+ void* bucket
)
-{ uint32_t* value_location, old_value;
- value_location = ston_dht32_entry(ht,key,column);
- old_value = *value_location;
- *value_location = value;
- return old_value;
+{ void** bucket_cur = (void**)((uint8_t*)bucket);
+ void** bucket_max = (void**)((uint8_t*)bucket_cur + (ht->rowsize * 0x100));
+ while (bucket_cur < bucket_max)
+ { if (*bucket_cur != NULL)
+ ston_dht_free_bucket(ht, *bucket_cur);
+ bucket_cur = (void**)((uint8_t*)bucket_cur + ht->rowsize);
+ }
+ ht->ht_free(bucket);
}
-/* Insert multiple values, returning the number of bytes written */
+/* Iterate over each key/value pair and execut 'fn' with key, value and
+ user_data as its arguments. user_data may be anything, even NULL, and is
+ expected to be referenced inside the body of 'fn' as the third argument of
+ 'fn' */
STON_FUNC
-size_t
-ston_dht32_insertx
+void ston_dht_iterate
( struct ston_dht_t* ht,
- uint32_t key,
- uint32_t* data_src,
- uint16_t start_column,
- size_t units
+ void (*fn)(void*,void*,void*),
+ void* user_data
)
-{ 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);
+{ ht->ht_iter = fn;
+ ht->ht_user_data = user_data;
+ ston_dht_iterate_r(ht,ht->bucket_root);
}
-/* 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;
+/* Recursively iterate through the given bucket belonging to hashtable ht */
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
+void ston_dht_iterate_r
+( struct ston_dht_t* ht,
+ void* bucket
+)
+{ uint8_t* row = (uint8_t*)bucket;
+ uint8_t* row_max = (row + (ht->rowsize * 0x100));
+ while (row < row_max)
+ { if (*(void**)row != NULL)
+ ston_dht_iterate_r(ht, *(void**)row);
+ row += sizeof(void*);
+ ht->ht_iter((void*)row, (void*)(row + ht->header.key_bytes),ht->ht_user_data);
+ row += ht->header.key_bytes + ht->header.val_bytes;
}
- return ht;
}
-
#endif //_STON_HT_H_