relicense isl under the MIT license
[platform/upstream/isl.git] / isl_hash.c
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 <strings.h>
12 #include <isl/hash.h>
13 #include <isl/ctx.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);
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]);
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,
57                                           size);
58         if (!table->entries)
59                 return -1;
60
61         return 0;
62 }
63
64 static int grow_table(struct isl_ctx *ctx, struct isl_hash_table *table,
65                         int (*eq)(const void *entry, const void *val))
66 {
67         int n;
68         size_t old_size, size;
69         struct isl_hash_table_entry *entries;
70         uint32_t h;
71
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;
80         }
81
82         n = table->n;
83         table->n = 0;
84         table->bits++;
85
86         for (h = 0; h < old_size; ++h) {
87                 struct isl_hash_table_entry *entry;
88
89                 if (!entries[h].data)
90                         continue;
91
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;
100                 }
101
102                 *entry = entries[h];
103         }
104
105         free(entries);
106
107         return 0;
108 }
109
110 struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
111 {
112         struct isl_hash_table *table = NULL;
113
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;
121 }
122
123 void isl_hash_table_clear(struct isl_hash_table *table)
124 {
125         if (!table)
126                 return;
127         free(table->entries);
128 }
129
130 void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
131 {
132         if (!table)
133                 return;
134         isl_hash_table_clear(table);
135         free(table);
136 }
137
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)
143 {
144         size_t size;
145         uint32_t h, key_bits;
146
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];
153
154         if (!reserve)
155                 return NULL;
156
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);
161         }
162
163         table->n++;
164         table->entries[h].hash = key_hash;
165
166         return &table->entries[h];
167 }
168
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)
172 {
173         size_t size;
174         uint32_t h;
175
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;
181         
182         return 0;
183 }
184
185 void isl_hash_table_remove(struct isl_ctx *ctx,
186                                 struct isl_hash_table *table,
187                                 struct isl_hash_table_entry *entry)
188 {
189         int h, h2;
190         size_t size;
191
192         if (!table || !entry)
193                 return;
194
195         size = 1 << table->bits;
196         h = entry - table->entries;
197         isl_assert(ctx, h >= 0 && h < size, return);
198
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];
208         }
209
210         entry->hash = 0;
211         entry->data = NULL;
212         table->n--;
213 }