db: github.com/cznic/db Index | Files

package db

import "github.com/cznic/db"

Package db implements selected data structures found in database implementations.

Index

Package Files

btree.go db.go dlist.go slist.go

type BTree Uses

type BTree struct {
    *DB
    Off   int64 // Location in the database.
    SzKey int64 // The szKey argument of NewBTree.
    SzVal int64 // The szVal argument of NewBTree.
    // contains filtered or unexported fields
}

BTree is a B+tree.

func (*BTree) Clear Uses

func (t *BTree) Clear(free func(koff, voff int64) error) error

Clear deletes all items of t.

The free function may be nil, otherwise it's called with the offsets of the key and value of an item that is being deleted from the tree. Both koff and voff may be zero when appropriate.

func (*BTree) Delete Uses

func (t *BTree) Delete(cmp func(koff int64) (int, error), free func(koff, voff int64) error) (bool, error)

Delete removes an item from t and returns a boolean value indicating if the item was found.

The item is searched for by calling the cmp function that gets the offset of a tree key to compare. It returns a positive value if the desired key collates after the tree key, a zero if the keys are equal and a negative value if the desired key collates before the tree key.

For discussion of the free function see Clear.

func (*BTree) Get Uses

func (t *BTree) Get(cmp func(koff int64) (int, error)) (int64, bool, error)

Get searches for a key in the tree and returns the offset of its associated value and a boolean value indicating success.

For discussion of the cmp function see Delete.

func (*BTree) Len Uses

func (t *BTree) Len() (int64, error)

Len returns the number of items i t or an error, if any.

func (*BTree) Remove Uses

func (t *BTree) Remove(free func(koff, voff int64) error) (err error)

Remove frees all space used by t.

For discussion of the free function see Clear.

func (*BTree) Seek Uses

func (t *BTree) Seek(cmp func(int64) (int, error)) (*BTreeCursor, bool, error)

Seek searches the tree for a key collating after the key used by the cmp function and a boolean value indicating the desired and found keys are equal.

For discussion of the cmp function see Delete.

func (*BTree) SeekFirst Uses

func (t *BTree) SeekFirst() (*BTreeCursor, error)

SeekFirst returns an Enumerator position on the first item of t or an error, if any.

func (*BTree) SeekLast Uses

func (t *BTree) SeekLast() (*BTreeCursor, error)

SeekLast returns an Enumerator position on the last item of t or an error, if any.

func (*BTree) Set Uses

func (t *BTree) Set(cmp func(koff int64) (int, error), free func(koff int64) error) (int64, int64, error)

Set adds or overwrites an item in t and returns the offsets if its key and value or an error, if any.

For discussion of the cmp function see Delete.

For discussion of the free function see Clear.

type BTreeCursor Uses

type BTreeCursor struct {
    K   int64 // Item key offset. Not valid before calling Next or Prev.
    V   int64 // Item value offset. Not valid before calling Next or Prev.
    // contains filtered or unexported fields
}

BTreeCursor provides enumerating BTree items.

func (*BTreeCursor) Err Uses

func (e *BTreeCursor) Err() error

Err returns the error, if any, that was encountered during iteration.

func (*BTreeCursor) Next Uses

func (e *BTreeCursor) Next() bool

Next moves the cursor to the next item in the tree and sets the K and V fields accordingly. It returns true on success, or false if there is no next item or an error happened while moving the cursor. Err should be consulted to distinguish between the two cases.

Every use of the K/V fields, even the first one, must be preceded by a call to Next or Prev.

func (*BTreeCursor) Prev Uses

func (e *BTreeCursor) Prev() bool

Prev moves the cursor to the previous item in the tree and sets the K and V fields accordingly. It returns true on success, or false if there is no previous item or an error happened while moving the cursor. Err should be consulted to distinguish between the two cases.

Every use of the K/V fields, even the first one, must be preceded by a call to Next or Prev.

type DB Uses

type DB struct {
    Storage
}

DB represents a database.

func NewDB Uses

func NewDB(s Storage) (*DB, error)

NewDB returns a newly created DB backed by s or an error, if any.

func (*DB) NewBTree Uses

func (db *DB) NewBTree(nd, nx int, szKey, szVal int64) (*BTree, error)

NewBTree allocates and returns a new, empty BTree or an error, if any. The nd and nx arguments are the desired number of items in a data or index page. Passing zero will use default values. The szKey and szVal arguments are the sizes of the BTree keys and values.

func (*DB) NewDList Uses

func (db *DB) NewDList(dataSize int64) (DList, error)

NewDList returns a newly allocated DList or an error, if any. The datasize parameter is the fixed size of data associated with the list node. To get/set the node data, use the ReadAt/WriteAt methods of db, using DList.DataOff() as the offset. Reading or writing more than datasize data at DataOff() is undefined behavior and may irreparably corrupt the database.

The result of NewDList is not a part of any list.

func (*DB) NewSList Uses

func (db *DB) NewSList(dataSize int64) (SList, error)

NewSList returns a newly allocated SList or an error, if any. The datasize parameter is the fixed size of data associated with the list node. To get/set the node data, use the ReadAt/WriteAt methods of db, using SList.DataOff() as the offset. Reading or writing more than datasize data at DataOff() is undefined behavior and may irreparably corrupt the database.

The result of NewSList is not a part of any list.

func (*DB) OpenBTree Uses

