+/*
+ * Copyright 2008-2009 Katholieke Universiteit Leuven
+ *
+ * Use of this software is governed by the MIT 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"
+#include <strings.h>
+#include <isl/hash.h>
+#include <isl/ctx.h>
uint32_t isl_hash_string(uint32_t hash, const char *s)
{
return hash;
}
+uint32_t isl_hash_mem(uint32_t hash, const void *p, size_t len)
+{
+ int i;
+ const char *s = p;
+ for (i = 0; i < len; ++i)
+ isl_hash_byte(hash, s[i]);
+ return hash;
+}
+
+static unsigned int round_up(unsigned int v)
+{
+ int old_v = v;
+
+ while (v) {
+ old_v = v;
+ v ^= v & -v;
+ }
+ return old_v << 1;
+}
+
int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
- int init_bits)
+ int min_size)
{
size_t size;
if (!table)
return -1;
- if (init_bits < 2)
- init_bits = 2;
- table->bits = init_bits;
+ if (min_size < 2)
+ min_size = 2;
+ 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))
+{
+ int n;
+ 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;
+ }
+
+ n = table->n;
+ table->n = 0;
+ 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;
+ table->n = n;
+ 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;
+
+ table = isl_alloc_type(ctx, struct isl_hash_table);
+ if (isl_hash_table_init(ctx, table, min_size))
+ goto error;
+ return table;
+error:
+ isl_hash_table_free(ctx, table);
+ return NULL;
+}
+
void isl_hash_table_clear(struct isl_hash_table *table)
{
if (!table)
free(table->entries);
}
+void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
+{
+ if (!table)
+ return;
+ isl_hash_table_clear(table);
+ free(table);
+}
+
struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
struct isl_hash_table *table,
uint32_t key_hash,
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, void *user), void *user)
+{
+ 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, user) < 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);