comments updated

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

diff --git a/ston/ston_ht.h b/ston/ston_ht.h
index e97a589..6ab03e7 100644 (file)
--- a/ston/ston_ht.h
+++ b/ston/ston_ht.h
@@ -52,6 +52,9 @@
 STON_FUNC_STATIC
 STON_FUNC_NOINLINE
 ston_ht   ston_ht32_fread(FILE*,long,void*(*)(size_t));
 STON_FUNC_STATIC
 STON_FUNC_NOINLINE
 ston_ht   ston_ht32_fread(FILE*,long,void*(*)(size_t));

+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
+size_t    ston_ht32_fwrite(ston_ht,FILE*,long);

 #else
 #include <stddef.h>
 #endif //STON_HT_FREAD
 #else
 #include <stddef.h>
 #endif //STON_HT_FREAD


@@ -150,6 +153,8 @@ ston_ht ston_ht32_create
    entire structure is verified, and all file operations are finished.  
    Returns NULL with properly set errno on failure.
 */
    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,
 ston_ht ston_ht32_fread
 ( FILE* file,
   long  fpos,


@@ -183,6 +188,26 @@ ston_ht ston_ht32_fread
   errno = errno_local;
   return NULL;
 }
   errno = errno_local;
   return NULL;
 }

+
+/* Writes a 32-bit hash table from memory into a file at fpos.  Returns the
+   number of bytes written to the file, errno is set on error. */
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
+size_t ston_ht32_fwrite
+( struct ston_ht_header_t* ht,
+  FILE*                    file,
+  long                     fpos
+)
+{ size_t bytes_written;
+  long   fpos_start;
+  if ((fpos_start = ftell(file)) == NULL
+      || fseek(file, fpos, SEEK_SET) == 0
+      || (bytes_written = fwrite(file, 1, sizeof(ston_ht_h), file)) < sizeof(ston_ht_h)
+      || (bytes_written += fwrite(file, 1, ston_ht32_bytes(ht), file)) < (sizeof(ston_ht_h) + ston_ht32_bytes(ht))
+      || fseek(file, fpos_start, SEEK_SET) == 0)
+    return 0;
+  return bytes_written;
+}

 #endif
 
 /* Returns a pointer to the row of data in the hashtable containing the provided
 #endif
 
 /* Returns a pointer to the row of data in the hashtable containing the provided


@@ -260,160 +285,181 @@ ston_ht32_insertx
 }
 
 
 }
 
 

-#ifndef STON_DHT_SIZE
-#define STON_DHT_SIZE 4096
-#endif
-

 /* STON Dynamic Hashtable Structure
    A dynamic form of the generic hashtable implementation above which uses
    external allocation.
 */
 typedef struct ston_dht_header_t
 /* STON Dynamic Hashtable Structure
    A dynamic form of the generic hashtable implementation above which uses
    external allocation.
 */
 typedef struct ston_dht_header_t

-{ uint16_t  columns;
-  uint8_t   unit_bytes;
-  uint8_t   start_depth;
+{ uint16_t  val_bytes;
+  uint8_t   key_bytes;
+  uint8_t   flags;

 }ston_dht_h;
 
 typedef struct ston_dht_t
 { ston_dht_h header;
 }ston_dht_h;
 
 typedef struct ston_dht_t
 { ston_dht_h header;

-  void*      pages[sizeof(void*) * 8];

   void*      (*ht_alloc)(size_t);
   void       (*ht_free)(void*);
   void*      (*ht_alloc)(size_t);
   void       (*ht_free)(void*);

+  void       (*ht_iter)(void*,void*,void*);
+  void*      ht_user_data;
+  void*      bucket_root;
+  size_t     rowsize, bucketsize;

 }* ston_dht;
 }* ston_dht;

-
-STON_FUNC
-ston_dht  ston_dht_create(uint16_t,uint8_t,uint8_t,void*(*)(size_t),void(*)(void*));
+/* STON DHT API
+   Primary functions for creating hashtables, retrieving pointers to values,
+   iterating over all keys and values, and destroying hashtables. */

 STON_FUNC
 STON_FUNC

