aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--c/cursor.go334
-rw-r--r--c/cursor_test.go227
-rw-r--r--c/doc.go4
-rw-r--r--c/quick_test.go77
-rw-r--r--cursor_test.go10
5 files changed, 394 insertions, 258 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...)
}
diff --git a/c/cursor_test.go b/c/cursor_test.go
index 8d40d8d..560d03c 100644
--- a/c/cursor_test.go
+++ b/c/cursor_test.go
@@ -1,129 +1,182 @@
-package c
+package c_test
import (
"fmt"
"io/ioutil"
"os"
- "sort"
"testing"
- "testing/quick"
"github.com/boltdb/bolt"
+ . "github.com/boltdb/bolt/c"
"github.com/stretchr/testify/assert"
)
-// Test when cursor hits the end
-// Implement seek; binary search within the page (branch page and element page)
+// Ensure that the C cursor can
+func TestCursor_First(t *testing.T) {
+ withDB(func(db *bolt.DB) {
+ db.Update(func(tx *bolt.Tx) error {
+ b, _ := tx.CreateBucket([]byte("widgets"))
+ return b.Put([]byte("foo"), []byte("barz"))
+ })
+ db.View(func(tx *bolt.Tx) error {
+ c := NewCursor(tx.Bucket([]byte("widgets")))
+ key, value := c.First()
+ assert.Equal(t, []byte("foo"), key)
+ assert.Equal(t, []byte("barz"), value)
+ return nil
+ })
+ })
+}
-// Ensure that a cursor can get the first element of a bucket.
-func TestCursorFirst(t *testing.T) {
- withOpenDB(func(db *bolt.DB, path string) {
+// 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) {
+ db.Update(func(tx *bolt.Tx) error {
+ tx.CreateBucket([]byte("widgets"))
+ tx.Bucket([]byte("widgets")).Put([]byte("baz"), []byte{})
+ tx.Bucket([]byte("widgets")).Put([]byte("foo"), []byte{0})
+ tx.Bucket([]byte("widgets")).Put([]byte("bar"), []byte{1})
+ return nil
+ })
+ db.View(func(tx *bolt.Tx) error {
+ c := NewCursor(tx.Bucket([]byte("widgets")))
- // Bulk insert all values.
- tx, _ := db.Begin(true)
- b, _ := tx.CreateBucket(toBytes("widgets"))
- assert.NoError(t, b.Put(toBytes("foo"), toBytes("barz")))
- assert.NoError(t, tx.Commit())
+ k, v := c.First()
+ assert.Equal(t, string(k), "bar")
+ assert.Equal(t, []byte{1}, v)
- // Get first and check consistency
- tx, _ = db.Begin(false)
- c := NewCursor(tx.Bucket(toBytes("widgets")))
- key, value := first(c)
- assert.Equal(t, key, toBytes("foo"))
- assert.Equal(t, value, toBytes("barz"))
+ k, v = c.Next()
+ assert.Equal(t, string(k), "baz")
+ assert.Equal(t, []byte{}, v)
- tx.Rollback()
+ k, v = c.Next()
+ assert.Equal(t, string(k), "foo")
+ assert.Equal(t, []byte{0}, v)
+
+ k, v = c.Next()
+ assert.Equal(t, []byte{}, k)
+ assert.Equal(t, []byte{}, v)
+
+ k, v = c.Next()
+ assert.Equal(t, []byte{}, k)
+ assert.Equal(t, []byte{}, v)
+ return nil
+ })
})
}
-// 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 *bolt.DB, path string) {
- // Bulk insert all values.
- tx, _ := db.Begin(true)
- b, _ := tx.CreateBucket(toBytes("widgets"))
- for _, item := range items {
- assert.NoError(t, b.Put(item.Key, item.Value))
+// 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)))
}
- 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)
- c := NewCursor(tx.Bucket(toBytes("widgets")))
- for key, value := first(c); key != nil && index < len(items); key, value = next(c) {
- assert.Equal(t, key, items[index].Key)
- assert.Equal(t, value, items[index].Value)
+ 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, len(items), index)
- assert.Equal(t, len(items), index)
- tx.Rollback()
+ assert.Equal(t, 1000, index)
+ return nil
})
- return true
- }
- if err := quick.Check(f, qconfig()); err != nil {
- t.Error(err)
- }
- fmt.Fprint(os.Stderr, "\n")
-}
-
-// toBytes converts a string to an array of bytes.
-func toBytes(s string) []byte {
- return []byte(s)
+ })
}
-// withTempPath executes a function with a database reference.
-func withTempPath(fn func(string)) {
- f, _ := ioutil.TempFile("", "bolt-")
- path := f.Name()
+// tempfile returns a temporary path.
+func tempfile() string {
+ f, _ := ioutil.TempFile("", "bolt-c-")
f.Close()
- os.Remove(path)
- defer os.RemoveAll(path)
-
- fn(path)
+ os.Remove(f.Name())
+ return f.Name()
}
-// withOpenDB executes a function with an already opened database.
-func withOpenDB(fn func(*bolt.DB, string)) {
- withTempPath(func(path string) {
- db, err := bolt.Open(path, 0666)
- if err != nil {
- panic("cannot open db: " + err.Error())
- }
- defer db.Close()
- fn(db, path)
+// withDB executes a function with an already opened database.
+func withDB(fn func(*bolt.DB)) {
+ path := tempfile()
+ db, err := bolt.Open(path, 0666)
+ if err != nil {
+ panic("cannot open db: " + err.Error())
+ }
+ defer os.Remove(path)
+ defer db.Close()
- // Log statistics.
- // if *statsFlag {
- // logStats(db)
- // }
+ fn(db)
- // Check database consistency after every test.
- mustCheck(db)
- })
+ // Check database consistency after every test.
+ mustCheck(db)
}
// mustCheck runs a consistency check on the database and panics if any errors are found.
func mustCheck(db *bolt.DB) {
if err := db.Check(); err != nil {
// Copy db off first.
- db.CopyFile("/tmp/check.db", 0600)
+ var path = tempfile()
+ db.CopyFile(path, 0600)
if errors, ok := err.(bolt.ErrorList); ok {
for _, err := range errors {
- warn(err)
+ fmt.Println(err)
}
}
- warn(err)
- panic("check failure: see /tmp/check.db")
+ fmt.Println(err)
+ panic("check failure: " + path)
}
}
diff --git a/c/doc.go b/c/doc.go
new file mode 100644
index 0000000..cbb98fe
--- /dev/null
+++ b/c/doc.go
@@ -0,0 +1,4 @@
+/*
+Package c provides a C interface to Bolt.
+*/
+package c
diff --git a/c/quick_test.go b/c/quick_test.go
deleted file mode 100644
index 7d87249..0000000
--- a/c/quick_test.go
+++ /dev/null
@@ -1,77 +0,0 @@
-package c
-
-import (
- "bytes"
- "flag"
- "math/rand"
- "reflect"
- "testing/quick"
- "time"
-)
-
-// testing/quick defaults to 5 iterations and a random seed.
-// You can override these settings from the command line:
-//
-// -quick.count The number of iterations to perform.
-// -quick.seed The seed to use for randomizing.
-// -quick.maxitems The maximum number of items to insert into a DB.
-// -quick.maxksize The maximum size of a key.
-// -quick.maxvsize The maximum size of a value.
-//
-
-var qcount, qseed, qmaxitems, qmaxksize, qmaxvsize int
-
-func init() {
- flag.IntVar(&qcount, "quick.count", 5, "")
- flag.IntVar(&qseed, "quick.seed", int(time.Now().UnixNano())%100000, "")
- flag.IntVar(&qmaxitems, "quick.maxitems", 1000, "")
- flag.IntVar(&qmaxksize, "quick.maxksize", 1024, "")
- flag.IntVar(&qmaxvsize, "quick.maxvsize", 1024, "")
- flag.Parse()
- warn("seed:", qseed)
- warnf("quick settings: count=%v, items=%v, ksize=%v, vsize=%v", qcount, qmaxitems, qmaxksize, qmaxvsize)
-}
-
-func qconfig() *quick.Config {
- return &quick.Config{
- MaxCount: qcount,
- Rand: rand.New(rand.NewSource(int64(qseed))),
- }
-}
-
-type testdata []testdataitem
-
-func (t testdata) Len() int { return len(t) }
-func (t testdata) Swap(i, j int) { t[i], t[j] = t[j], t[i] }
-func (t testdata) Less(i, j int) bool { return bytes.Compare(t[i].Key, t[j].Key) == -1 }
-
-func (t testdata) Generate(rand *rand.Rand, size int) reflect.Value {
- n := rand.Intn(qmaxitems-1) + 1
- items := make(testdata, n)
- for i := 0; i < n; i++ {
- item := &items[i]
- item.Key = randByteSlice(rand, 1, qmaxksize)
- item.Value = randByteSlice(rand, 0, qmaxvsize)
- }
- return reflect.ValueOf(items)
-}
-
-type revtestdata []testdataitem
-
-func (t revtestdata) Len() int { return len(t) }
-func (t revtestdata) Swap(i, j int) { t[i], t[j] = t[j], t[i] }
-func (t revtestdata) Less(i, j int) bool { return bytes.Compare(t[i].Key, t[j].Key) == 1 }
-
-type testdataitem struct {
- Key []byte
- Value []byte
-}
-
-func randByteSlice(rand *rand.Rand, minSize, maxSize int) []byte {
- n := rand.Intn(maxSize-minSize) + minSize
- b := make([]byte, n)
- for i := 0; i < n; i++ {
- b[i] = byte(rand.Intn(255))
- }
- return b
-}
diff --git a/cursor_test.go b/cursor_test.go
index 00fc561..fe406bf 100644
--- a/cursor_test.go
+++ b/cursor_test.go
@@ -89,7 +89,7 @@ func TestCursor_EmptyBucketReverse(t *testing.T) {
}
// Ensure that a Tx cursor can iterate over a single root with a couple elements.
-func TestCursor_LeafRoot(t *testing.T) {
+func TestCursor_Iterate_Leaf(t *testing.T) {
withOpenDB(func(db *DB, path string) {
db.Update(func(tx *Tx) error {
tx.CreateBucket([]byte("widgets"))
@@ -192,7 +192,7 @@ func TestCursor_Restart(t *testing.T) {
}
// Ensure that a Tx can iterate over all elements in a bucket.
-func TestCursor_Iterate(t *testing.T) {
+func TestCursor_QuickCheck(t *testing.T) {
f := func(items testdata) bool {
withOpenDB(func(db *DB, path string) {
// Bulk insert all values.
@@ -227,7 +227,7 @@ func TestCursor_Iterate(t *testing.T) {
}
// Ensure that a transaction can iterate over all elements in a bucket in reverse.
-func TestCursor_Iterate_Reverse(t *testing.T) {
+func TestCursor_QuickCheck_Reverse(t *testing.T) {
f := func(items testdata) bool {
withOpenDB(func(db *DB, path string) {
// Bulk insert all values.
@@ -262,7 +262,7 @@ func TestCursor_Iterate_Reverse(t *testing.T) {
}
// Ensure that a Tx cursor can iterate over subbuckets.
-func TestCursor_Iterate_BucketsOnly(t *testing.T) {
+func TestCursor_QuickCheck_BucketsOnly(t *testing.T) {
withOpenDB(func(db *DB, path string) {
db.Update(func(tx *Tx) error {
b, err := tx.CreateBucket([]byte("widgets"))
@@ -289,7 +289,7 @@ func TestCursor_Iterate_BucketsOnly(t *testing.T) {
}
// Ensure that a Tx cursor can reverse iterate over subbuckets.
-func TestCursor_Iterate_BucketsOnly_Reverse(t *testing.T) {
+func TestCursor_QuickCheck_BucketsOnly_Reverse(t *testing.T) {
withOpenDB(func(db *DB, path string) {
db.Update(func(tx *Tx) error {
b, err := tx.CreateBucket([]byte("widgets"))
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-23 05:33:29 +0000