declare isl_union_pw_multi_aff_intersect_params
[isl.git] / isl_hash.c
blob36817d7fb42dad02027feba381455bfe7f32f9e7
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.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 struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
153 struct isl_hash_table *table,
154 uint32_t key_hash,
155 int (*eq)(const void *entry, const void *val),
156 const void *val, int reserve)
158 size_t size;
159 uint32_t h, key_bits;
161 key_bits = isl_hash_bits(key_hash, table->bits);
162 size = 1 << table->bits;
163 for (h = key_bits; table->entries[h].data; h = (h+1) % size)
164 if (table->entries[h].hash == key_hash &&
165 eq(table->entries[h].data, val))
166 return &table->entries[h];
168 if (!reserve)
169 return NULL;
171 if (4 * table->n >= 3 * size) {
172 if (grow_table(ctx, table) < 0)
173 return NULL;
174 return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);
177 table->n++;
178 table->entries[h].hash = key_hash;
180 return &table->entries[h];
183 int isl_hash_table_foreach(struct isl_ctx *ctx,
184 struct isl_hash_table *table,
185 int (*fn)(void **entry, void *user), void *user)
187 size_t size;
188 uint32_t h;
190 if (!table->entries)
191 return -1;
193 size = 1 << table->bits;
194 for (h = 0; h < size; ++ h)
195 if (table->entries[h].data &&
196 fn(&table->entries[h].data, user) < 0)
197 return -1;
199 return 0;
202 void isl_hash_table_remove(struct isl_ctx *ctx,
203 struct isl_hash_table *table,
204 struct isl_hash_table_entry *entry)
206 int h, h2;
207 size_t size;
209 if (!table || !entry)
210 return;
212 size = 1 << table->bits;
213 h = entry - table->entries;
214 isl_assert(ctx, h >= 0 && h < size, return);
216 for (h2 = h+1; table->entries[h2 % size].data; h2++) {
217 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
218 table->bits);
219 uint32_t offset = (size + bits - (h+1)) % size;
220 if (offset <= h2 - (h+1))
221 continue;
222 *entry = table->entries[h2 % size];
223 h = h2;
224 entry = &table->entries[h % size];
227 entry->hash = 0;
228 entry->data = NULL;
229 table->n--;