isl_hash.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  *
   4  * Use of this software is governed by the GNU LGPLv2.1 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.h"
  12 #include "isl_ctx.h"
  13
  14 uint32_t isl_hash_string(uint32_t hash, const char *s)
  15 {
  16         for (; *s; s++)
  17                 isl_hash_byte(hash, *s);
  18         return hash;
  19 }
  20
  21 static unsigned int round_up(unsigned int v)
  22 {
  23         int old_v = v;
  24
  25         while (v) {
  26                 old_v = v;
  27                 v ^= v & -v;
  28         }
  29         return old_v << 1;
  30 }
  31
  32 int isl_hash_table_init(struct isl_ctx *ctx, struct isl_hash_table *table,
  33                         int min_size)
  34 {
  35         size_t size;
  36
  37         if (!table)
  38                 return -1;
  39
  40         if (min_size < 2)
  41                 min_size = 2;
  42         table->bits = ffs(round_up(4 * (min_size + 1) / 3 - 1)) - 1;
  43         table->n = 0;
  44
  45         size = 1 << table->bits;
  46         table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
  47                                           size);
  48         if (!table->entries)
  49                 return -1;
  50
  51         return 0;
  52 }
  53
  54 static int grow_table(struct isl_ctx *ctx, struct isl_hash_table *table,
  55                         int (*eq)(const void *entry, const void *val))
  56 {
  57         size_t old_size, size;
  58         struct isl_hash_table_entry *entries;
  59         uint32_t h;
  60
  61         entries = table->entries;
  62         old_size = 1 << table->bits;
  63         size = 2 * old_size;
  64         table->entries = isl_calloc_array(ctx, struct isl_hash_table_entry,
  65                                           size);
  66         if (!table->entries) {
  67                 table->entries = entries;
  68                 return -1;
  69         }
  70
  71         table->bits++;
  72
  73         for (h = 0; h < old_size; ++h) {
  74                 struct isl_hash_table_entry *entry;
  75
  76                 if (!entries[h].data)
  77                         continue;
  78
  79                 entry = isl_hash_table_find(ctx, table, entries[h].hash,
  80                                             eq, entries[h].data, 1);
  81                 if (!entry) {
  82                         table->bits--;
  83                         free(table->entries);
  84                         table->entries = entries;
  85                         return -1;
  86                 }
  87
  88                 *entry = entries[h];
  89         }
  90
  91         free(entries);
  92
  93         return 0;
  94 }
  95
  96 struct isl_hash_table *isl_hash_table_alloc(struct isl_ctx *ctx, int min_size)
  97 {
  98         struct isl_hash_table *table = NULL;
  99
 100         table = isl_alloc_type(ctx, struct isl_hash_table);
 101         if (isl_hash_table_init(ctx, table, min_size))
 102                 goto error;
 103         return table;
 104 error:
 105         isl_hash_table_free(ctx, table);
 106         return NULL;
 107 }
 108
 109 void isl_hash_table_clear(struct isl_hash_table *table)
 110 {
 111         if (!table)
 112                 return;
 113         free(table->entries);
 114 }
 115
 116 void isl_hash_table_free(struct isl_ctx *ctx, struct isl_hash_table *table)
 117 {
 118         if (!table)
 119                 return;
 120         isl_hash_table_clear(table);
 121         free(table);
 122 }
 123
 124 struct isl_hash_table_entry *isl_hash_table_find(struct isl_ctx *ctx,
 125                                 struct isl_hash_table *table,
 126                                 uint32_t key_hash,
 127                                 int (*eq)(const void *entry, const void *val),
 128                                 const void *val, int reserve)
 129 {
 130         size_t size;
 131         uint32_t h, key_bits;
 132
 133         key_bits = isl_hash_bits(key_hash, table->bits);
 134         size = 1 << table->bits;
 135         for (h = key_bits; table->entries[h].data; h = (h+1) % size)
 136                 if (table->entries[h].hash == key_hash &&
 137                     eq(table->entries[h].data, val))
 138                         return &table->entries[h];
 139
 140         if (!reserve)
 141                 return NULL;
 142
 143         if (4 * table->n >= 3 * size) {
 144                 if (grow_table(ctx, table, eq) < 0)
 145                         return NULL;
 146                 return isl_hash_table_find(ctx, table, key_hash, eq, val, 1);
 147         }
 148
 149         table->n++;
 150         table->entries[h].hash = key_hash;
 151
 152         return &table->entries[h];
 153 }
 154
 155 void isl_hash_table_remove(struct isl_ctx *ctx,
 156                                 struct isl_hash_table *table,
 157                                 struct isl_hash_table_entry *entry)
 158 {
 159         int h, h2;
 160         size_t size;
 161
 162         if (!table || !entry)
 163                 return;
 164
 165         size = 1 << table->bits;
 166         h = entry - table->entries;
 167         isl_assert(ctx, h >= 0 && h < size, return);
 168
 169         for (h2 = h+1; table->entries[h2 % size].data; h2++) {
 170                 uint32_t bits = isl_hash_bits(table->entries[h2 % size].hash,
 171                                                 table->bits);
 172                 uint32_t offset = (size + bits - (h+1)) % size;
 173                 if (offset <= h2 - (h+1))
 174                         continue;
 175                 *entry = table->entries[h2 % size];
 176                 h = h2;
 177                 entry = &table->entries[h % size];
 178         }
 179
 180         entry->hash = 0;
 181         entry->data = NULL;
 182         table->n--;
 183 }