ston/ston_ht.h

   1 /*!@file
   2   \brief   STON Hash Tables
   3   \details Aligned general purpose hash functions and memory definitions
   4            whose columns are provided, and whose rows, and sizes, are derived.
   5
   6              ht_size = header.ht_columns << header.ht_2pow;
   7              ht_rows = 0x1 << header.ht_2pow;
   8
   9            All generic hashtables in henge must have a power-of-two number of
  10            rows.  An ht_columns value that is also a power-of-two will result in
  11            a power-of-two sized memory imprint for the structure, making it easy
  12            to page align.
  13
  14            Elements in the columns may be of any arbitrary size.
  15
  16              typedef uint32_t my_ht_type;
  17              ht_bytes = ht_size * sizeof(my_ht_type);
  18
  19            implementation covers only 32-bit unit sizes.
  20
  21   \author  Ken Grimes
  22   \date    Feb 2017
  23   ----------------------------------------------------------------------------*/
  24 #ifndef _STON_HT_T_
  25 #define _STON_HT_T_
  26 /* Define STON_NOSTATIC to expose included function symbols */
  27 #ifndef STON_NOSTATIC
  28 #define STON_FUNC_STATIC static
  29 #else
  30 #define STON_FUNC_STATIC
  31 #endif //STON_NOSTATIC
  32 /* If GNUC is detected, uses attributes to stop inlining */
  33 #ifdef  __GNUC__
  34 #define STON_FUNC_NOINLINE __attribute__ ((noinline))
  35 #else
  36 #define STON_FUNC_NOINLINE
  37 #endif //__GNUC__
  38 /* Define STON_NOINLINE to prevent inline compiler hints */
  39 #ifndef STON_NOINLINE
  40 #define STON_FUNC_INLINE inline
  41 #else
  42 #define STON_FUNC_INLINE
  43 #endif //STON_NOINLINE
  44 /* Define STON_FUNC to override the default STON Function attributes */
  45 #ifndef STON_FUNC
  46 #define STON_FUNC STON_FUNC_STATIC STON_FUNC_INLINE
  47 #endif //STON_FUNC
  48 #ifndef STON_NOSTDIO
  49 #include <stdio.h>
  50 #include <string.h> //memcpy
  51 #include <alloca.h>
  52 #endif //STON_NOSTDIO
  53 #include <stdint.h>
  54 /* STON Hashtable Structure
  55    Hashtables are stored as dynamically sized two dimensional arrays
  56 */
  57 typedef struct ston_ht_header_t
  58 { uint16_t ht_columns;
  59   uint8_t  ht_2pow, ht_flags;
  60 }* ston_ht;
  61
  62 STON_FUNC
  63 size_t    ston_up2pow(size_t);
  64 STON_FUNC_STATIC
  65 STON_FUNC_NOINLINE
  66 ston_ht   ston_ht32_fread(FILE*,long,void*(*)(size_t));
  67 STON_FUNC
  68 ston_ht   ston_ht32_create(uint16_t,size_t,uint8_t,void*(*)(size_t));
  69 STON_FUNC
  70 uint32_t* ston_ht32_row(ston_ht,uint32_t);
  71 STON_FUNC
  72 uint32_t  ston_ht32_insert(ston_ht,uint32_t,uint16_t,uint32_t);
  73
  74 #define   ston_ht32_new(_COL,_N,_FN)   ston_ht32_create(_COLS,ston_up2pow(_N << 1),0,_FN)
  75 #define   ston_ht32_col(_HT,_KEY,_COL) (ston_ht32_row(_HT,_KEY) + _COL)
  76 #define   ston_ht32_insertx(_HT,_KEY,_COL,_VAL) *ston_ht32_col(_HT,_KEY,_COL) = _VAL
  77 #define   ston_ht_size(_HT)            ((_HT)->ht_columns << (_HT)->ht_2pow)
  78 #define   ston_ht_rows(_HT)            (0x1 << (_HT)->ht_2pow)
  79 #define   ston_ht_cols(_HT)            ((_HT)->ht_columns)
  80 #define   ston_ht_start(_HT)           (((uint8_t*)(_HT)) + sizeof(*(_HT)))
  81 #define   ston_ht_keyrow(_HT,_KEY)     ((_KEY) & (ston_ht_rows(ht) - 1))
  82 #define   ston_ht32_start(_HT)         ((uint32_t*)ston_ht_start(_HT))
  83 #define   ston_ht32_size(_HT)          (ston_ht_size(_HT) * sizeof(uint32_t))
  84
  85 /** @see http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 */
  86 STON_FUNC
  87 size_t ston_up2pow
  88 ( size_t val )
  89 { val = (val << 1) - 1;
  90   val |= val >> 1;
  91   val |= val >> 2;
  92   val |= val >> 4;
  93   val |= val >> 8;
  94   val |= val >> 16;
  95   return ++val;
  96 }
  97
  98 /* Creates a new hash table, provided a memory allocation function that takes a
  99    single size_t bytes, a column count, and a row count which estimates the
 100    number of unique keys held in the table.  The provided ht_rows is doubled,
 101    and rounded up to the nearest power of two to create a hash table with
 102    minimal collisions.
 103 */
 104 STON_FUNC
 105 ston_ht ston_ht32_create
 106 ( uint16_t ht_columns,
 107   size_t   ht_rows,
 108   uint8_t  ht_flags,
 109   void*    (*alloc_fn)(size_t)
 110 )
 111 { size_t  ht_size = ston_up2pow(ht_rows << 1) * ht_columns * sizeof(uint32_t);
 112   ston_ht ht = (ston_ht) alloc_fn(sizeof(struct ston_ht_header_t) + ht_size);
 113   if (ht != NULL)
 114     { for (ht->ht_2pow = 0; ht_size; ht->ht_2pow++)
 115         ht_size = ht_size >> 1;
 116       ht->ht_columns = ht_columns;
 117       ht->ht_flags = ht_flags;
 118     }
 119   return ht;
 120 }
 121
 122 #ifndef STON_NO_STDIO
 123 /* Reads a 32-bit hash table out of the provided file at the provide fpos, into
 124    a buffer allocated by alloc_fn.  Memory is allocated to the stack until the
 125    entire structure is verified, and all file operations are finished.
 126    Returns NULL with properly set errno on failure.
 127 */
 128 STON_FUNC_STATIC
 129 STON_FUNC_NOINLINE
 130 ston_ht ston_ht32_fread
 131 ( FILE* file,
 132   long  fpos,
 133   void* (*alloc_fn)(size_t)
 134 )
 135 { struct ston_ht_header_t header;
 136   ston_ht                 stack_ht, ht;
 137   long                    fpos_start;
 138   size_t                  table_size, alloc_size;
 139   if ((fpos_start = ftell(file)) == -1)
 140     return NULL;
 141   if (fread(&header, sizeof(header), 1, file) != 1)
 142     return NULL;
 143   table_size = ston_ht32_size(&header);
 144   alloc_size = sizeof(header) + table_size;
 145   stack_ht = (ston_ht) alloca(alloc_size);
 146   memcpy(stack_ht, &header, sizeof(header));
 147   if (fread(stack_ht + sizeof(header), table_size, 1, file) != 1)
 148     return NULL;
 149   if (fseek(file, fpos_start, SEEK_SET) != 0)
 150     return NULL;
 151   ht = (ston_ht) alloc_fn(alloc_size);
 152   if (ht != NULL)
 153     memcpy(ht, stack_ht, alloc_size);
 154   return ht;
 155 }
 156 #endif
 157
 158 /* Returns a pointer to the row of data in the hashtable containing the provided
 159    key, inserts if not found.  Returns NULL on overflow.
 160 */
 161 STON_FUNC_STATIC
 162 uint32_t* ston_ht32_row
 163 ( struct ston_ht_header_t* ht,
 164   uint32_t                key
 165 )
 166 { uint32_t* row,* row_start = ston_ht32_start(ht);
 167   uint16_t  ht_cols = ston_ht_cols(ht);
 168   size_t    row_number = ston_ht_keyrow(ht,key);
 169   size_t    row_max = ston_ht_rows(ht);
 170   uint8_t   looped = 0;
 171  next_row:
 172   row = row_start + (row_number * ht_cols);
 173   if (row[0] != 0)
 174     goto populated;
 175  write_position:
 176   row[0] = key;
 177   return row;
 178  populated:
 179   if (row[0] == key)
 180     goto write_position;
 181   if (row_number < row_max)
 182     row_number++;
 183   else if (looped)
 184       return NULL;
 185   else
 186     { looped++;
 187       row_number = 0;
 188     }
 189   goto next_row;
 190 }
 191
 192 /* Inserts a value into a hashtable at the specified column, returning the
 193    previous value */
 194 STON_FUNC
 195 uint32_t ston_ht32_insert
 196 ( struct ston_ht_header_t* ht,
 197   uint32_t                key,
 198   uint16_t                column,
 199   uint32_t                value
 200 )
 201 { uint32_t* value_location, old_value;
 202   value_location = ston_ht32_col(ht,key,column);
 203   old_value = *value_location;
 204   *value_location = value;
 205   return old_value;
 206 }
 207
 208 /* STON Dynamic Hashtable Structure
 209    A dynamic form of the generic hashtable implementation above which uses
 210    external allocation.
 211 */
 212 typedef struct ston_dht_header_t
 213 { uint16_t ht_columns;
 214   uint8_t  ht_2pow, ht_flags;
 215   void     (*ht_alloc)(size_t);
 216   void*    ht_pages[];
 217 }* ston_dht;
 218
 219 #define   ston_dht_size(_HT)          (ston_ht_size(_HT))
 220 #define   ston_dht_rows(_HT)          (ston_ht_rows(_HT))
 221 #define   ston_dht_cols(_HT)          (ston_ht_cols(_HT))
 222 #define   ston_dht_keyrow(_HT,_KEY)   (ston_ht_keyrow(_HT,_KEY))
 223 #define   ston_dht_start(_HT)         (_HT->ht_pages[0])
 224 #define   ston_dht32_start(_HT)       ((_uint32*)ston_dht_start(_HT))
 225 ston_dht  ston_dht32_create(uint16_t,size_t,void*(*)(size_t));
 226 uint32_t* ston_dht32_row(ston_dht,uint32_t);
 227 #define   ston_dht32_col(_HT,_KEY,_COL) (ston_dht32_row(_HT,_KEY) + _COL)
 228 uint32_t  ston_dht32_insert(ston_dht,uint32_t,uint16_t,uint32_t);
 229 #define   ston_dht32_insertx(_HT,_KEY,_COL,_VAL) *ston_dht32_col(_HT,_KEY,_COL) = _VAL
 230
 231
 232 #endif //_STON_HT_H_