Add sparse array data type.
authorPauli <paul.dale@oracle.com>
Thu, 24 Jan 2019 02:15:54 +0000 (12:15 +1000)
committerPauli <paul.dale@oracle.com>
Tue, 12 Feb 2019 11:07:29 +0000 (21:07 +1000)
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)

crypto/README.sparse_array [new file with mode: 0644]
crypto/build.info
crypto/include/internal/sparse_array.h [new file with mode: 0644]
crypto/sparse_array.c [new file with mode: 0644]
doc/internal/man3/DEFINE_SPARSE_ARRAY_OF.pod [new file with mode: 0644]
test/build.info
test/recipes/02-test_sparse_array.t [new file with mode: 0644]
test/sparse_array_test.c [new file with mode: 0644]

diff --git a/crypto/README.sparse_array b/crypto/README.sparse_array
new file mode 100644 (file)
index 0000000..947c34d
--- /dev/null
@@ -0,0 +1,155 @@
+The sparse_array.c file contains an implementation of a sparse array that
+attempts to be both space and time efficient.
+
+The sparse array is represented using a tree structure.  Each node in the
+tree contains a block of pointers to either the user supplied leaf values or
+to another node.
+
+There are a number of parameters used to define the block size:
+
+    OPENSSL_SA_BLOCK_BITS   Specifies the number of bits covered by each block
+    SA_BLOCK_MAX            Specifies the number of pointers in each block
+    SA_BLOCK_MASK           Specifies a bit mask to perform modulo block size
+    SA_BLOCK_MAX_LEVELS     Indicates the maximum possible height of the tree
+
+These constants are inter-related:
+    SA_BLOCK_MAX        = 2 ^ OPENSSL_SA_BLOCK_BITS
+    SA_BLOCK_MASK       = SA_BLOCK_MAX - 1
+    SA_BLOCK_MAX_LEVELS = number of bits in size_t divided by
+                          OPENSSL_SA_BLOCK_BITS rounded up to the next multiple
+                          of OPENSSL_SA_BLOCK_BITS
+
+OPENSSL_SA_BLOCK_BITS can be defined at compile time and this overrides the
+built in setting.
+
+As a space and performance optimisation, the height of the tree is usually
+less than the maximum possible height.  Only sufficient height is allocated to
+accommodate the largest index added to the data structure.
+
+The largest index used to add a value to the array determines the tree height:
+
+        +----------------------+---------------------+
+        | Largest Added Index  |   Height of Tree    |
+        +----------------------+---------------------+
+        | SA_BLOCK_MAX     - 1 |          1          |
+        | SA_BLOCK_MAX ^ 2 - 1 |          2          |
+        | SA_BLOCK_MAX ^ 3 - 1 |          3          |
+        | ...                  |          ...        |
+        | size_t max           | SA_BLOCK_MAX_LEVELS |
+        +----------------------+---------------------+
+
+The tree height is dynamically increased as needed based on additions.
+
+An empty tree is represented by a NULL root pointer.  Inserting a value at
+index 0 results in the allocation of a top level node full of null pointers
+except for the single pointer to the user's data (N = SA_BLOCK_MAX for
+breviety):
+
+        +----+
+        |Root|
+        |Node|
+        +-+--+
+          |
+          |
+          |
+          v
+        +-+-+---+---+---+---+
+        | 0 | 1 | 2 |...|N-1|
+        |   |nil|nil|...|nil|
+        +-+-+---+---+---+---+
+          |
+          |
+          |
+          v
+        +-+--+
+        |User|
+        |Data|
+        +----+
+    Index 0
+
+
+Inserting at element 2N+1 creates a new root node and pushes down the old root
+node.  It then creates a second second level node to hold the pointer to the
+user's new data:
+
+        +----+
+        |Root|
+        |Node|
+        +-+--+
+          |
+          |
+          |
+          v
+        +-+-+---+---+---+---+
+        | 0 | 1 | 2 |...|N-1|
+        |   |nil|   |...|nil|
+        +-+-+---+-+-+---+---+
+          |       |
+          |       +------------------+
+          |                          |
+          v                          v
+        +-+-+---+---+---+---+      +-+-+---+---+---+---+
+        | 0 | 1 | 2 |...|N-1|      | 0 | 1 | 2 |...|N-1|
+        |nil|   |nil|...|nil|      |nil|   |nil|...|nil|
+        +-+-+---+---+---+---+      +---+-+-+---+---+---+
+          |                              |
+          |                              |
+          |                              |
+          v                              v
+        +-+--+                         +-+--+
+        |User|                         |User|
+        |Data|                         |Data|
+        +----+                         +----+
+    Index 0                       Index 2N+1
+
+
+The nodes themselves are allocated in a sparse manner.  Only nodes which exist
+along a path from the root of the tree to an added leaf will be allocated.
+The complexity is hidden and nodes are allocated on an as needed basis.
+Because the data is expected to be sparse this doesn't result in a large waste
+of space.
+
+Values can be removed from the sparse array by setting their index position to
+NULL.  The data structure does not attempt to reclaim nodes or reduce the
+height of the tree on removal.  For example, now setting index 0 to NULL would
+result in:
+
+        +----+
+        |Root|
+        |Node|
+        +-+--+
+          |
+          |
+          |
+          v
+        +-+-+---+---+---+---+
+        | 0 | 1 | 2 |...|N-1|
+        |   |nil|   |...|nil|
+        +-+-+---+-+-+---+---+
+          |       |
+          |       +------------------+
+          |                          |
+          v                          v
+        +-+-+---+---+---+---+      +-+-+---+---+---+---+
+        | 0 | 1 | 2 |...|N-1|      | 0 | 1 | 2 |...|N-1|
+        |nil|nil|nil|...|nil|      |nil|   |nil|...|nil|
+        +---+---+---+---+---+      +---+-+-+---+---+---+
+                                         |
+                                         |
+                                         |
+                                         v
+                                       +-+--+
+                                       |User|
+                                       |Data|
+                                       +----+
+                                  Index 2N+1
+
+
+Accesses to elements in the sparse array take O(log n) time where n is the
+largest element.  The base of the logarithm is SA_BLOCK_MAX, so for moderately
+small indices (e.g. NIDs), single level (constant time) access is achievable.
+Space usage is O(minimum(m, n log(n)) where m is the number of elements in the
+array.
+
+Note: sparse arrays only include pointers to types.  Thus, SPARSE_ARRAY_OF(char)
+can be used to store a string.
index 5e879ea..3b67315 100644 (file)
@@ -12,8 +12,8 @@ SOURCE[../libcrypto]=\
         cryptlib.c mem.c mem_dbg.c cversion.c ex_data.c cpt_err.c \
         ebcdic.c uid.c o_time.c o_str.c o_dir.c o_fopen.c ctype.c \
         threads_pthread.c threads_win.c threads_none.c getenv.c \
         cryptlib.c mem.c mem_dbg.c cversion.c ex_data.c cpt_err.c \
         ebcdic.c uid.c o_time.c o_str.c o_dir.c o_fopen.c ctype.c \
         threads_pthread.c threads_win.c threads_none.c getenv.c \
-        o_init.c o_fips.c mem_sec.c init.c {- $target{cpuid_asm_src} -} \
-        {- $target{uplink_aux_src} -}
+        o_init.c o_fips.c mem_sec.c init.c sparse_array.c \
+        {- $target{cpuid_asm_src} -} {- $target{uplink_aux_src} -}
 
 DEPEND[cversion.o]=buildinf.h
 GENERATE[buildinf.h]=../util/mkbuildinf.pl "$(CC) $(LIB_CFLAGS) $(CPPFLAGS_Q)" "$(PLATFORM)"
 
 DEPEND[cversion.o]=buildinf.h
 GENERATE[buildinf.h]=../util/mkbuildinf.pl "$(CC) $(LIB_CFLAGS) $(CPPFLAGS_Q)" "$(PLATFORM)"
diff --git a/crypto/include/internal/sparse_array.h b/crypto/include/internal/sparse_array.h
new file mode 100644 (file)
index 0000000..bf0a996
--- /dev/null
@@ -0,0 +1,78 @@
+/*
+ * 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
+ */
+
+#ifndef HEADER_SPARSE_ARRAY_H
+# define HEADER_SPARSE_ARRAY_H
+
+# ifdef __cplusplus
+extern "C" {
+# endif
+
+# define SPARSE_ARRAY_OF(type) struct sparse_array_st_ ## type
+
+# define DEFINE_SPARSE_ARRAY_OF(type) \
+    SPARSE_ARRAY_OF(type); \
+    static ossl_inline SPARSE_ARRAY_OF(type) * \
+        ossl_sa_##type##_new(void) \
+    { \
+        return (SPARSE_ARRAY_OF(type) *)OPENSSL_SA_new(); \
+    } \
+    static ossl_inline void ossl_sa_##type##_free(SPARSE_ARRAY_OF(type) *sa) \
+    { \
+        OPENSSL_SA_free((OPENSSL_SA *)sa); \
+    } \
+    static ossl_inline void ossl_sa_##type##_free_leaves(SPARSE_ARRAY_OF(type) *sa) \
+    { \
+        OPENSSL_SA_free_leaves((OPENSSL_SA *)sa); \
+    } \
+    static ossl_inline size_t ossl_sa_##type##_num(const SPARSE_ARRAY_OF(type) *sa) \
+    { \
+        return OPENSSL_SA_num((OPENSSL_SA *)sa); \
+    } \
+    static ossl_inline void ossl_sa_##type##_doall(const SPARSE_ARRAY_OF(type) *sa, \
+                                                   void (*leaf)(type *)) \
+    { \
+        OPENSSL_SA_doall((OPENSSL_SA *)sa, (void (*)(void *))leaf); \
+    } \
+    static ossl_inline void ossl_sa_##type##_doall_arg(const SPARSE_ARRAY_OF(type) *sa, \
+                                                       void (*leaf)(type *, \
+                                                                   void *),\
+                                                       void *arg) \
+    { \
+        OPENSSL_SA_doall_arg((OPENSSL_SA *)sa, (void (*)(void *, void *))leaf, \
+                             arg); \
+    } \
+    static ossl_inline type *ossl_sa_##type##_get(const SPARSE_ARRAY_OF(type) *sa, \
+                                                  size_t n) \
+    { \
+        return (type *)OPENSSL_SA_get((OPENSSL_SA *)sa, n); \
+    } \
+    static ossl_inline int ossl_sa_##type##_set(SPARSE_ARRAY_OF(type) *sa, \
+                                                size_t n, type *val) \
+    { \
+        return OPENSSL_SA_set((OPENSSL_SA *)sa, n, (void *)val); \
+    } \
+    SPARSE_ARRAY_OF(type)
+
+typedef struct sparse_array_st OPENSSL_SA;
+OPENSSL_SA *OPENSSL_SA_new(void);
+void OPENSSL_SA_free(OPENSSL_SA *sa);
+void OPENSSL_SA_free_leaves(OPENSSL_SA *sa);
+size_t OPENSSL_SA_num(const OPENSSL_SA *sa);
+void OPENSSL_SA_doall(const OPENSSL_SA *sa, void (*leaf)(void *));
+void OPENSSL_SA_doall_arg(const OPENSSL_SA *sa, void (*leaf)(void *, void *),
+                          void *);
+void *OPENSSL_SA_get(const OPENSSL_SA *sa, size_t n);
+int OPENSSL_SA_set(OPENSSL_SA *sa, size_t n, void *val);
+
+# ifdef  __cplusplus
+}
+# endif
+#endif
diff --git a/crypto/sparse_array.c b/crypto/sparse_array.c
new file mode 100644 (file)
index 0000000..8b56b25
--- /dev/null
@@ -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;
+}
diff --git a/doc/internal/man3/DEFINE_SPARSE_ARRAY_OF.pod b/doc/internal/man3/DEFINE_SPARSE_ARRAY_OF.pod
new file mode 100644 (file)
index 0000000..146f02d
--- /dev/null
@@ -0,0 +1,112 @@
+=pod
+
+=head1 NAME
+
+DEFINE_SPARSE_ARRAY_OF, ossl_sa_TYPE_new, ossl_sa_TYPE_free,
+ossl_sa_TYPE_free_leaves, ossl_sa_TYPE_num, ossl_sa_TYPE_doall,
+ossl_sa_TYPE_doall_arg, ossl_sa_TYPE_get, ossl_sa_TYPE_set
+- sparse array container
+
+=head1 SYNOPSIS
+
+ #include "internal/sparse_array.h"
+
+ typedef struct sparse_array_st OPENSSL_SA;
+
+ SPARSE_ARRAY_OF(TYPE)
+ DEFINE_SPARSE_ARRAY_OF(TYPE)
+
+ SPARSE_ARRAY_OF(TYPE) *ossl_sa_TYPE_new(void);
+ void ossl_sa_TYPE_free(const SPARSE_ARRAY_OF(TYPE) *sa);
+ void ossl_sa_TYPE_free_leaves(const SPARSE_ARRAY_OF(TYPE) *sa);
+ int ossl_sa_TYPE_num(const SPARSE_ARRAY_OF(TYPE) *sa);
+ void ossl_sa_TYPE_doall(const OPENSSL_SA *sa, void (*leaf)(void *));
+ void ossl_sa_TYPE_doall_arg(const OPENSSL_SA *sa, void (*leaf)(void *), void *arg);
+ TYPE *ossl_sa_TYPE_get(const SPARSE_ARRAY_OF(TYPE) *sa, size_t idx);
+ int ossl_sa_TYPE_set(SPARSE_ARRAY_OF(TYPE) *sa, size_t idx, TYPE *value);
+
+=head1 DESCRIPTION
+
+SPARSE_ARRAY_OF() returns the name for a sparse array of the specified
+B<TYPE>.  DEFINE_STACK_OF() creates set of functions for a sparse array of
+B<TYPE>. This will mean that a pointer to type B<TYPE> is stored in each
+element of a sparse array, the type is referenced by SPARSE_ARRAY_OF(TYPE) and
+each function name begins with I<ossl_sa_TYPE_>. For example:
+
+ TYPE *ossl_sa_TYPE_get(SPARSE_ARRAY_OF(TYPE) *sa, size_t idx);
+
+ossl_sa_TYPE_num() returns the number of elements in B<sa> or 0 if B<sa> is
+B<NULL>.
+
+ossl_sa_TYPE_get() returns element B<idx> in B<sa>, where B<idx> starts at
+zero. If B<idx> refers to a value that has not been set then B<NULL> is
+returned.
+
+ossl_sa_TYPE_set() sets element B<idx> in B<sa> to B<value>, where B<idx>
+starts at zero. The sparse array will be resized as required.
+
+ossl_sa_TYPE_new() allocates a new empty sparse array.
+
+ossl_sa_TYPE_free() frees up the B<sa> structure. It does B<not> free up any
+elements of B<sa>. After this call B<sa> is no longer valid.
+
+ossl_sa_TYPE_free_leaves() frees up the B<sa> structure and all of its
+elements.  After this call B<sa> is no longer valid.
+
+ossl_sa_TYPE_doall() calls the function B<leaf> for each element in B<sa> in
+ascending index order.
+
+ossl_sa_TYPE_doall_arg() calls the function B<leaf> for each element in B<sa>
+in ascending index order. The argument B<arg> is passed to each call of
+B<leaf>.
+
+=head1 NOTES
+
+Sparse arrays are an internal data structure and should B<not> be used by user
+applications.
+
+Care should be taken when accessing sparse arrays in multi-threaded
+environments.  The ossl_sa_TYPE_set operation can cause the internal structure
+of the sparse array to change which causes race conditions if the sparse array
+is accessed in a different thread.
+
+SPARSE_ARRAY_OF() and DEFINE_SPARSE_ARRAY_OF() are implemented as macros.
+
+The underlying utility B<OPENSSL_SA_> API should not be used directly.  It
+defines these functions: OPENSSL_SA_doall, OPENSSL_SA_doall_arg,
+OPENSSL_SA_free, OPENSSL_SA_free_leaves, OPENSSL_SA_get, OPENSSL_SA_new,
+OPENSSL_SA_num and OPENSSL_SA_set.
+
+=head1 RETURN VALUES
+
+ossl_sa_TYPE_num() returns the number of elements in the sparse array or B<0>
+if the passed sparse array is B<NULL>.
+
+ossl_sa_TYPE_get() returns a pointer to a sparse array element or B<NULL> if
+the element has not be set.
+
+ossl_sa_TYPE_set() return B<1> on success and B<0> on error. In the latter
+case, the elements of the sparse array remain unchanged, although the internal
+structures might have.
+
+ossl_sa_TYPE_new() returns an empty sparse array or B<NULL> if an error
+occurs.
+
+ossl_sa_TYPE_doall, ossl_sa_TYPE_doall_arg, ossl_sa_TYPE_free() and
+ossl_sa_TYPE_free_leaves() do not return values.
+
+=head1 HISTORY
+
+This functionality was added to OpenSSL 3.0.0.
+
+=head1 COPYRIGHT
+
+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
+L<https://www.openssl.org/source/license.html>.
+
+=cut
index 4c29beb..b2b7375 100644 (file)
@@ -30,7 +30,7 @@ IF[{- !$disabled{tests} -}]
           dhtest enginetest casttest \
           bftest ssltest_old dsatest dsa_no_digest_size_test exptest rsa_test \
           evp_test evp_extra_test igetest v3nametest v3ext \
           dhtest enginetest casttest \
           bftest ssltest_old dsatest dsa_no_digest_size_test exptest rsa_test \
           evp_test evp_extra_test igetest v3nametest v3ext \
