diff options
| -rw-r--r-- | c/cursor.go | 109 | ||||
| -rw-r--r-- | c/cursor_test.go | 75 |
2 files changed, 180 insertions, 4 deletions
diff --git a/c/cursor.go b/c/cursor.go index 000dd9d..92e93eb 100644 --- a/c/cursor.go +++ b/c/cursor.go @@ -4,6 +4,7 @@ package c #include <stdint.h> #include <stdlib.h> #include <stdio.h> +#include <string.h> #include <inttypes.h> //------------------------------------------------------------------------------ @@ -41,7 +42,7 @@ typedef struct page { typedef struct branch_element { uint32_t pos; uint32_t ksize; - pgid page; + pgid pgid; } branch_element; // The leaf element represents an a item in a leaf page @@ -87,6 +88,11 @@ void cursor_first_leaf(bolt_cursor *c); void cursor_key_value(bolt_cursor *c, bolt_val *key, bolt_val *value, uint32_t *flags); +void cursor_search(bolt_cursor *c, bolt_val key, pgid id); + +void cursor_search_branch(bolt_cursor *c, bolt_val key); + +void cursor_search_leaf(bolt_cursor *c, bolt_val key); //------------------------------------------------------------------------------ // Public Functions @@ -138,6 +144,27 @@ void bolt_cursor_next(bolt_cursor *c, bolt_val *key, bolt_val *value, uint32_t * cursor_key_value(c, key, value, flags); } +// Positions the cursor first leaf element starting from a given key. +// If there is a matching key then the cursor will be place on that key. +// 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_search(c, seek, c->root); + elem_ref *ref = &c->stack[c->top]; + + // If the cursor is pointing to the end of page then return nil. + if (ref->index >= ref->page->count) { + 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); +} + //------------------------------------------------------------------------------ // Private Functions @@ -180,16 +207,76 @@ 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]); - branch_element *branch; while (ref->page->flags & PAGE_BRANCH) { - branch = branch_page_element(ref->page,ref->index); + 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, branch->page); + ref->page = cursor_page(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; + + // If we're on a leaf page/node then find the specific node. + if (ref->page->flags & PAGE_LEAF) { + cursor_search_leaf(c, key); + return; + } + + // Otherwise search the branch page. + cursor_search_branch(c, key); +} + +// 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]; + + // HACK: Simply loop over elements to find the right one. Replace with a binary search. + leaf_element *elems = (leaf_element*)((void*)(ref->page) + sizeof(page)); + for (int i=0; i<ref->page->count; i++) { + leaf_element *elem = &elems[i]; + int rc = memcmp(key.data, ((void*)elem) + elem->pos, (elem->ksize < key.size ? elem->ksize : key.size)); + + // printf("? %.*s | %.*s\n", key.size, key.data, elem->ksize, ((void*)elem) + elem->pos); + // printf("rc=%d; key.size(%d) >= elem->ksize(%d)\n", rc, key.size, elem->ksize); + if (key.size == 0 || (rc == 0 && key.size >= elem->ksize) || rc < 0) { + ref->index = i; + return; + } + } + + // If nothing was matched then move the cursor to the end. + ref->index = ref->page->count; +} + +// 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]; + + // HACK: Simply loop over elements to find the right one. Replace with a binary search. + branch_element *elems = (branch_element*)((void*)(ref->page) + sizeof(page)); + for (int i=0; i<ref->page->count; i++) { + branch_element *elem = &elems[i]; + int rc = memcmp(key.data, ((void*)elem) + elem->pos, (elem->ksize < key.size ? elem->ksize : key.size)); + + if (key.size == 0 || (rc == 0 && key.size >= elem->ksize) || rc < 0) { + ref->index = i; + cursor_search(c, key, elem->pgid); + return; + } + } + + // If nothing was matched then move the cursor to the end. + ref->index = ref->page->count; +} + */ import "C" @@ -233,6 +320,20 @@ func (c *Cursor) Next() (key, value []byte) { return C.GoBytes(k.data, C.int(k.size)), C.GoBytes(v.data, C.int(v.size)) } +// Seek moves the cursor to a given key and returns it. +// If the key does not exist then the next key is used. If no keys +// follow, an empty value is returned. +func (c *Cursor) Seek(seek []byte) (key, value []byte, flags int) { + var _flags C.uint32_t + var _seek, k, v C.bolt_val + if len(seek) > 0 { + _seek.size = C.uint32_t(len(seek)) + _seek.data = unsafe.Pointer(&seek[0]) + } + C.bolt_cursor_seek(c.C, _seek, &k, &v, &_flags) + return C.GoBytes(k.data, C.int(k.size)), C.GoBytes(v.data, C.int(v.size)), int(_flags) +} + func warn(v ...interface{}) { fmt.Fprintln(os.Stderr, v...) } diff --git a/c/cursor_test.go b/c/cursor_test.go index fd0fa1a..560d03c 100644 --- a/c/cursor_test.go +++ b/c/cursor_test.go @@ -28,6 +28,57 @@ func TestCursor_First(t *testing.T) { }) } +// Ensure that a C cursor can seek to the appropriate keys. +func TestCursor_Seek(t *testing.T) { + withDB(func(db *bolt.DB) { + db.Update(func(tx *bolt.Tx) error { + b, err := tx.CreateBucket([]byte("widgets")) + assert.NoError(t, err) + assert.NoError(t, b.Put([]byte("foo"), []byte("0001"))) + assert.NoError(t, b.Put([]byte("bar"), []byte("0002"))) + assert.NoError(t, b.Put([]byte("baz"), []byte("0003"))) + _, err = b.CreateBucket([]byte("bkt")) + assert.NoError(t, err) + return nil + }) + db.View(func(tx *bolt.Tx) error { + c := NewCursor(tx.Bucket([]byte("widgets"))) + + // Exact match should go to the key. + k, v, flags := c.Seek([]byte("bar")) + assert.Equal(t, "bar", string(k)) + assert.Equal(t, "0002", string(v)) + assert.Equal(t, 0, flags) + + // Inexact match should go to the next key. + k, v, flags = c.Seek([]byte("bas")) + assert.Equal(t, "baz", string(k)) + assert.Equal(t, "0003", string(v)) + assert.Equal(t, 0, flags) + + // Low key should go to the first key. + k, v, flags = c.Seek([]byte("")) + assert.Equal(t, "bar", string(k)) + assert.Equal(t, "0002", string(v)) + assert.Equal(t, 0, flags) + + // High key should return no key. + k, v, flags = c.Seek([]byte("zzz")) + assert.Equal(t, "", string(k)) + assert.Equal(t, "", string(v)) + assert.Equal(t, 0, flags) + + // Buckets should return their key but no value. + k, v, flags = c.Seek([]byte("bkt")) + assert.Equal(t, []byte("bkt"), k) + assert.True(t, len(v) > 0) + assert.Equal(t, 1, flags) // bucketLeafFlag + + return nil + }) + }) +} + // Ensure that a C cursor can iterate over a single root with a couple elements. func TestCursor_Iterate_Leaf(t *testing.T) { withDB(func(db *bolt.DB) { @@ -65,6 +116,30 @@ func TestCursor_Iterate_Leaf(t *testing.T) { }) } +// Ensure that a C cursor can iterate over a branches and leafs. +func TestCursor_Iterate_Large(t *testing.T) { + withDB(func(db *bolt.DB) { + db.Update(func(tx *bolt.Tx) error { + b, _ := tx.CreateBucket([]byte("widgets")) + for i := 0; i < 1000; i++ { + b.Put([]byte(fmt.Sprintf("%d", i)), []byte(fmt.Sprintf("%020d", i))) + } + return nil + }) + db.View(func(tx *bolt.Tx) error { + var index int + c := NewCursor(tx.Bucket([]byte("widgets"))) + for k, v := c.First(); len(k) > 0; k, v = c.Next() { + assert.Equal(t, fmt.Sprintf("%d", index), string(k)) + assert.Equal(t, fmt.Sprintf("%020d", index), string(v)) + index++ + } + assert.Equal(t, 1000, index) + return nil + }) + }) +} + // tempfile returns a temporary path. func tempfile() string { f, _ := ioutil.TempFile("", "bolt-c-") |