◄ prev contents next ►

⚠

The web version only has simple instructions since chapter 04, while the full book has detailed explanations and background info.

0402: Iterators

Iterator Interface

To traverse an array, you just move an index. With other data structures, traversal is not that simple. Different structures need different methods. So we need a common interface to traverse KV, usually called an iterator:

func (kv *KV) Seek(key []byte) (*KVIterator, error)
// Is traversal ended?
func (iter *KVIterator) Valid() bool
// Current element
func (iter *KVIterator) Key() []byte
func (iter *KVIterator) Val() []byte
// Move to next/prev element
func (iter *KVIterator) Next() error
func (iter *KVIterator) Prev() error

Usage:

for iter, err = kv.Seek(start); err == nil && iter.Valid(); err = iter.Next() {
    key, val := iter.Key(), iter.Val()
    // ...
}

When this becomes disk-based later, IO errors may occur, so they return error.

Iterator Definition

KVIterator needs to track the current position. For an array, this is just an index:

type KVIterator struct {
    keys [][]byte
    vals [][]byte
    pos  int // position
}

It also keeps references to the slices. If the data structure changes later, this implementation will change completely.

Iterator Implementation

KV.Seek() returns an iterator positioned at the result of binary search on key, that is, the first position where key >= target.

func (kv *KV) Seek(key []byte) (*KVIterator, error) {
    pos, _ := slices.BinarySearchFunc(kv.keys, key, bytes.Compare)
    return &KVIterator{keys: kv.keys, vals: kv.vals, pos: pos}, nil
}

This position may be out of range, so check with Valid() before use:

func (iter *KVIterator) Valid() bool {
    return 0 <= iter.pos && iter.pos < len(iter.keys)
}
func (iter *KVIterator) Key() []byte { return iter.keys[iter.pos] }
func (iter *KVIterator) Val() []byte { return iter.vals[iter.pos] }

Positions -1 and len(keys) mean out of range. With this design, moving one step back when out of range can return to range.

func (iter *KVIterator) Next() error {
    if iter.pos < len(iter.keys) {
        iter.pos++
    }
    return nil
}
func (iter *KVIterator) Prev() error {
    if iter.pos >= 0 {
        iter.pos--
    }
    return nil
}

ⓘ

CodeCrafters.io has similar courses in many programming languages, including build your own Redis, SQLite, Docker, etc. It’s worth checking out.

◄ prev contents next ►