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 <strings.h>
  12 #include <isl_hash_private.h>
  13 #include <isl/ctx.h>
  14 #include "isl_config.h"
  15
  16 uint32_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
  23 uint32_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
  32 static 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
  43 int 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  */
  67 static 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  */
  79 static 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
 124 struct 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;
 132 error:
 133         isl_hash_table_free(ctx, table);
 134         return NULL;
 135 }
 136
 137 void isl_hash_table_clear(struct isl_hash_table *table)
 138 {
 139         if (!table)
 140                 return;
 141         free(table->entries);
 142 }
 143
 144 void 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
 152 /* A dummy entry that can be used to make a distinction between
 153  * a missing entry and an error condition.
 154  * It is used by isl_union_*_find_part_entry.
 155  */
 156 static struct isl_hash_table_entry none = { 0, NULL };
 157 struct isl_hash_table_entry *isl_hash_table_entry_none = &none;
 158
 159 struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
 160                                 struct isl_hash_table *table,
 161                                 uint32_t key_hash,
 162                                 int (*eq)(const void *entry, const void *val),
 163                                 const void *val, int reserve)
 164 {
 165         size_t size;
 166         uint32_t h, key_bits;
 167
 168         key_bits = isl_hash_bits(key_hash, table->bits);
 169         size = 1 << table->bits;
 170         for (h = key_bits; table->entries[h].data; h = (h+1) % size)
 171                 if (table->entries[h].hash == key_hash &&
 172                     eq(table->entries[h].data, val))
 173                         return &table->entries[h];
 174
 175         if (!reserve)
 176                 return NULL;
 177
 178         if (4 * table->n >= 3 * size) {
 179                 if (grow_table(ctx, table) < 0)
 180                         return NULL;
 181                 return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);
 182         }
 183
 184         table->n++;
 185         table->entries[h].hash = key_hash;
 186
 187         return &table->entries[h];
 188 }
 189
 190 isl_stat isl_hash_table_foreach(isl_ctx *ctx, struct isl_hash_table *table,
 191         isl_stat (*fn)(void **entry, void *user), void *user)
 192 {
 193         size_t size;
 194         uint32_t h;
 195
 196         if (!table->entries)
 197                 return isl_stat_error;
 198
 199         size = 1 << table->bits;
 200         for (h = 0; h < size; ++ h)
 201                 if (table->entries[h].data &&
 202                     fn(&table->entries[h].data, user) < 0)
 203                         return isl_stat_error;
 204
 205         return isl_stat_ok;
 206 }
 207
 208 void isl_hash_table_remove(struct isl_ctx *ctx,
 209                                 struct isl_hash_table *table,
 210                                 struct isl_hash_table_entry *entry)
 211 {
 212         int h, h2;
 213         size_t size;
 214
 215         if (!table || !entry)
 216                 return;
 217
 218         size = 1 << table->bits;
 219         h = entry - table->entries;
 220         isl_assert(ctx, h >= 0 && h < size, return);
 221
 222         for (h2 = h+1; table->entries[h2 % size].data; h2++) {
 223                 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
 224                                                 table->bits);
 225                 uint32_t offset = (size + bits - (h+1)) % size;
 226                 if (offset <= h2 - (h+1))
 227                         continue;
 228                 *entry = table->entries[h2 % size];
 229                 h = h2;
 230                 entry = &table->entries[h % size];
 231         }
 232
 233         entry->hash = 0;
 234         entry->data = NULL;
 235         table->n--;
 236 }