-          crltest danetest bad_dtls_test lhash_test \
+          crltest danetest bad_dtls_test lhash_test sparse_array_test \
           conf_include_test \
           constant_time_test verify_extra_test clienthellotest \
           packettest asynctest secmemtest srptest memleaktest stack_test \
           conf_include_test \
           constant_time_test verify_extra_test clienthellotest \
           packettest asynctest secmemtest srptest memleaktest stack_test \
@@ -488,6 +488,10 @@ IF[{- !$disabled{tests} -}]
     INCLUDE[ctype_internal_test]=.. ../crypto/include ../include
     DEPEND[ctype_internal_test]=../libcrypto.a libtestutil.a
 
     INCLUDE[ctype_internal_test]=.. ../crypto/include ../include
     DEPEND[ctype_internal_test]=../libcrypto.a libtestutil.a
 
+    SOURCE[sparse_array_test]=sparse_array_test.c
+    INCLUDE[sparse_array_test]=../crypto/include ../include
+    DEPEND[sparse_array_test]=../libcrypto.a libtestutil.a
+
     SOURCE[siphash_internal_test]=siphash_internal_test.c
     INCLUDE[siphash_internal_test]=.. ../include ../crypto/include
     DEPEND[siphash_internal_test]=../libcrypto.a libtestutil.a
     SOURCE[siphash_internal_test]=siphash_internal_test.c
     INCLUDE[siphash_internal_test]=.. ../include ../crypto/include
     DEPEND[siphash_internal_test]=../libcrypto.a libtestutil.a
