Project

General

Profile

Statistics
| Branch: | Tag: | Revision:

gdp / ep / ep_hash.c @ master

History | View | Annotate | Download (5.87 KB)

1 a901db09 Eric Allman
/* vim: set ai sw=8 sts=8 ts=8 :*/
2 47c6ea64 Eric Allman
3
/***********************************************************************
4 055d3009 Eric Allman
**  ----- BEGIN LICENSE BLOCK -----
5
**        LIBEP: Enhanced Portability Library (Reduced Edition)
6
**
7 c87dd166 Eric Allman
**        Copyright (c) 2008-2019, Eric P. Allman.  All rights reserved.
8
**        Copyright (c) 2015-2019, Regents of the University of California.
9 6bd5476b Eric Allman
**        All rights reserved.
10 055d3009 Eric Allman
**
11 6bd5476b Eric Allman
**        Permission is hereby granted, without written agreement and without
12
**        license or royalty fees, to use, copy, modify, and distribute this
13
**        software and its documentation for any purpose, provided that the above
14
**        copyright notice and the following two paragraphs appear in all copies
15
**        of this software.
16 055d3009 Eric Allman
**
17 6bd5476b Eric Allman
**        IN NO EVENT SHALL REGENTS BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT,
18
**        SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST
19
**        PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION,
20
**        EVEN IF REGENTS HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
21 055d3009 Eric Allman
**
22 6bd5476b Eric Allman
**        REGENTS SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT
23 055d3009 Eric Allman
**        LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 6bd5476b Eric Allman
**        FOR A PARTICULAR PURPOSE. THE SOFTWARE AND ACCOMPANYING DOCUMENTATION,
25
**        IF ANY, PROVIDED HEREUNDER IS PROVIDED "AS IS". REGENTS HAS NO
26
**        OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS,
27
**        OR MODIFICATIONS.
28 055d3009 Eric Allman
**  ----- END LICENSE BLOCK -----
29 47c6ea64 Eric Allman
***********************************************************************/
30
31
#include <ep.h>
32
#include <ep_rpool.h>
33
#include <ep_stat.h>
34
#include <ep_assert.h>
35
#include <ep_hash.h>
36
#include <ep_string.h>
37 49c87bd9 Eric Allman
#include <ep_thr.h>
38 47c6ea64 Eric Allman
39
40
41
/***********************************************************************
42
**
43
**  HASH HANDLING
44
*/
45
46
/**************************  BEGIN PRIVATE  **************************/
47
48
struct node
49
{
50 80662ee3 Eric Allman
        size_t                        keylen;                // length of key
51 58292089 Eric Allman
        const void                *key;                // actual key
52
        const void                *val;                // value
53 47c6ea64 Eric Allman
        struct node                *next;                // next in chain
54
};
55
56
struct EP_HASH
57
{
58
        EP_RPOOL                *rpool;                // resource pool
59
        uint32_t                flags;                // flags -- see below
60 49c87bd9 Eric Allman
        EP_THR_MUTEX                mutex;                // lock on this object
61 47c6ea64 Eric Allman
        EP_HASH_HASH_FUNCP        hfunc;                // hashing function
62
        int                        tabsize;        // size of hash tab
63
        struct node                *tab[0];        // actually longer
64
};
65
66
// no flags at this time
67
68
69
int
70
def_hfunc(
71
        const EP_HASH *const hp,
72 80662ee3 Eric Allman
        const size_t keysize,
73 fc0cbc23 Eric Allman
        const void *_key)
74 47c6ea64 Eric Allman
{
75 fc0cbc23 Eric Allman
        uint8_t *key = (uint8_t *) _key;
76 47c6ea64 Eric Allman
        int hfunc = 0;
77 80662ee3 Eric Allman
        size_t i;
78 47c6ea64 Eric Allman
79
        for (i = 0; i < keysize; i++)
80
        {
81
                hfunc = ((hfunc << 1) ^ (*(uint8_t*)key++ & 0xff)) % hp->tabsize;
82
        }
83
        return hfunc;
84
}
85
86
/***************************  END PRIVATE  ***************************/
87
88
EP_HASH *
89
ep_hash_new(
90
        const char *name,
91
        EP_HASH_HASH_FUNCP hfunc,
92
        int tabsize)
