idx_binary_search_test.go 2.2 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758
  1. package storage
  2. import (
  3. "os"
  4. "testing"
  5. "github.com/seaweedfs/seaweedfs/weed/storage/idx"
  6. "github.com/seaweedfs/seaweedfs/weed/storage/needle"
  7. "github.com/seaweedfs/seaweedfs/weed/storage/super_block"
  8. "github.com/seaweedfs/seaweedfs/weed/storage/types"
  9. "github.com/stretchr/testify/assert"
  10. )
  11. func TestFirstInvalidIndex(t *testing.T) {
  12. dir := t.TempDir()
  13. v, err := NewVolume(dir, dir, "", 1, NeedleMapInMemory, &super_block.ReplicaPlacement{}, &needle.TTL{}, 0, 0, 0)
  14. if err != nil {
  15. t.Fatalf("volume creation: %v", err)
  16. }
  17. type WriteInfo struct {
  18. offset int64
  19. size int32
  20. }
  21. // initialize 20 needles then update first 10 needles
  22. for i := 1; i <= 30; i++ {
  23. n := newRandomNeedle(uint64(i))
  24. n.Flags = 0x08
  25. _, _, _, err := v.writeNeedle2(n, true, false)
  26. if err != nil {
  27. t.Fatalf("write needle %d: %v", i, err)
  28. }
  29. }
  30. b, err := os.ReadFile(v.IndexFileName() + ".idx")
  31. // base case every record is valid -> nothing is filtered
  32. index, err := idx.FirstInvalidIndex(b, func(key types.NeedleId, offset types.Offset, size types.Size) (bool, error) {
  33. return true, nil
  34. })
  35. if err != nil {
  36. t.Fatalf("failed to complete binary search %v", err)
  37. }
  38. assert.Equal(t, 30, index, "when every record is valid nothing should be filtered from binary search")
  39. index, err = idx.FirstInvalidIndex(b, func(key types.NeedleId, offset types.Offset, size types.Size) (bool, error) {
  40. return false, nil
  41. })
  42. assert.Equal(t, 0, index, "when every record is invalid everything should be filtered from binary search")
  43. index, err = idx.FirstInvalidIndex(b, func(key types.NeedleId, offset types.Offset, size types.Size) (bool, error) {
  44. return key < 20, nil
  45. })
  46. // needle key range from 1 to 30 so < 20 means 19 keys are valid and cutoff the bytes at 19 * 16 = 304
  47. assert.Equal(t, 19, index, "when every record is invalid everything should be filtered from binary search")
  48. index, err = idx.FirstInvalidIndex(b, func(key types.NeedleId, offset types.Offset, size types.Size) (bool, error) {
  49. return key <= 1, nil
  50. })
  51. // needle key range from 1 to 30 so <=1 1 means 1 key is valid and cutoff the bytes at 1 * 16 = 16
  52. assert.Equal(t, 1, index, "when every record is invalid everything should be filtered from binary search")
  53. }