first draft

2 files changed, 193 insertions, 0 deletions

diff --git a/c/cursor.go b/c/cursor.go
new file mode 100644
index 0000000..5874b20
--- /dev/null
+++ b/c/cursor.go
@@ -0,0 +1,138 @@
+package c
+
+/*
+
+#define MAX_DEPTH	100
+#define BRANCH_PAGE	1
+
+// These types MUST have the same layout as their corresponding Go types
+
+typedef unsigned long long	pageid;
+typedef unsigned short		elemid;
+
+typedef struct page {
+	pgid			id;
+	unsigned short	flags;
+	elemid			count;
+	unsigned long	overflow;
+} page;
+
+typedef struct branch_elem {
+	unsigned long	pos;
+	unsigned long	ksize;
+	pgid			pgid;
+} branch_elem;
+
+typedef struct leaf_elem {
+	unsigned long	flags;
+	unsigned long	pos;
+	unsigned long	ksize;
+	unsigned long	vsize;
+} leaf_elem;
+
+// private types
+
+typedef struct elem_ref {
+	void	*element;
+	page	*page;
+	elemid	index;
+} elem_ref;
+
+// public types
+
+typedef struct bolt_val {
+    uint32_t size;
+    void     *data;
+} bolt_val;
+
+typedef struct bolt_cursor {
+	void			*data;
+	pgid			root;
+	size_t			pgsz;
+	elemid[MAX_DEPTH]	stack;
+	unsigned int	stackp;
+} bolt_cursor;
+
+void bolt_cursor_init(bolt_cursor* c, void *data, size_t pgsz, pgid root) {
+	c->data = data;
+	c->pgid = pgid;
+	c->pgsz = pgsz;
+}
+
+// public functions
+
+int bolt_cursor_first(bolt_cursor* c, bolt_val *key, bolt_val *value) {
+	leaf_elem* leaf;
+	elem_ref* ref;
+	c->stackp = 0;
+	ref = &c->stack[c->stackp]
+	ref->page = page(c, c->pgid);
+	ref->index = 0;
+	return next_element(c, key, value);
+}
+
+int bolt_cursor_next(bolt_cursor* c, bolt_val *key, bolt_val *value) {
+	elem_ref* ref= &c->stack[c->stackp];
+	ref->index++;
+	while (ref->index >= ref->page->count ) {
+		c->stackp--;
+		ref = &c->stack[c->stackp];
+		ref->index++;
+	}
+	if(ref->page | BRANCH_PAGE)
+		ref->element += sizeof(branch_elem);
+	else
+		ref->element += sizeof(leaf_elem);
+	return next_element(c, key, value);		
+}
+
+// int bolt_cursor_seek(bolt_cursor* c, bolt_val key, bolt_val *actual_key, bolt_val *value)
+
+
+// private functions
+
+page* page(bolt_cursor* c, pgid id) {
+	return (page*)(c->data + (c->pgsz * id));
+}
+
+branch_elem* branch_page_element(*p, elemid index) {
+	return p + sizeof(page) + index * sizeof(branch_elem);
+}
+
+leaf_elem* leaf_page_element(page* p, elemid index) {
+	return p + sizeof(page) + index * sizeof(leaf_elem);
+}
+
+set_key_value(leaf_elem* leaf, bolt_val* key, bolt_val *value) {
+	key.size = leaf->ksize;
+	key.data = leaf + leaf->pos;
+	value.size = leaf->vsize;
+	value.data = key.data + key.size;	
+}
+
+int next_element(bolt_cursor* c, bolt_val *key, bolt_val *value) {
+	elem_ref* ref = &c->stack[c->stackp];
+	branch_elem* branch;
+	for(ref->page->flags | BRANCH_PAGE) {
+		branch = branch_page_element(ref->page,ref->index);
+		c->stackp++;
+		ref = &c->stack[c->stackp];
+		ref->index = 0;
+		ref->element = branch;
+		ref->page = page(c, branch->pgid);
+	};
+	set_key_value(leaf_page_element(ref->page,ref->index), key, value);
+	return 0
+}
+
+*/
+import "C"
+import "github.com/boltdb/bolt"
+
+func  NewCursor(b *bolt.Bucket) *C.bolt_cursor {
+	data := (*C.void)(&b.tx.db.data[0])]
+	pgsz := (C.size_t)(b.tx.db.pageSize)
+	cursor := new(C.bolt_cursor)
+	C.bolt_cursor_init(cursor, data, pgsz, (C.pgid)(b.root))
+	return cursor
+}
diff --git a/c/cursor_test.go b/c/cursor_test.go
new file mode 100644
index 0000000..7c45346
--- /dev/null
+++ b/c/cursor_test.go
@@ -0,0 +1,55 @@
+package c
+
+import "C"
+import (
+	"github.com/boltdb/bolt"
+	"github.com/stretchr/testify/assert"
+	"testing"
+	"testing/quick"
+)
+
+// Ensure that a cursor can iterate over all elements in a bucket.
+func TestIterate(t *testing.T) {
+	if testing.Short() {
+		t.Skip("skipping test in short mode.")
+	}
+
+	f := func(items testdata) bool {
+		withOpenDB(func(db *DB, path string) {
+			// Bulk insert all values.
+			tx, _ := db.Begin(true)
+			tx.CreateBucket("widgets")
+			b := tx.Bucket("widgets")
+			for _, item := range items {
+				assert.NoError(t, b.Put(item.Key, item.Value))
+			}
+			assert.NoError(t, tx.Commit())
+
+			// Sort test data.
+			sort.Sort(items)
+
+			// Iterate over all items and check consistency.
+			var index = 0
+			tx, _ = db.Begin(false)
+			var k, v C.bolt_val
+			c := NewCursor(tx.Bucket("widgets"))
+			C.bolt_cursor_first(c, &k, &v)
+			key := C.GoBytes(k.data, k.size)
+			for key != nil && index < len(items) {
+				assert.Equal(t, key, items[index].Key)
+				assert.Equal(t, C.GoBytes(v.data, v.size), items[index].Value)
+				index++
+				C.bolt_cursor_next(c, &k, &v)
+				key := C.GoBytes(k.data, k.size)
+			}
+			assert.Equal(t, len(items), index)
+			assert.Equal(t, len(items), index)
+			tx.Rollback()
+		})
+		return true
+	}
+	if err := quick.Check(f, qconfig()); err != nil {
+		t.Error(err)
+	}
+	fmt.Fprint(os.Stderr, "\n")
+}