README
¶
github.com/cznic/db has moved to modernc.org/db (vcs).
Please update your import paths to modernc.org/db.
This repo is now archived.
Documentation
¶
Overview ¶
Package db implements selected data structures found in database implementations.
Index ¶
- type BTree
- func (t *BTree) Clear(free func(koff, voff int64) error) error
- func (t *BTree) Delete(cmp func(koff int64) (int, error), free func(koff, voff int64) error) (bool, error)
- func (t *BTree) Get(cmp func(koff int64) (int, error)) (int64, bool, error)
- func (t *BTree) Len() (int64, error)
- func (t *BTree) Remove(free func(koff, voff int64) error) (err error)
- func (t *BTree) Seek(cmp func(int64) (int, error)) (*BTreeCursor, bool, error)
- func (t *BTree) SeekFirst() (*BTreeCursor, error)
- func (t *BTree) SeekLast() (*BTreeCursor, error)
- func (t *BTree) Set(cmp func(koff int64) (int, error), free func(koff int64) error) (int64, int64, error)
- type BTreeCursor
- type DB
- func (db *DB) NewBTree(nd, nx int, szKey, szVal int64) (*BTree, error)
- func (db *DB) NewDList(dataSize int64) (DList, error)
- func (db *DB) NewSList(dataSize int64) (SList, error)
- func (db *DB) OpenBTree(off int64) (*BTree, error)
- func (db *DB) OpenDList(off int64) (DList, error)
- func (db *DB) OpenSList(off int64) (SList, error)
- type DList
- type SList
- type Storage
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type BTree ¶
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 ¶
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 ¶
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 ¶
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) Remove ¶
Remove frees all space used by t.
For discussion of the free function see Clear.
func (*BTree) Seek ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
func (e *BTreeCursor) Err() error
Err returns the error, if any, that was encountered during iteration.
func (*BTreeCursor) Next ¶
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 ¶
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 ¶
type DB struct {
Storage
}
DB represents a database.
func (*DB) NewBTree ¶
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 ¶
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 ¶
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.
type DList ¶
DList is a node of a doubly linked list.
func (DList) InsertAfter ¶
InsertAfter inserts l after the DList node at off. Node l must not be already a part of any list.
func (DList) InsertBefore ¶
InsertBefore inserts l before the DList node at off. Node l must not be already a part of any list.
func (DList) RemoveToFirst ¶
RemoveToFirst removes all nodes from a list starting at first list node, up to and including l.
func (DList) RemoveToLast ¶
RemoveToLast removes all nodes from a list starting at l to the end of the list.
type SList ¶
SList is a node of a single linked list.
func (SList) InsertAfter ¶
InsertAfter inserts l after the SList node at off. Node l must not be already a part of any list.
func (SList) InsertBefore ¶
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) Remove ¶
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 ¶
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 ¶
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.
Source Files