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.h>
  13 #include <isl/ctx.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 static int grow_table(struct isl_ctx *ctx, struct isl_hash_table *table,
  65                         int (*eq)(const void *entry, const void *val))
  66 {
  67         int n;
  68         size_t old_size, size;
  69         struct isl_hash_table_entry *entries;
  70         uint32_t h;
  71
  72         entries = table->entries;
  73         old_size = 1 << table->bits;
  74         size = 2 * old_size;
  75         table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
  76                                           size);
  77         if (!table->entries) {
  78                 table->entries = entries;
  79                 return -1;
  80         }
  81
  82         n = table->n;
  83         table->n = 0;
  84         table->bits++;
  85
  86         for (h = 0; h < old_size; ++h) {
  87                 struct isl_hash_table_entry *entry;
  88
  89                 if (!entries[h].data)
  90                         continue;
  91
  92                 entry = isl_hash_table_find(ctx, table, entries[h].hash,
  93                                             eq, entries[h].data, 1);
  94                 if (!entry) {
  95                         table->bits--;
  96                         free(table->entries);
  97                         table->entries = entries;
  98                         table->n = n;
  99                         return -1;
 100                 }
 101
 102                 *entry = entries[h];
 103         }
 104
 105         free(entries);
 106
 107         return 0;
 108 }
 109
 110 struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
 111 {
 112         struct isl_hash_table *table = NULL;
 113
 114         table = isl_alloc_type(ctx, struct isl_hash_table);
 115         if (isl_hash_table_init(ctx, table, min_size))
 116                 goto error;
 117         return table;
 118 error:
 119         isl_hash_table_free(ctx, table);
 120         return NULL;
 121 }
 122
 123 void isl_hash_table_clear(struct isl_hash_table *table)
 124 {
 125         if (!table)
 126                 return;
 127         free(table->entries);
 128 }
 129
 130 void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
 131 {
 132         if (!table)
 133                 return;
 134         isl_hash_table_clear(table);
 135         free(table);
 136 }
 137
 138 struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
 139                                 struct isl_hash_table *table,
 140                                 uint32_t key_hash,
 141                                 int (*eq)(const void *entry, const void *val),
 142                                 const void *val, int reserve)
 143 {
 144         size_t size;
 145         uint32_t h, key_bits;
 146
 147         key_bits = isl_hash_bits(key_hash, table->bits);
 148         size = 1 << table->bits;
 149         for (h = key_bits; table->entries[h].data; h = (h+1) % size)
 150                 if (table->entries[h].hash == key_hash &&
 151                     eq(table->entries[h].data, val))
 152                         return &table->entries[h];
 153
 154         if (!reserve)
 155                 return NULL;
 156
 157         if (4 * table->n >= 3 * size) {
 158                 if (grow_table(ctx, table, eq) < 0)
 159                         return NULL;
 160                 return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);
 161         }
 162
 163         table->n++;
 164         table->entries[h].hash = key_hash;
 165
 166         return &table->entries[h];
 167 }
 168
 169 int isl_hash_table_foreach(struct isl_ctx *ctx,
 170                                 struct isl_hash_table *table,
 171                                 int (*fn)(void **entry, void *user), void *user)
 172 {
 173         size_t size;
 174         uint32_t h;
 175
 176         size = 1 << table->bits;
 177         for (h = 0; h < size; ++ h)
 178                 if (table->entries[h].data &&
 179                     fn(&table->entries[h].data, user) < 0)
 180                         return -1;
 181
 182         return 0;
 183 }
 184
 185 void isl_hash_table_remove(struct isl_ctx *ctx,
 186                                 struct isl_hash_table *table,
 187                                 struct isl_hash_table_entry *entry)
 188 {
 189         int h, h2;
 190         size_t size;
 191
 192         if (!table || !entry)
 193                 return;
 194
 195         size = 1 << table->bits;
 196         h = entry - table->entries;
 197         isl_assert(ctx, h >= 0 && h < size, return);
 198
 199         for (h2 = h+1; table->entries[h2 % size].data; h2++) {
 200                 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
 201                                                 table->bits);
 202                 uint32_t offset = (size + bits - (h+1)) % size;
 203                 if (offset <= h2 - (h+1))
 204                         continue;
 205                 *entry = table->entries[h2 % size];
 206                 h = h2;
 207                 entry = &table->entries[h % size];
 208         }
 209
 210         entry->hash = 0;
 211         entry->data = NULL;
 212         table->n--;
 213 }