isl_simple_hull: check for empty/single-disjunct map _after_ detect_equalities
[isl.git] / isl_hash.c
blob89beecc7082e98ac02383331b332cb1ac8b512ec
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8 */
10 #include <stdlib.h>
11 #include <strings.h>
12 #include <isl_hash_private.h>
13 #include <isl/ctx.h>
14 #include "isl_config.h"
16 uint32_t isl_hash_string(uint32_t hash, const char *s)
18 for (; *s; s++)
19 isl_hash_byte(hash, *s);
20 return hash;
23 uint32_t isl_hash_mem(uint32_t hash, const void *p, size_t len)
25 int i;
26 const char *s = p;
27 for (i = 0; i < len; ++i)
28 isl_hash_byte(hash, s[i]);
29 return hash;
32 static unsigned int round_up(unsigned int v)
34 int old_v = v;
36 while (v) {
37 old_v = v;
38 v ^= v & -v;
40 return old_v << 1;
43 int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
44 int min_size)
46 size_t size;
48 if (!table)
49 return -1;
51 if (min_size < 2)
52 min_size = 2;
53 table->bits = ffs(round_up(4 * (min_size + 1) / 3 - 1)) - 1;
54 table->n = 0;
56 size = 1 << table->bits;
57 table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
58 size);
59 if (!table->entries)
60 return -1;
62 return 0;
65 /* Dummy comparison function that always returns false.
67 static int no(const void *entry, const void *val)
69 return 0;
72 /* Extend "table" to twice its size.
73 * Return 0 on success and -1 on error.
75 * We reuse isl_hash_table_find to create entries in the extended table.
76 * Since all entries in the original table are assumed to be different,
77 * there is no need to compare them against each other.
79 static int grow_table(struct isl_ctx *ctx, struct isl_hash_table *table)
81 int n;
82 size_t old_size, size;
83 struct isl_hash_table_entry *entries;
84 uint32_t h;
86 entries = table->entries;
87 old_size = 1 << table->bits;
88 size = 2 * old_size;
89 table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
90 size);
91 if (!table->entries) {
92 table->entries = entries;
93 return -1;
96 n = table->n;
97 table->n = 0;
98 table->bits++;
100 for (h = 0; h < old_size; ++h) {
101 struct isl_hash_table_entry *entry;
103 if (!entries[h].data)
104 continue;
106 entry = isl_hash_table_find(ctx, table, entries[h].hash,
107 &no, NULL, 1);
108 if (!entry) {
109 table->bits--;
110 free(table->entries);
111 table->entries = entries;
112 table->n = n;
113 return -1;
116 *entry = entries[h];
119 free(entries);
121 return 0;
124 struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
126 struct isl_hash_table *table = NULL;
128 table = isl_alloc_type(ctx, struct isl_hash_table);
129 if (isl_hash_table_init(ctx, table, min_size))
130 goto error;
131 return table;
132 error:
133 isl_hash_table_free(ctx, table);
134 return NULL;
137 void isl_hash_table_clear(struct isl_hash_table *table)
139 if (!table)
140 return;
141 free(table->entries);
144 void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
146 if (!table)
147 return;
148 isl_hash_table_clear(table);
149 free(table);
152 /* A dummy entry that can be used to make a distinction between
153 * a missing entry and an error condition.
154 * It is used by isl_union_*_find_part_entry.
156 static struct isl_hash_table_entry none = { 0, NULL };
157 struct isl_hash_table_entry *isl_hash_table_entry_none = &none;
159 struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
160 struct isl_hash_table *table,
161 uint32_t key_hash,
162 int (*eq)(const void *entry, const void *val),
163 const void *val, int reserve)
165 size_t size;
166 uint32_t h, key_bits;
168 key_bits = isl_hash_bits(key_hash, table->bits);
169 size = 1 << table->bits;
170 for (h = key_bits; table->entries[h].data; h = (h+1) % size)
171 if (table->entries[h].hash == key_hash &&
172 eq(table->entries[h].data, val))
173 return &table->entries[h];
175 if (!reserve)
176 return NULL;
178 if (4 * table->n >= 3 * size) {
179 if (grow_table(ctx, table) < 0)
180 return NULL;
181 return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);
184 table->n++;
185 table->entries[h].hash = key_hash;
187 return &table->entries[h];
190 isl_stat isl_hash_table_foreach(isl_ctx *ctx, struct isl_hash_table *table,
191 isl_stat (*fn)(void **entry, void *user), void *user)
193 size_t size;
194 uint32_t h;
196 if (!table->entries)
197 return isl_stat_error;
199 size = 1 << table->bits;
200 for (h = 0; h < size; ++ h)
201 if (table->entries[h].data &&
202 fn(&table->entries[h].data, user) < 0)
203 return isl_stat_error;
205 return isl_stat_ok;
208 void isl_hash_table_remove(struct isl_ctx *ctx,
209 struct isl_hash_table *table,
210 struct isl_hash_table_entry *entry)
212 int h, h2;
213 size_t size;
215 if (!table || !entry)
216 return;
218 size = 1 << table->bits;
219 h = entry - table->entries;
220 isl_assert(ctx, h >= 0 && h < size, return);
222 for (h2 = h+1; table->entries[h2 % size].data; h2++) {
223 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
224 table->bits);
225 uint32_t offset = (size + bits - (h+1)) % size;
226 if (offset <= h2 - (h+1))
227 continue;
228 *entry = table->entries[h2 % size];
229 h = h2;
230 entry = &table->entries[h % size];
233 entry->hash = 0;
234 entry->data = NULL;
235 table->n--;