vendor/github.com/btcsuite/btcd/database/internal/treap/common_test.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         "encoding/binary"
   9         "encoding/hex"
  10         "math/rand"
  11         "reflect"
  12         "testing"
  13 )
  14
  15 // fromHex converts the passed hex string into a byte slice and will panic if
  16 // there is an error.  This is only provided for the hard-coded constants so
  17 // errors in the source code can be detected. It will only (and must only) be
  18 // called for initialization purposes.
  19 func fromHex(s string) []byte {
  20         r, err := hex.DecodeString(s)
  21         if err != nil {
  22                 panic("invalid hex in source file: " + s)
  23         }
  24         return r
  25 }
  26
  27 // serializeUint32 returns the big-endian encoding of the passed uint32.
  28 func serializeUint32(ui uint32) []byte {
  29         var ret [4]byte
  30         binary.BigEndian.PutUint32(ret[:], ui)
  31         return ret[:]
  32 }
  33
  34 // TestParentStack ensures the treapParentStack functionality works as intended.
  35 func TestParentStack(t *testing.T) {
  36         t.Parallel()
  37
  38         tests := []struct {
  39                 numNodes int
  40         }{
  41                 {numNodes: 1},
  42                 {numNodes: staticDepth},
  43                 {numNodes: staticDepth + 1}, // Test dynamic code paths
  44         }
  45
  46 testLoop:
  47         for i, test := range tests {
  48                 nodes := make([]*treapNode, 0, test.numNodes)
  49                 for j := 0; j < test.numNodes; j++ {
  50                         var key [4]byte
  51                         binary.BigEndian.PutUint32(key[:], uint32(j))
  52                         node := newTreapNode(key[:], key[:], 0)
  53                         nodes = append(nodes, node)
  54                 }
  55
  56                 // Push all of the nodes onto the parent stack while testing
  57                 // various stack properties.
  58                 stack := &parentStack{}
  59                 for j, node := range nodes {
  60                         stack.Push(node)
  61
  62                         // Ensure the stack length is the expected value.
  63                         if stack.Len() != j+1 {
  64                                 t.Errorf("Len #%d (%d): unexpected stack "+
  65                                         "length - got %d, want %d", i, j,
  66                                         stack.Len(), j+1)
  67                                 continue testLoop
  68                         }
  69
  70                         // Ensure the node at each index is the expected one.
  71                         for k := 0; k <= j; k++ {
  72                                 atNode := stack.At(j - k)
  73                                 if !reflect.DeepEqual(atNode, nodes[k]) {
  74                                         t.Errorf("At #%d (%d): mismatched node "+
  75                                                 "- got %v, want %v", i, j-k,
  76                                                 atNode, nodes[k])
  77                                         continue testLoop
  78                                 }
  79                         }
  80                 }
  81
  82                 // Ensure each popped node is the expected one.
  83                 for j := 0; j < len(nodes); j++ {
  84                         node := stack.Pop()
  85                         expected := nodes[len(nodes)-j-1]
  86                         if !reflect.DeepEqual(node, expected) {
  87                                 t.Errorf("At #%d (%d): mismatched node - "+
  88                                         "got %v, want %v", i, j, node, expected)
  89                                 continue testLoop
  90                         }
  91                 }
  92
  93                 // Ensure the stack is now empty.
  94                 if stack.Len() != 0 {
  95                         t.Errorf("Len #%d: stack is not empty - got %d", i,
  96                                 stack.Len())
  97                         continue testLoop
  98                 }
  99
 100                 // Ensure attempting to retrieve a node at an index beyond the
 101                 // stack's length returns nil.
 102                 if node := stack.At(2); node != nil {
 103                         t.Errorf("At #%d: did not give back nil - got %v", i,
 104                                 node)
 105                         continue testLoop
 106                 }
 107
 108                 // Ensure attempting to pop a node from an empty stack returns
 109                 // nil.
 110                 if node := stack.Pop(); node != nil {
 111                         t.Errorf("Pop #%d: did not give back nil - got %v", i,
 112                                 node)
 113                         continue testLoop
 114                 }
 115         }
 116 }
 117
 118 func init() {
 119         // Force the same pseudo random numbers for each test run.
 120         rand.Seed(0)
 121 }