aboutsummaryrefslogtreecommitdiff
path: root/src/dedo.go
diff options
context:
space:
mode:
Diffstat (limited to 'src/dedo.go')
-rw-r--r--src/dedo.go1723
1 files changed, 1007 insertions, 716 deletions
diff --git a/src/dedo.go b/src/dedo.go
index 3850348..2dde5eb 100644
--- a/src/dedo.go
+++ b/src/dedo.go
@@ -1,3 +1,41 @@
+/// Package dedo implements a low-level key/value store in pure Go. It supports
+/// fully serializable transactions, ACID semantics, and lock-free MVCC with
+/// multiple readers and a single writer. Dedo can be used for projects that
+/// want a simple data store without the need to add large dependencies such as
+/// Postgres or MySQL.
+///
+/// Dedo is a single-level, zero-copy, B+tree data store. This means that Dedo
+/// is optimized for fast read access and does not require recovery in the event
+/// of a system crash. Transactions which have not finished committing will
+/// simply be rolled back in the event of a crash.
+///
+/// The design of Dedo is based on Howard Chu's LMDB database project.
+///
+///
+/// == Basics
+///
+/// There are only a few types in Dedo: DB, Bucket, Tx, and Cursor. The DB is
+/// a collection of buckets and is represented by a single file on disk. A
+/// bucket is a collection of unique keys that are associated with values.
+///
+/// Transactions provide either read-only or read-write access to the database.
+/// Read-only transactions can retrieve key/value pairs and can use Cursors to
+/// iterate over the dataset sequentially. Read-write transactions can create
+/// and delete buckets and can insert and remove keys. Only one read-write
+/// transaction is allowed at a time.
+///
+///
+/// == Caveats
+///
+/// The database uses a read-only, memory-mapped data file to ensure that
+/// applications cannot corrupt the database, however, this means that keys and
+/// values returned from Dedo cannot be changed. Writing to a read-only byte
+/// slice will cause Go to panic.
+///
+/// Keys and values retrieved from the database are only valid for the life of
+/// the transaction. When used outside the transaction, these byte slices can
+/// point to different data or can point to invalid memory which will cause a
+/// panic.
package dedo
import (
@@ -24,84 +62,87 @@ import (
type pgid uint64
-// bucket represents the on-file representation of a bucket.
-// This is stored as the "value" of a bucket key. If the bucket is small enough,
-// then its root page can be stored inline in the "value", after the bucket
-// header. In the case of inline buckets, the "root" will be 0.
+/// bucket represents the on-file representation of a bucket. This is stored as
+/// the "value" of a bucket key. If the bucket is small enough, then its root
+/// page can be stored inline in the "value", after the bucket header. In the
+/// case of inline buckets, the "root" will be 0.
type bucket struct {
- root pgid // page id of the bucket's root-level page
- sequence uint64 // monotonically incrementing, used by NextSequence()
+ root pgid /// page id of the bucket's root-level page
+ sequence uint64 /// monotonically incrementing, used by NextSequence()
}
-// Bucket represents a distinct collection of key/value pairs inside the
-// database. Keys aren't unique across different buckets.
+/// Bucket represents a distinct collection of key/value pairs inside the
+/// database. Keys aren't unique across different buckets.
type Bucket struct {
ref *bucket
- tx *Tx // the associated transaction
- buckets map[string]*Bucket // subbucket cache
- page *page // inline page reference
- rootNode *node // materialized node for the root page.
- nodes map[pgid]*node // node cache
-}
-
-// Cursor represents an iterator that can traverse over all key/value pairs in a bucket in sorted order.
-// Cursors see nested buckets with value == nil.
-// Cursors can be obtained from a transaction and are valid as long as the transaction is open.
-//
-// Keys and values returned from the cursor are only valid for the life of the transaction.
-//
-// Changing data while traversing with a cursor may cause it to be invalidated
-// and return unexpected keys and/or values. You must reposition your cursor
-// after mutating data.
+ tx *Tx /// the associated transaction
+ buckets map[string]*Bucket /// subbucket cache
+ page *page /// inline page reference
+ rootNode *node /// materialized node for the root page
+ nodes map[pgid]*node /// node cache
+}
+
+/// Cursor represents an iterator that can traverse over all key/value pairs in
+/// a bucket in sorted order. Cursors see nested buckets with value == nil.
+/// Cursors can be obtained from a transaction and are valid as long as the
+/// transaction is open.
+///
+/// Keys and values returned from the cursor are only valid for the life of the
+/// transaction.
+///
+/// Changing data while traversing with a cursor may cause it to be invalidated
+/// and return unexpected keys and/or values. You must reposition your cursor
+/// after mutating data.
type Cursor struct {
bucket *Bucket
stack []elemRef
}
-// elemRef represents a reference to an element on a given page/node.
+/// elemRef represents a reference to an element on a given page/node.
type elemRef struct {
page *page
node *node
index int
}
-// DB represents a collection of buckets persisted to a file on disk.
-// All data access is performed through transactions which can be obtained through the DB.
-// All the functions on DB will return a ErrDatabaseNotOpen if accessed before Open() is called.
+/// DB represents a collection of buckets persisted to a file on disk. All data
+/// access is performed through transactions which can be obtained through the
+/// DB. All the functions on DB will return a ErrDatabaseNotOpen if accessed
+/// before Open() is called.
type DB struct {
- // When enabled, the database will perform a Check() after every commit.
- // A panic is issued if the database is in an inconsistent state. This
- // flag has a large performance impact so it should only be used for
- // debugging purposes.
+ /// When enabled, the database will perform a Check() after every
+ /// commit. A panic is issued if the database is in an inconsistent
+ /// state. This flag has a large performance impact so it should only
+ /// be used for debugging purposes.
StrictMode bool
- // MaxBatchSize is the maximum size of a batch. Default value is
- // copied from DefaultMaxBatchSize in Open.
- //
- // If <=0, disables batching.
- //
- // Do not change concurrently with calls to Batch.
+ /// MaxBatchSize is the maximum size of a batch. Default value is
+ /// copied from DefaultMaxBatchSize in Open.
+ ///
+ /// If <=0, disables batching.
+ ///
+ /// Do not change concurrently with calls to Batch.
MaxBatchSize int
- // MaxBatchDelay is the maximum delay before a batch starts.
- // Default value is copied from DefaultMaxBatchDelay in Open.
- //
- // If <=0, effectively disables batching.
- //
- // Do not change concurrently with calls to Batch.
+ /// MaxBatchDelay is the maximum delay before a batch starts. Default
+ /// value is copied from DefaultMaxBatchDelay in Open.
+ ///
+ /// If <=0, effectively disables batching.
+ ///
+ /// Do not change concurrently with calls to Batch.
MaxBatchDelay time.Duration
- // AllocSize is the amount of space allocated when the database
- // needs to create new pages. This is done to amortize the cost
- // of truncate() and fsync() when growing the data file.
+ /// AllocSize is the amount of space allocated when the database needs
+ /// to create new pages. This is done to amortize the cost of
+ /// truncate() and fsync() when growing the data file.
AllocSize int
path string
file *os.File
- dataref []byte // mmap'ed read-only via PROT_READ, write throws SEGV
+ dataref []byte /// mmap'ed read-only via PROT_READ, write throws SEGV
data *[maxMapSize]byte
datasz int
- filesz int // current on disk file size
+ filesz int /// current on disk file size
meta0 *meta
meta1 *meta
pageSize int
@@ -115,9 +156,9 @@ type DB struct {
batchMu sync.Mutex
batch *batch
- rwlock sync.Mutex // Allows only one writer at a time.
- metalock sync.Mutex // Protects meta page access.
- mmaplock sync.RWMutex // Protects mmap access during remapping.
+ rwlock sync.Mutex /// Allows only one writer at a time.
+ metalock sync.Mutex /// Protects meta page access.
+ mmaplock sync.RWMutex /// Protects mmap access during remapping.
}
type call struct {
@@ -148,15 +189,16 @@ type meta struct {
checksum uint64
}
-// freelist represents a list of all pages that are available for allocation.
-// It also tracks pages that have been freed but are still in use by open transactions.
+/// freelist represents a list of all pages that are available for allocation.
+/// It also tracks pages that have been freed but are still in use by open
+/// transactions.
type freelist struct {
- ids []pgid // all free and available free page ids.
- pending map[txid][]pgid // mapping of soon-to-be free page ids by tx.
- cache map[pgid]bool // fast lookup of all free and pending page ids.
+ ids []pgid /// all free and available free page ids
+ pending map[txid][]pgid /// mapping of soon-to-be free page ids by tx
+ cache map[pgid]bool /// fast lookup of all free and pending page ids
}
-// node represents an in-memory, deserialized page.
+/// node represents an in-memory, deserialized page.
type node struct {
bucket *Bucket
isLeaf bool
@@ -173,9 +215,9 @@ type nodes []*node
type pages []*page
-// inode represents an internal node inside of a node.
-// It can be used to point to elements in a page or point
-// to an element which hasn't been added to a page yet.
+/// inode represents an internal node inside of a node.
+/// It can be used to point to elements in a page or point
+/// to an element which hasn't been added to a page yet.
type inode struct {
flags uint32
pgid pgid
@@ -193,14 +235,14 @@ type page struct {
ptr uintptr
}
-// branchPageElement represents a node on a branch page.
+/// branchPageElement represents a node on a branch page.
type branchPageElement struct {
pos uint32
ksize uint32
pgid pgid
}
-// leafPageElement represents a node on a leaf page.
+/// leafPageElement represents a node on a leaf page.
type leafPageElement struct {
flags uint32
pos uint32
@@ -208,7 +250,7 @@ type leafPageElement struct {
vsize uint32
}
-// PageInfo represents human readable information about a page.
+/// PageInfo represents human readable information about a page.
type PageInfo struct {
ID int
Type string
@@ -218,17 +260,18 @@ type PageInfo struct {
type pgids []pgid
-// txid represents the internal transaction identifier.
+/// txid represents the internal transaction identifier.
type txid uint64
-// Tx represents a read-only or read/write transaction on the database.
-// Read-only transactions can be used for retrieving values for keys and creating cursors.
-// Read/write transactions can create and remove buckets and create and remove keys.
-//
-// IMPORTANT: You must commit or rollback transactions when you are done with
-// them. Pages can not be reclaimed by the writer until no more transactions
-// are using them. A long running read transaction can cause the database to
-// quickly grow.
+/// Tx represents a read-only or read/write transaction on the database.
+/// Read-only transactions can be used for retrieving values for keys and
+/// creating cursors. Read/write transactions can create and remove buckets
+/// and create and remove keys.
+///
+/// IMPORTANT: You must commit or rollback transactions when you are done with
+/// them. Pages can not be reclaimed by the writer until no more transactions
+/// are using them. A long running read transaction can cause the database to
+/// quickly grow.
type Tx struct {
writable bool
managed bool
@@ -239,9 +282,9 @@ type Tx struct {
commitHandlers []func()
}
-// walkFunc is the type of the function called for keys (buckets and "normal"
-// values) discovered by Walk. keys is the list of keys to descend to the bucket
-// owning the discovered key/value pair k/v.
+/// walkFunc is the type of the function called for keys (buckets and "normal"
+/// values) discovered by Walk. Keys is the list of keys to descend to the
+/// bucket owning the discovered key/value pair k/v.
type walkFunc func(keys [][]byte, k, v []byte, seq uint64) error
type argsT struct{
@@ -263,32 +306,32 @@ type commandT struct{
const (
- // maxMapSize represents the largest mmap size supported by Bolt.
- maxMapSize = 0xFFFFFFFFFFFF // 256TB
+ /// maxMapSize represents the largest mmap size supported by Dedo.
+ maxMapSize = 0xFFFFFFFFFFFF /// 256TB
- // maxAllocSize is the size used when creating array pointers.
+ /// maxAllocSize is the size used when creating array pointers.
maxAllocSize = 0x7FFFFFFF
// FIXME: why?
- // MaxKeySize is the maximum length of a key, in bytes.
+ /// MaxKeySize is the maximum length of a key, in bytes.
MaxKeySize = 32768
// FIXME: why?
- // MaxValueSize is the maximum length of a value, in bytes.
+ /// MaxValueSize is the maximum length of a value, in bytes.
MaxValueSize = (1 << 31) - 2
bucketHeaderSize = int(unsafe.Sizeof(bucket{}))
- // The largest step that can be taken when remapping the mmap.
- maxMmapStep = 1 << 30 // 1GB
+ /// The largest step that can be taken when remapping the mmap.
+ maxMmapStep = 1 << 30 /// 1GB
- // The data file format version.
+ /// The data file format version.
version = 2
- // Represents a marker value to indicate that a file is a Bolt DB.
+ /// Represents a marker value to indicate that a file is a Dedo DB.
magic uint32 = 0xFACADAAB
- // Default values if not set in a DB instance.
+ /// Default values if not set in a DB instance.
DefaultMaxBatchSize int = 1000
DefaultMaxBatchDelay = 10 * time.Millisecond
DefaultAllocSize = 16 * 1024 * 1024
@@ -298,7 +341,7 @@ const (
minKeysPerPage = 2
branchPageElementSize = int(unsafe.Sizeof(branchPageElement{}))
- leafPageElementSize = int(unsafe.Sizeof(leafPageElement{}))
+ leafPageElementSize = int(unsafe.Sizeof(leafPageElement{}))
branchPageFlag = 0x01
leafPageFlag = 0x02
@@ -307,116 +350,125 @@ const (
bucketLeafFlag = 0x01
- // PageHeaderSize represents the size of the bolt.page header.
+ /// PageHeaderSize represents the size of the dedo.page header.
PageHeaderSize = 16
)
var (
- // trySolo is a special sentinel error value used for signaling that a
- // transaction function should be re-run. It should never be seen by
- // callers.
- trySolo = errors.New("batch function returned an error and should be re-run solo")
+ /// trySolo is a special sentinel error value used for signaling that a
+ /// transaction function should be re-run. It should never be seen by
+ /// callers.
+ trySolo = errors.New(
+ "batch function returned an error and should be re-run solo",
+ )
- //
- // These errors can be returned when opening or calling methods on a DB.
- //
+ ///
+ /// These errors can be returned when opening or calling methods on a
+ /// DB.
+ ///
- // ErrDatabaseNotOpen is returned when a DB instance is accessed before it
- // is opened or after it is closed.
+ /// ErrDatabaseNotOpen is returned when a DB instance is accessed before
+ /// it is opened or after it is closed.
ErrDatabaseNotOpen = errors.New("database not open")
- // ErrInvalid is returned when both meta pages on a database are invalid.
- // This typically occurs when a file is not a bolt database.
+ /// ErrInvalid is returned when both meta pages on a database are
+ /// invalid. This typically occurs when a file is not a dedo database.
ErrInvalid = errors.New("invalid database")
- // ErrVersionMismatch is returned when the data file was created with a
- // different version of Bolt.
+ /// ErrVersionMismatch is returned when the data file was created with a
+ /// different version of Dedo.
ErrVersionMismatch = errors.New("version mismatch")
- // ErrChecksum is returned when either meta page checksum does not match.
+ /// ErrChecksum is returned when either meta page checksum does not
+ /// match.
ErrChecksum = errors.New("checksum error")
- //
- // These errors can occur when beginning or committing a Tx.
- //
+ ///
+ /// These errors can occur when beginning or committing a Tx.
+ ///
- // ErrTxNotWritable is returned when performing a write operation on a
- // read-only transaction.
+ /// ErrTxNotWritable is returned when performing a write operation on a
+ /// read-only transaction.
ErrTxNotWritable = errors.New("tx not writable")
- // ErrTxClosed is returned when committing or rolling back a transaction
- // that has already been committed or rolled back.
+ /// ErrTxClosed is returned when committing or rolling back a
+ /// transaction that has already been committed or rolled back.
ErrTxClosed = errors.New("tx closed")
- //
- // These errors can occur when putting or deleting a value or a bucket.
- //
+ ///
+ /// These errors can occur when putting or deleting a value or a bucket.
+ ///
- // ErrBucketNotFound is returned when trying to access a bucket that has
- // not been created yet.
+ /// ErrBucketNotFound is returned when trying to access a bucket that
+ /// has not been created yet.
ErrBucketNotFound = errors.New("bucket not found")
- // ErrBucketExists is returned when creating a bucket that already exists.
+ /// ErrBucketExists is returned when creating a bucket that already
+ /// exists.
ErrBucketExists = errors.New("bucket already exists")
- // ErrBucketNameRequired is returned when creating a bucket with a blank name.
+ /// ErrBucketNameRequired is returned when creating a bucket with a
+ /// blank name.
ErrBucketNameRequired = errors.New("bucket name required")
- // ErrKeyRequired is returned when inserting a zero-length key.
+ /// ErrKeyRequired is returned when inserting a zero-length key.
ErrKeyRequired = errors.New("key required")
- // ErrKeyTooLarge is returned when inserting a key that is larger than MaxKeySize.
+ /// ErrKeyTooLarge is returned when inserting a key that is larger than
+ /// MaxKeySize.
ErrKeyTooLarge = errors.New("key too large")
- // ErrValueTooLarge is returned when inserting a value that is larger than MaxValueSize.
+ /// ErrValueTooLarge is returned when inserting a value that is larger
+ /// than MaxValueSize.
ErrValueTooLarge = errors.New("value too large")
- // ErrIncompatibleValue is returned when trying create or delete a bucket
- // on an existing non-bucket key or when trying to create or delete a
- // non-bucket key on an existing bucket key.
+ /// ErrIncompatibleValue is returned when trying create or delete a
+ /// bucket on an existing non-bucket key or when trying to create or
+ /// delete a non-bucket key on an existing bucket key.
ErrIncompatibleValue = errors.New("incompatible value")
-
- //
- //
- //
-
+ /// ErrMissingKey is returned when the CLI tries to get a key that it
+ /// can't find in the specified bucket.
ErrMissingKey = errors.New("missing key")
- // ErrUsage is returned when a usage message was printed and the process
- // should simply exit with an error.
+ /// ErrUsage is returned when a usage message was printed and the
+ /// process should simply exit with an error.
ErrUsage = errors.New("usage")
- // ErrUnknownCommand is returned when a CLI command is not specified.
+ /// ErrUnknownCommand is returned when a CLI command is not specified.
ErrUnknownCommand = errors.New("unknown command")
- // ErrPathRequired is returned when the path to a Bolt database is not specified.
+ /// ErrPathRequired is returned when the path to a Dedo database is not
+ /// specified.
ErrPathRequired = errors.New("path required")
- // ErrFileNotFound is returned when a Bolt database does not exist.
+ /// ErrFileNotFound is returned when a Dedo database does not exist.
ErrFileNotFound = errors.New("file not found")
- // ErrCorrupt is returned when a checking a data file finds errors.
+ /// ErrCorrupt is returned when a checking a data file finds errors.
ErrCorrupt = errors.New("invalid value")
- // ErrNonDivisibleBatchSize is returned when the batch size can't be evenly
- // divided by the iteration count.
- ErrNonDivisibleBatchSize = errors.New("number of iterations must be divisible by the batch size")
+ /// ErrNonDivisibleBatchSize is returned when the batch size can't be
+ /// evenly divided by the iteration count.
+ ErrNonDivisibleBatchSize = errors.New(
+ "number of iterations must be divisible by the batch size",
+ )
- // ErrPageIDRequired is returned when a required page id is not specified.
+ /// ErrPageIDRequired is returned when a required page id is not
+ /// specified.
ErrPageIDRequired = errors.New("page id required")
)
-// fdatasync flushes written data to a file descriptor.
+/// fdatasync() flushes written data to a file descriptor.
func fdatasync(db *DB) error {
return db.file.Sync()
}
-// flock acquires an advisory lock on a file descriptor.
+/// flock() acquires an advisory lock on a file descriptor.
func flock(db *DB) error {
const lockFlags = syscall.LOCK_EX | syscall.LOCK_NB
@@ -433,22 +485,21 @@ func flock(db *DB) error {
}
}
-// funlock releases an advisory lock on a file descriptor.
+/// funlock() releases an advisory lock on a file descriptor.
func funlock(db *DB) error {
return syscall.Flock(int(db.file.Fd()), syscall.LOCK_UN)
}
-// mmap memory maps a DB's data file.
+/// mmap memory() maps a DB's data file.
func mmap(db *DB, sz int) error {
- // Map the data file to memory.
fd := int(db.file.Fd())
b, err := syscall.Mmap(fd, 0, sz, syscall.PROT_READ, syscall.MAP_SHARED)
if err != nil {
return err
}
- // Advise the kernel that the mmap is accessed randomly.
- if err := madvise(b, syscall.MADV_RANDOM); err != nil {
+ err = madvise(b, syscall.MADV_RANDOM)
+ if err != nil {
return fmt.Errorf("madvise: %s", err)
}
@@ -459,14 +510,12 @@ func mmap(db *DB, sz int) error {
return nil
}
-// munmap unmaps a DB's data file from memory.
+/// munmap() unmaps a DB's data file from memory.
func munmap(db *DB) error {
- // Ignore the unmap if we have no mapped data.
if db.dataref == nil {
return nil
}
- // Unmap using the original byte slice.
err := syscall.Munmap(db.dataref)
db.dataref = nil
db.data = nil
@@ -474,18 +523,22 @@ func munmap(db *DB) error {
return err
}
-// NOTE: This function is copied from stdlib because it is not available on darwin.
func madvise(b []byte, advice int) (err error) {
- _, _, e1 := syscall.Syscall(syscall.SYS_MADVISE, uintptr(unsafe.Pointer(&b[0])), uintptr(len(b)), uintptr(advice))
+ _, _, e1 := syscall.Syscall(
+ syscall.SYS_MADVISE,
+ uintptr(unsafe.Pointer(&b[0])),
+ uintptr(len(b)),
+ uintptr(advice),
+ )
if e1 != 0 {
err = e1
}
return
}
-// newBucket returns a new bucket associated with a transaction.
+/// newBucket() returns a new bucket associated with a transaction.
func newBucket(tx *Tx) Bucket {
- var b = Bucket{tx: tx}
+ b := Bucket{tx: tx}
if tx.writable {
b.buckets = make(map[string]*Bucket)
b.nodes = make(map[pgid]*node)
@@ -493,28 +546,28 @@ func newBucket(tx *Tx) Bucket {
return b
}
-// Writable returns whether the bucket is writable.
+/// Bucket.Writable() returns whether the bucket is writable.
func (b *Bucket) Writable() bool {
return b.tx.writable
}
-// Cursor creates a cursor associated with the bucket.
-// The cursor is only valid as long as the transaction is open.
-// Do not use a cursor after the transaction is closed.
+/// Bucket.Cursor() creates a cursor associated with the bucket. The cursor is
+/// only valid as long as the transaction is open. Do not use a cursor after
+/// the transaction is closed.
func (b *Bucket) Cursor() *Cursor {
- // Allocate and return a cursor.
return &Cursor{
bucket: b,
stack: make([]elemRef, 0),
}
}
-// Bucket retrieves a nested bucket by name.
-// Returns nil if the bucket does not exist.
-// The bucket instance is only valid for the lifetime of the transaction.
+/// Bucket.Bucket() retrieves a nested bucket by name. Returns nil if the
+/// bucket does not exist. The bucket instance is only valid for the lifetime
+/// of the transaction.
func (b *Bucket) Bucket(name []byte) *Bucket {
if b.buckets != nil {
- if child := b.buckets[string(name)]; child != nil {
+ child := b.buckets[string(name)]
+ if child != nil {
return child
}
}
@@ -529,7 +582,7 @@ func (b *Bucket) Bucket(name []byte) *Bucket {
}
// Otherwise create a bucket and cache it.
- var child = b.openBucket(v)
+ child := b.openBucket(v)
if b.buckets != nil {
b.buckets[string(name)] = child
}
@@ -537,13 +590,13 @@ func (b *Bucket) Bucket(name []byte) *Bucket {
return child
}
-// Helper method that re-interprets a sub-bucket value
-// from a parent into a Bucket
+/// Bucket.Helper() method that re-interprets a sub-bucket value from a parent
+/// into a Bucket
func (b *Bucket) openBucket(value []byte) *Bucket {
- var child = newBucket(b.tx)
+ child := newBucket(b.tx)
- // If this is a writable transaction then we need to copy the bucket entry.
- // Read-only transactions can point directly at the mmap entry.
+ // If this is a writable transaction then we need to copy the bucket
+ // entry. Read-only transactions can point directly at the mmap entry.
if b.tx.writable {
child.ref = &bucket{}
*child.ref = *(*bucket)(unsafe.Pointer(&value[0]))
@@ -559,9 +612,10 @@ func (b *Bucket) openBucket(value []byte) *Bucket {
return &child
}
-// CreateBucket creates a new bucket at the given key and returns the new bucket.
-// Returns an error if the key already exists, if the bucket name is blank, or if the bucket name is too long.
-// The bucket instance is only valid for the lifetime of the transaction.
+/// Bucket.CreateBucket() creates a new bucket at the given key and returns the
+/// new bucket. Returns an error if the key already exists, if the bucket name
+/// is blank, or if the bucket name is too long. The bucket instance is only
+/// valid for the lifetime of the transaction.
func (b *Bucket) CreateBucket(key []byte) (*Bucket, error) {
if b.tx.db == nil {
return nil, ErrTxClosed
@@ -584,27 +638,29 @@ func (b *Bucket) CreateBucket(key []byte) (*Bucket, error) {
}
// Create empty, inline bucket.
- var bucket = Bucket{
+ bucket := Bucket{
ref: &bucket{},
rootNode: &node{isLeaf: true},
}
- var value = bucket.write()
+ value := bucket.write()
// Insert into node.
key = cloneBytes(key)
c.node().put(key, key, value, 0, bucketLeafFlag)
// Since subbuckets are not allowed on inline buckets, we need to
- // dereference the inline page, if it exists. This will cause the bucket
- // to be treated as a regular, non-inline bucket for the rest of the tx.
+ // dereference the inline page, if it exists. This will cause the
+ // bucket to be treated as a regular, non-inline bucket for the rest of
+ // the tx.
b.page = nil
return b.Bucket(key), nil
}
-// CreateBucketIfNotExists creates a new bucket if it doesn't already exist and returns a reference to it.
-// Returns an error if the bucket name is blank, or if the bucket name is too long.
-// The bucket instance is only valid for the lifetime of the transaction.
+/// Bucket.CreateBucketIfNotExists() creates a new bucket if it doesn't already
+/// exist and returns a reference to it. Returns an error if the bucket name is
+/// blank, or if the bucket name is too long. The bucket instance is only valid
+/// for the lifetime of the transaction.
func (b *Bucket) CreateBucketIfNotExists(key []byte) (*Bucket, error) {
child, err := b.CreateBucket(key)
if err == ErrBucketExists {
@@ -615,8 +671,8 @@ func (b *Bucket) CreateBucketIfNotExists(key []byte) (*Bucket, error) {
return child, nil
}
-// DeleteBucket deletes a bucket at the given key.
-// Returns an error if the bucket does not exists, or if the key represents a non-bucket value.
+/// Bucket.DeleteBucket() deletes a bucket at the given key. Returns an error
+/// if the bucket does not exists, or if the key represents a non-bucket value.
func (b *Bucket) DeleteBucket(key []byte) error {
if b.tx.db == nil {
return ErrTxClosed
@@ -639,7 +695,8 @@ func (b *Bucket) DeleteBucket(key []byte) error {
child := b.Bucket(key)
err := child.ForEach(func(k, v []byte) error {
if v == nil {
- if err := child.DeleteBucket(k); err != nil {
+ err := child.DeleteBucket(k)
+ if err != nil {
return fmt.Errorf("delete bucket: %s", err)
}
}
@@ -663,9 +720,9 @@ func (b *Bucket) DeleteBucket(key []byte) error {
return nil
}
-// Get retrieves the value for a key in the bucket.
-// Returns a nil value if the key does not exist or if the key is a nested bucket.
-// The returned value is only valid for the life of the transaction.
+/// Bucket.Get() retrieves the value for a key in the bucket. Returns a nil
+/// value if the key does not exist or if the key is a nested bucket. The
+/// returned value is only valid for the life of the transaction.
func (b *Bucket) Get(key []byte) []byte {
k, v, flags := b.Cursor().seek(key)
@@ -674,17 +731,19 @@ func (b *Bucket) Get(key []byte) []byte {
return nil
}
- // If our target node isn't the same key as what's passed in then return nil.
+ // If our target node isn't the same key as what's passed in then return
+ // nil.
if !bytes.Equal(key, k) {
return nil
}
return v
}
-// Put sets the value for a key in the bucket.
-// If the key exist then its previous value will be overwritten.
-// Supplied value must remain valid for the life of the transaction.
-// Returns an error if the bucket was created from a read-only transaction, if the key is blank, if the key is too large, or if the value is too large.
+/// Bucket.Put() sets the value for a key in the bucket. If the key exist then
+/// its previous value will be overwritten. Supplied value must remain valid
+/// for the life of the transaction. Returns an error if the bucket was created
+/// from a read-only transaction, if the key is blank, if the key is too large,
+/// or if the value is too large.
func (b *Bucket) Put(key []byte, value []byte) error {
if b.tx.db == nil {
return ErrTxClosed
@@ -714,9 +773,9 @@ func (b *Bucket) Put(key []byte, value []byte) error {
return nil
}
-// Delete removes a key from the bucket.
-// If the key does not exist then nothing is done and a nil error is returned.
-// Returns an error if the bucket was created from a read-only transaction.
+/// Bucket.Delete() removes a key from the bucket. If the key does not exist
+/// then nothing is done and a nil error is returned. Returns an error if the
+/// bucket was created from a read-only transaction.
func (b *Bucket) Delete(key []byte) error {
if b.tx.db == nil {
return ErrTxClosed
@@ -739,12 +798,13 @@ func (b *Bucket) Delete(key []byte) error {
return nil
}
-// Sequence returns the current integer for the bucket without incrementing it.
+/// Bucket.Sequence() returns the current integer for the bucket without
+/// incrementing it.
func (b *Bucket) Sequence() uint64 {
return b.ref.sequence
}
-// SetSequence updates the sequence number for the bucket.
+/// Bucket.SetSequence() updates the sequence number for the bucket.
func (b *Bucket) SetSequence(v uint64) error {
if b.tx.db == nil {
return ErrTxClosed
@@ -763,7 +823,7 @@ func (b *Bucket) SetSequence(v uint64) error {
return nil
}
-// NextSequence returns an autoincrementing integer for the bucket.
+/// Bucket.NextSequence() returns an autoincrementing integer for the bucket.
func (b *Bucket) NextSequence() (uint64, error) {
if b.tx.db == nil {
return 0, ErrTxClosed
@@ -782,24 +842,26 @@ func (b *Bucket) NextSequence() (uint64, error) {
return b.ref.sequence, nil
}
-// ForEach executes a function for each key/value pair in a bucket.
-// If the provided function returns an error then the iteration is stopped and
-// the error is returned to the caller. The provided function must not modify
-// the bucket; this will result in undefined behavior.
+/// Bucket.ForEach() executes a function for each key/value pair in a bucket.
+/// If the provided function returns an error then the iteration is stopped and
+/// the error is returned to the caller. The provided function must not modify
+/// the bucket; this will result in undefined behavior.
func (b *Bucket) ForEach(fn func(k, v []byte) error) error {
if b.tx.db == nil {
return ErrTxClosed
}
c := b.Cursor()
for k, v := c.First(); k != nil; k, v = c.Next() {
- if err := fn(k, v); err != nil {
+ err := fn(k, v)
+ if err != nil {
return err
}
}
return nil
}
-// forEachPage iterates over every page in a bucket, including inline pages.
+/// Bucket.forEachPage() iterates over every page in a bucket, including inline
+/// pages.
func (b *Bucket) forEachPage(fn func(*page, int)) {
// If we have an inline page then just use that.
if b.page != nil {
@@ -811,8 +873,8 @@ func (b *Bucket) forEachPage(fn func(*page, int)) {
b.tx.forEachPage(b.ref.root, 0, fn)
}
-// forEachPageNode iterates over every page (or node) in a bucket.
-// This also includes inline pages.
+/// Bucket.forEachPageNode() iterates over every page (or node) in a bucket.
+/// This also includes inline pages.
func (b *Bucket) forEachPageNode(fn func(*page, *node, int)) {
// If we have an inline page or root node then just use that.
if b.page != nil {
@@ -822,8 +884,12 @@ func (b *Bucket) forEachPageNode(fn func(*page, *node, int)) {
b._forEachPageNode(b.ref.root, 0, fn)
}
-func (b *Bucket) _forEachPageNode(pgid pgid, depth int, fn func(*page, *node, int)) {
- var p, n = b.pageNode(pgid)
+func (b *Bucket) _forEachPageNode(
+ pgid pgid,
+ depth int,
+ fn func(*page, *node, int),
+) {
+ p, n := b.pageNode(pgid)
// Execute function.
fn(p, n, depth)
@@ -845,25 +911,27 @@ func (b *Bucket) _forEachPageNode(pgid pgid, depth int, fn func(*page, *node, in
}
}
-// spill writes all the nodes for this bucket to dirty pages.
+/// Bucket.spill() writes all the nodes for this bucket to dirty pages.
func (b *Bucket) spill() error {
// Spill all child buckets first.
for name, child := range b.buckets {
- // If the child bucket is small enough and it has no child buckets then
- // write it inline into the parent bucket's page. Otherwise spill it
- // like a normal bucket and make the parent value a pointer to the page.
+ // If the child bucket is small enough and it has no child
+ // buckets then write it inline into the parent bucket's page.
+ // Otherwise spill it like a normal bucket and make the parent
+ // value a pointer to the page.
var value []byte
if child.inlineable() {
child.free()
value = child.write()
} else {
- if err := child.spill(); err != nil {
+ err := child.spill()
+ if err != nil {
return err
}
// Update the child bucket header in this bucket.
value = make([]byte, unsafe.Sizeof(bucket{}))
- var bucket = (*bucket)(unsafe.Pointer(&value[0]))
+ bucket := (*bucket)(unsafe.Pointer(&value[0]))
*bucket = *child.ref
}
@@ -873,15 +941,28 @@ func (b *Bucket) spill() error {
}
// Update parent node.
- var c = b.Cursor()
+ c := b.Cursor()
k, _, flags := c.seek([]byte(name))
if !bytes.Equal([]byte(name), k) {
- panic(fmt.Sprintf("misplaced bucket header: %x -> %x", []byte(name), k))
+ panic(fmt.Sprintf(
+ "misplaced bucket header: %x -> %x",
+ []byte(name),
+ k,
+ ))
}
if flags&bucketLeafFlag == 0 {
- panic(fmt.Sprintf("unexpected bucket header flag: %x", flags))
+ panic(fmt.Sprintf(
+ "unexpected bucket header flag: %x",
+ flags,
+ ))
}
- c.node().put([]byte(name), []byte(name), value, 0, bucketLeafFlag)
+ c.node().put(
+ []byte(name),
+ []byte(name),
+ value,
+ 0,
+ bucketLeafFlag,
+ )
}
// Ignore if there's not a materialized root node.
@@ -890,33 +971,38 @@ func (b *Bucket) spill() error {
}
// Spill nodes.
- if err := b.rootNode.spill(); err != nil {
+ err := b.rootNode.spill()
+ if err != nil {
return err
}
b.rootNode = b.rootNode.root()
// Update the root node for this bucket.
if b.rootNode.pgid >= b.tx.meta.pgid {
- panic(fmt.Sprintf("pgid (%d) above high water mark (%d)", b.rootNode.pgid, b.tx.meta.pgid))
+ panic(fmt.Sprintf(
+ "pgid (%d) above high water mark (%d)",
+ b.rootNode.pgid,
+ b.tx.meta.pgid,
+ ))
}
b.ref.root = b.rootNode.pgid
return nil
}
-// inlineable returns true if a bucket is small enough to be written inline
-// and if it contains no subbuckets. Otherwise returns false.
+/// Bucket.inlineable() returns true if a bucket is small enough to be written
+/// inline and if it contains no subbuckets. Otherwise returns false.
func (b *Bucket) inlineable() bool {
- var n = b.rootNode
+ n := b.rootNode
// Bucket must only contain a single leaf node.
if n == nil || !n.isLeaf {
return false
}
- // Bucket is not inlineable if it contains subbuckets or if it goes beyond
- // our threshold for inline bucket size.
- var size = pageHeaderSize
+ // Bucket is not inlineable if it contains subbuckets or if it goes
+ // beyond our threshold for inline bucket size.
+ size := pageHeaderSize
for _, inode := range n.inodes {
size += leafPageElementSize + len(inode.key) + len(inode.value)
@@ -930,29 +1016,30 @@ func (b *Bucket) inlineable() bool {
return true
}
-// Returns the maximum total size of a bucket to make it a candidate for inlining.
+/// Bucket.maInlineBucketSize() returns the maximum total size of a bucket to
+/// make it a candidate for inlining.
func (b *Bucket) maxInlineBucketSize() int {
return b.tx.db.pageSize / 4
}
-// write allocates and writes a bucket to a byte slice.
+/// Bucket.write() allocates and writes a bucket to a byte slice.
func (b *Bucket) write() []byte {
// Allocate the appropriate size.
- var n = b.rootNode
- var value = make([]byte, bucketHeaderSize+n.size())
+ n := b.rootNode
+ value := make([]byte, bucketHeaderSize+n.size())
// Write a bucket header.
- var bucket = (*bucket)(unsafe.Pointer(&value[0]))
+ bucket := (*bucket)(unsafe.Pointer(&value[0]))
*bucket = *b.ref
// Convert byte slice to a fake page and write the root node.
- var p = (*page)(unsafe.Pointer(&value[bucketHeaderSize]))
+ p := (*page)(unsafe.Pointer(&value[bucketHeaderSize]))
n.write(p)
return value
}
-// rebalance attempts to balance all nodes.
+/// Bucket.rebalance() attempts to balance all nodes.
func (b *Bucket) rebalance() {
for _, n := range b.nodes {
n.rebalance()
@@ -962,17 +1049,19 @@ func (b *Bucket) rebalance() {
}
}
-// node creates a node from a page and associates it with a given parent.
+/// Bucket.node() creates a node from a page and associates it with a given
+/// parent.
func (b *Bucket) node(pgid pgid, parent *node) *node {
- _assert(b.nodes != nil, "nodes map expected")
+ g.Assert(b.nodes != nil, "nodes map expected")
// Retrieve node if it's already been created.
- if n := b.nodes[pgid]; n != nil {
+ n := b.nodes[pgid]
+ if n != nil {
return n
}
// Otherwise create a node and cache it.
- n := &node{bucket: b, parent: parent}
+ n = &node{bucket: b, parent: parent}
if parent == nil {
b.rootNode = n
} else {
@@ -980,7 +1069,7 @@ func (b *Bucket) node(pgid pgid, parent *node) *node {
}
// Use the inline page if this is an inline bucket.
- var p = b.page
+ p := b.page
if p == nil {
p = b.tx.page(pgid)
}
@@ -992,13 +1081,13 @@ func (b *Bucket) node(pgid pgid, parent *node) *node {
return n
}
-// free recursively frees all pages in the bucket.
+/// Bucket.free() recursively frees all pages in the bucket.
func (b *Bucket) free() {
if b.ref.root == 0 {
return
}
- var tx = b.tx
+ tx := b.tx
b.forEachPageNode(func(p *page, n *node, _ int) {
if p != nil {
tx.db.freelist.free(tx.meta.txid, p)
@@ -1009,7 +1098,7 @@ func (b *Bucket) free() {
b.ref.root = 0
}
-// dereference removes all references to the old mmap.
+/// Bucket.dereference() removes all references to the old mmap.
func (b *Bucket) dereference() {
if b.rootNode != nil {
b.rootNode.root().dereference()
@@ -1020,14 +1109,19 @@ func (b *Bucket) dereference() {
}
}
-// pageNode returns the in-memory node, if it exists.
-// Otherwise returns the underlying page.
+/// Bucket.pageNode() returns the in-memory node, if it exists. Otherwise
+/// returns the underlying page.
func (b *Bucket) pageNode(id pgid) (*page, *node) {
// Inline buckets have a fake page embedded in their value so treat them
- // differently. We'll return the rootNode (if available) or the fake page.
+ // differently. We'll return the rootNode (if available) or the fake
+ // page.
if b.ref.root == 0 {
if id != 0 {
- panic(fmt.Sprintf("inline bucket non-zero page access(2): %d != 0", id))
+ panic(fmt.Sprintf(
+ "inline bucket non-zero page access(2): " +
+ "%d != 0",
+ id,
+ ))
}
if b.rootNode != nil {
return nil, b.rootNode
@@ -1037,32 +1131,35 @@ func (b *Bucket) pageNode(id pgid) (*page, *node) {
// Check the node cache for non-inline buckets.
if b.nodes != nil {
- if n := b.nodes[id]; n != nil {
+ n := b.nodes[id]
+ if n != nil {
return nil, n
}
}
- // Finally lookup the page from the transaction if no node is materialized.
+ // Finally lookup the page from the transaction if no node is
+ // materialized.
return b.tx.page(id), nil
}
-// cloneBytes returns a copy of a given slice.
+/// cloneBytes() returns a copy of a given slice.
func cloneBytes(v []byte) []byte {
- var clone = make([]byte, len(v))
+ clone := make([]byte, len(v))
copy(clone, v)
return clone
}
-// Bucket returns the bucket that this cursor was created from.
+/// Cursor.Bucket() returns the bucket that this cursor was created from.
func (c *Cursor) Bucket() *Bucket {
return c.bucket
}
-// First moves the cursor to the first item in the bucket and returns its key and value.
-// If the bucket is empty then a nil key and value are returned.
-// The returned key and value are only valid for the life of the transaction.
+/// Cursor.First() moves the cursor to the first item in the bucket and returns
+/// its key and value. If the bucket is empty then a nil key and value are
+/// returned. The returned key and value are only valid for the life of the
+/// transaction.
func (c *Cursor) First() (key []byte, value []byte) {
- _assert(c.bucket.tx.db != nil, "tx closed")
+ g.Assert(c.bucket.tx.db != nil, "tx closed")
c.stack = c.stack[:0]
p, n := c.bucket.pageNode(c.bucket.ref.root)
c.stack = append(c.stack, elemRef{page: p, node: n, index: 0})
@@ -1082,11 +1179,12 @@ func (c *Cursor) First() (key []byte, value []byte) {
}
-// Last moves the cursor to the last item in the bucket and returns its key and value.
-// If the bucket is empty then a nil key and value are returned.
-// The returned key and value are only valid for the life of the transaction.
+/// Cursor.Last() moves the cursor to the last item in the bucket and returns
+/// its key and value. If the bucket is empty then a nil key and value are
+/// returned. The returned key and value are only valid for the life of the
+/// transaction.
func (c *Cursor) Last() (key []byte, value []byte) {
- _assert(c.bucket.tx.db != nil, "tx closed")
+ g.Assert(c.bucket.tx.db != nil, "tx closed")
c.stack = c.stack[:0]
p, n := c.bucket.pageNode(c.bucket.ref.root)
ref := elemRef{page: p, node: n}
@@ -1100,11 +1198,12 @@ func (c *Cursor) Last() (key []byte, value []byte) {
return k, v
}
-// Next moves the cursor to the next item in the bucket and returns its key and value.
-// If the cursor is at the end of the bucket then a nil key and value are returned.
-// The returned key and value are only valid for the life of the transaction.
+/// Cursor.Next() moves the cursor to the next item in the bucket and returns
+/// its key and value. If the cursor is at the end of the bucket then a nil key
+/// and value are returned. The returned key and value are only valid for the
+/// life of the transaction.
func (c *Cursor) Next() (key []byte, value []byte) {
- _assert(c.bucket.tx.db != nil, "tx closed")
+ g.Assert(c.bucket.tx.db != nil, "tx closed")
k, v, flags := c.next()
if (flags & uint32(bucketLeafFlag)) != 0 {
return k, nil
@@ -1112,11 +1211,12 @@ func (c *Cursor) Next() (key []byte, value []byte) {
return k, v
}
-// Prev moves the cursor to the previous item in the bucket and returns its key and value.
-// If the cursor is at the beginning of the bucket then a nil key and value are returned.
-// The returned key and value are only valid for the life of the transaction.
+/// Cursor.Prev() moves the cursor to the previous item in the bucket and
+/// returns its key and value. If the cursor is at the beginning of the bucket
+/// then a nil key and value are returned. The returned key and value are only
+/// valid for the life of the transaction.
func (c *Cursor) Prev() (key []byte, value []byte) {
- _assert(c.bucket.tx.db != nil, "tx closed")
+ g.Assert(c.bucket.tx.db != nil, "tx closed")
// Attempt to move back one element until we're successful.
// Move up the stack as we hit the beginning of each page in our stack.
@@ -1134,7 +1234,8 @@ func (c *Cursor) Prev() (key []byte, value []byte) {
return nil, nil
}
- // Move down the stack to find the last element of the last leaf under this branch.
+ // Move down the stack to find the last element of the last leaf under
+ // this branch.
c.last()
k, v, flags := c.keyValue()
if (flags & uint32(bucketLeafFlag)) != 0 {
@@ -1143,15 +1244,17 @@ func (c *Cursor) Prev() (key []byte, value []byte) {
return k, v
}
-// 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, a nil key is returned.
-// The returned key and value are only valid for the life of the transaction.
+/// Cursor.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, a nil key is
+/// returned. The returned key and value are only valid for the life of the
+/// transaction.
func (c *Cursor) Seek(seek []byte) (key []byte, value []byte) {
k, v, flags := c.seek(seek)
- // If we ended up after the last element of a page then move to the next one.
- if ref := &c.stack[len(c.stack)-1]; ref.index >= ref.count() {
+ // If we ended up after the last element of a page then move to the next
+ // one.
+ ref := &c.stack[len(c.stack)-1]
+ if ref.index >= ref.count() {
k, v, flags = c.next()
}
@@ -1159,12 +1262,14 @@ func (c *Cursor) Seek(seek []byte) (key []byte, value []byte) {
return nil, nil
} else if (flags & uint32(bucketLeafFlag)) != 0 {
return k, nil
+ } else {
+ return k, v
}
- return k, v
}
-// Delete removes the current key/value under the cursor from the bucket.
-// Delete fails if current key/value is a bucket or if the transaction is not writable.
+/// Cursor.Delete() removes the current key/value under the cursor from the
+/// bucket. Cursor.Delete() fails if current key/value is a bucket or if the
+/// transaction is not writable.
func (c *Cursor) Delete() error {
if c.bucket.tx.db == nil {
return ErrTxClosed
@@ -1182,10 +1287,10 @@ func (c *Cursor) Delete() error {
return nil
}
-// seek moves the cursor to a given key and returns it.
-// If the key does not exist then the next key is used.
+/// Cursor.seek() moves the cursor to a given key and returns it. If the key
+/// does not exist then the next key is used.
func (c *Cursor) seek(seek []byte) (key []byte, value []byte, flags uint32) {
- _assert(c.bucket.tx.db != nil, "tx closed")
+ g.Assert(c.bucket.tx.db != nil, "tx closed")
// Start from root page/node and traverse to correct page.
c.stack = c.stack[:0]
@@ -1201,11 +1306,12 @@ func (c *Cursor) seek(seek []byte) (key []byte, value []byte, flags uint32) {
return c.keyValue()
}
-// first moves the cursor to the first leaf element under the last page in the stack.
+/// Cursor.first() moves the cursor to the first leaf element under the last
+/// page in the stack.
func (c *Cursor) first() {
for {
// Exit when we hit a leaf page.
- var ref = &c.stack[len(c.stack)-1]
+ ref := &c.stack[len(c.stack)-1]
if ref.isLeaf() {
break
}
@@ -1215,14 +1321,17 @@ func (c *Cursor) first() {
if ref.node != nil {
pgid = ref.node.inodes[ref.index].pgid
} else {
- pgid = ref.page.branchPageElement(uint16(ref.index)).pgid
+ pgid = ref.page.branchPageElement(
+ uint16(ref.index),
+ ).pgid
}
p, n := c.bucket.pageNode(pgid)
c.stack = append(c.stack, elemRef{page: p, node: n, index: 0})
}
}
-// last moves the cursor to the last leaf element under the last page in the stack.
+/// Cursor.last() moves the cursor to the last leaf element under the last page
+/// in the stack.
func (c *Cursor) last() {
for {
// Exit when we hit a leaf page.
@@ -1236,22 +1345,26 @@ func (c *Cursor) last() {
if ref.node != nil {
pgid = ref.node.inodes[ref.index].pgid
} else {
- pgid = ref.page.branchPageElement(uint16(ref.index)).pgid
+ pgid = ref.page.branchPageElement(
+ uint16(ref.index),
+ ).pgid
}
p, n := c.bucket.pageNode(pgid)
- var nextRef = elemRef{page: p, node: n}
+ nextRef := elemRef{page: p, node: n}
nextRef.index = nextRef.count() - 1
c.stack = append(c.stack, nextRef)
}
}
-// next moves to the next leaf element and returns the key and value.
-// If the cursor is at the last leaf element then it stays there and returns nil.
+/// Cursor.next() moves to the next leaf element and returns the key and value.
+/// If the cursor is at the last leaf element then it stays there and returns
+/// nil.
func (c *Cursor) next() (key []byte, value []byte, flags uint32) {
for {
// 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.
+ // Move up the stack as we hit the end of each page in our
+ // stack.
var i int
for i = len(c.stack) - 1; i >= 0; i-- {
elem := &c.stack[i]
@@ -1261,18 +1374,19 @@ func (c *Cursor) next() (key []byte, value []byte, flags uint32) {
}
}
- // If we've hit the root page then stop and return. This will leave the
- // cursor on the last element of the last page.
+ // If we've hit the root page then stop and return. This will
+ // leave the cursor on the last element of the last page.
if i == -1 {
return nil, nil, 0
}
- // Otherwise start from where we left off in the stack and find the
- // first element of the first leaf page.
+ // Otherwise start from where we left off in the stack and find
+ // the first element of the first leaf page.
c.stack = c.stack[:i+1]
c.first()
- // If this is an empty page then restart and move back up the stack.
+ // If this is an empty page then restart and move back up the
+ // stack.
// https://github.com/boltdb/bolt/issues/450
if c.stack[len(c.stack)-1].count() == 0 {
continue
@@ -1282,7 +1396,8 @@ func (c *Cursor) next() (key []byte, value []byte, flags uint32) {
}
}
-// search recursively performs a binary search against a given page/node until it finds a given key.
+/// Cursor.search() recursively performs a binary search against a given
+/// page/node until it finds a given key.
func (c *Cursor) search(key []byte, pgid pgid) {
p, n := c.bucket.pageNode(pgid)
if p != nil && (p.flags&(branchPageFlag|leafPageFlag)) == 0 {
@@ -1307,8 +1422,9 @@ func (c *Cursor) search(key []byte, pgid pgid) {
func (c *Cursor) searchNode(key []byte, n *node) {
var exact bool
index := sort.Search(len(n.inodes), func(i int) bool {
- // TODO(benbjohnson): Optimize this range search. It's a bit hacky right now.
- // sort.Search() finds the lowest index where f() != -1 but we need the highest index.
+ // TODO(benbjohnson): Optimize this range search. It's a bit
+ // hacky right now. sort.Search() finds the lowest index where
+ // f() != -1 but we need the highest index.
ret := bytes.Compare(n.inodes[i].key, key)
if ret == 0 {
exact = true
@@ -1330,8 +1446,9 @@ func (c *Cursor) searchPage(key []byte, p *page) {
var exact bool
index := sort.Search(int(p.count), func(i int) bool {
- // TODO(benbjohnson): Optimize this range search. It's a bit hacky right now.
- // sort.Search() finds the lowest index where f() != -1 but we need the highest index.
+ // TODO(benbjohnson): Optimize this range search. It's a bit
+ // hacky right now. sort.Search() finds the lowest index where
+ // f() != -1 but we need the highest index.
ret := bytes.Compare(inodes[i].key(), key)
if ret == 0 {
exact = true
@@ -1347,7 +1464,7 @@ func (c *Cursor) searchPage(key []byte, p *page) {
c.search(key, inodes[index].pgid)
}
-// nsearch searches the leaf node on the top of the stack for a key.
+/// Cursor.nsearch() searches the leaf node on the top of the stack for a key.
func (c *Cursor) nsearch(key []byte) {
e := &c.stack[len(c.stack)-1]
p, n := e.page, e.node
@@ -1369,7 +1486,7 @@ func (c *Cursor) nsearch(key []byte) {
e.index = index
}
-// keyValue returns the key and value of the current leaf element.
+/// Cursor.keyValue() returns the key and value of the current leaf element.
func (c *Cursor) keyValue() ([]byte, []byte, uint32) {
ref := &c.stack[len(c.stack)-1]
if ref.count() == 0 || ref.index >= ref.count() {
@@ -1387,29 +1504,33 @@ func (c *Cursor) keyValue() ([]byte, []byte, uint32) {
return elem.key(), elem.value(), elem.flags
}
-// node returns the node that the cursor is currently positioned on.
+/// Cursor.node() returns the node that the cursor is currently positioned on.
func (c *Cursor) node() *node {
- _assert(len(c.stack) > 0, "accessing a node with a zero-length cursor stack")
+ g.Assert(
+ len(c.stack) > 0,
+ "accessing a node with a zero-length cursor stack",
+ )
// If the top of the stack is a leaf node then just return it.
- if ref := &c.stack[len(c.stack)-1]; ref.node != nil && ref.isLeaf() {
+ ref := &c.stack[len(c.stack)-1]
+ if ref.node != nil && ref.isLeaf() {
return ref.node
}
// Start from root and traverse down the hierarchy.
- var n = c.stack[0].node
+ n := c.stack[0].node
if n == nil {
n = c.bucket.node(c.stack[0].page.id, nil)
}
for _, ref := range c.stack[:len(c.stack)-1] {
- _assert(!n.isLeaf, "expected branch node")
+ g.Assert(!n.isLeaf, "expected branch node")
n = n.childAt(int(ref.index))
}
- _assert(n.isLeaf, "expected leaf node")
+ g.Assert(n.isLeaf, "expected leaf node")
return n
}
-// isLeaf returns whether the ref is pointing at a leaf page/node.
+/// elemRef.isLeaf() returns whether the ref is pointing at a leaf page/node.
func (r *elemRef) isLeaf() bool {
if r.node != nil {
return r.node.isLeaf
@@ -1417,7 +1538,7 @@ func (r *elemRef) isLeaf() bool {
return (r.page.flags & leafPageFlag) != 0
}
-// count returns the number of inodes or page elements.
+/// elemRef.count() returns the number of inodes or page elements.
func (r *elemRef) count() int {
if r.node != nil {
return len(r.node.inodes)
@@ -1425,7 +1546,7 @@ func (r *elemRef) count() int {
return int(r.page.count)
}
-// Path returns the path to currently open database file.
+/// DB.Path() returns the path to currently open database file.
func (db *DB) Path() string {
return db.path
}
@@ -1478,7 +1599,7 @@ func readPageSize(db *DB) (int, error) {
return int(m.pageSize), nil
}
-// init creates a new database file and initializes its meta pages.
+/// initDB() creates a new database file and initializes its meta pages.
func initDB(db *DB, size int64) error {
if size != 0 {
pageSize, err := readPageSize(db)
@@ -1524,18 +1645,21 @@ func initDB(db *DB, size int64) error {
p.count = 0
// Write the buffer to our data file.
- if _, err := db.file.WriteAt(buf, 0); err != nil {
+ _, err := db.file.WriteAt(buf, 0)
+ if err != nil {
return err
}
- if err := fdatasync(db); err != nil {
+
+ err = fdatasync(db)
+ if err != nil {
return err
}
return nil
}
-// Open creates and opens a database at the given path.
-// If the file does not exist then it will be created automatically.
+/// Open creates and opens a database at the given path. If the file does not
+/// exist then it will be created automatically.
func Open(path string) (*DB, error) {
file, err := openFile(path)
if err != nil {
@@ -1583,8 +1707,8 @@ func Open(path string) (*DB, error) {
return db, nil
}
-// mmap opens the underlying memory-mapped file and initializes the meta references.
-// minsz is the minimum size that the new mmap can be.
+/// DB.mmap() opens the underlying memory-mapped file and initializes the meta
+/// references. minsz is the minimum size that the new mmap can be.
func (db *DB) mmap(minsz int) error {
db.mmaplock.Lock()
defer db.mmaplock.Unlock()
@@ -1597,7 +1721,7 @@ func (db *DB) mmap(minsz int) error {
}
// Ensure the size is at least the minimum size.
- var size = int(info.Size())
+ size := int(info.Size())
if size < minsz {
size = minsz
}
@@ -1612,12 +1736,14 @@ func (db *DB) mmap(minsz int) error {
}
// Unmap existing data before continuing.
- if err := db.munmap(); err != nil {
+ err = db.munmap()
+ if err != nil {
return err
}
// Memory-map the data file as a byte slice.
- if err := mmap(db, size); err != nil {
+ err = mmap(db, size)
+ if err != nil {
return err
}
@@ -1625,9 +1751,9 @@ func (db *DB) mmap(minsz int) error {
db.meta0 = db.page(0).meta()
db.meta1 = db.page(1).meta()
- // Validate the meta pages. We only return an error if both meta pages fail
- // validation, since meta0 failing validation means that it wasn't saved
- // properly -- but we can recover using meta1. And vice-versa.
+ // Validate the meta pages. We only return an error if both meta pages
+ // fail validation, since meta0 failing validation means that it wasn't
+ // saved properly -- but we can recover using meta1. And vice-versa.
err0 := db.meta0.validate()
err1 := db.meta1.validate()
if err0 != nil && err1 != nil {
@@ -1637,17 +1763,19 @@ func (db *DB) mmap(minsz int) error {
return nil
}
-// munmap unmaps the data file from memory.
+/// DB.munmap() unmaps the data file from memory.
func (db *DB) munmap() error {
- if err := munmap(db); err != nil {
+ err := munmap(db)
+ if err != nil {
return fmt.Errorf("unmap error: " + err.Error())
}
return nil
}
-// mmapSize determines the appropriate size for the mmap given the current size
-// of the database. The minimum size is 32KB and doubles until it reaches 1GB.
-// Returns an error if the new mmap size is greater than the max allowed.
+/// DB. mmapSize() determines the appropriate size for the mmap given the
+/// current size of the database. The minimum size is 32KB and doubles until it
+/// reaches 1GB. Returns an error if the new mmap size is greater than the max
+/// allowed.
func (db *DB) mmapSize(size int) (int, error) {
// Double the size from 32KB until 1GB.
for i := uint(15); i <= 30; i++ {
@@ -1663,7 +1791,8 @@ func (db *DB) mmapSize(size int) (int, error) {
// If larger than 1GB then grow by 1GB at a time.
sz := int64(size)
- if remainder := sz % int64(maxMmapStep); remainder > 0 {
+ remainder := sz % int64(maxMmapStep)
+ if remainder > 0 {
sz += int64(maxMmapStep) - remainder
}
@@ -1682,8 +1811,8 @@ func (db *DB) mmapSize(size int) (int, error) {
return int(sz), nil
}
-// Close releases all database resources.
-// All transactions must be closed before closing the database.
+/// DB.Close() releases all database resources. All transactions must be closed
+/// before closing the database.
func (db *DB) Close() error {
db.rwlock.Lock()
defer db.rwlock.Unlock()
@@ -1707,7 +1836,8 @@ func (db *DB) close() error {
db.freelist = nil
// Close the mmap.
- if err := db.munmap(); err != nil {
+ err := db.munmap()
+ if err != nil {
return err
}
@@ -1715,12 +1845,14 @@ func (db *DB) close() error {
if db.file != nil {
// No need to unlock read-only file.
// Unlock the file.
- if err := funlock(db); err != nil {
- log.Printf("bolt.Close(): funlock error: %s", err)
+ err := funlock(db)
+ if err != nil {
+ log.Printf("dedo.Close(): funlock error: %s", err)
}
// Close the file descriptor.
- if err := db.file.Close(); err != nil {
+ err = db.file.Close()
+ if err != nil {
return fmt.Errorf("db file close: %s", err)
}
db.file = nil
@@ -1730,23 +1862,22 @@ func (db *DB) close() error {
return nil
}
-// Begin starts a new transaction.
-// Multiple read-only transactions can be used concurrently but only one
-// write transaction can be used at a time. Starting multiple write transactions
-// will cause the calls to block and be serialized until the current write
-// transaction finishes.
-//
-// Transactions should not be dependent on one another. Opening a read
-// transaction and a write transaction in the same goroutine can cause the
-// writer to deadlock because the database periodically needs to re-mmap itself
-// as it grows and it cannot do that while a read transaction is open.
-//
-// If a long running read transaction (for example, a snapshot transaction) is
-// needed, you might want to set DB.InitialMmapSize to a large enough value
-// to avoid potential blocking of write transaction.
-//
-// IMPORTANT: You must close read-only transactions after you are finished or
-// else the database will not reclaim old pages.
+/// DB.Begin() starts a new transaction. Multiple read-only transactions can be
+/// used concurrently but only one write transaction can be used at a time.
+/// Starting multiple write transactions will cause the calls to block and be
+/// serialized until the current write transaction finishes.
+///
+/// Transactions should not be dependent on one another. Opening a read
+/// transaction and a write transaction in the same goroutine can cause the
+/// writer to deadlock because the database periodically needs to re-mmap itself
+/// as it grows and it cannot do that while a read transaction is open.
+///
+/// If a long running read transaction (for example, a snapshot transaction) is
+/// needed, you might want to set DB.InitialMmapSize to a large enough value to
+/// avoid potential blocking of write transaction.
+///
+/// IMPORTANT: You must close read-only transactions after you are finished or
+/// else the database will not reclaim old pages.
func (db *DB) Begin(writable bool) (*Tx, error) {
if writable {
return db.beginRWTx()
@@ -1756,14 +1887,14 @@ func (db *DB) Begin(writable bool) (*Tx, error) {
}
func (db *DB) beginTx() (*Tx, error) {
- // Lock the meta pages while we initialize the transaction. We obtain
+ // Lock the meta pages while we initialize the transaction. We obtain
// the meta lock before the mmap lock because that's the order that the
// write transaction will obtain them.
db.metalock.Lock()
- // Obtain a read-only lock on the mmap. When the mmap is remapped it will
- // obtain a write lock so all transactions must finish before it can be
- // remapped.
+ // Obtain a read-only lock on the mmap. When the mmap is remapped it
+ // will obtain a write lock so all transactions must finish before it
+ // can be remapped.
db.mmaplock.RLock()
// Exit if the database is not open yet.
@@ -1787,8 +1918,8 @@ func (db *DB) beginTx() (*Tx, error) {
}
func (db *DB) beginRWTx() (*Tx, error) {
- // Obtain writer lock. This is released by the transaction when it closes.
- // This enforces only one writer transaction at a time.
+ // Obtain writer lock. This is released by the transaction when it
+ // closes. This enforces only one writer transaction at a time.
db.rwlock.Lock()
// Once we have the writer lock then we can lock the meta pages so that
@@ -1808,7 +1939,7 @@ func (db *DB) beginRWTx() (*Tx, error) {
db.rwtx = t
// Free any pages associated with closed read-only transactions.
- var minid txid = 0xFFFFFFFFFFFFFFFF
+ minid := txid(0xFFFFFFFFFFFFFFFF)
for _, t := range db.txs {
if t.meta.txid < minid {
minid = t.meta.txid
@@ -1821,7 +1952,7 @@ func (db *DB) beginRWTx() (*Tx, error) {
return t, nil
}
-// removeTx removes a transaction from the database.
+/// DB.removeTx() removes a transaction from the database.
func (db *DB) removeTx(tx *Tx) {
// Release the read lock on the mmap.
db.mmaplock.RUnlock()
@@ -1844,13 +1975,14 @@ func (db *DB) removeTx(tx *Tx) {
db.metalock.Unlock()
}
-// Update executes a function within the context of a read-write managed transaction.
-// If no error is returned from the function then the transaction is committed.
-// If an error is returned then the entire transaction is rolled back.
-// Any error that is returned from the function or returned from the commit is
-// returned from the Update() method.
-//
-// Attempting to manually commit or rollback within the function will cause a panic.
+/// DB.Update() executes a function within the context of a read-write managed
+/// transaction. If no error is returned from the function then the transaction
+/// is committed. If an error is returned then the entire transaction is rolled
+/// back. Any error that is returned from the function or returned from the
+/// commit is returned from the DB.Update() method.
+///
+/// Attempting to manually commit or rollback within the function will cause a
+/// panic.
func (db *DB) Update(fn func(*Tx) error) error {
t, err := db.Begin(true)
if err != nil {
@@ -1864,10 +1996,12 @@ func (db *DB) Update(fn func(*Tx) error) error {
}
}()
- // Mark as a managed tx so that the inner function cannot manually commit.
+ // Mark as a managed tx so that the inner function cannot manually
+ // commit.
t.managed = true
- // If an error is returned from the function then rollback and return error.
+ // If an error is returned from the function then rollback and return
+ // error.
err = fn(t)
t.managed = false
if err != nil {
@@ -1878,10 +2012,11 @@ func (db *DB) Update(fn func(*Tx) error) error {
return t.Commit()
}
-// View executes a function within the context of a managed read-only transaction.
-// Any error that is returned from the function is returned from the View() method.
-//
-// Attempting to manually rollback within the function will cause a panic.
+/// DB.View() executes a function within the context of a managed read-only
+/// transaction. Any error that is returned from the function is returned from
+/// the DB.View() method.
+///
+/// Attempting to manually rollback within the function will cause a panic.
func (db *DB) View(fn func(*Tx) error) error {
t, err := db.Begin(false)
if err != nil {
@@ -1895,7 +2030,8 @@ func (db *DB) View(fn func(*Tx) error) error {
}
}()
- // Mark as a managed tx so that the inner function cannot manually rollback.
+ // Mark as a managed tx so that the inner function cannot manually
+ // rollback.
t.managed = true
// If an error is returned from the function then pass it through.
@@ -1906,40 +2042,48 @@ func (db *DB) View(fn func(*Tx) error) error {
return err
}
- if err := t.Rollback(); err != nil {
+ err = t.Rollback()
+ if err != nil {
return err
}
return nil
}
-// Batch calls fn as part of a batch. It behaves similar to Update,
-// except:
-//
-// 1. concurrent Batch calls can be combined into a single Bolt
-// transaction.
-//
-// 2. the function passed to Batch may be called multiple times,
-// regardless of whether it returns error or not.
-//
-// This means that Batch function side effects must be idempotent and
-// take permanent effect only after a successful return is seen in
-// caller.
-//
-// The maximum batch size and delay can be adjusted with DB.MaxBatchSize
-// and DB.MaxBatchDelay, respectively.
-//
-// Batch is only useful when there are multiple goroutines calling it.
+func needsNewBatch(batch *batch, max int) bool {
+ return (batch == nil) || (batch != nil && len(batch.calls) >= max)
+}
+
+/// DB.Batch() calls fn as part of a batch. It behaves similar to Update,
+/// except:
+///
+/// 1. concurrent DB.Batch() calls can be combined into a single Dedo
+/// transaction.
+///
+/// 2. the function passed to DB.Batch() may be called multiple times,
+/// regardless of whether it returns error or not.
+///
+/// This means that DB.Batch() function side effects must be idempotent and take
+/// permanent effect only after a successful return is seen in caller.
+///
+/// The maximum batch size and delay can be adjusted with DB.MaxBatchSize and
+/// DB.MaxBatchDelay, respectively.
+///
+/// DB.Batch() is only useful when there are multiple goroutines calling it.
func (db *DB) Batch(fn func(*Tx) error) error {
errCh := make(chan error, 1)
db.batchMu.Lock()
- if (db.batch == nil) || (db.batch != nil && len(db.batch.calls) >= db.MaxBatchSize) {
- // There is no existing batch, or the existing batch is full; start a new one.
+ if needsNewBatch(db.batch, db.MaxBatchSize) {
+ // There is no existing batch, or the existing batch is full;
+ // start a new one.
db.batch = &batch{
db: db,
}
- db.batch.timer = time.AfterFunc(db.MaxBatchDelay, db.batch.trigger)
+ db.batch.timer = time.AfterFunc(
+ db.MaxBatchDelay,
+ db.batch.trigger,
+ )
}
db.batch.calls = append(db.batch.calls, call{fn: fn, err: errCh})
if len(db.batch.calls) >= db.MaxBatchSize {
@@ -1955,13 +2099,13 @@ func (db *DB) Batch(fn func(*Tx) error) error {
return err
}
-// trigger runs the batch if it hasn't already been run.
+/// batch.trigger() runs the batch if it hasn't already been run.
func (b *batch) trigger() {
b.start.Do(b.run)
}
-// run performs the transactions in the batch and communicates results
-// back to DB.Batch.
+/// batch.run() performs the transactions in the batch and communicates results
+/// back to DB.Batch.
func (b *batch) run() {
b.db.batchMu.Lock()
b.timer.Stop()
@@ -1974,10 +2118,11 @@ func (b *batch) run() {
retry:
for len(b.calls) > 0 {
- var failIdx = -1
+ failIdx := -1
err := b.db.Update(func(tx *Tx) error {
for i, c := range b.calls {
- if err := safelyCall(c.fn, tx); err != nil {
+ err := safelyCall(c.fn, tx)
+ if err != nil {
failIdx = i
return err
}
@@ -1986,17 +2131,20 @@ retry:
})
if failIdx >= 0 {
- // take the failing transaction out of the batch. it's
- // safe to shorten b.calls here because db.batch no longer
- // points to us, and we hold the mutex anyway.
+ // take the failing transaction out of the batch. it's
+ // safe to shorten b.calls here because db.batch no
+ // longer points to us, and we hold the mutex anyway.
c := b.calls[failIdx]
- b.calls[failIdx], b.calls = b.calls[len(b.calls)-1], b.calls[:len(b.calls)-1]
- // tell the submitter re-run it solo, continue with the rest of the batch
+ b.calls[failIdx], b.calls =
+ b.calls[ len(b.calls) - 1],
+ b.calls[:len(b.calls) - 1]
+ // tell the submitter re-run it solo, continue with the
+ // rest of the batch
c.err <- trySolo
continue retry
}
- // pass success, or bolt internal errors, to all callers
+ // pass success, or dedo internal errors, to all callers
for _, c := range b.calls {
c.err <- err
}
@@ -2005,7 +2153,8 @@ retry:
}
func (p panicked) Error() string {
- if err, ok := p.reason.(error); ok {
+ err, ok := p.reason.(error)
+ if ok {
return err.Error()
}
return fmt.Sprintf("panic: %v", p.reason)
@@ -2013,29 +2162,32 @@ func (p panicked) Error() string {
func safelyCall(fn func(*Tx) error, tx *Tx) (err error) {
defer func() {
- if p := recover(); p != nil {
+ p := recover()
+ if p != nil {
err = panicked{p}
}
}()
return fn(tx)
}
-// page retrieves a page reference from the mmap based on the current page size.
+/// db.page() retrieves a page reference from the mmap based on the current page
+/// size.
func (db *DB) page(id pgid) *page {
pos := id * pgid(db.pageSize)
return (*page)(unsafe.Pointer(&db.data[pos]))
}
-// pageInBuffer retrieves a page reference from a given byte array based on the current page size.
+/// pageInBuffer() retrieves a page reference from a given byte array based on
+/// the current page size.
func pageInBuffer(db *DB, b []byte, id pgid) *page {
return (*page)(unsafe.Pointer(&b[id*pgid(db.pageSize)]))
}
-// meta retrieves the current meta page reference.
+/// db.meta() retrieves the current meta page reference.
func (db *DB) meta() *meta {
// We have to return the meta with the highest txid which doesn't fail
- // validation. Otherwise, we can cause errors when in fact the database is
- // in a consistent state. metaA is the one with the higher txid.
+ // validation. Otherwise, we can cause errors when in fact the database
+ // is in a consistent state. metaA is the one with the higher txid.
metaA := db.meta0
metaB := db.meta1
if db.meta1.txid > db.meta0.txid {
@@ -2043,19 +2195,24 @@ func (db *DB) meta() *meta {
metaB = db.meta0
}
- // Use higher meta page if valid. Otherwise fallback to previous, if valid.
- if err := metaA.validate(); err == nil {
+ // Use higher meta page if valid. Otherwise fallback to previous, if
+ // valid.
+ err := metaA.validate()
+ if err == nil {
return metaA
- } else if err := metaB.validate(); err == nil {
+ }
+
+ err = metaB.validate()
+ if err == nil {
return metaB
}
- // This should never be reached, because both meta1 and meta0 were validated
- // on mmap() and we do fsync() on every write.
- panic("bolt.DB.meta(): invalid meta pages")
+ // This should never be reached, because both meta1 and meta0 were
+ // validated on mmap() and we do fsync() on every write.
+ panic("dedo.DB.meta(): invalid meta pages")
}
-// allocate returns a contiguous block of memory starting at a given page.
+/// db.allocate() returns a contiguous block of memory starting at a given page.
func (db *DB) allocate(count int) (*page, error) {
// Allocate a temporary buffer for the page.
var buf []byte
@@ -2068,15 +2225,17 @@ func (db *DB) allocate(count int) (*page, error) {
p.overflow = uint32(count - 1)
// Use pages from the freelist if they are available.
- if p.id = db.freelist.allocate(count); p.id != 0 {
+ p.id = db.freelist.allocate(count)
+ if p.id != 0 {
return p, nil
}
// Resize mmap() if we're at the end.
p.id = db.rwtx.meta.pgid
- var minsz = int((p.id+pgid(count))+1) * db.pageSize
+ minsz := int((p.id+pgid(count))+1) * db.pageSize
if minsz >= db.datasz {
- if err := db.mmap(minsz); err != nil {
+ err := db.mmap(minsz)
+ if err != nil {
return nil, fmt.Errorf("mmap allocate error: %s", err)
}
}
@@ -2087,15 +2246,16 @@ func (db *DB) allocate(count int) (*page, error) {
return p, nil
}
-// grow grows the size of the database to the given sz.
+/// db.grow() grows the size of the database to the given sz.
func (db *DB) grow(sz int) error {
// Ignore if the new size is less than available file size.
if sz <= db.filesz {
return nil
}
- // If the data is smaller than the alloc size then only allocate what's needed.
- // Once it goes over the allocation size then allocate in chunks.
+ // If the data is smaller than the alloc size then only allocate what's
+ // needed. Once it goes over the allocation size then allocate in
+ // chunks.
if db.datasz < db.AllocSize {
sz = db.datasz
} else {
@@ -2104,10 +2264,13 @@ func (db *DB) grow(sz int) error {
// Truncate and fsync to ensure file size metadata is flushed.
// https://github.com/boltdb/bolt/issues/284
- if err := db.file.Truncate(int64(sz)); err != nil {
+ err := db.file.Truncate(int64(sz))
+ if err != nil {
return fmt.Errorf("file resize error: %s", err)
}
- if err := db.file.Sync(); err != nil {
+
+ err = db.file.Sync()
+ if err != nil {
return fmt.Errorf("file sync error: %s", err)
}
@@ -2115,7 +2278,8 @@ func (db *DB) grow(sz int) error {
return nil
}
-// validate checks the marker bytes and version of the meta page to ensure it matches this binary.
+/// meta.validate() checks the marker bytes and version of the meta page to
+/// ensure it matches this binary.
func (m *meta) validate() error {
if m.magic != magic {
return ErrInvalid
@@ -2127,20 +2291,29 @@ func (m *meta) validate() error {
return nil
}
-// copy copies one meta object to another.
+/// meta.copy() copies one meta object to another.
func (m *meta) copy(dest *meta) {
*dest = *m
}
-// write writes the meta onto a page.
+/// meta.write() writes the meta onto a page.
func (m *meta) write(p *page) {
if m.root.root >= m.pgid {
- panic(fmt.Sprintf("root bucket pgid (%d) above high water mark (%d)", m.root.root, m.pgid))
+ panic(fmt.Sprintf(
+ "root bucket pgid (%d) above high water mark (%d)",
+ m.root.root,
+ m.pgid,
+ ))
} else if m.freelist >= m.pgid {
- panic(fmt.Sprintf("freelist pgid (%d) above high water mark (%d)", m.freelist, m.pgid))
+ panic(fmt.Sprintf(
+ "freelist pgid (%d) above high water mark (%d)",
+ m.freelist,
+ m.pgid,
+ ))
}
- // Page id is either going to be 0 or 1 which we can determine by the transaction ID.
+ // Page id is either going to be 0 or 1 which we can determine by the
+ // transaction ID.
p.id = pgid(m.txid % 2)
p.flags |= metaPageFlag
@@ -2150,66 +2323,16 @@ func (m *meta) write(p *page) {
m.copy(p.meta())
}
-// generates the checksum for the meta.
+/// meta.sum64() generates the checksum for the meta.
func (m *meta) sum64() uint64 {
- var h = fnv.New64a()
- _, _ = h.Write((*[unsafe.Offsetof(meta{}.checksum)]byte)(unsafe.Pointer(m))[:])
+ h := fnv.New64a()
+ _, _ = h.Write(
+ (*[unsafe.Offsetof(meta{}.checksum)]byte)(unsafe.Pointer(m))[:],
+ )
return h.Sum64()
}
-// _assert will panic with a given formatted message if the given condition is false.
-func _assert(condition bool, msg string, v ...interface{}) {
- if !condition {
- panic(fmt.Sprintf("assertion failed: "+msg, v...))
- }
-}
-
-
-/*
-Package bolt implements a low-level key/value store in pure Go. It supports
-fully serializable transactions, ACID semantics, and lock-free MVCC with
-multiple readers and a single writer. Bolt can be used for projects that
-want a simple data store without the need to add large dependencies such as
-Postgres or MySQL.
-
-Bolt is a single-level, zero-copy, B+tree data store. This means that Bolt is
-optimized for fast read access and does not require recovery in the event of a
-system crash. Transactions which have not finished committing will simply be
-rolled back in the event of a crash.
-
-The design of Bolt is based on Howard Chu's LMDB database project.
-
-Bolt currently works on Windows, Mac OS X, and Linux.
-
-
-Basics
-
-There are only a few types in Bolt: DB, Bucket, Tx, and Cursor. The DB is
-a collection of buckets and is represented by a single file on disk. A bucket is
-a collection of unique keys that are associated with values.
-
-Transactions provide either read-only or read-write access to the database.
-Read-only transactions can retrieve key/value pairs and can use Cursors to
-iterate over the dataset sequentially. Read-write transactions can create and
-delete buckets and can insert and remove keys. Only one read-write transaction
-is allowed at a time.
-
-
-Caveats
-
-The database uses a read-only, memory-mapped data file to ensure that
-applications cannot corrupt the database, however, this means that keys and
-values returned from Bolt cannot be changed. Writing to a read-only byte slice
-will cause Go to panic.
-
-Keys and values retrieved from the database are only valid for the life of
-the transaction. When used outside the transaction, these byte slices can
-point to different data or can point to invalid memory which will cause a panic.
-
-
-*/
-
-// newFreelist returns an empty, initialized freelist.
+/// newFreelist() returns an empty, initialized freelist.
func newFreelist() *freelist {
return &freelist{
pending: make(map[txid][]pgid),
@@ -2217,37 +2340,39 @@ func newFreelist() *freelist {
}
}
-// size returns the size of the page after serialization.
+/// freelist.size() returns the size of the page after serialization.
func (f *freelist) size() int {
n := f.count()
if n >= 0xFFFF {
- // The first element will be used to store the count. See freelist.write.
+ // The first element will be used to store the count. See
+ // freelist.write.
n++
}
return pageHeaderSize + (int(unsafe.Sizeof(pgid(0))) * n)
}
-// count returns count of pages on the freelist
+/// freelist.count() returns count of pages on the freelist
func (f *freelist) count() int {
return f.free_count() + f.pending_count()
}
-// free_count returns count of free pages
+/// freelist.free_count() returns count of free pages
func (f *freelist) free_count() int {
return len(f.ids)
}
-// pending_count returns count of pending pages
+/// freelist.pending_count() returns count of pending pages
func (f *freelist) pending_count() int {
- var count int
+ count := 0
for _, list := range f.pending {
count += len(list)
}
return count
}
-// copyall copies into dst a list of all free ids and all pending ids in one sorted list.
-// f.count returns the minimum length required for dst.
+/// freelist.copyall() copies into dst a list of all free ids and all pending
+/// ids in one sorted list.
+/// f.count returns the minimum length required for dst.
func (f *freelist) copyall(dst []pgid) {
m := make(pgids, 0, f.pending_count())
for _, list := range f.pending {
@@ -2257,14 +2382,16 @@ func (f *freelist) copyall(dst []pgid) {
mergepgids(dst, f.ids, m)
}
-// allocate returns the starting page id of a contiguous list of pages of a given size.
-// If a contiguous block cannot be found then 0 is returned.
+/// freelist.allocate() returns the starting page id of a contiguous list of
+/// pages of a given size. If a contiguous block cannot be found then 0 is
+/// returned.
func (f *freelist) allocate(n int) pgid {
if len(f.ids) == 0 {
return 0
}
- var initial, previd pgid
+ initial := pgid(0)
+ previd := pgid(0)
for i, id := range f.ids {
if id <= 1 {
panic(fmt.Sprintf("invalid page allocation: %d", id))
@@ -2277,10 +2404,10 @@ func (f *freelist) allocate(n int) pgid {
// If we found a contiguous block then remove it and return it.
if (id-initial)+1 == pgid(n) {
- // If we're allocating off the beginning then take the fast path
- // and just adjust the existing slice. This will use extra memory
- // temporarily but the append() in free() will realloc the slice
- // as is necessary.
+ // If we're allocating off the beginning then take the
+ // fast path and just adjust the existing slice. This
+ // will use extra memory temporarily but the append() in
+ // free() will realloc the slice as is necessary.
if (i + 1) == n {
f.ids = f.ids[i+1:]
} else {
@@ -2301,15 +2428,15 @@ func (f *freelist) allocate(n int) pgid {
return 0
}
-// free releases a page and its overflow for a given transaction id.
-// If the page is already free then a panic will occur.
+/// freelist.free() releases a page and its overflow for a given transaction id.
+/// If the page is already free then a panic will occur.
func (f *freelist) free(txid txid, p *page) {
if p.id <= 1 {
panic(fmt.Sprintf("cannot free page 0 or 1: %d", p.id))
}
// Free page and all its overflow pages.
- var ids = f.pending[txid]
+ ids := f.pending[txid]
for id := p.id; id <= p.id+pgid(p.overflow); id++ {
// Verify that page is not already free.
if f.cache[id] {
@@ -2323,13 +2450,14 @@ func (f *freelist) free(txid txid, p *page) {
f.pending[txid] = ids
}
-// release moves all page ids for a transaction id (or older) to the freelist.
+/// release moves all page ids for a transaction id (or older) to the freelist.
func (f *freelist) release(txid txid) {
m := make(pgids, 0)
for tid, ids := range f.pending {
if tid <= txid {
- // Move transaction's pending pages to the available freelist.
- // Don't remove from the cache since the page is still free.
+ // Move transaction's pending pages to the available
+ // freelist. Don't remove from the cache since the page
+ // is still free.
m = append(m, ids...)
delete(f.pending, tid)
}
@@ -2338,7 +2466,7 @@ func (f *freelist) release(txid txid) {
f.ids = pgids(f.ids).merge(m)
}
-// rollback removes the pages from a given pending tx.
+/// rollback removes the pages from a given pending tx.
func (f *freelist) rollback(txid txid) {
// Remove page ids from cache.
for _, id := range f.pending[txid] {
@@ -2349,15 +2477,16 @@ func (f *freelist) rollback(txid txid) {
delete(f.pending, txid)
}
-// freed returns whether a given page is in the free list.
+/// freed returns whether a given page is in the free list.
func (f *freelist) freed(pgid pgid) bool {
return f.cache[pgid]
}
-// read initializes the freelist from a freelist page.
+/// freelist.read() initializes the freelist from a freelist page.
func (f *freelist) read(p *page) {
- // If the page.count is at the max uint16 value (64k) then it's considered
- // an overflow and the size of the freelist is stored as the first element.
+ // If the page.count is at the max uint16 value (64k) then it's
+ // considered an overflow and the size of the freelist is stored as the
+ // first element.
idx, count := 0, int(p.count)
if count == 0xFFFF {
idx = 1
@@ -2368,7 +2497,7 @@ func (f *freelist) read(p *page) {
if count == 0 {
f.ids = nil
} else {
- ids := ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[idx:count]
+ ids := (*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr))[idx:count]
f.ids = make([]pgid, len(ids))
copy(f.ids, ids)
@@ -2380,17 +2509,18 @@ func (f *freelist) read(p *page) {
f.reindex()
}
-// write writes the page ids onto a freelist page. All free and pending ids are
-// saved to disk since in the event of a program crash, all pending ids will
-// become free.
+/// freelist.write() writes the page ids onto a freelist page. All free and
+/// pending ids are saved to disk since in the event of a program crash, all
+/// pending ids will become free.
func (f *freelist) write(p *page) error {
// Combine the old free pgids and pgids waiting on an open transaction.
// Update the header flag.
p.flags |= freelistPageFlag
- // The page.count can only hold up to 64k elements so if we overflow that
- // number then we handle it by putting the size in the first element.
+ // The page.count can only hold up to 64k elements so if we overflow
+ // that number then we handle it by putting the size in the first
+ // element.
lenids := f.count()
if lenids == 0 {
p.count = uint16(lenids)
@@ -2399,14 +2529,15 @@ func (f *freelist) write(p *page) error {
f.copyall(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[:])
} else {
p.count = 0xFFFF
- ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0] = pgid(lenids)
+ pageID := pgid(lenids)
+ ((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[0] = pageID
f.copyall(((*[maxAllocSize]pgid)(unsafe.Pointer(&p.ptr)))[1:])
}
return nil
}
-// reload reads the freelist from a page and filters out pending items.
+/// reload reads the freelist from a page and filters out pending items.
func (f *freelist) reload(p *page) {
f.read(p)
@@ -2420,7 +2551,7 @@ func (f *freelist) reload(p *page) {
// Check each page in the freelist and build a new available freelist
// with any pages not in the pending lists.
- var a []pgid
+ a := []pgid{}
for _, id := range f.ids {
if !pcache[id] {
a = append(a, id)
@@ -2428,12 +2559,13 @@ func (f *freelist) reload(p *page) {
}
f.ids = a
- // Once the available list is rebuilt then rebuild the free cache so that
- // it includes the available and pending free pages.
+ // Once the available list is rebuilt then rebuild the free cache so
+ // that it includes the available and pending free pages.
f.reindex()
}
-// reindex rebuilds the free cache based on available and pending free lists.
+/// freelist.reindex() rebuilds the free cache based on available and pending
+/// free lists.
func (f *freelist) reindex() {
f.cache = make(map[pgid]bool, len(f.ids))
for _, id := range f.ids {
@@ -2446,7 +2578,7 @@ func (f *freelist) reindex() {
}
}
-// root returns the top-level node this node is attached to.
+/// node.root() returns the top-level node this node is attached to.
func (n *node) root() *node {
if n.parent == nil {
return n
@@ -2454,7 +2586,7 @@ func (n *node) root() *node {
return n.parent.root()
}
-// minKeys returns the minimum number of inodes this node should have.
+/// node.minKeys() returns the minimum number of inodes this node should have.
func (n *node) minKeys() int {
if n.isLeaf {
return 1
@@ -2462,7 +2594,7 @@ func (n *node) minKeys() int {
return 2
}
-// size returns the size of the node after serialization.
+/// node.size() returns the size of the node after serialization.
func (n *node) size() int {
sz, elsz := pageHeaderSize, n.pageElementSize()
for i := 0; i < len(n.inodes); i++ {
@@ -2472,9 +2604,9 @@ func (n *node) size() int {
return sz
}
-// sizeLessThan returns true if the node is less than a given size.
-// This is an optimization to avoid calculating a large node when we only need
-// to know if it fits inside a certain page size.
+/// node.sizeLessThan() returns true if the node is less than a given size.
+/// This is an optimization to avoid calculating a large node when we only need
+/// to know if it fits inside a certain page size.
func (n *node) sizeLessThan(v int) bool {
sz, elsz := pageHeaderSize, n.pageElementSize()
for i := 0; i < len(n.inodes); i++ {
@@ -2487,15 +2619,17 @@ func (n *node) sizeLessThan(v int) bool {
return true
}
-// pageElementSize returns the size of each page element based on the type of node.
+/// node.pageElementSize() returns the size of each page element based on the
+/// type of node.
func (n *node) pageElementSize() int {
if n.isLeaf {
return leafPageElementSize
+ } else {
+ return branchPageElementSize
}
- return branchPageElementSize
}
-// childAt returns the child node at a given index.
+/// node.childAt() returns the child node at a given index.
func (n *node) childAt(index int) *node {
if n.isLeaf {
panic(fmt.Sprintf("invalid childAt(%d) on a leaf node", index))
@@ -2503,18 +2637,20 @@ func (n *node) childAt(index int) *node {
return n.bucket.node(n.inodes[index].pgid, n)
}
-// childIndex returns the index of a given child node.
+/// node.childIndex() returns the index of a given child node.
func (n *node) childIndex(child *node) int {
- index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, child.key) != -1 })
+ index := sort.Search(len(n.inodes), func(i int) bool {
+ return bytes.Compare(n.inodes[i].key, child.key) != -1
+ })
return index
}
-// numChildren returns the number of children.
+/// node.numChildren() returns the number of children.
func (n *node) numChildren() int {
return len(n.inodes)
}
-// nextSibling returns the next node with the same parent.
+/// node.nextSibling() returns the next node with the same parent.
func (n *node) nextSibling() *node {
if n.parent == nil {
return nil
@@ -2526,7 +2662,7 @@ func (n *node) nextSibling() *node {
return n.parent.childAt(index + 1)
}
-// prevSibling returns the previous node with the same parent.
+/// node.prevSibling() returns the previous node with the same parent.
func (n *node) prevSibling() *node {
if n.parent == nil {
return nil
@@ -2538,10 +2674,14 @@ func (n *node) prevSibling() *node {
return n.parent.childAt(index - 1)
}
-// put inserts a key/value.
+/// node.put() inserts a key/value.
func (n *node) put(oldKey, newKey, value []byte, pgid pgid, flags uint32) {
if pgid >= n.bucket.tx.meta.pgid {
- panic(fmt.Sprintf("pgid (%d) above high water mark (%d)", pgid, n.bucket.tx.meta.pgid))
+ panic(fmt.Sprintf(
+ "pgid (%d) above high water mark (%d)",
+ pgid,
+ n.bucket.tx.meta.pgid,
+ ))
} else if len(oldKey) <= 0 {
panic("put: zero-length old key")
} else if len(newKey) <= 0 {
@@ -2549,10 +2689,16 @@ func (n *node) put(oldKey, newKey, value []byte, pgid pgid, flags uint32) {
}
// Find insertion index.
- index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, oldKey) != -1 })
+ index := sort.Search(len(n.inodes), func(i int) bool {
+ return bytes.Compare(n.inodes[i].key, oldKey) != -1
+ })
- // Add capacity and shift nodes if we don't have an exact match and need to insert.
- exact := (len(n.inodes) > 0 && index < len(n.inodes) && bytes.Equal(n.inodes[index].key, oldKey))
+ // Add capacity and shift nodes if we don't have an exact match and need
+ // to insert.
+ exact :=
+ len(n.inodes) > 0 &&
+ index < len(n.inodes) &&
+ bytes.Equal(n.inodes[index].key, oldKey)
if !exact {
n.inodes = append(n.inodes, inode{})
copy(n.inodes[index+1:], n.inodes[index:])
@@ -2563,13 +2709,15 @@ func (n *node) put(oldKey, newKey, value []byte, pgid pgid, flags uint32) {
inode.key = newKey
inode.value = value
inode.pgid = pgid
- _assert(len(inode.key) > 0, "put: zero-length inode key")
+ g.Assert(len(inode.key) > 0, "put: zero-length inode key")
}
-// del removes a key from the node.
+/// node.del() removes a key from the node.
func (n *node) del(key []byte) {
// Find index of key.
- index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, key) != -1 })
+ index := sort.Search(len(n.inodes), func(i int) bool {
+ return bytes.Compare(n.inodes[i].key, key) != -1
+ })
// Exit if the key isn't found.
if index >= len(n.inodes) || !bytes.Equal(n.inodes[index].key, key) {
@@ -2583,7 +2731,7 @@ func (n *node) del(key []byte) {
n.unbalanced = true
}
-// read initializes the node from a page.
+/// node.read() initializes the node from a page.
func (n *node) read(p *page) {
n.pgid = p.id
n.isLeaf = ((p.flags & leafPageFlag) != 0)
@@ -2601,19 +2749,23 @@ func (n *node) read(p *page) {
inode.pgid = elem.pgid
inode.key = elem.key()
}
- _assert(len(inode.key) > 0, "read: zero-length inode key")
+ g.Assert(len(inode.key) > 0, "read: zero-length inode key")
}
// Save first key so we can find the node in the parent when we spill.
if len(n.inodes) > 0 {
n.key = n.inodes[0].key
- _assert(len(n.key) > 0, "read: zero-length node key")
+ g.Assert(len(n.key) > 0, "read: zero-length node key")
} else {
n.key = nil
}
}
-// write writes the items onto one or more pages.
+func u32position(a unsafe.Pointer, b unsafe.Pointer) uint32 {
+ return uint32(uintptr(a) - uintptr(b))
+}
+
+/// node.write() writes the items onto one or more pages.
func (n *node) write(p *page) {
// Initialize page.
if n.isLeaf {
@@ -2623,7 +2775,11 @@ func (n *node) write(p *page) {
}
if len(n.inodes) >= 0xFFFF {
- panic(fmt.Sprintf("inode overflow: %d (pgid=%d)", len(n.inodes), p.id))
+ panic(fmt.Sprintf(
+ "inode overflow: %d (pgid=%d)",
+ len(n.inodes),
+ p.id,
+ ))
}
p.count = uint16(len(n.inodes))
@@ -2633,27 +2789,37 @@ func (n *node) write(p *page) {
}
// Loop over each item and write it to the page.
- b := (*[maxAllocSize]byte)(unsafe.Pointer(&p.ptr))[n.pageElementSize()*len(n.inodes):]
+ nth := n.pageElementSize() * len(n.inodes)
+ b := (*[maxAllocSize]byte)(unsafe.Pointer(&p.ptr))[nth:]
for i, item := range n.inodes {
- _assert(len(item.key) > 0, "write: zero-length inode key")
+ g.Assert(len(item.key) > 0, "write: zero-length inode key")
// Write the page element.
if n.isLeaf {
elem := p.leafPageElement(uint16(i))
- elem.pos = uint32(uintptr(unsafe.Pointer(&b[0])) - uintptr(unsafe.Pointer(elem)))
+ elem.pos = u32position(
+ unsafe.Pointer(&b[0]),
+ unsafe.Pointer(elem),
+ )
elem.flags = item.flags
elem.ksize = uint32(len(item.key))
elem.vsize = uint32(len(item.value))
} else {
elem := p.branchPageElement(uint16(i))
- elem.pos = uint32(uintptr(unsafe.Pointer(&b[0])) - uintptr(unsafe.Pointer(elem)))
+ elem.pos = u32position(
+ unsafe.Pointer(&b[0]),
+ unsafe.Pointer(elem),
+ )
elem.ksize = uint32(len(item.key))
elem.pgid = item.pgid
- _assert(elem.pgid != p.id, "write: circular dependency occurred")
+ g.Assert(
+ elem.pgid != p.id,
+ "write: circular dependency occurred",
+ )
}
- // If the length of key+value is larger than the max allocation size
- // then we need to reallocate the byte array pointer.
+ // If the length of key+value is larger than the max allocation
+ // size then we need to reallocate the byte array pointer.
//
// See: https://github.com/boltdb/bolt/pull/335
klen, vlen := len(item.key), len(item.value)
@@ -2667,15 +2833,12 @@ func (n *node) write(p *page) {
copy(b[0:], item.value)
b = b[vlen:]
}
-
- // DEBUG ONLY: n.dump()
}
-// split breaks up a node into multiple smaller nodes, if appropriate.
-// This should only be called from the spill() function.
+/// node.split() breaks up a node into multiple smaller nodes, if appropriate.
+/// This should only be called from the spill() function.
func (n *node) split(pageSize int) []*node {
- var nodes []*node
-
+ nodes := []*node{}
node := n
for {
// Split node into two.
@@ -2694,8 +2857,8 @@ func (n *node) split(pageSize int) []*node {
return nodes
}
-// splitTwo breaks up a node into two smaller nodes, if appropriate.
-// This should only be called from the split() function.
+/// node.splitTwo() breaks up a node into two smaller nodes, if appropriate.
+/// This should only be called from the split() function.
func (n *node) splitTwo(pageSize int) (*node, *node) {
const fillPercent = 0.5
@@ -2727,20 +2890,25 @@ func (n *node) splitTwo(pageSize int) (*node, *node) {
return n, next
}
-// splitIndex finds the position where a page will fill a given threshold.
-// It returns the index as well as the size of the first page.
-// This is only be called from split().
+/// node.splitIndex() finds the position where a page will fill a given
+/// threshold. It returns the index as well as the size of the first page.
+/// This is only be called from split().
func (n *node) splitIndex(threshold int) (index, sz int) {
sz = pageHeaderSize
- // Loop until we only have the minimum number of keys required for the second page.
+ // Loop until we only have the minimum number of keys required for the
+ // second page.
for i := 0; i < len(n.inodes)-minKeysPerPage; i++ {
index = i
inode := n.inodes[i]
- elsize := n.pageElementSize() + len(inode.key) + len(inode.value)
-
- // If we have at least the minimum number of keys and adding another
- // node would put us over the threshold then exit and return.
+ elsize :=
+ n.pageElementSize() +
+ len(inode.key) +
+ len(inode.value)
+
+ // If we have at least the minimum number of keys and adding
+ // another node would put us over the threshold then exit and
+ // return.
if i >= minKeysPerPage && sz+elsize > threshold {
break
}
@@ -2752,29 +2920,31 @@ func (n *node) splitIndex(threshold int) (index, sz int) {
return
}
-// spill writes the nodes to dirty pages and splits nodes as it goes.
-// Returns an error if dirty pages cannot be allocated.
+/// node.spill() writes the nodes to dirty pages and splits nodes as it goes.
+/// Returns an error if dirty pages cannot be allocated.
func (n *node) spill() error {
- var tx = n.bucket.tx
+ tx := n.bucket.tx
if n.spilled {
return nil
}
- // Spill child nodes first. Child nodes can materialize sibling nodes in
- // the case of split-merge so we cannot use a range loop. We have to check
- // the children size on every loop iteration.
+ // Spill child nodes first. Child nodes can materialize sibling nodes
+ // in the case of split-merge so we cannot use a range loop. We have to
+ // check the children size on every loop iteration.
sort.Sort(n.children)
for i := 0; i < len(n.children); i++ {
- if err := n.children[i].spill(); err != nil {
+ err := n.children[i].spill()
+ if err != nil {
return err
}
}
- // We no longer need the child list because it's only used for spill tracking.
+ // We no longer need the child list because it's only used for spill
+ // tracking.
n.children = nil
- // Split nodes into appropriate sizes. The first node will always be n.
- var nodes = n.split(tx.db.pageSize)
+ // Split nodes into appropriate sizes. The first node will always be n.
+ nodes := n.split(tx.db.pageSize)
for _, node := range nodes {
// Add node's page to the freelist if it's not new.
if node.pgid > 0 {
@@ -2790,7 +2960,11 @@ func (n *node) spill() error {
// Write the node.
if p.id >= tx.meta.pgid {
- panic(fmt.Sprintf("pgid (%d) above high water mark (%d)", p.id, tx.meta.pgid))
+ panic(fmt.Sprintf(
+ "pgid (%d) above high water mark (%d)",
+ p.id,
+ tx.meta.pgid,
+ ))
}
node.pgid = p.id
node.write(p)
@@ -2798,19 +2972,29 @@ func (n *node) spill() error {
// Insert into parent inodes.
if node.parent != nil {
- var key = node.key
+ key := node.key
if key == nil {
key = node.inodes[0].key
}
- node.parent.put(key, node.inodes[0].key, nil, node.pgid, 0)
+ node.parent.put(
+ key,
+ node.inodes[0].key,
+ nil,
+ node.pgid,
+ 0,
+ )
node.key = node.inodes[0].key
- _assert(len(node.key) > 0, "spill: zero-length node key")
+ g.Assert(
+ len(node.key) > 0,
+ "spill: zero-length node key",
+ )
}
}
- // If the root node split and created a new root then we need to spill that
- // as well. We'll clear out the children to make sure it doesn't try to respill.
+ // If the root node split and created a new root then we need to spill
+ // that as well. We'll clear out the children to make sure it doesn't
+ // try to respill.
if n.parent != nil && n.parent.pgid == 0 {
n.children = nil
return n.parent.spill()
@@ -2819,8 +3003,8 @@ func (n *node) spill() error {
return nil
}
-// rebalance attempts to combine the node with sibling nodes if the node fill
-// size is below a threshold or if there are not enough keys.
+/// node.rebalance() attempts to combine the node with sibling nodes if the node
+/// fill size is below a threshold or if there are not enough keys.
func (n *node) rebalance() {
if !n.unbalanced {
return
@@ -2828,14 +3012,15 @@ func (n *node) rebalance() {
n.unbalanced = false
// Ignore if node is above threshold (25%) and has enough keys.
- var threshold = n.bucket.tx.db.pageSize / 4
+ threshold := n.bucket.tx.db.pageSize / 4
if n.size() > threshold && len(n.inodes) > n.minKeys() {
return
}
// Root node has special handling.
if n.parent == nil {
- // If root node is a branch and only has one node then collapse it.
+ // If root node is a branch and only has one node then collapse
+ // it.
if !n.isLeaf && len(n.inodes) == 1 {
// Move root's child up.
child := n.bucket.node(n.inodes[0].pgid, n)
@@ -2845,7 +3030,8 @@ func (n *node) rebalance() {
// Reparent all child nodes being moved.
for _, inode := range n.inodes {
- if child, ok := n.bucket.nodes[inode.pgid]; ok {
+ child, ok := n.bucket.nodes[inode.pgid]
+ if ok {
child.parent = n
}
}
@@ -2869,11 +3055,15 @@ func (n *node) rebalance() {
return
}
- _assert(n.parent.numChildren() > 1, "parent must have at least 2 children")
+ g.Assert(
+ n.parent.numChildren() > 1,
+ "parent must have at least 2 children",
+ )
- // Destination node is right sibling if idx == 0, otherwise left sibling.
+ // Destination node is right sibling if idx == 0, otherwise left
+ // sibling.
var target *node
- var useNextSibling = (n.parent.childIndex(n) == 0)
+ useNextSibling := n.parent.childIndex(n) == 0
if useNextSibling {
target = n.nextSibling()
} else {
@@ -2884,10 +3074,14 @@ func (n *node) rebalance() {
if useNextSibling {
// Reparent all child nodes being moved.
for _, inode := range target.inodes {
- if child, ok := n.bucket.nodes[inode.pgid]; ok {
+ child, ok := n.bucket.nodes[inode.pgid]
+ if ok {
child.parent.removeChild(child)
child.parent = n
- child.parent.children = append(child.parent.children, child)
+ child.parent.children = append(
+ child.parent.children,
+ child,
+ )
}
}
@@ -2900,10 +3094,14 @@ func (n *node) rebalance() {
} else {
// Reparent all child nodes being moved.
for _, inode := range n.inodes {
- if child, ok := n.bucket.nodes[inode.pgid]; ok {
+ child, ok := n.bucket.nodes[inode.pgid]
+ if ok {
child.parent.removeChild(child)
child.parent = target
- child.parent.children = append(child.parent.children, child)
+ child.parent.children = append(
+ child.parent.children,
+ child,
+ )
}
}
@@ -2915,12 +3113,13 @@ func (n *node) rebalance() {
n.free()
}
- // Either this node or the target node was deleted from the parent so rebalance it.
+ // Either this node or the target node was deleted from the parent so
+ // rebalance it.
n.parent.rebalance()
}
-// removes a node from the list of in-memory children.
-// This does not affect the inodes.
+/// node.removeChild() removes a node from the list of in-memory children. This
+/// does not affect the inodes.
func (n *node) removeChild(target *node) {
for i, child := range n.children {
if child == target {
@@ -2930,14 +3129,18 @@ func (n *node) removeChild(target *node) {
}
}
-// dereference causes the node to copy all its inode key/value references to heap memory.
-// This is required when the mmap is reallocated so inodes are not pointing to stale data.
+/// node.dereference() causes the node to copy all its inode key/value
+/// references to heap memory. This is required when the mmap is reallocated so
+/// inodes are not pointing to stale data.
func (n *node) dereference() {
if n.key != nil {
key := make([]byte, len(n.key))
copy(key, n.key)
n.key = key
- _assert(n.pgid == 0 || len(n.key) > 0, "dereference: zero-length node key on existing node")
+ g.Assert(
+ n.pgid == 0 || len(n.key) > 0,
+ "dereference: zero-length node key on existing node",
+ )
}
for i := range n.inodes {
@@ -2946,7 +3149,10 @@ func (n *node) dereference() {
key := make([]byte, len(inode.key))
copy(key, inode.key)
inode.key = key
- _assert(len(inode.key) > 0, "dereference: zero-length inode key")
+ g.Assert(
+ len(inode.key) > 0,
+ "dereference: zero-length inode key",
+ )
value := make([]byte, len(inode.value))
copy(value, inode.value)
@@ -2959,19 +3165,30 @@ func (n *node) dereference() {
}
}
-// free adds the node's underlying page to the freelist.
+/// node.free() adds the node's underlying page to the freelist.
func (n *node) free() {
if n.pgid != 0 {
- n.bucket.tx.db.freelist.free(n.bucket.tx.meta.txid, n.bucket.tx.page(n.pgid))
+ n.bucket.tx.db.freelist.free(
+ n.bucket.tx.meta.txid,
+ n.bucket.tx.page(n.pgid),
+ )
n.pgid = 0
}
}
-func (s nodes) Len() int { return len(s) }
-func (s nodes) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
-func (s nodes) Less(i, j int) bool { return bytes.Compare(s[i].inodes[0].key, s[j].inodes[0].key) == -1 }
+func (s nodes) Len() int {
+ return len(s)
+}
+
+func (s nodes) Swap(i, j int) {
+ s[i], s[j] = s[j], s[i]
+}
+
+func (s nodes) Less(i, j int) bool {
+ return bytes.Compare(s[i].inodes[0].key, s[j].inodes[0].key) == -1
+}
-// typ returns a human readable page type string used for debugging.
+/// typ returns a human readable page type string used for debugging.
func (p *page) typ() string {
if (p.flags & branchPageFlag) != 0 {
return "branch"
@@ -2985,18 +3202,18 @@ func (p *page) typ() string {
return fmt.Sprintf("unknown<%02x>", p.flags)
}
-// meta returns a pointer to the metadata section of the page.
+/// page.meta() returns a pointer to the metadata section of the page.
func (p *page) meta() *meta {
return (*meta)(unsafe.Pointer(&p.ptr))
}
-// leafPageElement retrieves the leaf node by index
+/// page.leafPageElement() retrieves the leaf node by index
func (p *page) leafPageElement(index uint16) *leafPageElement {
n := &((*[0x7FFFFFF]leafPageElement)(unsafe.Pointer(&p.ptr)))[index]
return n
}
-// leafPageElements retrieves a list of leaf nodes.
+/// page.leafPageElements() retrieves a list of leaf nodes.
func (p *page) leafPageElements() []leafPageElement {
if p.count == 0 {
return nil
@@ -3004,12 +3221,12 @@ func (p *page) leafPageElements() []leafPageElement {
return ((*[0x7FFFFFF]leafPageElement)(unsafe.Pointer(&p.ptr)))[:]
}
-// branchPageElement retrieves the branch node by index
+/// page.branchPageElement() retrieves the branch node by index
func (p *page) branchPageElement(index uint16) *branchPageElement {
return &((*[0x7FFFFFF]branchPageElement)(unsafe.Pointer(&p.ptr)))[index]
}
-// branchPageElements retrieves a list of branch nodes.
+/// page.branchPageElements() retrieves a list of branch nodes.
func (p *page) branchPageElements() []branchPageElement {
if p.count == 0 {
return nil
@@ -3017,33 +3234,53 @@ func (p *page) branchPageElements() []branchPageElement {
return ((*[0x7FFFFFF]branchPageElement)(unsafe.Pointer(&p.ptr)))[:]
}
-func (s pages) Len() int { return len(s) }
-func (s pages) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
-func (s pages) Less(i, j int) bool { return s[i].id < s[j].id }
+func (s pages) Len() int {
+ return len(s)
+}
+
+func (s pages) Swap(i, j int) {
+ s[i], s[j] = s[j], s[i]
+}
+
+func (s pages) Less(i, j int) bool {
+ return s[i].id < s[j].id
+}
-// key returns a byte slice of the node key.
+/// branchPageElement.key() returns a byte slice of the node key.
func (n *branchPageElement) key() []byte {
buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))
return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos]))[:n.ksize]
}
-// key returns a byte slice of the node key.
+/// leafPageElement.key() returns a byte slice of the node key.
func (n *leafPageElement) key() []byte {
buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))
- return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos]))[:n.ksize:n.ksize]
+ return (*[maxAllocSize]byte)(
+ unsafe.Pointer(&buf[n.pos]),
+ )[:n.ksize:n.ksize]
}
-// value returns a byte slice of the node value.
+/// leafPageElement.value() returns a byte slice of the node value.
func (n *leafPageElement) value() []byte {
buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))
- return (*[maxAllocSize]byte)(unsafe.Pointer(&buf[n.pos+n.ksize]))[:n.vsize:n.vsize]
+ return (*[maxAllocSize]byte)(
+ unsafe.Pointer(&buf[n.pos+n.ksize]),
+ )[:n.vsize:n.vsize]
}
-func (s pgids) Len() int { return len(s) }
-func (s pgids) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
-func (s pgids) Less(i, j int) bool { return s[i] < s[j] }
+func (s pgids) Len() int {
+ return len(s)
+}
-// merge returns the sorted union of a and b.
+func (s pgids) Swap(i, j int) {
+ s[i], s[j] = s[j], s[i]
+}
+
+func (s pgids) Less(i, j int) bool {
+ return s[i] < s[j]
+}
+
+/// pgids.merge() returns the sorted union of a and b.
func (a pgids) merge(b pgids) pgids {
// Return the opposite slice if one is nil.
if len(a) == 0 {
@@ -3057,11 +3294,16 @@ func (a pgids) merge(b pgids) pgids {
return merged
}
-// mergepgids copies the sorted union of a and b into dst.
-// If dst is too small, it panics.
+/// mergepgids() copies the sorted union of a and b into dst. If dst is too
+/// small, it panics.
func mergepgids(dst, a, b pgids) {
if len(dst) < len(a)+len(b) {
- panic(fmt.Errorf("mergepgids bad len %d < %d + %d", len(dst), len(a), len(b)))
+ panic(fmt.Errorf(
+ "mergepgids bad len %d < %d + %d",
+ len(dst),
+ len(a),
+ len(b),
+ ))
}
// Copy in the opposite slice if one is nil.
if len(a) == 0 {
@@ -3076,7 +3318,8 @@ func mergepgids(dst, a, b pgids) {
// Merged will hold all elements from both lists.
merged := dst[:0]
- // Assign lead to the slice with a lower starting value, follow to the higher value.
+ // Assign lead to the slice with a lower starting value, follow to the
+ // higher value.
lead, follow := a, b
if b[0] < a[0] {
lead, follow = b, a
@@ -3085,7 +3328,9 @@ func mergepgids(dst, a, b pgids) {
// Continue while there are elements in the lead.
for len(lead) > 0 {
// Merge largest prefix of lead that is ahead of follow[0].
- n := sort.Search(len(lead), func(i int) bool { return lead[i] > follow[0] })
+ n := sort.Search(len(lead), func(i int) bool {
+ return lead[i] > follow[0]
+ })
merged = append(merged, lead[:n]...)
if n >= len(lead) {
break
@@ -3099,7 +3344,7 @@ func mergepgids(dst, a, b pgids) {
_ = append(merged, follow...)
}
-// init initializes the transaction.
+/// Tx.init() initializes the transaction.
func (tx *Tx) init(db *DB) {
tx.db = db
tx.pages = nil
@@ -3113,90 +3358,96 @@ func (tx *Tx) init(db *DB) {
tx.root.ref = &bucket{}
*tx.root.ref = tx.meta.root
- // Increment the transaction id and add a page cache for writable transactions.
+ // Increment the transaction id and add a page cache for writable
+ // transactions.
if tx.writable {
tx.pages = make(map[pgid]*page)
tx.meta.txid += txid(1)
}
}
-// ID returns the transaction id.
+/// Tx.ID() returns the transaction id.
func (tx *Tx) ID() int {
return int(tx.meta.txid)
}
-// DB returns a reference to the database that created the transaction.
+/// Tx.DB() returns a reference to the database that created the transaction.
func (tx *Tx) DB() *DB {
return tx.db
}
-// Size returns current database size in bytes as seen by this transaction.
+/// Tx.Size() returns current database size in bytes as seen by this
+/// transaction.
func (tx *Tx) Size() int64 {
return int64(tx.meta.pgid) * int64(tx.db.pageSize)
}
-// Writable returns whether the transaction can perform write operations.
+/// Tx.Writable() returns whether the transaction can perform write operations.
func (tx *Tx) Writable() bool {
return tx.writable
}
-// Cursor creates a cursor associated with the root bucket.
-// All items in the cursor will return a nil value because all root bucket keys point to buckets.
-// The cursor is only valid as long as the transaction is open.
-// Do not use a cursor after the transaction is closed.
+/// Tx.Cursor() creates a cursor associated with the root bucket. All items in
+/// the cursor will return a nil value because all root bucket keys point to
+/// buckets. The cursor is only valid as long as the transaction is open. Do
+/// not use a cursor after the transaction is closed.
func (tx *Tx) Cursor() *Cursor {
return tx.root.Cursor()
}
-// Bucket retrieves a bucket by name.
-// Returns nil if the bucket does not exist.
-// The bucket instance is only valid for the lifetime of the transaction.
+/// Tx.Bucket() retrieves a bucket by name. Returns nil if the bucket does not
+/// exist. The bucket instance is only valid for the lifetime of the
+/// transaction.
func (tx *Tx) Bucket(name []byte) *Bucket {
return tx.root.Bucket(name)
}
-// CreateBucket creates a new bucket.
-// Returns an error if the bucket already exists, if the bucket name is blank, or if the bucket name is too long.
-// The bucket instance is only valid for the lifetime of the transaction.
+/// Tx.CreateBucket() creates a new bucket. Returns an error if the bucket
+/// already exists, if the bucket name is blank, or if the bucket name is too
+/// long. The bucket instance is only valid for the lifetime of the
+/// transaction.
func (tx *Tx) CreateBucket(name []byte) (*Bucket, error) {
return tx.root.CreateBucket(name)
}
-// CreateBucketIfNotExists creates a new bucket if it doesn't already exist.
-// Returns an error if the bucket name is blank, or if the bucket name is too long.
-// The bucket instance is only valid for the lifetime of the transaction.
+/// Tx.CreateBucketIfNotExists() creates a new bucket if it doesn't already
+/// exist. Returns an error if the bucket name is blank, or if the bucket name
+/// is too long. The bucket instance is only valid for the lifetime of the
+/// transaction.
func (tx *Tx) CreateBucketIfNotExists(name []byte) (*Bucket, error) {
return tx.root.CreateBucketIfNotExists(name)
}
-// DeleteBucket deletes a bucket.
-// Returns an error if the bucket cannot be found or if the key represents a non-bucket value.
+/// Tx.DeleteBucket() deletes a bucket. Returns an error if the bucket cannot
+/// be found or if the key represents a non-bucket value.
func (tx *Tx) DeleteBucket(name []byte) error {
return tx.root.DeleteBucket(name)
}
-// ForEach executes a function for each bucket in the root.
-// If the provided function returns an error then the iteration is stopped and
-// the error is returned to the caller.
+/// Tx.ForEach() executes a function for each bucket in the root. If the
+/// provided function returns an error then the iteration is stopped and the
+/// error is returned to the caller.
func (tx *Tx) ForEach(fn func(name []byte, b *Bucket) error) error {
return tx.root.ForEach(func(k, v []byte) error {
- if err := fn(k, tx.root.Bucket(k)); err != nil {
+ err := fn(k, tx.root.Bucket(k))
+ if err != nil {
return err
}
return nil
})
}
-// OnCommit adds a handler function to be executed after the transaction successfully commits.
+/// Tx.OnCommit() adds a handler function to be executed after the transaction
+/// successfully commits.
func (tx *Tx) OnCommit(fn func()) {
tx.commitHandlers = append(tx.commitHandlers, fn)
}
-// Commit writes all changes to disk and updates the meta page.
-// Returns an error if a disk write error occurs, or if Commit is
-// called on a read-only transaction.
+/// Tx.Commit() writes all changes to disk and updates the meta page. Returns
+/// an error if a disk write error occurs, or if Tx.Commiti() is called on a
+/// read-only transaction.
func (tx *Tx) Commit() error {
- _assert(!tx.managed, "managed tx commit not allowed")
+ g.Assert(!tx.managed, "managed tx commit not allowed")
if tx.db == nil {
return ErrTxClosed
} else if !tx.writable {
@@ -3209,7 +3460,8 @@ func (tx *Tx) Commit() error {
tx.root.rebalance()
// spill data onto dirty pages.
- if err := tx.root.spill(); err != nil {
+ err := tx.root.spill()
+ if err != nil {
tx.rollback()
return err
}
@@ -3219,30 +3471,36 @@ func (tx *Tx) Commit() error {
opgid := tx.meta.pgid
- // Free the freelist and allocate new pages for it. This will overestimate
- // the size of the freelist but not underestimate the size (which would be bad).
+ // Free the freelist and allocate new pages for it. This will
+ // overestimate the size of the freelist but not underestimate the size
+ // (which would be bad).
tx.db.freelist.free(tx.meta.txid, tx.db.page(tx.meta.freelist))
p, err := tx.allocate((tx.db.freelist.size() / tx.db.pageSize) + 1)
if err != nil {
tx.rollback()
return err
}
- if err := tx.db.freelist.write(p); err != nil {
+
+ err = tx.db.freelist.write(p)
+ if err != nil {
tx.rollback()
return err
}
tx.meta.freelist = p.id
- // If the high water mark has moved up then attempt to grow the database.
+ // If the high water mark has moved up then attempt to grow the
+ // database.
if tx.meta.pgid > opgid {
- if err := tx.db.grow(int(tx.meta.pgid+1) * tx.db.pageSize); err != nil {
+ err := tx.db.grow(int(tx.meta.pgid + 1) * tx.db.pageSize)
+ if err != nil {
tx.rollback()
return err
}
}
// Write dirty pages to disk.
- if err := tx.write(); err != nil {
+ err = tx.write()
+ if err != nil {
tx.rollback()
return err
}
@@ -3251,7 +3509,7 @@ func (tx *Tx) Commit() error {
// Only the first consistency error is reported in the panic.
if tx.db.StrictMode {
ch := tx.Check()
- var errs []string
+ errs := []string{}
for {
err, ok := <-ch
if !ok {
@@ -3265,7 +3523,8 @@ func (tx *Tx) Commit() error {
}
// Write meta to disk.
- if err := tx.writeMeta(); err != nil {
+ err = tx.writeMeta()
+ if err != nil {
tx.rollback()
return err
}
@@ -3281,10 +3540,10 @@ func (tx *Tx) Commit() error {
return nil
}
-// Rollback closes the transaction and ignores all previous updates. Read-only
-// transactions must be rolled back and not committed.
+/// Tx.Rollback() closes the transaction and ignores all previous updates.
+/// Read-only transactions must be rolled back and not committed.
func (tx *Tx) Rollback() error {
- _assert(!tx.managed, "managed tx rollback not allowed")
+ g.Assert(!tx.managed, "managed tx rollback not allowed")
if tx.db == nil {
return ErrTxClosed
}
@@ -3322,8 +3581,8 @@ func (tx *Tx) close() {
tx.pages = nil
}
-// WriteTo writes the entire database to a writer.
-// If err == nil then exactly tx.Size() bytes will be written into the writer.
+/// Tx.WriteTo() writes the entire database to a writer. If err == nil then
+/// exactly tx.Size() bytes will be written into the writer.
func (tx *Tx) WriteTo(w io.Writer) (n int64, err error) {
f, err := os.OpenFile(tx.db.path, os.O_RDONLY, 0)
if err != nil {
@@ -3331,7 +3590,7 @@ func (tx *Tx) WriteTo(w io.Writer) (n int64, err error) {
}
defer f.Close()
- // Generate a meta page. We use the same page data for both meta pages.
+ // Generate a meta page. We use the same page data for both meta pages.
buf := make([]byte, tx.db.pageSize)
page := (*page)(unsafe.Pointer(&buf[0]))
page.flags = metaPageFlag
@@ -3357,7 +3616,8 @@ func (tx *Tx) WriteTo(w io.Writer) (n int64, err error) {
}
// Move past the meta pages in the file.
- if _, err := f.Seek(int64(tx.db.pageSize*2), os.SEEK_SET); err != nil {
+ _, err = f.Seek(int64(tx.db.pageSize*2), os.SEEK_SET)
+ if err != nil {
return n, fmt.Errorf("seek: %s", err)
}
@@ -3371,9 +3631,9 @@ func (tx *Tx) WriteTo(w io.Writer) (n int64, err error) {
return n, f.Close()
}
-// CopyFile copies the entire database to file at the given path.
-// A reader transaction is maintained during the copy so it is safe to continue
-// using the database while a copy is in progress.
+/// Tx.CopyFile() copies the entire database to file at the given path. A
+/// reader transaction is maintained during the copy so it is safe to continue
+/// using the database while a copy is in progress.
func (tx *Tx) CopyFile(path string, mode os.FileMode) error {
f, err := os.OpenFile(path, os.O_RDWR|os.O_CREATE|os.O_TRUNC, mode)
if err != nil {
@@ -3388,14 +3648,14 @@ func (tx *Tx) CopyFile(path string, mode os.FileMode) error {
return f.Close()
}
-// Check performs several consistency checks on the database for this transaction.
-// An error is returned if any inconsistency is found.
-//
-// It can be safely run concurrently on a writable transaction. However, this
-// incurs a high cost for large databases and databases with a lot of subbuckets
-// because of caching. This overhead can be removed if running on a read-only
-// transaction, however, it is not safe to execute other writer transactions at
-// the same time.
+/// Tx.Check() performs several consistency checks on the database for this
+/// transaction. An error is returned if any inconsistency is found.
+///
+/// It can be safely run concurrently on a writable transaction. However, this
+/// incurs a high cost for large databases and databases with a lot of
+/// subbuckets because of caching. This overhead can be removed if running on a
+/// read-only transaction, however, it is not safe to execute other writer
+/// transactions at the same time.
func (tx *Tx) Check() <-chan error {
ch := make(chan error)
go tx.check(ch)
@@ -3437,7 +3697,20 @@ func (tx *Tx) check(ch chan error) {
close(ch)
}
-func (tx *Tx) checkBucket(b *Bucket, reachable map[pgid]*page, freed map[pgid]bool, ch chan error) {
+func isBranchPage(p *page) bool {
+ return (p.flags & branchPageFlag) == 0
+}
+
+func isLeafPage(p *page) bool {
+ return (p.flags & leafPageFlag) == 0
+}
+
+func (tx *Tx) checkBucket(
+ b *Bucket,
+ reachable map[pgid]*page,
+ freed map[pgid]bool,
+ ch chan error,
+) {
// Ignore inline buckets.
if b.ref.root == 0 {
return
@@ -3446,14 +3719,22 @@ func (tx *Tx) checkBucket(b *Bucket, reachable map[pgid]*page, freed map[pgid]bo
// Check every page used by this bucket.
b.tx.forEachPage(b.ref.root, 0, func(p *page, _ int) {
if p.id > tx.meta.pgid {
- ch <- fmt.Errorf("page %d: out of bounds: %d", int(p.id), int(b.tx.meta.pgid))
+ ch <- fmt.Errorf(
+ "page %d: out of bounds: %d",
+ int(p.id),
+ int(b.tx.meta.pgid),
+ )
}
// Ensure each page is only referenced once.
for i := pgid(0); i <= pgid(p.overflow); i++ {
- var id = p.id + i
- if _, ok := reachable[id]; ok {
- ch <- fmt.Errorf("page %d: multiple references", int(id))
+ id := p.id + i
+ _, ok := reachable[id]
+ if ok {
+ ch <- fmt.Errorf(
+ "page %d: multiple references",
+ int(id),
+ )
}
reachable[id] = p
}
@@ -3461,21 +3742,26 @@ func (tx *Tx) checkBucket(b *Bucket, reachable map[pgid]*page, freed map[pgid]bo
// We should only encounter un-freed leaf and branch pages.
if freed[p.id] {
ch <- fmt.Errorf("page %d: reachable freed", int(p.id))
- } else if (p.flags&branchPageFlag) == 0 && (p.flags&leafPageFlag) == 0 {
- ch <- fmt.Errorf("page %d: invalid type: %s", int(p.id), p.typ())
+ } else if isBranchPage(p) && isLeafPage(p) {
+ ch <- fmt.Errorf(
+ "page %d: invalid type: %s",
+ int(p.id),
+ p.typ(),
+ )
}
})
// Check each bucket within this bucket.
_ = b.ForEach(func(k, v []byte) error {
- if child := b.Bucket(k); child != nil {
+ child := b.Bucket(k)
+ if child != nil {
tx.checkBucket(child, reachable, freed, ch)
}
return nil
})
}
-// allocate returns a contiguous block of memory starting at a given page.
+/// Tx.allocate() returns a contiguous block of memory starting at a given page.
func (tx *Tx) allocate(count int) (*page, error) {
p, err := tx.db.allocate(count)
if err != nil {
@@ -3488,7 +3774,7 @@ func (tx *Tx) allocate(count int) (*page, error) {
return p, nil
}
-// write writes any dirty pages to disk.
+/// Tx.write() writes any dirty pages to disk.
func (tx *Tx) write() error {
// Sort pages by id.
pages := make(pages, 0, len(tx.pages))
@@ -3515,7 +3801,8 @@ func (tx *Tx) write() error {
// Write chunk to disk.
buf := ptr[:sz]
- if _, err := tx.db.file.WriteAt(buf, offset); err != nil {
+ _, err := tx.db.file.WriteAt(buf, offset)
+ if err != nil {
return err
}
@@ -3525,13 +3812,15 @@ func (tx *Tx) write() error {
break
}
- // Otherwise move offset forward and move pointer to next chunk.
+ // Otherwise move offset forward and move pointer to
+ // next chunk.
offset += int64(sz)
ptr = (*[maxAllocSize]byte)(unsafe.Pointer(&ptr[sz]))
}
}
- if err := fdatasync(tx.db); err != nil {
+ err := fdatasync(tx.db)
+ if err != nil {
return err
}
@@ -3544,8 +3833,6 @@ func (tx *Tx) write() error {
}
buf := (*[maxAllocSize]byte)(unsafe.Pointer(p))[:tx.db.pageSize]
-
- // See https://go.googlesource.com/go/+/f03c9202c43e0abb130669852082117ca50aa9b1
for i := range buf {
buf[i] = 0
}
@@ -3555,7 +3842,7 @@ func (tx *Tx) write() error {
return nil
}
-// writeMeta writes the meta to the disk.
+/// Tx.writeMeta() writes the meta to the disk.
func (tx *Tx) writeMeta() error {
// Create a temporary buffer for the meta page.
buf := make([]byte, tx.db.pageSize)
@@ -3563,23 +3850,26 @@ func (tx *Tx) writeMeta() error {
tx.meta.write(p)
// Write the meta page to file.
- if _, err := tx.db.file.WriteAt(buf, int64(p.id)*int64(tx.db.pageSize)); err != nil {
+ _, err := tx.db.file.WriteAt(buf, int64(p.id)*int64(tx.db.pageSize))
+ if err != nil {
return err
}
- if err := fdatasync(tx.db); err != nil {
+ err = fdatasync(tx.db)
+ if err != nil {
return err
}
return nil
}
-// page returns a reference to the page with a given id.
-// If page has been written to then a temporary buffered page is returned.
+/// Tx.page() returns a reference to the page with a given id. If page has been
+/// written to then a temporary buffered page is returned.
func (tx *Tx) page(id pgid) *page {
// Check the dirty pages first.
if tx.pages != nil {
- if p, ok := tx.pages[id]; ok {
+ p, ok := tx.pages[id]
+ if ok {
return p
}
}
@@ -3588,7 +3878,8 @@ func (tx *Tx) page(id pgid) *page {
return tx.db.page(id)
}
-// forEachPage iterates over every page within a given page and executes a function.
+/// Tx.forEachPage() iterates over every page within a given page and executes a
+/// function.
func (tx *Tx) forEachPage(pgid pgid, depth int, fn func(*page, int)) {
p := tx.page(pgid)
@@ -3604,8 +3895,8 @@ func (tx *Tx) forEachPage(pgid pgid, depth int, fn func(*page, int)) {
}
}
-// Page returns page information for a given page number.
-// This is only safe for concurrent use when used by a writable transaction.
+/// Tx.Page() returns page information for a given page number. This is only
+/// safe for concurrent use when used by a writable transaction.
func (tx *Tx) Page(id int) (*PageInfo, error) {
if tx.db == nil {
return nil, ErrTxClosed