Name | Date | Size | #Lines | LOC | ||
---|---|---|---|---|---|---|
.. | 17-Dec-2024 | - | ||||
aes/ | H | 19-Jun-2024 | - | |||
aria/ | H | 24-May-2022 | - | |||
asn1/ | H | 20-Dec-2024 | - | |||
async/ | H | 06-Dec-2024 | - | |||
bf/ | H | 19-Jun-2024 | - | |||
bio/ | H | 10-Dec-2024 | - | |||
bn/ | H | 06-Dec-2024 | - | |||
buffer/ | H | 19-Jun-2024 | - | |||
camellia/ | H | 24-May-2022 | - | |||
cast/ | H | 19-Jun-2024 | - | |||
chacha/ | H | 05-Sep-2024 | - | |||
cmac/ | H | 31-Jul-2024 | - | |||
cmp/ | H | 13-Nov-2024 | - | |||
cms/ | H | 11-Dec-2024 | - | |||
comp/ | H | 19-Jun-2024 | - | |||
conf/ | H | 05-Sep-2024 | - | |||
crmf/ | H | 05-Sep-2024 | - | |||
ct/ | H | 19-Jun-2024 | - | |||
des/ | H | 05-Sep-2024 | - | |||
dh/ | H | 10-Dec-2024 | - | |||
dsa/ | H | 10-Dec-2024 | - | |||
dso/ | H | 10-Dec-2024 | - | |||
ec/ | H | 10-Dec-2024 | - | |||
encode_decode/ | H | 29-Nov-2024 | - | |||
engine/ | H | 05-Sep-2024 | - | |||
err/ | H | 17-Dec-2024 | - | |||
ess/ | H | 05-Sep-2024 | - | |||
evp/ | H | 17-Dec-2024 | - | |||
ffc/ | H | 28-Nov-2024 | - | |||
hashtable/ | H | 22-Aug-2024 | - | |||
hmac/ | H | 03-Sep-2024 | - | |||
hpke/ | H | 30-Oct-2024 | - | |||
http/ | H | 23-Sep-2024 | - | |||
idea/ | H | 05-Sep-2024 | - | |||
kdf/ | H | 24-Feb-2020 | - | |||
lhash/ | H | 19-Jun-2024 | - | |||
md2/ | H | 19-Jun-2024 | - | |||
md4/ | H | 19-Jun-2024 | - | |||
md5/ | H | 19-Jun-2024 | - | |||
mdc2/ | H | 19-Jun-2024 | - | |||
modes/ | H | 12-Sep-2024 | - | |||
objects/ | H | 05-Sep-2024 | - | |||
ocsp/ | H | 05-Sep-2024 | - | |||
pem/ | H | 09-Sep-2024 | - | |||
perlasm/ | H | 13-Dec-2024 | - | |||
pkcs12/ | H | 07-Oct-2024 | - | |||
pkcs7/ | H | 02-Dec-2024 | - | |||
poly1305/ | H | 05-Sep-2024 | - | |||
property/ | H | 19-Nov-2024 | - | |||
rand/ | H | 10-Dec-2024 | - | |||
rc2/ | H | 19-Jun-2024 | - | |||
rc4/ | H | 19-Jun-2024 | - | |||
rc5/ | H | 19-Jun-2024 | - | |||
ripemd/ | H | 19-Jun-2024 | - | |||
rsa/ | H | 10-Dec-2024 | - | |||
seed/ | H | 19-Jun-2024 | - | |||
sha/ | H | 05-Sep-2024 | - | |||
siphash/ | H | 19-Jun-2024 | - | |||
sm2/ | H | 21-Nov-2024 | - | |||
sm3/ | H | 05-Sep-2024 | - | |||
sm4/ | H | 05-Sep-2024 | - | |||
srp/ | H | 11-Oct-2024 | - | |||
stack/ | H | 19-Jun-2024 | - | |||
store/ | H | 05-Sep-2024 | - | |||
thread/ | H | 10-Sep-2024 | - | |||
ts/ | H | 05-Sep-2024 | - | |||
txt_db/ | H | 19-Jun-2024 | - | |||
ui/ | H | 09-Sep-2024 | - | |||
whrlpool/ | H | 19-Jun-2024 | - | |||
x509/ | H | Today | - | |||
LPdir_nyi.c | H A D | 24-Feb-2020 | 2 KiB | 57 | 16 | |
LPdir_unix.c | H A D | 19-Jun-2024 | 4.9 KiB | 170 | 103 | |
LPdir_vms.c | H A D | 24-Feb-2020 | 6.2 KiB | 208 | 135 | |
LPdir_win.c | H A D | 24-Feb-2020 | 6.9 KiB | 215 | 140 | |
LPdir_win32.c | H A D | 24-Feb-2020 | 1.9 KiB | 42 | 3 | |
LPdir_wince.c | H A D | 24-Feb-2020 | 2 KiB | 45 | 2 | |
README-sparse_array.md | H A D | 05-Jul-2020 | 5.6 KiB | 157 | 136 | |
alphacpuid.pl | H A D | 23-Apr-2020 | 3.9 KiB | 257 | 220 | |
arm64cpuid.pl | H A D | 03-May-2022 | 5.6 KiB | 271 | 226 | |
arm_arch.h | H A D | 19-Jun-2024 | 7.7 KiB | 220 | 163 | |
armcap.c | H A D | 22-Nov-2024 | 14.4 KiB | 450 | 331 | |
armv4cpuid.pl | H A D | 22-Nov-2024 | 5.6 KiB | 301 | 264 | |
asn1_dsa.c | H A D | 23-May-2021 | 7.4 KiB | 253 | 124 | |
bsearch.c | H A D | 24-Feb-2020 | 1.2 KiB | 45 | 33 | |
build.info | H A D | 11-Jul-2024 | 4.9 KiB | 146 | 115 | |
c64xpluscpuid.pl | H A D | 23-Apr-2020 | 5.3 KiB | 288 | 259 | |
comp_methods.c | H A D | 19-Jun-2024 | 1.5 KiB | 60 | 42 | |
context.c | H A D | 19-Sep-2024 | 16.7 KiB | 674 | 525 | |
core_algorithm.c | H A D | 19-Jun-2024 | 6.5 KiB | 198 | 125 | |
core_fetch.c | H A D | 20-Dec-2024 | 5.8 KiB | 172 | 98 | |
core_namemap.c | H A D | 05-Sep-2024 | 14.1 KiB | 548 | 369 | |
cpt_err.c | H A D | 21-Aug-2024 | 3.8 KiB | 90 | 75 | |
cpuid.c | H A D | 13-Dec-2024 | 6.7 KiB | 230 | 140 | |
cryptlib.c | H A D | 19-Jun-2024 | 7.9 KiB | 283 | 212 | |
ctype.c | H A D | 19-Jun-2024 | 14.9 KiB | 314 | 269 | |
cversion.c | H A D | 17-Oct-2024 | 3.5 KiB | 140 | 109 | |
defaults.c | H A D | 07-Aug-2024 | 5 KiB | 201 | 111 | |
der_writer.c | H A D | 27-Jun-2022 | 6 KiB | 200 | 142 | |
deterministic_nonce.c | H A D | 05-Sep-2024 | 7.5 KiB | 241 | 132 | |
dllmain.c | H A D | 03-May-2022 | 1.2 KiB | 47 | 24 | |
ebcdic.c | H A D | 24-Feb-2020 | 15 KiB | 362 | 232 | |
ex_data.c | H A D | 19-Jun-2024 | 14 KiB | 509 | 363 | |
getenv.c | H A D | 03-May-2022 | 3.1 KiB | 104 | 68 | |
ia64cpuid.S | H A D | 24-Feb-2020 | 6.3 KiB | 298 | 258 | |
indicator_core.c | H A D | 11-Jul-2024 | 1.4 KiB | 56 | 37 | |
info.c | H A D | 13-Dec-2024 | 10 KiB | 261 | 218 | |
init.c | H A D | 19-Jun-2024 | 21.4 KiB | 732 | 511 | |
initthread.c | H A D | 05-Sep-2024 | 13.3 KiB | 481 | 336 | |
loongarch64cpuid.pl | H A D | 19-Jun-2024 | 3.2 KiB | 114 | 93 | |
loongarch_arch.h | H A D | 19-Jun-2024 | 577 | 20 | 8 | |
loongarchcap.c | H A D | 19-Jun-2024 | 517 | 18 | 7 | |
mem.c | H A D | 28-Nov-2024 | 10.9 KiB | 433 | 296 | |
mem_clr.c | H A D | 24-Feb-2020 | 773 | 26 | 8 | |
mem_sec.c | H A D | 05-Sep-2024 | 19.6 KiB | 750 | 575 | |
mips_arch.h | H A D | 24-Feb-2020 | 1.2 KiB | 41 | 27 | |
o_dir.c | H A D | 03-May-2022 | 1.1 KiB | 38 | 20 | |
o_fopen.c | H A D | 05-Sep-2024 | 4.3 KiB | 131 | 78 | |
o_init.c | H A D | 03-May-2022 | 525 | 22 | 6 | |
o_str.c | H A D | 07-Aug-2024 | 11.4 KiB | 435 | 303 | |
o_time.c | H A D | 23-May-2021 | 5.5 KiB | 201 | 133 | |
packet.c | H A D | 19-Jun-2024 | 13.8 KiB | 591 | 413 | |
param_build.c | H A D | 19-Jun-2024 | 11.5 KiB | 392 | 323 | |
param_build_set.c | H A D | 19-Jun-2024 | 3.8 KiB | 125 | 96 | |
params.c | H A D | 19-Jun-2024 | 46.6 KiB | 1,688 | 1,445 | |
params_dup.c | H A D | 19-Jun-2024 | 7.2 KiB | 237 | 184 | |
params_from_text.c | H A D | 19-Nov-2024 | 10.5 KiB | 338 | 220 | |
params_idx.c.in | H A D | 19-Jun-2024 | 626 | 22 | 19 | |
pariscid.pl | H A D | 23-Apr-2020 | 4.8 KiB | 280 | 237 | |
passphrase.c | H A D | 19-Jun-2024 | 11 KiB | 347 | 277 | |
ppccap.c | H A D | 05-Sep-2024 | 8.7 KiB | 326 | 252 | |
ppccpuid.pl | H A D | 03-May-2022 | 7.4 KiB | 398 | 340 | |
provider.c | H A D | 19-Jun-2024 | 4.6 KiB | 159 | 126 | |
provider_child.c | H A D | 19-Jun-2024 | 9.7 KiB | 317 | 222 | |
provider_conf.c | H A D | 19-Jun-2024 | 13.2 KiB | 431 | 309 | |
provider_core.c | H A D | 19-Nov-2024 | 81.5 KiB | 2,533 | 1,752 | |
provider_local.h | H A D | 24-Jun-2021 | 1 KiB | 34 | 20 | |
provider_predefined.c | H A D | 24-Jun-2021 | 1.1 KiB | 33 | 22 | |
punycode.c | H A D | 19-Jun-2024 | 8.7 KiB | 313 | 183 | |
quic_vlint.c | H A D | 19-Jun-2024 | 2 KiB | 82 | 67 | |
rcu_internal.h | H A D | 19-Jun-2024 | 527 | 23 | 10 | |
riscv32cpuid.pl | H A D | 05-Sep-2024 | 2.8 KiB | 106 | 87 | |
riscv64cpuid.pl | H A D | 19-Jun-2024 | 2.8 KiB | 106 | 87 | |
riscvcap.c | H A D | 10-Oct-2024 | 3.7 KiB | 142 | 102 | |
s390x_arch.h | H A D | 23-Oct-2024 | 7.3 KiB | 207 | 153 | |
s390xcap.c | H A D | 23-Oct-2024 | 30.9 KiB | 802 | 686 | |
s390xcpuid.pl | H A D | 05-Sep-2024 | 11.5 KiB | 562 | 447 | |
self_test_core.c | H A D | 05-Sep-2024 | 4.4 KiB | 165 | 119 | |
sleep.c | H A D | 19-Jun-2024 | 3.1 KiB | 117 | 62 | |
sparccpuid.S | H A D | 24-Feb-2020 | 12 KiB | 579 | 535 | |
sparcv9cap.c | H A D | 15-Jul-2021 | 7.3 KiB | 232 | 173 | |
sparse_array.c | H A D | 05-Sep-2024 | 5.8 KiB | 217 | 154 | |
threads_lib.c | H A D | 19-Jun-2024 | 543 | 28 | 14 | |
threads_none.c | H A D | 05-Sep-2024 | 5 KiB | 276 | 203 | |
threads_pthread.c | H A D | 13-Dec-2024 | 30.5 KiB | 1,047 | 680 | |
threads_win.c | H A D | 05-Sep-2024 | 19.3 KiB | 749 | 509 | |
time.c | H A D | 05-Sep-2024 | 1.3 KiB | 50 | 35 | |
trace.c | H A D | 19-Nov-2024 | 15.6 KiB | 560 | 447 | |
uid.c | H A D | 19-Jun-2024 | 1.4 KiB | 56 | 36 | |
vms_rms.h | H A D | 24-Feb-2020 | 2.1 KiB | 59 | 43 | |
x86_64cpuid.pl | H A D | 13-Dec-2024 | 11.7 KiB | 549 | 489 | |
x86cpuid.pl | H A D | 13-Dec-2024 | 13.4 KiB | 532 | 446 |
README-sparse_array.md
1Sparse Arrays 2============= 3 4The `sparse_array.c` file contains an implementation of a sparse array that 5attempts to be both space and time efficient. 6 7The sparse array is represented using a tree structure. Each node in the 8tree contains a block of pointers to either the user supplied leaf values or 9to another node. 10 11There are a number of parameters used to define the block size: 12 13 OPENSSL_SA_BLOCK_BITS Specifies the number of bits covered by each block 14 SA_BLOCK_MAX Specifies the number of pointers in each block 15 SA_BLOCK_MASK Specifies a bit mask to perform modulo block size 16 SA_BLOCK_MAX_LEVELS Indicates the maximum possible height of the tree 17 18These constants are inter-related: 19 20 SA_BLOCK_MAX = 2 ^ OPENSSL_SA_BLOCK_BITS 21 SA_BLOCK_MASK = SA_BLOCK_MAX - 1 22 SA_BLOCK_MAX_LEVELS = number of bits in size_t divided by 23 OPENSSL_SA_BLOCK_BITS rounded up to the next multiple 24 of OPENSSL_SA_BLOCK_BITS 25 26`OPENSSL_SA_BLOCK_BITS` can be defined at compile time and this overrides the 27built in setting. 28 29As a space and performance optimisation, the height of the tree is usually 30less than the maximum possible height. Only sufficient height is allocated to 31accommodate the largest index added to the data structure. 32 33The largest index used to add a value to the array determines the tree height: 34 35 +----------------------+---------------------+ 36 | Largest Added Index | Height of Tree | 37 +----------------------+---------------------+ 38 | SA_BLOCK_MAX - 1 | 1 | 39 | SA_BLOCK_MAX ^ 2 - 1 | 2 | 40 | SA_BLOCK_MAX ^ 3 - 1 | 3 | 41 | ... | ... | 42 | size_t max | SA_BLOCK_MAX_LEVELS | 43 +----------------------+---------------------+ 44 45The tree height is dynamically increased as needed based on additions. 46 47An empty tree is represented by a NULL root pointer. Inserting a value at 48index 0 results in the allocation of a top level node full of null pointers 49except for the single pointer to the user's data (N = SA_BLOCK_MAX for 50brevity): 51 52 +----+ 53 |Root| 54 |Node| 55 +-+--+ 56 | 57 | 58 | 59 v 60 +-+-+---+---+---+---+ 61 | 0 | 1 | 2 |...|N-1| 62 | |nil|nil|...|nil| 63 +-+-+---+---+---+---+ 64 | 65 | 66 | 67 v 68 +-+--+ 69 |User| 70 |Data| 71 +----+ 72 Index 0 73 74Inserting at element 2N+1 creates a new root node and pushes down the old root 75node. It then creates a second second level node to hold the pointer to the 76user's new data: 77 78 +----+ 79 |Root| 80 |Node| 81 +-+--+ 82 | 83 | 84 | 85 v 86 +-+-+---+---+---+---+ 87 | 0 | 1 | 2 |...|N-1| 88 | |nil| |...|nil| 89 +-+-+---+-+-+---+---+ 90 | | 91 | +------------------+ 92 | | 93 v v 94 +-+-+---+---+---+---+ +-+-+---+---+---+---+ 95 | 0 | 1 | 2 |...|N-1| | 0 | 1 | 2 |...|N-1| 96 |nil| |nil|...|nil| |nil| |nil|...|nil| 97 +-+-+---+---+---+---+ +---+-+-+---+---+---+ 98 | | 99 | | 100 | | 101 v v 102 +-+--+ +-+--+ 103 |User| |User| 104 |Data| |Data| 105 +----+ +----+ 106 Index 0 Index 2N+1 107 108The nodes themselves are allocated in a sparse manner. Only nodes which exist 109along a path from the root of the tree to an added leaf will be allocated. 110The complexity is hidden and nodes are allocated on an as needed basis. 111Because the data is expected to be sparse this doesn't result in a large waste 112of space. 113 114Values can be removed from the sparse array by setting their index position to 115NULL. The data structure does not attempt to reclaim nodes or reduce the 116height of the tree on removal. For example, now setting index 0 to NULL would 117result in: 118 119 +----+ 120 |Root| 121 |Node| 122 +-+--+ 123 | 124 | 125 | 126 v 127 +-+-+---+---+---+---+ 128 | 0 | 1 | 2 |...|N-1| 129 | |nil| |...|nil| 130 +-+-+---+-+-+---+---+ 131 | | 132 | +------------------+ 133 | | 134 v v 135 +-+-+---+---+---+---+ +-+-+---+---+---+---+ 136 | 0 | 1 | 2 |...|N-1| | 0 | 1 | 2 |...|N-1| 137 |nil|nil|nil|...|nil| |nil| |nil|...|nil| 138 +---+---+---+---+---+ +---+-+-+---+---+---+ 139 | 140 | 141 | 142 v 143 +-+--+ 144 |User| 145 |Data| 146 +----+ 147 Index 2N+1 148 149Accesses to elements in the sparse array take O(log n) time where n is the 150largest element. The base of the logarithm is `SA_BLOCK_MAX`, so for moderately 151small indices (e.g. NIDs), single level (constant time) access is achievable. 152Space usage is O(minimum(m, n log(n)) where m is the number of elements in the 153array. 154 155Note: sparse arrays only include pointers to types. 156Thus, `SPARSE_ARRAY_OF(char)` can be used to store a string. 157