+void ht_print (hashtable_t *ht, int verbose) {
+ printf("probe:%-2d density:%.1f%% count:%-8lld ", ht->probe, ht->density, (uint64_t)ht_count(ht));
+ hti_t *hti = ht->hti;
+ while (hti) {
+ if (verbose) {
+ for (int i = 0; i < (1ULL << hti->scale); ++i) {
+ volatile entry_t *ent = hti->table + i;
+ printf("[0x%x] 0x%llx:0x%llx\n", i, (uint64_t)ent->key, (uint64_t)ent->val);
+ if (i > 30) {
+ printf("...\n");
+ break;
+ }
+ }
+ }
+ int scale = hti->scale;
+ printf("hti count:%lld scale:%d key density:%.1f%% value density:%.1f%% probe:%d\n",
+ (uint64_t)hti->count, scale, (double)hti->key_count / (1ULL << scale) * 100,
+ (double)hti->count / (1ULL << scale) * 100, hti->probe);
+ hti = hti->next;
+ }
+}
+
+ht_iter_t *ht_iter_begin (hashtable_t *ht, map_key_t key) {
+ hti_t *hti;
+ int ref_count;
+ do {
+ hti = ht->hti;
+ while (hti->next != NULL) {
+ do { } while (hti_help_copy(hti) != TRUE);
+ hti = hti->next;
+ }
+ do {
+ ref_count = hti->ref_count;
+ if(ref_count == 0)
+ break;
+ } while (ref_count != SYNC_CAS(&hti->ref_count, ref_count, ref_count + 1));
+ } while (ref_count == 0);
+
+ ht_iter_t *iter = nbd_malloc(sizeof(ht_iter_t));
+ iter->hti = hti;
+ iter->idx = -1;
+
+ return iter;
+}
+
+map_val_t ht_iter_next (ht_iter_t *iter, map_key_t *key_ptr) {
+ volatile entry_t *ent;
+ map_key_t key;
+ map_val_t val;
+ size_t table_size = (1ULL << iter->hti->scale);
+ do {
+ iter->idx++;
+ if (iter->idx == table_size) {
+ return DOES_NOT_EXIST;
+ }
+ ent = &iter->hti->table[iter->idx];
+ key = (iter->hti->ht->key_type == NULL) ? (map_key_t)ent->key : (map_key_t)GET_PTR(ent->key);
+ val = ent->val;
+
+ } while (key == DOES_NOT_EXIST || val == DOES_NOT_EXIST || val == TOMBSTONE);
+
+ if (val == COPIED_VALUE) {
+ const datatype_t *key_type = iter->hti->ht->key_type;
+#ifdef NBD32
+ uint32_t hash = (key_type == NULL) ? murmur32_4b((uint64_t)key) : key_type->hash((void *)key);
+#else
+ uint32_t hash = (key_type == NULL) ? murmur32_8b((uint64_t)key) : key_type->hash((void *)key);
+#endif
+ val = hti_get(iter->hti->next, (map_key_t)ent->key, hash);
+
+ // Go to the next entry if key is already deleted.
+ if (val == DOES_NOT_EXIST)
+ return ht_iter_next(iter, key_ptr); // recursive tail-call
+ }
+
+ if (key_ptr) {
+ *key_ptr = key;
+ }
+ return val;
+}
+
+void ht_iter_free (ht_iter_t *iter) {
+ hti_release(iter->hti);
+ nbd_free(iter);