From: ken <ken@mihrtec.com>
Date: Tue, 14 Mar 2017 21:15:51 +0000 (-0700)
Subject: dht iterator
X-Git-Url: https://git.kengrimes.com/?p=henge%2Fapc.git;a=commitdiff_plain;h=7472c5df1b4ee28cb2cfc0a3189b37b8ba503b0d

dht iterator
---

diff --git a/ston/ston_ht.h b/ston/ston_ht.h
index 2d9cb79..de6a464 100644
--- a/ston/ston_ht.h
+++ b/ston/ston_ht.h
@@ -296,11 +296,13 @@ 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_FUNC
@@ -308,20 +310,21 @@ ston_dht  ston_dht_new(uint16_t,uint8_t,void*(*)(size_t),void(*)(void*));
 STON_FUNC
 ston_dht  ston_dht_free(ston_dht);
 STON_FUNC
-void*     ston_dht_data(ston_dht,void*);
+void*     ston_dht_val(ston_dht,void*);
 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); */
+STON_FUNC
+void      ston_dht_iterate(ston_dht,void(*)(void*,void*,void*),void*);
+STON_FUNC_STATIC
+STON_FUNC_NOINLINE
+void      ston_dht_iterate_r(ston_dht,void*);
 
 // Compatibility macros
 #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
@@ -352,12 +355,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;
@@ -411,19 +414,47 @@ 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 and value as
+   arguments */
+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,(void**)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_