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) {
         n.edges.Sort()
 }
 
-func (n *node) replaceEdge(e edge) {
+func (n *node) updateEdge(label byte, node *node) {
         num := len(n.edges)
         idx := sort.Search(num, func(i int) bool {
-                return n.edges[i].label >= e.label
+                return n.edges[i].label >= label
         })
-        if idx < num && n.edges[idx].label == e.label {
-                n.edges[idx].node = e.node
+        if idx < num && n.edges[idx].label == label {
+                n.edges[idx].node = node
                 return
         }
         panic("replacing missing edge")
@@ -198,10 +198,7 @@ func (t *Tree) Insert(s string, v interface{}) (interface{}, bool) {
                 child := &node{
                         prefix: search[:commonPrefix],
                 }
-                parent.replaceEdge(edge{
-                        label: search[0],
-                        node:  child,
-                })
+                parent.updateEdge(search[0], child)
 
                 // Restore the existing node
                 child.addEdge(edge{
@@ -292,6 +289,53 @@ DELETE:
         return leaf.val, true
 }
 
+// DeletePrefix is used to delete the subtree under a prefix
+// Returns how many nodes were deleted
+// Use this to delete large subtrees efficiently
+func (t *Tree) DeletePrefix(s string) int {
+        return t.deletePrefix(nil, t.root, s)
+}
+
+// delete does a recursive deletion
+func (t *Tree) deletePrefix(parent, n *node, prefix string) int {
+        // Check for key exhaustion
+        if len(prefix) == 0 {
+                // Remove the leaf node
+                subTreeSize := 0
+                //recursively walk from all edges of the node to be deleted
+                recursiveWalk(n, func(s string, v interface{}) bool {
+                        subTreeSize++
+                        return false
+                })
+                if n.isLeaf() {
+                        n.leaf = nil
+                }
+                n.edges = nil // deletes the entire subtree
+
+                // Check if we should merge the parent's other child
+                if parent != nil && parent != t.root && len(parent.edges) == 1 && !parent.isLeaf() {
+                        parent.mergeChild()
+                }
+                t.size -= subTreeSize
+                return subTreeSize
+        }
+
+        // Look for an edge
+        label := prefix[0]
+        child := n.getEdge(label)
+        if child == nil || (!strings.HasPrefix(child.prefix, prefix) && !strings.HasPrefix(prefix, child.prefix)) {
+                return 0
+        }
+
+        // Consume the search prefix
+        if len(child.prefix) > len(prefix) {
+                prefix = prefix[len(prefix):]
+        } else {
+                prefix = prefix[len(child.prefix):]
+        }
+        return t.deletePrefix(n, child, prefix)
+}
+
 func (n *node) mergeChild() {
         e := n.edges[0]
         child := e.node