ibtree

package
v0.0.0-...-cdd27d5 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 7, 2019 License: GPL-3.0 Imports: 8 Imported by: 0

Documentation

Overview

  • Author: Markus Stenberg <fingon@iki.fi> *
  • Copyright (c) 2017 Markus Stenberg *
  • Created: Wed Dec 27 17:19:12 2017 mstenber
  • Last modified: Tue Jan 9 19:59:56 2018 mstenber
  • Edit time: 175 min *

ibtree package provides a functional b+ tree that consists of nodes, with N children each, that are either leaves or other nodes.

It has built-in persistence, and Merkle tree-style hash tree behavior; root is defined by simply root node's hash, and similarly also all the children.

ONLY root and dirty Nodes are kept in memory; the rest count on (caching) storage backend + persistence layer being 'fast enough'.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type BlockDataType 

type BlockDataType byte
const (
	BDT_NODE BlockDataType = 7
)

type BlockId 

type BlockId string

func (BlockId) String 

func (self BlockId) String() string

type DeltaCallback 

type DeltaCallback func(old, new *NodeDataChild)

type DummyBackend 

type DummyBackend struct {
	// contains filtered or unexported fields
}

DummyBackend is minimal in-memory backend that can be used for testing purposes.

func (DummyBackend) Init 

func (self DummyBackend) Init() *DummyBackend

func (*DummyBackend) LoadNode 

func (self *DummyBackend) LoadNode(id BlockId) *NodeData

func (*DummyBackend) SaveNode 

func (self *DummyBackend) SaveNode(nd *NodeData) BlockId

type Key 

type Key string

func (*Key) DecodeMsg 

func (z *Key) DecodeMsg(dc *msgp.Reader) (err error)

DecodeMsg implements msgp.Decodable We treat empty fields as if we read a Nil from the wire.

func (Key) EncodeMsg 

func (z Key) EncodeMsg(en *msgp.Writer) (err error)

EncodeMsg implements msgp.Encodable

func (Key) MarshalMsg 

func (z Key) MarshalMsg(b []byte) (o []byte, err error)

MarshalMsg implements msgp.Marshaler

func (Key) Msgsize 

func (z Key) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*Key) UnmarshalMsg 

func (z *Key) UnmarshalMsg(bts []byte) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

func (*Key) UnmarshalMsgWithCfg 

func (z *Key) UnmarshalMsgWithCfg(bts []byte, cfg *msgp.RuntimeConfig) (o []byte, err error)

type Node 

type Node struct {
	NodeData
	// contains filtered or unexported fields
}

Node represents single node in single tree.

func (*Node) Commit 

func (self *Node) Commit() (*Node, BlockId)

Commit pushes dirty Node to default backend, returning the new root.

func (*Node) CommitTo 

func (self *Node) CommitTo(backend TreeSaver) (*Node, BlockId)

CommitTo pushes dirty Node to the specified backend, returning the new root.

func (*Node) Delete 

func (self *Node) Delete(key Key, st *Stack) *Node

func (*Node) DeleteRange 

func (self *Node) DeleteRange(key1, key2 Key, st2 *Stack) *Node

func (*Node) Get 

func (self *Node) Get(key Key, st *Stack) *string

func (*Node) IterateDelta 

func (self *Node) IterateDelta(original *Node, deltacb DeltaCallback)

IterateDelta produces callback for every difference in the leaves local tree as opposed to 'other'.

Some clever things are done to avoid pointless subtree iteration. Still, this is pretty expensive operation and should be done only in background.

func (*Node) NextKey 

func (self *Node) NextKey(key Key, st *Stack) *Key

func (*Node) PrevKey 

func (self *Node) PrevKey(key Key, st *Stack) *Key

func (*Node) PrintToMLogAll 

func (self *Node) PrintToMLogAll()

func (*Node) PrintToMLogDirty 

func (self *Node) PrintToMLogDirty()

func (*Node) Set 

func (self *Node) Set(key Key, value string, st *Stack) *Node

func (*Node) String 

func (self *Node) String() string

type NodeData 

type NodeData struct {
	Leafy    bool             `zid:"0"`
	Children []*NodeDataChild `zid:"1"`
}

func NewNodeDataFromBytes 

func NewNodeDataFromBytes(bd []byte) *NodeData

func (*NodeData) CheckNodeStructure 

func (self *NodeData) CheckNodeStructure()

CheckNodeStructure allows sanity checking a node's content (should not be really used except for debugging)

func (*NodeData) DecodeMsg 

func (z *NodeData) DecodeMsg(dc *msgp.Reader) (err error)

DecodeMsg implements msgp.Decodable We treat empty fields as if we read a Nil from the wire.

