nexmon – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 *
4 * Use of this software is governed by the GNU LGPLv2.1 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 size_t old_size, size;
68 struct isl_hash_table_entry *entries;
69 uint32_t h;
70  
71 entries = table->entries;
72 old_size = 1 << table->bits;
73 size = 2 * old_size;
74 table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
75 size);
76 if (!table->entries) {
77 table->entries = entries;
78 return -1;
79 }
80  
81 table->bits++;
82  
83 for (h = 0; h < old_size; ++h) {
84 struct isl_hash_table_entry *entry;
85  
86 if (!entries[h].data)
87 continue;
88  
89 entry = isl_hash_table_find(ctx, table, entries[h].hash,
90 eq, entries[h].data, 1);
91 if (!entry) {
92 table->bits--;
93 free(table->entries);
94 table->entries = entries;
95 return -1;
96 }
97  
98 *entry = entries[h];
99 }
100  
101 free(entries);
102  
103 return 0;
104 }
105  
106 struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
107 {
108 struct isl_hash_table *table = NULL;
109  
110 table = isl_alloc_type(ctx, struct isl_hash_table);
111 if (isl_hash_table_init(ctx, table, min_size))
112 goto error;
113 return table;
114 error:
115 isl_hash_table_free(ctx, table);
116 return NULL;
117 }
118  
119 void isl_hash_table_clear(struct isl_hash_table *table)
120 {
121 if (!table)
122 return;
123 free(table->entries);
124 }
125  
126 void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
127 {
128 if (!table)
129 return;
130 isl_hash_table_clear(table);
131 free(table);
132 }
133  
134 struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
135 struct isl_hash_table *table,
136 uint32_t key_hash,
137 int (*eq)(const void *entry, const void *val),
138 const void *val, int reserve)
139 {
140 size_t size;
141 uint32_t h, key_bits;
142  
143 key_bits = isl_hash_bits(key_hash, table->bits);
144 size = 1 << table->bits;
145 for (h = key_bits; table->entries[h].data; h = (h+1) % size)
146 if (table->entries[h].hash == key_hash &&
147 eq(table->entries[h].data, val))
148 return &table->entries[h];
149  
150 if (!reserve)
151 return NULL;
152  
153 if (4 * table->n >= 3 * size) {
154 if (grow_table(ctx, table, eq) < 0)
155 return NULL;
156 return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);
157 }
158  
159 table->n++;
160 table->entries[h].hash = key_hash;
161  
162 return &table->entries[h];
163 }
164  
165 int isl_hash_table_foreach(struct isl_ctx *ctx,
166 struct isl_hash_table *table,
167 int (*fn)(void **entry, void *user), void *user)
168 {
169 size_t size;
170 uint32_t h;
171  
172 size = 1 << table->bits;
173 for (h = 0; h < size; ++ h)
174 if (table->entries[h].data &&
175 fn(&table->entries[h].data, user) < 0)
176 return -1;
177  
178 return 0;
179 }
180  
181 void isl_hash_table_remove(struct isl_ctx *ctx,
182 struct isl_hash_table *table,
183 struct isl_hash_table_entry *entry)
184 {
185 int h, h2;
186 size_t size;
187  
188 if (!table || !entry)
189 return;
190  
191 size = 1 << table->bits;
192 h = entry - table->entries;
193 isl_assert(ctx, h >= 0 && h < size, return);
194  
195 for (h2 = h+1; table->entries[h2 % size].data; h2++) {
196 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
197 table->bits);
198 uint32_t offset = (size + bits - (h+1)) % size;
199 if (offset <= h2 - (h+1))
200 continue;
201 *entry = table->entries[h2 % size];
202 h = h2;
203 entry = &table->entries[h % size];
204 }
205  
206 entry->hash = 0;
207 entry->data = NULL;
208 table->n--;
209 }