1package iradix 2 3import ( 4 "bytes" 5 "sort" 6) 7 8// WalkFn is used when walking the tree. Takes a 9// key and value, returning if iteration should 10// be terminated. 11type WalkFn func(k []byte, v interface{}) bool 12 13// leafNode is used to represent a value 14type leafNode struct { 15 mutateCh chan struct{} 16 key []byte 17 val interface{} 18} 19 20// edge is used to represent an edge node 21type edge struct { 22 label byte 23 node *Node 24} 25 26// Node is an immutable node in the radix tree 27type Node struct { 28 // mutateCh is closed if this node is modified 29 mutateCh chan struct{} 30 31 // leaf is used to store possible leaf 32 leaf *leafNode 33 34 // prefix is the common prefix we ignore 35 prefix []byte 36 37 // Edges should be stored in-order for iteration. 38 // We avoid a fully materialized slice to save memory, 39 // since in most cases we expect to be sparse 40 edges edges 41} 42 43func (n *Node) isLeaf() bool { 44 return n.leaf != nil 45} 46 47func (n *Node) addEdge(e edge) { 48 num := len(n.edges) 49 idx := sort.Search(num, func(i int) bool { 50 return n.edges[i].label >= e.label 51 }) 52 n.edges = append(n.edges, e) 53 if idx != num { 54 copy(n.edges[idx+1:], n.edges[idx:num]) 55 n.edges[idx] = e 56 } 57} 58 59func (n *Node) replaceEdge(e edge) { 60 num := len(n.edges) 61 idx := sort.Search(num, func(i int) bool { 62 return n.edges[i].label >= e.label 63 }) 64 if idx < num && n.edges[idx].label == e.label { 65 n.edges[idx].node = e.node 66 return 67 } 68 panic("replacing missing edge") 69} 70 71func (n *Node) getEdge(label byte) (int, *Node) { 72 num := len(n.edges) 73 idx := sort.Search(num, func(i int) bool { 74 return n.edges[i].label >= label 75 }) 76 if idx < num && n.edges[idx].label == label { 77 return idx, n.edges[idx].node 78 } 79 return -1, nil 80} 81 82func (n *Node) delEdge(label byte) { 83 num := len(n.edges) 84 idx := sort.Search(num, func(i int) bool { 85 return n.edges[i].label >= label 86 }) 87 if idx < num && n.edges[idx].label == label { 88 copy(n.edges[idx:], n.edges[idx+1:]) 89 n.edges[len(n.edges)-1] = edge{} 90 n.edges = n.edges[:len(n.edges)-1] 91 } 92} 93 94func (n *Node) GetWatch(k []byte) (<-chan struct{}, interface{}, bool) { 95 search := k 96 watch := n.mutateCh 97 for { 98 // Check for key exhaustion 99 if len(search) == 0 { 100 if n.isLeaf() { 101 return n.leaf.mutateCh, n.leaf.val, true 102 } 103 break 104 } 105 106 // Look for an edge 107 _, n = n.getEdge(search[0]) 108 if n == nil { 109 break 110 } 111 112 // Update to the finest granularity as the search makes progress 113 watch = n.mutateCh 114 115 // Consume the search prefix 116 if bytes.HasPrefix(search, n.prefix) { 117 search = search[len(n.prefix):] 118 } else { 119 break 120 } 121 } 122 return watch, nil, false 123} 124 125func (n *Node) Get(k []byte) (interface{}, bool) { 126 _, val, ok := n.GetWatch(k) 127 return val, ok 128} 129 130// LongestPrefix is like Get, but instead of an 131// exact match, it will return the longest prefix match. 132func (n *Node) LongestPrefix(k []byte) ([]byte, interface{}, bool) { 133 var last *leafNode 134 search := k 135 for { 136 // Look for a leaf node 137 if n.isLeaf() { 138 last = n.leaf 139 } 140 141 // Check for key exhaution 142 if len(search) == 0 { 143 break 144 } 145 146 // Look for an edge 147 _, n = n.getEdge(search[0]) 148 if n == nil { 149 break 150 } 151 152 // Consume the search prefix 153 if bytes.HasPrefix(search, n.prefix) { 154 search = search[len(n.prefix):] 155 } else { 156 break 157 } 158 } 159 if last != nil { 160 return last.key, last.val, true 161 } 162 return nil, nil, false 163} 164 165// Minimum is used to return the minimum value in the tree 166func (n *Node) Minimum() ([]byte, interface{}, bool) { 167 for { 168 if n.isLeaf() { 169 return n.leaf.key, n.leaf.val, true 170 } 171 if len(n.edges) > 0 { 172 n = n.edges[0].node 173 } else { 174 break 175 } 176 } 177 return nil, nil, false 178} 179 180// Maximum is used to return the maximum value in the tree 181func (n *Node) Maximum() ([]byte, interface{}, bool) { 182 for { 183 if num := len(n.edges); num > 0 { 184 n = n.edges[num-1].node 185 continue 186 } 187 if n.isLeaf() { 188 return n.leaf.key, n.leaf.val, true 189 } else { 190 break 191 } 192 } 193 return nil, nil, false 194} 195 196// Iterator is used to return an iterator at 197// the given node to walk the tree 198func (n *Node) Iterator() *Iterator { 199 return &Iterator{node: n} 200} 201 202// rawIterator is used to return a raw iterator at the given node to walk the 203// tree. 204func (n *Node) rawIterator() *rawIterator { 205 iter := &rawIterator{node: n} 206 iter.Next() 207 return iter 208} 209 210// Walk is used to walk the tree 211func (n *Node) Walk(fn WalkFn) { 212 recursiveWalk(n, fn) 213} 214 215// WalkPrefix is used to walk the tree under a prefix 216func (n *Node) WalkPrefix(prefix []byte, fn WalkFn) { 217 search := prefix 218 for { 219 // Check for key exhaution 220 if len(search) == 0 { 221 recursiveWalk(n, fn) 222 return 223 } 224 225 // Look for an edge 226 _, n = n.getEdge(search[0]) 227 if n == nil { 228 break 229 } 230 231 // Consume the search prefix 232 if bytes.HasPrefix(search, n.prefix) { 233 search = search[len(n.prefix):] 234 235 } else if bytes.HasPrefix(n.prefix, search) { 236 // Child may be under our search prefix 237 recursiveWalk(n, fn) 238 return 239 } else { 240 break 241 } 242 } 243} 244 245// WalkPath is used to walk the tree, but only visiting nodes 246// from the root down to a given leaf. Where WalkPrefix walks 247// all the entries *under* the given prefix, this walks the 248// entries *above* the given prefix. 249func (n *Node) WalkPath(path []byte, fn WalkFn) { 250 search := path 251 for { 252 // Visit the leaf values if any 253 if n.leaf != nil && fn(n.leaf.key, n.leaf.val) { 254 return 255 } 256 257 // Check for key exhaution 258 if len(search) == 0 { 259 return 260 } 261 262 // Look for an edge 263 _, n = n.getEdge(search[0]) 264 if n == nil { 265 return 266 } 267 268 // Consume the search prefix 269 if bytes.HasPrefix(search, n.prefix) { 270 search = search[len(n.prefix):] 271 } else { 272 break 273 } 274 } 275} 276 277// recursiveWalk is used to do a pre-order walk of a node 278// recursively. Returns true if the walk should be aborted 279func recursiveWalk(n *Node, fn WalkFn) bool { 280 // Visit the leaf values if any 281 if n.leaf != nil && fn(n.leaf.key, n.leaf.val) { 282 return true 283 } 284 285 // Recurse on the children 286 for _, e := range n.edges { 287 if recursiveWalk(e.node, fn) { 288 return true 289 } 290 } 291 return false 292} 293