diff options
Diffstat (limited to 'c/cursor.go')
| -rw-r--r-- | c/cursor.go | 334 |
1 files changed, 245 insertions, 89 deletions
diff --git a/c/cursor.go b/c/cursor.go index 73c5269..92e93eb 100644 --- a/c/cursor.go +++ b/c/cursor.go @@ -4,139 +4,279 @@ package c #include <stdint.h> #include <stdlib.h> #include <stdio.h> +#include <string.h> #include <inttypes.h> +//------------------------------------------------------------------------------ +// Constants +//------------------------------------------------------------------------------ + +// This represents the maximum number of levels that a cursor can traverse. #define MAX_DEPTH 100 -#define BRANCH_PAGE 1 + +// These flags mark the type of page and are set in the page.flags. +#define PAGE_BRANCH 0x01 +#define PAGE_LEAF 0x02 +#define PAGE_META 0x04 +#define PAGE_FREELIST 0x10 + + +//------------------------------------------------------------------------------ +// Typedefs +//------------------------------------------------------------------------------ // These types MUST have the same layout as their corresponding Go types typedef int64_t pgid; +// Page represents a header struct of a block in the mmap. typedef struct page { - pgid id; - uint16_t flags; - uint16_t count; - uint32_t overflow; + pgid id; + uint16_t flags; + uint16_t count; + uint32_t overflow; } page; -typedef struct branch_elem { - uint32_t pos; - uint32_t ksize; - pgid page; -} branch_elem; - -typedef struct leaf_elem { - uint32_t flags; - uint32_t pos; - uint32_t ksize; - uint32_t vsize; -} leaf_elem; - -// private types - +// The branch element represents an a item in a branch page +// that points to a child page. +typedef struct branch_element { + uint32_t pos; + uint32_t ksize; + pgid pgid; +} branch_element; + +// The leaf element represents an a item in a leaf page +// that points to a key/value pair. +typedef struct leaf_element { + uint32_t flags; + uint32_t pos; + uint32_t ksize; + uint32_t vsize; +} leaf_element; + +// elem_ref represents a pointer to an element inside of a page. +// It is used by the cursor stack to track the position at each level. typedef struct elem_ref { - page *page; - uint16_t index; + page *page; + uint16_t index; } elem_ref; -// public types - +// bolt_val represents a pointer to a fixed-length series of bytes. +// It is used to represent keys and values returned by the cursor. typedef struct bolt_val { uint32_t size; void *data; } bolt_val; +// bolt_cursor represents a cursor attached to a bucket. typedef struct bolt_cursor { - void *data; - pgid root; - size_t pgsz; - unsigned int stackp; - elem_ref stack[MAX_DEPTH]; + void *data; + pgid root; + size_t pgsz; + int top; + elem_ref stack[MAX_DEPTH]; } bolt_cursor; -// int bolt_cursor_seek(bolt_cursor *c, bolt_val *key, bolt_val *actual_key, bolt_val *value) +//------------------------------------------------------------------------------ +// Forward Declarations +//------------------------------------------------------------------------------ + +page *cursor_page(bolt_cursor *c, pgid id); + +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 +//------------------------------------------------------------------------------ + +// Initializes a cursor. +void bolt_cursor_init(bolt_cursor *c, void *data, size_t pgsz, pgid root) { + c->data = data; + c->root = root; + c->pgsz = pgsz; +} + +// 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; + + // Find first leaf and return key/value. + cursor_first_leaf(c); + cursor_key_value(c, key, value, flags); +} + +// 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) { + // 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 (int i = c->top; i >= 0; i--) { + elem_ref *elem = &c->stack[i]; + if (elem->index < elem->page->count - 1) { + elem->index++; + break; + } + c->top--; + } + + // If we are at the top of the stack then return a blank key/value pair. + if (c->top == -1) { + key->size = value->size = 0; + key->data = value->data = NULL; + *flags = 0; + return; + } + + // Find first leaf and return key/value. + cursor_first_leaf(c); + cursor_key_value(c, key, value, flags); +} -// private functions +// 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 +//------------------------------------------------------------------------------ // Returns a page pointer from a page identifier. -page *get_page(bolt_cursor *c, pgid id) { +page *cursor_page(bolt_cursor *c, pgid id) { return (page *)(c->data + (c->pgsz * id)); } // Returns the leaf element at a given index on a given page. -branch_elem *branch_page_element(page *p, uint16_t index) { - branch_elem *elements = (branch_elem*)((void*)(p) + sizeof(page)); +branch_element *branch_page_element(page *p, uint16_t index) { + branch_element *elements = (branch_element*)((void*)(p) + sizeof(page)); return &elements[index]; } // Returns the leaf element at a given index on a given page. -leaf_elem *leaf_page_element(page *p, uint16_t index) { - leaf_elem *elements = (leaf_elem*)((void*)(p) + sizeof(page)); +leaf_element *page_leaf_element(page *p, uint16_t index) { + leaf_element *elements = (leaf_element*)((void*)(p) + sizeof(page)); return &elements[index]; } -// Sets the key and value for a leaf element to a bolt value. -void key_value(leaf_elem *leaf, bolt_val *key, bolt_val *value) { - key->size = leaf->ksize; - key->data = ((void*)leaf) + leaf->pos; - value->size = leaf->vsize; +// 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]); + leaf_element *elem = page_leaf_element(ref->page,ref->index); + + // Assign key pointer. + key->size = elem->ksize; + key->data = ((void*)elem) + elem->pos; + + // Assign value pointer. + value->size = elem->vsize; value->data = key->data + key->size; + + // Return the element flags. + *flags = elem->flags; } // Traverses from the current stack position down to the first leaf element. -int bolt_cursor_first_leaf(bolt_cursor *c, bolt_val *key, bolt_val *value) { - elem_ref *ref = &(c->stack[c->stackp]); - branch_elem *branch; - while (ref->page->flags & BRANCH_PAGE) { - branch = branch_page_element(ref->page,ref->index); - c->stackp++; - ref = &c->stack[c->stackp]; +void cursor_first_leaf(bolt_cursor *c) { + elem_ref *ref = &(c->stack[c->top]); + 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 = get_page(c, branch->page); + ref->page = cursor_page(c, elem->pgid); }; - key_value(leaf_page_element(ref->page,ref->index), key, value); - return 0; } -// public functions - -void bolt_cursor_init(bolt_cursor *c, void *data, size_t pgsz, pgid root) { - c->data = data; - c->root = root; - c->pgsz = pgsz; -} - -int bolt_cursor_first(bolt_cursor *c, bolt_val *key, bolt_val *value) { - leaf_elem *leaf; - elem_ref *ref; - - // reset stack to initial state - c->stackp = 0; - ref = &(c->stack[c->stackp]); - ref->page = get_page(c, c->root); +// 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; - // get current leaf element - return bolt_cursor_first_leaf(c, key, value); -} + // 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; + } -int bolt_cursor_next(bolt_cursor *c, bolt_val *key, bolt_val *value) { - elem_ref *ref = &c->stack[c->stackp]; + // Otherwise search the branch page. + cursor_search_branch(c, key); +} - // increment element index - ref->index++; - // if we're past last element pop the stack and repeat - while (ref->index >= ref->page->count ) { - c->stackp--; - ref = &c->stack[c->stackp]; - ref->index++; - }; +// 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; +} - // get current leaf element - return bolt_cursor_first_leaf(c, key, value); +// 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" @@ -162,22 +302,38 @@ func NewCursor(b *bolt.Bucket) *Cursor { return c } -// first moves the cursor to the first element and returns the key and value. +// Next moves the cursor to the first element and returns the key and value. // Returns a nil key if there are no elements. -func first(c *Cursor) (key, value []byte) { +func (c *Cursor) First() (key, value []byte) { var k, v C.bolt_val - C.bolt_cursor_first(c.C, &k, &v) + var flags C.uint32_t + C.bolt_cursor_first(c.C, &k, &v, &flags) return C.GoBytes(k.data, C.int(k.size)), C.GoBytes(v.data, C.int(v.size)) } -// next moves the cursor to the next element and returns the key and value. -// Returns a nil key if at the end of the bucket. -func next(c *Cursor) (key, value []byte) { +// Next moves the cursor to the next element and returns the key and value. +// Returns a nil key if there are no more key/value pairs. +func (c *Cursor) Next() (key, value []byte) { var k, v C.bolt_val - C.bolt_cursor_next(c.C, &k, &v) + var flags C.uint32_t + C.bolt_cursor_next(c.C, &k, &v, &flags) 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...) } |