--- /dev/null
+/*!@file
+ \brief STON Hash Tables
+ \details Aligned general purpose hash functions and memory definitions
+ whose columns are provided, and whose rows, and sizes, are derived.
+
+ ht_size = header.ht_columns << header.ht_2pow;
+ ht_rows = 0x1 << header.ht_2pow;
+
+ All generic hashtables in henge must have a power-of-two number of
+ rows. An ht_columns value that is also a power-of-two will result in
+ a power-of-two sized memory imprint for the structure, making it easy
+ to page align.
+
+ Elements in the columns may be of any arbitrary size.
+
+ typedef uint32_t my_ht_type;
+ ht_bytes = ht_size * sizeof(my_ht_type);
+
+ implementation covers only 32-bit unit sizes.
+
+ \author Ken Grimes
+ \date Feb 2017
+ ----------------------------------------------------------------------------*/
+#ifndef _STON_HT_T_
+#define _STON_HT_T_
+/* Define STON_NOSTATIC to expose included function symbols */
+#ifndef STON_NOSTATIC
+#define STON_FUNC_STATIC static
+#else
+#define STON_FUNC_STATIC
+#endif //STON_NOSTATIC
+/* If GNUC is detected, uses attributes to stop inlining */
+#ifdef __GNUC__
+#define STON_FUNC_NOINLINE __attribute__ ((noinline))
+#else
+#define STON_FUNC_NOINLINE
+#endif //__GNUC__
+/* Define STON_NOINLINE to prevent inline compiler hints */
+#ifndef STON_NOINLINE
+#define STON_FUNC_INLINE inline
+#else
+#define STON_FUNC_INLINE
+#endif //STON_NOINLINE
+/* Define STON_FUNC to override the default STON Function attributes */
+#ifndef STON_FUNC
+#define STON_FUNC STON_FUNC_STATIC STON_FUNC_INLINE
+#endif //STON_FUNC
+#ifndef STON_NOSTDIO
+#include <stdio.h>
+#include <string.h> //memcpy
+#include <alloca.h>
+#endif //STON_NOSTDIO
+#include <stdint.h>
+/* STON Hashtable Structure
+ Hashtables are stored as dynamically sized two dimensional arrays
+*/
+typedef struct ston_ht_header_t
+{ uint16_t ht_columns;
+ uint8_t ht_2pow, ht_flags;
+}* ston_ht;
+
+STON_FUNC
+size_t ston_up2pow(size_t);
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
+ston_ht ston_ht32_fread(FILE*,long,void*(*)(size_t));
+STON_FUNC
+ston_ht ston_ht32_create(uint16_t,size_t,uint8_t,void*(*)(size_t));
+STON_FUNC
+uint32_t* ston_ht32_row(ston_ht,uint32_t);
+STON_FUNC
+uint32_t ston_ht32_insert(ston_ht,uint32_t,uint16_t,uint32_t);
+
+#define ston_ht32_new(_COL,_N,_FN) ston_ht32_create(_COLS,ston_up2pow(_N << 1),0,_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_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_size(_HT) (ston_ht_size(_HT) * sizeof(uint32_t))
+
+/** @see http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 */
+STON_FUNC
+size_t ston_up2pow
+( size_t val )
+{ val = (val << 1) - 1;
+ val |= val >> 1;
+ val |= val >> 2;
+ val |= val >> 4;
+ val |= val >> 8;
+ val |= val >> 16;
+ return ++val;
+}
+
+/* Creates a new hash table, provided a memory allocation function that takes a
+ single size_t bytes, a column count, and a row count which estimates the
+ number of unique keys held in the table. The provided ht_rows is doubled,
+ and rounded up to the nearest power of two to create a hash table with
+ minimal collisions.
+*/
+STON_FUNC
+ston_ht ston_ht32_create
+( uint16_t ht_columns,
+ size_t ht_rows,
+ uint8_t ht_flags,
+ void* (*alloc_fn)(size_t)
+)
+{ size_t ht_size = ston_up2pow(ht_rows << 1) * ht_columns * sizeof(uint32_t);
+ ston_ht ht = (ston_ht) alloc_fn(sizeof(struct ston_ht_header_t) + ht_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;
+ }
+ return ht;
+}
+
+#ifndef STON_NO_STDIO
+/* Reads a 32-bit hash table out of the provided file at the provide fpos, into
+ a buffer allocated by alloc_fn. Memory is allocated to the stack until the
+ 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,
+ void* (*alloc_fn)(size_t)
+)
+{ struct ston_ht_header_t header;
+ ston_ht stack_ht, ht;
+ long fpos_start;
+ size_t table_size, alloc_size;
+ if ((fpos_start = ftell(file)) == -1)
+ return NULL;
+ if (fread(&header, sizeof(header), 1, file) != 1)
+ return NULL;
+ 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;
+ 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;
+}
+#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
+uint32_t* ston_ht32_row
+( struct ston_ht_header_t* ht,
+ uint32_t key
+)
+{ uint32_t* row,* row_start = ston_ht32_start(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);
+ if (row[0] != 0)
+ goto populated;
+ write_position:
+ row[0] = key;
+ return row;
+ populated:
+ if (row[0] == key)
+ goto write_position;
+ if (row_number < row_max)
+ row_number++;
+ else if (looped)
+ return NULL;
+ else
+ { looped++;
+ row_number = 0;
+ }
+ goto next_row;
+}
+
+/* Inserts a value into a hashtable at the specified column, returning the
+ previous value */
+STON_FUNC
+uint32_t ston_ht32_insert
+( struct ston_ht_header_t* ht,
+ uint32_t key,
+ uint16_t column,
+ uint32_t value
+)
+{ uint32_t* value_location, old_value;
+ value_location = ston_ht32_col(ht,key,column);
+ old_value = *value_location;
+ *value_location = value;
+ return old_value;
+}
+
+/* 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[];
+}* ston_dht;
+
+#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));
+uint32_t* ston_dht32_row(ston_dht,uint32_t);
+#define ston_dht32_col(_HT,_KEY,_COL) (ston_dht32_row(_HT,_KEY) + _COL)
+uint32_t ston_dht32_insert(ston_dht,uint32_t,uint16_t,uint32_t);
+#define ston_dht32_insertx(_HT,_KEY,_COL,_VAL) *ston_dht32_col(_HT,_KEY,_COL) = _VAL
+
+
+#endif //_STON_HT_H_
projects / henge / apc.git / blobdiff