aboutsummaryrefslogtreecommitdiffstats
path: root/org.eclipse.jgit/resources/org/eclipse/jgit/internal
diff options
context:
space:
mode:
authorMatthias Sohn <matthias.sohn@sap.com>2021-10-05 04:08:49 +0200
committerMatthias Sohn <matthias.sohn@sap.com>2023-01-04 23:51:23 +0100
commit70b436b1b2de249c795035ca1c655c34bceaf01f (patch)
tree972510444250fade02bf61f682f8cf76d0c369d6 /org.eclipse.jgit/resources/org/eclipse/jgit/internal
parent414bfe05ff3c9fbca5767116348a4de1d7b95841 (diff)
downloadjgit-70b436b1b2de249c795035ca1c655c34bceaf01f.tar.gz
jgit-70b436b1b2de249c795035ca1c655c34bceaf01f.zip
Add TernarySearchTree
A ternary search tree is a type of tree where nodes are arranged in a manner similar to a binary search tree, but with up to three children rather than the binary tree's limit of two. Each node of a ternary search tree stores a single character, a reference to a value object and references to its three children named equal kid, lo kid and hi kid. The lo kid pointer must point to a node whose character value is less than the current node. The hi kid pointer must point to a node whose character is greater than the current node.[1] The equal kid points to the next character in the word. Each node in a ternary search tree represents a prefix of the stored strings. All strings in the middle subtree of a node start with that prefix. Like other prefix trees, a ternary search tree can be used as an associative map with the ability for incremental string search. Ternary search trees are more space efficient compared to standard prefix trees, at the cost of speed. They allow efficient prefix search which is important to implement searching refs by prefix in a RefDatabase. Searching by prefix returns all keys if the prefix is an empty string. Bug: 576165 Change-Id: If160df70151a8e1c1bd6716ee4968e4c45b2c7ac
Diffstat (limited to 'org.eclipse.jgit/resources/org/eclipse/jgit/internal')
-rw-r--r--org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties2
1 files changed, 2 insertions, 0 deletions
diff --git a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
index 836213286d..bdf35d8d73 100644
--- a/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
+++ b/org.eclipse.jgit/resources/org/eclipse/jgit/internal/JGitText.properties
@@ -360,6 +360,8 @@ illegalArgumentNotA=Not {0}
illegalCombinationOfArguments=The combination of arguments {0} and {1} is not allowed
illegalHookName=Illegal hook name {0}
illegalPackingPhase=Illegal packing phase {0}
+illegalTernarySearchTreeKey=TernarySearchTree key must not be null or empty
+illegalTernarySearchTreeValue=cannot insert null value into TernarySearchTree
incorrectHashFor=Incorrect hash for {0}; computed {1} as a {2} from {3} bytes.
incorrectOBJECT_ID_LENGTH=Incorrect OBJECT_ID_LENGTH.
indexFileCorruptedNegativeBucketCount=Invalid negative bucket count read from pack v2 index file: {0}