vendor/github.com/btcsuite/btcd/database/internal/treap/common.go

   1 // Copyright (c) 2015-2016 The btcsuite developers
   2 // Use of this source code is governed by an ISC
   3 // license that can be found in the LICENSE file.
   4
   5 package treap
   6
   7 import (
   8         "math/rand"
   9         "time"
  10 )
  11
  12 const (
  13         // staticDepth is the size of the static array to use for keeping track
  14         // of the parent stack during treap iteration.  Since a treap has a very
  15         // high probability that the tree height is logarithmic, it is
  16         // exceedingly unlikely that the parent stack will ever exceed this size
  17         // even for extremely large numbers of items.
  18         staticDepth = 128
  19
  20         // nodeFieldsSize is the size the fields of each node takes excluding
  21         // the contents of the key and value.  It assumes 64-bit pointers so
  22         // technically it is smaller on 32-bit platforms, but overestimating the
  23         // size in that case is acceptable since it avoids the need to import
  24         // unsafe.  It consists of 24-bytes for each key and value + 8 bytes for
  25         // each of the priority, left, and right fields (24*2 + 8*3).
  26         nodeFieldsSize = 72
  27 )
  28
  29 var (
  30         // emptySlice is used for keys that have no value associated with them
  31         // so callers can distinguish between a key that does not exist and one
  32         // that has no value associated with it.
  33         emptySlice = make([]byte, 0)
  34 )
  35
  36 // treapNode represents a node in the treap.
  37 type treapNode struct {
  38         key      []byte
  39         value    []byte
  40         priority int
  41         left     *treapNode
  42         right    *treapNode
  43 }
  44
  45 // nodeSize returns the number of bytes the specified node occupies including
  46 // the struct fields and the contents of the key and value.
  47 func nodeSize(node *treapNode) uint64 {
  48         return nodeFieldsSize + uint64(len(node.key)+len(node.value))
  49 }
  50
  51 // newTreapNode returns a new node from the given key, value, and priority.  The
  52 // node is not initially linked to any others.
  53 func newTreapNode(key, value []byte, priority int) *treapNode {
  54         return &treapNode{key: key, value: value, priority: priority}
  55 }
  56
  57 // parentStack represents a stack of parent treap nodes that are used during
  58 // iteration.  It consists of a static array for holding the parents and a
  59 // dynamic overflow slice.  It is extremely unlikely the overflow will ever be
  60 // hit during normal operation, however, since a treap's height is
  61 // probabilistic, the overflow case needs to be handled properly.  This approach
  62 // is used because it is much more efficient for the majority case than
  63 // dynamically allocating heap space every time the treap is iterated.
  64 type parentStack struct {
  65         index    int
  66         items    [staticDepth]*treapNode
  67         overflow []*treapNode
  68 }
  69
  70 // Len returns the current number of items in the stack.
  71 func (s *parentStack) Len() int {
  72         return s.index
  73 }
  74
  75 // At returns the item n number of items from the top of the stack, where 0 is
  76 // the topmost item, without removing it.  It returns nil if n exceeds the
  77 // number of items on the stack.
  78 func (s *parentStack) At(n int) *treapNode {
  79         index := s.index - n - 1
  80         if index < 0 {
  81                 return nil
  82         }
  83
  84         if index < staticDepth {
  85                 return s.items[index]
  86         }
  87
  88         return s.overflow[index-staticDepth]
  89 }
  90
  91 // Pop removes the top item from the stack.  It returns nil if the stack is
  92 // empty.
  93 func (s *parentStack) Pop() *treapNode {
  94         if s.index == 0 {
  95                 return nil
  96         }
  97
  98         s.index--
  99         if s.index < staticDepth {
 100                 node := s.items[s.index]
 101                 s.items[s.index] = nil
 102                 return node
 103         }
 104
 105         node := s.overflow[s.index-staticDepth]
 106         s.overflow[s.index-staticDepth] = nil
 107         return node
 108 }
 109
 110 // Push pushes the passed item onto the top of the stack.
 111 func (s *parentStack) Push(node *treapNode) {
 112         if s.index < staticDepth {
 113                 s.items[s.index] = node
 114                 s.index++
 115                 return
 116         }
 117
 118         // This approach is used over append because reslicing the slice to pop
 119         // the item causes the compiler to make unneeded allocations.  Also,
 120         // since the max number of items is related to the tree depth which
 121         // requires expontentially more items to increase, only increase the cap
 122         // one item at a time.  This is more intelligent than the generic append
 123         // expansion algorithm which often doubles the cap.
 124         index := s.index - staticDepth
 125         if index+1 > cap(s.overflow) {
 126                 overflow := make([]*treapNode, index+1)
 127                 copy(overflow, s.overflow)
 128                 s.overflow = overflow
 129         }
 130         s.overflow[index] = node
 131         s.index++
 132 }
 133
 134 func init() {
 135         rand.Seed(time.Now().UnixNano())
 136 }