+/*
+ * Copyright 2008-2009 Katholieke Universiteit Leuven
+ *
+ * Use of this software is governed by the GNU LGPLv2.1 license
+ *
+ * Written by Sven Verdoolaege, K.U.Leuven, Departement
+ * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
+ */
+
#include <stdlib.h>
#include "isl_hash.h"
#include "isl_ctx.h"
table->bits = ffs(round_up(4 * (min_size + 1) / 3 - 1)) - 1;
table->n = 0;
- size = 2 << table->bits;
+ size = 1 << table->bits;
table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
size);
if (!table->entries)
return 0;
}
+static int grow_table(struct isl_ctx *ctx, struct isl_hash_table *table,
+ int (*eq)(const void *entry, const void *val))
+{
+ size_t old_size, size;
+ struct isl_hash_table_entry *entries;
+ uint32_t h;
+
+ entries = table->entries;
+ old_size = 1 << table->bits;
+ size = 2 * old_size;
+ table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
+ size);
+ if (!table->entries) {
+ table->entries = entries;
+ return -1;
+ }
+
+ table->bits++;
+
+ for (h = 0; h < old_size; ++h) {
+ struct isl_hash_table_entry *entry;
+
+ if (!entries[h].data)
+ continue;
+
+ entry = isl_hash_table_find(ctx, table, entries[h].hash,
+ eq, entries[h].data, 1);
+ if (!entry) {
+ table->bits--;
+ free(table->entries);
+ table->entries = entries;
+ return -1;
+ }
+
+ *entry = entries[h];
+ }
+
+ free(entries);
+
+ return 0;
+}
+
struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
{
struct isl_hash_table *table = NULL;
uint32_t h, key_bits;
key_bits = isl_hash_bits(key_hash, table->bits);
- size = 2 << table->bits;
+ size = 1 << table->bits;
for (h = key_bits; table->entries[h].data; h = (h+1) % size)
if (table->entries[h].hash == key_hash &&
eq(table->entries[h].data, val))
if (!reserve)
return NULL;
- assert(4 * table->n < 3 * size); /* XXX */
+ if (4 * table->n >= 3 * size) {
+ if (grow_table(ctx, table, eq) < 0)
+ return NULL;
+ return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);
+ }
+
table->n++;
table->entries[h].hash = key_hash;
return &table->entries[h];
}
+int isl_hash_table_foreach(struct isl_ctx *ctx,
+ struct isl_hash_table *table,
+ int (*fn)(void *entry))
+{
+ size_t size;
+ uint32_t h;
+
+ size = 1 << table->bits;
+ for (h = 0; h < size; ++ h)
+ if (table->entries[h].data && fn(table->entries[h].data) < 0)
+ return -1;
+
+ return 0;
+}
+
void isl_hash_table_remove(struct isl_ctx *ctx,
struct isl_hash_table *table,
struct isl_hash_table_entry *entry)
{
- int h, h2, last_h;
+ int h, h2;
size_t size;
if (!table || !entry)
return;
- size = 2 << table->bits;
+ size = 1 << table->bits;
h = entry - table->entries;
isl_assert(ctx, h >= 0 && h < size, return);