lhash.c revision 296465 
1/* crypto/lhash/lhash.c */
2/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved.
4 *
5 * This package is an SSL implementation written
6 * by Eric Young (eay@cryptsoft.com).
7 * The implementation was written so as to conform with Netscapes SSL.
8 *
9 * This library is free for commercial and non-commercial use as long as
10 * the following conditions are aheared to.  The following conditions
11 * apply to all code found in this distribution, be it the RC4, RSA,
12 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
13 * included with this distribution is covered by the same copyright terms
14 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 *
16 * Copyright remains Eric Young's, and as such any Copyright notices in
17 * the code are not to be removed.
18 * If this package is used in a product, Eric Young should be given attribution
19 * as the author of the parts of the library used.
20 * This can be in the form of a textual message at program startup or
21 * in documentation (online or textual) provided with the package.
22 *
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions
25 * are met:
26 * 1. Redistributions of source code must retain the copyright
27 *    notice, this list of conditions and the following disclaimer.
28 * 2. Redistributions in binary form must reproduce the above copyright
29 *    notice, this list of conditions and the following disclaimer in the
30 *    documentation and/or other materials provided with the distribution.
31 * 3. All advertising materials mentioning features or use of this software
32 *    must display the following acknowledgement:
33 *    "This product includes cryptographic software written by
34 *     Eric Young (eay@cryptsoft.com)"
35 *    The word 'cryptographic' can be left out if the rouines from the library
36 *    being used are not cryptographic related :-).
37 * 4. If you include any Windows specific code (or a derivative thereof) from
38 *    the apps directory (application code) you must include an acknowledgement:
39 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 *
41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51 * SUCH DAMAGE.
52 *
53 * The licence and distribution terms for any publically available version or
54 * derivative of this code cannot be changed.  i.e. this code cannot simply be
55 * copied and put under another distribution licence
56 * [including the GNU Public Licence.]
57 */
58
59/*-
60 * Code for dynamic hash table routines
61 * Author - Eric Young v 2.0
62 *
63 * 2.2 eay - added #include "crypto.h" so the memory leak checking code is
64 *           present. eay 18-Jun-98
65 *
66 * 2.1 eay - Added an 'error in last operation' flag. eay 6-May-98
67 *
68 * 2.0 eay - Fixed a bug that occurred when using lh_delete
69 *           from inside lh_doall().  As entries were deleted,
70 *           the 'table' was 'contract()ed', making some entries
71 *           jump from the end of the table to the start, there by
72 *           skipping the lh_doall() processing. eay - 4/12/95
73 *
74 * 1.9 eay - Fixed a memory leak in lh_free, the LHASH_NODEs
75 *           were not being free()ed. 21/11/95
76 *
77 * 1.8 eay - Put the stats routines into a separate file, lh_stats.c
78 *           19/09/95
79 *
80 * 1.7 eay - Removed the fputs() for realloc failures - the code
81 *           should silently tolerate them.  I have also fixed things
82 *           lint complained about 04/05/95
83 *
84 * 1.6 eay - Fixed an invalid pointers in contract/expand 27/07/92
85 *
86 * 1.5 eay - Fixed a misuse of realloc in expand 02/03/1992
87 *
88 * 1.4 eay - Fixed lh_doall so the function can call lh_delete 28/05/91
89 *
90 * 1.3 eay - Fixed a few lint problems 19/3/1991
91 *
92 * 1.2 eay - Fixed lh_doall problem 13/3/1991
93 *
94 * 1.1 eay - Added lh_doall
95 *
96 * 1.0 eay - First version
97 */
98#include <stdio.h>
99#include <string.h>
100#include <stdlib.h>
101#include <openssl/crypto.h>
102#include <openssl/lhash.h>
103
104const char lh_version[] = "lhash" OPENSSL_VERSION_PTEXT;
105
106#undef MIN_NODES
107#define MIN_NODES       16
108#define UP_LOAD         (2*LH_LOAD_MULT) /* load times 256 (default 2) */
109#define DOWN_LOAD       (LH_LOAD_MULT) /* load times 256 (default 1) */
110
111static void expand(LHASH *lh);
112static void contract(LHASH *lh);
113static LHASH_NODE **getrn(LHASH *lh, const void *data, unsigned long *rhash);
114
115LHASH *lh_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c)
116{
117    LHASH *ret;
118    int i;
119
120    if ((ret = (LHASH *)OPENSSL_malloc(sizeof(LHASH))) == NULL)
121        goto err0;
122    if ((ret->b =
123         (LHASH_NODE **)OPENSSL_malloc(sizeof(LHASH_NODE *) * MIN_NODES)) ==
124        NULL)
125        goto err1;
126    for (i = 0; i < MIN_NODES; i++)
127        ret->b[i] = NULL;
128    ret->comp = ((c == NULL) ? (LHASH_COMP_FN_TYPE)strcmp : c);
129    ret->hash = ((h == NULL) ? (LHASH_HASH_FN_TYPE)lh_strhash : h);
130    ret->num_nodes = MIN_NODES / 2;
131    ret->num_alloc_nodes = MIN_NODES;
132    ret->p = 0;
133    ret->pmax = MIN_NODES / 2;
134    ret->up_load = UP_LOAD;
135    ret->down_load = DOWN_LOAD;
136    ret->num_items = 0;
137
138    ret->num_expands = 0;
139    ret->num_expand_reallocs = 0;
140    ret->num_contracts = 0;
141    ret->num_contract_reallocs = 0;
142    ret->num_hash_calls = 0;
143    ret->num_comp_calls = 0;
144    ret->num_insert = 0;
145    ret->num_replace = 0;
146    ret->num_delete = 0;
147    ret->num_no_delete = 0;
148    ret->num_retrieve = 0;
149    ret->num_retrieve_miss = 0;
150    ret->num_hash_comps = 0;
151
152    ret->error = 0;
153    return (ret);
154 err1:
155    OPENSSL_free(ret);
156 err0:
157    return (NULL);
158}
159
160void lh_free(LHASH *lh)
161{
162    unsigned int i;
163    LHASH_NODE *n, *nn;
164
165    if (lh == NULL)
166        return;
167
168    for (i = 0; i < lh->num_nodes; i++) {
169        n = lh->b[i];
170        while (n != NULL) {
171            nn = n->next;
172            OPENSSL_free(n);
173            n = nn;
174        }
175    }
176    OPENSSL_free(lh->b);
177    OPENSSL_free(lh);
178}
179
180void *lh_insert(LHASH *lh, void *data)
181{
182    unsigned long hash;
183    LHASH_NODE *nn, **rn;
184    void *ret;
185
186    lh->error = 0;
187    if (lh->up_load <= (lh->num_items * LH_LOAD_MULT / lh->num_nodes))
188        expand(lh);
189
190    rn = getrn(lh, data, &hash);
191
192    if (*rn == NULL) {
193        if ((nn = (LHASH_NODE *)OPENSSL_malloc(sizeof(LHASH_NODE))) == NULL) {
194            lh->error++;
195            return (NULL);
196        }
197        nn->data = data;
198        nn->next = NULL;
199#ifndef OPENSSL_NO_HASH_COMP
200        nn->hash = hash;
201#endif
202        *rn = nn;
203        ret = NULL;
204        lh->num_insert++;
205        lh->num_items++;
206    } else {                    /* replace same key */
207
208        ret = (*rn)->data;
209        (*rn)->data = data;
210        lh->num_replace++;
211    }
212    return (ret);
213}
214
215void *lh_delete(LHASH *lh, const void *data)
216{
217    unsigned long hash;
218    LHASH_NODE *nn, **rn;
219    void *ret;
220
221    lh->error = 0;
222    rn = getrn(lh, data, &hash);
223
224    if (*rn == NULL) {
225        lh->num_no_delete++;
226        return (NULL);
227    } else {
228        nn = *rn;
229        *rn = nn->next;
230        ret = nn->data;
231        OPENSSL_free(nn);
232        lh->num_delete++;
233    }
234
235    lh->num_items--;
236    if ((lh->num_nodes > MIN_NODES) &&
237        (lh->down_load >= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)))
238        contract(lh);
239
240    return (ret);
241}
242
243void *lh_retrieve(LHASH *lh, const void *data)
244{
245    unsigned long hash;
246    LHASH_NODE **rn;
247    void *ret;
248
249    lh->error = 0;
250    rn = getrn(lh, data, &hash);
251
252    if (*rn == NULL) {
253        lh->num_retrieve_miss++;
254        return (NULL);
255    } else {
256        ret = (*rn)->data;
257        lh->num_retrieve++;
258    }
259    return (ret);
260}
261
262static void doall_util_fn(LHASH *lh, int use_arg, LHASH_DOALL_FN_TYPE func,
263                          LHASH_DOALL_ARG_FN_TYPE func_arg, void *arg)
264{
265    int i;
266    LHASH_NODE *a, *n;
267
268    /*
269     * reverse the order so we search from 'top to bottom' We were having
270     * memory leaks otherwise
271     */
272    for (i = lh->num_nodes - 1; i >= 0; i--) {
273        a = lh->b[i];
274        while (a != NULL) {
275            /*
276             * 28/05/91 - eay - n added so items can be deleted via lh_doall
277             */
278            n = a->next;
279            if (use_arg)
280                func_arg(a->data, arg);
281            else
282                func(a->data);
283            a = n;
284        }
285    }
286}
287
288void lh_doall(LHASH *lh, LHASH_DOALL_FN_TYPE func)
289{
290    doall_util_fn(lh, 0, func, (LHASH_DOALL_ARG_FN_TYPE)0, NULL);
291}
292
293void lh_doall_arg(LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg)
294{
295    doall_util_fn(lh, 1, (LHASH_DOALL_FN_TYPE)0, func, arg);
296}
297
298static void expand(LHASH *lh)
299{
300    LHASH_NODE **n, **n1, **n2, *np;
301    unsigned int p, i, j, pmax;
302    unsigned long hash, nni;
303
304    p = (int)lh->p++;
305    nni = lh->num_alloc_nodes;
306    pmax = lh->pmax;
307
308    if ((lh->p) >= lh->pmax) {
309        j = (int)lh->num_alloc_nodes * 2;
310        n = (LHASH_NODE **)OPENSSL_realloc(lh->b,
311                                           (int)sizeof(LHASH_NODE *) * j);
312        if (n == NULL) {
313/*                      fputs("realloc error in lhash",stderr); */
314            lh->error++;
315            lh->p = 0;
316            return;
317        }
318        /* else */
319        for (i = (int)lh->num_alloc_nodes; i < j; i++) /* 26/02/92 eay */
320            n[i] = NULL;        /* 02/03/92 eay */
321        lh->pmax = lh->num_alloc_nodes;
322        lh->num_alloc_nodes = j;
323        lh->num_expand_reallocs++;
324        lh->p = 0;
325        lh->b = n;
326    }
327
328    lh->num_nodes++;
329    lh->num_expands++;
330    n1 = &(lh->b[p]);
331    n2 = &(lh->b[p + pmax]);
332    *n2 = NULL;                 /* 27/07/92 - eay - undefined pointer bug */
333
334    for (np = *n1; np != NULL;) {
335#ifndef OPENSSL_NO_HASH_COMP
336        hash = np->hash;
337#else
338        hash = lh->hash(np->data);
339        lh->num_hash_calls++;
340#endif
341        if ((hash % nni) != p) { /* move it */
342            *n1 = (*n1)->next;
343            np->next = *n2;
344            *n2 = np;
345        } else
346            n1 = &((*n1)->next);
347        np = *n1;
348    }
349
350}
351
352static void contract(LHASH *lh)
353{
354    LHASH_NODE **n, *n1, *np;
355    int idx = lh->p + lh->pmax - 1;
356
357    np = lh->b[idx];
358    if (lh->p == 0) {
359        n = (LHASH_NODE **)OPENSSL_realloc(lh->b,
360                                           (unsigned int)(sizeof(LHASH_NODE *)
361                                                          * lh->pmax));
362        if (n == NULL) {
363/*                      fputs("realloc error in lhash",stderr); */
364            lh->error++;
365            return;
366        }
367        lh->num_contract_reallocs++;
368        lh->num_alloc_nodes /= 2;
369        lh->pmax /= 2;
370        lh->p = lh->pmax - 1;
371        lh->b = n;
372    } else
373        lh->p--;
374
375    lh->b[idx] = NULL;
376    lh->num_nodes--;
377    lh->num_contracts++;
378
379    n1 = lh->b[(int)lh->p];
380    if (n1 == NULL)
381        lh->b[(int)lh->p] = np;
382    else {
383        while (n1->next != NULL)
384            n1 = n1->next;
385        n1->next = np;
386    }
387}
388
389static LHASH_NODE **getrn(LHASH *lh, const void *data, unsigned long *rhash)
390{
391    LHASH_NODE **ret, *n1;
392    unsigned long hash, nn;
393    LHASH_COMP_FN_TYPE cf;
394
395    hash = (*(lh->hash)) (data);
396    lh->num_hash_calls++;
397    *rhash = hash;
398
399    nn = hash % lh->pmax;
400    if (nn < lh->p)
401        nn = hash % lh->num_alloc_nodes;
402
403    cf = lh->comp;
404    ret = &(lh->b[(int)nn]);
405    for (n1 = *ret; n1 != NULL; n1 = n1->next) {
406#ifndef OPENSSL_NO_HASH_COMP
407        lh->num_hash_comps++;
408        if (n1->hash != hash) {
409            ret = &(n1->next);
410            continue;
411        }
412#endif
413        lh->num_comp_calls++;
414        if (cf(n1->data, data) == 0)
415            break;
416        ret = &(n1->next);
417    }
418    return (ret);
419}
420
421/*
422 * The following hash seems to work very well on normal text strings no
423 * collisions on /usr/dict/words and it distributes on %2^n quite well, not
424 * as good as MD5, but still good.
425 */
426unsigned long lh_strhash(const char *c)
427{
428    unsigned long ret = 0;
429    long n;
430    unsigned long v;
431    int r;
432
433    if ((c == NULL) || (*c == '\0'))
434        return (ret);
435/*-
436    unsigned char b[16];
437    MD5(c,strlen(c),b);
438    return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24));
439*/
440
441    n = 0x100;
442    while (*c) {
443        v = n | (*c);
444        n += 0x100;
445        r = (int)((v >> 2) ^ v) & 0x0f;
446        ret = (ret << r) | (ret >> (32 - r));
447        ret &= 0xFFFFFFFFL;
448        ret ^= v * v;
449        c++;
450    }
451    return ((ret >> 16) ^ ret);
452}
453
454unsigned long lh_num_items(const LHASH *lh)
455{
456    return lh ? lh->num_items : 0;
457}
458