func (*NodeData) EncodeMsg 

func (z *NodeData) EncodeMsg(en *msgp.Writer) (err error)

EncodeMsg implements msgp.Encodable

func (*NodeData) MarshalMsg 

func (z *NodeData) MarshalMsg(b []byte) (o []byte, err error)

MarshalMsg implements msgp.Marshaler

func (*NodeData) Msgsize 

func (z *NodeData) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*NodeData) String 

func (self *NodeData) String() string

func (*NodeData) ToBytes 

func (self *NodeData) ToBytes() []byte

func (*NodeData) UnmarshalMsg 

func (z *NodeData) UnmarshalMsg(bts []byte) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

func (*NodeData) UnmarshalMsgWithCfg 

func (z *NodeData) UnmarshalMsgWithCfg(bts []byte, cfg *msgp.RuntimeConfig) (o []byte, err error)

type NodeDataCart 

type NodeDataCart struct {
	// contains filtered or unexported fields
}

NodeDataCart provides CART (Clock with Adaptive Replacement and Temporal filtering) cache map of string-ish BlockId to *NodeData.

For details about CART, see: Bansal & Modha 2004, CAR: Clock with Adaptive Replacement paper.

The type is not threadsafe, and requires also YYYList to be available for NodeDataCartEntryList.

variables are as close as possible to ones in paper

func (*NodeDataCart) Get 

func (self *NodeDataCart) Get(key BlockId) (value *NodeData, found bool)

Get retrieves the key, and returns the value if found, and indicates in found if it was found or not.

func (*NodeDataCart) GetOrCreate 

func (self *NodeDataCart) GetOrCreate(key BlockId, factory func(key BlockId) *NodeData) (value *NodeData, created bool)

GetOrCreate uses Get first, and then calls factory if Get fails. The value is returned, as well as whether or not it was created.

func (*NodeDataCart) Init 

func (self *NodeDataCart) Init(maximumSize int) *NodeDataCart

func (*NodeDataCart) Set 

func (self *NodeDataCart) Set(key BlockId, value *NodeData)

Set sets the key to value. If value is nil, the key is cleared instead.

type NodeDataCartEntry 

type NodeDataCartEntry struct {
	// contains filtered or unexported fields
}

NodeDataCartEntry represents a single cache entry; maps point at it under key

func (*NodeDataCartEntry) String 

func (self *NodeDataCartEntry) String() string

type NodeDataCartEntryList 

type NodeDataCartEntryList struct {
	Back, Front *NodeDataCartEntryListElement

	Length int
	// contains filtered or unexported fields
}

NodeDataCartEntryList provides doubly linked list which does not have inefficient operations, is typesafe, and does minimum amount of extra allocations needed. This is accomplished by sticking the freed items to a freelist instead of freeing them directly. The list is obviously not threadsafe.

func (*NodeDataCartEntryList) Iterate 

func (self *NodeDataCartEntryList) Iterate(cb func(v *NodeDataCartEntry))

func (*NodeDataCartEntryList) PushBack 

func (self *NodeDataCartEntryList) PushBack(v *NodeDataCartEntry) *NodeDataCartEntryListElement

func (*NodeDataCartEntryList) PushBackElement 

func (self *NodeDataCartEntryList) PushBackElement(e *NodeDataCartEntryListElement)

func (*NodeDataCartEntryList) PushFront 

func (self *NodeDataCartEntryList) PushFront(v *NodeDataCartEntry) *NodeDataCartEntryListElement

func (*NodeDataCartEntryList) PushFrontElement 

func (self *NodeDataCartEntryList) PushFrontElement(e *NodeDataCartEntryListElement)

func (*NodeDataCartEntryList) Remove 

func (self *NodeDataCartEntryList) Remove(e *NodeDataCartEntryListElement)

func (*NodeDataCartEntryList) RemoveElement 

func (self *NodeDataCartEntryList) RemoveElement(e *NodeDataCartEntryListElement)

func (*NodeDataCartEntryList) String 

func (self *NodeDataCartEntryList) String() string

type NodeDataCartEntryListElement 

type NodeDataCartEntryListElement struct {
	Prev, Next *NodeDataCartEntryListElement
	Value      *NodeDataCartEntry
}

type NodeDataChild 

type NodeDataChild struct {
	Key   Key    `zid:"0"`
	Value string `zid:"1"`
	// contains filtered or unexported fields
}

func (*NodeDataChild) DecodeMsg 

func (z *NodeDataChild) DecodeMsg(dc *msgp.Reader) (err error)

DecodeMsg implements msgp.Decodable We treat empty fields as if we read a Nil from the wire.

