non-dynamic hashtables finished testing

[henge/apc.git] / ston / ston_ht.h

diff --git a/ston/ston_ht.h b/ston/ston_ht.h
index 11454b3..b17e18e 100644 (file)
--- a/ston/ston_ht.h
+++ b/ston/ston_ht.h
@@ -47,7 +47,6 @@
 #endif //STON_FUNC
 #ifdef STON_HT_FREAD
 #include <stdio.h>
-#include <string.h> //memcpy
 #include <errno.h>
 #include <alloca.h>
 STON_FUNC_STATIC
@@ -57,6 +56,7 @@ ston_ht   ston_ht32_fread(FILE*,long,void*(*)(size_t));
 #include <stddef.h>
 #endif //STON_HT_FREAD
 #include <stdint.h>
+#include <string.h> //mem*
 /* STON Hashtable Structure
    Hashtables are stored as dynamically sized two dimensional arrays
 */
@@ -64,23 +64,27 @@ typedef struct ston_ht_header_t
 { uint16_t ht_columns;
   uint8_t  ht_2pow, ht_flags;
 }* ston_ht;
+#define   STON_HT_HEADERSIZE (sizeof(struct ston_ht_header_t))
 
 STON_FUNC
-size_t    ston_up2pow(size_t);
+uint32_t  ston_up2pow(uint32_t);
 STON_FUNC
-ston_ht   ston_ht32_create(uint16_t,size_t,uint8_t,void*(*)(size_t));
+uint8_t   ston_trailing0(uint32_t);
+STON_FUNC
+ston_ht   ston_ht32_create(struct ston_ht_header_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);
+STON_FUNC
+size_t    ston_ht32_insertx(ston_ht,uint32_t,uint32_t*,size_t,size_t);
 
-#define   ston_ht32_new(_COL,_N,_F,_FN) ston_ht32_create(_COL,ston_up2pow(_N << 1),_F,_FN)
-#define   ston_ht32_entry(_HT,_KEY,_COL)        (ston_ht32_row(_HT,_KEY) + _COL)
-#define   ston_ht32_insertx(_HT,_KEY,_COL,_VAL) *ston_ht32_entry(_HT,_KEY,_COL) = _VAL
+#define   ston_ht32_new(_COL,_N,_F,_FN) (ston_ht32_create((struct ston_ht_header_t){_COL,ston_trailing0(ston_up2pow(_N << 1)),_F},_FN))
+#define   ston_ht32_entry(_HT,_KEY,_COL) (ston_ht32_row(_HT,_KEY) + _COL)
 #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_start(_HT)           ((uint8_t*)((_HT) + 1))
 #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_end(_HT)           (ston_ht32_start(_HT) + ston_ht_size(_HT))
@@ -88,8 +92,8 @@ uint32_t  ston_ht32_insert(ston_ht,uint32_t,uint16_t,uint32_t);
 
 /** @see http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 */
 STON_FUNC
-size_t ston_up2pow
-( size_t val )
+uint32_t ston_up2pow
+( uint32_t val )
 { val = (val << 1) - 1;
   val |= val >> 1;
   val |= val >> 2;
@@ -99,6 +103,21 @@ size_t ston_up2pow
   return ++val;
 }
 
+/** @see https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel */
+STON_FUNC
+uint8_t ston_trailing0
+( uint32_t v )
+{ uint8_t c = 32;
+  v &= -(int32_t)v;
+  if (v) c--;
+  if (v & 0x0000FFFF) c -= 16;
+  if (v & 0x00FF00FF) c -= 8;
+  if (v & 0x0F0F0F0F) c -= 4;
+  if (v & 0x33333333) c -= 2;
+  if (v & 0x55555555) c -= 1;
+  return c;
+}
+
 /* 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 determines the
    size of the table.
@@ -110,18 +129,14 @@ size_t ston_up2pow
 */
 STON_FUNC
 ston_ht ston_ht32_create
-( uint16_t ht_columns,
-  size_t   ht_rows,
-  uint8_t  ht_flags,
-  void*    (*alloc_fn)(size_t)
+( struct ston_ht_header_t ht_header,
+  void*                   (*alloc_fn)(size_t)
 )
-{ size_t  ht_size = ht_rows * ht_columns * sizeof(uint32_t);
-  ston_ht ht = (ston_ht) alloc_fn(sizeof(struct ston_ht_header_t) + ht_size);
+{ size_t  ht_bytes = ston_ht32_size(&ht_header);
+  ston_ht ht = (ston_ht) alloc_fn(STON_HT_HEADERSIZE + ht_bytes);
   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;
+    { memcpy(ht,&ht_header,STON_HT_HEADERSIZE);
+      memset(ht + 1, 0, ht_bytes);
     }
   return ht;
 }
@@ -132,8 +147,6 @@ ston_ht ston_ht32_create
    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,
@@ -193,7 +206,7 @@ uint32_t* ston_ht32_row
  populated:
   if (row[0] == key)
     goto write_position;
-  if (row < row_end)
+  if (row + ht_cols < row_end)
     row += ht_cols;
   else if (looped)
       return NULL;
@@ -220,6 +233,30 @@ uint32_t ston_ht32_insert
   return old_value;
 }
 
+/* Inserts a row of units into a hashtable, starting with the specified column.
+   Returns the number of elements that were written.  This function will not
+   overflow internal buffers, but will return a short count (lower than the
+   provided 'units') when truncation of source data occurs. */
+STON_FUNC
+size_t
+ston_ht32_insertx
+( struct ston_ht_header_t* ht,
+  uint32_t                 key,
+  uint32_t*                data_src,
+  size_t                   start_column,
+  size_t                   units
+)
+{ uint32_t* data_row = ston_ht32_row(ht,key);
+  uint32_t* data_limit = data_row + ston_ht_cols(ht);
+  uint32_t* data_trg = data_row + start_column;
+  if (data_row == NULL)
+    return 0;
+  while (units-- && data_trg < data_limit)
+    *data_trg++ = *data_src++;
+  return (size_t)(data_trg - data_row);
+}
+
+
 #ifndef STON_DHT_SIZE
 #define STON_DHT_SIZE 4096
 #endif