func (db *DB) OpenBTree(off int64) (*BTree, error)

OpenBTree opend and returns an existing BTree or an error, if any.

func (*DB) OpenDList Uses

func (db *DB) OpenDList(off int64) (DList, error)

OpenDList returns a DList found at offset off.

func (*DB) OpenSList Uses

func (db *DB) OpenSList(off int64) (SList, error)

OpenSList returns an SList found at offset off.

type DList Uses

type DList struct {
    *DB
    Off int64
}

DList is a node of a doubly linked list.

func (DList) DataOff Uses

func (l DList) DataOff() int64

DataOff returns the offset in db at which data of l are located.

func (DList) InsertAfter Uses

func (l DList) InsertAfter(off int64) error

InsertAfter inserts l after the DList node at off. Node l must not be already a part of any list.

func (DList) InsertBefore Uses

func (l DList) InsertBefore(off int64) error

InsertBefore inserts l before the DList node at off. Node l must not be already a part of any list.

func (DList) Next Uses

func (l DList) Next() (int64, error)

Next returns the offset of the next node of l.

func (DList) Prev Uses

func (l DList) Prev() (int64, error)

Prev returns the offset of the prev node of l.

func (DList) Remove Uses

func (l DList) Remove() error

Remove removes l from a list.

func (DList) RemoveToFirst Uses

func (l DList) RemoveToFirst() error

RemoveToFirst removes all nodes from a list starting at first list node, up to and including l.

func (DList) RemoveToLast Uses

func (l DList) RemoveToLast() error

RemoveToLast removes all nodes from a list starting at l to the end of the list.

type SList Uses

type SList struct {
    *DB
    Off int64
}

SList is a node of a single linked list.

func (SList) DataOff Uses

func (l SList) DataOff() int64

DataOff returns the offset in db at which data of l are located.

func (SList) InsertAfter Uses

func (l SList) InsertAfter(off int64) error

InsertAfter inserts l after the SList node at off. Node l must not be already a part of any list.

func (SList) InsertBefore Uses

func (l SList) InsertBefore(prev, off int64) error

InsertBefore inserts l before the SList node at off. If the SList node at off is linked to from an SList node at prev, the prev argument must reflect that, otherwise prev must be zero. Node l must not be already a part of any list.

func (SList) Next Uses

func (l SList) Next() (int64, error)

Next returns the offset of the next node of l.

func (SList) Remove Uses

func (l SList) Remove(prev int64) error

Remove removes l from a list. If l is linked to from an SList node at prev, the prev argument must reflect that, otherwise prev must be zero.

func (SList) RemoveToLast Uses

func (l SList) RemoveToLast(prev int64) error

RemoveToLast removes all nodes from a list starting at l to the end of the list. If l is linked to from an SList node at prev, the prev argument must reflect that, otherwise prev must be zero.

type Storage Uses

type Storage interface {
    // Alloc allocates a storage block large enough for storing size bytes
    // and returns its offset or an error, if any.
    Alloc(size int64) (int64, error)

    // Calloc is like Alloc but the allocated storage block is zeroed up
    // to size.
    Calloc(size int64) (int64, error)

    // Close finishes storage use.
    Close() error

    // Free recycles the allocated storage block at off.
    Free(off int64) error

    // ReadAt reads len(p) bytes into p starting at offset off in the
    // storage. It returns the number of bytes read (0 <= n <= len(p)) and
    // any error encountered.
    //
    // When ReadAt returns n < len(p), it returns a non-nil error
    // explaining why more bytes were not returned.
    //
    // Even if ReadAt returns n < len(p), it may use all of p as scratch
    // space during the call.
    //
    // If the n = len(p) bytes returned by ReadAt are at the end of the
    // storage, ReadAt may return either err == EOF or err == nil.
    ReadAt(p []byte, off int64) (n int, err error)

    // Realloc changes the size of the file block allocated at off, which
    // must have been returned from Alloc or Realloc, to size and returns
    // the offset of the relocated file block or an error, if any. The
    // contents will be unchanged in the range from the start of the region
    // up to the minimum of the old and new sizes. Realloc(off, 0) is equal
    // to Free(off). If the file block was moved, a Free(off) is done.
    Realloc(off, size int64) (int64, error)

    // Root returns the offset of the database root object or an error, if
    // any.  It's not an error if a newly created or empty database has no
    // root yet.  The returned offset in that case will be zero.
    Root() (int64, error)

    // SetRoot sets the offset of the database root object.
    SetRoot(root int64) error

    // Stat returns the os.FileInfo structure describing the storage. If
    // there is an error, it will be of type *os.PathError.
    Stat() (os.FileInfo, error)

    // Sync commits the current contents of the database to stable storage.
    // Typically, this means flushing the file system's in-memory copy of
    // recently written data to disk.
    Sync() error

    // Truncate changes the size of the storage. If there is an error, it
    // will be of type *os.PathError.
    Truncate(int64) error

    // WriteAt writes len(p) bytes from p to the storage at offset off. It
    // returns the number of bytes written from p (0 <= n <= len(p)) and
    // any error encountered that caused the write to stop early. WriteAt
    // must return a non-nil error if it returns n < len(p).
    WriteAt(p []byte, off int64) (n int, err error)
}

Storage represents a database back end.

Package db imports 5 packages (graph) and is imported by 1 packages. Updated 2019-01-07. Refresh now. Tools for package owners.