Spaces:
Running
Running
File size: 2,379 Bytes
b110593 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
// _ _
// __ _____ __ ___ ___ __ _| |_ ___
// \ \ /\ / / _ \/ _` \ \ / / |/ _` | __/ _ \
// \ V V / __/ (_| |\ V /| | (_| | || __/
// \_/\_/ \___|\__,_| \_/ |_|\__,_|\__\___|
//
// Copyright © 2016 - 2024 Weaviate B.V. All rights reserved.
//
// CONTACT: [email protected]
//
package lsmkv
import (
"bytes"
"github.com/weaviate/weaviate/entities/lsmkv"
)
type memtableCursorMap struct {
data []*binarySearchNodeMap
current int
lock func()
unlock func()
}
func (m *Memtable) newMapCursor() innerCursorMap {
// This cursor is a really primitive approach, it actually requires
// flattening the entire memtable - even if the cursor were to point to the
// very last element. However, given that the memtable will on average be
// only half it's max capacity and even that is relatively small, we might
// get away with the full-flattening and a linear search. Let's not optimize
// prematurely.
m.RLock()
defer m.RUnlock()
data := m.keyMap.flattenInOrder()
return &memtableCursorMap{
data: data,
lock: m.RLock,
unlock: m.RUnlock,
}
}
func (c *memtableCursorMap) first() ([]byte, []MapPair, error) {
c.lock()
defer c.unlock()
if len(c.data) == 0 {
return nil, nil, lsmkv.NotFound
}
c.current = 0
// there is no key-level tombstone, only individual values can have
// tombstones
return c.data[c.current].key, c.data[c.current].values, nil
}
func (c *memtableCursorMap) seek(key []byte) ([]byte, []MapPair, error) {
c.lock()
defer c.unlock()
pos := c.posLargerThanEqual(key)
if pos == -1 {
return nil, nil, lsmkv.NotFound
}
c.current = pos
// there is no key-level tombstone, only individual values can have
// tombstones
return c.data[pos].key, c.data[pos].values, nil
}
func (c *memtableCursorMap) posLargerThanEqual(key []byte) int {
for i, node := range c.data {
if bytes.Compare(node.key, key) >= 0 {
return i
}
}
return -1
}
func (c *memtableCursorMap) next() ([]byte, []MapPair, error) {
c.lock()
defer c.unlock()
c.current++
if c.current >= len(c.data) {
return nil, nil, lsmkv.NotFound
}
// there is no key-level tombstone, only individual values can have
// tombstones
return c.data[c.current].key, c.data[c.current].values, nil
}
|