libdm/datastruct/hash.c

   1 /*
   2  * Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved.
   3  * Copyright (C) 2004-2007 Red Hat, Inc. All rights reserved.
   4  *
   5  * This file is part of the device-mapper userspace tools.
   6  *
   7  * This copyrighted material is made available to anyone wishing to use,
   8  * modify, copy, or redistribute it subject to the terms and conditions
   9  * of the GNU Lesser General Public License v.2.1.
  10  *
  11  * You should have received a copy of the GNU Lesser General Public License
  12  * along with this program; if not, write to the Free Software Foundation,
  13  * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  14  */
  15
  16 #include "dmlib.h"
  17
  18 struct dm_hash_node {
  19         struct dm_hash_node *next;
  20         void *data;
  21         unsigned keylen;
  22         char key[0];
  23 };
  24
  25 struct dm_hash_table {
  26         unsigned num_nodes;
  27         unsigned num_slots;
  28         struct dm_hash_node **slots;
  29 };
  30
  31 /* Permutation of the Integers 0 through 255 */
  32 static unsigned char _nums[] = {
  33         1, 14, 110, 25, 97, 174, 132, 119, 138, 170, 125, 118, 27, 233, 140, 51,
  34         87, 197, 177, 107, 234, 169, 56, 68, 30, 7, 173, 73, 188, 40, 36, 65,
  35         49, 213, 104, 190, 57, 211, 148, 223, 48, 115, 15, 2, 67, 186, 210, 28,
  36         12, 181, 103, 70, 22, 58, 75, 78, 183, 167, 238, 157, 124, 147, 172,
  37         144,
  38         176, 161, 141, 86, 60, 66, 128, 83, 156, 241, 79, 46, 168, 198, 41, 254,
  39         178, 85, 253, 237, 250, 154, 133, 88, 35, 206, 95, 116, 252, 192, 54,
  40         221,
  41         102, 218, 255, 240, 82, 106, 158, 201, 61, 3, 89, 9, 42, 155, 159, 93,
  42         166, 80, 50, 34, 175, 195, 100, 99, 26, 150, 16, 145, 4, 33, 8, 189,
  43         121, 64, 77, 72, 208, 245, 130, 122, 143, 55, 105, 134, 29, 164, 185,
  44         194,
  45         193, 239, 101, 242, 5, 171, 126, 11, 74, 59, 137, 228, 108, 191, 232,
  46         139,
  47         6, 24, 81, 20, 127, 17, 91, 92, 251, 151, 225, 207, 21, 98, 113, 112,
  48         84, 226, 18, 214, 199, 187, 13, 32, 94, 220, 224, 212, 247, 204, 196,
  49         43,
  50         249, 236, 45, 244, 111, 182, 153, 136, 129, 90, 217, 202, 19, 165, 231,
  51         71,
  52         230, 142, 96, 227, 62, 179, 246, 114, 162, 53, 160, 215, 205, 180, 47,
  53         109,
  54         44, 38, 31, 149, 135, 0, 216, 52, 63, 23, 37, 69, 39, 117, 146, 184,
  55         163, 200, 222, 235, 248, 243, 219, 10, 152, 131, 123, 229, 203, 76, 120,
  56         209
  57 };
  58
  59 static struct dm_hash_node *_create_node(const char *str, unsigned len)
  60 {
  61         struct dm_hash_node *n = dm_malloc(sizeof(*n) + len);
  62
  63         if (n) {
  64                 memcpy(n->key, str, len);
  65                 n->keylen = len;
  66         }
  67
  68         return n;
  69 }
  70
  71 static unsigned long _hash(const char *str, unsigned len)
  72 {
  73         unsigned long h = 0, g;
  74         unsigned i;
  75
  76         for (i = 0; i < len; i++) {
  77                 h <<= 4;
  78                 h += _nums[(unsigned char) *str++];
  79                 g = h & ((unsigned long) 0xf << 16u);
  80                 if (g) {
  81                         h ^= g >> 16u;
  82                         h ^= g >> 5u;
  83                 }
  84         }
  85
  86         return h;
  87 }
  88
  89 struct dm_hash_table *dm_hash_create(unsigned size_hint)
  90 {
  91         size_t len;
  92         unsigned new_size = 16u;
  93         struct dm_hash_table *hc = dm_zalloc(sizeof(*hc));
  94
  95         if (!hc)
  96                 return_0;
  97
  98         /* round size hint up to a power of two */
  99         while (new_size < size_hint)
 100                 new_size = new_size << 1;
 101
 102         hc->num_slots = new_size;
 103         len = sizeof(*(hc->slots)) * new_size;
 104         if (!(hc->slots = dm_malloc(len))) {
 105                 stack;
 106                 goto bad;
 107         }
 108         memset(hc->slots, 0, len);
 109         return hc;
 110
 111       bad:
 112         dm_free(hc->slots);
 113         dm_free(hc);
 114         return 0;
 115 }
 116
 117 static void _free_nodes(struct dm_hash_table *t)
 118 {
 119         struct dm_hash_node *c, *n;
 120         unsigned i;
 121
 122         for (i = 0; i < t->num_slots; i++)
 123                 for (c = t->slots[i]; c; c = n) {
 124                         n = c->next;
 125                         dm_free(c);
 126                 }
 127 }
 128
 129 void dm_hash_destroy(struct dm_hash_table *t)
 130 {
 131         _free_nodes(t);
 132         dm_free(t->slots);
 133         dm_free(t);
 134 }
 135
 136 static struct dm_hash_node **_find(struct dm_hash_table *t, const char *key,
 137                                    uint32_t len)
 138 {
 139         unsigned h = _hash(key, len) & (t->num_slots - 1);
 140         struct dm_hash_node **c;
 141
 142         for (c = &t->slots[h]; *c; c = &((*c)->next)) {
 143                 if ((*c)->keylen != len)
 144                         continue;
 145
 146                 if (!memcmp(key, (*c)->key, len))
 147                         break;
 148         }
 149
 150         return c;
 151 }
 152
 153 void *dm_hash_lookup_binary(struct dm_hash_table *t, const char *key,
 154                          uint32_t len)
 155 {
 156         struct dm_hash_node **c = _find(t, key, len);
 157
 158         return *c ? (*c)->data : 0;
 159 }
 160
 161 int dm_hash_insert_binary(struct dm_hash_table *t, const char *key,
 162                           uint32_t len, void *data)
 163 {
 164         struct dm_hash_node **c = _find(t, key, len);
 165
 166         if (*c)
 167                 (*c)->data = data;
 168         else {
 169                 struct dm_hash_node *n = _create_node(key, len);
 170
 171                 if (!n)
 172                         return 0;
 173
 174                 n->data = data;
 175                 n->next = 0;
 176                 *c = n;
 177                 t->num_nodes++;
 178         }
 179
 180         return 1;
 181 }
 182
 183 void dm_hash_remove_binary(struct dm_hash_table *t, const char *key,
 184                         uint32_t len)
 185 {
 186         struct dm_hash_node **c = _find(t, key, len);
 187
 188         if (*c) {
 189                 struct dm_hash_node *old = *c;
 190                 *c = (*c)->next;
 191                 dm_free(old);
 192                 t->num_nodes--;
 193         }
 194 }
 195
 196 void *dm_hash_lookup(struct dm_hash_table *t, const char *key)
 197 {
 198         return dm_hash_lookup_binary(t, key, strlen(key) + 1);
 199 }
 200
 201 int dm_hash_insert(struct dm_hash_table *t, const char *key, void *data)
 202 {
 203         return dm_hash_insert_binary(t, key, strlen(key) + 1, data);
 204 }
 205
 206 void dm_hash_remove(struct dm_hash_table *t, const char *key)
 207 {
 208         dm_hash_remove_binary(t, key, strlen(key) + 1);
 209 }
 210
 211 unsigned dm_hash_get_num_entries(struct dm_hash_table *t)
 212 {
 213         return t->num_nodes;
 214 }
 215
 216 void dm_hash_iter(struct dm_hash_table *t, dm_hash_iterate_fn f)
 217 {
 218         struct dm_hash_node *c, *n;
 219         unsigned i;
 220
 221         for (i = 0; i < t->num_slots; i++)
 222                 for (c = t->slots[i]; c; c = n) {
 223                         n = c->next;
 224                         f(c->data);
 225                 }
 226 }
 227
 228 void dm_hash_wipe(struct dm_hash_table *t)
 229 {
 230         _free_nodes(t);
 231         memset(t->slots, 0, sizeof(struct dm_hash_node *) * t->num_slots);
 232         t->num_nodes = 0u;
 233 }
 234
 235 char *dm_hash_get_key(struct dm_hash_table *t __attribute__((unused)),
 236                       struct dm_hash_node *n)
 237 {
 238         return n->key;
 239 }
 240
 241 void *dm_hash_get_data(struct dm_hash_table *t __attribute__((unused)),
 242                        struct dm_hash_node *n)
 243 {
 244         return n->data;
 245 }
 246
 247 static struct dm_hash_node *_next_slot(struct dm_hash_table *t, unsigned s)
 248 {
 249         struct dm_hash_node *c = NULL;
 250         unsigned i;
 251
 252         for (i = s; i < t->num_slots && !c; i++)
 253                 c = t->slots[i];
 254
 255         return c;
 256 }
 257
 258 struct dm_hash_node *dm_hash_get_first(struct dm_hash_table *t)
 259 {
 260         return _next_slot(t, 0);
 261 }
 262
 263 struct dm_hash_node *dm_hash_get_next(struct dm_hash_table *t, struct dm_hash_node *n)
 264 {
 265         unsigned h = _hash(n->key, n->keylen) & (t->num_slots - 1);
 266
 267         return n->next ? n->next : _next_slot(t, h + 1);
 268 }