From 6f8c57f8040bf31ebad01119365b416a12c94341 Mon Sep 17 00:00:00 2001 From: ken Date: Tue, 7 Mar 2017 16:57:35 -0800 Subject: [PATCH] fwrite implemented fwrite implemented --- ston/ston_ht.h | 214 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 214 insertions(+) diff --git a/ston/ston_ht.h b/ston/ston_ht.h index e97a589..5063431 100644 --- a/ston/ston_ht.h +++ b/ston/ston_ht.h @@ -52,6 +52,7 @@ STON_FUNC_STATIC STON_FUNC_NOINLINE ston_ht ston_ht32_fread(FILE*,long,void*(*)(size_t)); +size_t ston_ht32_fwrite(ston_ht,FILE*,long); #else #include #endif //STON_HT_FREAD @@ -183,6 +184,22 @@ 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. */ +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 + || (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))) + return 0; + return bytes_written; +} #endif /* Returns a pointer to the row of data in the hashtable containing the provided @@ -415,5 +432,202 @@ struct ston_dht_t* ston_dht_free 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; + } + } + 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 +) +{ 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; + } + /* 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; +} + +/* Inserts a value into a hashtable at the specified column, returning the + previous value */ +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; +} + +/* 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 +) +{ 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; + } + return ht; +} + #endif //_STON_HT_H_ -- 2.18.0