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