2 * Copyright 2008-2009 Katholieke Universiteit Leuven
4 * Use of this software is governed by the MIT license
6 * Written by Sven Verdoolaege, K.U.Leuven, Departement
7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
14 #include "isl_config.h"
16 uint32_t isl_hash_string(uint32_t hash
, const char *s
)
19 isl_hash_byte(hash
, *s
);
23 uint32_t isl_hash_mem(uint32_t hash
, const void *p
, size_t len
)
27 for (i
= 0; i
< len
; ++i
)
28 isl_hash_byte(hash
, s
[i
]);
32 static unsigned int round_up(unsigned int v
)
43 int isl_hash_table_init(struct isl_ctx
*ctx
, struct isl_hash_table
*table
,
53 table
->bits
= ffs(round_up(4 * (min_size
+ 1) / 3 - 1)) - 1;
56 size
= 1 << table
->bits
;
57 table
->entries
= isl_calloc_array(ctx
, struct isl_hash_table_entry
,
65 static int grow_table(struct isl_ctx
*ctx
, struct isl_hash_table
*table
,
66 int (*eq
)(const void *entry
, const void *val
))
69 size_t old_size
, size
;
70 struct isl_hash_table_entry
*entries
;
73 entries
= table
->entries
;
74 old_size
= 1 << table
->bits
;
76 table
->entries
= isl_calloc_array(ctx
, struct isl_hash_table_entry
,
78 if (!table
->entries
) {
79 table
->entries
= entries
;
87 for (h
= 0; h
< old_size
; ++h
) {
88 struct isl_hash_table_entry
*entry
;
93 entry
= isl_hash_table_find(ctx
, table
, entries
[h
].hash
,
94 eq
, entries
[h
].data
, 1);
98 table
->entries
= entries
;
111 struct isl_hash_table
*isl_hash_table_alloc(struct isl_ctx
*ctx
, int min_size
)
113 struct isl_hash_table
*table
= NULL
;
115 table
= isl_alloc_type(ctx
, struct isl_hash_table
);
116 if (isl_hash_table_init(ctx
, table
, min_size
))
120 isl_hash_table_free(ctx
, table
);
124 void isl_hash_table_clear(struct isl_hash_table
*table
)
128 free(table
->entries
);
131 void isl_hash_table_free(struct isl_ctx
*ctx
, struct isl_hash_table
*table
)
135 isl_hash_table_clear(table
);
139 struct isl_hash_table_entry
*isl_hash_table_find(struct isl_ctx
*ctx
,
140 struct isl_hash_table
*table
,
142 int (*eq
)(const void *entry
, const void *val
),
143 const void *val
, int reserve
)
146 uint32_t h
, key_bits
;
148 key_bits
= isl_hash_bits(key_hash
, table
->bits
);
149 size
= 1 << table
->bits
;
150 for (h
= key_bits
; table
->entries
[h
].data
; h
= (h
+1) % size
)
151 if (table
->entries
[h
].hash
== key_hash
&&
152 eq(table
->entries
[h
].data
, val
))
153 return &table
->entries
[h
];
158 if (4 * table
->n
>= 3 * size
) {
159 if (grow_table(ctx
, table
, eq
) < 0)
161 return isl_hash_table_find(ctx
, table
, key_hash
, eq
, val
, 1);
165 table
->entries
[h
].hash
= key_hash
;
167 return &table
->entries
[h
];
170 int isl_hash_table_foreach(struct isl_ctx
*ctx
,
171 struct isl_hash_table
*table
,
172 int (*fn
)(void **entry
, void *user
), void *user
)
177 size
= 1 << table
->bits
;
178 for (h
= 0; h
< size
; ++ h
)
179 if (table
->entries
[h
].data
&&
180 fn(&table
->entries
[h
].data
, user
) < 0)
186 void isl_hash_table_remove(struct isl_ctx
*ctx
,
187 struct isl_hash_table
*table
,
188 struct isl_hash_table_entry
*entry
)
193 if (!table
|| !entry
)
196 size
= 1 << table
->bits
;
197 h
= entry
- table
->entries
;
198 isl_assert(ctx
, h
>= 0 && h
< size
, return);
200 for (h2
= h
+1; table
->entries
[h2
% size
].data
; h2
++) {
201 uint32_t bits
= isl_hash_bits(table
->entries
[h2
% size
].hash
,
203 uint32_t offset
= (size
+ bits
- (h
+1)) % size
;
204 if (offset
<= h2
- (h
+1))
206 *entry
= table
->entries
[h2
% size
];
208 entry
= &table
->entries
[h
% size
];