Line data Source code
1 : /*
2 : * Copyright 2008-2009 Katholieke Universiteit Leuven
3 : *
4 : * Use of this software is governed by the MIT license
5 : *
6 : * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 : * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
8 : */
9 :
10 : #include <stdlib.h>
11 : #include <isl_hash_private.h>
12 : #include <isl/ctx.h>
13 : #include "isl_config.h"
14 :
15 0 : uint32_t isl_hash_string(uint32_t hash, const char *s)
16 : {
17 0 : for (; *s; s++)
18 0 : isl_hash_byte(hash, *s);
19 0 : return hash;
20 : }
21 :
22 0 : uint32_t isl_hash_mem(uint32_t hash, const void *p, size_t len)
23 : {
24 : int i;
25 0 : const char *s = p;
26 0 : for (i = 0; i < len; ++i)
27 0 : isl_hash_byte(hash, s[i]);
28 0 : return hash;
29 : }
30 :
31 238500 : static unsigned int round_up(unsigned int v)
32 : {
33 238500 : int old_v = v;
34 :
35 824819 : while (v) {
36 347819 : old_v = v;
37 347819 : v ^= v & -v;
38 : }
39 238500 : return old_v << 1;
40 : }
41 :
42 238500 : int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
43 : int min_size)
44 : {
45 : size_t size;
46 :
47 238500 : if (!table)
48 0 : return -1;
49 :
50 238500 : if (min_size < 2)
51 37647 : min_size = 2;
52 238500 : table->bits = ffs(round_up(4 * (min_size + 1) / 3 - 1)) - 1;
53 238500 : table->n = 0;
54 :
55 238500 : size = 1 << table->bits;
56 238500 : table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
57 : size);
58 238500 : if (!table->entries)
59 0 : return -1;
60 :
61 238500 : return 0;
62 : }
63 :
64 : /* Dummy comparison function that always returns false.
65 : */
66 0 : static int no(const void *entry, const void *val)
67 : {
68 0 : return 0;
69 : }
70 :
71 : /* Extend "table" to twice its size.
72 : * Return 0 on success and -1 on error.
73 : *
74 : * We reuse isl_hash_table_find to create entries in the extended table.
75 : * Since all entries in the original table are assumed to be different,
76 : * there is no need to compare them against each other.
77 : */
78 0 : static int grow_table(struct isl_ctx *ctx, struct isl_hash_table *table)
79 : {
80 : int n;
81 : size_t old_size, size;
82 : struct isl_hash_table_entry *entries;
83 : uint32_t h;
84 :
85 0 : entries = table->entries;
86 0 : old_size = 1 << table->bits;
87 0 : size = 2 * old_size;
88 0 : table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
89 : size);
90 0 : if (!table->entries) {
91 0 : table->entries = entries;
92 0 : return -1;
93 : }
94 :
95 0 : n = table->n;
96 0 : table->n = 0;
97 0 : table->bits++;
98 :
99 0 : for (h = 0; h < old_size; ++h) {
100 : struct isl_hash_table_entry *entry;
101 :
102 0 : if (!entries[h].data)
103 0 : continue;
104 :
105 0 : entry = isl_hash_table_find(ctx, table, entries[h].hash,
106 : &no, NULL, 1);
107 0 : if (!entry) {
108 0 : table->bits--;
109 0 : free(table->entries);
110 0 : table->entries = entries;
111 0 : table->n = n;
112 0 : return -1;
113 : }
114 :
115 0 : *entry = entries[h];
116 : }
117 :
118 0 : free(entries);
119 :
120 0 : return 0;
121 : }
122 :
123 0 : struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
124 : {
125 0 : struct isl_hash_table *table = NULL;
126 :
127 0 : table = isl_alloc_type(ctx, struct isl_hash_table);
128 0 : if (isl_hash_table_init(ctx, table, min_size))
129 0 : goto error;
130 0 : return table;
131 : error:
132 0 : isl_hash_table_free(ctx, table);
133 0 : return NULL;
134 : }
135 :
136 200853 : void isl_hash_table_clear(struct isl_hash_table *table)
137 : {
138 200853 : if (!table)
139 0 : return;
140 200853 : free(table->entries);
141 : }
142 :
143 0 : void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
144 : {
145 0 : if (!table)
146 0 : return;
147 0 : isl_hash_table_clear(table);
148 0 : free(table);
149 : }
150 :
151 : /* A dummy entry that can be used to make a distinction between
152 : * a missing entry and an error condition.
153 : * It is used by isl_union_*_find_part_entry.
154 : */
155 : static struct isl_hash_table_entry none = { 0, NULL };
156 : struct isl_hash_table_entry *isl_hash_table_entry_none = &none;
157 :
158 1801236 : struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
159 : struct isl_hash_table *table,
160 : uint32_t key_hash,
161 : int (*eq)(const void *entry, const void *val),
162 : const void *val, int reserve)
163 : {
164 : size_t size;
165 : uint32_t h, key_bits;
166 :
167 1801236 : key_bits = isl_hash_bits(key_hash, table->bits);
168 1801236 : size = 1 << table->bits;
169 2448961 : for (h = key_bits; table->entries[h].data; h = (h+1) % size)
170 1333423 : if (table->entries[h].hash == key_hash &&
171 342849 : eq(table->entries[h].data, val))
172 342849 : return &table->entries[h];
173 :
174 1458387 : if (!reserve)
175 705739 : return NULL;
176 :
177 752648 : if (4 * table->n >= 3 * size) {
178 0 : if (grow_table(ctx, table) < 0)
179 0 : return NULL;
180 0 : return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);
181 : }
182 :
183 752648 : table->n++;
184 752648 : table->entries[h].hash = key_hash;
185 :
186 752648 : return &table->entries[h];
187 : }
188 :
189 0 : isl_stat isl_hash_table_foreach(isl_ctx *ctx, struct isl_hash_table *table,
190 : isl_stat (*fn)(void **entry, void *user), void *user)
191 : {
192 : size_t size;
193 : uint32_t h;
194 :
195 0 : if (!table->entries)
196 0 : return isl_stat_error;
197 :
198 0 : size = 1 << table->bits;
199 0 : for (h = 0; h < size; ++ h)
200 0 : if (table->entries[h].data &&
201 0 : fn(&table->entries[h].data, user) < 0)
202 0 : return isl_stat_error;
203 :
204 0 : return isl_stat_ok;
205 : }
206 :
207 1131 : void isl_hash_table_remove(struct isl_ctx *ctx,
208 : struct isl_hash_table *table,
209 : struct isl_hash_table_entry *entry)
210 : {
211 : int h, h2;
212 : size_t size;
213 :
214 1131 : if (!table || !entry)
215 0 : return;
216 :
217 1131 : size = 1 << table->bits;
218 1131 : h = entry - table->entries;
219 1131 : isl_assert(ctx, h >= 0 && h < size, return);
220 :
221 2171 : for (h2 = h+1; table->entries[h2 % size].data; h2++) {
222 1040 : uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
223 : table->bits);
224 1040 : uint32_t offset = (size + bits - (h+1)) % size;
225 1040 : if (offset <= h2 - (h+1))
226 760 : continue;
227 280 : *entry = table->entries[h2 % size];
228 280 : h = h2;
229 280 : entry = &table->entries[h % size];
230 : }
231 :
232 1131 : entry->hash = 0;
233 1131 : entry->data = NULL;
234 1131 : table->n--;
235 : }
|
