1package bbolt 2 3import ( 4 "testing" 5 "unsafe" 6) 7 8// Ensure that a node can insert a key/value. 9func TestNode_put(t *testing.T) { 10 n := &node{inodes: make(inodes, 0), bucket: &Bucket{tx: &Tx{meta: &meta{pgid: 1}}}} 11 n.put([]byte("baz"), []byte("baz"), []byte("2"), 0, 0) 12 n.put([]byte("foo"), []byte("foo"), []byte("0"), 0, 0) 13 n.put([]byte("bar"), []byte("bar"), []byte("1"), 0, 0) 14 n.put([]byte("foo"), []byte("foo"), []byte("3"), 0, leafPageFlag) 15 16 if len(n.inodes) != 3 { 17 t.Fatalf("exp=3; got=%d", len(n.inodes)) 18 } 19 if k, v := n.inodes[0].key, n.inodes[0].value; string(k) != "bar" || string(v) != "1" { 20 t.Fatalf("exp=<bar,1>; got=<%s,%s>", k, v) 21 } 22 if k, v := n.inodes[1].key, n.inodes[1].value; string(k) != "baz" || string(v) != "2" { 23 t.Fatalf("exp=<baz,2>; got=<%s,%s>", k, v) 24 } 25 if k, v := n.inodes[2].key, n.inodes[2].value; string(k) != "foo" || string(v) != "3" { 26 t.Fatalf("exp=<foo,3>; got=<%s,%s>", k, v) 27 } 28 if n.inodes[2].flags != uint32(leafPageFlag) { 29 t.Fatalf("not a leaf: %d", n.inodes[2].flags) 30 } 31} 32 33// Ensure that a node can deserialize from a leaf page. 34func TestNode_read_LeafPage(t *testing.T) { 35 // Create a page. 36 var buf [4096]byte 37 page := (*page)(unsafe.Pointer(&buf[0])) 38 page.flags = leafPageFlag 39 page.count = 2 40 41 // Insert 2 elements at the beginning. sizeof(leafPageElement) == 16 42 nodes := (*[3]leafPageElement)(unsafe.Pointer(&page.ptr)) 43 nodes[0] = leafPageElement{flags: 0, pos: 32, ksize: 3, vsize: 4} // pos = sizeof(leafPageElement) * 2 44 nodes[1] = leafPageElement{flags: 0, pos: 23, ksize: 10, vsize: 3} // pos = sizeof(leafPageElement) + 3 + 4 45 46 // Write data for the nodes at the end. 47 data := (*[4096]byte)(unsafe.Pointer(&nodes[2])) 48 copy(data[:], "barfooz") 49 copy(data[7:], "helloworldbye") 50 51 // Deserialize page into a leaf. 52 n := &node{} 53 n.read(page) 54 55 // Check that there are two inodes with correct data. 56 if !n.isLeaf { 57 t.Fatal("expected leaf") 58 } 59 if len(n.inodes) != 2 { 60 t.Fatalf("exp=2; got=%d", len(n.inodes)) 61 } 62 if k, v := n.inodes[0].key, n.inodes[0].value; string(k) != "bar" || string(v) != "fooz" { 63 t.Fatalf("exp=<bar,fooz>; got=<%s,%s>", k, v) 64 } 65 if k, v := n.inodes[1].key, n.inodes[1].value; string(k) != "helloworld" || string(v) != "bye" { 66 t.Fatalf("exp=<helloworld,bye>; got=<%s,%s>", k, v) 67 } 68} 69 70// Ensure that a node can serialize into a leaf page. 71func TestNode_write_LeafPage(t *testing.T) { 72 // Create a node. 73 n := &node{isLeaf: true, inodes: make(inodes, 0), bucket: &Bucket{tx: &Tx{db: &DB{}, meta: &meta{pgid: 1}}}} 74 n.put([]byte("susy"), []byte("susy"), []byte("que"), 0, 0) 75 n.put([]byte("ricki"), []byte("ricki"), []byte("lake"), 0, 0) 76 n.put([]byte("john"), []byte("john"), []byte("johnson"), 0, 0) 77 78 // Write it to a page. 79 var buf [4096]byte 80 p := (*page)(unsafe.Pointer(&buf[0])) 81 n.write(p) 82 83 // Read the page back in. 84 n2 := &node{} 85 n2.read(p) 86 87 // Check that the two pages are the same. 88 if len(n2.inodes) != 3 { 89 t.Fatalf("exp=3; got=%d", len(n2.inodes)) 90 } 91 if k, v := n2.inodes[0].key, n2.inodes[0].value; string(k) != "john" || string(v) != "johnson" { 92 t.Fatalf("exp=<john,johnson>; got=<%s,%s>", k, v) 93 } 94 if k, v := n2.inodes[1].key, n2.inodes[1].value; string(k) != "ricki" || string(v) != "lake" { 95 t.Fatalf("exp=<ricki,lake>; got=<%s,%s>", k, v) 96 } 97 if k, v := n2.inodes[2].key, n2.inodes[2].value; string(k) != "susy" || string(v) != "que" { 98 t.Fatalf("exp=<susy,que>; got=<%s,%s>", k, v) 99 } 100} 101 102// Ensure that a node can split into appropriate subgroups. 103func TestNode_split(t *testing.T) { 104 // Create a node. 105 n := &node{inodes: make(inodes, 0), bucket: &Bucket{tx: &Tx{db: &DB{}, meta: &meta{pgid: 1}}}} 106 n.put([]byte("00000001"), []byte("00000001"), []byte("0123456701234567"), 0, 0) 107 n.put([]byte("00000002"), []byte("00000002"), []byte("0123456701234567"), 0, 0) 108 n.put([]byte("00000003"), []byte("00000003"), []byte("0123456701234567"), 0, 0) 109 n.put([]byte("00000004"), []byte("00000004"), []byte("0123456701234567"), 0, 0) 110 n.put([]byte("00000005"), []byte("00000005"), []byte("0123456701234567"), 0, 0) 111 112 // Split between 2 & 3. 113 n.split(100) 114 115 var parent = n.parent 116 if len(parent.children) != 2 { 117 t.Fatalf("exp=2; got=%d", len(parent.children)) 118 } 119 if len(parent.children[0].inodes) != 2 { 120 t.Fatalf("exp=2; got=%d", len(parent.children[0].inodes)) 121 } 122 if len(parent.children[1].inodes) != 3 { 123 t.Fatalf("exp=3; got=%d", len(parent.children[1].inodes)) 124 } 125} 126 127// Ensure that a page with the minimum number of inodes just returns a single node. 128func TestNode_split_MinKeys(t *testing.T) { 129 // Create a node. 130 n := &node{inodes: make(inodes, 0), bucket: &Bucket{tx: &Tx{db: &DB{}, meta: &meta{pgid: 1}}}} 131 n.put([]byte("00000001"), []byte("00000001"), []byte("0123456701234567"), 0, 0) 132 n.put([]byte("00000002"), []byte("00000002"), []byte("0123456701234567"), 0, 0) 133 134 // Split. 135 n.split(20) 136 if n.parent != nil { 137 t.Fatalf("expected nil parent") 138 } 139} 140 141// Ensure that a node that has keys that all fit on a page just returns one leaf. 142func TestNode_split_SinglePage(t *testing.T) { 143 // Create a node. 144 n := &node{inodes: make(inodes, 0), bucket: &Bucket{tx: &Tx{db: &DB{}, meta: &meta{pgid: 1}}}} 145 n.put([]byte("00000001"), []byte("00000001"), []byte("0123456701234567"), 0, 0) 146 n.put([]byte("00000002"), []byte("00000002"), []byte("0123456701234567"), 0, 0) 147 n.put([]byte("00000003"), []byte("00000003"), []byte("0123456701234567"), 0, 0) 148 n.put([]byte("00000004"), []byte("00000004"), []byte("0123456701234567"), 0, 0) 149 n.put([]byte("00000005"), []byte("00000005"), []byte("0123456701234567"), 0, 0) 150 151 // Split. 152 n.split(4096) 153 if n.parent != nil { 154 t.Fatalf("expected nil parent") 155 } 156} 157