xref: /dragonfly/crypto/libressl/crypto/lhash/lhash.c (revision cca6fc52)
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