vendor/github.com/tchap/go-patricia/patricia/children.go

   1 // Copyright (c) 2014 The go-patricia AUTHORS
   2 //
   3 // Use of this source code is governed by The MIT License
   4 // that can be found in the LICENSE file.
   5
   6 package patricia
   7
   8 import (
   9         "fmt"
  10         "io"
  11         "sort"
  12 )
  13
  14 type childList interface {
  15         length() int
  16         head() *Trie
  17         add(child *Trie) childList
  18         remove(b byte)
  19         replace(b byte, child *Trie)
  20         next(b byte) *Trie
  21         walk(prefix *Prefix, visitor VisitorFunc) error
  22         print(w io.Writer, indent int)
  23         total() int
  24 }
  25
  26 type tries []*Trie
  27
  28 func (t tries) Len() int {
  29         return len(t)
  30 }
  31
  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)
  35 }
  36
  37 func (t tries) Swap(i, j int) {
  38         t[i], t[j] = t[j], t[i]
  39 }
  40
  41 type sparseChildList struct {
  42         children tries
  43 }
  44
  45 func newSparseChildList(maxChildrenPerSparseNode int) childList {
  46         return &sparseChildList{
  47                 children: make(tries, 0, maxChildrenPerSparseNode),
  48         }
  49 }
  50
  51 func (list *sparseChildList) length() int {
  52         return len(list.children)
  53 }
  54
  55 func (list *sparseChildList) head() *Trie {
  56         return list.children[0]
  57 }
  58
  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)
  63                 return list
  64         }
  65
  66         // Otherwise we have to transform to the dense list type.
  67         return newDenseChildList(list, child)
  68 }
  69
  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]
  76                         return
  77                 }
  78         }
  79
  80         // This is not supposed to be reached.
  81         panic("removing non-existent child")
  82 }
  83
  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))
  88         }
  89
  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
  94                         return
  95                 }
  96         }
  97 }
  98
  99 func (list *sparseChildList) next(b byte) *Trie {
 100         for _, child := range list.children {
 101                 if child.prefix[0] == b {
 102                         return child
 103                 }
 104         }
 105         return nil
 106 }
 107
 108 func (list *sparseChildList) walk(prefix *Prefix, visitor VisitorFunc) error {
 109
 110         sort.Sort(list.children)
 111
 112         for _, child := range list.children {
 113                 *prefix = append(*prefix, child.prefix...)
 114                 if child.item != nil {
 115                         err := visitor(*prefix, child.item)
 116                         if err != nil {
 117                                 if err == SkipSubtree {
 118                                         *prefix = (*prefix)[:len(*prefix)-len(child.prefix)]
 119                                         continue
 120                                 }
 121                                 *prefix = (*prefix)[:len(*prefix)-len(child.prefix)]
 122                                 return err
 123                         }
 124                 }
 125
 126                 err := child.children.walk(prefix, visitor)
 127                 *prefix = (*prefix)[:len(*prefix)-len(child.prefix)]
 128                 if err != nil {
 129                         return err
 130                 }
 131         }
 132
 133         return nil
 134 }
 135
 136 func (list *sparseChildList) total() int {
 137         tot := 0
 138         for _, child := range list.children {
 139                 if child != nil {
 140                         tot = tot + child.total()
 141                 }
 142         }
 143         return tot
 144 }
 145
 146 func (list *sparseChildList) print(w io.Writer, indent int) {
 147         for _, child := range list.children {
 148                 if child != nil {
 149                         child.print(w, indent)
 150                 }
 151         }
 152 }
 153
 154 type denseChildList struct {
 155         min         int
 156         max         int
 157         numChildren int
 158         headIndex   int
 159         children    []*Trie
 160 }
 161
 162 func newDenseChildList(list *sparseChildList, child *Trie) childList {
 163         var (
 164                 min int = 255
 165                 max int = 0
 166         )
 167         for _, child := range list.children {
 168                 b := int(child.prefix[0])
 169                 if b < min {
 170                         min = b
 171                 }
 172                 if b > max {
 173                         max = b
 174                 }
 175         }
 176
 177         b := int(child.prefix[0])
 178         if b < min {
 179                 min = b
 180         }
 181         if b > max {
 182                 max = b
 183         }
 184
 185         children := make([]*Trie, max-min+1)
 186         for _, child := range list.children {
 187                 children[int(child.prefix[0])-min] = child
 188         }
 189         children[int(child.prefix[0])-min] = child
 190
 191         return &denseChildList{
 192                 min:         min,
 193                 max:         max,
 194                 numChildren: list.length() + 1,
 195                 headIndex:   0,
 196                 children:    children,
 197         }
 198 }
 199
 200 func (list *denseChildList) length() int {
 201         return list.numChildren
 202 }
 203
 204 func (list *denseChildList) head() *Trie {
 205         return list.children[list.headIndex]
 206 }
 207
 208 func (list *denseChildList) add(child *Trie) childList {
 209         b := int(child.prefix[0])
 210         var i int
 211
 212         switch {
 213         case list.min <= b && b <= list.max:
 214                 if list.children[b-list.min] != nil {
 215                         panic("dense child list collision detected")
 216                 }
 217                 i = b - list.min
 218                 list.children[i] = child
 219
 220         case b < list.min:
 221                 children := make([]*Trie, list.max-b+1)
 222                 i = 0
 223                 children[i] = child
 224                 copy(children[list.min-b:], list.children)
 225                 list.children = children
 226                 list.min = b
 227
 228         default: // b > list.max
 229                 children := make([]*Trie, b-list.min+1)
 230                 i = b - list.min
 231                 children[i] = child
 232                 copy(children, list.children)
 233                 list.children = children
 234                 list.max = b
 235         }
 236
 237         list.numChildren++
 238         if i < list.headIndex {
 239                 list.headIndex = i
 240         }
 241         return list
 242 }
 243
 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")
 249         }
 250         list.numChildren--
 251         list.children[i] = nil
 252
 253         // Update head index.
 254         if i == list.headIndex {
 255                 for ; i < len(list.children); i++ {
 256                         if list.children[i] != nil {
 257                                 list.headIndex = i
 258                                 return
 259                         }
 260                 }
 261         }
 262 }
 263
 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))
 268         }
 269
 270         // Replace the child.
 271         list.children[int(b)-list.min] = child
 272 }
 273
 274 func (list *denseChildList) next(b byte) *Trie {
 275         i := int(b)
 276         if i < list.min || list.max < i {
 277                 return nil
 278         }
 279         return list.children[i-list.min]
 280 }
 281
 282 func (list *denseChildList) walk(prefix *Prefix, visitor VisitorFunc) error {
 283         for _, child := range list.children {
 284                 if child == nil {
 285                         continue
 286                 }
 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)]
 292                                         continue
 293                                 }
 294                                 *prefix = (*prefix)[:len(*prefix)-len(child.prefix)]
 295                                 return err
 296                         }
 297                 }
 298
 299                 err := child.children.walk(prefix, visitor)
 300                 *prefix = (*prefix)[:len(*prefix)-len(child.prefix)]
 301                 if err != nil {
 302                         return err
 303                 }
 304         }
 305
 306         return nil
 307 }
 308
 309 func (list *denseChildList) print(w io.Writer, indent int) {
 310         for _, child := range list.children {
 311                 if child != nil {
 312                         child.print(w, indent)
 313                 }
 314         }
 315 }
 316
 317 func (list *denseChildList) total() int {
 318         tot := 0
 319         for _, child := range list.children {
 320                 if child != nil {
 321                         tot = tot + child.total()
 322                 }
 323         }
 324         return tot
 325 }