chiark / gitweb /
Merge mac build fix
[disorder] / lib / hash.c
1 /*
2  * This file is part of DisOrder
3  * Copyright (C) 2005-2008 Richard Kettlewell
4  *
5  * This program is free software: you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation, either version 3 of the License, or
8  * (at your option) any later version.
9  * 
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  * 
15  * You should have received a copy of the GNU General Public License
16  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
17  */
18 /** @file lib/hash.c
19  * @brief A simple hash table
20  */
21 #include "common.h"
22
23 #include "hash.h"
24 #include "mem.h"
25 #include "log.h"
26 #include "kvp.h"
27
28 struct entry {
29   struct entry *next;                   /* next entry same key */
30   size_t h;                             /* hash of KEY */
31   const char *key;                      /* key of this entry */
32   void *value;                          /* value of this entry */
33 };
34
35 struct hash {
36   size_t nslots;                        /* number of slots */
37   size_t nitems;                        /* total number of entries */
38   struct entry **slots;                 /* table of slots */
39   size_t valuesize;                     /* size of a value */
40 };
41
42 /** @brief Hash function
43  * @param key Key to hash
44  * @return Hash code
45  */
46 static size_t hashfn(const char *key) {
47   size_t i = 0;
48
49   while(*key)
50     i = 33 * i + (unsigned char)*key++;
51   return i;
52 }
53
54 /** @brief Expand a hash table
55  * @param h Hash table to expand
56  */
57 static void grow(hash *h) {
58   size_t n, newnslots;
59   struct entry **newslots, *e, *f;
60
61   /* Allocate a new, larger array */
62   newnslots = 2 * h->nslots;
63   newslots = xcalloc(newnslots, sizeof (struct entry *));
64   /* Copy everything to it */
65   for(n = 0; n < h->nslots; ++n) {
66     for(e = h->slots[n]; e; e = f) {
67       f = e->next;
68       e->next = newslots[e->h & (newnslots - 1)];
69       newslots[e->h & (newnslots - 1)] = e;
70     }
71   }
72   h->slots = newslots;
73   h->nslots = newnslots;
74 }
75
76 /** @brief Create a new hash table
77  * @param valuesize Size of value type
78  * @return Hash table
79  */
80 hash *hash_new(size_t valuesize) {
81   hash *h = xmalloc(sizeof *h);
82
83   h->nslots = 256;
84   h->slots = xcalloc(h->nslots, sizeof (struct slot *));
85   h->valuesize = valuesize;
86   return h;
87 }
88
89 /** @brief Add an element to a hash table
90  * @param h Hash table
91  * @param key Key
92  * @param value New value (will be shallow-copied)
93  * @param mode Add mode
94  * @return 0 on success, -1 if the value could not be added
95  *
96  * Possible add modes are:
97  * - @ref HASH_INSERT - key must not exist yet
98  * - @ref HASH_REPLACE - key must already exist
99  * - @ref HASH_INSERT_OR_REPLACE - key may or may not exist
100  */
101 int hash_add(hash *h, const char *key, const void *value, int mode) {
102   size_t n = hashfn(key);
103   struct entry *e;
104   
105   for(e = h->slots[n & (h->nslots - 1)]; e; e = e->next)
106     if(e->h == n || !strcmp(e->key, key))
107       break;
108   if(e) {
109     /* This key is already present. */
110     if(mode == HASH_INSERT) return -1;
111     if(value) memcpy(e->value, value, h->valuesize);
112     return 0;
113   } else {
114     /* This key is absent. */
115     if(mode == HASH_REPLACE) return -1;
116     if(h->nitems >= h->nslots)          /* bound mean chain length */
117       grow(h);
118     e = xmalloc(sizeof *e);
119     e->next = h->slots[n & (h->nslots - 1)];
120     e->h = n;
121     e->key = xstrdup(key);
122     e->value = xmalloc(h->valuesize);
123     if(value) memcpy(e->value, value, h->valuesize);
124     h->slots[n & (h->nslots - 1)] = e;
125     ++h->nitems;
126     return 0;
127   }
128 }
129
130 /** @brief Remove an element from a hash table
131  * @param h Hash table
132  * @param key Key to remove
133  * @return 0 on success, -1 if the key wasn't found
134  */
135 int hash_remove(hash *h, const char *key) {
136   size_t n = hashfn(key);
137   struct entry *e, **ee;
138   
139   for(ee = &h->slots[n & (h->nslots - 1)]; (e = *ee); ee = &e->next)
140     if(e->h == n || !strcmp(e->key, key))
141       break;
142   if(e) {
143     *ee = e->next;
144     --h->nitems;
145     return 0;
146   } else
147     return -1;
148 }
149
150 /** @brief Find an item in a hash table
151  * @param h Hash table
152  * @param key Key to find
153  * @return Pointer to value or NULL if not found
154  *
155  * The return value points inside the hash table and should not be modified.
156  */
157 void *hash_find(hash *h, const char *key) {
158   size_t n = hashfn(key);
159   struct entry *e;
160
161   for(e = h->slots[n & (h->nslots - 1)]; e; e = e->next)
162     if(e->h == n || !strcmp(e->key, key))
163       return e->value;
164   return 0;
165 }
166
167 /** @brief Visit every item in a hash table
168  * @param h Hash Table
169  * @param callback Function to call for each item
170  * @param u Passed to @p callback
171  * @return 0 on completion, else last return from @p callback
172  *
173  * @p callback should return 0 to continue or non-0 to stop.  The @p key and @p
174  * value pointers passed to it point into the hash table and should not be
175  * modified.
176  *
177  * It's safe to remove items from inside the callback including the visited
178  * one.  It is not safe to add items from inside the callback.
179  *
180  * No particular ordering is used.
181  */
182 int hash_foreach(hash *h,
183                  int (*callback)(const char *key, void *value, void *u),
184                  void *u) {
185   size_t n;
186   int ret;
187   struct entry *e, *f;
188
189   for(n = 0; n < h->nslots; ++n)
190     for(e = h->slots[n]; e; e = f) {
191       f = e->next;
192       if((ret = callback(e->key, e->value, u)))
193         return ret;
194     }
195   return 0;
196 }
197
198 /** @brief Count the size of a hash table
199  * @param h Hash table
200  * @return Number of elements in hash table
201  */
202 size_t hash_count(hash *h) {
203   return h->nitems;
204 }
205
206 /** @brief Get all the keys of a hash table
207  * @param h Hash table
208  * @return NULL-terminated list of keys
209  *
210  * The keys point into the hash table itself and should not be modified.
211  *
212  * No particular ordering is used.
213  */
214 char **hash_keys(hash *h) {
215   size_t n;
216   char **vec = xcalloc(h->nitems + 1, sizeof (char *)), **vp = vec;
217   struct entry *e;
218
219   for(n = 0; n < h->nslots; ++n)
220     for(e = h->slots[n]; e; e = e->next)
221       *vp++ = (char *)e->key;
222   *vp = 0;
223   return vec;
224 }
225
226 /*
227 Local Variables:
228 c-basic-offset:2
229 comment-column:40
230 fill-column:79
231 indent-tabs-mode:nil
232 End:
233 */