-uint32_t* ston_dht32_row(ston_dht,uint32_t);
+ston_dht  ston_dht_new(uint16_t,uint8_t,void*(*)(size_t),void(*)(void*));

 STON_FUNC
 STON_FUNC

-uint32_t  ston_dht32_insert(ston_dht,uint32_t,uint16_t,uint32_t);
-STON_FUNC
-size_t    ston_dht32_insertx(ston_dht,uint32_t,uint32_t*,uint16_t,size_t);
+void*     ston_dht_val(ston_dht,void*);

 STON_FUNC
 ston_dht  ston_dht_free(ston_dht);
 STON_FUNC
 ston_dht  ston_dht_free(ston_dht);

+STON_FUNC
+void      ston_dht_iterate(ston_dht,void(*)(void*,void*,void*),void*);
+/* Recursive functions intended to be called by other functions, above */
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
+void      ston_dht_free_bucket(ston_dht,void*);
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
+void      ston_dht_iterate_r(ston_dht,void*);
+// Compatibility macros - Deprecated
+#define ston_dht32_new(_COL,_ALOC,_FRE) (ston_dht_new(4 * _COL, 4, _ALOC, _FRE))
+#define ston_dht32_row(_HT,_K) ((uint32_t*)((uint8_t*)ston_dht_val(_HT,&(_K)) - 4))
+#define ston_dht32_insertx(_HT,_K,_VP,_OFFS,_N) \
+  memcpy((uint32_t*)((uint8_t*)ston_dht_val(_HT,&(_K)) + ((_OFFS - 1) * 4)),_VP,_N * 4)

 
 

-#define ston_dht_units(_HT,_DEPTH)           ((_HT)->header.columns << _DEPTH)
-#define ston_dht_bytes(_HT,_DEPTH)           (ston_dht_units(_HT,_DEPTH) * (_HT)->header.unit_bytes)
-#define ston_dht_new(_COL,_ALOC,_FRE)        (ston_dht_create(_COL,3,sizeof(int),_ALOC,_FRE))
-#define ston_dht_sized(_COL,_N,_ALOC,_FRE)   (ston_dht_create(_COL,ston_trailing0(ston_up2pow(_N),sizeof(int),_ALOC,_FRE)))
-#define ston_dht32_entry(_HT,_KEY,_COL)      (ston_dht32_row(_HT,_KEY) + _COL)
-#define ston_dht32_new(_COL,_ALOC,_FRE)      (ston_dht_create(_COL,0,sizeof(uint32_t),_ALOC,_FRE))
-#define ston_dht32_sized(_COL,_N,_ALOC,_FRE) (ston_dht_create(_COL,ston_trailing0(ston_up2pow(_N)),sizeof(uint32_t),_ALOC,_FRE))
-
-
-/* Creates a new bucketted hash table, provided a memory allocation function
-   that takes a single size_t bytes, a memory free function, a column count, and
-   a row count which determines the size of the buckets.
-*/
+/* New dynamic hashtable, provided value bytes, key bytes, allocator function,
+   and free function.  Value bytes and key bytes are respectively constrained to
+   uint16 and uint8 so they can be aligned to hashtables encoded for
+   streaming */

 STON_FUNC
 STON_FUNC

