42 int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,  in isl_hash_table_init()  argument
47 	if (!table)  in isl_hash_table_init()
52 	table->bits = ffs(round_up(4 * (min_size + 1) / 3 - 1)) - 1;  in isl_hash_table_init()
53 	table->n = 0;  in isl_hash_table_init()
55 	size = 1 << table->bits;  in isl_hash_table_init()
56 	table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,  in isl_hash_table_init()
58 	if (!table->entries)  in isl_hash_table_init()
71 /* Extend "table" to twice its size.
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,
78 static int grow_table(struct isl_ctx *ctx, struct isl_hash_table *table)  in grow_table()  argument
85 	entries = table->entries;  in grow_table()
86 	old_size = 1 << table->bits;  in grow_table()
88 	table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,  in grow_table()
90 	if (!table->entries) {  in grow_table()
91 		table->entries = entries;  in grow_table()
95 	n = table->n;  in grow_table()
96 	table->n = 0;  in grow_table()
97 	table->bits++;  in grow_table()
105 		entry = isl_hash_table_find(ctx, table, entries[h].hash,  in grow_table()
108 			table->bits--;  in grow_table()
109 			free(table->entries);  in grow_table()
110 			table->entries = entries;  in grow_table()
111 			table->n = n;  in grow_table()
125 	struct isl_hash_table *table = NULL;  in isl_hash_table_alloc()  local
127 	table = isl_alloc_type(ctx, struct isl_hash_table);  in isl_hash_table_alloc()
128 	if (isl_hash_table_init(ctx, table, min_size))  in isl_hash_table_alloc()
130 	return table;  in isl_hash_table_alloc()
132 	isl_hash_table_free(ctx, table);  in isl_hash_table_alloc()
136 void isl_hash_table_clear(struct isl_hash_table *table)  in isl_hash_table_clear()  argument
138 	if (!table)  in isl_hash_table_clear()
140 	free(table->entries);  in isl_hash_table_clear()
143 void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)  in isl_hash_table_free()  argument
145 	if (!table)  in isl_hash_table_free()
147 	isl_hash_table_clear(table);  in isl_hash_table_free()
148 	free(table);  in isl_hash_table_free()
158 			    struct isl_hash_table *table,  in isl_hash_table_find()  argument
166 	key_bits = isl_hash_bits(key_hash, table->bits);  in isl_hash_table_find()
167 	size = 1 << table->bits;  in isl_hash_table_find()
168 	for (h = key_bits; table->entries[h].data; h = (h+1) % size) {  in isl_hash_table_find()
171 		if (table->entries[h].hash != key_hash)  in isl_hash_table_find()
173 		equal = eq(table->entries[h].data, val);  in isl_hash_table_find()
177 			return &table->entries[h];  in isl_hash_table_find()
183 	if (4 * table->n >= 3 * size) {  in isl_hash_table_find()
184 		if (grow_table(ctx, table) < 0)  in isl_hash_table_find()
186 		return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);  in isl_hash_table_find()
189 	table->n++;  in isl_hash_table_find()
190 	table->entries[h].hash = key_hash;  in isl_hash_table_find()
192 	return &table->entries[h];  in isl_hash_table_find()
195 isl_stat isl_hash_table_foreach(isl_ctx *ctx, struct isl_hash_table *table,  in isl_hash_table_foreach()  argument
201 	if (!table->entries)  in isl_hash_table_foreach()
204 	size = 1 << table->bits;  in isl_hash_table_foreach()
206 		if (table->entries[h].data &&  in isl_hash_table_foreach()
207 		    fn(&table->entries[h].data, user) < 0)  in isl_hash_table_foreach()
214 				struct isl_hash_table *table,  in isl_hash_table_remove()  argument
220 	if (!table || !entry)  in isl_hash_table_remove()
223 	size = 1 << table->bits;  in isl_hash_table_remove()
224 	h = entry - table->entries;  in isl_hash_table_remove()
227 	for (h2 = h+1; table->entries[h2 % size].data; h2++) {  in isl_hash_table_remove()
228 		uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,  in isl_hash_table_remove()
229 						table->bits);  in isl_hash_table_remove()
233 		*entry = table->entries[h2 % size];  in isl_hash_table_remove()
235 		entry = &table->entries[h % size];  in isl_hash_table_remove()
240 	table->n--;  in isl_hash_table_remove()