93
{
94
        uint32_t flags = 0;
95
        EP_HASH *hash;
96
        EP_RPOOL *rp;
97 80662ee3 Eric Allman
        size_t xtra;
98 47c6ea64 Eric Allman
99
        if (tabsize == 0)
100
                tabsize = ep_adm_getintparam("libep.hash.tabsize", 2003);
101 9e55d093 Eric Allman
        if (name == NULL)
102 47c6ea64 Eric Allman
                name = "<hash>";
103 9e55d093 Eric Allman
        if (hfunc == NULL)
104 47c6ea64 Eric Allman
                hfunc = def_hfunc;
105
106
        EP_ASSERT(tabsize >= 2);
107
108
        rp = ep_rpool_new(name, (size_t) 0);
109
110
        // figure how much extra space we need to allocate for table
111
        xtra = tabsize * sizeof hash->tab[0];
112
113 fc0cbc23 Eric Allman
        hash = (EP_HASH *) ep_rpool_zalloc(rp, sizeof *hash + xtra);
114 47c6ea64 Eric Allman
        hash->rpool = rp;
115
        hash->hfunc = hfunc;
116
        hash->flags = flags;
117
        hash->tabsize = tabsize;
118 51775f02 Eric Allman
        ep_thr_mutex_init(&hash->mutex, EP_THR_MUTEX_DEFAULT);
119 47c6ea64 Eric Allman
120
        return hash;
121
}
122
123
124
void
125
ep_hash_free(EP_HASH *hash)
126
{
127
        EP_ASSERT_POINTER_VALID(hash);
128 49c87bd9 Eric Allman
        ep_thr_mutex_destroy(&hash->mutex);
129 47c6ea64 Eric Allman
        ep_rpool_free(hash->rpool);        // also frees hash
130
}
131
132
133 0c663d10 Eric Allman
struct node **
134
find_node_ptr(EP_HASH *hp,
135 80662ee3 Eric Allman
        size_t keylen,
136 47c6ea64 Eric Allman
        const void *key)
137
{
138
        int indx;
139 0c663d10 Eric Allman
        struct node **npp;
140 47c6ea64 Eric Allman
        struct node *n;
141
142
        indx = hp->hfunc(hp, keylen, key);
143 0c663d10 Eric Allman
        npp = &hp->tab[indx];
144 47c6ea64 Eric Allman
145 0c663d10 Eric Allman
        for (n = *npp; n != NULL; npp = &n->next, n = *npp)
146 47c6ea64 Eric Allman
        {
147
                if (keylen == n->keylen &&
148
                    memcmp(key, n->key, keylen) == 0)
149
                {
150
                        // match
151 0c663d10 Eric Allman
                        break;
152 47c6ea64 Eric Allman
                }
153
        }
154 0c663d10 Eric Allman
155
        return npp;
156
}
157
158
159 58292089 Eric Allman
const void *
160 0c663d10 Eric Allman
ep_hash_search(
161
        EP_HASH *hp,
162 80662ee3 Eric Allman
        size_t keylen,
163 0c663d10 Eric Allman
        const void *key)
164
{
165
        struct node **npp;
166 58292089 Eric Allman
        const void *val;
167 0c663d10 Eric Allman
168
        EP_ASSERT_POINTER_VALID(hp);
169
170 0314a7a7 Eric Allman
        ep_thr_mutex_lock(&hp->mutex);
171 0c663d10 Eric Allman
        npp = find_node_ptr(hp, keylen, key);
172
        if (*npp == NULL)
173 0314a7a7 Eric Allman
                val = NULL;
174 0c663d10 Eric Allman
        else
175 0314a7a7 Eric Allman
                val = (*npp)->val;
176
        ep_thr_mutex_unlock(&hp->mutex);
177
        return val;
178 47c6ea64 Eric Allman
}
179
180
181 58292089 Eric Allman
const void *
182 47c6ea64 Eric Allman
ep_hash_insert(
183
        EP_HASH *hp,
184 80662ee3 Eric Allman
        size_t keylen,
185 47c6ea64 Eric Allman
        const void *key,
186 58292089 Eric Allman
        const void *val)
