crypto/lhash/lhash.c

129 static int expand(_LHASH *lh);
130 static void contract(_LHASH *lh);
131 static LHASH_NODE **getrn(_LHASH *lh, const void *data, unsigned long *rhash);
176 void lh_free(_LHASH *lh)
181     if (lh == NULL)
184     for (i = 0; i < lh->num_nodes; i++) {
185         n = lh->b[i];
192     OPENSSL_free(lh->b);
193     OPENSSL_free(lh);
196 void *lh_insert(_LHASH *lh, void *data)
202     lh->error = 0;
203     if (lh->up_load <= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)
204             && !expand(lh))
207     rn = getrn(lh, data, &hash);
211             lh->error++;
221         lh->num_insert++;
222         lh->num_items++;
227         lh->num_replace++;
232 void *lh_delete(_LHASH *lh, const void *data)
238     lh->error = 0;
239     rn = getrn(lh, data, &hash);
242         lh->num_no_delete++;
249         lh->num_delete++;
252     lh->num_items--;
253     if ((lh->num_nodes > MIN_NODES) &&
254         (lh->down_load >= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)))
255         contract(lh);
260 void *lh_retrieve(_LHASH *lh, const void *data)
266     lh->error = 0;
267     rn = getrn(lh, data, &hash);
270         lh->num_retrieve_miss++;
274         lh->num_retrieve++;
279 static void doall_util_fn(_LHASH *lh, int use_arg, LHASH_DOALL_FN_TYPE func,
285     if (lh == NULL)
292     for (i = lh->num_nodes - 1; i >= 0; i--) {
293         a = lh->b[i];
312 void lh_doall(_LHASH *lh, LHASH_DOALL_FN_TYPE func)
314     doall_util_fn(lh, 0, func, (LHASH_DOALL_ARG_FN_TYPE)0, NULL);
317 void lh_doall_arg(_LHASH *lh, LHASH_DOALL_ARG_FN_TYPE func, void *arg)
319     doall_util_fn(lh, 1, (LHASH_DOALL_FN_TYPE)0, func, arg);
322 static int expand(_LHASH *lh)
328     nni = lh->num_alloc_nodes;
329     p = lh->p;
330     pmax = lh->pmax;
333         n = OPENSSL_realloc(lh->b, (int)(sizeof(LHASH_NODE *) * j));
335             lh->error++;
338         lh->b = n;
340         lh->pmax = nni;
341         lh->num_alloc_nodes = j;
342         lh->num_expand_reallocs++;
343         lh->p = 0;
345         lh->p++;
348     lh->num_nodes++;
349     lh->num_expands++;
350     n1 = &(lh->b[p]);
351     n2 = &(lh->b[p + pmax]);
358         hash = lh->hash(np->data);
359         lh->num_hash_calls++;
373 static void contract(_LHASH *lh)
377     np = lh->b[lh->p + lh->pmax - 1];
378     lh->b[lh->p + lh->pmax - 1] = NULL; /* 24/07-92 - eay - weird but :-( */
379     if (lh->p == 0) {
380         n = (LHASH_NODE **)OPENSSL_realloc(lh->b,
382                                                           * lh->pmax));
385             lh->error++;
388         lh->num_contract_reallocs++;
389         lh->num_alloc_nodes /= 2;
390         lh->pmax /= 2;
391         lh->p = lh->pmax - 1;
392         lh->b = n;
394         lh->p--;
396     lh->num_nodes--;
397     lh->num_contracts++;
399     n1 = lh->b[(int)lh->p];
401         lh->b[(int)lh->p] = np;
409 static LHASH_NODE **getrn(_LHASH *lh, const void *data, unsigned long *rhash)
415     hash = (*(lh->hash)) (data);
416     lh->num_hash_calls++;
419     nn = hash % lh->pmax;
420     if (nn < lh->p)
421         nn = hash % lh->num_alloc_nodes;
423     cf = lh->comp;
424     ret = &(lh->b[(int)nn]);
427         lh->num_hash_comps++;
433         lh->num_comp_calls++;
474 unsigned long lh_num_items(const _LHASH *lh)
476     return lh ? lh->num_items : 0;