287 lines · c
1/*2 * Copyright 2008-2009 Katholieke Universiteit Leuven3 *4 * Use of this software is governed by the MIT license5 *6 * Written by Sven Verdoolaege, K.U.Leuven, Departement7 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium8 */9 10#include <stdlib.h>11#include <isl_hash_private.h>12#include <isl/ctx.h>13#include "isl_config.h"14 15uint32_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 22uint32_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 31static 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 42int 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/* Dummy comparison function that always returns false.65 */66static isl_bool no(const void *entry, const void *val)67{68 return isl_bool_false;69}70 71/* Extend "table" to twice its size.72 * Return 0 on success and -1 on error.73 *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,76 * there is no need to compare them against each other.77 */78static int grow_table(struct isl_ctx *ctx, struct isl_hash_table *table)79{80 int n;81 size_t old_size, size;82 struct isl_hash_table_entry *entries;83 uint32_t h;84 85 entries = table->entries;86 old_size = 1 << table->bits;87 size = 2 * old_size;88 table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,89 size);90 if (!table->entries) {91 table->entries = entries;92 return -1;93 }94 95 n = table->n;96 table->n = 0;97 table->bits++;98 99 for (h = 0; h < old_size; ++h) {100 struct isl_hash_table_entry *entry;101 102 if (!entries[h].data)103 continue;104 105 entry = isl_hash_table_find(ctx, table, entries[h].hash,106 &no, NULL, 1);107 if (!entry) {108 table->bits--;109 free(table->entries);110 table->entries = entries;111 table->n = n;112 return -1;113 }114 115 *entry = entries[h];116 }117 118 free(entries);119 120 return 0;121}122 123struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)124{125 struct isl_hash_table *table = NULL;126 127 table = isl_alloc_type(ctx, struct isl_hash_table);128 if (isl_hash_table_init(ctx, table, min_size))129 goto error;130 return table;131error:132 isl_hash_table_free(ctx, table);133 return NULL;134}135 136void isl_hash_table_clear(struct isl_hash_table *table)137{138 if (!table)139 return;140 free(table->entries);141}142 143void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)144{145 if (!table)146 return;147 isl_hash_table_clear(table);148 free(table);149}150 151/* A dummy entry that is used by isl_hash_table_find152 * to make a distinction between a missing entry and an error condition.153 */154static struct isl_hash_table_entry none = { 0, NULL };155struct isl_hash_table_entry *isl_hash_table_entry_none = &none;156 157struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,158 struct isl_hash_table *table,159 uint32_t key_hash,160 isl_bool (*eq)(const void *entry, const void *val),161 const void *val, int reserve)162{163 size_t size;164 uint32_t h, key_bits;165 166 key_bits = isl_hash_bits(key_hash, table->bits);167 size = 1 << table->bits;168 for (h = key_bits; table->entries[h].data; h = (h+1) % size) {169 isl_bool equal;170 171 if (table->entries[h].hash != key_hash)172 continue;173 equal = eq(table->entries[h].data, val);174 if (equal < 0)175 return NULL;176 if (equal)177 return &table->entries[h];178 }179 180 if (!reserve)181 return isl_hash_table_entry_none;182 183 if (4 * table->n >= 3 * size) {184 if (grow_table(ctx, table) < 0)185 return NULL;186 return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);187 }188 189 table->n++;190 table->entries[h].hash = key_hash;191 192 return &table->entries[h];193}194 195/* Return the first entry containing data in "table".196 * Return isl_hash_table_entry_none is there is no such entry and197 * NULL on error.198 */199struct isl_hash_table_entry *isl_hash_table_first(struct isl_hash_table *table)200{201 size_t size;202 uint32_t h;203 204 if (!table->entries)205 return NULL;206 207 size = 1 << table->bits;208 for (h = 0; h < size; ++ h)209 if (table->entries[h].data)210 return &table->entries[h];211 212 return isl_hash_table_entry_none;213}214 215isl_stat isl_hash_table_foreach(isl_ctx *ctx, struct isl_hash_table *table,216 isl_stat (*fn)(void **entry, void *user), void *user)217{218 size_t size;219 uint32_t h;220 221 if (!table->entries)222 return isl_stat_error;223 224 size = 1 << table->bits;225 for (h = 0; h < size; ++ h)226 if (table->entries[h].data &&227 fn(&table->entries[h].data, user) < 0)228 return isl_stat_error;229 230 return isl_stat_ok;231}232 233/* Does "test" succeed on every (non-empty) entry of "table"?234 */235isl_bool isl_hash_table_every(isl_ctx *ctx, struct isl_hash_table *table,236 isl_bool (*test)(void **entry, void *user), void *user)237{238 size_t size;239 uint32_t h;240 241 if (!table->entries)242 return isl_bool_error;243 244 size = 1 << table->bits;245 for (h = 0; h < size; ++ h) {246 isl_bool r;247 248 if (!table->entries[h].data)249 continue;250 r = test(&table->entries[h].data, user);251 if (r < 0 || !r)252 return r;253 }254 255 return isl_bool_true;256}257 258void isl_hash_table_remove(struct isl_ctx *ctx,259 struct isl_hash_table *table,260 struct isl_hash_table_entry *entry)261{262 int h, h2;263 size_t size;264 265 if (!table || !entry)266 return;267 268 size = 1 << table->bits;269 h = entry - table->entries;270 isl_assert(ctx, h >= 0 && h < size, return);271 272 for (h2 = h+1; table->entries[h2 % size].data; h2++) {273 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,274 table->bits);275 uint32_t offset = (size + bits - (h+1)) % size;276 if (offset <= h2 - (h+1))277 continue;278 *entry = table->entries[h2 % size];279 h = h2;280 entry = &table->entries[h % size];281 }282 283 entry->hash = 0;284 entry->data = NULL;285 table->n--;286}287