Fix up path generation to use OPENSSL_MODULES

[openssl.git] / crypto / sparse_array.c

diff --git a/crypto/sparse_array.c b/crypto/sparse_array.c
index 9d444739f53ab8c4098a14fab58ee03c4007b37a..bb378edacbc0b3271663b13ffd5c8b9252956cc1 100644 (file)
--- a/crypto/sparse_array.c
+++ b/crypto/sparse_array.c
@@ -1,5 +1,5 @@
 /*
- * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2019-2022 The OpenSSL Project Authors. All Rights Reserved.
  * Copyright (c) 2019, Oracle and/or its affiliates.  All rights reserved.
  *
  * Licensed under the Apache License 2.0 (the "License").  You may not use
@@ -19,24 +19,19 @@
  * depth of the tree but potentially wastes more memory.  That is, this is a
  * direct space versus time tradeoff.
  *
- * The large memory model uses twelve bits which means that the are 4096
- * pointers in each tree node.  This is more than sufficient to hold the
- * largest defined NID (as of Feb 2019).  This means that using a NID to
- * index a sparse array becomes a constant time single array look up.
- *
- * The small memory model uses four bits which means the tree nodes contain
- * sixteen pointers.  This reduces the amount of unused space significantly
- * at a cost in time.
+ * The default is to use four bits which means that there are 16
+ * pointers in each tree node.
  *
  * The library builder is also permitted to define other sizes in the closed
- * interval [2, sizeof(ossl_uintmax_t) * 8].
+ * interval [2, sizeof(ossl_uintmax_t) * 8].  Space use generally scales
+ * exponentially with the block size, although the implementation only
+ * creates enough blocks to support the largest used index.  The depth is:
+ *      ceil(log_2(largest index) / 2^{block size})
+ * E.g. with a block size of 4, and a largest index of 1000, the depth
+ * will be three.
  */
 #ifndef OPENSSL_SA_BLOCK_BITS
-# ifdef OPENSSL_SMALL_FOOTPRINT
-#  define OPENSSL_SA_BLOCK_BITS           4
-# else
-#  define OPENSSL_SA_BLOCK_BITS           12
-# endif
+# define OPENSSL_SA_BLOCK_BITS           4
 #elif OPENSSL_SA_BLOCK_BITS < 2 || OPENSSL_SA_BLOCK_BITS > (BN_BITS2 - 1)
 # error OPENSSL_SA_BLOCK_BITS is out of range
 #endif
@@ -60,7 +55,7 @@ struct sparse_array_st {
     void **nodes;
 };
 
-OPENSSL_SA *OPENSSL_SA_new(void)
+OPENSSL_SA *ossl_sa_new(void)
 {
     OPENSSL_SA *res = OPENSSL_zalloc(sizeof(*res));
 
@@ -112,13 +107,15 @@ static void sa_free_leaf(ossl_uintmax_t n, void *p, void *arg)
     OPENSSL_free(p);
 }
 
-void OPENSSL_SA_free(OPENSSL_SA *sa)
+void ossl_sa_free(OPENSSL_SA *sa)
 {
-    sa_doall(sa, &sa_free_node, NULL, NULL);
-    OPENSSL_free(sa);
+    if (sa != NULL) {
+        sa_doall(sa, &sa_free_node, NULL, NULL);
+        OPENSSL_free(sa);
+    }
 }
 
-void OPENSSL_SA_free_leaves(OPENSSL_SA *sa)
+void ossl_sa_free_leaves(OPENSSL_SA *sa)
 {
     sa_doall(sa, &sa_free_node, &sa_free_leaf, NULL);
     OPENSSL_free(sa);
@@ -134,8 +131,7 @@ static void trampoline(ossl_uintmax_t n, void *l, void *arg)
     ((const struct trampoline_st *)arg)->func(n, l);
 }
 
-void OPENSSL_SA_doall(const OPENSSL_SA *sa, void (*leaf)(ossl_uintmax_t,
-                                                         void *))
+void ossl_sa_doall(const OPENSSL_SA *sa, void (*leaf)(ossl_uintmax_t, void *))
 {
     struct trampoline_st tramp;
 
@@ -144,7 +140,7 @@ void OPENSSL_SA_doall(const OPENSSL_SA *sa, void (*leaf)(ossl_uintmax_t,
         sa_doall(sa, NULL, &trampoline, &tramp);
 }
 
-void OPENSSL_SA_doall_arg(const OPENSSL_SA *sa,
+void ossl_sa_doall_arg(const OPENSSL_SA *sa,
                           void (*leaf)(ossl_uintmax_t, void *, void *),
                           void *arg)
 {
@@ -152,17 +148,17 @@ void OPENSSL_SA_doall_arg(const OPENSSL_SA *sa,
         sa_doall(sa, NULL, leaf, arg);
 }
 
-size_t OPENSSL_SA_num(const OPENSSL_SA *sa)
+size_t ossl_sa_num(const OPENSSL_SA *sa)
 {
     return sa == NULL ? 0 : sa->nelem;
 }
 
-void *OPENSSL_SA_get(const OPENSSL_SA *sa, ossl_uintmax_t n)
+void *ossl_sa_get(const OPENSSL_SA *sa, ossl_uintmax_t n)
 {
     int level;
     void **p, *r = NULL;
 
-    if (sa == NULL)
+    if (sa == NULL || sa->nelem == 0)
         return NULL;
 
     if (n <= sa->top) {
@@ -180,7 +176,7 @@ static ossl_inline void **alloc_node(void)
     return OPENSSL_zalloc(SA_BLOCK_MAX * sizeof(void *));
 }
 
-int OPENSSL_SA_set(OPENSSL_SA *sa, ossl_uintmax_t posn, void *val)
+int ossl_sa_set(OPENSSL_SA *sa, ossl_uintmax_t posn, void *val)
 {
     int i, level = 1;
     ossl_uintmax_t n = posn;