crypto/lhash/lhash.c

111 static void expand(_LHASH *lh);
112 static void contract(_LHASH *lh);
113 static LHASH_NODE **getrn(_LHASH *lh, const void *data, unsigned long *rhash);
158 void lh_free(_LHASH *lh)
163     if (lh == NULL)
166     for (i = 0; i < lh->num_nodes; i++) {
167         n = lh->b[i];
174     OPENSSL_free(lh->b);
175     OPENSSL_free(lh);
178 void *lh_insert(_LHASH *lh, void *data)
184     lh->error = 0;
185     if (lh->up_load <= (lh->num_items * LH_LOAD_MULT / lh->num_nodes))
186         expand(lh);
188     rn = getrn(lh, data, &hash);
192             lh->error++;
202         lh->num_insert++;
203         lh->num_items++;
208         lh->num_replace++;
213 void *lh_delete(_LHASH *lh, const void *data)
219     lh->error = 0;
220     rn = getrn(lh, data, &hash);
223         lh->num_no_delete++;
230         lh->num_delete++;
233     lh->num_items--;
234     if ((lh->num_nodes > MIN_NODES) &&
235         (lh->down_load >= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)))
236         contract(lh);
241 void *lh_retrieve(_LHASH *lh, const void *data)
247     lh->error = 0;
248     rn = getrn(lh, data, &hash);
251         lh->num_retrieve_miss++;
255         lh->num_retrieve++;
260 static void doall_util_fn(_LHASH *lh, int use_arg, LHASH_DOALL_FN_TYPE func,
266     if (lh == NULL)
273     for (i = lh->num_nodes - 1; i >= 0; i--) {
274         a = lh->b[i];
293 void lh_doall(_LHASH *lh, LHASH_DOALL_FN_TYPE func)
295     doall_util_fn(lh, 0, func, (LHASH_DOALL_ARG_FN_TYPE)0, NULL);
298 void lh_doall_arg(_LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg)
300     doall_util_fn(lh, 1, (LHASH_DOALL_FN_TYPE)0, func, arg);
303 static void expand(_LHASH *lh)
309     lh->num_nodes++;
310     lh->num_expands++;
311     p = (int)lh->p++;
312     n1 = &(lh->b[p]);
313     n2 = &(lh->b[p + (int)lh->pmax]);
315     nni = lh->num_alloc_nodes;
321         hash = lh->hash(np->data);
322         lh->num_hash_calls++;
333     if ((lh->p) >= lh->pmax) {
334         j = (int)lh->num_alloc_nodes * 2;
335         n = (LHASH_NODE **)OPENSSL_realloc(lh->b,
339             lh->error++;
340             lh->p = 0;
344         for (i = (int)lh->num_alloc_nodes; i < j; i++) /* 26/02/92 eay */
346         lh->pmax = lh->num_alloc_nodes;
347         lh->num_alloc_nodes = j;
348         lh->num_expand_reallocs++;
349         lh->p = 0;
350         lh->b = n;
354 static void contract(_LHASH *lh)
358     np = lh->b[lh->p + lh->pmax - 1];
359     lh->b[lh->p + lh->pmax - 1] = NULL; /* 24/07-92 - eay - weird but :-( */
360     if (lh->p == 0) {
361         n = (LHASH_NODE **)OPENSSL_realloc(lh->b,
363                                                           * lh->pmax));
366             lh->error++;
369         lh->num_contract_reallocs++;
370         lh->num_alloc_nodes /= 2;
371         lh->pmax /= 2;
372         lh->p = lh->pmax - 1;
373         lh->b = n;
375         lh->p--;
377     lh->num_nodes--;
378     lh->num_contracts++;
380     n1 = lh->b[(int)lh->p];
382         lh->b[(int)lh->p] = np;
390 static LHASH_NODE **getrn(_LHASH *lh, const void *data, unsigned long *rhash)
396     hash = (*(lh->hash)) (data);
397     lh->num_hash_calls++;
400     nn = hash % lh->pmax;
401     if (nn < lh->p)
402         nn = hash % lh->num_alloc_nodes;
404     cf = lh->comp;
405     ret = &(lh->b[(int)nn]);
408         lh->num_hash_comps++;
414         lh->num_comp_calls++;
455 unsigned long lh_num_items(const _LHASH *lh)
457     return lh ? lh->num_items : 0;