/*
* Copyright 2008-2009 Katholieke Universiteit Leuven
*
- * Use of this software is governed by the GNU LGPLv2.1 license
+ * 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;
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)
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 = 2 << table->bits;
+ old_size = 1 << table->bits;
size = 2 * old_size;
table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
size);
return -1;
}
+ n = table->n;
+ table->n = 0;
table->bits++;
for (h = 0; h < old_size; ++h) {
table->bits--;
free(table->entries);
table->entries = entries;
+ table->n = n;
return -1;
}
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))
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)
if (!table || !entry)
return;
- size = 2 << table->bits;
+ size = 1 << table->bits;
h = entry - table->entries;
isl_assert(ctx, h >= 0 && h < size, return);