2 * Copyright 2008-2009 Katholieke Universiteit Leuven
4 * Use of this software is governed by the GNU LGPLv2.1 license
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
14 uint32_t isl_hash_string(uint32_t hash, const char *s)
17 isl_hash_byte(hash, *s);
21 static unsigned int round_up(unsigned int v)
32 int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
42 table->bits = ffs(round_up(4 * (min_size + 1) / 3 - 1)) - 1;
45 size = 2 << table->bits;
46 table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
54 struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
56 struct isl_hash_table *table = NULL;
58 table = isl_alloc_type(ctx, struct isl_hash_table);
59 if (isl_hash_table_init(ctx, table, min_size))
63 isl_hash_table_free(ctx, table);
67 void isl_hash_table_clear(struct isl_hash_table *table)
74 void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
78 isl_hash_table_clear(table);
82 struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
83 struct isl_hash_table *table,
85 int (*eq)(const void *entry, const void *val),
86 const void *val, int reserve)
91 key_bits = isl_hash_bits(key_hash, table->bits);
92 size = 2 << table->bits;
93 for (h = key_bits; table->entries[h].data; h = (h+1) % size)
94 if (table->entries[h].hash == key_hash &&
95 eq(table->entries[h].data, val))
96 return &table->entries[h];
101 assert(4 * table->n < 3 * size); /* XXX */
103 table->entries[h].hash = key_hash;
105 return &table->entries[h];
108 void isl_hash_table_remove(struct isl_ctx *ctx,
109 struct isl_hash_table *table,
110 struct isl_hash_table_entry *entry)
115 if (!table || !entry)
118 size = 2 << table->bits;
119 h = entry - table->entries;
120 isl_assert(ctx, h >= 0 && h < size, return);
122 for (h2 = h+1; table->entries[h2 % size].data; h2++) {
123 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
125 uint32_t offset = (size + bits - (h+1)) % size;
126 if (offset <= h2 - (h+1))
128 *entry = table->entries[h2 % size];
130 entry = &table->entries[h % size];