summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/lhash
diff options
context:
space:
mode:
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.c475
-rw-r--r--src/lib/libcrypto/lhash/lhash.h241
3 files changed, 0 insertions, 964 deletions
diff --git a/src/lib/libcrypto/lhash/lh_stats.c b/src/lib/libcrypto/lhash/lh_stats.c
deleted file mode 100644
index 815615e338..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 47f748081b..0000000000
--- a/src/lib/libcrypto/lhash/lhash.c
+++ /dev/null
@@ -1,475 +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
114_LHASH *lh_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c)
115 {
116 _LHASH *ret;
117 int i;
118
119 if ((ret=OPENSSL_malloc(sizeof(_LHASH))) == NULL)
120 goto err0;
121 if ((ret->b=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, 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 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(ret);
215 }
216
217void *lh_delete(_LHASH *lh, const 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, const 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
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 if (lh == NULL)
277 return;
278
279 /* reverse the order so we search from 'top to bottom'
280 * We were having memory leaks otherwise */
281 for (i=lh->num_nodes-1; i>=0; i--)
282 {
283 a=lh->b[i];
284 while (a != NULL)
285 {
286 /* 28/05/91 - eay - n added so items can be deleted
287 * via lh_doall */
288 /* 22/05/08 - ben - eh? since a is not passed,
289 * this should not be needed */
290 n=a->next;
291 if(use_arg)
292 func_arg(a->data,arg);
293 else
294 func(a->data);
295 a=n;
296 }
297 }
298 }
299
300void lh_doall(_LHASH *lh, LHASH_DOALL_FN_TYPE func)
301 {
302 doall_util_fn(lh, 0, func, (LHASH_DOALL_ARG_FN_TYPE)0, NULL);
303 }
304
305void lh_doall_arg(_LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg)
306 {
307 doall_util_fn(lh, 1, (LHASH_DOALL_FN_TYPE)0, func, arg);
308 }
309
310static void expand(_LHASH *lh)
311 {
312 LHASH_NODE **n,**n1,**n2,*np;
313 unsigned int p,i,j;
314 unsigned long hash,nni;
315
316 lh->num_nodes++;
317 lh->num_expands++;
318 p=(int)lh->p++;
319 n1= &(lh->b[p]);
320 n2= &(lh->b[p+(int)lh->pmax]);
321 *n2=NULL; /* 27/07/92 - eay - undefined pointer bug */
322 nni=lh->num_alloc_nodes;
323
324 for (np= *n1; np != NULL; )
325 {
326#ifndef OPENSSL_NO_HASH_COMP
327 hash=np->hash;
328#else
329 hash=lh->hash(np->data);
330 lh->num_hash_calls++;
331#endif
332 if ((hash%nni) != p)
333 { /* move it */
334 *n1= (*n1)->next;
335 np->next= *n2;
336 *n2=np;
337 }
338 else
339 n1= &((*n1)->next);
340 np= *n1;
341 }
342
343 if ((lh->p) >= lh->pmax)
344 {
345 j=(int)lh->num_alloc_nodes*2;
346 n=(LHASH_NODE **)OPENSSL_realloc(lh->b,
347 (int)(sizeof(LHASH_NODE *)*j));
348 if (n == NULL)
349 {
350/* fputs("realloc error in lhash",stderr); */
351 lh->error++;
352 lh->p=0;
353 return;
354 }
355 /* else */
356 for (i=(int)lh->num_alloc_nodes; i<j; i++)/* 26/02/92 eay */
357 n[i]=NULL; /* 02/03/92 eay */
358 lh->pmax=lh->num_alloc_nodes;
359 lh->num_alloc_nodes=j;
360 lh->num_expand_reallocs++;
361 lh->p=0;
362 lh->b=n;
363 }
364 }
365
366static void contract(_LHASH *lh)
367 {
368 LHASH_NODE **n,*n1,*np;
369
370 np=lh->b[lh->p+lh->pmax-1];
371 lh->b[lh->p+lh->pmax-1]=NULL; /* 24/07-92 - eay - weird but :-( */
372 if (lh->p == 0)
373 {
374 n=(LHASH_NODE **)OPENSSL_realloc(lh->b,
375 (unsigned int)(sizeof(LHASH_NODE *)*lh->pmax));
376 if (n == NULL)
377 {
378/* fputs("realloc error in lhash",stderr); */
379 lh->error++;
380 return;
381 }
382 lh->num_contract_reallocs++;
383 lh->num_alloc_nodes/=2;
384 lh->pmax/=2;
385 lh->p=lh->pmax-1;
386 lh->b=n;
387 }
388 else
389 lh->p--;
390
391 lh->num_nodes--;
392 lh->num_contracts++;
393
394 n1=lh->b[(int)lh->p];
395 if (n1 == NULL)
396 lh->b[(int)lh->p]=np;
397 else
398 {
399 while (n1->next != NULL)
400 n1=n1->next;
401 n1->next=np;
402 }
403 }
404
405static LHASH_NODE **getrn(_LHASH *lh, const void *data, unsigned long *rhash)
406 {
407 LHASH_NODE **ret,*n1;
408 unsigned long hash,nn;
409 LHASH_COMP_FN_TYPE cf;
410
411 hash=(*(lh->hash))(data);
412 lh->num_hash_calls++;
413 *rhash=hash;
414
415 nn=hash%lh->pmax;
416 if (nn < lh->p)
417 nn=hash%lh->num_alloc_nodes;
418
419 cf=lh->comp;
420 ret= &(lh->b[(int)nn]);
421 for (n1= *ret; n1 != NULL; n1=n1->next)
422 {
423#ifndef OPENSSL_NO_HASH_COMP
424 lh->num_hash_comps++;
425 if (n1->hash != hash)
426 {
427 ret= &(n1->next);
428 continue;
429 }
430#endif
431 lh->num_comp_calls++;
432 if(cf(n1->data,data) == 0)
433 break;
434 ret= &(n1->next);
435 }
436 return(ret);
437 }
438
439/* The following hash seems to work very well on normal text strings
440 * no collisions on /usr/dict/words and it distributes on %2^n quite
441 * well, not as good as MD5, but still good.
442 */
443unsigned long lh_strhash(const char *c)
444 {
445 unsigned long ret=0;
446 long n;
447 unsigned long v;
448 int r;
449
450 if ((c == NULL) || (*c == '\0'))
451 return(ret);
452/*
453 unsigned char b[16];
454 MD5(c,strlen(c),b);
455 return(b[0]|(b[1]<<8)|(b[2]<<16)|(b[3]<<24));
456*/
457
458 n=0x100;
459 while (*c)
460 {
461 v=n|(*c);
462 n+=0x100;
463 r= (int)((v>>2)^v)&0x0f;
464 ret=(ret<<r)|(ret>>(32-r));
465 ret&=0xFFFFFFFFL;
466 ret^=v*v;
467 c++;
468 }
469 return((ret>>16)^ret);
470 }
471
472unsigned long lh_num_items(const _LHASH *lh)
473 {
474 return lh ? lh->num_items : 0;
475 }
diff --git a/src/lib/libcrypto/lhash/lhash.h b/src/lib/libcrypto/lhash/lhash.h
deleted file mode 100644
index e7d8763591..0000000000
--- a/src/lib/libcrypto/lhash/lhash.h
+++ /dev/null
@@ -1,241 +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#include <openssl/e_os2.h>
67#ifndef OPENSSL_NO_FP_API
68#include <stdio.h>
69#endif
70
71#ifndef OPENSSL_NO_BIO
72#include <openssl/bio.h>
73#endif
74
75#ifdef __cplusplus
76extern "C" {
77#endif
78
79typedef struct lhash_node_st
80 {
81 void *data;
82 struct lhash_node_st *next;
83#ifndef OPENSSL_NO_HASH_COMP
84 unsigned long hash;
85#endif
86 } LHASH_NODE;
87
88typedef int (*LHASH_COMP_FN_TYPE)(const void *, const void *);
89typedef unsigned long (*LHASH_HASH_FN_TYPE)(const void *);
90typedef void (*LHASH_DOALL_FN_TYPE)(void *);
91typedef void (*LHASH_DOALL_ARG_FN_TYPE)(void *, void *);
92
93/* Macros for declaring and implementing type-safe wrappers for LHASH callbacks.
94 * This way, callbacks can be provided to LHASH structures without function
95 * pointer casting and the macro-defined callbacks provide per-variable casting
96 * before deferring to the underlying type-specific callbacks. NB: It is
97 * possible to place a "static" in front of both the DECLARE and IMPLEMENT
98 * macros if the functions are strictly internal. */
99
100/* First: "hash" functions */
101#define DECLARE_LHASH_HASH_FN(name, o_type) \
102 unsigned long name##_LHASH_HASH(const void *);
103#define IMPLEMENT_LHASH_HASH_FN(name, o_type) \
104 unsigned long name##_LHASH_HASH(const void *arg) { \
105 const o_type *a = arg; \
106 return name##_hash(a); }
107#define LHASH_HASH_FN(name) name##_LHASH_HASH
108
109/* Second: "compare" functions */
110#define DECLARE_LHASH_COMP_FN(name, o_type) \
111 int name##_LHASH_COMP(const void *, const void *);
112#define IMPLEMENT_LHASH_COMP_FN(name, o_type) \
113 int name##_LHASH_COMP(const void *arg1, const void *arg2) { \
114 const o_type *a = arg1; \
115 const o_type *b = arg2; \
116 return name##_cmp(a,b); }
117#define LHASH_COMP_FN(name) name##_LHASH_COMP
118
119/* Third: "doall" functions */
120#define DECLARE_LHASH_DOALL_FN(name, o_type) \
121 void name##_LHASH_DOALL(void *);
122#define IMPLEMENT_LHASH_DOALL_FN(name, o_type) \
123 void name##_LHASH_DOALL(void *arg) { \
124 o_type *a = arg; \
125 name##_doall(a); }
126#define LHASH_DOALL_FN(name) name##_LHASH_DOALL
127
128/* Fourth: "doall_arg" functions */
129#define DECLARE_LHASH_DOALL_ARG_FN(name, o_type, a_type) \
130 void name##_LHASH_DOALL_ARG(void *, void *);
131#define IMPLEMENT_LHASH_DOALL_ARG_FN(name, o_type, a_type) \
132 void name##_LHASH_DOALL_ARG(void *arg1, void *arg2) { \
133 o_type *a = arg1; \
134 a_type *b = arg2; \
135 name##_doall_arg(a, b); }
136#define LHASH_DOALL_ARG_FN(name) name##_LHASH_DOALL_ARG
137
138typedef struct lhash_st
139 {
140 LHASH_NODE **b;
141 LHASH_COMP_FN_TYPE comp;
142 LHASH_HASH_FN_TYPE hash;
143 unsigned int num_nodes;
144 unsigned int num_alloc_nodes;
145 unsigned int p;
146 unsigned int pmax;
147 unsigned long up_load; /* load times 256 */
148 unsigned long down_load; /* load times 256 */
149 unsigned long num_items;
150
151 unsigned long num_expands;
152 unsigned long num_expand_reallocs;
153 unsigned long num_contracts;
154 unsigned long num_contract_reallocs;
155 unsigned long num_hash_calls;
156 unsigned long num_comp_calls;
157 unsigned long num_insert;
158 unsigned long num_replace;
159 unsigned long num_delete;
160 unsigned long num_no_delete;
161 unsigned long num_retrieve;
162 unsigned long num_retrieve_miss;
163 unsigned long num_hash_comps;
164
165 int error;
166 } _LHASH; /* Do not use _LHASH directly, use LHASH_OF
167 * and friends */
168
169#define LH_LOAD_MULT 256
170
171/* Indicates a malloc() error in the last call, this is only bad
172 * in lh_insert(). */
173#define lh_error(lh) ((lh)->error)
174
175_LHASH *lh_new(LHASH_HASH_FN_TYPE h, LHASH_COMP_FN_TYPE c);
176void lh_free(_LHASH *lh);
177void *lh_insert(_LHASH *lh, void *data);
178void *lh_delete(_LHASH *lh, const void *data);
179void *lh_retrieve(_LHASH *lh, const void *data);
180void lh_doall(_LHASH *lh, LHASH_DOALL_FN_TYPE func);
181void lh_doall_arg(_LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg);
182unsigned long lh_strhash(const char *c);
183unsigned long lh_num_items(const _LHASH *lh);
184
185#ifndef OPENSSL_NO_FP_API
186void lh_stats(const _LHASH *lh, FILE *out);
187void lh_node_stats(const _LHASH *lh, FILE *out);
188void lh_node_usage_stats(const _LHASH *lh, FILE *out);
189#endif
190
191#ifndef OPENSSL_NO_BIO
192void lh_stats_bio(const _LHASH *lh, BIO *out);
193void lh_node_stats_bio(const _LHASH *lh, BIO *out);
194void lh_node_usage_stats_bio(const _LHASH *lh, BIO *out);
195#endif
196
197/* Type checking... */
198
199#define LHASH_OF(type) struct lhash_st_##type
200
201#define DECLARE_LHASH_OF(type) LHASH_OF(type) { int dummy; }
202
203#define CHECKED_LHASH_OF(type,lh) \
204 ((_LHASH *)CHECKED_PTR_OF(LHASH_OF(type),lh))
205
206/* Define wrapper functions. */
207#define LHM_lh_new(type, name) \
208 ((LHASH_OF(type) *)lh_new(LHASH_HASH_FN(name), LHASH_COMP_FN(name)))
209#define LHM_lh_error(type, lh) \
210 lh_error(CHECKED_LHASH_OF(type,lh))
211#define LHM_lh_insert(type, lh, inst) \
212 ((type *)lh_insert(CHECKED_LHASH_OF(type, lh), \
213 CHECKED_PTR_OF(type, inst)))
214#define LHM_lh_retrieve(type, lh, inst) \
215 ((type *)lh_retrieve(CHECKED_LHASH_OF(type, lh), \
216 CHECKED_PTR_OF(type, inst)))
217#define LHM_lh_delete(type, lh, inst) \
218 ((type *)lh_delete(CHECKED_LHASH_OF(type, lh), \
219 CHECKED_PTR_OF(type, inst)))
220#define LHM_lh_doall(type, lh,fn) lh_doall(CHECKED_LHASH_OF(type, lh), fn)
221#define LHM_lh_doall_arg(type, lh, fn, arg_type, arg) \
222 lh_doall_arg(CHECKED_LHASH_OF(type, lh), fn, CHECKED_PTR_OF(arg_type, arg))
223#define LHM_lh_num_items(type, lh) lh_num_items(CHECKED_LHASH_OF(type, lh))
224#define LHM_lh_down_load(type, lh) (CHECKED_LHASH_OF(type, lh)->down_load)
225#define LHM_lh_node_stats_bio(type, lh, out) \
226 lh_node_stats_bio(CHECKED_LHASH_OF(type, lh), out)
227#define LHM_lh_node_usage_stats_bio(type, lh, out) \
228 lh_node_usage_stats_bio(CHECKED_LHASH_OF(type, lh), out)
229#define LHM_lh_stats_bio(type, lh, out) \
230 lh_stats_bio(CHECKED_LHASH_OF(type, lh), out)
231#define LHM_lh_free(type, lh) lh_free(CHECKED_LHASH_OF(type, lh))
232
233DECLARE_LHASH_OF(OPENSSL_STRING);
234DECLARE_LHASH_OF(OPENSSL_CSTRING);
235
236#ifdef __cplusplus
237}
238#endif
239
240#endif
241
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-03-19 18:20:59 +0000