File: | polly/lib/External/isl/isl_hash.c |
Warning: | line 167, column 11 The result of the left shift is undefined due to shifting by '32', which is greater or equal to the width of type 'int' |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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.h> | |||
12 | #include <isl/ctx.h> | |||
13 | #include "isl_config.h" | |||
14 | ||||
15 | uint32_t isl_hash_string(uint32_t hash, const char *s) | |||
16 | { | |||
17 | for (; *s; s++) | |||
18 | isl_hash_byte(hash, *s)do { hash *= 16777619; hash ^= *s; } while(0); | |||
19 | return hash; | |||
20 | } | |||
21 | ||||
22 | uint32_t isl_hash_mem(uint32_t hash, const void *p, size_t len) | |||
23 | { | |||
24 | int i; | |||
25 | const char *s = p; | |||
26 | for (i = 0; i < len; ++i) | |||
27 | isl_hash_byte(hash, s[i])do { hash *= 16777619; hash ^= s[i]; } while(0); | |||
28 | return hash; | |||
29 | } | |||
30 | ||||
31 | static unsigned int round_up(unsigned int v) | |||
32 | { | |||
33 | int old_v = v; | |||
34 | ||||
35 | while (v) { | |||
36 | old_v = v; | |||
37 | v ^= v & -v; | |||
38 | } | |||
39 | return old_v << 1; | |||
40 | } | |||
41 | ||||
42 | 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 | if (!table) | |||
48 | return -1; | |||
49 | ||||
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; | |||
54 | ||||
55 | size = 1 << table->bits; | |||
56 | table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,((struct isl_hash_table_entry *)isl_calloc_or_die(ctx, size, sizeof (struct isl_hash_table_entry))) | |||
57 | size)((struct isl_hash_table_entry *)isl_calloc_or_die(ctx, size, sizeof (struct isl_hash_table_entry))); | |||
58 | if (!table->entries) | |||
59 | return -1; | |||
60 | ||||
61 | return 0; | |||
62 | } | |||
63 | ||||
64 | /* Dummy comparison function that always returns false. | |||
65 | */ | |||
66 | static isl_bool no(const void *entry, const void *val) | |||
67 | { | |||
68 | return isl_bool_false; | |||
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 | 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 | entries = table->entries; | |||
86 | old_size = 1 << table->bits; | |||
87 | size = 2 * old_size; | |||
88 | table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,((struct isl_hash_table_entry *)isl_calloc_or_die(ctx, size, sizeof (struct isl_hash_table_entry))) | |||
89 | size)((struct isl_hash_table_entry *)isl_calloc_or_die(ctx, size, sizeof (struct isl_hash_table_entry))); | |||
90 | if (!table->entries) { | |||
| ||||
91 | table->entries = entries; | |||
92 | return -1; | |||
93 | } | |||
94 | ||||
95 | n = table->n; | |||
96 | table->n = 0; | |||
97 | table->bits++; | |||
98 | ||||
99 | for (h = 0; h < old_size; ++h) { | |||
100 | struct isl_hash_table_entry *entry; | |||
101 | ||||
102 | if (!entries[h].data) | |||
103 | continue; | |||
104 | ||||
105 | entry = isl_hash_table_find(ctx, table, entries[h].hash, | |||
106 | &no, NULL((void*)0), 1); | |||
107 | if (!entry) { | |||
108 | table->bits--; | |||
109 | free(table->entries); | |||
110 | table->entries = entries; | |||
111 | table->n = n; | |||
112 | return -1; | |||
113 | } | |||
114 | ||||
115 | *entry = entries[h]; | |||
116 | } | |||
117 | ||||
118 | free(entries); | |||
119 | ||||
120 | return 0; | |||
121 | } | |||
122 | ||||
123 | struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size) | |||
124 | { | |||
125 | struct isl_hash_table *table = NULL((void*)0); | |||
126 | ||||
127 | table = isl_alloc_type(ctx, struct isl_hash_table)((struct isl_hash_table *)isl_malloc_or_die(ctx, sizeof(struct isl_hash_table))); | |||
128 | if (isl_hash_table_init(ctx, table, min_size)) | |||
129 | goto error; | |||
130 | return table; | |||
131 | error: | |||
132 | isl_hash_table_free(ctx, table); | |||
133 | return NULL((void*)0); | |||
134 | } | |||
135 | ||||
136 | void isl_hash_table_clear(struct isl_hash_table *table) | |||
137 | { | |||
138 | if (!table) | |||
139 | return; | |||
140 | free(table->entries); | |||
141 | } | |||
142 | ||||
143 | void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table) | |||
144 | { | |||
145 | if (!table) | |||
146 | return; | |||
147 | isl_hash_table_clear(table); | |||
148 | free(table); | |||
149 | } | |||
150 | ||||
151 | /* A dummy entry that is used by isl_hash_table_find | |||
152 | * to make a distinction between a missing entry and an error condition. | |||
153 | */ | |||
154 | static struct isl_hash_table_entry none = { 0, NULL((void*)0) }; | |||
155 | struct isl_hash_table_entry *isl_hash_table_entry_none = &none; | |||
156 | ||||
157 | struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx, | |||
158 | struct isl_hash_table *table, | |||
159 | uint32_t key_hash, | |||
160 | isl_bool (*eq)(const void *entry, const void *val), | |||
161 | const void *val, int reserve) | |||
162 | { | |||
163 | size_t size; | |||
164 | uint32_t h, key_bits; | |||
165 | ||||
166 | key_bits = isl_hash_bits(key_hash, table->bits)((table->bits) == 32) ? (key_hash) : ((table->bits) >= 16) ? ((key_hash) >> (table->bits)) ^ ((key_hash) & (((uint32_t)1 << (table->bits)) - 1)) : (((key_hash ) >> (table->bits)) ^ (key_hash)) & (((uint32_t) 1 << (table->bits)) - 1); | |||
167 | size = 1 << table->bits; | |||
| ||||
168 | for (h = key_bits; table->entries[h].data; h = (h+1) % size) { | |||
169 | isl_bool equal; | |||
170 | ||||
171 | if (table->entries[h].hash != key_hash) | |||
172 | continue; | |||
173 | equal = eq(table->entries[h].data, val); | |||
174 | if (equal < 0) | |||
175 | return NULL((void*)0); | |||
176 | if (equal) | |||
177 | return &table->entries[h]; | |||
178 | } | |||
179 | ||||
180 | if (!reserve) | |||
181 | return isl_hash_table_entry_none; | |||
182 | ||||
183 | if (4 * table->n >= 3 * size) { | |||
184 | if (grow_table(ctx, table) < 0) | |||
185 | return NULL((void*)0); | |||
186 | return isl_hash_table_find(ctx, table, key_hash, eq, val, 1); | |||
187 | } | |||
188 | ||||
189 | table->n++; | |||
190 | table->entries[h].hash = key_hash; | |||
191 | ||||
192 | return &table->entries[h]; | |||
193 | } | |||
194 | ||||
195 | isl_stat isl_hash_table_foreach(isl_ctx *ctx, struct isl_hash_table *table, | |||
196 | isl_stat (*fn)(void **entry, void *user), void *user) | |||
197 | { | |||
198 | size_t size; | |||
199 | uint32_t h; | |||
200 | ||||
201 | if (!table->entries) | |||
202 | return isl_stat_error; | |||
203 | ||||
204 | size = 1 << table->bits; | |||
205 | for (h = 0; h < size; ++ h) | |||
206 | if (table->entries[h].data && | |||
207 | fn(&table->entries[h].data, user) < 0) | |||
208 | return isl_stat_error; | |||
209 | ||||
210 | return isl_stat_ok; | |||
211 | } | |||
212 | ||||
213 | void isl_hash_table_remove(struct isl_ctx *ctx, | |||
214 | struct isl_hash_table *table, | |||
215 | struct isl_hash_table_entry *entry) | |||
216 | { | |||
217 | int h, h2; | |||
218 | size_t size; | |||
219 | ||||
220 | if (!table || !entry) | |||
221 | return; | |||
222 | ||||
223 | size = 1 << table->bits; | |||
224 | h = entry - table->entries; | |||
225 | isl_assert(ctx, h >= 0 && h < size, return)do { if (h >= 0 && h < size) break; do { isl_handle_error (ctx, isl_error_unknown, "Assertion \"" "h >= 0 && h < size" "\" failed", "/build/llvm-toolchain-snapshot-14~++20210828111110+16086d47c0d0/polly/lib/External/isl/isl_hash.c" , 225); return; } while (0); } while (0); | |||
226 | ||||
227 | for (h2 = h+1; table->entries[h2 % size].data; h2++) { | |||
228 | uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,((table->bits) == 32) ? (table->entries[h2 % size].hash ) : ((table->bits) >= 16) ? ((table->entries[h2 % size ].hash) >> (table->bits)) ^ ((table->entries[h2 % size].hash) & (((uint32_t)1 << (table->bits)) - 1)) : (((table->entries[h2 % size].hash) >> (table-> bits)) ^ (table->entries[h2 % size].hash)) & (((uint32_t )1 << (table->bits)) - 1) | |||
229 | table->bits)((table->bits) == 32) ? (table->entries[h2 % size].hash ) : ((table->bits) >= 16) ? ((table->entries[h2 % size ].hash) >> (table->bits)) ^ ((table->entries[h2 % size].hash) & (((uint32_t)1 << (table->bits)) - 1)) : (((table->entries[h2 % size].hash) >> (table-> bits)) ^ (table->entries[h2 % size].hash)) & (((uint32_t )1 << (table->bits)) - 1); | |||
230 | uint32_t offset = (size + bits - (h+1)) % size; | |||
231 | if (offset <= h2 - (h+1)) | |||
232 | continue; | |||
233 | *entry = table->entries[h2 % size]; | |||
234 | h = h2; | |||
235 | entry = &table->entries[h % size]; | |||
236 | } | |||
237 | ||||
238 | entry->hash = 0; | |||
239 | entry->data = NULL((void*)0); | |||
240 | table->n--; | |||
241 | } |