vendor/github.com/btcsuite/btcd/database/internal/treap/mutable_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         "bytes"
   9         "crypto/sha256"
  10         "testing"
  11 )
  12
  13 // TestMutableEmpty ensures calling functions on an empty mutable treap works as
  14 // expected.
  15 func TestMutableEmpty(t *testing.T) {
  16         t.Parallel()
  17
  18         // Ensure the treap length is the expected value.
  19         testTreap := NewMutable()
  20         if gotLen := testTreap.Len(); gotLen != 0 {
  21                 t.Fatalf("Len: unexpected length - got %d, want %d", gotLen, 0)
  22         }
  23
  24         // Ensure the reported size is 0.
  25         if gotSize := testTreap.Size(); gotSize != 0 {
  26                 t.Fatalf("Size: unexpected byte size - got %d, want 0",
  27                         gotSize)
  28         }
  29
  30         // Ensure there are no errors with requesting keys from an empty treap.
  31         key := serializeUint32(0)
  32         if gotVal := testTreap.Has(key); gotVal {
  33                 t.Fatalf("Has: unexpected result - got %v, want false", gotVal)
  34         }
  35         if gotVal := testTreap.Get(key); gotVal != nil {
  36                 t.Fatalf("Get: unexpected result - got %x, want nil", gotVal)
  37         }
  38
  39         // Ensure there are no panics when deleting keys from an empty treap.
  40         testTreap.Delete(key)
  41
  42         // Ensure the number of keys iterated by ForEach on an empty treap is
  43         // zero.
  44         var numIterated int
  45         testTreap.ForEach(func(k, v []byte) bool {
  46                 numIterated++
  47                 return true
  48         })
  49         if numIterated != 0 {
  50                 t.Fatalf("ForEach: unexpected iterate count - got %d, want 0",
  51                         numIterated)
  52         }
  53 }
  54
  55 // TestMutableReset ensures that resetting an existing mutable treap works as
  56 // expected.
  57 func TestMutableReset(t *testing.T) {
  58         t.Parallel()
  59
  60         // Insert a few keys.
  61         numItems := 10
  62         testTreap := NewMutable()
  63         for i := 0; i < numItems; i++ {
  64                 key := serializeUint32(uint32(i))
  65                 testTreap.Put(key, key)
  66         }
  67
  68         // Reset it.
  69         testTreap.Reset()
  70
  71         // Ensure the treap length is now 0.
  72         if gotLen := testTreap.Len(); gotLen != 0 {
  73                 t.Fatalf("Len: unexpected length - got %d, want %d", gotLen, 0)
  74         }
  75
  76         // Ensure the reported size is now 0.
  77         if gotSize := testTreap.Size(); gotSize != 0 {
  78                 t.Fatalf("Size: unexpected byte size - got %d, want 0",
  79                         gotSize)
  80         }
  81
  82         // Ensure the treap no longer has any of the keys.
  83         for i := 0; i < numItems; i++ {
  84                 key := serializeUint32(uint32(i))
  85
  86                 // Ensure the treap no longer has the key.
  87                 if testTreap.Has(key) {
  88                         t.Fatalf("Has #%d: key %q is in treap", i, key)
  89                 }
  90
  91                 // Get the key that no longer exists from the treap and ensure
  92                 // it is nil.
  93                 if gotVal := testTreap.Get(key); gotVal != nil {
  94                         t.Fatalf("Get #%d: unexpected value - got %x, want nil",
  95                                 i, gotVal)
  96                 }
  97         }
  98
  99         // Ensure the number of keys iterated by ForEach is zero.
 100         var numIterated int
 101         testTreap.ForEach(func(k, v []byte) bool {
 102                 numIterated++
 103                 return true
 104         })
 105         if numIterated != 0 {
 106                 t.Fatalf("ForEach: unexpected iterate count - got %d, want 0",
 107                         numIterated)
 108         }
 109 }
 110
 111 // TestMutableSequential ensures that putting keys into a mutable treap in
 112 // sequential order works as expected.
 113 func TestMutableSequential(t *testing.T) {
 114         t.Parallel()
 115
 116         // Insert a bunch of sequential keys while checking several of the treap
 117         // functions work as expected.
 118         expectedSize := uint64(0)
 119         numItems := 1000
 120         testTreap := NewMutable()
 121         for i := 0; i < numItems; i++ {
 122                 key := serializeUint32(uint32(i))
 123                 testTreap.Put(key, key)
 124
 125                 // Ensure the treap length is the expected value.
 126                 if gotLen := testTreap.Len(); gotLen != i+1 {
 127                         t.Fatalf("Len #%d: unexpected length - got %d, want %d",
 128                                 i, gotLen, i+1)
 129                 }
 130
 131                 // Ensure the treap has the key.
 132                 if !testTreap.Has(key) {
 133                         t.Fatalf("Has #%d: key %q is not in treap", i, key)
 134                 }
 135
 136                 // Get the key from the treap and ensure it is the expected
 137                 // value.
 138                 if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
 139                         t.Fatalf("Get #%d: unexpected value - got %x, want %x",
 140                                 i, gotVal, key)
 141                 }
 142
 143                 // Ensure the expected size is reported.
 144                 expectedSize += (nodeFieldsSize + 8)
 145                 if gotSize := testTreap.Size(); gotSize != expectedSize {
 146                         t.Fatalf("Size #%d: unexpected byte size - got %d, "+
 147                                 "want %d", i, gotSize, expectedSize)
 148                 }
 149         }
 150
 151         // Ensure the all keys are iterated by ForEach in order.
 152         var numIterated int
 153         testTreap.ForEach(func(k, v []byte) bool {
 154                 wantKey := serializeUint32(uint32(numIterated))
 155
 156                 // Ensure the key is as expected.
 157                 if !bytes.Equal(k, wantKey) {
 158                         t.Fatalf("ForEach #%d: unexpected key - got %x, want %x",
 159                                 numIterated, k, wantKey)
 160                 }
 161
 162                 // Ensure the value is as expected.
 163                 if !bytes.Equal(v, wantKey) {
 164                         t.Fatalf("ForEach #%d: unexpected value - got %x, want %x",
 165                                 numIterated, v, wantKey)
 166                 }
 167
 168                 numIterated++
 169                 return true
 170         })
 171
 172         // Ensure all items were iterated.
 173         if numIterated != numItems {
 174                 t.Fatalf("ForEach: unexpected iterate count - got %d, want %d",
 175                         numIterated, numItems)
 176         }
 177
 178         // Delete the keys one-by-one while checking several of the treap
 179         // functions work as expected.
 180         for i := 0; i < numItems; i++ {
 181                 key := serializeUint32(uint32(i))
 182                 testTreap.Delete(key)
 183
 184                 // Ensure the treap length is the expected value.
 185                 if gotLen := testTreap.Len(); gotLen != numItems-i-1 {
 186                         t.Fatalf("Len #%d: unexpected length - got %d, want %d",
 187                                 i, gotLen, numItems-i-1)
 188                 }
 189
 190                 // Ensure the treap no longer has the key.
 191                 if testTreap.Has(key) {
 192                         t.Fatalf("Has #%d: key %q is in treap", i, key)
 193                 }
 194
 195                 // Get the key that no longer exists from the treap and ensure
 196                 // it is nil.
 197                 if gotVal := testTreap.Get(key); gotVal != nil {
 198                         t.Fatalf("Get #%d: unexpected value - got %x, want nil",
 199                                 i, gotVal)
 200                 }
 201
 202                 // Ensure the expected size is reported.
 203                 expectedSize -= (nodeFieldsSize + 8)
 204                 if gotSize := testTreap.Size(); gotSize != expectedSize {
 205                         t.Fatalf("Size #%d: unexpected byte size - got %d, "+
 206                                 "want %d", i, gotSize, expectedSize)
 207                 }
 208         }
 209 }
 210
 211 // TestMutableReverseSequential ensures that putting keys into a mutable treap
 212 // in reverse sequential order works as expected.
 213 func TestMutableReverseSequential(t *testing.T) {
 214         t.Parallel()
 215
 216         // Insert a bunch of sequential keys while checking several of the treap
 217         // functions work as expected.
 218         expectedSize := uint64(0)
 219         numItems := 1000
 220         testTreap := NewMutable()
 221         for i := 0; i < numItems; i++ {
 222                 key := serializeUint32(uint32(numItems - i - 1))
 223                 testTreap.Put(key, key)
 224
 225                 // Ensure the treap length is the expected value.
 226                 if gotLen := testTreap.Len(); gotLen != i+1 {
 227                         t.Fatalf("Len #%d: unexpected length - got %d, want %d",
 228                                 i, gotLen, i+1)
 229                 }
 230
 231                 // Ensure the treap has the key.
 232                 if !testTreap.Has(key) {
 233                         t.Fatalf("Has #%d: key %q is not in treap", i, key)
 234                 }
 235
 236                 // Get the key from the treap and ensure it is the expected
 237                 // value.
 238                 if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
 239                         t.Fatalf("Get #%d: unexpected value - got %x, want %x",
 240                                 i, gotVal, key)
 241                 }
 242
 243                 // Ensure the expected size is reported.
 244                 expectedSize += (nodeFieldsSize + 8)
 245                 if gotSize := testTreap.Size(); gotSize != expectedSize {
 246                         t.Fatalf("Size #%d: unexpected byte size - got %d, "+
 247                                 "want %d", i, gotSize, expectedSize)
 248                 }
 249         }
 250
 251         // Ensure the all keys are iterated by ForEach in order.
 252         var numIterated int
 253         testTreap.ForEach(func(k, v []byte) bool {
 254                 wantKey := serializeUint32(uint32(numIterated))
 255
 256                 // Ensure the key is as expected.
 257                 if !bytes.Equal(k, wantKey) {
 258                         t.Fatalf("ForEach #%d: unexpected key - got %x, want %x",
 259                                 numIterated, k, wantKey)
 260                 }
 261
 262                 // Ensure the value is as expected.
 263                 if !bytes.Equal(v, wantKey) {
 264                         t.Fatalf("ForEach #%d: unexpected value - got %x, want %x",
 265                                 numIterated, v, wantKey)
 266                 }
 267
 268                 numIterated++
 269                 return true
 270         })
 271
 272         // Ensure all items were iterated.
 273         if numIterated != numItems {
 274                 t.Fatalf("ForEach: unexpected iterate count - got %d, want %d",
 275                         numIterated, numItems)
 276         }
 277
 278         // Delete the keys one-by-one while checking several of the treap
 279         // functions work as expected.
 280         for i := 0; i < numItems; i++ {
 281                 // Intentionally use the reverse order they were inserted here.
 282                 key := serializeUint32(uint32(i))
 283                 testTreap.Delete(key)
 284
 285                 // Ensure the treap length is the expected value.
 286                 if gotLen := testTreap.Len(); gotLen != numItems-i-1 {
 287                         t.Fatalf("Len #%d: unexpected length - got %d, want %d",
 288                                 i, gotLen, numItems-i-1)
 289                 }
 290
 291                 // Ensure the treap no longer has the key.
 292                 if testTreap.Has(key) {
 293                         t.Fatalf("Has #%d: key %q is in treap", i, key)
 294                 }
 295
 296                 // Get the key that no longer exists from the treap and ensure
 297                 // it is nil.
 298                 if gotVal := testTreap.Get(key); gotVal != nil {
 299                         t.Fatalf("Get #%d: unexpected value - got %x, want nil",
 300                                 i, gotVal)
 301                 }
 302
 303                 // Ensure the expected size is reported.
 304                 expectedSize -= (nodeFieldsSize + 8)
 305                 if gotSize := testTreap.Size(); gotSize != expectedSize {
 306                         t.Fatalf("Size #%d: unexpected byte size - got %d, "+
 307                                 "want %d", i, gotSize, expectedSize)
 308                 }
 309         }
 310 }
 311
 312 // TestMutableUnordered ensures that putting keys into a mutable treap in no
 313 // paritcular order works as expected.
 314 func TestMutableUnordered(t *testing.T) {
 315         t.Parallel()
 316
 317         // Insert a bunch of out-of-order keys while checking several of the
 318         // treap functions work as expected.
 319         expectedSize := uint64(0)
 320         numItems := 1000
 321         testTreap := NewMutable()
 322         for i := 0; i < numItems; i++ {
 323                 // Hash the serialized int to generate out-of-order keys.
 324                 hash := sha256.Sum256(serializeUint32(uint32(i)))
 325                 key := hash[:]
 326                 testTreap.Put(key, key)
 327
 328                 // Ensure the treap length is the expected value.
 329                 if gotLen := testTreap.Len(); gotLen != i+1 {
 330                         t.Fatalf("Len #%d: unexpected length - got %d, want %d",
 331                                 i, gotLen, i+1)
 332                 }
 333
 334                 // Ensure the treap has the key.
 335                 if !testTreap.Has(key) {
 336                         t.Fatalf("Has #%d: key %q is not in treap", i, key)
 337                 }
 338
 339                 // Get the key from the treap and ensure it is the expected
 340                 // value.
 341                 if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
 342                         t.Fatalf("Get #%d: unexpected value - got %x, want %x",
 343                                 i, gotVal, key)
 344                 }
 345
 346                 // Ensure the expected size is reported.
 347                 expectedSize += nodeFieldsSize + uint64(len(key)+len(key))
 348                 if gotSize := testTreap.Size(); gotSize != expectedSize {
 349                         t.Fatalf("Size #%d: unexpected byte size - got %d, "+
 350                                 "want %d", i, gotSize, expectedSize)
 351                 }
 352         }
 353
 354         // Delete the keys one-by-one while checking several of the treap
 355         // functions work as expected.
 356         for i := 0; i < numItems; i++ {
 357                 // Hash the serialized int to generate out-of-order keys.
 358                 hash := sha256.Sum256(serializeUint32(uint32(i)))
 359                 key := hash[:]
 360                 testTreap.Delete(key)
 361
 362                 // Ensure the treap length is the expected value.
 363                 if gotLen := testTreap.Len(); gotLen != numItems-i-1 {
 364                         t.Fatalf("Len #%d: unexpected length - got %d, want %d",
 365                                 i, gotLen, numItems-i-1)
 366                 }
 367
 368                 // Ensure the treap no longer has the key.
 369                 if testTreap.Has(key) {
 370                         t.Fatalf("Has #%d: key %q is in treap", i, key)
 371                 }
 372
 373                 // Get the key that no longer exists from the treap and ensure
 374                 // it is nil.
 375                 if gotVal := testTreap.Get(key); gotVal != nil {
 376                         t.Fatalf("Get #%d: unexpected value - got %x, want nil",
 377                                 i, gotVal)
 378                 }
 379
 380                 // Ensure the expected size is reported.
 381                 expectedSize -= (nodeFieldsSize + 64)
 382                 if gotSize := testTreap.Size(); gotSize != expectedSize {
 383                         t.Fatalf("Size #%d: unexpected byte size - got %d, "+
 384                                 "want %d", i, gotSize, expectedSize)
 385                 }
 386         }
 387 }
 388
 389 // TestMutableDuplicatePut ensures that putting a duplicate key into a mutable
 390 // treap updates the existing value.
 391 func TestMutableDuplicatePut(t *testing.T) {
 392         t.Parallel()
 393
 394         key := serializeUint32(0)
 395         val := []byte("testval")
 396
 397         // Put the key twice with the second put being the expected final value.
 398         testTreap := NewMutable()
 399         testTreap.Put(key, key)
 400         testTreap.Put(key, val)
 401
 402         // Ensure the key still exists and is the new value.
 403         if gotVal := testTreap.Has(key); !gotVal {
 404                 t.Fatalf("Has: unexpected result - got %v, want true", gotVal)
 405         }
 406         if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, val) {
 407                 t.Fatalf("Get: unexpected result - got %x, want %x", gotVal, val)
 408         }
 409
 410         // Ensure the expected size is reported.
 411         expectedSize := uint64(nodeFieldsSize + len(key) + len(val))
 412         if gotSize := testTreap.Size(); gotSize != expectedSize {
 413                 t.Fatalf("Size: unexpected byte size - got %d, want %d",
 414                         gotSize, expectedSize)
 415         }
 416 }
 417
 418 // TestMutableNilValue ensures that putting a nil value into a mutable treap
 419 // results in a key being added with an empty byte slice.
 420 func TestMutableNilValue(t *testing.T) {
 421         t.Parallel()
 422
 423         key := serializeUint32(0)
 424
 425         // Put the key with a nil value.
 426         testTreap := NewMutable()
 427         testTreap.Put(key, nil)
 428
 429         // Ensure the key exists and is an empty byte slice.
 430         if gotVal := testTreap.Has(key); !gotVal {
 431                 t.Fatalf("Has: unexpected result - got %v, want true", gotVal)
 432         }
 433         if gotVal := testTreap.Get(key); gotVal == nil {
 434                 t.Fatalf("Get: unexpected result - got nil, want empty slice")
 435         }
 436         if gotVal := testTreap.Get(key); len(gotVal) != 0 {
 437                 t.Fatalf("Get: unexpected result - got %x, want empty slice",
 438                         gotVal)
 439         }
 440 }
 441
 442 // TestMutableForEachStopIterator ensures that returning false from the ForEach
 443 // callback of a mutable treap stops iteration early.
 444 func TestMutableForEachStopIterator(t *testing.T) {
 445         t.Parallel()
 446
 447         // Insert a few keys.
 448         numItems := 10
 449         testTreap := NewMutable()
 450         for i := 0; i < numItems; i++ {
 451                 key := serializeUint32(uint32(i))
 452                 testTreap.Put(key, key)
 453         }
 454
 455         // Ensure ForEach exits early on false return by caller.
 456         var numIterated int
 457         testTreap.ForEach(func(k, v []byte) bool {
 458                 numIterated++
 459                 return numIterated != numItems/2
 460         })
 461         if numIterated != numItems/2 {
 462                 t.Fatalf("ForEach: unexpected iterate count - got %d, want %d",
 463                         numIterated, numItems/2)
 464         }
 465 }