Add sparse array data type.

This commit adds a space and time efficient sparse array data structure.
The structure's raw API is wrapped by inline functions which provide type
safety.

Reviewed-by: Richard Levitte <levitte@openssl.org>
Reviewed-by: Nicola Tuveri <nic.tuv@gmail.com>
(Merged from https://github.com/openssl/openssl/pull/8197)

1 files changed, 213 insertions, 0 deletions

diff --git a/crypto/sparse_array.c b/crypto/sparse_array.c
new file mode 100644
index 0000000000..8b56b257cf
--- /dev/null
+++ b/crypto/sparse_array.c
@@ -0,0 +1,213 @@
+/*
+ * Copyright 2019 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
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#include <openssl/crypto.h>
+#include "internal/sparse_array.h"
+
+/*
+ * How many bits are used to index each level in the tree structre?
+ * This setting determines the number of pointers stored in each node of the
+ * tree used to represent the sparse array.  Having more pointers reduces the
+ * 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 library builder is also permitted to define other sizes in the closed
+ * interval [2, sizeof(size_t) * 8].
+ */
+#ifndef OPENSSL_SA_BLOCK_BITS
+# ifdef OPENSSL_SMALL_FOOTPRINT
+#  define OPENSSL_SA_BLOCK_BITS           4
+# else
+#  define OPENSSL_SA_BLOCK_BITS           12
+# endif
+#elif OPENSSL_SA_BLOCK_BITS < 2 || OPENSSL_SA_BLOCK_BITS > BN_BITS2
+# error OPENSSL_SA_BLOCK_BITS is out of range
+#endif
+
+/*
+ * From the number of bits, work out:
+ *    the number of pointers in a tree node;
+ *    a bit mask to quickly extra an index and
+ *    the maximum depth of the tree structure.
+  */
+#define SA_BLOCK_MAX            (1 << OPENSSL_SA_BLOCK_BITS)
+#define SA_BLOCK_MASK           (SA_BLOCK_MAX - 1)
+#define SA_BLOCK_MAX_LEVELS     (((int)sizeof(size_t) * 8 \
+                                  + OPENSSL_SA_BLOCK_BITS - 1) \
+                                 / OPENSSL_SA_BLOCK_BITS)
+
+struct sparse_array_st {
+    int levels;
+    size_t top;
+    size_t nelem;
+    void **nodes;
+};
+
+OPENSSL_SA *OPENSSL_SA_new(void)
+{
+    OPENSSL_SA *res = OPENSSL_zalloc(sizeof(*res));
+
+    return res;
+}
+
+static void sa_doall(const OPENSSL_SA *sa, void (*node)(void **),
+                     void (*leaf)(void *, void *), void *arg)
+{
+    int i[SA_BLOCK_MAX_LEVELS];
+    void *nodes[SA_BLOCK_MAX_LEVELS];
+    int l = 0;
+
+    i[0] = 0;
+    nodes[0] = sa->nodes;
+    while (l >= 0) {
+        const int n = i[l];
+        void ** const p = nodes[l];
+
+        if (n >= SA_BLOCK_MAX) {
+            if (p != NULL && node != NULL)
+                (*node)(p);
+            l--;
+        } else {
+            i[l] = n + 1;
+            if (p != NULL && p[n] != NULL) {
+                if (l < sa->levels - 1) {
+                    i[++l] = 0;
+                    nodes[l] = p[n];
+                } else if (leaf != NULL) {
+                    (*leaf)(p[n], arg);
+                }
+            }
+        }
+    }
+}
+
+static void sa_free_node(void **p)
+{
+    OPENSSL_free(p);
+}
+
+static void sa_free_leaf(void *p, void *arg)
+{
+    OPENSSL_free(p);
+}
+
+void OPENSSL_SA_free(OPENSSL_SA *sa)
+{
+    sa_doall(sa, &sa_free_node, NULL, NULL);
+    OPENSSL_free(sa);
+}
+
+void OPENSSL_SA_free_leaves(OPENSSL_SA *sa)
+{
+    sa_doall(sa, &sa_free_node, &sa_free_leaf, NULL);
+    OPENSSL_free(sa);
+}
+
+/* Wrap this in a structure to avoid compiler warnings */
+struct trampoline_st {
+    void (*func)(void *);
+};
+
+static void trampoline(void *l, void *arg)
+{
+    ((const struct trampoline_st *)arg)->func(l);
+}
+
+void OPENSSL_SA_doall(const OPENSSL_SA *sa, void (*leaf)(void *))
+{
+    struct trampoline_st tramp;
+
+    tramp.func = leaf;
+    if (sa != NULL)
+        sa_doall(sa, NULL, &trampoline, &tramp);
+}
+
+void OPENSSL_SA_doall_arg(const OPENSSL_SA *sa, void (*leaf)(void *, void *),
+                          void *arg)
+{
+    if (sa != NULL)
+        sa_doall(sa, NULL, leaf, arg);
+}
+
+size_t OPENSSL_SA_num(const OPENSSL_SA *sa)
+{
+    return sa == NULL ? 0 : sa->nelem;
+}
+
+void *OPENSSL_SA_get(const OPENSSL_SA *sa, size_t n)
+{
+    int level;
+    void **p, *r = NULL;
+
+    if (sa == NULL)
+        return NULL;
+
+    if (n <= sa->top) {
+        p = sa->nodes;
+        for (level = sa->levels - 1; p != NULL && level > 0; level--)
+            p = (void **)p[(n >> (OPENSSL_SA_BLOCK_BITS * level))
+                           & SA_BLOCK_MASK];
+        r = p == NULL ? NULL : p[n & SA_BLOCK_MASK];
+    }
+    return r;
+}
+
+static ossl_inline void **alloc_node(void)
+{
+    return OPENSSL_zalloc(SA_BLOCK_MAX * sizeof(void *));
+}
+
+int OPENSSL_SA_set(OPENSSL_SA *sa, size_t posn, void *val)
+{
+    int i, level = 1;
+    size_t n = posn;
+    void **p;
+
+    if (sa == NULL)
+        return 0;
+
+    for (level = 1; level <= SA_BLOCK_MAX_LEVELS; level++)
+        if ((n >>= OPENSSL_SA_BLOCK_BITS) == 0)
+            break;
+
+    for (;sa->levels < level; sa->levels++) {
+        p = alloc_node();
+        if (p == NULL)
+            return 0;
+        p[0] = sa->nodes;
+        sa->nodes = p;
+    }
+    if (sa->top < posn)
+        sa->top = posn;
+
+    p = sa->nodes;
+    for (level = sa->levels - 1; level > 0; level--) {
+        i = (posn >> (OPENSSL_SA_BLOCK_BITS * level)) & SA_BLOCK_MASK;
+        if (p[i] == NULL && (p[i] = alloc_node()) == NULL)
+            return 0;
+        p = p[i];
+    }
+    p += posn & SA_BLOCK_MASK;
+    if (val == NULL && *p != NULL)
+        sa->nelem--;
+    else if (val != NULL && *p == NULL)
+        sa->nelem++;
+    *p = val;
+    return 1;
+}