func (NodeDataChild) EncodeMsg 

func (z NodeDataChild) EncodeMsg(en *msgp.Writer) (err error)

EncodeMsg implements msgp.Encodable

func (NodeDataChild) MarshalMsg 

func (z NodeDataChild) MarshalMsg(b []byte) (o []byte, err error)

MarshalMsg implements msgp.Marshaler

func (NodeDataChild) Msgsize 

func (z NodeDataChild) Msgsize() (s int)

Msgsize returns an upper bound estimate of the number of bytes occupied by the serialized message

func (*NodeDataChild) String 

func (self *NodeDataChild) String() string

func (*NodeDataChild) UnmarshalMsg 

func (z *NodeDataChild) UnmarshalMsg(bts []byte) (o []byte, err error)

UnmarshalMsg implements msgp.Unmarshaler

func (*NodeDataChild) UnmarshalMsgWithCfg 

func (z *NodeDataChild) UnmarshalMsgWithCfg(bts []byte, cfg *msgp.RuntimeConfig) (o []byte, err error)

type Stack 

type Stack struct {
	// contains filtered or unexported fields
}

Stack is internal utility class which is used to keep trace about stack of nodes on the current immutable tree path (parents mainly).

If using lowlevel API (= direct calls to Node), passing empty one may be necessary. Otherwise Transaction should be used.

func (*Stack) Reset 

func (self *Stack) Reset()

Reset rests the Stack to ~factory defaults. It is still tied to particular tree though, and also calling it mid-operation is fatal error.

type SubTree 

type SubTree struct {
	// contains filtered or unexported fields
}

SubTree is convenience API for handling subtree of entries with common key prefix. Using the object, the tree behaves just like normal transaction (modulo few API calls that root transaction has to be used for).

func (*SubTree) Delete 

func (self *SubTree) Delete(key Key)

func (*SubTree) DeleteRange 

func (self *SubTree) DeleteRange(key1, key2 Key)

func (*SubTree) Get 

func (self *SubTree) Get(key Key) *string

func (*SubTree) NextKey 

func (self *SubTree) NextKey(key Key) *Key

func (*SubTree) PrevKey 

func (self *SubTree) PrevKey(key Key) *Key

func (*SubTree) Set 

func (self *SubTree) Set(key Key, value string)

type Transaction 

type Transaction struct {
	// contains filtered or unexported fields
}

Transaction is convenience API for dealing with the chaining of things in the ibtree. While API wise it is same as dealing with Nodes (and manual Stack allocation), there is no need to track the most recent access, and it is slightly more efficient as it maintains its own cache of most recent accesses within the built-in Stack.

func NewTransaction 

func NewTransaction(root *Node) *Transaction

func (*Transaction) Commit 

func (self *Transaction) Commit() (*Node, BlockId)

func (*Transaction) CommitTo 

func (self *Transaction) CommitTo(backend TreeSaver) (*Node, BlockId)

func (*Transaction) Delete 

func (self *Transaction) Delete(key Key)

func (*Transaction) DeleteRange 

func (self *Transaction) DeleteRange(key1, key2 Key)

func (*Transaction) Get 

func (self *Transaction) Get(key Key) *string

func (*Transaction) NewSubTree 

func (self *Transaction) NewSubTree(treePrefix Key) *SubTree

func (*Transaction) NextKey 

func (self *Transaction) NextKey(key Key) *Key

func (*Transaction) PrevKey 

func (self *Transaction) PrevKey(key Key) *Key

func (*Transaction) Root 

func (self *Transaction) Root() *Node

func (*Transaction) Set 

func (self *Transaction) Set(key Key, value string)

type Tree 

type Tree struct {
	// Can be provided externally
	NodeMaximumSize int
	// contains filtered or unexported fields
}

Tree represents static configuration that can be used over multiple B+ trees. If this is changed with existing trees, bad things WILL happen.

func (Tree) Init 

func (self Tree) Init(backend TreeBackend) *Tree

func (*Tree) LoadRoot 

func (self *Tree) LoadRoot(bid BlockId) *Node

func (*Tree) NewRoot 

func (self *Tree) NewRoot() *Node

NewRoot creates a new node; by default, it is essentially new tree of its own. Tree is really just factory for root nodes.

type TreeBackend 

type TreeBackend interface {
	TreeLoader
	TreeSaver
}

type TreeLoader 

type TreeLoader interface {
	// LoadNode loads node based on backend id.
	LoadNode(id BlockId) *NodeData
}

type TreeSaver 

type TreeSaver interface {
	// SaveNode persists the node, and returns the backend id for it.
	SaveNode(nd *NodeData) BlockId
}

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.