summaryrefslogtreecommitdiff
path: root/crypto/README-sparse_array.md
diff options
context:
space:
mode:
authorDr. David von Oheimb <David.von.Oheimb@siemens.com>2020-06-10 17:49:25 +0200
committerDr. David von Oheimb <David.von.Oheimb@siemens.com>2020-07-05 11:29:43 +0200
commit1dc1ea182be183d8a393fdce4494360aee059cd2 (patch)
tree88ed6f74c0c79a5efa10a7f463061ed223b97fa6 /crypto/README-sparse_array.md
parent036cbb6bbf30955abdcffaf6e52cd926d8d8ee75 (diff)
downloadopenssl-new-1dc1ea182be183d8a393fdce4494360aee059cd2.tar.gz
Fix many MarkDown issues in {NOTES*,README*,HACKING,LICENSE}.md files
Reviewed-by: Tim Hudson <tjh@openssl.org> (Merged from https://github.com/openssl/openssl/pull/12109)
Diffstat (limited to 'crypto/README-sparse_array.md')
-rw-r--r--crypto/README-sparse_array.md17
1 files changed, 9 insertions, 8 deletions
diff --git a/crypto/README-sparse_array.md b/crypto/README-sparse_array.md
index d86a48d9e1..bc2ff0cb8a 100644
--- a/crypto/README-sparse_array.md
+++ b/crypto/README-sparse_array.md
@@ -1,4 +1,7 @@
-The sparse_array.c file contains an implementation of a sparse array that
+Sparse Arrays
+=============
+
+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
@@ -13,13 +16,14 @@ There are a number of parameters used to define the 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
+`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
@@ -67,7 +71,6 @@ brevity):
+----+
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:
@@ -102,7 +105,6 @@ user's new 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.
@@ -144,12 +146,11 @@ result in:
+----+
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
+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.
+Note: sparse arrays only include pointers to types.
+Thus, `SPARSE_ARRAY_OF(char)` can be used to store a string.