summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/lhash
diff options
context:
space:
mode:
authorcvs2svn <admin@example.com>2001-10-01 21:58:54 +0000
committercvs2svn <admin@example.com>2001-10-01 21:58:54 +0000
commit2b482d950b0e856294fcd4c1068c1b21939a7240 (patch)
treeaa05f6be64877f76547f1b54ad84f7bfcb291f5d /src/lib/libcrypto/lhash
parentd7b0aad33e28dafbbef67eb5b84ecb05a844fc88 (diff)
downloadopenbsd-OPENBSD_3_0_BASE.tar.gz
openbsd-OPENBSD_3_0_BASE.tar.bz2
openbsd-OPENBSD_3_0_BASE.zip
This commit was manufactured by cvs2git to create tag 'OPENBSD_3_0_BASE'.OPENBSD_3_0_BASE
Diffstat (limited to 'src/lib/libcrypto/lhash')
-rw-r--r--src/lib/libcrypto/lhash/lh_stats.c274
-rw-r--r--src/lib/libcrypto/lhash/lhash.c461
-rw-r--r--src/lib/libcrypto/lhash/lhash.h149
3 files changed, 0 insertions, 884 deletions
diff --git a/src/lib/libcrypto/lhash/lh_stats.c b/src/lib/libcrypto/lhash/lh_stats.c
deleted file mode 100644
index ee0600060e..0000000000
--- a/src/lib/libcrypto/lhash/lh_stats.c
+++ /dev/null
@@ -1,274 +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 NO_BIO
67#include <openssl/bio.h>
68#endif
69#include <openssl/lhash.h>
70
71#ifdef 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#ifdef DEBUG
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 NO_FP_API
142void lh_stats(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(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(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(LHASH *lh, BIO *out)
181 {
182 char buf[128];
183
184 sprintf(buf,"num_items = %lu\n",lh->num_items);
185 BIO_puts(out,buf);
186 sprintf(buf,"num_nodes = %u\n",lh->num_nodes);
187 BIO_puts(out,buf);
188 sprintf(buf,"num_alloc_nodes = %u\n",lh->num_alloc_nodes);
189 BIO_puts(out,buf);
190 sprintf(buf,"num_expands = %lu\n",lh->num_expands);
191 BIO_puts(out,buf);
192 sprintf(buf,"num_expand_reallocs = %lu\n",lh->num_expand_reallocs);
193 BIO_puts(out,buf);
194 sprintf(buf,"num_contracts = %lu\n",lh->num_contracts);
195 BIO_puts(out,buf);
196 sprintf(buf,"num_contract_reallocs = %lu\n",lh->num_contract_reallocs);
197 BIO_puts(out,buf);
198 sprintf(buf,"num_hash_calls = %lu\n",lh->num_hash_calls);
199 BIO_puts(out,buf);
200 sprintf(buf,"num_comp_calls = %lu\n",lh->num_comp_calls);
201 BIO_puts(out,buf);
202 sprintf(buf,"num_insert = %lu\n",lh->num_insert);
203 BIO_puts(out,buf);
204 sprintf(buf,"num_replace = %lu\n",lh->num_replace);
205 BIO_puts(out,buf);
206 sprintf(buf,"num_delete = %lu\n",lh->num_delete);
207 BIO_puts(out,buf);
208 sprintf(buf,"num_no_delete = %lu\n",lh->num_no_delete);
209 BIO_puts(out,buf);
210 sprintf(buf,"num_retrieve = %lu\n",lh->num_retrieve);
211 BIO_puts(out,buf);
212 sprintf(buf,"num_retrieve_miss = %lu\n",lh->num_retrieve_miss);
213 BIO_puts(out,buf);
214 sprintf(buf,"num_hash_comps = %lu\n",lh->num_hash_comps);
215 BIO_puts(out,buf);
216#ifdef DEBUG
217 sprintf(buf,"p = %u\n",lh->p);
218 BIO_puts(out,buf);
219 sprintf(buf,"pmax = %u\n",lh->pmax);
220 BIO_puts(out,buf);
221 sprintf(buf,"up_load = %lu\n",lh->up_load);
222 BIO_puts(out,buf);
223 sprintf(buf,"down_load = %lu\n",lh->down_load);
224 BIO_puts(out,buf);
225#endif
226 }
227
228void lh_node_stats_bio(LHASH *lh, BIO *out)
229 {
230 LHASH_NODE *n;
231 unsigned int i,num;
232 char buf[128];
233
234 for (i=0; i<lh->num_nodes; i++)
235 {
236 for (n=lh->b[i],num=0; n != NULL; n=n->next)
237 num++;
238 sprintf(buf,"node %6u -> %3u\n",i,num);
239 BIO_puts(out,buf);
240 }
241 }
242
243void lh_node_usage_stats_bio(LHASH *lh, BIO *out)
244 {
245 LHASH_NODE *n;
246 unsigned long num;
247 unsigned int i;
248 unsigned long total=0,n_used=0;
249 char buf[128];
250
251 for (i=0; i<lh->num_nodes; i++)
252 {
253 for (n=lh->b[i],num=0; n != NULL; n=n->next)
254 num++;
255 if (num != 0)
256 {
257 n_used++;
258 total+=num;
259 }
260 }
261 sprintf(buf,"%lu nodes used out of %u\n",n_used,lh->num_nodes);
262 BIO_puts(out,buf);
263 sprintf(buf,"%lu items\n",total);
264 BIO_puts(out,buf);
265 if (n_used == 0) return;
266 sprintf(buf,"load %d.%02d actual load %d.%02d\n",
267 (int)(total/lh->num_nodes),
268 (int)((total%lh->num_nodes)*100/lh->num_nodes),
269 (int)(total/n_used),
270 (int)((total%n_used)*100/n_used));
271 BIO_puts(out,buf);
272 }
273
274#endif
diff --git a/src/lib/libcrypto/lhash/lhash.c b/src/lib/libcrypto/lhash/lhash.c
deleted file mode 100644
index 7da14620a4..0000000000
--- a/src/lib/libcrypto/lhash/lhash.c
+++ /dev/null
@@ -1,461 +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, void *data, unsigned long *rhash);
113
114LHASH *lh_new(unsigned long (*h)(), int (*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)?(int (*)())strcmp:c);
126 ret->hash=((h == NULL)?(unsigned long (*)())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, void *data)
180 {
181 unsigned long hash;
182 LHASH_NODE *nn,**rn;
183 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 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(ret);
215 }
216
217void *lh_delete(LHASH *lh, void *data)
218 {
219 unsigned long hash;
220 LHASH_NODE *nn,**rn;
221 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(ret);
246 }
247
248void *lh_retrieve(LHASH *lh, void *data)
249 {
250 unsigned long hash;
251 LHASH_NODE **rn;
252 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(ret);
268 }
269
270void lh_doall(LHASH *lh, void (*func)())
271 {
272 lh_doall_arg(lh,func,NULL);
273 }
274
275void lh_doall_arg(LHASH *lh, void (*func)(), void *arg)
276 {
277 int i;
278 LHASH_NODE *a,*n;
279
280 /* reverse the order so we search from 'top to bottom'
281 * We were having memory leaks otherwise */
282 for (i=lh->num_nodes-1; i>=0; i--)
283 {
284 a=lh->b[i];
285 while (a != NULL)
286 {
287 /* 28/05/91 - eay - n added so items can be deleted
288 * via lh_doall */
289 n=a->next;
290 func(a->data,arg);
291 a=n;
292 }
293 }
294 }
295
296static void expand(LHASH *lh)
297 {
298 LHASH_NODE **n,**n1,**n2,*np;
299 unsigned int p,i,j;
300 unsigned long hash,nni;
301
302 lh->num_nodes++;
303 lh->num_expands++;
304 p=(int)lh->p++;
305 n1= &(lh->b[p]);
306 n2= &(lh->b[p+(int)lh->pmax]);
307 *n2=NULL; /* 27/07/92 - eay - undefined pointer bug */
308 nni=lh->num_alloc_nodes;
309
310 for (np= *n1; np != NULL; )
311 {
312#ifndef NO_HASH_COMP
313 hash=np->hash;
314#else
315 hash=(*(lh->hash))(np->data);
316 lh->num_hash_calls++;
317#endif
318 if ((hash%nni) != p)
319 { /* move it */
320 *n1= (*n1)->next;
321 np->next= *n2;
322 *n2=np;
323 }
324 else
325 n1= &((*n1)->next);
326 np= *n1;
327 }
328
329 if ((lh->p) >= lh->pmax)
330 {
331 j=(int)lh->num_alloc_nodes*2;
332 n=(LHASH_NODE **)OPENSSL_realloc(lh->b,
333 (unsigned int)sizeof(LHASH_NODE *)*j);
334 if (n == NULL)
335 {
336/* fputs("realloc error in lhash",stderr); */
337 lh->error++;
338 lh->p=0;
339 return;
340 }
341 /* else */
342 for (i=(int)lh->num_alloc_nodes; i<j; i++)/* 26/02/92 eay */
343 n[i]=NULL; /* 02/03/92 eay */
344 lh->pmax=lh->num_alloc_nodes;
345 lh->num_alloc_nodes=j;
346 lh->num_expand_reallocs++;
347 lh->p=0;
348 lh->b=n;
349 }
350 }
351
352static void contract(LHASH *lh)
353 {
354 LHASH_NODE **n,*n1,*np;
355
356 np=lh->b[lh->p+lh->pmax-1];
357 lh->b[lh->p+lh->pmax-1]=NULL; /* 24/07-92 - eay - weird but :-( */
358 if (lh->p == 0)
359 {
360 n=(LHASH_NODE **)OPENSSL_realloc(lh->b,
361 (unsigned int)(sizeof(LHASH_NODE *)*lh->pmax));
362 if (n == NULL)
363 {
364/* fputs("realloc error in lhash",stderr); */
365 lh->error++;
366 return;
367 }
368 lh->num_contract_reallocs++;
369 lh->num_alloc_nodes/=2;
370 lh->pmax/=2;
371 lh->p=lh->pmax-1;
372 lh->b=n;
373 }
374 else
375 lh->p--;
376
377 lh->num_nodes--;
378 lh->num_contracts++;
379
380 n1=lh->b[(int)lh->p];
381 if (n1 == NULL)
382 lh->b[(int)lh->p]=np;
383 else
384 {
385 while (n1->next != NULL)
386 n1=n1->next;
387 n1->next=np;
388 }
389 }
390
391static LHASH_NODE **getrn(LHASH *lh, void *data, unsigned long *rhash)
392 {
393 LHASH_NODE **ret,*n1;
394 unsigned long hash,nn;
395 int (*cf)();
396
397 hash=(*(lh->hash))(data);
398 lh->num_hash_calls++;
399 *rhash=hash;
400
401 nn=hash%lh->pmax;
402 if (nn < lh->p)
403 nn=hash%lh->num_alloc_nodes;
404
405 cf=lh->comp;
406 ret= &(lh->b[(int)nn]);
407 for (n1= *ret; n1 != NULL; n1=n1->next)
408 {
409#ifndef NO_HASH_COMP
410 lh->num_hash_comps++;
411 if (n1->hash != hash)
412 {
413 ret= &(n1->next);
414 continue;
415 }
416#endif
417 lh->num_comp_calls++;
418 if ((*cf)(n1->data,data) == 0)
419 break;
420 ret= &(n1->next);
421 }
422 return(ret);
423 }
424
425/* The following hash seems to work very well on normal text strings
426 * no collisions on /usr/dict/words and it distributes on %2^n quite
427 * well, not as good as MD5, but still good.
428 */
429unsigned long lh_strhash(const char *c)
430 {
431 unsigned long ret=0;
432 long n;
433 unsigned long v;
434 int r;
435
436 if ((c == NULL) || (*c == '\0'))
437 return(ret);
438/*
439 unsigned char b[16];
440 MD5(c,strlen(c),b);
441 return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24));
442*/
443
444 n=0x100;
445 while (*c)
446 {
447 v=n|(*c);
448 n+=0x100;
449 r= (int)((v>>2)^v)&0x0f;
450 ret=(ret<<r)|(ret>>(32-r));
451 ret&=0xFFFFFFFFL;
452 ret^=v*v;
453 c++;
454 }
455 return((ret>>16)^ret);
456 }
457
458unsigned long lh_num_items(LHASH *lh)
459 {
460 return lh ? lh->num_items : 0;
461 }
diff --git a/src/lib/libcrypto/lhash/lhash.h b/src/lib/libcrypto/lhash/lhash.h
deleted file mode 100644
index b8ff021906..0000000000
--- a/src/lib/libcrypto/lhash/lhash.h
+++ /dev/null
@@ -1,149 +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 NO_FP_API
67#include <stdio.h>
68#endif
69
70#ifndef 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 void *data;
81 struct lhash_node_st *next;
82#ifndef NO_HASH_COMP
83 unsigned long hash;
84#endif
85 } LHASH_NODE;
86
87typedef struct lhash_st
88 {
89 LHASH_NODE **b;
90 int (*comp)();
91 unsigned long (*hash)();
92 unsigned int num_nodes;
93 unsigned int num_alloc_nodes;
94 unsigned int p;
95 unsigned int pmax;
96 unsigned long up_load; /* load times 256 */
97 unsigned long down_load; /* load times 256 */
98 unsigned long num_items;
99
100 unsigned long num_expands;
101 unsigned long num_expand_reallocs;
102 unsigned long num_contracts;
103 unsigned long num_contract_reallocs;
104 unsigned long num_hash_calls;
105 unsigned long num_comp_calls;
106 unsigned long num_insert;
107 unsigned long num_replace;
108 unsigned long num_delete;
109 unsigned long num_no_delete;
110 unsigned long num_retrieve;
111 unsigned long num_retrieve_miss;
112 unsigned long num_hash_comps;
113
114 int error;
115 } LHASH;
116
117#define LH_LOAD_MULT 256
118
119/* Indicates a malloc() error in the last call, this is only bad
120 * in lh_insert(). */
121#define lh_error(lh) ((lh)->error)
122
123LHASH *lh_new(unsigned long (*h)(/* void *a */), int (*c)(/* void *a,void *b */));
124void lh_free(LHASH *lh);
125void *lh_insert(LHASH *lh, void *data);
126void *lh_delete(LHASH *lh, void *data);
127void *lh_retrieve(LHASH *lh, void *data);
128 void lh_doall(LHASH *lh, void (*func)(/*void *b*/));
129void lh_doall_arg(LHASH *lh, void (*func)(/*void *a,void *b*/),void *arg);
130unsigned long lh_strhash(const char *c);
131unsigned long lh_num_items(LHASH *lh);
132
133#ifndef NO_FP_API
134void lh_stats(LHASH *lh, FILE *out);
135void lh_node_stats(LHASH *lh, FILE *out);
136void lh_node_usage_stats(LHASH *lh, FILE *out);
137#endif
138
139#ifndef NO_BIO
140void lh_stats_bio(LHASH *lh, BIO *out);
141void lh_node_stats_bio(LHASH *lh, BIO *out);
142void lh_node_usage_stats_bio(LHASH *lh, BIO *out);
143#endif
144#ifdef __cplusplus
145}
146#endif
147
148#endif
149
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-19 21:50:39 +0000