X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=isl_hash.c;h=7b96c51cd2f8e4fdfe9e68c500ed316013269f7c;hb=baee941de1964a2cab64c34b627d5ab767060a79;hp=f751f46e59392b45537491c8f1889813af2da234;hpb=a97e198db4b396ab108896cb9ac6d5157a97fe53;p=platform%2Fupstream%2Fisl.git

diff --git a/isl_hash.c b/isl_hash.c
index f751f46..7b96c51 100644
--- a/isl_hash.c
+++ b/isl_hash.c
@@ -1,6 +1,16 @@
+/*
+ * 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)
 {
@@ -9,6 +19,15 @@ 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;
@@ -33,7 +52,7 @@ int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
 	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)
@@ -42,6 +61,52 @@ int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
 	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;
@@ -80,7 +145,7 @@ struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
 	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))
@@ -89,24 +154,45 @@ struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
 	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);