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, 103 insertions, 0 deletions

diff --git a/test/sparse_array_test.c b/test/sparse_array_test.c
new file mode 100644
index 0000000000..295ccb0782
--- /dev/null
+++ b/test/sparse_array_test.c
@@ -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;
+}