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