summaryrefslogtreecommitdiff
path: root/vendor/github.com/tchap
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/tchap')
-rw-r--r--vendor/github.com/tchap/go-patricia/patricia/children.go38
-rw-r--r--vendor/github.com/tchap/go-patricia/patricia/patricia.go12
2 files changed, 50 insertions, 0 deletions
diff --git a/vendor/github.com/tchap/go-patricia/patricia/children.go b/vendor/github.com/tchap/go-patricia/patricia/children.go
index a5677c335..bcfd0a5dd 100644
--- a/vendor/github.com/tchap/go-patricia/patricia/children.go
+++ b/vendor/github.com/tchap/go-patricia/patricia/children.go
@@ -20,6 +20,7 @@ type childList interface {
next(b byte) *Trie
walk(prefix *Prefix, visitor VisitorFunc) error
print(w io.Writer, indent int)
+ clone() childList
total() int
}
@@ -143,6 +144,17 @@ func (list *sparseChildList) total() int {
return tot
}
+func (list *sparseChildList) clone() childList {
+ clones := make(tries, len(list.children), cap(list.children))
+ for i, child := range list.children {
+ clones[i] = child.Clone()
+ }
+
+ return &sparseChildList{
+ children: clones,
+ }
+}
+
func (list *sparseChildList) print(w io.Writer, indent int) {
for _, child := range list.children {
if child != nil {
@@ -314,6 +326,32 @@ func (list *denseChildList) print(w io.Writer, indent int) {
}
}
+func (list *denseChildList) clone() childList {
+ clones := make(tries, cap(list.children))
+
+ if list.numChildren != 0 {
+ clonedCount := 0
+ for i := list.headIndex; i < len(list.children); i++ {
+ child := list.children[i]
+ if child != nil {
+ clones[i] = child.Clone()
+ clonedCount++
+ if clonedCount == list.numChildren {
+ break
+ }
+ }
+ }
+ }
+
+ return &denseChildList{
+ min: list.min,
+ max: list.max,
+ numChildren: list.numChildren,
+ headIndex: list.headIndex,
+ children: clones,
+ }
+}
+
func (list *denseChildList) total() int {
tot := 0
for _, child := range list.children {
diff --git a/vendor/github.com/tchap/go-patricia/patricia/patricia.go b/vendor/github.com/tchap/go-patricia/patricia/patricia.go
index a1fc53d5d..7b9975e38 100644
--- a/vendor/github.com/tchap/go-patricia/patricia/patricia.go
+++ b/vendor/github.com/tchap/go-patricia/patricia/patricia.go
@@ -77,6 +77,18 @@ func MaxChildrenPerSparseNode(value int) Option {
}
}
+// Clone makes a copy of an existing trie.
+// Items stored in both tries become shared, obviously.
+func (trie *Trie) Clone() *Trie {
+ return &Trie{
+ prefix: append(Prefix(nil), trie.prefix...),
+ item: trie.item,
+ maxPrefixPerNode: trie.maxPrefixPerNode,
+ maxChildrenPerSparseNode: trie.maxChildrenPerSparseNode,
+ children: trie.children.clone(),
+ }
+}
+
// Item returns the item stored in the root of this trie.
func (trie *Trie) Item() Item {
return trie.item