uint32_t ston_ht32_insert(ston_ht,uint32_t,uint16_t,uint32_t);
#define ston_ht32_new(_COL,_N,_F,_FN) ston_ht32_create(_COLS,ston_up2pow(_N << 1),_F,_FN)
-#define ston_ht32_col(_HT,_KEY,_COL) (ston_ht32_row(_HT,_KEY) + _COL)
-#define ston_ht32_insertx(_HT,_KEY,_COL,_VAL) *ston_ht32_col(_HT,_KEY,_COL) = _VAL
+#define ston_ht32_entry(_HT,_KEY,_COL) (ston_ht32_row(_HT,_KEY) + _COL)
+#define ston_ht32_insertx(_HT,_KEY,_COL,_VAL) *ston_ht32_entry(_HT,_KEY,_COL) = _VAL
#define ston_ht_size(_HT) ((_HT)->ht_columns << (_HT)->ht_2pow)
#define ston_ht_rows(_HT) (0x1 << (_HT)->ht_2pow)
#define ston_ht_cols(_HT) ((_HT)->ht_columns)
#define ston_ht_start(_HT) (((uint8_t*)(_HT)) + sizeof(*(_HT)))
#define ston_ht_keyrow(_HT,_KEY) ((_KEY) & (ston_ht_rows(ht) - 1))
#define ston_ht32_start(_HT) ((uint32_t*)ston_ht_start(_HT))
+#define ston_ht32_end(_HT) (ston_ht32_start(_HT) + ston_ht_size(_HT))
#define ston_ht32_size(_HT) (ston_ht_size(_HT) * sizeof(uint32_t))
/** @see http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 */
ston_ht stack_ht, ht;
long fpos_start;
size_t table_size, alloc_size;
+ int errno_local;
if ((fpos_start = ftell(file)) == -1)
return NULL;
if (fread(&header, sizeof(header), 1, file) != 1)
- return NULL;
+ goto fail_seekback;
table_size = ston_ht32_size(&header);
alloc_size = sizeof(header) + table_size;
stack_ht = (ston_ht) alloca(alloc_size);
memcpy(stack_ht, &header, sizeof(header));
if (fread(stack_ht + sizeof(header), table_size, 1, file) != 1)
- return NULL;
+ goto fail_seekback;
if (fseek(file, fpos_start, SEEK_SET) != 0)
return NULL;
ht = (ston_ht) alloc_fn(alloc_size);
if (ht != NULL)
memcpy(ht, stack_ht, alloc_size);
return ht;
+ fail_seekback:
+ /* Try to seek the file back to origin without clobbering errno */
+ errno_local = errno;
+ fseek(file, fpos_start, SEEK_SET);
+ errno = errno_local;
+ return NULL;
}
#endif
/* 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_STATIC
+STON_FUNC
uint32_t* ston_ht32_row
( struct ston_ht_header_t* ht,
uint32_t key
)
-{ uint32_t* row,* row_start = ston_ht32_start(ht);
+{ uint32_t* row;
+ uint32_t* row_start = ston_ht32_start(ht);
+ uint32_t* row_end = ston_ht32_end(ht);
uint16_t ht_cols = ston_ht_cols(ht);
size_t row_number = ston_ht_keyrow(ht,key);
- size_t row_max = ston_ht_rows(ht);
uint8_t looped = 0;
- next_row:
row = row_start + (row_number * ht_cols);
+ next_row:
if (row[0] != 0)
goto populated;
write_position:
populated:
if (row[0] == key)
goto write_position;
- if (row_number < row_max)
- row_number++;
+ if (row < row_end)
+ row += ht_cols;
else if (looped)
return NULL;
else
{ looped++;
- row_number = 0;
+ row = row_start;
}
goto next_row;
}
uint32_t value
)
{ uint32_t* value_location, old_value;
- value_location = ston_ht32_col(ht,key,column);
+ value_location = ston_ht32_entry(ht,key,column);
old_value = *value_location;
*value_location = value;
return old_value;
}
+#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_pages[];
+{ 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))
-#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_start(_HT) (_HT->ht_pages[0])
-#define ston_dht32_start(_HT) ((_uint32*)ston_dht_start(_HT))
-ston_dht ston_dht32_create(uint16_t,size_t,void*(*)(size_t));
+STON_FUNC
+ston_dht ston_dht32_create(uint16_t,size_t,uint8_t,void*(*)(size_t),void(*)(void*));
+STON_FUNC
uint32_t* ston_dht32_row(ston_dht,uint32_t);
-#define ston_dht32_col(_HT,_KEY,_COL) (ston_dht32_row(_HT,_KEY) + _COL)
+STON_FUNC
uint32_t ston_dht32_insert(ston_dht,uint32_t,uint16_t,uint32_t);
+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--))
+
+/* 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
+( uint16_t ht_columns,
+ size_t ht_rows,
+ uint8_t ht_flags,
+ 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);
+ 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->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_free(ht);
+ }
+ 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_header_t* ht,
+ uint32_t 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);
+ 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;
+ }
+ else if (!loop_y)
+ { loop_y = 1;
+ row = *page;
+ goto next_row;
+ }
+ 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;
+}
+
+/* Free the dynamic hash table */
+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);
+ }
+}
#endif //_STON_HT_H_
projects / henge / apc.git / blobdiff