Add sparse array data type.
[openssl.git] / crypto / sparse_array.c
1 /*
2  * Copyright 2019 The OpenSSL Project Authors. All Rights Reserved.
3  * Copyright (c) 2019, Oracle and/or its affiliates.  All rights reserved.
4  *
5  * Licensed under the Apache License 2.0 (the "License").  You may not use
6  * this file except in compliance with the License.  You can obtain a copy
7  * in the file LICENSE in the source distribution or at
8  * https://www.openssl.org/source/license.html
9  */
10
11 #include <openssl/crypto.h>
12 #include "internal/sparse_array.h"
13
14 /*
15  * How many bits are used to index each level in the tree structre?
16  * This setting determines the number of pointers stored in each node of the
17  * tree used to represent the sparse array.  Having more pointers reduces the
18  * depth of the tree but potentially wastes more memory.  That is, this is a
19  * direct space versus time tradeoff.
20  *
21  * The large memory model uses twelve bits which means that the are 4096
22  * pointers in each tree node.  This is more than sufficient to hold the
23  * largest defined NID (as of Feb 2019).  This means that using a NID to
24  * index a sparse array becomes a constant time single array look up.
25  *
26  * The small memory model uses four bits which means the tree nodes contain
27  * sixteen pointers.  This reduces the amount of unused space significantly
28  * at a cost in time.
29  *
30  * The library builder is also permitted to define other sizes in the closed
31  * interval [2, sizeof(size_t) * 8].
32  */
33 #ifndef OPENSSL_SA_BLOCK_BITS
34 # ifdef OPENSSL_SMALL_FOOTPRINT
35 #  define OPENSSL_SA_BLOCK_BITS           4
36 # else
37 #  define OPENSSL_SA_BLOCK_BITS           12
38 # endif
39 #elif OPENSSL_SA_BLOCK_BITS < 2 || OPENSSL_SA_BLOCK_BITS > BN_BITS2
40 # error OPENSSL_SA_BLOCK_BITS is out of range
41 #endif
42
43 /*
44  * From the number of bits, work out:
45  *    the number of pointers in a tree node;
46  *    a bit mask to quickly extra an index and
47  *    the maximum depth of the tree structure.
48   */
49 #define SA_BLOCK_MAX            (1 << OPENSSL_SA_BLOCK_BITS)
50 #define SA_BLOCK_MASK           (SA_BLOCK_MAX - 1)
51 #define SA_BLOCK_MAX_LEVELS     (((int)sizeof(size_t) * 8 \
52                                   + OPENSSL_SA_BLOCK_BITS - 1) \
53                                  / OPENSSL_SA_BLOCK_BITS)
54
55 struct sparse_array_st {
56     int levels;
57     size_t top;
58     size_t nelem;
59     void **nodes;
60 };
61
62 OPENSSL_SA *OPENSSL_SA_new(void)
63 {
64     OPENSSL_SA *res = OPENSSL_zalloc(sizeof(*res));
65
66     return res;
67 }
68
69 static void sa_doall(const OPENSSL_SA *sa, void (*node)(void **),
70                      void (*leaf)(void *, void *), void *arg)
71 {
72     int i[SA_BLOCK_MAX_LEVELS];
73     void *nodes[SA_BLOCK_MAX_LEVELS];
74     int l = 0;
75
76     i[0] = 0;
77     nodes[0] = sa->nodes;
78     while (l >= 0) {
79         const int n = i[l];
80         void ** const p = nodes[l];
81
82         if (n >= SA_BLOCK_MAX) {
83             if (p != NULL && node != NULL)
84                 (*node)(p);
85             l--;
86         } else {
87             i[l] = n + 1;
88             if (p != NULL && p[n] != NULL) {
89                 if (l < sa->levels - 1) {
90                     i[++l] = 0;
91                     nodes[l] = p[n];
92                 } else if (leaf != NULL) {
93                     (*leaf)(p[n], arg);
94                 }
95             }
96         }
97     }
98 }
99
100 static void sa_free_node(void **p)
101 {
102     OPENSSL_free(p);
103 }
104
105 static void sa_free_leaf(void *p, void *arg)
106 {
107     OPENSSL_free(p);
108 }
109
110 void OPENSSL_SA_free(OPENSSL_SA *sa)
111 {
112     sa_doall(sa, &sa_free_node, NULL, NULL);
113     OPENSSL_free(sa);
114 }
115
116 void OPENSSL_SA_free_leaves(OPENSSL_SA *sa)
117 {
118     sa_doall(sa, &sa_free_node, &sa_free_leaf, NULL);
119     OPENSSL_free(sa);
120 }
121
122 /* Wrap this in a structure to avoid compiler warnings */
123 struct trampoline_st {
124     void (*func)(void *);
125 };
126
127 static void trampoline(void *l, void *arg)
128 {
129     ((const struct trampoline_st *)arg)->func(l);
130 }
131
132 void OPENSSL_SA_doall(const OPENSSL_SA *sa, void (*leaf)(void *))
133 {
134     struct trampoline_st tramp;
135
136     tramp.func = leaf;
137     if (sa != NULL)
138         sa_doall(sa, NULL, &trampoline, &tramp);
139 }
140
141 void OPENSSL_SA_doall_arg(const OPENSSL_SA *sa, void (*leaf)(void *, void *),
142                           void *arg)
143 {
144     if (sa != NULL)
145         sa_doall(sa, NULL, leaf, arg);
146 }
147
148 size_t OPENSSL_SA_num(const OPENSSL_SA *sa)
149 {
150     return sa == NULL ? 0 : sa->nelem;
151 }
152
153 void *OPENSSL_SA_get(const OPENSSL_SA *sa, size_t n)
154 {
155     int level;
156     void **p, *r = NULL;
157
158     if (sa == NULL)
159         return NULL;
160
161     if (n <= sa->top) {
162         p = sa->nodes;
163         for (level = sa->levels - 1; p != NULL && level > 0; level--)
164             p = (void **)p[(n >> (OPENSSL_SA_BLOCK_BITS * level))
165                            & SA_BLOCK_MASK];
166         r = p == NULL ? NULL : p[n & SA_BLOCK_MASK];
167     }
168     return r;
169 }
170
171 static ossl_inline void **alloc_node(void)
172 {
173     return OPENSSL_zalloc(SA_BLOCK_MAX * sizeof(void *));
174 }
175
176 int OPENSSL_SA_set(OPENSSL_SA *sa, size_t posn, void *val)
177 {
178     int i, level = 1;
179     size_t n = posn;
180     void **p;
181
182     if (sa == NULL)
183         return 0;
184
185     for (level = 1; level <= SA_BLOCK_MAX_LEVELS; level++)
186         if ((n >>= OPENSSL_SA_BLOCK_BITS) == 0)
187             break;
188
189     for (;sa->levels < level; sa->levels++) {
190         p = alloc_node();
191         if (p == NULL)
192             return 0;
193         p[0] = sa->nodes;
194         sa->nodes = p;
195     }
196     if (sa->top < posn)
197         sa->top = posn;
198
199     p = sa->nodes;
200     for (level = sa->levels - 1; level > 0; level--) {
201         i = (posn >> (OPENSSL_SA_BLOCK_BITS * level)) & SA_BLOCK_MASK;
202         if (p[i] == NULL && (p[i] = alloc_node()) == NULL)
203             return 0;
204         p = p[i];
205     }
206     p += posn & SA_BLOCK_MASK;
207     if (val == NULL && *p != NULL)
208         sa->nelem--;
209     else if (val != NULL && *p == NULL)
210         sa->nelem++;
211     *p = val;
212     return 1;
213 }