comments updated

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

diff --git a/ston/ston_ht.h b/ston/ston_ht.h
index 2d9cb79..6ab03e7 100644 (file)
--- a/ston/ston_ht.h
+++ b/ston/ston_ht.h
@@ -296,37 +296,42 @@ typedef struct ston_dht_header_t
 }ston_dht_h;
 
 typedef struct ston_dht_t
-{ ston_dht_h        header;
-  void*              (*ht_alloc)(size_t);
-  void               (*ht_free)(void*);
-  void*              bucket_root;
-  size_t             rowsize, bucketsize;
+{ ston_dht_h header;
+  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 API
+   Primary functions for creating hashtables, retrieving pointers to values,
+   iterating over all keys and values, and destroying hashtables. */
 STON_FUNC
 ston_dht  ston_dht_new(uint16_t,uint8_t,void*(*)(size_t),void(*)(void*));
 STON_FUNC
+void*     ston_dht_val(ston_dht,void*);
+STON_FUNC
 ston_dht  ston_dht_free(ston_dht);
 STON_FUNC
-void*     ston_dht_data(ston_dht,void*);
+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 */
-/* ston_dht ston_dht_iterate_start(ston_dht); */
-/* STON_FUNC */
-/* ston_dht ston_dht_iterate_next(ston_dht); */
-
-// Compatibility macros
+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_data(_HT,&(_K)) - 4))
+#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_data(_HT,&(_K)) + ((_OFFS - 1) * 4)),_VP,_N * 4)
+  memcpy((uint32_t*)((uint8_t*)ston_dht_val(_HT,&(_K)) + ((_OFFS - 1) * 4)),_VP,_N * 4)
 
-/* 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_dht ston_dht_new
 ( uint16_t val_bytes,
@@ -352,12 +357,12 @@ ston_dht ston_dht_new
 }
 
 
-/* Returns a pointer to the row of data in the hashtable containing the provided
-   key, inserting if not found, or NULL if a memory error occurs */
+/* 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
-void* ston_dht_data
+void* ston_dht_val
 ( struct ston_dht_t* ht,
-  void*               key
+  void*              key
 )
 { size_t   key_bytes = ht->header.key_bytes;
   uint8_t* key_byte = (uint8_t*)key;
@@ -394,7 +399,8 @@ void* ston_dht_data
   return (void*) row + sizeof(void*) + key_bytes;
 }
 
-/* Free the dynamic hash table */
+/* Recursively frees all memory stored in the hashtable, and the hashtable
+   itself */
 STON_FUNC
 struct ston_dht_t* ston_dht_free
 ( struct ston_dht_t* ht )
@@ -406,24 +412,54 @@ struct ston_dht_t* ston_dht_free
   return ht;
 }
 
-/* Recursively free pages by lookup */
+/* Recursive free function for nested buckets */
 STON_FUNC_STATIC
 STON_FUNC_NOINLINE
 void ston_dht_free_bucket
 ( struct ston_dht_t* ht,
-  void*               bucket
+  void*              bucket
 )
-{ size_t key_bytes = ht->header.key_bytes;
-  size_t val_bytes = ht->header.val_bytes;
-  void** bucket_cur = (void**)((uint8_t*)bucket);
-  void** bucket_max = (void**)((uint8_t*)bucket_cur + ((sizeof(void*) + key_bytes + val_bytes) * 0x100));
+{ 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 + sizeof(void*) + key_bytes + val_bytes);
+      bucket_cur = (void**)((uint8_t*)bucket_cur + ht->rowsize);
     }
   ht->ht_free(bucket);
 }
 
+/* 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
+void ston_dht_iterate
+( struct ston_dht_t* ht,
+  void               (*fn)(void*,void*,void*),
+  void*              user_data
+)
+{ ht->ht_iter = fn;
+  ht->ht_user_data = user_data;
+  ston_dht_iterate_r(ht,ht->bucket_root);
+}
+
+/* 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;
+    }
+}
 
 #endif //_STON_HT_H_