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 <errno.h>
  51 #include <alloca.h>
  52 STON_FUNC_STATIC
  53 STON_FUNC_NOINLINE
  54 ston_ht   ston_ht32_fread(FILE*,long,void*(*)(size_t));
  55 STON_FUNC_STATIC
  56 STON_FUNC_NOINLINE
  57 size_t    ston_ht32_fwrite(ston_ht,FILE*,long);
  58 #else
  59 #include <stddef.h>
  60 #endif //STON_HT_FREAD
  61 #include <stdint.h>
  62 #include <string.h> //mem*
  63 /* STON Hashtable Structure
  64    Hashtables are stored as dynamically sized two dimensional arrays
  65 */
  66 typedef struct ston_ht_header_t
  67 { uint16_t ht_columns;
  68   uint8_t  ht_2pow, ht_flags;
  69 }ston_ht_h,* ston_ht;
  70
  71 STON_FUNC
  72 uint32_t  ston_up2pow(uint32_t);
  73 STON_FUNC
  74 uint8_t   ston_trailing0(uint32_t);
  75 STON_FUNC
  76 ston_ht   ston_ht32_create(uint16_t,uint8_t,uint8_t,void*(*)(size_t));
  77 STON_FUNC
  78 uint32_t* ston_ht32_row(ston_ht,uint32_t);
  79 STON_FUNC
  80 uint32_t  ston_ht32_insert(ston_ht,uint32_t,uint16_t,uint32_t);
  81 STON_FUNC
  82 size_t    ston_ht32_insertx(ston_ht,uint32_t,uint32_t*,size_t,size_t);
  83
  84 #define   ston_ht32_new(_COL,_N,_F,_FN) (ston_ht32_create(_COL,ston_trailing0(ston_up2pow(_N << 1)),_F,_FN))
  85 #define   ston_ht32_entry(_HT,_KEY,_COL) (ston_ht32_row(_HT,_KEY) + _COL)
  86 #define   ston_ht_size(_HT)            ((_HT)->ht_columns << (_HT)->ht_2pow)
  87 #define   ston_ht_rows(_HT)            (0x1 << (_HT)->ht_2pow)
  88 #define   ston_ht_cols(_HT)            ((_HT)->ht_columns)
  89 #define   ston_ht_start(_HT)           ((uint8_t*)((_HT) + 1))
  90 #define   ston_ht_keyrow(_HT,_KEY)     ((_KEY) & (ston_ht_rows(ht) - 1))
  91 #define   ston_ht32_start(_HT)         ((uint32_t*)ston_ht_start(_HT))
  92 #define   ston_ht32_end(_HT)           (ston_ht32_start(_HT) + ston_ht_size(_HT))
  93 #define   ston_ht32_size(_HT)          (ston_ht_size(_HT) * sizeof(uint32_t))
  94
  95 /** @see http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 */
  96 STON_FUNC
  97 uint32_t ston_up2pow
  98 ( uint32_t val )
  99 { val = (val << 1) - 1;
 100   val |= val >> 1;
 101   val |= val >> 2;
 102   val |= val >> 4;
 103   val |= val >> 8;
 104   val |= val >> 16;
 105   return ++val;
 106 }
 107
 108 /** @see https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel */
 109 STON_FUNC
 110 uint8_t ston_trailing0
 111 ( uint32_t v )
 112 { uint8_t c = 32;
 113   v &= -(int32_t)v;
 114   if (v) c--;
 115   if (v & 0x0000FFFF) c -= 16;
 116   if (v & 0x00FF00FF) c -= 8;
 117   if (v & 0x0F0F0F0F) c -= 4;
 118   if (v & 0x33333333) c -= 2;
 119   if (v & 0x55555555) c -= 1;
 120   return c;
 121 }
 122
 123 /* Creates a new hash table, provided a memory allocation function that takes a
 124    single size_t bytes, a column count, and a row count which determines the
 125    size of the table.
 126
 127    use ston_ht32_new to specify the exact or estimated number of unique keys
 128    held in the table.  With ston_ht32_new, the provided ht_rows is doubled, and
 129    rounded up to the nearest power of two to create a hash table with minimal
 130    collisions.
 131 */
 132 STON_FUNC
 133 ston_ht ston_ht32_create
 134 ( uint16_t ht_columns,
 135   uint8_t  ht_2pow,
 136   uint8_t  ht_flags,
 137   void*    (*alloc_fn)(size_t)
 138 )
 139 { size_t  ht_bytes = (ht_columns << ht_2pow) * sizeof(uint32_t);
 140   ston_ht ht = (ston_ht) alloc_fn(sizeof(ston_ht_h) + ht_bytes);
 141   if (ht != NULL)
 142     { ht->ht_columns = ht_columns;
 143       ht->ht_2pow = ht_2pow;
 144       ht->ht_flags = ht_flags;
 145       memset(ht + 1, 0, ht_bytes);
 146     }
 147   return ht;
 148 }
 149
 150 #ifdef STON_HT_FREAD
 151 /* Reads a 32-bit hash table out of the provided file at the provide fpos, into
 152    a buffer allocated by alloc_fn.  Memory is allocated to the stack until the
 153    entire structure is verified, and all file operations are finished.
 154    Returns NULL with properly set errno on failure.
 155 */
 156 STON_FUNC_STATIC
 157 STON_FUNC_NOINLINE
 158 ston_ht ston_ht32_fread
 159 ( FILE* file,
 160   long  fpos,
 161   void* (*alloc_fn)(size_t)
 162 )
 163 { struct ston_ht_header_t header;
 164   ston_ht                 stack_ht, ht;
 165   long                    fpos_start;
 166   size_t                  table_size, alloc_size;
 167   int                     errno_local;
 168   if ((fpos_start = ftell(file)) == -1)
 169     return NULL;
 170   if (fread(&header, sizeof(header), 1, file) != 1)
 171     goto fail_seekback;
 172   table_size = ston_ht32_size(&header);
 173   alloc_size = sizeof(header) + table_size;
 174   stack_ht = (ston_ht) alloca(alloc_size);
 175   memcpy(stack_ht, &header, sizeof(header));
 176   if (fread(stack_ht + sizeof(header), table_size, 1, file) != 1)
 177     goto fail_seekback;
 178   if (fseek(file, fpos_start, SEEK_SET) != 0)
 179     return NULL;
 180   ht = (ston_ht) alloc_fn(alloc_size);
 181   if (ht != NULL)
 182     memcpy(ht, stack_ht, alloc_size);
 183   return ht;
 184  fail_seekback:
 185   /* Try to seek the file back to origin without clobbering errno */
 186   errno_local = errno;
 187   fseek(file, fpos_start, SEEK_SET);
 188   errno = errno_local;
 189   return NULL;
 190 }
 191
 192 /* Writes a 32-bit hash table from memory into a file at fpos.  Returns the
 193    number of bytes written to the file, errno is set on error. */
 194 STON_FUNC_STATIC
 195 STON_FUNC_NOINLINE
 196 size_t ston_ht32_fwrite
 197 ( struct ston_ht_header_t* ht,
 198   FILE*                    file,
 199   long                     fpos
 200 )
 201 { size_t bytes_written;
 202   long   fpos_start;
 203   if ((fpos_start = ftell(file)) == NULL
 204       || fseek(file, fpos, SEEK_SET) == 0
 205       || (bytes_written = fwrite(file, 1, sizeof(ston_ht_h), file)) < sizeof(ston_ht_h)
 206       || (bytes_written += fwrite(file, 1, ston_ht32_bytes(ht), file)) < (sizeof(ston_ht_h) + ston_ht32_bytes(ht))
 207       || fseek(file, fpos_start, SEEK_SET) == 0)
 208     return 0;
 209   return bytes_written;
 210 }
 211 #endif
 212
 213 /* Returns a pointer to the row of data in the hashtable containing the provided
 214    key, inserts if not found.  Returns NULL on overflow.
 215 */
 216 STON_FUNC
 217 uint32_t* ston_ht32_row
 218 ( struct ston_ht_header_t* ht,
 219   uint32_t                key
 220 )
 221 { uint32_t* row;
 222   uint32_t* row_start = ston_ht32_start(ht);
 223   uint32_t* row_end = ston_ht32_end(ht);
 224   uint16_t  ht_cols = ston_ht_cols(ht);
 225   size_t    row_number = ston_ht_keyrow(ht,key);
 226   uint8_t   looped = 0;
 227   row = row_start + (row_number * ht_cols);
 228  next_row:
 229   if (row[0] != 0)
 230     goto populated;
 231  write_position:
 232   row[0] = key;
 233   return row;
 234  populated:
 235   if (row[0] == key)
 236     goto write_position;
 237   if (row + ht_cols < row_end)
 238     row += ht_cols;
 239   else if (looped)
 240       return NULL;
 241   else
 242     { looped++;
 243       row = row_start;
 244     }
 245   goto next_row;
 246 }
 247
 248 /* Inserts a value into a hashtable at the specified column, returning the
 249    previous value */
 250 STON_FUNC
 251 uint32_t ston_ht32_insert
 252 ( struct ston_ht_header_t* ht,
 253   uint32_t                key,
 254   uint16_t                column,
 255   uint32_t                value
 256 )
 257 { uint32_t* value_location, old_value;
 258   value_location = ston_ht32_entry(ht,key,column);
 259   old_value = *value_location;
 260   *value_location = value;
 261   return old_value;
 262 }
 263
 264 /* Inserts a row of units into a hashtable, starting with the specified column.
 265    Returns the number of elements that were written.  This function will not
 266    overflow internal buffers, but will return a short count (lower than the
 267    provided 'units') when truncation of source data occurs. */
 268 STON_FUNC
 269 size_t
 270 ston_ht32_insertx
 271 ( struct ston_ht_header_t* ht,
 272   uint32_t                 key,
 273   uint32_t*                data_src,
 274   size_t                   start_column,
 275   size_t                   units
 276 )
 277 { uint32_t* data_row = ston_ht32_row(ht,key);
 278   uint32_t* data_limit = data_row + ston_ht_cols(ht);
 279   uint32_t* data_trg = data_row + start_column;
 280   if (data_row == NULL)
 281     return 0;
 282   while (units-- && data_trg < data_limit)
 283     *data_trg++ = *data_src++;
 284   return (size_t)(data_trg - data_row);
 285 }
 286
 287
 288 /* STON Dynamic Hashtable Structure
 289    A dynamic form of the generic hashtable implementation above which uses
 290    external allocation.
 291 */
 292 typedef struct ston_dht_header_t
 293 { uint16_t  val_bytes;
 294   uint8_t   key_bytes;
 295   uint8_t   flags;
 296 }ston_dht_h;
 297
 298 typedef struct ston_dht_t
 299 { ston_dht_h header;
 300   void*      (*ht_alloc)(size_t);
 301   void       (*ht_free)(void*);
 302   void       (*ht_iter)(void*,void*,void*);
 303   void*      ht_user_data;
 304   void*      bucket_root;
 305   size_t     rowsize, bucketsize;
 306 }* ston_dht;
 307
 308 STON_FUNC
 309 ston_dht  ston_dht_new(uint16_t,uint8_t,void*(*)(size_t),void(*)(void*));
 310 STON_FUNC
 311 ston_dht  ston_dht_free(ston_dht);
 312 STON_FUNC
 313 void*     ston_dht_val(ston_dht,void*);
 314 STON_FUNC_STATIC
 315 STON_FUNC_NOINLINE
 316 void      ston_dht_free_bucket(ston_dht,void*);
 317 STON_FUNC
 318 void      ston_dht_iterate(ston_dht,void(*)(void*,void*,void*),void*);
 319 STON_FUNC_STATIC
 320 STON_FUNC_NOINLINE
 321 void      ston_dht_iterate_r(ston_dht,void*);
 322
 323 // Compatibility macros
 324 #define ston_dht32_new(_COL,_ALOC,_FRE) (ston_dht_new(4 * _COL, 4, _ALOC, _FRE))
 325 #define ston_dht32_row(_HT,_K) ((uint32_t*)((uint8_t*)ston_dht_val(_HT,&(_K)) - 4))
 326 #define ston_dht32_insertx(_HT,_K,_VP,_OFFS,_N) \
 327   memcpy((uint32_t*)((uint8_t*)ston_dht_val(_HT,&(_K)) + ((_OFFS - 1) * 4)),_VP,_N * 4)
 328
 329 /* Creates a new bucketted hash table, provided a memory allocation function
 330    that takes a single size_t bytes, a memory free function, a column count, and
 331    a row count which determines the size of the buckets.
 332 */
 333 STON_FUNC
 334 ston_dht ston_dht_new
 335 ( uint16_t val_bytes,
 336   uint8_t  key_bytes,
 337   void*    (*ht_alloc)(size_t),
 338   void     (*ht_free)(void*)
 339 )
 340 { ston_dht ht = (ston_dht) ht_alloc(sizeof(struct ston_dht_t));
 341   if (ht != NULL)
 342     { ht->header.val_bytes = val_bytes;
 343       ht->header.key_bytes = key_bytes;
 344       ht->rowsize = sizeof(void*) + key_bytes + val_bytes;
 345       ht->bucketsize = ht->rowsize * 0x100;
 346       ht->ht_alloc = ht_alloc;
 347       ht->ht_free = ht_free;
 348       ht->bucket_root = ht_alloc(ht->bucketsize);
 349       if (ht->bucket_root == NULL && ht_free != NULL)
 350         ht_free(ht);
 351       else
 352         memset((ht->bucket_root), 0, ht->bucketsize);
 353     }
 354   return ht;
 355 }
 356
 357
 358 /* Returns a pointer to the value in the hashtable matching the provided key,
 359    inserting if not found, or NULL if a memory error occurs */
 360 STON_FUNC
 361 void* ston_dht_val
 362 ( struct ston_dht_t* ht,
 363   void*              key
 364 )
 365 { size_t   key_bytes = ht->header.key_bytes;
 366   uint8_t* key_byte = (uint8_t*)key;
 367   uint8_t* bucket = (uint8_t*)ht->bucket_root;
 368   uint8_t** bucketp;
 369   uint8_t* row,* a,* b;
 370   uint8_t  a_not_empty;
 371   size_t   i;
 372  next_row:
 373   row = bucket + (ht->rowsize * (*key_byte));
 374   a = row + sizeof(void*);
 375   b = (uint8_t*)key;
 376   a_not_empty = 0;
 377   for (i = 0; i < key_bytes; i++)
 378     { a_not_empty |= a[i];
 379       if (a_not_empty && a[i] != b[i])
 380         goto next_bucket;
 381     }
 382   if (!a_not_empty)
 383     memcpy(row + sizeof(void*),key,key_bytes);
 384   goto done;
 385  next_bucket:
 386   key_byte++;
 387   bucketp = (uint8_t**)row;
 388   if (*bucketp == NULL)
 389     { if ((*bucketp = ht->ht_alloc(ht->bucketsize)) == NULL)
 390         return NULL;
 391       else
 392         memset(*bucketp,0,ht->bucketsize);
 393     }
 394   bucket = *bucketp;
 395   goto next_row;
 396  done:
 397   return (void*) row + sizeof(void*) + key_bytes;
 398 }
 399
 400 /* Free the dynamic hash table */
 401 STON_FUNC
 402 struct ston_dht_t* ston_dht_free
 403 ( struct ston_dht_t* ht )
 404 { void (*ht_free)(void*) = ht->ht_free;
 405   if (ht_free == NULL)
 406     return NULL;
 407   ston_dht_free_bucket(ht, ht->bucket_root);
 408   ht_free(ht);
 409   return ht;
 410 }
 411
 412 /* Recursively free pages by lookup */
 413 STON_FUNC_STATIC
 414 STON_FUNC_NOINLINE
 415 void ston_dht_free_bucket
 416 ( struct ston_dht_t* ht,
 417   void*              bucket
 418 )
 419 { void** bucket_cur = (void**)((uint8_t*)bucket);
 420   void** bucket_max = (void**)((uint8_t*)bucket_cur + (ht->rowsize * 0x100));
 421   while (bucket_cur < bucket_max)
 422     { if (*bucket_cur != NULL)
 423         ston_dht_free_bucket(ht, *bucket_cur);
 424       bucket_cur = (void**)((uint8_t*)bucket_cur + ht->rowsize);
 425     }
 426   ht->ht_free(bucket);
 427 }
 428
 429 /* Iterate over each key/value pair and execut 'fn' with key and value as
 430    arguments */
 431 STON_FUNC
 432 void ston_dht_iterate
 433 ( struct ston_dht_t* ht,
 434   void               (*fn)(void*,void*,void*),
 435   void*              user_data
 436 )
 437 { ht->ht_iter = fn;
 438   ht->ht_user_data = user_data;
 439   ston_dht_iterate_r(ht,ht->bucket_root);
 440 }
 441
 442 /* Recursively iterate through the given bucket belonging to hashtable ht */
 443 STON_FUNC_STATIC
 444 STON_FUNC_NOINLINE
 445 void ston_dht_iterate_r
 446 ( struct ston_dht_t* ht,
 447   void*              bucket
 448 )
 449 { uint8_t* row = (uint8_t*)bucket;
 450   uint8_t* row_max = (row + (ht->rowsize * 0x100));
 451   while (row < row_max)
 452     { if (*(void**)row != NULL)
 453         ston_dht_iterate_r(ht, *(void**)row);
 454       row += sizeof(void*);
 455       ht->ht_iter((void*)row, (void*)(row + ht->header.key_bytes),ht->ht_user_data);
 456       row += ht->header.key_bytes + ht->header.val_bytes;
 457     }
 458 }
 459
 460 #endif //_STON_HT_H_