1 // Copyright (c) 2014 The go-patricia AUTHORS
3 // Use of this source code is governed by The MIT License
4 // that can be found in the LICENSE file.
14 type childList interface {
17 add(child *Trie) childList
19 replace(b byte, child *Trie)
21 walk(prefix *Prefix, visitor VisitorFunc) error
22 print(w io.Writer, indent int)
28 func (t tries) Len() int {
32 func (t tries) Less(i, j int) bool {
33 strings := sort.StringSlice{string(t[i].prefix), string(t[j].prefix)}
34 return strings.Less(0, 1)
37 func (t tries) Swap(i, j int) {
38 t[i], t[j] = t[j], t[i]
41 type sparseChildList struct {
45 func newSparseChildList(maxChildrenPerSparseNode int) childList {
46 return &sparseChildList{
47 children: make(tries, 0, maxChildrenPerSparseNode),
51 func (list *sparseChildList) length() int {
52 return len(list.children)
55 func (list *sparseChildList) head() *Trie {
56 return list.children[0]
59 func (list *sparseChildList) add(child *Trie) childList {
60 // Search for an empty spot and insert the child if possible.
61 if len(list.children) != cap(list.children) {
62 list.children = append(list.children, child)
66 // Otherwise we have to transform to the dense list type.
67 return newDenseChildList(list, child)
70 func (list *sparseChildList) remove(b byte) {
71 for i, node := range list.children {
72 if node.prefix[0] == b {
73 list.children[i] = list.children[len(list.children)-1]
74 list.children[len(list.children)-1] = nil
75 list.children = list.children[:len(list.children)-1]
80 // This is not supposed to be reached.
81 panic("removing non-existent child")
84 func (list *sparseChildList) replace(b byte, child *Trie) {
85 // Make a consistency check.
86 if p0 := child.prefix[0]; p0 != b {
87 panic(fmt.Errorf("child prefix mismatch: %v != %v", p0, b))
90 // Seek the child and replace it.
91 for i, node := range list.children {
92 if node.prefix[0] == b {
93 list.children[i] = child
99 func (list *sparseChildList) next(b byte) *Trie {
100 for _, child := range list.children {
101 if child.prefix[0] == b {
108 func (list *sparseChildList) walk(prefix *Prefix, visitor VisitorFunc) error {
110 sort.Sort(list.children)
112 for _, child := range list.children {
113 *prefix = append(*prefix, child.prefix...)
114 if child.item != nil {
115 err := visitor(*prefix, child.item)
117 if err == SkipSubtree {
118 *prefix = (*prefix)[:len(*prefix)-len(child.prefix)]
121 *prefix = (*prefix)[:len(*prefix)-len(child.prefix)]
126 err := child.children.walk(prefix, visitor)
127 *prefix = (*prefix)[:len(*prefix)-len(child.prefix)]
136 func (list *sparseChildList) total() int {
138 for _, child := range list.children {
140 tot = tot + child.total()
146 func (list *sparseChildList) print(w io.Writer, indent int) {
147 for _, child := range list.children {
149 child.print(w, indent)
154 type denseChildList struct {
162 func newDenseChildList(list *sparseChildList, child *Trie) childList {
167 for _, child := range list.children {
168 b := int(child.prefix[0])
177 b := int(child.prefix[0])
185 children := make([]*Trie, max-min+1)
186 for _, child := range list.children {
187 children[int(child.prefix[0])-min] = child
189 children[int(child.prefix[0])-min] = child
191 return &denseChildList{
194 numChildren: list.length() + 1,
200 func (list *denseChildList) length() int {
201 return list.numChildren
204 func (list *denseChildList) head() *Trie {
205 return list.children[list.headIndex]
208 func (list *denseChildList) add(child *Trie) childList {
209 b := int(child.prefix[0])
213 case list.min <= b && b <= list.max:
214 if list.children[b-list.min] != nil {
215 panic("dense child list collision detected")
218 list.children[i] = child
221 children := make([]*Trie, list.max-b+1)
224 copy(children[list.min-b:], list.children)
225 list.children = children
228 default: // b > list.max
229 children := make([]*Trie, b-list.min+1)
232 copy(children, list.children)
233 list.children = children
238 if i < list.headIndex {
244 func (list *denseChildList) remove(b byte) {
245 i := int(b) - list.min
246 if list.children[i] == nil {
247 // This is not supposed to be reached.
248 panic("removing non-existent child")
251 list.children[i] = nil
253 // Update head index.
254 if i == list.headIndex {
255 for ; i < len(list.children); i++ {
256 if list.children[i] != nil {
264 func (list *denseChildList) replace(b byte, child *Trie) {
265 // Make a consistency check.
266 if p0 := child.prefix[0]; p0 != b {
267 panic(fmt.Errorf("child prefix mismatch: %v != %v", p0, b))
270 // Replace the child.
271 list.children[int(b)-list.min] = child
274 func (list *denseChildList) next(b byte) *Trie {
276 if i < list.min || list.max < i {
279 return list.children[i-list.min]
282 func (list *denseChildList) walk(prefix *Prefix, visitor VisitorFunc) error {
283 for _, child := range list.children {
287 *prefix = append(*prefix, child.prefix...)
288 if child.item != nil {
289 if err := visitor(*prefix, child.item); err != nil {
290 if err == SkipSubtree {
291 *prefix = (*prefix)[:len(*prefix)-len(child.prefix)]
294 *prefix = (*prefix)[:len(*prefix)-len(child.prefix)]
299 err := child.children.walk(prefix, visitor)
300 *prefix = (*prefix)[:len(*prefix)-len(child.prefix)]
309 func (list *denseChildList) print(w io.Writer, indent int) {
310 for _, child := range list.children {
312 child.print(w, indent)
317 func (list *denseChildList) total() int {
319 for _, child := range list.children {
321 tot = tot + child.total()