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
typedef struct ston_ht_header_t
{ uint16_t ht_columns;
uint8_t ht_2pow, ht_flags;
-}* ston_ht;
-#define STON_HT_HEADERSIZE (sizeof(struct ston_ht_header_t))
+}ston_ht_h,* ston_ht;
STON_FUNC
uint32_t ston_up2pow(uint32_t);
STON_FUNC
uint8_t ston_trailing0(uint32_t);
STON_FUNC
-ston_ht ston_ht32_create(struct ston_ht_header_t,void*(*)(size_t));
+ston_ht ston_ht32_create(uint16_t,uint8_t,uint8_t,void*(*)(size_t));
STON_FUNC
uint32_t* ston_ht32_row(ston_ht,uint32_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(_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)
*/
STON_FUNC
ston_ht ston_ht32_create
-( struct ston_ht_header_t ht_header,
- void* (*alloc_fn)(size_t)
+( uint16_t ht_columns,
+ uint8_t ht_2pow,
+ uint8_t ht_flags,
+ void* (*alloc_fn)(size_t)
)
-{ size_t ht_bytes = ston_ht32_size(&ht_header);
- ston_ht ht = (ston_ht) alloc_fn(STON_HT_HEADERSIZE + ht_bytes);
+{ size_t ht_bytes = (ht_columns << ht_2pow) * sizeof(uint32_t);
+ ston_ht ht = (ston_ht) alloc_fn(sizeof(ston_ht_h) + ht_bytes);
if (ht != NULL)
- { memcpy(ht,&ht_header,STON_HT_HEADERSIZE);
+ { ht->ht_columns = ht_columns;
+ ht->ht_2pow = ht_2pow;
+ ht->ht_flags = ht_flags;
memset(ht + 1, 0, ht_bytes);
}
return ht;
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 ht_columns;
- uint8_t ht_2pow, ht_flags;
- void* (*ht_alloc)(size_t);
- void (*ht_free)(void*);
- void** page_head;
-}* ston_dht;
-#define STON_DHT_HEADERSIZE (sizeof(struct ston_dht_header_t))
+{ uint16_t val_bytes;
+ uint8_t key_bytes;
+ uint8_t flags;
+}ston_dht_h;
+typedef struct ston_dht_t
+{ ston_dht_h header;
+ 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_dht32_create(uint16_t,size_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);
+void* ston_dht_val(ston_dht,void*);
STON_FUNC
-uint32_t ston_dht32_insert(ston_dht,uint32_t,uint16_t,uint32_t);
+ston_dht ston_dht_free(ston_dht);
STON_FUNC
-void 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_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))
-#define ston_dht_keyrow(_HT,_KEY) (ston_ht_keyrow(_HT,_KEY))
-#define ston_dht_pagestart(_HT) ((void**)(((uint8_t*)(_HT)) + STON_DHT_HEADERSIZE))
-#define ston_dht_pagehead(_HT) ((_HT)->page_head)
-#define ston_dht_pagemax(_HT) ((void**)((uint8_t*)(_HT) + STON_DHT_SIZE - sizeof(void**)))
-#define ston_dht_start(_HT,_DEPTH) ((uint8_t*)*(ston_dht_pagestart(_HT) + _DEPTH))
-#define ston_dht32_start(_HT,_DEPTH) ((uint32_t*)ston_dht_start(_HT,_DEPTH))
-#define ston_dht32_end(_HT,_DEPTH) (ston_ht32_start(_HT,_DEPTH) + ston_ht_size(_HT))
-#define ston_dht32_size(_HT) (ston_dht_size(_HT) * sizeof(uint32_t))
-#define ston_dht32_pagepush(_HT) ((*(++((_HT)->page_head)) = (_HT)->ht_alloc(ston_dht32_size(_HT))))
-#define ston_dht32_pagepop(_HT) ((_HT)->ht_free((_HT)->page_head--))
+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)
-/* 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_dht32_create
-( uint16_t ht_columns,
- size_t ht_rows,
- uint8_t ht_flags,
- void* (*ht_alloc)(size_t),
- void (*ht_free)(void*)
+ston_dht ston_dht_new
+( uint16_t val_bytes,
+ uint8_t key_bytes,
+ void* (*ht_alloc)(size_t),
+ void (*ht_free)(void*)
)
-{ size_t ht_size = ht_rows * ht_columns * sizeof(uint32_t);
- ston_dht ht = (ston_dht) ht_alloc(STON_DHT_SIZE);
+{ ston_dht ht = (ston_dht) ht_alloc(sizeof(struct ston_dht_t));
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;
+ { 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;
- ht->page_head = ston_dht_pagestart(ht);
- if ((*(ht->page_head) = ht->ht_alloc(ston_dht_size(ht))) == NULL)
+ ht->bucket_root = ht_alloc(ht->bucketsize);
+ if (ht->bucket_root == NULL && ht_free != NULL)
ht_free(ht);
+ else
+ 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
-( struct ston_dht_header_t* ht,
- uint32_t key
+void* ston_dht_val
+( struct ston_dht_t* ht,
+ void* key
)
-{ uint16_t ht_cols = ston_dht_cols(ht);
- size_t row_number = ston_dht_keyrow(ht,key);
- uint32_t** page = (uint32_t**)ston_dht_pagestart(ht);
- uint32_t** pagemax = (uint32_t**)ston_dht_pagemax(ht);
- uint8_t loop_x = 0;
- uint8_t loop_y = 0;
- uint32_t* row,* row_end;
- next_page:
- row = *page + (row_number * ht_cols);
- row_end = *page + (ston_dht_size(ht) - 1);
+{ 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:
- if (row[0] != 0)
- goto populated;
- write_position:
- row[0] = key;
- return row;
- populated:
- if (row[0] == key)
- goto write_position;
- if (!loop_x)
- { if (page < pagemax)
- { if (page == (uint32_t**)ston_dht_pagehead(ht))
- if (ston_dht32_pagepush(ht) == NULL)
- { ston_dht32_free(ht);
- return NULL;
- }
- ++page;
- goto next_row;
- }
- loop_x = 1;
- row_number = (row_number + 1) % ston_dht_rows(ht);
- page = (uint32_t**)ston_dht_pagestart(ht);
- goto next_row;
- }
- if (row < row_end)
- { row += ht_cols;
- goto 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;
}
- else if (!loop_y)
- { loop_y = 1;
- row = *page;
- goto next_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);
}
- if (page < pagemax)
- { loop_y = 0;
- page++;
- goto next_page;
- }
- return NULL;
+ 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_header_t* ht,
- uint32_t key,
- uint16_t column,
- uint32_t 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;
+}
+
+/* Recursive free function for nested buckets */
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
+void ston_dht_free_bucket
+( struct ston_dht_t* ht,
+ 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);
}
-/* Free the dynamic hash table */
+/* 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
-void 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);
+void ston_dht_iterate
+( struct ston_dht_t* ht,
+ void (*fn)(void*,void*,void*),
+ void* user_data
+)
+{ ht->ht_iter = fn;
+ ht->ht_user_data = user_data;
+ ston_dht_iterate_r(ht,ht->bucket_root);
+}
+
+/* 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;
}
}
projects / henge / apc.git / blobdiff