aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--c/cursor.go102
-rw-r--r--c/cursor_test.go40
2 files changed, 101 insertions, 41 deletions
diff --git a/c/cursor.go b/c/cursor.go
index b98211e..e3495b3 100644
--- a/c/cursor.go
+++ b/c/cursor.go
@@ -82,7 +82,11 @@ typedef struct bolt_cursor {
// Forward Declarations
//------------------------------------------------------------------------------
-page *cursor_page(bolt_cursor *c, pgid id);
+elem_ref *cursor_push(bolt_cursor *c, pgid id);
+
+elem_ref *cursor_current(bolt_cursor *c);
+
+elem_ref *cursor_pop(bolt_cursor *c);
void cursor_first_leaf(bolt_cursor *c);
@@ -103,15 +107,13 @@ void bolt_cursor_init(bolt_cursor *c, void *data, size_t pgsz, pgid root) {
c->data = data;
c->root = root;
c->pgsz = pgsz;
+ c->top = -1;
}
// Positions the cursor to the first leaf element and returns the key/value pair.
void bolt_cursor_first(bolt_cursor *c, bolt_val *key, bolt_val *value, uint32_t *flags) {
// reset stack to initial state
- c->top = 0;
- elem_ref *ref = &(c->stack[c->top]);
- ref->page = cursor_page(c, c->root);
- ref->index = 0;
+ elem_ref *ref = cursor_push(c, c->root);
// Find first leaf and return key/value.
cursor_first_leaf(c);
@@ -121,25 +123,23 @@ void bolt_cursor_first(bolt_cursor *c, bolt_val *key, bolt_val *value, uint32_t
// Positions the cursor to the next leaf element and returns the key/value pair.
void bolt_cursor_next(bolt_cursor *c, bolt_val *key, bolt_val *value, uint32_t *flags) {
int i;
+ elem_ref *ref;
// Attempt to move over one element until we're successful.
// Move up the stack as we hit the end of each page in our stack.
- for (i = c->top; i >= 0; i--) {
- elem_ref *elem = &c->stack[i];
- if (elem->index < elem->page->count - 1) {
- elem->index++;
- break;
- }
- c->top--;
- }
+ for (ref = cursor_current(c); ref != NULL; ref = cursor_current(c)) {
+ ref->index++;
+ if (ref->index < ref->page->count) break;
+ cursor_pop(c);
+ };
// If we are at the top of the stack then return a blank key/value pair.
- if (c->top == -1) {
+ if (ref == NULL) {
key->size = value->size = 0;
key->data = value->data = NULL;
*flags = 0;
return;
- }
+ };
// Find first leaf and return key/value.
cursor_first_leaf(c);
@@ -151,17 +151,17 @@ void bolt_cursor_next(bolt_cursor *c, bolt_val *key, bolt_val *value, uint32_t *
// If there not a match then the cursor will be placed on the next key, if available.
void bolt_cursor_seek(bolt_cursor *c, bolt_val seek, bolt_val *key, bolt_val *value, uint32_t *flags) {
// Start from root page/node and traverse to correct page.
- c->top = -1;
+ cursor_push(c, c->root);
cursor_search(c, seek, c->root);
- elem_ref *ref = &c->stack[c->top];
+ elem_ref *ref = cursor_current(c);
// If the cursor is pointing to the end of page then return nil.
- if (ref->index >= ref->page->count) {
+ if (ref == NULL) {
key->size = value->size = 0;
key->data = value->data = NULL;
*flags = 0;
return;
- }
+ };
// Set the key/value for the current position.
cursor_key_value(c, key, value, flags);
@@ -172,13 +172,36 @@ void bolt_cursor_seek(bolt_cursor *c, bolt_val seek, bolt_val *key, bolt_val *va
// Private Functions
//------------------------------------------------------------------------------
-// Returns a page pointer from a page identifier.
-page *cursor_page(bolt_cursor *c, pgid id) {
- return (page *)(c->data + (c->pgsz * id));
+// Push ref to the first element of the page onto the cursor stack
+// If the page is the root page reset the stack to initial state
+elem_ref *cursor_push(bolt_cursor *c, pgid id) {
+ elem_ref *ref;
+ if (id == c->root)
+ c->top = 0;
+ else
+ c->top++;
+ ref = &(c->stack[c->top]);
+ ref->page = (page *)(c->data + (c->pgsz * id));
+ ref->index = 0;
+ return ref;
+}
+
+// Return current element ref from the cursor stack
+// If stack is empty return null
+elem_ref *cursor_current(bolt_cursor *c) {
+ if (c->top < 0) return NULL;
+ return &c->stack[c->top];
+}
+
+// Pop current element ref off the cursor stack
+elem_ref *cursor_pop(bolt_cursor *c) {
+ elem_ref *ref = cursor_current(c);
+ if (ref != NULL) c->top--;
+ return ref;
}
// Returns the branch element at a given index on a given page.
-branch_element *branch_page_element(page *p, uint16_t index) {
+branch_element *page_branch_element(page *p, uint16_t index) {
branch_element *elements = (branch_element*)((void*)(p) + sizeof(page));
return &elements[index];
}
@@ -191,7 +214,7 @@ leaf_element *page_leaf_element(page *p, uint16_t index) {
// Returns the key/value pair for the current position of the cursor.
void cursor_key_value(bolt_cursor *c, bolt_val *key, bolt_val *value, uint32_t *flags) {
- elem_ref *ref = &(c->stack[c->top]);
+ elem_ref *ref = cursor_current(c);
leaf_element *elem = page_leaf_element(ref->page,ref->index);
// Assign key pointer.
@@ -208,23 +231,17 @@ void cursor_key_value(bolt_cursor *c, bolt_val *key, bolt_val *value, uint32_t *
// Traverses from the current stack position down to the first leaf element.
void cursor_first_leaf(bolt_cursor *c) {
- elem_ref *ref = &(c->stack[c->top]);
+ elem_ref *ref = cursor_current(c);
while (ref->page->flags & PAGE_BRANCH) {
- branch_element *elem = branch_page_element(ref->page,ref->index);
- c->top++;
- ref = &c->stack[c->top];
- ref->index = 0;
- ref->page = cursor_page(c, elem->pgid);
+ branch_element *elem = page_branch_element(ref->page,ref->index);
+ ref = cursor_push(c, elem->pgid);
};
}
// Recursively performs a binary search against a given page/node until it finds a given key.
void cursor_search(bolt_cursor *c, bolt_val key, pgid id) {
// Push page onto the cursor stack.
- c->top++;
- elem_ref *ref = &c->stack[c->top];
- ref->page = cursor_page(c, id);
- ref->index = 0;
+ elem_ref *ref = cursor_push(c, id);
// If we're on a leaf page/node then find the specific node.
if (ref->page->flags & PAGE_LEAF) {
@@ -238,7 +255,7 @@ void cursor_search(bolt_cursor *c, bolt_val key, pgid id) {
// Recursively search over a leaf page for a key.
void cursor_search_leaf(bolt_cursor *c, bolt_val key) {
- elem_ref *ref = &c->stack[c->top];
+ elem_ref *ref = cursor_current(c);
int i;
// HACK: Simply loop over elements to find the right one. Replace with a binary search.
@@ -255,13 +272,13 @@ void cursor_search_leaf(bolt_cursor *c, bolt_val key) {
}
}
- // If nothing was matched then move the cursor to the end.
- ref->index = ref->page->count;
+ // If nothing was matched then pop the current page off the stack.
+ cursor_pop(c);
}
// Recursively search over a branch page for a key.
void cursor_search_branch(bolt_cursor *c, bolt_val key) {
- elem_ref *ref = &c->stack[c->top];
+ elem_ref *ref = cursor_current(c);
int i;
// HACK: Simply loop over elements to find the right one. Replace with a binary search.
@@ -277,8 +294,8 @@ void cursor_search_branch(bolt_cursor *c, bolt_val key) {
}
}
- // If nothing was matched then move the cursor to the end.
- ref->index = ref->page->count;
+ // If nothing was matched then pop the current page off the stack.
+ cursor_pop(c);
}
*/
@@ -335,6 +352,11 @@ func (c *Cursor) Seek(seek []byte) (key, value []byte, flags int) {
_seek.data = unsafe.Pointer(&seek[0])
}
C.bolt_cursor_seek(c.C, _seek, &k, &v, &_flags)
+ //fmt.Printf("Key %v [%v]\n", k.data, k.size)
+ //fmt.Printf("Value %v [%v]\n", k.data, k.size)
+ if k.data == nil {
+ return nil, nil, 0
+ }
return C.GoBytes(k.data, C.int(k.size)), C.GoBytes(v.data, C.int(v.size)), int(_flags)
}
diff --git a/c/cursor_test.go b/c/cursor_test.go
index 5be85de..21b6696 100644
--- a/c/cursor_test.go
+++ b/c/cursor_test.go
@@ -116,7 +116,7 @@ func TestCursor_Iterate_Leaf(t *testing.T) {
})
}
-// Ensure that a C cursor can iterate over a branches and leafs.
+// Ensure that a C cursor can iterate over branches and leafs.
func TestCursor_Iterate_Large(t *testing.T) {
withDB(func(db *bolt.DB) {
db.Update(func(tx *bolt.Tx) error {
@@ -140,6 +140,44 @@ func TestCursor_Iterate_Large(t *testing.T) {
})
}
+// Ensure that a C cursor can seek over branches and leafs.
+func TestCursor_Seek_Large(t *testing.T) {
+ withDB(func(db *bolt.DB) {
+ db.Update(func(tx *bolt.Tx) error {
+ b, _ := tx.CreateBucket([]byte("widgets"))
+ for i := 1; i < 1000; i++ {
+ b.Put([]byte(fmt.Sprintf("%05d", i*10)), []byte(fmt.Sprintf("%020d", i*10)))
+ }
+ return nil
+ })
+ db.View(func(tx *bolt.Tx) error {
+ c := NewCursor(tx.Bucket([]byte("widgets")))
+
+ // Exact match should go to the key.
+ k, v, _ := c.Seek([]byte("05000"))
+ assert.Equal(t, "05000", string(k))
+ assert.Equal(t, fmt.Sprintf("%020d", 5000), string(v))
+
+ // Inexact match should go to the next key.
+ k, v, _ = c.Seek([]byte("07495"))
+ assert.Equal(t, "07500", string(k))
+ assert.Equal(t, fmt.Sprintf("%020d", 7500), string(v))
+
+ // Low key should go to the first key.
+ k, v, _ = c.Seek([]byte("00000"))
+ assert.Equal(t, "00010", string(k))
+ assert.Equal(t, fmt.Sprintf("%020d", 10), string(v))
+
+ // High key should return no key.
+ k, v, _ = c.Seek([]byte("40000"))
+ assert.Equal(t, "", string(k))
+ assert.Equal(t, "", string(v))
+
+ return nil
+ })
+ })
+}
+
// tempfile returns a temporary path.
func tempfile() string {
f, _ := ioutil.TempFile("", "bolt-c-")
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-22 12:59:02 +0000