isl_affine_hull.c: affine_hull_with_cone: plug memory leak on error path
[isl.git] / isl_hash.c
blob7b96c51cd2f8e4fdfe9e68c500ed316013269f7c
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>
15 uint32_t isl_hash_string(uint32_t hash, const char *s)
17 for (; *s; s++)
18 isl_hash_byte(hash, *s);
19 return hash;
22 uint32_t isl_hash_mem(uint32_t hash, const void *p, size_t len)
24 int i;
25 const char *s = p;
26 for (i = 0; i < len; ++i)
27 isl_hash_byte(hash, s[i]);
28 return hash;
31 static unsigned int round_up(unsigned int v)
33 int old_v = v;
35 while (v) {
36 old_v = v;
37 v ^= v & -v;
39 return old_v << 1;
42 int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
43 int min_size)
45 size_t size;
47 if (!table)
48 return -1;
50 if (min_size < 2)
51 min_size = 2;
52 table->bits = ffs(round_up(4 * (min_size + 1) / 3 - 1)) - 1;
53 table->n = 0;
55 size = 1 << table->bits;
56 table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
57 size);
58 if (!table->entries)
59 return -1;
61 return 0;
64 static int grow_table(struct isl_ctx *ctx, struct isl_hash_table *table,
65 int (*eq)(const void *entry, const void *val))
67 int n;
68 size_t old_size, size;
69 struct isl_hash_table_entry *entries;
70 uint32_t h;
72 entries = table->entries;
73 old_size = 1 << table->bits;
74 size = 2 * old_size;
75 table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
76 size);
77 if (!table->entries) {
78 table->entries = entries;
79 return -1;
82 n = table->n;
83 table->n = 0;
84 table->bits++;
86 for (h = 0; h < old_size; ++h) {
87 struct isl_hash_table_entry *entry;
89 if (!entries[h].data)
90 continue;
92 entry = isl_hash_table_find(ctx, table, entries[h].hash,
93 eq, entries[h].data, 1);
94 if (!entry) {
95 table->bits--;
96 free(table->entries);
97 table->entries = entries;
98 table->n = n;
99 return -1;
102 *entry = entries[h];
105 free(entries);
107 return 0;
110 struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
112 struct isl_hash_table *table = NULL;
114 table = isl_alloc_type(ctx, struct isl_hash_table);
115 if (isl_hash_table_init(ctx, table, min_size))
116 goto error;
117 return table;
118 error:
119 isl_hash_table_free(ctx, table);
120 return NULL;
123 void isl_hash_table_clear(struct isl_hash_table *table)
125 if (!table)
126 return;
127 free(table->entries);
130 void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
132 if (!table)
133 return;
134 isl_hash_table_clear(table);
135 free(table);
138 struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
139 struct isl_hash_table *table,
140 uint32_t key_hash,
141 int (*eq)(const void *entry, const void *val),
142 const void *val, int reserve)
144 size_t size;
145 uint32_t h, key_bits;
147 key_bits = isl_hash_bits(key_hash, table->bits);
148 size = 1 << table->bits;
149 for (h = key_bits; table->entries[h].data; h = (h+1) % size)
150 if (table->entries[h].hash == key_hash &&
151 eq(table->entries[h].data, val))
152 return &table->entries[h];
154 if (!reserve)
155 return NULL;
157 if (4 * table->n >= 3 * size) {
158 if (grow_table(ctx, table, eq) < 0)
159 return NULL;
160 return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);
163 table->n++;
164 table->entries[h].hash = key_hash;
166 return &table->entries[h];
169 int isl_hash_table_foreach(struct isl_ctx *ctx,
170 struct isl_hash_table *table,
171 int (*fn)(void **entry, void *user), void *user)
173 size_t size;
174 uint32_t h;
176 size = 1 << table->bits;
177 for (h = 0; h < size; ++ h)
178 if (table->entries[h].data &&
179 fn(&table->entries[h].data, user) < 0)
180 return -1;
182 return 0;
185 void isl_hash_table_remove(struct isl_ctx *ctx,
186 struct isl_hash_table *table,
187 struct isl_hash_table_entry *entry)
189 int h, h2;
190 size_t size;
192 if (!table || !entry)
193 return;
195 size = 1 << table->bits;
196 h = entry - table->entries;
197 isl_assert(ctx, h >= 0 && h < size, return);
199 for (h2 = h+1; table->entries[h2 % size].data; h2++) {
200 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
201 table->bits);
202 uint32_t offset = (size + bits - (h+1)) % size;
203 if (offset <= h2 - (h+1))
204 continue;
205 *entry = table->entries[h2 % size];
206 h = h2;
207 entry = &table->entries[h % size];
210 entry->hash = 0;
211 entry->data = NULL;
212 table->n--;