crypto/lhash/lhash.c

   1 /*
   2  * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved.
   3  *
   4  * Licensed under the OpenSSL license (the "License").  You may not use
   5  * this file except in compliance with the License.  You can obtain a copy
   6  * in the file LICENSE in the source distribution or at
   7  * https://www.openssl.org/source/license.html
   8  */
   9
  10 #include <stdio.h>
  11 #include <string.h>
  12 #include <stdlib.h>
  13 #include <openssl/crypto.h>
  14 #include <openssl/lhash.h>
  15 #include "lhash_lcl.h"
  16
  17 /*
  18  * A hashing implementation that appears to be based on the linear hashing
  19  * alogrithm:
  20  * https://en.wikipedia.org/wiki/Linear_hashing
  21  *
  22  * Litwin, Witold (1980), "Linear hashing: A new tool for file and table
  23  * addressing", Proc. 6th Conference on Very Large Databases: 212–223
  24  * http://hackthology.com/pdfs/Litwin-1980-Linear_Hashing.pdf
  25  *
  26  * From the wikipedia article "Linear hashing is used in the BDB Berkeley
  27  * database system, which in turn is used by many software systems such as
  28  * OpenLDAP, using a C implementation derived from the CACM article and first
  29  * published on the Usenet in 1988 by Esmond Pitt."
  30  *
  31  * The CACM paper is available here:
  32  * https://pdfs.semanticscholar.org/ff4d/1c5deca6269cc316bfd952172284dbf610ee.pdf
  33  */
  34
  35 #undef MIN_NODES
  36 #define MIN_NODES       16
  37 #define UP_LOAD         (2*LH_LOAD_MULT) /* load times 256 (default 2) */
  38 #define DOWN_LOAD       (LH_LOAD_MULT) /* load times 256 (default 1) */
  39
  40 static int expand(OPENSSL_LHASH *lh);
  41 static void contract(OPENSSL_LHASH *lh);
  42 static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh, const void *data, unsigned long *rhash);
  43
  44 OPENSSL_LHASH *OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h, OPENSSL_LH_COMPFUNC c)
  45 {
  46     OPENSSL_LHASH *ret;
  47
  48     if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL)
  49         return NULL;
  50     if ((ret->b = OPENSSL_zalloc(sizeof(*ret->b) * MIN_NODES)) == NULL)
  51         goto err;
  52     ret->comp = ((c == NULL) ? (OPENSSL_LH_COMPFUNC)strcmp : c);
  53     ret->hash = ((h == NULL) ? (OPENSSL_LH_HASHFUNC)OPENSSL_LH_strhash : h);
  54     ret->num_nodes = MIN_NODES / 2;
  55     ret->num_alloc_nodes = MIN_NODES;
  56     ret->pmax = MIN_NODES / 2;
  57     ret->up_load = UP_LOAD;
  58     ret->down_load = DOWN_LOAD;
  59     return ret;
  60
  61 err:
  62     OPENSSL_free(ret->b);
  63     OPENSSL_free(ret);
  64     return NULL;
  65 }
  66
  67 void OPENSSL_LH_free(OPENSSL_LHASH *lh)
  68 {
  69     unsigned int i;
  70     OPENSSL_LH_NODE *n, *nn;
  71
  72     if (lh == NULL)
  73         return;
  74
  75     for (i = 0; i < lh->num_nodes; i++) {
  76         n = lh->b[i];
  77         while (n != NULL) {
  78             nn = n->next;
  79             OPENSSL_free(n);
  80             n = nn;
  81         }
  82     }
  83     OPENSSL_free(lh->b);
  84     OPENSSL_free(lh);
  85 }
  86
  87 void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data)
  88 {
  89     unsigned long hash;
  90     OPENSSL_LH_NODE *nn, **rn;
  91     void *ret;
  92
  93     lh->error = 0;
  94     if ((lh->up_load <= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)) && !expand(lh))
  95         return NULL;        /* 'lh->error++' already done in 'expand' */
  96
  97     rn = getrn(lh, data, &hash);
  98
  99     if (*rn == NULL) {
 100         if ((nn = OPENSSL_malloc(sizeof(*nn))) == NULL) {
 101             lh->error++;
 102             return NULL;
 103         }
 104         nn->data = data;
 105         nn->next = NULL;
 106         nn->hash = hash;
 107         *rn = nn;
 108         ret = NULL;
 109         lh->num_insert++;
 110         lh->num_items++;
 111     } else {                    /* replace same key */
 112         ret = (*rn)->data;
 113         (*rn)->data = data;
 114         lh->num_replace++;
 115     }
 116     return ret;
 117 }
 118
 119 void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data)
 120 {
 121     unsigned long hash;
 122     OPENSSL_LH_NODE *nn, **rn;
 123     void *ret;
 124
 125     lh->error = 0;
 126     rn = getrn(lh, data, &hash);
 127
 128     if (*rn == NULL) {
 129         lh->num_no_delete++;
 130         return NULL;
 131     } else {
 132         nn = *rn;
 133         *rn = nn->next;
 134         ret = nn->data;
 135         OPENSSL_free(nn);
 136         lh->num_delete++;
 137     }
 138
 139     lh->num_items--;
 140     if ((lh->num_nodes > MIN_NODES) &&
 141         (lh->down_load >= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)))
 142         contract(lh);
 143
 144     return ret;
 145 }
 146
 147 void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data)
 148 {
 149     unsigned long hash;
 150     OPENSSL_LH_NODE **rn;
 151     void *ret;
 152
 153     lh->error = 0;
 154     rn = getrn(lh, data, &hash);
 155
 156     if (*rn == NULL) {
 157         lh->num_retrieve_miss++;
 158         return NULL;
 159     } else {
 160         ret = (*rn)->data;
 161         lh->num_retrieve++;
 162     }
 163     return ret;
 164 }
 165
 166 static void doall_util_fn(OPENSSL_LHASH *lh, int use_arg,
 167                           OPENSSL_LH_DOALL_FUNC func,
 168                           OPENSSL_LH_DOALL_FUNCARG func_arg, void *arg)
 169 {
 170     int i;
 171     OPENSSL_LH_NODE *a, *n;
 172
 173     if (lh == NULL)
 174         return;
 175
 176     /*
 177      * reverse the order so we search from 'top to bottom' We were having
 178      * memory leaks otherwise
 179      */
 180     for (i = lh->num_nodes - 1; i >= 0; i--) {
 181         a = lh->b[i];
 182         while (a != NULL) {
 183             n = a->next;
 184             if (use_arg)
 185                 func_arg(a->data, arg);
 186             else
 187                 func(a->data);
 188             a = n;
 189         }
 190     }
 191 }
 192
 193 void OPENSSL_LH_doall(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNC func)
 194 {
 195     doall_util_fn(lh, 0, func, (OPENSSL_LH_DOALL_FUNCARG)0, NULL);
 196 }
 197
 198 void OPENSSL_LH_doall_arg(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNCARG func, void *arg)
 199 {
 200     doall_util_fn(lh, 1, (OPENSSL_LH_DOALL_FUNC)0, func, arg);
 201 }
 202
 203 static int expand(OPENSSL_LHASH *lh)
 204 {
 205     OPENSSL_LH_NODE **n, **n1, **n2, *np;
 206     unsigned int p, pmax, nni, j;
 207     unsigned long hash;
 208
 209     nni = lh->num_alloc_nodes;
 210     p = lh->p;
 211     pmax = lh->pmax;
 212     if (p + 1 >= pmax) {
 213         j = nni * 2;
 214         n = OPENSSL_realloc(lh->b, sizeof(OPENSSL_LH_NODE *) * j);
 215         if (n == NULL) {
 216             lh->error++;
 217             return 0;
 218         }
 219         lh->b = n;
 220         memset(n + nni, 0, sizeof(*n) * (j - nni));
 221         lh->pmax = nni;
 222         lh->num_alloc_nodes = j;
 223         lh->num_expand_reallocs++;
 224         lh->p = 0;
 225     } else {
 226         lh->p++;
 227     }
 228
 229     lh->num_nodes++;
 230     lh->num_expands++;
 231     n1 = &(lh->b[p]);
 232     n2 = &(lh->b[p + pmax]);
 233     *n2 = NULL;
 234
 235     for (np = *n1; np != NULL;) {
 236         hash = np->hash;
 237         if ((hash % nni) != p) { /* move it */
 238             *n1 = (*n1)->next;
 239             np->next = *n2;
 240             *n2 = np;
 241         } else
 242             n1 = &((*n1)->next);
 243         np = *n1;
 244     }
 245
 246     return 1;
 247 }
 248
 249 static void contract(OPENSSL_LHASH *lh)
 250 {
 251     OPENSSL_LH_NODE **n, *n1, *np;
 252
 253     np = lh->b[lh->p + lh->pmax - 1];
 254     lh->b[lh->p + lh->pmax - 1] = NULL; /* 24/07-92 - eay - weird but :-( */
 255     if (lh->p == 0) {
 256         n = OPENSSL_realloc(lh->b,
 257                             (unsigned int)(sizeof(OPENSSL_LH_NODE *) * lh->pmax));
 258         if (n == NULL) {
 259             /* fputs("realloc error in lhash",stderr); */
 260             lh->error++;
 261             return;
 262         }
 263         lh->num_contract_reallocs++;
 264         lh->num_alloc_nodes /= 2;
 265         lh->pmax /= 2;
 266         lh->p = lh->pmax - 1;
 267         lh->b = n;
 268     } else
 269         lh->p--;
 270
 271     lh->num_nodes--;
 272     lh->num_contracts++;
 273
 274     n1 = lh->b[(int)lh->p];
 275     if (n1 == NULL)
 276         lh->b[(int)lh->p] = np;
 277     else {
 278         while (n1->next != NULL)
 279             n1 = n1->next;
 280         n1->next = np;
 281     }
 282 }
 283
 284 static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh,
 285                                const void *data, unsigned long *rhash)
 286 {
 287     OPENSSL_LH_NODE **ret, *n1;
 288     unsigned long hash, nn;
 289     OPENSSL_LH_COMPFUNC cf;
 290
 291     hash = (*(lh->hash)) (data);
 292     lh->num_hash_calls++;
 293     *rhash = hash;
 294
 295     nn = hash % lh->pmax;
 296     if (nn < lh->p)
 297         nn = hash % lh->num_alloc_nodes;
 298
 299     cf = lh->comp;
 300     ret = &(lh->b[(int)nn]);
 301     for (n1 = *ret; n1 != NULL; n1 = n1->next) {
 302         lh->num_hash_comps++;
 303         if (n1->hash != hash) {
 304             ret = &(n1->next);
 305             continue;
 306         }
 307         lh->num_comp_calls++;
 308         if (cf(n1->data, data) == 0)
 309             break;
 310         ret = &(n1->next);
 311     }
 312     return ret;
 313 }
 314
 315 /*
 316  * The following hash seems to work very well on normal text strings no
 317  * collisions on /usr/dict/words and it distributes on %2^n quite well, not
 318  * as good as MD5, but still good.
 319  */
 320 unsigned long OPENSSL_LH_strhash(const char *c)
 321 {
 322     unsigned long ret = 0;
 323     long n;
 324     unsigned long v;
 325     int r;
 326
 327     if ((c == NULL) || (*c == '\0'))
 328         return ret;
 329
 330     n = 0x100;
 331     while (*c) {
 332         v = n | (*c);
 333         n += 0x100;
 334         r = (int)((v >> 2) ^ v) & 0x0f;
 335         ret = (ret << r) | (ret >> (32 - r));
 336         ret &= 0xFFFFFFFFL;
 337         ret ^= v * v;
 338         c++;
 339     }
 340     return (ret >> 16) ^ ret;
 341 }
 342
 343 unsigned long OPENSSL_LH_num_items(const OPENSSL_LHASH *lh)
 344 {
 345     return lh ? lh->num_items : 0;
 346 }
 347
 348 unsigned long OPENSSL_LH_get_down_load(const OPENSSL_LHASH *lh)
 349 {
 350     return lh->down_load;
 351 }
 352
 353 void OPENSSL_LH_set_down_load(OPENSSL_LHASH *lh, unsigned long down_load)
 354 {
 355     lh->down_load = down_load;
 356 }
 357
 358 int OPENSSL_LH_error(OPENSSL_LHASH *lh)
 359 {
 360     return lh->error;
 361 }