aboutsummaryrefslogtreecommitdiffhomepage
path: root/vendor/github.com/armon/go-radix
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/armon/go-radix')
-rw-r--r--vendor/github.com/armon/go-radix/go.mod1
-rw-r--r--vendor/github.com/armon/go-radix/radix.go60
2 files changed, 53 insertions, 8 deletions
diff --git a/vendor/github.com/armon/go-radix/go.mod b/vendor/github.com/armon/go-radix/go.mod
new file mode 100644
index 0000000..4336aa2
--- /dev/null
+++ b/vendor/github.com/armon/go-radix/go.mod
@@ -0,0 +1 @@
module github.com/armon/go-radix
diff --git a/vendor/github.com/armon/go-radix/radix.go b/vendor/github.com/armon/go-radix/radix.go
index d2914c1..e2bb22e 100644
--- a/vendor/github.com/armon/go-radix/radix.go
+++ b/vendor/github.com/armon/go-radix/radix.go
@@ -44,13 +44,13 @@ func (n *node) addEdge(e edge) {
44 n.edges.Sort() 44 n.edges.Sort()
45} 45}
46 46
47func (n *node) replaceEdge(e edge) { 47func (n *node) updateEdge(label byte, node *node) {
48 num := len(n.edges) 48 num := len(n.edges)
49 idx := sort.Search(num, func(i int) bool { 49 idx := sort.Search(num, func(i int) bool {
50 return n.edges[i].label >= e.label 50 return n.edges[i].label >= label
51 }) 51 })
52 if idx < num && n.edges[idx].label == e.label { 52 if idx < num && n.edges[idx].label == label {
53 n.edges[idx].node = e.node 53 n.edges[idx].node = node
54 return 54 return
55 } 55 }
56 panic("replacing missing edge") 56 panic("replacing missing edge")
@@ -198,10 +198,7 @@ func (t *Tree) Insert(s string, v interface{}) (interface{}, bool) {
198 child := &node{ 198 child := &node{
199 prefix: search[:commonPrefix], 199 prefix: search[:commonPrefix],
200 } 200 }
201 parent.replaceEdge(edge{ 201 parent.updateEdge(search[0], child)
202 label: search[0],
203 node: child,
204 })
205 202
206 // Restore the existing node 203 // Restore the existing node
207 child.addEdge(edge{ 204 child.addEdge(edge{
@@ -292,6 +289,53 @@ DELETE:
292 return leaf.val, true 289 return leaf.val, true
293} 290}
294 291
292// DeletePrefix is used to delete the subtree under a prefix
293// Returns how many nodes were deleted
294// Use this to delete large subtrees efficiently
295func (t *Tree) DeletePrefix(s string) int {
296 return t.deletePrefix(nil, t.root, s)
297}
298
299// delete does a recursive deletion
300func (t *Tree) deletePrefix(parent, n *node, prefix string) int {
301 // Check for key exhaustion
302 if len(prefix) == 0 {
303 // Remove the leaf node
304 subTreeSize := 0
305 //recursively walk from all edges of the node to be deleted
306 recursiveWalk(n, func(s string, v interface{}) bool {
307 subTreeSize++
308 return false
309 })
310 if n.isLeaf() {
311 n.leaf = nil
312 }
313 n.edges = nil // deletes the entire subtree
314
315 // Check if we should merge the parent's other child
316 if parent != nil && parent != t.root && len(parent.edges) == 1 && !parent.isLeaf() {
317 parent.mergeChild()
318 }
319 t.size -= subTreeSize
320 return subTreeSize
321 }
322
323 // Look for an edge
324 label := prefix[0]
325 child := n.getEdge(label)
326 if child == nil || (!strings.HasPrefix(child.prefix, prefix) && !strings.HasPrefix(prefix, child.prefix)) {
327 return 0
328 }
329
330 // Consume the search prefix
331 if len(child.prefix) > len(prefix) {
332 prefix = prefix[len(prefix):]
333 } else {
334 prefix = prefix[len(child.prefix):]
335 }
336 return t.deletePrefix(n, child, prefix)
337}
338
295func (n *node) mergeChild() { 339func (n *node) mergeChild() {
296 e := n.edges[0] 340 e := n.edges[0]
297 child := e.node 341 child := e.node