-ston_dht ston_dht_create
-( uint16_t columns,
-  uint8_t  start_depth,
-  uint8_t  unit_bytes,
+ston_dht ston_dht_new
+( uint16_t val_bytes,
+  uint8_t  key_bytes,

   void*    (*ht_alloc)(size_t),
   void     (*ht_free)(void*)
 )
 { ston_dht ht = (ston_dht) ht_alloc(sizeof(struct ston_dht_t));
   if (ht != NULL)
   void*    (*ht_alloc)(size_t),
   void     (*ht_free)(void*)
 )
 { ston_dht ht = (ston_dht) ht_alloc(sizeof(struct ston_dht_t));
   if (ht != NULL)

-    { ht->header.columns = columns;
-      ht->header.start_depth = start_depth;
-      ht->header.unit_bytes = unit_bytes;
-      memset(ht->pages, 0, sizeof(void*) * sizeof(void*) * 8);
-      ht->pages[start_depth] = ht_alloc(ston_dht_bytes(ht, start_depth));
+    { ht->header.val_bytes = val_bytes;
+      ht->header.key_bytes = key_bytes;
+      ht->rowsize = sizeof(void*) + key_bytes + val_bytes;
+      ht->bucketsize = ht->rowsize * 0x100;

       ht->ht_alloc = ht_alloc;
       ht->ht_free = ht_free;
       ht->ht_alloc = ht_alloc;
       ht->ht_free = ht_free;

-      if (ht->pages[start_depth] == NULL && ht_free != NULL)
+      ht->bucket_root = ht_alloc(ht->bucketsize);
+      if (ht->bucket_root == NULL && ht_free != NULL)

        ht_free(ht);
       else
        ht_free(ht);
       else

-       memset(ht->pages[start_depth], 0, ston_dht_bytes(ht, start_depth));
+       memset((ht->bucket_root), 0, ht->bucketsize);

     }
   return ht;
 }
 
     }
   return ht;
 }
 

-/* Returns a pointer to the row of data in the hashtable containing the provided
-   key, inserts if not found.  Returns NULL on overflow.
-*/
+
+/* Returns a pointer to the value in the hashtable matching the provided key,
+   inserting if not found, or NULL if a memory error occurs */

 STON_FUNC
 STON_FUNC

-uint32_t* ston_dht32_row
+void* ston_dht_val

 ( struct ston_dht_t* ht,
 ( struct ston_dht_t* ht,

-  uint32_t           key
+  void*              key

 )
 )

-{ uint16_t columns = ht->header.columns;
-  uint8_t  depth = ht->header.start_depth;
-  uint32_t mask = ((0x1 << depth) - 1) >> 1;
-  void* page;
-  uint32_t* row;
-  uint32_t  row_key;
- next_page:
-  if (ht->pages[depth] == NULL)
-    { ht->pages[depth] = ht->ht_alloc(ston_dht_bytes(ht, depth));
-      if (ht->pages[depth] == NULL)
-       return NULL;
-      memset(ht->pages[depth], 0, ston_dht_bytes(ht, depth));
+{ size_t   key_bytes = ht->header.key_bytes;
+  uint8_t* key_byte = (uint8_t*)key;
+  uint8_t* bucket = (uint8_t*)ht->bucket_root;
+  uint8_t** bucketp;
+  uint8_t* row,* a,* b;
+  uint8_t  a_not_empty;
+  size_t   i;
+ next_row:
+  row = bucket + (ht->rowsize * (*key_byte));
+  a = row + sizeof(void*);
+  b = (uint8_t*)key;
+  a_not_empty = 0;
+  for (i = 0; i < key_bytes; i++)
+    { a_not_empty |= a[i];
+      if (a_not_empty && a[i] != b[i])
+       goto next_bucket;

     }
     }

-  page = ht->pages[depth];
-  row = (uint32_t*)page + ((key & mask) * columns);
-  row_key = *row;
-  if (row_key == key || row_key == 0)
-    { row[0] = key;
-      return row;
+  if (!a_not_empty)
+    memcpy(row + sizeof(void*),key,key_bytes);
+  goto done;
+ next_bucket:
+  key_byte++;
+  bucketp = (uint8_t**)row;
+  if (*bucketp == NULL)
+    { if ((*bucketp = ht->ht_alloc(ht->bucketsize)) == NULL)
+       return NULL;
+      else
+       memset(*bucketp,0,ht->bucketsize);

     }
     }

-  depth++;
-  mask = (mask << 1) | 0x1;
-  goto next_page;
+  bucket = *bucketp;
+  goto next_row;
+ done:
+  return (void*) row + sizeof(void*) + key_bytes;

 }
 
 }
 

