From 78c78f12412aa19ebdd788a5d0f13eba2ec88bc9 Mon Sep 17 00:00:00 2001 From: ken Date: Fri, 24 Feb 2017 10:48:01 -0800 Subject: [PATCH] ston initial --- ston/ston.h | 12 +++ ston/ston_ht.h | 232 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 244 insertions(+) create mode 100644 ston/ston.h create mode 100644 ston/ston_ht.h diff --git a/ston/ston.h b/ston/ston.h new file mode 100644 index 0000000..b691f56 --- /dev/null +++ b/ston/ston.h @@ -0,0 +1,12 @@ +/*!@file + \brief STON Interpretation Functions + \details C implementation of data structures and algorithms in the STON asset + package protocol + \author Ken Grimes + \date Feb 2017 + ----------------------------------------------------------------------------*/ +#ifndef _STON_H_ +#define _STON_H_ +/* STON Hashtable implementation */ +#include "ston_ht.h" +#endif //_STON_H_ diff --git a/ston/ston_ht.h b/ston/ston_ht.h new file mode 100644 index 0000000..0864aa7 --- /dev/null +++ b/ston/ston_ht.h @@ -0,0 +1,232 @@ +/*!@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 +#include //memcpy +#include +#endif //STON_NOSTDIO +#include +/* 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_ -- 2.18.0