diff --git a/test/recipes/02-test_sparse_array.t b/test/recipes/02-test_sparse_array.t
new file mode 100644 (file)
index 0000000..ee4a63e
--- /dev/null
@@ -0,0 +1,12 @@
+#! /usr/bin/env perl
+# 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
+
+use OpenSSL::Test::Simple;
+
+simple_test("test_sparse_array", "sparse_array_test");
diff --git a/test/sparse_array_test.c b/test/sparse_array_test.c
new file mode 100644 (file)
index 0000000..295ccb0
--- /dev/null
@@ -0,0 +1,103 @@
+/*
+ * 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 <stdio.h>
+#include <string.h>
+#include <limits.h>
+
+#include <openssl/crypto.h>
+#include <internal/nelem.h>
+
+#include "internal/sparse_array.h"
+#include "testutil.h"
+
+/* The macros below generate unused functions which error out one of the clang
+ * builds.  We disable this check here.
+ */
+#ifdef __clang__
+#pragma clang diagnostic ignored "-Wunused-function"
+#endif
+
+DEFINE_SPARSE_ARRAY_OF(char);
+
+static int test_sparse_array(void)
+{
+    static const struct {
+        size_t n;
+        char *v;
+    } cases[] = {
+        { 22, "a" }, { 0, "z" }, { 1, "b" }, { 290, "c" },
+        { INT_MAX, "m" }, { 6666666, "d" }, { (size_t)-1, "H" },
+        { 99, "e" }
+    };
+    SPARSE_ARRAY_OF(char) *sa;
+    size_t i, j;
+    int res = 0;
+
+    if (!TEST_ptr(sa = ossl_sa_char_new())
+            || !TEST_ptr_null(ossl_sa_char_get(sa, 3))
+            || !TEST_ptr_null(ossl_sa_char_get(sa, 0))
+            || !TEST_ptr_null(ossl_sa_char_get(sa, UINT_MAX)))
+        goto err;
+
+    for (i = 0; i < OSSL_NELEM(cases); i++) {
+        if (!TEST_true(ossl_sa_char_set(sa, cases[i].n, cases[i].v))) {
+            TEST_note("iteration %zu", i + 1);
+            goto err;
+        }
+        for (j = 0; j <= i; j++)
+            if (!TEST_str_eq(ossl_sa_char_get(sa, cases[j].n), cases[j].v)) {
+                TEST_note("iteration %zu / %zu", i + 1, j + 1);
+                goto err;
+            }
+    }
+
+    res = 1;
+err:
+    ossl_sa_char_free(sa);
+    return res;
+}
+
+static int test_sparse_array_num(void)
+{
+    static const struct {
+        size_t num;
+        size_t n;
+        char *v;
+    } cases[] = {
+        { 1, 22, "a" }, { 2, 1021, "b" }, { 3, 3, "c" }, { 2, 22, NULL },
+        { 2, 3, "d" }, { 3, 22, "e" }, { 3, 666, NULL }, { 4, 666, "f" },
+        { 3, 3, NULL }, { 2, 22, NULL }, { 1, 666, NULL }, { 2, 64000, "g" },
+        { 1, 1021, NULL }, { 0, 64000, NULL }, { 1, 23, "h" }, { 0, 23, NULL }
+    };
+    SPARSE_ARRAY_OF(char) *sa = NULL;
+    size_t i;
+    int res = 0;
+
+    if (!TEST_size_t_eq(ossl_sa_char_num(NULL), 0)
+            || !TEST_ptr(sa = ossl_sa_char_new())
+            || !TEST_size_t_eq(ossl_sa_char_num(sa), 0))
+        goto err;
+    for (i = 0; i < OSSL_NELEM(cases); i++)
+        if (!TEST_true(ossl_sa_char_set(sa, cases[i].n, cases[i].v))
+                || !TEST_size_t_eq(ossl_sa_char_num(sa), cases[i].num))
+            goto err;
+    res = 1;
+err:
+    ossl_sa_char_free(sa);
+    return res;
+}
+
+int setup_tests(void)
+{
+    ADD_TEST(test_sparse_array);
+    ADD_TEST(test_sparse_array_num);
+    return 1;
+}