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