File: | tools/polly/lib/External/isl/isl_hash.c |
Warning: | line 167, column 13 The result of the left shift is undefined due to shifting by '33', which is greater or equal to the width of type 'uint32_t' |
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_private.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 int no(const void *entry, const void *val) | |||||
67 | { | |||||
68 | 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 | 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 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((void*)0) }; | |||||
156 | struct isl_hash_table_entry *isl_hash_table_entry_none = &none; | |||||
157 | ||||||
158 | 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 | 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); | |||||
| ||||||
168 | size = 1 << table->bits; | |||||
169 | for (h = key_bits; table->entries[h].data; h = (h+1) % size) | |||||
170 | if (table->entries[h].hash == key_hash && | |||||
171 | eq(table->entries[h].data, val)) | |||||
172 | return &table->entries[h]; | |||||
173 | ||||||
174 | if (!reserve) | |||||
175 | return NULL((void*)0); | |||||
176 | ||||||
177 | if (4 * table->n >= 3 * size) { | |||||
178 | if (grow_table(ctx, table) < 0) | |||||
179 | return NULL((void*)0); | |||||
180 | return isl_hash_table_find(ctx, table, key_hash, eq, val, 1); | |||||
181 | } | |||||
182 | ||||||
183 | table->n++; | |||||
184 | table->entries[h].hash = key_hash; | |||||
185 | ||||||
186 | return &table->entries[h]; | |||||
187 | } | |||||
188 | ||||||
189 | 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 | if (!table->entries) | |||||
196 | return isl_stat_error; | |||||
197 | ||||||
198 | size = 1 << table->bits; | |||||
199 | for (h = 0; h < size; ++ h) | |||||
200 | if (table->entries[h].data && | |||||
201 | fn(&table->entries[h].data, user) < 0) | |||||
202 | return isl_stat_error; | |||||
203 | ||||||
204 | return isl_stat_ok; | |||||
205 | } | |||||
206 | ||||||
207 | 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 | if (!table || !entry) | |||||
215 | return; | |||||
216 | ||||||
217 | size = 1 << table->bits; | |||||
218 | h = entry - table->entries; | |||||
219 | 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-7~svn337204/tools/polly/lib/External/isl/isl_hash.c" , 219); return; } while (0); } while (0); | |||||
220 | ||||||
221 | for (h2 = h+1; table->entries[h2 % size].data; h2++) { | |||||
222 | 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) | |||||
223 | 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); | |||||
224 | uint32_t offset = (size + bits - (h+1)) % size; | |||||
225 | if (offset <= h2 - (h+1)) | |||||
226 | continue; | |||||
227 | *entry = table->entries[h2 % size]; | |||||
228 | h = h2; | |||||
229 | entry = &table->entries[h % size]; | |||||
230 | } | |||||
231 | ||||||
232 | entry->hash = 0; | |||||
233 | entry->data = NULL((void*)0); | |||||
234 | table->n--; | |||||
235 | } |