isl_hash.c

   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 <isl_hash_private.h>
  12 #include <isl/ctx.h>
  13 #include "isl_config.h"
  14
  15 uint32_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
  22 uint32_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
  31 static 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
  42 int 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  */
  66 static 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  */
  78 static 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
 123 struct 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;
 131 error:
 132         isl_hash_table_free(ctx, table);
 133         return NULL;
 134 }
 135
 136 void isl_hash_table_clear(struct isl_hash_table *table)
 137 {
 138         if (!table)
 139                 return;
 140         free(table->entries);
 141 }
 142
 143 void 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_find
 152  * to make a distinction between a missing entry and an error condition.
 153  */
 154 static struct isl_hash_table_entry none = { 0, NULL };
 155 struct isl_hash_table_entry *isl_hash_table_entry_none = &none;
 156
 157 struct 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 and
 197  * NULL on error.
 198  */
 199 struct 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
 215 isl_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  */
 235 isl_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
 258 void 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 }