Project

General

Profile

Statistics
| Branch: | Tag: | Revision:

gdp / ep / ep_hash.c @ master

History | View | Annotate | Download (5.87 KB)

1
/* vim: set ai sw=8 sts=8 ts=8 :*/
2

    
3
/***********************************************************************
4
**  ----- BEGIN LICENSE BLOCK -----
5
**        LIBEP: Enhanced Portability Library (Reduced Edition)
6
**
7
**        Copyright (c) 2008-2019, Eric P. Allman.  All rights reserved.
8
**        Copyright (c) 2015-2019, Regents of the University of California.
9
**        All rights reserved.
10
**
11
**        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
**
17
**        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
**
22
**        REGENTS SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT
23
**        LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24
**        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
**  ----- END LICENSE BLOCK -----
29
***********************************************************************/
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
#include <ep_thr.h>
38

    
39

    
40

    
41
/***********************************************************************
42
**
43
**  HASH HANDLING
44
*/
45

    
46
/**************************  BEGIN PRIVATE  **************************/
47

    
48
struct node
49
{
50
        size_t                        keylen;                // length of key
51
        const void                *key;                // actual key
52
        const void                *val;                // value
53
        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
        EP_THR_MUTEX                mutex;                // lock on this object
61
        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
        const size_t keysize,
73
        const void *_key)
74
{
75
        uint8_t *key = (uint8_t *) _key;
76
        int hfunc = 0;
77
        size_t i;
78

    
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
        size_t xtra;
98

    
99
        if (tabsize == 0)
100
                tabsize = ep_adm_getintparam("libep.hash.tabsize", 2003);
101
        if (name == NULL)
102
                name = "<hash>";
103
        if (hfunc == NULL)
104
                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
        hash = (EP_HASH *) ep_rpool_zalloc(rp, sizeof *hash + xtra);
114
        hash->rpool = rp;
115
        hash->hfunc = hfunc;
116
        hash->flags = flags;
117
        hash->tabsize = tabsize;
118
        ep_thr_mutex_init(&hash->mutex, EP_THR_MUTEX_DEFAULT);
119

    
120
        return hash;
121
}
122

    
123

    
124
void
125
ep_hash_free(EP_HASH *hash)
126
{
127
        EP_ASSERT_POINTER_VALID(hash);
128
        ep_thr_mutex_destroy(&hash->mutex);
129
        ep_rpool_free(hash->rpool);        // also frees hash
130
}
131

    
132

    
133
struct node **
134
find_node_ptr(EP_HASH *hp,
135
        size_t keylen,
136
        const void *key)
137
{
138
        int indx;
139
        struct node **npp;
140
        struct node *n;
141

    
142
        indx = hp->hfunc(hp, keylen, key);
143
        npp = &hp->tab[indx];
144

    
145
        for (n = *npp; n != NULL; npp = &n->next, n = *npp)
146
        {
147
                if (keylen == n->keylen &&
148
                    memcmp(key, n->key, keylen) == 0)
149
                {
150
                        // match
151
                        break;
152
                }
153
        }
154

    
155
        return npp;
156
}
157

    
158

    
159
const void *
160
ep_hash_search(
161
        EP_HASH *hp,
162
        size_t keylen,
163
        const void *key)
164
{
165
        struct node **npp;
166
        const void *val;
167

    
168
        EP_ASSERT_POINTER_VALID(hp);
169

    
170
        ep_thr_mutex_lock(&hp->mutex);
171
        npp = find_node_ptr(hp, keylen, key);
172
        if (*npp == NULL)
173
                val = NULL;
174
        else
175
                val = (*npp)->val;
176
        ep_thr_mutex_unlock(&hp->mutex);
177
        return val;
178
}
179

    
180

    
181
const void *
182
ep_hash_insert(
183
        EP_HASH *hp,
184
        size_t keylen,
185
        const void *key,
186
        const void *val)
187
{
188
        struct node **npp;
189
        struct node *n;
190
        void *kp;
191

    
192
        EP_ASSERT_POINTER_VALID(hp);
193

    
194
        ep_thr_mutex_lock(&hp->mutex);
195
        npp = find_node_ptr(hp, keylen, key);
196
        if (*npp != NULL)
197
        {
198
                // there is an existing value; replace it
199
                const void *oldval;
200

    
201
                n = *npp;
202
                oldval = n->val;
203
                n->val = val;
204
                ep_thr_mutex_unlock(&hp->mutex);
205
                return oldval;
206
        }
207

    
208
        // not found -- insert it
209
        n = (struct node *) ep_rpool_malloc(hp->rpool, sizeof *n);
210
        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
        n->next = NULL;
216
        *npp = n;
217
        ep_thr_mutex_unlock(&hp->mutex);
218
        return NULL;
219
}
220

    
221

    
222
const void *
223
ep_hash_delete(
224
        EP_HASH *hp,
225
        size_t keylen,
226
        const void *key)
227
{
228
        struct node **npp;
229
        struct node *n;
230
        const void *v;
231

    
232
        EP_ASSERT_POINTER_VALID(hp);
233

    
234
        ep_thr_mutex_lock(&hp->mutex);
235
        npp = find_node_ptr(hp, keylen, key);
236
        if (*npp == NULL)
237
        {
238
                // entry does not exist
239
                ep_thr_mutex_unlock(&hp->mutex);
240
                return NULL;
241
        }
242

    
243
        n = *npp;
244
        v = n->val;
245
        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
        ep_thr_mutex_unlock(&hp->mutex);
254
        return v;
255
}
256

    
257

    
258
/*
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
        ep_thr_mutex_lock(&hp->mutex);
277
        for (i = 0; i < hp->tabsize; i++)
278
        {
279
                struct node *next;
280
                for (n = hp->tab[i]; n != NULL; n = next)
281
                {
282
                        va_list lav;
283
                        next = n->next;
284

    
285
                        va_copy(lav, av);
286
                        (*func)(n->keylen, n->key, n->val, lav);
287
                }
288
        }
289

    
290
        va_end(av);
291
        ep_thr_mutex_unlock(&hp->mutex);
292
}