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 size_t    ston_ht32_fwrite(ston_ht,FILE*,long);
  56 #else
  57 #include <stddef.h>
  58 #endif //STON_HT_FREAD
  59 #include <stdint.h>
  60 #include <string.h> //mem*
  61 /* STON Hashtable Structure
  62    Hashtables are stored as dynamically sized two dimensional arrays
  63 */
  64 typedef struct ston_ht_header_t
  65 { uint16_t ht_columns;
  66   uint8_t  ht_2pow, ht_flags;
  67 }ston_ht_h,* ston_ht;
  68
  69 STON_FUNC
  70 uint32_t  ston_up2pow(uint32_t);
  71 STON_FUNC
  72 uint8_t   ston_trailing0(uint32_t);
  73 STON_FUNC
  74 ston_ht   ston_ht32_create(uint16_t,uint8_t,uint8_t,void*(*)(size_t));
  75 STON_FUNC
  76 uint32_t* ston_ht32_row(ston_ht,uint32_t);
  77 STON_FUNC
  78 uint32_t  ston_ht32_insert(ston_ht,uint32_t,uint16_t,uint32_t);
  79 STON_FUNC
  80 size_t    ston_ht32_insertx(ston_ht,uint32_t,uint32_t*,size_t,size_t);
  81
  82 #define   ston_ht32_new(_COL,_N,_F,_FN) (ston_ht32_create(_COL,ston_trailing0(ston_up2pow(_N << 1)),_F,_FN))
  83 #define   ston_ht32_entry(_HT,_KEY,_COL) (ston_ht32_row(_HT,_KEY) + _COL)
  84 #define   ston_ht_size(_HT)            ((_HT)->ht_columns << (_HT)->ht_2pow)
  85 #define   ston_ht_rows(_HT)            (0x1 << (_HT)->ht_2pow)
  86 #define   ston_ht_cols(_HT)            ((_HT)->ht_columns)
  87 #define   ston_ht_start(_HT)           ((uint8_t*)((_HT) + 1))
  88 #define   ston_ht_keyrow(_HT,_KEY)     ((_KEY) & (ston_ht_rows(ht) - 1))
  89 #define   ston_ht32_start(_HT)         ((uint32_t*)ston_ht_start(_HT))
  90 #define   ston_ht32_end(_HT)           (ston_ht32_start(_HT) + ston_ht_size(_HT))
  91 #define   ston_ht32_size(_HT)          (ston_ht_size(_HT) * sizeof(uint32_t))
  92
  93 /** @see http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 */
  94 STON_FUNC
  95 uint32_t ston_up2pow
  96 ( uint32_t val )
  97 { val = (val << 1) - 1;
  98   val |= val >> 1;
  99   val |= val >> 2;
 100   val |= val >> 4;
 101   val |= val >> 8;
 102   val |= val >> 16;
 103   return ++val;
 104 }
 105
 106 /** @see https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel */
 107 STON_FUNC
 108 uint8_t ston_trailing0
 109 ( uint32_t v )
 110 { uint8_t c = 32;
 111   v &= -(int32_t)v;
 112   if (v) c--;
 113   if (v & 0x0000FFFF) c -= 16;
 114   if (v & 0x00FF00FF) c -= 8;
 115   if (v & 0x0F0F0F0F) c -= 4;
 116   if (v & 0x33333333) c -= 2;
 117   if (v & 0x55555555) c -= 1;
 118   return c;
 119 }
 120
 121 /* Creates a new hash table, provided a memory allocation function that takes a
 122    single size_t bytes, a column count, and a row count which determines the
 123    size of the table.
 124
 125    use ston_ht32_new to specify the exact or estimated number of unique keys
 126    held in the table.  With ston_ht32_new, the provided ht_rows is doubled, and
 127    rounded up to the nearest power of two to create a hash table with minimal
 128    collisions.
 129 */
 130 STON_FUNC
 131 ston_ht ston_ht32_create
 132 ( uint16_t ht_columns,
 133   uint8_t  ht_2pow,
 134   uint8_t  ht_flags,
 135   void*    (*alloc_fn)(size_t)
 136 )
 137 { size_t  ht_bytes = (ht_columns << ht_2pow) * sizeof(uint32_t);
 138   ston_ht ht = (ston_ht) alloc_fn(sizeof(ston_ht_h) + ht_bytes);
 139   if (ht != NULL)
 140     { ht->ht_columns = ht_columns;
 141       ht->ht_2pow = ht_2pow;
 142       ht->ht_flags = ht_flags;
 143       memset(ht + 1, 0, ht_bytes);
 144     }
 145   return ht;
 146 }
 147
 148 #ifdef STON_HT_FREAD
 149 /* Reads a 32-bit hash table out of the provided file at the provide fpos, into
 150    a buffer allocated by alloc_fn.  Memory is allocated to the stack until the
 151    entire structure is verified, and all file operations are finished.
 152    Returns NULL with properly set errno on failure.
 153 */
 154 ston_ht ston_ht32_fread
 155 ( FILE* file,
 156   long  fpos,
 157   void* (*alloc_fn)(size_t)
 158 )
 159 { struct ston_ht_header_t header;
 160   ston_ht                 stack_ht, ht;
 161   long                    fpos_start;
 162   size_t                  table_size, alloc_size;
 163   int                     errno_local;
 164   if ((fpos_start = ftell(file)) == -1)
 165     return NULL;
 166   if (fread(&header, sizeof(header), 1, file) != 1)
 167     goto fail_seekback;
 168   table_size = ston_ht32_size(&header);
 169   alloc_size = sizeof(header) + table_size;
 170   stack_ht = (ston_ht) alloca(alloc_size);
 171   memcpy(stack_ht, &header, sizeof(header));
 172   if (fread(stack_ht + sizeof(header), table_size, 1, file) != 1)
 173     goto fail_seekback;
 174   if (fseek(file, fpos_start, SEEK_SET) != 0)
 175     return NULL;
 176   ht = (ston_ht) alloc_fn(alloc_size);
 177   if (ht != NULL)
 178     memcpy(ht, stack_ht, alloc_size);
 179   return ht;
 180  fail_seekback:
 181   /* Try to seek the file back to origin without clobbering errno */
 182   errno_local = errno;
 183   fseek(file, fpos_start, SEEK_SET);
 184   errno = errno_local;
 185   return NULL;
 186 }
 187
 188 /* Writes a 32-bit hash table from memory into a file at fpos.  Returns the
 189    number of bytes written to the file, errno is set on error. */
 190 size_t ston_ht32_fwrite
 191 ( struct ston_ht_header_t* ht,
 192   FILE*                    file,
 193   long                     fpos
 194 )
 195 { size_t bytes_written;
 196   long   fpos_start;
 197   if ((fpos_start = ftell(file)) == NULL
 198       || fseek(file, fpos, SEEK_SET) == 0
 199       || (bytes_written = fwrite(file, 1, sizeof(ston_ht_h), file)) < sizeof(ston_ht_h)
 200       || (bytes_written += fwrite(file, 1, ston_ht32_bytes(ht), file)) < (sizeof(ston_ht_h) + ston_ht32_bytes(ht))
 201       || fseek(file, fpos_start, SEEK_SET) == 0)
 202     return 0;
 203   return bytes_written;
 204 }
 205 #endif
 206
 207 /* Returns a pointer to the row of data in the hashtable containing the provided
 208    key, inserts if not found.  Returns NULL on overflow.
 209 */
 210 STON_FUNC
 211 uint32_t* ston_ht32_row
 212 ( struct ston_ht_header_t* ht,
 213   uint32_t                key
 214 )
 215 { uint32_t* row;
 216   uint32_t* row_start = ston_ht32_start(ht);
 217   uint32_t* row_end = ston_ht32_end(ht);
 218   uint16_t  ht_cols = ston_ht_cols(ht);
 219   size_t    row_number = ston_ht_keyrow(ht,key);
 220   uint8_t   looped = 0;
 221   row = row_start + (row_number * ht_cols);
 222  next_row:
 223   if (row[0] != 0)
 224     goto populated;
 225  write_position:
 226   row[0] = key;
 227   return row;
 228  populated:
 229   if (row[0] == key)
 230     goto write_position;
 231   if (row + ht_cols < row_end)
 232     row += ht_cols;
 233   else if (looped)
 234       return NULL;
 235   else
 236     { looped++;
 237       row = row_start;
 238     }
 239   goto next_row;
 240 }
 241
 242 /* Inserts a value into a hashtable at the specified column, returning the
 243    previous value */
 244 STON_FUNC
 245 uint32_t ston_ht32_insert
 246 ( struct ston_ht_header_t* ht,
 247   uint32_t                key,
 248   uint16_t                column,
 249   uint32_t                value
 250 )
 251 { uint32_t* value_location, old_value;
 252   value_location = ston_ht32_entry(ht,key,column);
 253   old_value = *value_location;
 254   *value_location = value;
 255   return old_value;
 256 }
 257
 258 /* Inserts a row of units into a hashtable, starting with the specified column.
 259    Returns the number of elements that were written.  This function will not
 260    overflow internal buffers, but will return a short count (lower than the
 261    provided 'units') when truncation of source data occurs. */
 262 STON_FUNC
 263 size_t
 264 ston_ht32_insertx
 265 ( struct ston_ht_header_t* ht,
 266   uint32_t                 key,
 267   uint32_t*                data_src,
 268   size_t                   start_column,
 269   size_t                   units
 270 )
 271 { uint32_t* data_row = ston_ht32_row(ht,key);
 272   uint32_t* data_limit = data_row + ston_ht_cols(ht);
 273   uint32_t* data_trg = data_row + start_column;
 274   if (data_row == NULL)
 275     return 0;
 276   while (units-- && data_trg < data_limit)
 277     *data_trg++ = *data_src++;
 278   return (size_t)(data_trg - data_row);
 279 }
 280
 281
 282 #ifndef STON_DHT_SIZE
 283 #define STON_DHT_SIZE 4096
 284 #endif
 285
 286 /* STON Dynamic Hashtable Structure
 287    A dynamic form of the generic hashtable implementation above which uses
 288    external allocation.
 289 */
 290 typedef struct ston_dht_header_t
 291 { uint16_t  columns;
 292   uint8_t   unit_bytes;
 293   uint8_t   start_depth;
 294 }ston_dht_h;
 295
 296 typedef struct ston_dht_t
 297 { ston_dht_h header;
 298   void*      pages[sizeof(void*) * 8];
 299   void*      (*ht_alloc)(size_t);
 300   void       (*ht_free)(void*);
 301 }* ston_dht;
 302
 303 STON_FUNC
 304 ston_dht  ston_dht_create(uint16_t,uint8_t,uint8_t,void*(*)(size_t),void(*)(void*));
 305 STON_FUNC
 306 uint32_t* ston_dht32_row(ston_dht,uint32_t);
 307 STON_FUNC
 308 uint32_t  ston_dht32_insert(ston_dht,uint32_t,uint16_t,uint32_t);
 309 STON_FUNC
 310 size_t    ston_dht32_insertx(ston_dht,uint32_t,uint32_t*,uint16_t,size_t);
 311 STON_FUNC
 312 ston_dht  ston_dht_free(ston_dht);
 313
 314 #define ston_dht_units(_HT,_DEPTH)           ((_HT)->header.columns << _DEPTH)
 315 #define ston_dht_bytes(_HT,_DEPTH)           (ston_dht_units(_HT,_DEPTH) * (_HT)->header.unit_bytes)
 316 #define ston_dht_new(_COL,_ALOC,_FRE)        (ston_dht_create(_COL,3,sizeof(int),_ALOC,_FRE))
 317 #define ston_dht_sized(_COL,_N,_ALOC,_FRE)   (ston_dht_create(_COL,ston_trailing0(ston_up2pow(_N),sizeof(int),_ALOC,_FRE)))
 318 #define ston_dht32_entry(_HT,_KEY,_COL)      (ston_dht32_row(_HT,_KEY) + _COL)
 319 #define ston_dht32_new(_COL,_ALOC,_FRE)      (ston_dht_create(_COL,0,sizeof(uint32_t),_ALOC,_FRE))
 320 #define ston_dht32_sized(_COL,_N,_ALOC,_FRE) (ston_dht_create(_COL,ston_trailing0(ston_up2pow(_N)),sizeof(uint32_t),_ALOC,_FRE))
 321
 322
 323 /* Creates a new bucketted hash table, provided a memory allocation function
 324    that takes a single size_t bytes, a memory free function, a column count, and
 325    a row count which determines the size of the buckets.
 326 */
 327 STON_FUNC
 328 ston_dht ston_dht_create
 329 ( uint16_t columns,
 330   uint8_t  start_depth,
 331   uint8_t  unit_bytes,
 332   void*    (*ht_alloc)(size_t),
 333   void     (*ht_free)(void*)
 334 )
 335 { ston_dht ht = (ston_dht) ht_alloc(sizeof(struct ston_dht_t));
 336   if (ht != NULL)
 337     { ht->header.columns = columns;
 338       ht->header.start_depth = start_depth;
 339       ht->header.unit_bytes = unit_bytes;
 340       memset(ht->pages, 0, sizeof(void*) * sizeof(void*) * 8);
 341       ht->pages[start_depth] = ht_alloc(ston_dht_bytes(ht, start_depth));
 342       ht->ht_alloc = ht_alloc;
 343       ht->ht_free = ht_free;
 344       if (ht->pages[start_depth] == NULL && ht_free != NULL)
 345         ht_free(ht);
 346       else
 347         memset(ht->pages[start_depth], 0, ston_dht_bytes(ht, start_depth));
 348     }
 349   return ht;
 350 }
 351
 352 /* Returns a pointer to the row of data in the hashtable containing the provided
 353    key, inserts if not found.  Returns NULL on overflow.
 354 */
 355 STON_FUNC
 356 uint32_t* ston_dht32_row
 357 ( struct ston_dht_t* ht,
 358   uint32_t           key
 359 )
 360 { uint16_t columns = ht->header.columns;
 361   uint8_t  depth = ht->header.start_depth;
 362   uint32_t mask = ((0x1 << depth) - 1) >> 1;
 363   void* page;
 364   uint32_t* row;
 365   uint32_t  row_key;
 366  next_page:
 367   if (ht->pages[depth] == NULL)
 368     { ht->pages[depth] = ht->ht_alloc(ston_dht_bytes(ht, depth));
 369       if (ht->pages[depth] == NULL)
 370         return NULL;
 371       memset(ht->pages[depth], 0, ston_dht_bytes(ht, depth));
 372     }
 373   page = ht->pages[depth];
 374   row = (uint32_t*)page + ((key & mask) * columns);
 375   row_key = *row;
 376   if (row_key == key || row_key == 0)
 377     { row[0] = key;
 378       return row;
 379     }
 380   depth++;
 381   mask = (mask << 1) | 0x1;
 382   goto next_page;
 383 }
 384
 385 /* Inserts a value into a hashtable at the specified column, returning the
 386    previous value */
 387 STON_FUNC
 388 uint32_t ston_dht32_insert
 389 ( struct ston_dht_t* ht,
 390   uint32_t           key,
 391   uint16_t           column,
 392   uint32_t           value
 393 )
 394 { uint32_t* value_location, old_value;
 395   value_location = ston_dht32_entry(ht,key,column);
 396   old_value = *value_location;
 397   *value_location = value;
 398   return old_value;
 399 }
 400
 401 /* Insert multiple values, returning the number of bytes written */
 402 STON_FUNC
 403 size_t
 404 ston_dht32_insertx
 405 ( struct ston_dht_t* ht,
 406   uint32_t           key,
 407   uint32_t*          data_src,
 408   uint16_t           start_column,
 409   size_t             units
 410 )
 411 { uint32_t* data_row = ston_dht32_row(ht,key);
 412   uint32_t* data_limit = data_row + ht->header.columns;
 413   uint32_t* data_trg = data_row + start_column;
 414   if (data_row == NULL)
 415     return 0;
 416   while (units-- && data_trg < data_limit)
 417     *data_trg++ = *data_src++;
 418   return (size_t)(data_trg - data_row);
 419 }
 420
 421 /* Free the dynamic hash table */
 422 STON_FUNC
 423 struct ston_dht_t* ston_dht_free
 424 ( struct ston_dht_t* ht )
 425 { void (*ht_free)(void*) = ht->ht_free;
 426   uint8_t depth = ht->header.start_depth;
 427   void**  pages = ht->pages;
 428   if (ht_free != NULL)
 429     { while (pages[depth] != NULL)
 430         ht_free(pages[depth++]);
 431       ht_free(ht);
 432       return NULL;
 433     }
 434   return ht;
 435 }
 436
 437 /********************************************************************************
 438 *********************************************************************************
 439 *********************************************************************************
 440 ********************************************************************************/
 441 typedef struct ston_dht2_header_t
 442 { uint16_t  val_bytes;
 443   uint8_t   key_bytes;
 444   uint8_t   flags;
 445 }ston_dht2_h;
 446
 447 typedef struct ston_dht2_bucket_t
 448 { uint8_t  depth;
 449   void*    page;
 450   uint32_t count;
 451 }ston_dht2_bucket_h,* ston_dht2_bucket;
 452
 453 #define STON_DHT_BUCKETS_SIZE (sizeof(void*) * 8)
 454 typedef struct ston_dht2_t
 455 { ston_dht2_h        header;
 456   ston_dht2_bucket_h buckets[1 + STON_DHT_BUCKETS_SIZE];
 457   ston_dht2_bucket   bsp;
 458   uint32_t           row_bytes;
 459   uint8_t            buckets_len;
 460   void*              (*ht_alloc)(size_t);
 461   void               (*ht_free)(void*);
 462 }* ston_dht2;
 463
 464 STON_FUNC
 465 ston_dht2  ston_dht2_create(uint16_t,uint8_t,void*(*)(size_t),void(*)(void*));
 466 STON_FUNC
 467 uint32_t* ston_dht232_row(ston_dht2,uint32_t);
 468 STON_FUNC
 469 uint32_t  ston_dht232_insert(ston_dht2,uint32_t,uint16_t,uint32_t);
 470 STON_FUNC
 471 size_t    ston_dht232_insertx(ston_dht2,uint32_t,uint32_t*,uint16_t,size_t);
 472 STON_FUNC
 473 ston_dht2  ston_dht2_free(ston_dht2);
 474
 475 #define ston_dht2_bytes(_HT,_DEPTH)      ((_HT)->row_bytes << (_DEPTH))
 476 #define ston_dht2_new(_COL,_ALOC,_FRE)   (ston_dht2_create(_COL,sizeof(int),_ALOC,_FRE))
 477 #define ston_dht232_new(_COL,_ALOC,_FRE) (ston_dht2_create(_COL,sizeof(uint32_t),_ALOC,_FRE))
 478 #define ston_dht232_entry(_HT,_KEY,_COL) (ston_dht232_row(_HT,_KEY) + _COL)
 479
 480
 481 /* Creates a new bucketted hash table, provided a memory allocation function
 482    that takes a single size_t bytes, a memory free function, a column count, and
 483    a row count which determines the size of the buckets.
 484 */
 485 static ston_dht2_bucket_h dummy_bucket = { (uint8_t)-1, NULL, (uint32_t)-1 };
 486
 487 STON_FUNC
 488 ston_dht2 ston_dht2_create
 489 ( uint16_t val_bytes,
 490   uint8_t  key_bytes,
 491   void*    (*ht_alloc)(size_t),
 492   void     (*ht_free)(void*)
 493 )
 494 { ston_dht2 ht = (ston_dht2) ht_alloc(sizeof(struct ston_dht2_t));
 495   if (ht != NULL)
 496     { ht->header.val_bytes = val_bytes;
 497       ht->header.key_bytes = key_bytes;
 498       ht->row_bytes = val_bytes + key_bytes;
 499       ht->ht_alloc = ht_alloc;
 500       ht->ht_free = ht_free;
 501       size_t i;
 502       for (i = 0; i <= STON_DHT_BUCKETS_SIZE; i++)
 503         ht->buckets[i] = dummy_bucket;
 504       ht->bsp = ht->buckets + STON_DHT_BUCKETS_SIZE - 1;
 505       ht->bsp->page = ht_alloc(ston_dht2_bytes(ht, 4));
 506       if (ht->bsp->page == NULL && ht_free != NULL)
 507         ht_free(ht);
 508       else
 509         { memset((ht->bsp->page), 0, ston_dht2_bytes(ht,4));
 510           ht->bsp->depth = 4;
 511           ht->bsp->count = 0;
 512           ht->buckets_len = 1;
 513         }
 514     }
 515   return ht;
 516 }
 517
 518
 519 /* Returns a pointer to the row of data in the hashtable containing the provided
 520    key, inserting if not found, or NULL if a memory error occurs */
 521 STON_FUNC
 522 uint32_t* ston_dht232_row
 523 ( struct ston_dht2_t* ht,
 524   uint32_t            key
 525 )
 526 { int8_t    bucket_no = (int8_t)ht->buckets_len - 1;
 527   uint32_t* row, row_key, mask;
 528   size_t    bytes;
 529   int8_t    zero_bucket = (int8_t)-1;
 530   ston_dht2_bucket   bsp = ht->bsp;
 531   ston_dht2_bucket_h bucket;
 532  next_bucket:
 533   bucket = bsp[bucket_no];
 534   /* Find until out of allocated pages, then insert at last empty bucket position */
 535   if (bucket.page == NULL)
 536     { if (zero_bucket != (int8_t)-1)
 537         { bucket = bsp[zero_bucket];
 538           mask = (0x1 << bucket.depth) - 1;
 539           row = (uint32_t*)bucket.page + (key & mask);
 540           *row = key;
 541           bucket.count++;
 542           /* Swap the buckets up a level if the count has exceeded its parent's count */
 543           if (bucket.count > bsp[zero_bucket + 1].count)
 544             { bsp[zero_bucket] = bsp[zero_bucket + 1];
 545               bsp[zero_bucket + 1] = bucket;
 546             }
 547           else
 548             bsp[zero_bucket].count = bucket.count;
 549           return row;
 550         }
 551       /* No buckets with a slot, shift the key right by depth, try again add a new bucket */
 552       bsp--;
 553       bucket.depth = 4 + (ht->buckets_len >> 1);
 554       bucket.count = 1;
 555       bytes = ston_dht2_bytes(ht,bucket.depth);
 556       if ((bucket.page = ht->ht_alloc(bytes)) == NULL)
 557         { printf("Failed to allocate %lu bytes, bucket %i at with len %i\n",
 558                  bytes, bucket_no, ht->buckets_len);
 559           return NULL;
 560         }
 561       memset(bucket.page,0,bytes);
 562       *bsp = bucket;
 563       ht->bsp = bsp;
 564       ht->buckets_len++;
 565       mask = (0x1 << bucket.depth) - 1;
 566       row = (uint32_t*)bucket.page + (key & mask);
 567       *row = key;
 568       return row;
 569     }
 570   /* Compute mask, and use it to find the row in the page */
 571   mask = (0x1 << bucket.depth) - 1;
 572   row = (uint32_t*)bucket.page + (key & mask);
 573   /* Look at the key at row[0], branch */
 574   row_key = *row;
 575   if (row_key == key)
 576     return row;
 577   if (row_key == 0)
 578     zero_bucket = bucket_no;
 579   bucket_no--;
 580   goto next_bucket;
 581 }
 582
 583 /* Inserts a value into a hashtable at the specified column, returning the
 584    previous value */
 585 STON_FUNC
 586 uint32_t ston_dht232_insert
 587 ( struct ston_dht2_t* ht,
 588   uint32_t           key,
 589   uint16_t           column,
 590   uint32_t           value
 591 )
 592 { uint32_t* value_location, old_value;
 593   value_location = ston_dht232_entry(ht,key,column);
 594   old_value = *value_location;
 595   *value_location = value;
 596   return old_value;
 597 }
 598
 599 /* Insert multiple values, returning the number of bytes written */
 600 STON_FUNC
 601 size_t
 602 ston_dht232_insertx
 603 ( struct ston_dht2_t* ht,
 604   uint32_t           key,
 605   uint32_t*          data_src,
 606   uint16_t           start_column,
 607   size_t             units
 608 )
 609 { uint32_t* data_row = ston_dht232_row(ht,key);
 610   uint32_t* data_limit = data_row + ht->row_bytes;
 611   uint32_t* data_trg = data_row + start_column;
 612   if (data_row == NULL)
 613     return 0;
 614   while (units-- && data_trg < data_limit)
 615     *data_trg++ = *data_src++;
 616   return (size_t)(data_trg - data_row);
 617 }
 618
 619 /* Free the dynamic hash table */
 620 STON_FUNC
 621 struct ston_dht2_t* ston_dht2_free
 622 ( struct ston_dht2_t* ht )
 623 { void (*ht_free)(void*) = ht->ht_free;
 624   uint8_t bucket = ht->buckets_len;
 625   if (ht_free != NULL)
 626     { while (bucket--)
 627         ht_free(ht->buckets[bucket].page);
 628       ht_free(ht);
 629       return NULL;
 630     }
 631   return ht;
 632 }
 633
 634
 635 #endif //_STON_HT_H_