187 47c6ea64 Eric Allman
{
188 0c663d10 Eric Allman
        struct node **npp;
189 47c6ea64 Eric Allman
        struct node *n;
190
        void *kp;
191
192
        EP_ASSERT_POINTER_VALID(hp);
193
194 0314a7a7 Eric Allman
        ep_thr_mutex_lock(&hp->mutex);
195 0c663d10 Eric Allman
        npp = find_node_ptr(hp, keylen, key);
196
        if (*npp != NULL)
197 47c6ea64 Eric Allman
        {
198 0c663d10 Eric Allman
                // there is an existing value; replace it
199 58292089 Eric Allman
                const void *oldval;
200 47c6ea64 Eric Allman
201 0c663d10 Eric Allman
                n = *npp;
202
                oldval = n->val;
203
                n->val = val;
204 0314a7a7 Eric Allman
                ep_thr_mutex_unlock(&hp->mutex);
205 0c663d10 Eric Allman
                return oldval;
206 47c6ea64 Eric Allman
        }
207
208
        // not found -- insert it
209 fc0cbc23 Eric Allman
        n = (struct node *) ep_rpool_malloc(hp->rpool, sizeof *n);
210 47c6ea64 Eric Allman
        n->keylen = keylen;
211
        kp = ep_rpool_malloc(hp->rpool, keylen);
212
        memcpy(kp, key, keylen);
213
        n->key = kp;
214
        n->val = val;
215 0c663d10 Eric Allman
        n->next = NULL;
216
        *npp = n;
217 0314a7a7 Eric Allman
        ep_thr_mutex_unlock(&hp->mutex);
218 9e55d093 Eric Allman
        return NULL;
219 47c6ea64 Eric Allman
}
220
221
222 58292089 Eric Allman
const void *
223 0c663d10 Eric Allman
ep_hash_delete(
224
        EP_HASH *hp,
225 80662ee3 Eric Allman
        size_t keylen,
226 0c663d10 Eric Allman
        const void *key)
227
{
228
        struct node **npp;
229
        struct node *n;
230 58292089 Eric Allman
        const void *v;
231 0c663d10 Eric Allman
232
        EP_ASSERT_POINTER_VALID(hp);
233
234 0314a7a7 Eric Allman
        ep_thr_mutex_lock(&hp->mutex);
235 0c663d10 Eric Allman
        npp = find_node_ptr(hp, keylen, key);
236
        if (*npp == NULL)
237
        {
238
                // entry does not exist
239 0314a7a7 Eric Allman
                ep_thr_mutex_unlock(&hp->mutex);
240 0c663d10 Eric Allman
                return NULL;
241
        }
242
243
        n = *npp;
244
        v = n->val;
245 58283344 Eric Allman
        n->val = NULL;
246
247
        // since ep_rpool_mfree doesn't free yet, leave this node in
248
        // the list to allow re-use of the key without losing more memory
249
        //*npp = n->next;
250
        //ep_rpool_mfree(hp->rpool, n->key);
251
        //ep_rpool_mfree(hp->rpool, n);
252
253 0314a7a7 Eric Allman
        ep_thr_mutex_unlock(&hp->mutex);
254 0c663d10 Eric Allman
        return v;
255
}
256
257
258 47c6ea64 Eric Allman
/*
259
**  EP_HASH_FORALL -- apply a function to all nodes
260
*/
261
262
void
263
ep_hash_forall(
264
        EP_HASH *hp,
265
        EP_HASH_FORALL_FUNCP func,
266
        ...)
267
{
268
        va_list av;
269
        struct node *n;
270
        int i;
271
272
        va_start(av, func);
273
274
        EP_ASSERT_POINTER_VALID(hp);
275
276 0314a7a7 Eric Allman
        ep_thr_mutex_lock(&hp->mutex);
277 47c6ea64 Eric Allman
        for (i = 0; i < hp->tabsize; i++)
278
        {
279 458b37ea Eric Allman
                struct node *next;
280
                for (n = hp->tab[i]; n != NULL; n = next)
281 47c6ea64 Eric Allman
                {
282
                        va_list lav;
283 458b37ea Eric Allman
                        next = n->next;
284 47c6ea64 Eric Allman
285
                        va_copy(lav, av);
286
                        (*func)(n->keylen, n->key, n->val, lav);
287
                }
288
        }
289
290
        va_end(av);
291 0314a7a7 Eric Allman
        ep_thr_mutex_unlock(&hp->mutex);
292 47c6ea64 Eric Allman
}