Don't make any changes to the lhash structure if we are going to fail

[openssl.git] / crypto / lhash / lhash.c

diff --git a/crypto/lhash/lhash.c b/crypto/lhash/lhash.c
index 82de2235997935d8963630c6fb0dd45a8c8a21f8..1b0f26d0298b7962e7bb1ff28342b11ed5dbd771 100644 (file)
--- a/crypto/lhash/lhash.c
+++ b/crypto/lhash/lhash.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved.
  *
  * Licensed under the OpenSSL license (the "License").  You may not use
  * this file except in compliance with the License.  You can obtain a copy
@@ -14,6 +14,23 @@
 #include <openssl/lhash.h>
 #include "lhash_lcl.h"
 
+/*
+ * A hashing implementation that appears to be based on the linear hashing
+ * alogrithm:
+ * https://en.wikipedia.org/wiki/Linear_hashing
+ *
+ * Litwin, Witold (1980), "Linear hashing: A new tool for file and table
+ * addressing", Proc. 6th Conference on Very Large Databases: 212–223
+ * http://hackthology.com/pdfs/Litwin-1980-Linear_Hashing.pdf
+ *
+ * From the wikipedia article "Linear hashing is used in the BDB Berkeley
+ * database system, which in turn is used by many software systems such as
+ * OpenLDAP, using a C implementation derived from the CACM article and first
+ * published on the Usenet in 1988 by Esmond Pitt."
+ *
+ * The CACM paper is available here:
+ * https://pdfs.semanticscholar.org/ff4d/1c5deca6269cc316bfd952172284dbf610ee.pdf
+ */
 
 #undef MIN_NODES
 #define MIN_NODES       16
@@ -29,9 +46,9 @@ OPENSSL_LHASH *OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h, OPENSSL_LH_COMPFUNC c)
     OPENSSL_LHASH *ret;
 
     if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL)
-        goto err0;
+        return NULL;
     if ((ret->b = OPENSSL_zalloc(sizeof(*ret->b) * MIN_NODES)) == NULL)
-        goto err1;
+        goto err;
     ret->comp = ((c == NULL) ? (OPENSSL_LH_COMPFUNC)strcmp : c);
     ret->hash = ((h == NULL) ? (OPENSSL_LH_HASHFUNC)OPENSSL_LH_strhash : h);
     ret->num_nodes = MIN_NODES / 2;
@@ -39,12 +56,12 @@ OPENSSL_LHASH *OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h, OPENSSL_LH_COMPFUNC c)
     ret->pmax = MIN_NODES / 2;
     ret->up_load = UP_LOAD;
     ret->down_load = DOWN_LOAD;
-    return (ret);
+    return ret;
 
- err1:
+err:
+    OPENSSL_free(ret->b);
     OPENSSL_free(ret);
- err0:
-    return (NULL);
+    return NULL;
 }
 
 void OPENSSL_LH_free(OPENSSL_LHASH *lh)
@@ -82,7 +99,7 @@ void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data)
     if (*rn == NULL) {
         if ((nn = OPENSSL_malloc(sizeof(*nn))) == NULL) {
             lh->error++;
-            return (NULL);
+            return NULL;
         }
         nn->data = data;
         nn->next = NULL;
@@ -92,12 +109,11 @@ void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data)
         lh->num_insert++;
         lh->num_items++;
     } else {                    /* replace same key */
-
         ret = (*rn)->data;
         (*rn)->data = data;
         lh->num_replace++;
     }
-    return (ret);
+    return ret;
 }
 
 void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data)
@@ -111,7 +127,7 @@ void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data)
 
     if (*rn == NULL) {
         lh->num_no_delete++;
-        return (NULL);
+        return NULL;
     } else {
         nn = *rn;
         *rn = nn->next;
@@ -125,7 +141,7 @@ void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data)
         (lh->down_load >= (lh->num_items * LH_LOAD_MULT / lh->num_nodes)))
         contract(lh);
 
-    return (ret);
+    return ret;
 }
 
 void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data)
@@ -139,12 +155,12 @@ void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data)
 
     if (*rn == NULL) {
         lh->num_retrieve_miss++;
-        return (NULL);
+        return NULL;
     } else {
         ret = (*rn)->data;
         lh->num_retrieve++;
     }
-    return (ret);
+    return ret;
 }
 
 static void doall_util_fn(OPENSSL_LHASH *lh, int use_arg,
@@ -187,16 +203,34 @@ void OPENSSL_LH_doall_arg(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNCARG func, void
 static int expand(OPENSSL_LHASH *lh)
 {
     OPENSSL_LH_NODE **n, **n1, **n2, *np;
-    unsigned int p, i, j;
-    unsigned long hash, nni;
+    unsigned int p, pmax, nni, j;
+    unsigned long hash;
+
+    nni = lh->num_alloc_nodes;
+    p = lh->p;
+    pmax = lh->pmax;
+    if (p + 1 >= pmax) {
+        j = nni * 2;
+        n = OPENSSL_realloc(lh->b, sizeof(OPENSSL_LH_NODE *) * j);
+        if (n == NULL) {
+            lh->error++;
+            return 0;
+        }
+        lh->b = n;
+        memset(n + nni, 0, sizeof(*n) * (j - nni));
+        lh->pmax = nni;
+        lh->num_alloc_nodes = j;
+        lh->num_expand_reallocs++;
+        lh->p = 0;
+    } else {
+        lh->p++;
+    }
 
     lh->num_nodes++;
     lh->num_expands++;
-    p = (int)lh->p++;
     n1 = &(lh->b[p]);
-    n2 = &(lh->b[p + (int)lh->pmax]);
+    n2 = &(lh->b[p + pmax]);
     *n2 = NULL;
-    nni = lh->num_alloc_nodes;
 
     for (np = *n1; np != NULL;) {
         hash = np->hash;
@@ -209,23 +243,6 @@ static int expand(OPENSSL_LHASH *lh)
         np = *n1;
     }
 
-    if ((lh->p) >= lh->pmax) {
-        j = (int)lh->num_alloc_nodes * 2;
-        n = OPENSSL_realloc(lh->b, (int)(sizeof(OPENSSL_LH_NODE *) * j));
-        if (n == NULL) {
-            lh->error++;
-            lh->num_nodes--;
-            lh->p = 0;
-            return 0;
-        }
-        for (i = (int)lh->num_alloc_nodes; i < j; i++) /* 26/02/92 eay */
-            n[i] = NULL;        /* 02/03/92 eay */
-        lh->pmax = lh->num_alloc_nodes;
-        lh->num_alloc_nodes = j;
-        lh->num_expand_reallocs++;
-        lh->p = 0;
-        lh->b = n;
-    }
     return 1;
 }
 
@@ -292,7 +309,7 @@ static OPENSSL_LH_NODE **getrn(OPENSSL_LHASH *lh,
             break;
         ret = &(n1->next);
     }
-    return (ret);
+    return ret;
 }
 
 /*
@@ -308,7 +325,7 @@ unsigned long OPENSSL_LH_strhash(const char *c)
     int r;
 
     if ((c == NULL) || (*c == '\0'))
-        return (ret);
+        return ret;
 
     n = 0x100;
     while (*c) {
@@ -320,7 +337,7 @@ unsigned long OPENSSL_LH_strhash(const char *c)
         ret ^= v * v;
         c++;
     }
-    return ((ret >> 16) ^ ret);
+    return (ret >> 16) ^ ret;
 }
 
 unsigned long OPENSSL_LH_num_items(const OPENSSL_LHASH *lh)