summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/lhash
diff options
context:
space:
mode:
authorcvs2svn <admin@example.com>2007-03-01 16:29:10 +0000
committercvs2svn <admin@example.com>2007-03-01 16:29:10 +0000
commitd92cde8050488a0c87c357c4756a89026b6659ee (patch)
tree737670254ff24eff6f6dddb0b97cae8c0ba8c571 /src/lib/libcrypto/lhash
parent9c4b4ca341957016adebec4e1eb2446cf0261241 (diff)
downloadopenbsd-OPENBSD_4_1_BASE.tar.gz
openbsd-OPENBSD_4_1_BASE.tar.bz2
openbsd-OPENBSD_4_1_BASE.zip
This commit was manufactured by cvs2git to create tag 'OPENBSD_4_1_BASE'.OPENBSD_4_1_BASE
Diffstat (limited to 'src/lib/libcrypto/lhash')
-rw-r--r--src/lib/libcrypto/lhash/lh_stats.c248
-rw-r--r--src/lib/libcrypto/lhash/lhash.c470
-rw-r--r--src/lib/libcrypto/lhash/lhash.h199
3 files changed, 0 insertions, 917 deletions
diff --git a/src/lib/libcrypto/lhash/lh_stats.c b/src/lib/libcrypto/lhash/lh_stats.c
deleted file mode 100644
index 5aa7766aa6..0000000000
--- a/src/lib/libcrypto/lhash/lh_stats.c
+++ /dev/null
@@ -1,248 +0,0 @@
1/* crypto/lhash/lh_stats.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#include <stdio.h>
60#include <string.h>
61#include <stdlib.h>
62/* If you wish to build this outside of SSLeay, remove the following lines
63 * and things should work as expected */
64#include "cryptlib.h"
65
66#ifndef OPENSSL_NO_BIO
67#include <openssl/bio.h>
68#endif
69#include <openssl/lhash.h>
70
71#ifdef OPENSSL_NO_BIO
72
73void lh_stats(LHASH *lh, FILE *out)
74 {
75 fprintf(out,"num_items = %lu\n",lh->num_items);
76 fprintf(out,"num_nodes = %u\n",lh->num_nodes);
77 fprintf(out,"num_alloc_nodes = %u\n",lh->num_alloc_nodes);
78 fprintf(out,"num_expands = %lu\n",lh->num_expands);
79 fprintf(out,"num_expand_reallocs = %lu\n",lh->num_expand_reallocs);
80 fprintf(out,"num_contracts = %lu\n",lh->num_contracts);
81 fprintf(out,"num_contract_reallocs = %lu\n",lh->num_contract_reallocs);
82 fprintf(out,"num_hash_calls = %lu\n",lh->num_hash_calls);
83 fprintf(out,"num_comp_calls = %lu\n",lh->num_comp_calls);
84 fprintf(out,"num_insert = %lu\n",lh->num_insert);
85 fprintf(out,"num_replace = %lu\n",lh->num_replace);
86 fprintf(out,"num_delete = %lu\n",lh->num_delete);
87 fprintf(out,"num_no_delete = %lu\n",lh->num_no_delete);
88 fprintf(out,"num_retrieve = %lu\n",lh->num_retrieve);
89 fprintf(out,"num_retrieve_miss = %lu\n",lh->num_retrieve_miss);
90 fprintf(out,"num_hash_comps = %lu\n",lh->num_hash_comps);
91#if 0
92 fprintf(out,"p = %u\n",lh->p);
93 fprintf(out,"pmax = %u\n",lh->pmax);
94 fprintf(out,"up_load = %lu\n",lh->up_load);
95 fprintf(out,"down_load = %lu\n",lh->down_load);
96#endif
97 }
98
99void lh_node_stats(LHASH *lh, FILE *out)
100 {
101 LHASH_NODE *n;
102 unsigned int i,num;
103
104 for (i=0; i<lh->num_nodes; i++)
105 {
106 for (n=lh->b[i],num=0; n != NULL; n=n->next)
107 num++;
108 fprintf(out,"node %6u -> %3u\n",i,num);
109 }
110 }
111
112void lh_node_usage_stats(LHASH *lh, FILE *out)
113 {
114 LHASH_NODE *n;
115 unsigned long num;
116 unsigned int i;
117 unsigned long total=0,n_used=0;
118
119 for (i=0; i<lh->num_nodes; i++)
120 {
121 for (n=lh->b[i],num=0; n != NULL; n=n->next)
122 num++;
123 if (num != 0)
124 {
125 n_used++;
126 total+=num;
127 }
128 }
129 fprintf(out,"%lu nodes used out of %u\n",n_used,lh->num_nodes);
130 fprintf(out,"%lu items\n",total);
131 if (n_used == 0) return;
132 fprintf(out,"load %d.%02d actual load %d.%02d\n",
133 (int)(total/lh->num_nodes),
134 (int)((total%lh->num_nodes)*100/lh->num_nodes),
135 (int)(total/n_used),
136 (int)((total%n_used)*100/n_used));
137 }
138
139#else
140
141#ifndef OPENSSL_NO_FP_API
142void lh_stats(const LHASH *lh, FILE *fp)
143 {
144 BIO *bp;
145
146 bp=BIO_new(BIO_s_file());
147 if (bp == NULL) goto end;
148 BIO_set_fp(bp,fp,BIO_NOCLOSE);
149 lh_stats_bio(lh,bp);
150 BIO_free(bp);
151end:;
152 }
153
154void lh_node_stats(const LHASH *lh, FILE *fp)
155 {
156 BIO *bp;
157
158 bp=BIO_new(BIO_s_file());
159 if (bp == NULL) goto end;
160 BIO_set_fp(bp,fp,BIO_NOCLOSE);
161 lh_node_stats_bio(lh,bp);
162 BIO_free(bp);
163end:;
164 }
165
166void lh_node_usage_stats(const LHASH *lh, FILE *fp)
167 {
168 BIO *bp;
169
170 bp=BIO_new(BIO_s_file());
171 if (bp == NULL) goto end;
172 BIO_set_fp(bp,fp,BIO_NOCLOSE);
173 lh_node_usage_stats_bio(lh,bp);
174 BIO_free(bp);
175end:;
176 }
177
178#endif
179
180void lh_stats_bio(const LHASH *lh, BIO *out)
181 {
182 BIO_printf(out,"num_items = %lu\n",lh->num_items);
183 BIO_printf(out,"num_nodes = %u\n",lh->num_nodes);
184 BIO_printf(out,"num_alloc_nodes = %u\n",lh->num_alloc_nodes);
185 BIO_printf(out,"num_expands = %lu\n",lh->num_expands);
186 BIO_printf(out,"num_expand_reallocs = %lu\n",
187 lh->num_expand_reallocs);
188 BIO_printf(out,"num_contracts = %lu\n",lh->num_contracts);
189 BIO_printf(out,"num_contract_reallocs = %lu\n",
190 lh->num_contract_reallocs);
191 BIO_printf(out,"num_hash_calls = %lu\n",lh->num_hash_calls);
192 BIO_printf(out,"num_comp_calls = %lu\n",lh->num_comp_calls);
193 BIO_printf(out,"num_insert = %lu\n",lh->num_insert);
194 BIO_printf(out,"num_replace = %lu\n",lh->num_replace);
195 BIO_printf(out,"num_delete = %lu\n",lh->num_delete);
196 BIO_printf(out,"num_no_delete = %lu\n",lh->num_no_delete);
197 BIO_printf(out,"num_retrieve = %lu\n",lh->num_retrieve);
198 BIO_printf(out,"num_retrieve_miss = %lu\n",lh->num_retrieve_miss);
199 BIO_printf(out,"num_hash_comps = %lu\n",lh->num_hash_comps);
200#if 0
201 BIO_printf(out,"p = %u\n",lh->p);
202 BIO_printf(out,"pmax = %u\n",lh->pmax);
203 BIO_printf(out,"up_load = %lu\n",lh->up_load);
204 BIO_printf(out,"down_load = %lu\n",lh->down_load);
205#endif
206 }
207
208void lh_node_stats_bio(const LHASH *lh, BIO *out)
209 {
210 LHASH_NODE *n;
211 unsigned int i,num;
212
213 for (i=0; i<lh->num_nodes; i++)
214 {
215 for (n=lh->b[i],num=0; n != NULL; n=n->next)
216 num++;
217 BIO_printf(out,"node %6u -> %3u\n",i,num);
218 }
219 }
220
221void lh_node_usage_stats_bio(const LHASH *lh, BIO *out)
222 {
223 LHASH_NODE *n;
224 unsigned long num;
225 unsigned int i;
226 unsigned long total=0,n_used=0;
227
228 for (i=0; i<lh->num_nodes; i++)
229 {
230 for (n=lh->b[i],num=0; n != NULL; n=n->next)
231 num++;
232 if (num != 0)
233 {
234 n_used++;
235 total+=num;
236 }
237 }
238 BIO_printf(out,"%lu nodes used out of %u\n",n_used,lh->num_nodes);
239 BIO_printf(out,"%lu items\n",total);
240 if (n_used == 0) return;
241 BIO_printf(out,"load %d.%02d actual load %d.%02d\n",
242 (int)(total/lh->num_nodes),
243 (int)((total%lh->num_nodes)*100/lh->num_nodes),
244 (int)(total/n_used),
245 (int)((total%n_used)*100/n_used));
246 }
247
248#endif
diff --git a/src/lib/libcrypto/lhash/lhash.c b/src/lib/libcrypto/lhash/lhash.c
deleted file mode 100644
index 0a16fcf27d..0000000000
--- a/src/lib/libcrypto/lhash/lhash.c
+++ /dev/null
@@ -1,470 +0,0 @@
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/* Code for dynamic hash table routines
60 * Author - Eric Young v 2.0
61 *
62 * 2.2 eay - added #include "crypto.h" so the memory leak checking code is
63 * present. eay 18-Jun-98
64 *
65 * 2.1 eay - Added an 'error in last operation' flag. eay 6-May-98
66 *
67 * 2.0 eay - Fixed a bug that occurred when using lh_delete
68 * from inside lh_doall(). As entries were deleted,
69 * the 'table' was 'contract()ed', making some entries
70 * jump from the end of the table to the start, there by
71 * skipping the lh_doall() processing. eay - 4/12/95
72 *
73 * 1.9 eay - Fixed a memory leak in lh_free, the LHASH_NODEs
74 * were not being free()ed. 21/11/95
75 *
76 * 1.8 eay - Put the stats routines into a separate file, lh_stats.c
77 * 19/09/95
78 *
79 * 1.7 eay - Removed the fputs() for realloc failures - the code
80 * should silently tolerate them. I have also fixed things
81 * lint complained about 04/05/95
82 *
83 * 1.6 eay - Fixed an invalid pointers in contract/expand 27/07/92
84 *
85 * 1.5 eay - Fixed a misuse of realloc in expand 02/03/1992
86 *
87 * 1.4 eay - Fixed lh_doall so the function can call lh_delete 28/05/91
88 *
89 * 1.3 eay - Fixed a few lint problems 19/3/1991
90 *
91 * 1.2 eay - Fixed lh_doall problem 13/3/1991
92 *
93 * 1.1 eay - Added lh_doall
94 *
95 * 1.0 eay - First version
96 */
97#include <stdio.h>
98#include <string.h>
99#include <stdlib.h>
100#include <openssl/crypto.h>
101#include <openssl/lhash.h>
102
103const char *lh_version="lhash" OPENSSL_VERSION_PTEXT;
104
105#undef MIN_NODES
106#define MIN_NODES 16
107#define UP_LOAD (2*LH_LOAD_MULT) /* load times 256 (default 2) */
108#define DOWN_LOAD (LH_LOAD_MULT) /* load times 256 (default 1) */
109
110static void expand(LHASH *lh);
111static void contract(LHASH *lh);
112static LHASH_NODE **getrn(LHASH *lh, const void *data, unsigned long *rhash);
113
114LHASH *lh_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c)
115 {
116 LHASH *ret;
117 int i;
118
119 if ((ret=(LHASH *)OPENSSL_malloc(sizeof(LHASH))) == NULL)
120 goto err0;
121 if ((ret->b=(LHASH_NODE **)OPENSSL_malloc(sizeof(LHASH_NODE *)*MIN_NODES)) == NULL)
122 goto err1;
123 for (i=0; i<MIN_NODES; i++)
124 ret->b[i]=NULL;
125 ret->comp=((c == NULL)?(LHASH_COMP_FN_TYPE)strcmp:c);
126 ret->hash=((h == NULL)?(LHASH_HASH_FN_TYPE)lh_strhash:h);
127 ret->num_nodes=MIN_NODES/2;
128 ret->num_alloc_nodes=MIN_NODES;
129 ret->p=0;
130 ret->pmax=MIN_NODES/2;
131 ret->up_load=UP_LOAD;
132 ret->down_load=DOWN_LOAD;
133 ret->num_items=0;
134
135 ret->num_expands=0;
136 ret->num_expand_reallocs=0;
137 ret->num_contracts=0;
138 ret->num_contract_reallocs=0;
139 ret->num_hash_calls=0;
140 ret->num_comp_calls=0;
141 ret->num_insert=0;
142 ret->num_replace=0;
143 ret->num_delete=0;
144 ret->num_no_delete=0;
145 ret->num_retrieve=0;
146 ret->num_retrieve_miss=0;
147 ret->num_hash_comps=0;
148
149 ret->error=0;
150 return(ret);
151err1:
152 OPENSSL_free(ret);
153err0:
154 return(NULL);
155 }
156
157void lh_free(LHASH *lh)
158 {
159 unsigned int i;
160 LHASH_NODE *n,*nn;
161
162 if (lh == NULL)
163 return;
164
165 for (i=0; i<lh->num_nodes; i++)
166 {
167 n=lh->b[i];
168 while (n != NULL)
169 {
170 nn=n->next;
171 OPENSSL_free(n);
172 n=nn;
173 }
174 }
175 OPENSSL_free(lh->b);
176 OPENSSL_free(lh);
177 }
178
179void *lh_insert(LHASH *lh, const void *data)
180 {
181 unsigned long hash;
182 LHASH_NODE *nn,**rn;
183 const void *ret;
184
185 lh->error=0;
186 if (lh->up_load <= (lh->num_items*LH_LOAD_MULT/lh->num_nodes))
187 expand(lh);
188
189 rn=getrn(lh,data,&hash);
190
191 if (*rn == NULL)
192 {
193 if ((nn=(LHASH_NODE *)OPENSSL_malloc(sizeof(LHASH_NODE))) == NULL)
194 {
195 lh->error++;
196 return(NULL);
197 }
198 nn->data=data;
199 nn->next=NULL;
200#ifndef OPENSSL_NO_HASH_COMP
201 nn->hash=hash;
202#endif
203 *rn=nn;
204 ret=NULL;
205 lh->num_insert++;
206 lh->num_items++;
207 }
208 else /* replace same key */
209 {
210 ret= (*rn)->data;
211 (*rn)->data=data;
212 lh->num_replace++;
213 }
214 return((void *)ret);
215 }
216
217void *lh_delete(LHASH *lh, const void *data)
218 {
219 unsigned long hash;
220 LHASH_NODE *nn,**rn;
221 const void *ret;
222
223 lh->error=0;
224 rn=getrn(lh,data,&hash);
225
226 if (*rn == NULL)
227 {
228 lh->num_no_delete++;
229 return(NULL);
230 }
231 else
232 {
233 nn= *rn;
234 *rn=nn->next;
235 ret=nn->data;
236 OPENSSL_free(nn);
237 lh->num_delete++;
238 }
239
240 lh->num_items--;
241 if ((lh->num_nodes > MIN_NODES) &&
242 (lh->down_load >= (lh->num_items*LH_LOAD_MULT/lh->num_nodes)))
243 contract(lh);
244
245 return((void *)ret);
246 }
247
248void *lh_retrieve(LHASH *lh, const void *data)
249 {
250 unsigned long hash;
251 LHASH_NODE **rn;
252 const void *ret;
253
254 lh->error=0;
255 rn=getrn(lh,data,&hash);
256
257 if (*rn == NULL)
258 {
259 lh->num_retrieve_miss++;
260 return(NULL);
261 }
262 else
263 {
264 ret= (*rn)->data;
265 lh->num_retrieve++;
266 }
267 return((void *)ret);
268 }
269
270static void doall_util_fn(LHASH *lh, int use_arg, LHASH_DOALL_FN_TYPE func,
271 LHASH_DOALL_ARG_FN_TYPE func_arg, void *arg)
272 {
273 int i;
274 LHASH_NODE *a,*n;
275
276 /* reverse the order so we search from 'top to bottom'
277 * We were having memory leaks otherwise */
278 for (i=lh->num_nodes-1; i>=0; i--)
279 {
280 a=lh->b[i];
281 while (a != NULL)
282 {
283 /* 28/05/91 - eay - n added so items can be deleted
284 * via lh_doall */
285 n=a->next;
286 if(use_arg)
287 func_arg(a->data,arg);
288 else
289 func(a->data);
290 a=n;
291 }
292 }
293 }
294
295void lh_doall(LHASH *lh, LHASH_DOALL_FN_TYPE func)
296 {
297 doall_util_fn(lh, 0, func, (LHASH_DOALL_ARG_FN_TYPE)0, NULL);
298 }
299
300void lh_doall_arg(LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg)
301 {
302 doall_util_fn(lh, 1, (LHASH_DOALL_FN_TYPE)0, func, arg);
303 }
304
305static void expand(LHASH *lh)
306 {
307 LHASH_NODE **n,**n1,**n2,*np;
308 unsigned int p,i,j;
309 unsigned long hash,nni;
310
311 lh->num_nodes++;
312 lh->num_expands++;
313 p=(int)lh->p++;
314 n1= &(lh->b[p]);
315 n2= &(lh->b[p+(int)lh->pmax]);
316 *n2=NULL; /* 27/07/92 - eay - undefined pointer bug */
317 nni=lh->num_alloc_nodes;
318
319 for (np= *n1; np != NULL; )
320 {
321#ifndef OPENSSL_NO_HASH_COMP
322 hash=np->hash;
323#else
324 hash=lh->hash(np->data);
325 lh->num_hash_calls++;
326#endif
327 if ((hash%nni) != p)
328 { /* move it */
329 *n1= (*n1)->next;
330 np->next= *n2;
331 *n2=np;
332 }
333 else
334 n1= &((*n1)->next);
335 np= *n1;
336 }
337
338 if ((lh->p) >= lh->pmax)
339 {
340 j=(int)lh->num_alloc_nodes*2;
341 n=(LHASH_NODE **)OPENSSL_realloc(lh->b,
342 (unsigned int)sizeof(LHASH_NODE *)*j);
343 if (n == NULL)
344 {
345/* fputs("realloc error in lhash",stderr); */
346 lh->error++;
347 lh->p=0;
348 return;
349 }
350 /* else */
351 for (i=(int)lh->num_alloc_nodes; i<j; i++)/* 26/02/92 eay */
352 n[i]=NULL; /* 02/03/92 eay */
353 lh->pmax=lh->num_alloc_nodes;
354 lh->num_alloc_nodes=j;
355 lh->num_expand_reallocs++;
356 lh->p=0;
357 lh->b=n;
358 }
359 }
360
361static void contract(LHASH *lh)
362 {
363 LHASH_NODE **n,*n1,*np;
364
365 np=lh->b[lh->p+lh->pmax-1];
366 lh->b[lh->p+lh->pmax-1]=NULL; /* 24/07-92 - eay - weird but :-( */
367 if (lh->p == 0)
368 {
369 n=(LHASH_NODE **)OPENSSL_realloc(lh->b,
370 (unsigned int)(sizeof(LHASH_NODE *)*lh->pmax));
371 if (n == NULL)
372 {
373/* fputs("realloc error in lhash",stderr); */
374 lh->error++;
375 return;
376 }
377 lh->num_contract_reallocs++;
378 lh->num_alloc_nodes/=2;
379 lh->pmax/=2;
380 lh->p=lh->pmax-1;
381 lh->b=n;
382 }
383 else
384 lh->p--;
385
386 lh->num_nodes--;
387 lh->num_contracts++;
388
389 n1=lh->b[(int)lh->p];
390 if (n1 == NULL)
391 lh->b[(int)lh->p]=np;
392 else
393 {
394 while (n1->next != NULL)
395 n1=n1->next;
396 n1->next=np;
397 }
398 }
399
400static LHASH_NODE **getrn(LHASH *lh, const void *data, unsigned long *rhash)
401 {
402 LHASH_NODE **ret,*n1;
403 unsigned long hash,nn;
404 int (*cf)();
405
406 hash=(*(lh->hash))(data);
407 lh->num_hash_calls++;
408 *rhash=hash;
409
410 nn=hash%lh->pmax;
411 if (nn < lh->p)
412 nn=hash%lh->num_alloc_nodes;
413
414 cf=lh->comp;
415 ret= &(lh->b[(int)nn]);
416 for (n1= *ret; n1 != NULL; n1=n1->next)
417 {
418#ifndef OPENSSL_NO_HASH_COMP
419 lh->num_hash_comps++;
420 if (n1->hash != hash)
421 {
422 ret= &(n1->next);
423 continue;
424 }
425#endif
426 lh->num_comp_calls++;
427 if(cf(n1->data,data) == 0)
428 break;
429 ret= &(n1->next);
430 }
431 return(ret);
432 }
433
434/* The following hash seems to work very well on normal text strings
435 * no collisions on /usr/dict/words and it distributes on %2^n quite
436 * well, not as good as MD5, but still good.
437 */
438unsigned long lh_strhash(const char *c)
439 {
440 unsigned long ret=0;
441 long n;
442 unsigned long v;
443 int r;
444
445 if ((c == NULL) || (*c == '\0'))
446 return(ret);
447/*
448 unsigned char b[16];
449 MD5(c,strlen(c),b);
450 return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24));
451*/
452
453 n=0x100;
454 while (*c)
455 {
456 v=n|(*c);
457 n+=0x100;
458 r= (int)((v>>2)^v)&0x0f;
459 ret=(ret<<r)|(ret>>(32-r));
460 ret&=0xFFFFFFFFL;
461 ret^=v*v;
462 c++;
463 }
464 return((ret>>16)^ret);
465 }
466
467unsigned long lh_num_items(const LHASH *lh)
468 {
469 return lh ? lh->num_items : 0;
470 }
diff --git a/src/lib/libcrypto/lhash/lhash.h b/src/lib/libcrypto/lhash/lhash.h
deleted file mode 100644
index dee8207333..0000000000
--- a/src/lib/libcrypto/lhash/lhash.h
+++ /dev/null
@@ -1,199 +0,0 @@
1/* crypto/lhash/lhash.h */
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/* Header for dynamic hash table routines
60 * Author - Eric Young
61 */
62
63#ifndef HEADER_LHASH_H
64#define HEADER_LHASH_H
65
66#ifndef OPENSSL_NO_FP_API
67#include <stdio.h>
68#endif
69
70#ifndef OPENSSL_NO_BIO
71#include <openssl/bio.h>
72#endif
73
74#ifdef __cplusplus
75extern "C" {
76#endif
77
78typedef struct lhash_node_st
79 {
80 const void *data;
81 struct lhash_node_st *next;
82#ifndef OPENSSL_NO_HASH_COMP
83 unsigned long hash;
84#endif
85 } LHASH_NODE;
86
87typedef int (*LHASH_COMP_FN_TYPE)(const void *, const void *);
88typedef unsigned long (*LHASH_HASH_FN_TYPE)(const void *);
89typedef void (*LHASH_DOALL_FN_TYPE)(const void *);
90typedef void (*LHASH_DOALL_ARG_FN_TYPE)(const void *, void *);
91
92/* Macros for declaring and implementing type-safe wrappers for LHASH callbacks.
93 * This way, callbacks can be provided to LHASH structures without function
94 * pointer casting and the macro-defined callbacks provide per-variable casting
95 * before deferring to the underlying type-specific callbacks. NB: It is
96 * possible to place a "static" in front of both the DECLARE and IMPLEMENT
97 * macros if the functions are strictly internal. */
98
99/* First: "hash" functions */
100#define DECLARE_LHASH_HASH_FN(f_name,o_type) \
101 unsigned long f_name##_LHASH_HASH(const void *);
102#define IMPLEMENT_LHASH_HASH_FN(f_name,o_type) \
103 unsigned long f_name##_LHASH_HASH(const void *arg) { \
104 o_type a = (o_type)arg; \
105 return f_name(a); }
106#define LHASH_HASH_FN(f_name) f_name##_LHASH_HASH
107
108/* Second: "compare" functions */
109#define DECLARE_LHASH_COMP_FN(f_name,o_type) \
110 int f_name##_LHASH_COMP(const void *, const void *);
111#define IMPLEMENT_LHASH_COMP_FN(f_name,o_type) \
112 int f_name##_LHASH_COMP(const void *arg1, const void *arg2) { \
113 o_type a = (o_type)arg1; \
114 o_type b = (o_type)arg2; \
115 return f_name(a,b); }
116#define LHASH_COMP_FN(f_name) f_name##_LHASH_COMP
117
118/* Third: "doall" functions */
119#define DECLARE_LHASH_DOALL_FN(f_name,o_type) \
120 void f_name##_LHASH_DOALL(const void *);
121#define IMPLEMENT_LHASH_DOALL_FN(f_name,o_type) \
122 void f_name##_LHASH_DOALL(const void *arg) { \
123 o_type a = (o_type)arg; \
124 f_name(a); }
125#define LHASH_DOALL_FN(f_name) f_name##_LHASH_DOALL
126
127/* Fourth: "doall_arg" functions */
128#define DECLARE_LHASH_DOALL_ARG_FN(f_name,o_type,a_type) \
129 void f_name##_LHASH_DOALL_ARG(const void *, void *);
130#define IMPLEMENT_LHASH_DOALL_ARG_FN(f_name,o_type,a_type) \
131 void f_name##_LHASH_DOALL_ARG(const void *arg1, void *arg2) { \
132 o_type a = (o_type)arg1; \
133 a_type b = (a_type)arg2; \
134 f_name(a,b); }
135#define LHASH_DOALL_ARG_FN(f_name) f_name##_LHASH_DOALL_ARG
136
137typedef struct lhash_st
138 {
139 LHASH_NODE **b;
140 LHASH_COMP_FN_TYPE comp;
141 LHASH_HASH_FN_TYPE hash;
142 unsigned int num_nodes;
143 unsigned int num_alloc_nodes;
144 unsigned int p;
145 unsigned int pmax;
146 unsigned long up_load; /* load times 256 */
147 unsigned long down_load; /* load times 256 */
148 unsigned long num_items;
149
150 unsigned long num_expands;
151 unsigned long num_expand_reallocs;
152 unsigned long num_contracts;
153 unsigned long num_contract_reallocs;
154 unsigned long num_hash_calls;
155 unsigned long num_comp_calls;
156 unsigned long num_insert;
157 unsigned long num_replace;
158 unsigned long num_delete;
159 unsigned long num_no_delete;
160 unsigned long num_retrieve;
161 unsigned long num_retrieve_miss;
162 unsigned long num_hash_comps;
163
164 int error;
165 } LHASH;
166
167#define LH_LOAD_MULT 256
168
169/* Indicates a malloc() error in the last call, this is only bad
170 * in lh_insert(). */
171#define lh_error(lh) ((lh)->error)
172
173LHASH *lh_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c);
174void lh_free(LHASH *lh);
175void *lh_insert(LHASH *lh, const void *data);
176void *lh_delete(LHASH *lh, const void *data);
177void *lh_retrieve(LHASH *lh, const void *data);
178void lh_doall(LHASH *lh, LHASH_DOALL_FN_TYPE func);
179void lh_doall_arg(LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg);
180unsigned long lh_strhash(const char *c);
181unsigned long lh_num_items(const LHASH *lh);
182
183#ifndef OPENSSL_NO_FP_API
184void lh_stats(const LHASH *lh, FILE *out);
185void lh_node_stats(const LHASH *lh, FILE *out);
186void lh_node_usage_stats(const LHASH *lh, FILE *out);
187#endif
188
189#ifndef OPENSSL_NO_BIO
190void lh_stats_bio(const LHASH *lh, BIO *out);
191void lh_node_stats_bio(const LHASH *lh, BIO *out);
192void lh_node_usage_stats_bio(const LHASH *lh, BIO *out);
193#endif
194#ifdef __cplusplus
195}
196#endif
197
198#endif
199
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-19 21:50:57 +0000