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,
{ 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)))
+ || (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;
}
}
-#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 DHT API
+ Primary functions for creating hashtables, retrieving pointers to values,
+ iterating over all keys and values, and destroying hashtables. */
STON_FUNC
-ston_dht ston_dht_create(uint16_t,uint8_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_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);
+void* ston_dht_val(ston_dht,void*);
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 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)
+
+/* 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_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;
-}
-
-/* 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);
+ bucket = *bucketp;
+ goto next_row;
+ done:
+ return (void*) row + sizeof(void*) + key_bytes;
}
-/* Free the dynamic hash table */
+/* Recursively frees all memory stored in the hashtable, and the hashtable
+ itself */
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;
-
-#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;
- void* (*ht_alloc)(size_t);
- void (*ht_free)(void*);
-}* ston_dht2;
-
-STON_FUNC
-ston_dht2 ston_dht2_create(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_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)
-
-
-/* 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
-( 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));
- if (ht != NULL)
- { ht->header.val_bytes = val_bytes;
- ht->header.key_bytes = key_bytes;
- ht->row_bytes = val_bytes + key_bytes;
- 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_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;
- }
- }
+ if (ht_free == NULL)
+ return NULL;
+ ston_dht_free_bucket(ht, ht->bucket_root);
+ ht_free(ht);
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
+/* Recursive free function for nested buckets */
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
+void ston_dht_free_bucket
+( struct ston_dht_t* ht,
+ void* bucket
)
-{ 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;
- 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;
+{ 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);
}
- /* 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;
+ ht->ht_free(bucket);
}
-/* Inserts a value into a hashtable at the specified column, returning the
- previous value */
+/* 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
-uint32_t ston_dht232_insert
-( struct ston_dht2_t* ht,
- uint32_t key,
- uint16_t column,
- uint32_t value
+void ston_dht_iterate
+( struct ston_dht_t* ht,
+ void (*fn)(void*,void*,void*),
+ void* user_data
)
-{ uint32_t* value_location, old_value;
- value_location = ston_dht232_entry(ht,key,column);
- old_value = *value_location;
- *value_location = value;
- return old_value;
+{ ht->ht_iter = fn;
+ ht->ht_user_data = user_data;
+ ston_dht_iterate_r(ht,ht->bucket_root);
}
-/* 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 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
)
-{ 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;
+{ 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_
projects / henge / apc.git / blobdiff