X-Git-Url: https://git.kengrimes.com/?p=henge%2Fapc.git;a=blobdiff_plain;f=ston%2Fston_ht.h;fp=ston%2Fston_ht.h;h=2d9cb79d2c65a1bf5a8d05ab0f2694f0cbf88be9;hp=4cddc78b15bec347e299b23d359df0e9f2de3856;hb=6bcbbd2bd3710e13cad79b6822ef93e796d5e105;hpb=43d6067b655dbb51a4db074cfae58618b4ebb493 diff --git a/ston/ston_ht.h b/ston/ston_ht.h index 4cddc78..2d9cb79 100644 --- a/ston/ston_ht.h +++ b/ston/ston_ht.h @@ -52,6 +52,8 @@ 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 @@ -151,6 +153,8 @@ ston_ht ston_ht32_create 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, @@ -187,6 +191,8 @@ ston_ht ston_ht32_fread /* 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, @@ -279,238 +285,68 @@ ston_ht32_insertx } -#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; } @@ -519,116 +355,74 @@ ston_dht2 ston_dht2_create /* 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); }