5 uint32_t isl_hash_string(uint32_t hash, const char *s)
8 isl_hash_byte(hash, *s);
12 static unsigned int round_up(unsigned int v)
23 int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
33 table->bits = ffs(round_up(4 * (min_size + 1) / 3 - 1)) - 1;
36 size = 2 << table->bits;
37 table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
45 struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
47 struct isl_hash_table *table = NULL;
49 table = isl_alloc_type(ctx, struct isl_hash_table);
50 if (isl_hash_table_init(ctx, table, min_size))
54 isl_hash_table_free(ctx, table);
58 void isl_hash_table_clear(struct isl_hash_table *table)
65 void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
69 isl_hash_table_clear(table);
73 struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
74 struct isl_hash_table *table,
76 int (*eq)(const void *entry, const void *val),
77 const void *val, int reserve)
82 key_bits = isl_hash_bits(key_hash, table->bits);
83 size = 2 << table->bits;
84 for (h = key_bits; table->entries[h].data; h = (h+1) % size)
85 if (table->entries[h].hash == key_hash &&
86 eq(table->entries[h].data, val))
87 return &table->entries[h];
92 assert(4 * table->n < 3 * size); /* XXX */
94 table->entries[h].hash = key_hash;
96 return &table->entries[h];
99 void isl_hash_table_remove(struct isl_ctx *ctx,
100 struct isl_hash_table *table,
101 struct isl_hash_table_entry *entry)
106 if (!table || !entry)
109 size = 2 << table->bits;
110 h = entry - table->entries;
111 isl_assert(ctx, h >= 0 && h < size, return);
113 for (h2 = h+1; table->entries[h2 % size].data; h2++) {
114 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
116 uint32_t offset = (size + bits - (h+1)) % size;
117 if (offset <= h2 - (h+1))
119 *entry = table->entries[h2 % size];
121 entry = &table->entries[h % size];