k4: Iterator Prev() method

[guycipher]

Writing some tests it seems as if the iterator method to go backwards on iteration is causing missed keys. Take a look at below test.

func TestIterator(t *testing.T) {
    dir := setup(t)
    defer teardown(dir)

    k4, err := Open(dir, 12196/4, 3000, true, false)
    if err != nil {
        t.Fatalf("Failed to open K4: %v", err)
    }

    for i := 0; i < 500; i++ {
        key := []byte("key" + fmt.Sprintf("%d", i))
        value := []byte("value" + fmt.Sprintf("%d", i))

        err = k4.Put(key, value, nil)
        if err != nil {
            k4.Close()
            t.Fatalf("Failed to put key-value: %v", err)
        }
    }

    k4.Close()

    k4, err = Open(dir, 1024*1024, 2, false, false)
    if err != nil {
        t.Fatalf("Failed to reopen K4: %v", err)
    }
    defer k4.Close()

    // add more keys to also populate the memtable
    for i := 500; i < 510; i++ {
        key := []byte("key" + fmt.Sprintf("%d", i))
        value := []byte("value" + fmt.Sprintf("%d", i))

        err = k4.Put(key, value, nil)
        if err != nil {
            t.Fatalf("Failed to put key-value: %v", err)
        }
    }

    it := NewIterator(k4)

    expectedKeys := make(map[string]bool)

    for i := 0; i < 510; i++ {
        key := []byte("key" + fmt.Sprintf("%d", i))
        expectedKeys[string(key)] = true
    }

    // Iterate forward
    for {
        key, _ := it.Next()
        if key == nil {
            break
        }

        if !expectedKeys[string(key)] {
            t.Fatalf("Unexpected key %s", key)
        }
        expectedKeys[string(key)] = false
    }

    // Now we go backwards and mark the keys we find true
    for {
        key, _ := it.Prev()
        if key == nil {
            break
        }

        if expectedKeys[string(key)] {
            t.Fatalf("Unexpected key %s", key)
        }
        expectedKeys[string(key)] = true
    }

    // Verify all keys are true
    for k, v := range expectedKeys {
        if !v {
            t.Fatalf("Expected key not found %s", k)
        }
    }
}

=== RUN   TestIterator
    k4_test.go:305: Expected key not found key500
--- FAIL: TestIterator (0.06s)

The expectation here is once we iterate over all keys in memtables and sstables tables, we should be able to then do the same loop as we did to get all keys again but go backwards.

[guycipher]

Figured it out. Coming next commit.

[guycipher]

Corrected: https://github.com/guycipher/k4/releases/tag/v1.9.3