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 #ifdef STON_HT_FREAD
  49 #include <stdio.h>
  50 #include <string.h> //memcpy
  51 #include <errno.h>
  52 #include <alloca.h>
  53 STON_FUNC_STATIC
  54 STON_FUNC_NOINLINE
  55 ston_ht   ston_ht32_fread(FILE*,long,void*(*)(size_t));
  56 #else
  57 #include <stddef.h>
  58 #endif //STON_HT_FREAD
  59 #include <stdint.h>
  60 /* STON Hashtable Structure
  61    Hashtables are stored as dynamically sized two dimensional arrays
  62 */
  63 typedef struct ston_ht_header_t
  64 { uint16_t ht_columns;
  65   uint8_t  ht_2pow, ht_flags;
  66 }* ston_ht;
  67
  68 STON_FUNC
  69 size_t    ston_up2pow(size_t);
  70 STON_FUNC
  71 ston_ht   ston_ht32_create(uint16_t,size_t,uint8_t,void*(*)(size_t));
  72 STON_FUNC
  73 uint32_t* ston_ht32_row(ston_ht,uint32_t);
  74 STON_FUNC
  75 uint32_t  ston_ht32_insert(ston_ht,uint32_t,uint16_t,uint32_t);
  76
  77 #define   ston_ht32_new(_COL,_N,_F,_FN) ston_ht32_create(_COL,ston_up2pow(_N << 1),_F,_FN)
  78 #define   ston_ht32_entry(_HT,_KEY,_COL)        (ston_ht32_row(_HT,_KEY) + _COL)
  79 #define   ston_ht32_insertx(_HT,_KEY,_COL,_VAL) *ston_ht32_entry(_HT,_KEY,_COL) = _VAL
  80 #define   ston_ht_size(_HT)            ((_HT)->ht_columns << (_HT)->ht_2pow)
  81 #define   ston_ht_rows(_HT)            (0x1 << (_HT)->ht_2pow)
  82 #define   ston_ht_cols(_HT)            ((_HT)->ht_columns)
  83 #define   ston_ht_start(_HT)           (((uint8_t*)(_HT)) + sizeof(*(_HT)))
  84 #define   ston_ht_keyrow(_HT,_KEY)     ((_KEY) & (ston_ht_rows(ht) - 1))
  85 #define   ston_ht32_start(_HT)         ((uint32_t*)ston_ht_start(_HT))
  86 #define   ston_ht32_end(_HT)           (ston_ht32_start(_HT) + ston_ht_size(_HT))
  87 #define   ston_ht32_size(_HT)          (ston_ht_size(_HT) * sizeof(uint32_t))
  88
  89 /** @see http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 */
  90 STON_FUNC
  91 size_t ston_up2pow
  92 ( size_t val )
  93 { val = (val << 1) - 1;
  94   val |= val >> 1;
  95   val |= val >> 2;
  96   val |= val >> 4;
  97   val |= val >> 8;
  98   val |= val >> 16;
  99   return ++val;
 100 }
 101
 102 /* Creates a new hash table, provided a memory allocation function that takes a
 103    single size_t bytes, a column count, and a row count which determines the
 104    size of the table.
 105
 106    use ston_ht32_new to specify the exact or estimated number of unique keys
 107    held in the table.  With ston_ht32_new, the provided ht_rows is doubled, and
 108    rounded up to the nearest power of two to create a hash table with minimal
 109    collisions.
 110 */
 111 STON_FUNC
 112 ston_ht ston_ht32_create
 113 ( uint16_t ht_columns,
 114   size_t   ht_rows,
 115   uint8_t  ht_flags,
 116   void*    (*alloc_fn)(size_t)
 117 )
 118 { size_t  ht_size = ht_rows * ht_columns * sizeof(uint32_t);
 119   ston_ht ht = (ston_ht) alloc_fn(sizeof(struct ston_ht_header_t) + ht_size);
 120   if (ht != NULL)
 121     { for (ht->ht_2pow = 0; ht_size; ht->ht_2pow++)
 122         ht_size = ht_size >> 1;
 123       ht->ht_columns = ht_columns;
 124       ht->ht_flags = ht_flags;
 125     }
 126   return ht;
 127 }
 128
 129 #ifdef STON_HT_FREAD
 130 /* Reads a 32-bit hash table out of the provided file at the provide fpos, into
 131    a buffer allocated by alloc_fn.  Memory is allocated to the stack until the
 132    entire structure is verified, and all file operations are finished.
 133    Returns NULL with properly set errno on failure.
 134 */
 135 STON_FUNC_STATIC
 136 STON_FUNC_NOINLINE
 137 ston_ht ston_ht32_fread
 138 ( FILE* file,
 139   long  fpos,
 140   void* (*alloc_fn)(size_t)
 141 )
 142 { struct ston_ht_header_t header;
 143   ston_ht                 stack_ht, ht;
 144   long                    fpos_start;
 145   size_t                  table_size, alloc_size;
 146   int                     errno_local;
 147   if ((fpos_start = ftell(file)) == -1)
 148     return NULL;
 149   if (fread(&header, sizeof(header), 1, file) != 1)
 150     goto fail_seekback;
 151   table_size = ston_ht32_size(&header);
 152   alloc_size = sizeof(header) + table_size;
 153   stack_ht = (ston_ht) alloca(alloc_size);
 154   memcpy(stack_ht, &header, sizeof(header));
 155   if (fread(stack_ht + sizeof(header), table_size, 1, file) != 1)
 156     goto fail_seekback;
 157   if (fseek(file, fpos_start, SEEK_SET) != 0)
 158     return NULL;
 159   ht = (ston_ht) alloc_fn(alloc_size);
 160   if (ht != NULL)
 161     memcpy(ht, stack_ht, alloc_size);
 162   return ht;
 163  fail_seekback:
 164   /* Try to seek the file back to origin without clobbering errno */
 165   errno_local = errno;
 166   fseek(file, fpos_start, SEEK_SET);
 167   errno = errno_local;
 168   return NULL;
 169 }
 170 #endif
 171
 172 /* Returns a pointer to the row of data in the hashtable containing the provided
 173    key, inserts if not found.  Returns NULL on overflow.
 174 */
 175 STON_FUNC
 176 uint32_t* ston_ht32_row
 177 ( struct ston_ht_header_t* ht,
 178   uint32_t                key
 179 )
 180 { uint32_t* row;
 181   uint32_t* row_start = ston_ht32_start(ht);
 182   uint32_t* row_end = ston_ht32_end(ht);
 183   uint16_t  ht_cols = ston_ht_cols(ht);
 184   size_t    row_number = ston_ht_keyrow(ht,key);
 185   uint8_t   looped = 0;
 186   row = row_start + (row_number * ht_cols);
 187  next_row:
 188   if (row[0] != 0)
 189     goto populated;
 190  write_position:
 191   row[0] = key;
 192   return row;
 193  populated:
 194   if (row[0] == key)
 195     goto write_position;
 196   if (row < row_end)
 197     row += ht_cols;
 198   else if (looped)
 199       return NULL;
 200   else
 201     { looped++;
 202       row = row_start;
 203     }
 204   goto next_row;
 205 }
 206
 207 /* Inserts a value into a hashtable at the specified column, returning the
 208    previous value */
 209 STON_FUNC
 210 uint32_t ston_ht32_insert
 211 ( struct ston_ht_header_t* ht,
 212   uint32_t                key,
 213   uint16_t                column,
 214   uint32_t                value
 215 )
 216 { uint32_t* value_location, old_value;
 217   value_location = ston_ht32_entry(ht,key,column);
 218   old_value = *value_location;
 219   *value_location = value;
 220   return old_value;
 221 }
 222
 223 #ifndef STON_DHT_SIZE
 224 #define STON_DHT_SIZE 4096
 225 #endif
 226
 227 /* STON Dynamic Hashtable Structure
 228    A dynamic form of the generic hashtable implementation above which uses
 229    external allocation.
 230 */
 231 typedef struct ston_dht_header_t
 232 { uint16_t  ht_columns;
 233   uint8_t   ht_2pow, ht_flags;
 234   void*     (*ht_alloc)(size_t);
 235   void      (*ht_free)(void*);
 236   void**    page_head;
 237 }* ston_dht;
 238 #define   STON_DHT_HEADERSIZE (sizeof(struct ston_dht_header_t))
 239
 240 STON_FUNC
 241 ston_dht  ston_dht32_create(uint16_t,size_t,uint8_t,void*(*)(size_t),void(*)(void*));
 242 STON_FUNC
 243 uint32_t* ston_dht32_row(ston_dht,uint32_t);
 244 STON_FUNC
 245 uint32_t  ston_dht32_insert(ston_dht,uint32_t,uint16_t,uint32_t);
 246 STON_FUNC
 247 void      ston_dht32_free(ston_dht);
 248
 249 #define   ston_dht32_new(_COL,_N,_F,_FN)         ston_dht32_create(_COLS,ston_up2pow(_N << 1),_F,_FN)
 250 #define   ston_dht32_entry(_HT,_KEY,_COL)        (ston_dht32_row(_HT,_KEY) + _COL)
 251 #define   ston_dht32_insertx(_HT,_KEY,_COL,_VAL) *ston_dht32_col(_HT,_KEY,_COL) = _VAL
 252 #define   ston_dht_size(_HT)           (ston_ht_size(_HT))
 253 #define   ston_dht_rows(_HT)           (ston_ht_rows(_HT))
 254 #define   ston_dht_cols(_HT)           (ston_ht_cols(_HT))
 255 #define   ston_dht_keyrow(_HT,_KEY)    (ston_ht_keyrow(_HT,_KEY))
 256 #define   ston_dht_pagestart(_HT)      ((void**)(((uint8_t*)(_HT)) + STON_DHT_HEADERSIZE))
 257 #define   ston_dht_pagehead(_HT)       ((_HT)->page_head)
 258 #define   ston_dht_pagemax(_HT)        ((void**)((uint8_t*)(_HT) + STON_DHT_SIZE - sizeof(void**)))
 259 #define   ston_dht_start(_HT,_DEPTH)   ((uint8_t*)*(ston_dht_pagestart(_HT) + _DEPTH))
 260 #define   ston_dht32_start(_HT,_DEPTH) ((uint32_t*)ston_dht_start(_HT,_DEPTH))
 261 #define   ston_dht32_end(_HT,_DEPTH)   (ston_ht32_start(_HT,_DEPTH) + ston_ht_size(_HT))
 262 #define   ston_dht32_size(_HT)         (ston_dht_size(_HT) * sizeof(uint32_t))
 263 #define   ston_dht32_pagepush(_HT)     ((*(++((_HT)->page_head)) = (_HT)->ht_alloc(ston_dht32_size(_HT))))
 264 #define   ston_dht32_pagepop(_HT)      ((_HT)->ht_free((_HT)->page_head--))
 265
 266 /* Creates a new bucketted hash table, provided a memory allocation function
 267    that takes a single size_t bytes, a memory free function, a column count, and
 268    a row count which determines the size of the buckets.
 269 */
 270 STON_FUNC
 271 ston_dht ston_dht32_create
 272 ( uint16_t ht_columns,
 273   size_t   ht_rows,
 274   uint8_t  ht_flags,
 275   void*   (*ht_alloc)(size_t),
 276   void    (*ht_free)(void*)
 277 )
 278 { size_t   ht_size = ht_rows * ht_columns * sizeof(uint32_t);
 279   ston_dht ht = (ston_dht) ht_alloc(STON_DHT_SIZE);
 280   if (ht != NULL)
 281     { for (ht->ht_2pow = 0; ht_size; ht->ht_2pow++)
 282         ht_size = ht_size >> 1;
 283       ht->ht_columns = ht_columns;
 284       ht->ht_flags = ht_flags;
 285       ht->ht_alloc = ht_alloc;
 286       ht->ht_free = ht_free;
 287       ht->page_head = ston_dht_pagestart(ht);
 288       if ((*(ht->page_head) = ht->ht_alloc(ston_dht_size(ht))) == NULL)
 289         ht_free(ht);
 290     }
 291   return ht;
 292 }
 293
 294 /* Returns a pointer to the row of data in the hashtable containing the provided
 295    key, inserts if not found.  Returns NULL on overflow.
 296 */
 297 STON_FUNC
 298 uint32_t* ston_dht32_row
 299 ( struct ston_dht_header_t* ht,
 300   uint32_t                  key
 301 )
 302 { uint16_t   ht_cols = ston_dht_cols(ht);
 303   size_t     row_number = ston_dht_keyrow(ht,key);
 304   uint32_t** page = (uint32_t**)ston_dht_pagestart(ht);
 305   uint32_t** pagemax = (uint32_t**)ston_dht_pagemax(ht);
 306   uint8_t    loop_x = 0;
 307   uint8_t    loop_y = 0;
 308   uint32_t*  row,* row_end;
 309  next_page:
 310   row = *page + (row_number * ht_cols);
 311   row_end = *page + (ston_dht_size(ht) - 1);
 312  next_row:
 313   if (row[0] != 0)
 314     goto populated;
 315  write_position:
 316   row[0] = key;
 317   return row;
 318  populated:
 319   if (row[0] == key)
 320     goto write_position;
 321   if (!loop_x)
 322     { if (page < pagemax)
 323         { if (page == (uint32_t**)ston_dht_pagehead(ht))
 324             if (ston_dht32_pagepush(ht) == NULL)
 325               { ston_dht32_free(ht);
 326                 return NULL;
 327               }
 328           ++page;
 329           goto next_row;
 330         }
 331       loop_x = 1;
 332       row_number = (row_number + 1) % ston_dht_rows(ht);
 333       page = (uint32_t**)ston_dht_pagestart(ht);
 334       goto next_row;
 335     }
 336   if (row < row_end)
 337     { row += ht_cols;
 338       goto next_row;
 339     }
 340   else if (!loop_y)
 341     { loop_y = 1;
 342       row = *page;
 343       goto next_row;
 344     }
 345   if (page < pagemax)
 346     { loop_y = 0;
 347       page++;
 348       goto next_page;
 349     }
 350   return NULL;
 351 }
 352
 353 /* Inserts a value into a hashtable at the specified column, returning the
 354    previous value */
 355 STON_FUNC
 356 uint32_t ston_dht32_insert
 357 ( struct ston_dht_header_t* ht,
 358   uint32_t                  key,
 359   uint16_t                  column,
 360   uint32_t                  value
 361 )
 362 { uint32_t* value_location, old_value;
 363   value_location = ston_dht32_entry(ht,key,column);
 364   old_value = *value_location;
 365   *value_location = value;
 366   return old_value;
 367 }
 368
 369 /* Free the dynamic hash table */
 370 STON_FUNC
 371 void ston_dht32_free
 372 ( struct ston_dht_header_t* ht )
 373 { void (*ht_free)(void*) = ht->ht_free;
 374   if (ht_free != NULL)
 375     { while (ht->page_head >= ston_dht_pagestart(ht))
 376         ht_free(ht->page_head--);
 377       ht_free(ht);
 378     }
 379 }
 380
 381 #endif //_STON_HT_H_