X-Git-Url: https://git.kengrimes.com/?p=henge%2Fapc.git;a=blobdiff_plain;f=ston%2Fston_ht.h;h=2d9cb79d2c65a1bf5a8d05ab0f2694f0cbf88be9;hp=fb5d5669d4b6a5e65b7d026a1b2bdccb3a18754c;hb=6bcbbd2bd3710e13cad79b6822ef93e796d5e105;hpb=16091722cd675ef3e48a56c22fc827eb5cde352e diff --git a/ston/ston_ht.h b/ston/ston_ht.h index fb5d566..2d9cb79 100644 --- a/ston/ston_ht.h +++ b/ston/ston_ht.h @@ -52,6 +52,9 @@ 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 #endif //STON_HT_FREAD @@ -64,14 +67,13 @@ typedef struct ston_ht_header_t { uint16_t ht_columns; uint8_t ht_2pow, ht_flags; }ston_ht_h,* ston_ht; -#define STON_HT_HEADERSIZE (sizeof(struct ston_ht_header_t)) 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 @@ -79,7 +81,7 @@ uint32_t ston_ht32_insert(ston_ht,uint32_t,uint16_t,uint32_t); 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((ston_ht_h){_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) @@ -129,13 +131,17 @@ uint8_t ston_trailing0 */ 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; @@ -147,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, @@ -180,6 +188,26 @@ ston_ht ston_ht32_fread 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 @@ -257,183 +285,144 @@ 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 ht_columns; - uint8_t ht_2pow, ht_flags; - void* (*ht_alloc)(size_t); - void (*ht_free)(void*); - void** page_head; -}ston_dht_h,* 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* bucket_root; + size_t rowsize, bucketsize; +}* ston_dht; STON_FUNC -ston_dht ston_dht32_create(struct ston_ht_header_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_dht ston_dht_new(uint16_t,uint8_t,void*(*)(size_t),void(*)(void*)); STON_FUNC -size_t ston_dht32_insertx(ston_dht,uint32_t,uint32_t*,size_t,size_t); +ston_dht ston_dht_free(ston_dht); STON_FUNC -ston_dht ston_dht32_free(ston_dht); +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); */ -#define ston_dht32_new(_COL,_N,_F,_ALLOC,_FREE) (ston_dht32_create((ston_ht_h){_COL,ston_trailing0(ston_up2pow(_N << 1)),_F},_ALLOC,_FREE)) -#define ston_dht32_entry(_HT,_KEY,_COL) (ston_dht32_row(_HT,_KEY) + _COL) -#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--)) +// 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. */ STON_FUNC -ston_dht ston_dht32_create -( struct ston_ht_header_t ht_header, - 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_bytes = ston_dht32_size(&ht_header); - 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) - { memcpy(ht, &ht_header, sizeof(ht_header)); + { 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(ht_bytes)) == NULL) - if (ht_free != NULL) - ht_free(ht); + 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. -*/ + 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_data +( 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; + 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 (row + ht_cols < row_end) - { row += ht_cols; - goto next_row; - } - 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; -} - -/* Inserts a value into a hashtable at the specified column, returning the - previous value */ -STON_FUNC -uint32_t ston_dht32_insert -( struct ston_dht_header_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; + bucket = *bucketp; + goto next_row; + done: + return (void*) row + sizeof(void*) + key_bytes; } /* Free the dynamic hash table */ STON_FUNC -struct ston_dht_header_t* ston_dht32_free -( struct ston_dht_header_t* ht ) +struct ston_dht_t* ston_dht_free +( struct ston_dht_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->page_head--; - } - ht_free(ht); - return NULL; - } + 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_dht32_insertx -( struct ston_dht_header_t* ht, - uint32_t key, - uint32_t* data_src, - size_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_dht32_row(ht,key); - uint32_t* data_limit = data_row + ston_dht_cols(ht); - 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); +{ 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); + } + ht->ht_free(bucket); }