/*
 * 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
 * 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 <openssl/bn.h>
#include "crypto/sparse_array.h"

/*
 * How many bits are used to index each level in the tree structure?
 * 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 default is to use four bits which means that the 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]. 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
# 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

/*
 * From the number of bits, work out:
 * the number of pointers in a tree node;
 * a bit mask to quickly extract 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(ossl_uintmax_t) * 8 \
 + OPENSSL_SA_BLOCK_BITS - 1) \
 / OPENSSL_SA_BLOCK_BITS)

struct sparse_array_st {
 int levels;
 ossl_uintmax_t top;
 size_t nelem;
 void **nodes;
};

OPENSSL_SA *ossl_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)(ossl_uintmax_t, void *, void *), void *arg)
{
 int i[SA_BLOCK_MAX_LEVELS];
 void *nodes[SA_BLOCK_MAX_LEVELS];
 ossl_uintmax_t idx = 0;
 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--;
 idx >>= OPENSSL_SA_BLOCK_BITS;
 } else {
 i[l] = n + 1;
 if (p != NULL && p[n] != NULL) {
 idx = (idx & ~SA_BLOCK_MASK) | n;
 if (l < sa->levels - 1) {
 i[++l] = 0;
 nodes[l] = p[n];
 idx <<= OPENSSL_SA_BLOCK_BITS;
 } else if (leaf != NULL) {
 (*leaf)(idx, p[n], arg);
 }
 }
 }
 }
}

static void sa_free_node(void **p)
{
 OPENSSL_free(p);
}

static void sa_free_leaf(ossl_uintmax_t n, void *p, void *arg)
{
 OPENSSL_free(p);
}

void ossl_sa_free(OPENSSL_SA *sa)
{
 if (sa != NULL) {
 sa_doall(sa, &sa_free_node, NULL, NULL);
 OPENSSL_free(sa);
 }
}

void ossl_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)(ossl_uintmax_t, void *);
};

static void trampoline(ossl_uintmax_t n, void *l, void *arg)
{
 ((const struct trampoline_st *)arg)->func(n, l);
}

void ossl_sa_doall(const OPENSSL_SA *sa, void (*leaf)(ossl_uintmax_t, void *))
{
 struct trampoline_st tramp;

 tramp.func = leaf;
 if (sa != NULL)
 sa_doall(sa, NULL, &trampoline, &tramp);
}

void ossl_sa_doall_arg(const OPENSSL_SA *sa,
 void (*leaf)(ossl_uintmax_t, void *, void *),
 void *arg)
{
 if (sa != NULL)
 sa_doall(sa, NULL, leaf, arg);
}

size_t ossl_sa_num(const OPENSSL_SA *sa)
{
 return sa == NULL ? 0 : sa->nelem;
}

void *ossl_sa_get(const OPENSSL_SA *sa, ossl_uintmax_t n)
{
 int level;
 void **p, *r = NULL;

 if (sa == NULL || sa->nelem == 0)
 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 ossl_sa_set(OPENSSL_SA *sa, ossl_uintmax_t posn, void *val)
{
 int i, level = 1;
 ossl_uintmax_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;
}