-/* Inserts a value into a hashtable at the specified column, returning the
-   previous value */
+/* Recursively frees all memory stored in the hashtable, and the hashtable
+   itself */

 STON_FUNC
 STON_FUNC

-uint32_t ston_dht32_insert
+struct ston_dht_t* ston_dht_free
+( struct ston_dht_t* ht )
+{ void (*ht_free)(void*) = ht->ht_free;
+  if (ht_free == NULL)
+    return NULL;
+  ston_dht_free_bucket(ht, ht->bucket_root);
+  ht_free(ht);
+  return ht;
+}
+
+/* Recursive free function for nested buckets */
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
+void ston_dht_free_bucket

 ( struct ston_dht_t* ht,
 ( struct ston_dht_t* ht,

-  uint32_t           key,
-  uint16_t           column,
-  uint32_t           value
+  void*              bucket

 )
 )

-{ uint32_t* value_location, old_value;
-  value_location = ston_dht32_entry(ht,key,column);
-  old_value = *value_location;
-  *value_location = value;
-  return old_value;
+{ void** bucket_cur = (void**)((uint8_t*)bucket);
+  void** bucket_max = (void**)((uint8_t*)bucket_cur + (ht->rowsize * 0x100));
+  while (bucket_cur < bucket_max)
+    { if (*bucket_cur != NULL)
+       ston_dht_free_bucket(ht, *bucket_cur);
+      bucket_cur = (void**)((uint8_t*)bucket_cur + ht->rowsize);
+    }
+  ht->ht_free(bucket);

 }
 
 }
 

-/* Insert multiple values, returning the number of bytes written */
+/* Iterate over each key/value pair and execut 'fn' with key, value and
+   user_data as its arguments.  user_data may be anything, even NULL, and is
+   expected to be referenced inside the body of 'fn' as the third argument of
+   'fn' */

 STON_FUNC
 STON_FUNC

-size_t
-ston_dht32_insertx
+void ston_dht_iterate

 ( struct ston_dht_t* ht,
 ( struct ston_dht_t* ht,

-  uint32_t           key,
-  uint32_t*          data_src,
-  uint16_t           start_column,
-  size_t             units
+  void               (*fn)(void*,void*,void*),
+  void*              user_data

 )
 )

-{ uint32_t* data_row = ston_dht32_row(ht,key);
-  uint32_t* data_limit = data_row + ht->header.columns;
-  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);
+{ ht->ht_iter = fn;
+  ht->ht_user_data = user_data;
+  ston_dht_iterate_r(ht,ht->bucket_root);

 }
 
 }
 

-/* Free the dynamic hash table */
-STON_FUNC
-struct ston_dht_t* ston_dht_free
-( struct ston_dht_t* ht )
-{ void (*ht_free)(void*) = ht->ht_free;
-  uint8_t depth = ht->header.start_depth;
-  void**  pages = ht->pages;
-  if (ht_free != NULL)
-    { while (pages[depth] != NULL)
-       ht_free(pages[depth++]);
-      ht_free(ht);
-      return NULL;
+/* Recursively iterate through the given bucket belonging to hashtable ht */
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
+void ston_dht_iterate_r
+( struct ston_dht_t* ht,
+  void*              bucket
+)
+{ uint8_t* row = (uint8_t*)bucket;
+  uint8_t* row_max = (row + (ht->rowsize * 0x100));
+  while (row < row_max)
+    { if (*(void**)row != NULL)
+       ston_dht_iterate_r(ht, *(void**)row);
+      row += sizeof(void*);
+      ht->ht_iter((void*)row, (void*)(row + ht->header.key_bytes),ht->ht_user_data);
+      row += ht->header.key_bytes + ht->header.val_bytes;

     }
     }

-  return ht;

 }
 
 }
 

-

 #endif //_STON_HT_H_
 #endif //_STON_HT_H_