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