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#include "isl_config.h"
15
16uint32_t isl_hash_string(uint32_t hash, const char *s)
17{
18	for (; *s; s++)
19		isl_hash_byte(hash, *s);
20	return hash;
21}
22
23uint32_t isl_hash_mem(uint32_t hash, const void *p, size_t len)
24{
25	int i;
26	const char *s = p;
27	for (i = 0; i < len; ++i)
28		isl_hash_byte(hash, s[i]);
29	return hash;
30}
31
32static unsigned int round_up(unsigned int v)
33{
34	int old_v = v;
35
36	while (v) {
37		old_v = v;
38		v ^= v & -v;
39	}
40	return old_v << 1;
41}
42
43int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
44			int min_size)
45{
46	size_t size;
47
48	if (!table)
49		return -1;
50
51	if (min_size < 2)
52		min_size = 2;
53	table->bits = ffs(round_up(4 * (min_size + 1) / 3 - 1)) - 1;
54	table->n = 0;
55
56	size = 1 << table->bits;
57	table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
58					  size);
59	if (!table->entries)
60		return -1;
61
62	return 0;
63}
64
65/* Dummy comparison function that always returns false.
66 */
67static int no(const void *entry, const void *val)
68{
69	return 0;
70}
71
72/* Extend "table" to twice its size.
73 * Return 0 on success and -1 on error.
74 *
75 * We reuse isl_hash_table_find to create entries in the extended table.
76 * Since all entries in the original table are assumed to be different,
77 * there is no need to compare them against each other.
78 */
79static int grow_table(struct isl_ctx *ctx, struct isl_hash_table *table)
80{
81	int n;
82	size_t old_size, size;
83	struct isl_hash_table_entry *entries;
84	uint32_t h;
85
86	entries = table->entries;
87	old_size = 1 << table->bits;
88	size = 2 * old_size;
89	table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
90					  size);
91	if (!table->entries) {
92		table->entries = entries;
93		return -1;
94	}
95
96	n = table->n;
97	table->n = 0;
98	table->bits++;
99
100	for (h = 0; h < old_size; ++h) {
101		struct isl_hash_table_entry *entry;
102
103		if (!entries[h].data)
104			continue;
105
106		entry = isl_hash_table_find(ctx, table, entries[h].hash,
107					    &no, NULL, 1);
108		if (!entry) {
109			table->bits--;
110			free(table->entries);
111			table->entries = entries;
112			table->n = n;
113			return -1;
114		}
115
116		*entry = entries[h];
117	}
118
119	free(entries);
120
121	return 0;
122}
123
124struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
125{
126	struct isl_hash_table *table = NULL;
127
128	table = isl_alloc_type(ctx, struct isl_hash_table);
129	if (isl_hash_table_init(ctx, table, min_size))
130		goto error;
131	return table;
132error:
133	isl_hash_table_free(ctx, table);
134	return NULL;
135}
136
137void isl_hash_table_clear(struct isl_hash_table *table)
138{
139	if (!table)
140		return;
141	free(table->entries);
142}
143
144void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
145{
146	if (!table)
147		return;
148	isl_hash_table_clear(table);
149	free(table);
150}
151
152struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
153				struct isl_hash_table *table,
154				uint32_t key_hash,
155				int (*eq)(const void *entry, const void *val),
156				const void *val, int reserve)
157{
158	size_t size;
159	uint32_t h, key_bits;
160
161	key_bits = isl_hash_bits(key_hash, table->bits);
162	size = 1 << table->bits;
163	for (h = key_bits; table->entries[h].data; h = (h+1) % size)
164		if (table->entries[h].hash == key_hash &&
165		    eq(table->entries[h].data, val))
166			return &table->entries[h];
167
168	if (!reserve)
169		return NULL;
170
171	if (4 * table->n >= 3 * size) {
172		if (grow_table(ctx, table) < 0)
173			return NULL;
174		return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);
175	}
176
177	table->n++;
178	table->entries[h].hash = key_hash;
179
180	return &table->entries[h];
181}
182
183int isl_hash_table_foreach(struct isl_ctx *ctx,
184				struct isl_hash_table *table,
185				int (*fn)(void **entry, void *user), void *user)
186{
187	size_t size;
188	uint32_t h;
189
190	size = 1 << table->bits;
191	for (h = 0; h < size; ++ h)
192		if (table->entries[h].data &&
193		    fn(&table->entries[h].data, user) < 0)
194			return -1;
195
196	return 0;
197}
198
199void isl_hash_table_remove(struct isl_ctx *ctx,
200				struct isl_hash_table *table,
201				struct isl_hash_table_entry *entry)
202{
203	int h, h2;
204	size_t size;
205
206	if (!table || !entry)
207		return;
208
209	size = 1 << table->bits;
210	h = entry - table->entries;
211	isl_assert(ctx, h >= 0 && h < size, return);
212
213	for (h2 = h+1; table->entries[h2 % size].data; h2++) {
214		uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
215						table->bits);
216		uint32_t offset = (size + bits - (h+1)) % size;
217		if (offset <= h2 - (h+1))
218			continue;
219		*entry = table->entries[h2 % size];
220		h = h2;
221		entry = &table->entries[h % size];
222	}
223
224	entry->hash = 0;
225	entry->data = NULL;
226	table->n--;
227}
228