#include <limits.h>
#include <stdbool.h>
#include <assert.h>
+#include <string.h>
/* We use 0x1 as deleted marker. */
#define HTABLE_DELETED (0x1)
ht->table = &ht->perfect_bit;
}
+/* We've changed ht->bits, update ht->max and ht->max_with_deleted */
+static void htable_adjust_capacity(struct htable *ht)
+{
+ ht->max = ((size_t)3 << ht->bits) / 4;
+ ht->max_with_deleted = ((size_t)9 << ht->bits) / 10;
+}
+
bool htable_init_sized(struct htable *ht,
size_t (*rehash)(const void *, void *),
void *priv, size_t expect)
ht->table = &ht->perfect_bit;
return false;
}
- ht->max = ((size_t)3 << ht->bits) / 4;
- ht->max_with_deleted = ((size_t)9 << ht->bits) / 10;
-
+ htable_adjust_capacity(ht);
return true;
}
htable_init(ht, ht->rehash, ht->priv);
}
+bool htable_copy(struct htable *dst, const struct htable *src)
+{
+ uintptr_t *htable = malloc(sizeof(size_t) << src->bits);
+
+ if (!htable)
+ return false;
+
+ *dst = *src;
+ dst->table = htable;
+ memcpy(dst->table, src->table, sizeof(size_t) << src->bits);
+ return true;
+}
+
static size_t hash_bucket(const struct htable *ht, size_t h)
{
return h & ((1 << ht->bits)-1);
return NULL;
}
+void *htable_prev(const struct htable *ht, struct htable_iter *i)
+{
+ for (;;) {
+ if (!i->off)
+ return NULL;
+ i->off --;
+ if (entry_is_valid(ht->table[i->off]))
+ return get_raw_ptr(ht, ht->table[i->off]);
+ }
+}
+
/* This does not expand the hash table, that's up to caller. */
static void ht_add(struct htable *ht, const void *new, size_t h)
{
return false;
}
ht->bits++;
- ht->max = ((size_t)3 << ht->bits) / 4;
- ht->max_with_deleted = ((size_t)9 << ht->bits) / 10;
+ htable_adjust_capacity(ht);
/* If we lost our "perfect bit", get it back now. */
if (!ht->perfect_bit && ht->common_mask) {