contrib/lvm2/dist/libdm/datastruct/hash.c

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