rb_tree

Documentation

Index

• Constants
• Variables
• func Init(stub cached_stub.CachedStubInterface, logLevel ...shim.LoggingLevel) ([]byte, error)
• type RBTree
  • func NewRBTree(stub cached_stub.CachedStubInterface, treeName string) *RBTree
  • func (t *RBTree) BiggerParent(n node) (node, error)
  • func (t *RBTree) DelNode(n node) error
  • func (t *RBTree) DelStateCached(key string) error
  • func (t *RBTree) FindMin(n node) (node, error)
  • func (t *RBTree) FindRoot(n node) (node, error)
  • func (t *RBTree) Get(key string) ([]byte, error)
  • func (t *RBTree) GetKeyByPartialCompositeKey(objectType string, keys []string) (shim.StateQueryIteratorInterface, error)
  • func (t *RBTree) GetKeyByRange(startKey, endKey string) (shim.StateQueryIteratorInterface, error)
  • func (t *RBTree) GetNode(key string) (node, error)
  • func (t *RBTree) GetNodeLedgerKey(n node) string
  • func (t *RBTree) GetRoot() (node, error)
  • func (t *RBTree) GetStateCached(key string) ([]byte, error)
  • func (t *RBTree) Grandparent(n node) (node, error)
  • func (t *RBTree) Insert(key string, value []byte) error
  • func (t *RBTree) NewTreeIter(startKey string, endKey string, ascending bool) (*TreeIter, error)
  • func (t *RBTree) Parent(n node) (node, error)
  • func (t *RBTree) PrintTree(filename string, currentNode interface{}) error
  • func (t *RBTree) PutStateCached(key string, value []byte) error
  • func (t *RBTree) Remove(key string) error
  • func (t *RBTree) RotateLeft(n node) error
  • func (t *RBTree) RotateRight(n node) error
  • func (t *RBTree) SaveNode(n node) error
  • func (t *RBTree) SaveRoot(r node) error
  • func (t *RBTree) SaveToLedger() error
  • func (t *RBTree) Search(key string) (node, error)
  • func (t *RBTree) SearchNext(n node) (node, error)
  • func (t *RBTree) Sibling(n node) (node, error)
  • func (t *RBTree) Uncle(n node) (node, error)
• type TreeIter
  • func (tIter *TreeIter) Close() error
  • func (tIter *TreeIter) HasNext() bool
  • func (tIter *TreeIter) Next() (*queryresult.KV, error)

Constants

const BLACK = "B"

const LEAF = ""

const PREFIX = "RBT_"

const RED = "R"

Variables

var DEBUG_PRINT_TREE = false

* The following implementation of Red-Black tree has been implemented * following the implementation example of the following site: * https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

var DEBUG_TREE = false

var NULL = node{Key: "", Value: nil, Parent: "", Color: BLACK, Left: LEAF, Right: LEAF}

Functions

func Init

func Init(stub cached_stub.CachedStubInterface, logLevel ...shim.LoggingLevel) ([]byte, error)

Init sets up the datastore package by adding default ledger connection.

Types

type RBTree

type RBTree struct {
	Stub     cached_stub.CachedStubInterface
	Cache    map[string][]byte
	ToDelete map[string]bool
	TreeName string
	Prefix   string
	Root     string
}

func NewRBTree

func NewRBTree(stub cached_stub.CachedStubInterface, treeName string) *RBTree

func (*RBTree) BiggerParent

func (t *RBTree) BiggerParent(n node) (node, error)

return the first parent whose key is greater than current node

func (*RBTree) DelNode

func (t *RBTree) DelNode(n node) error

func (*RBTree) DelStateCached

func (t *RBTree) DelStateCached(key string) error

func (*RBTree) FindMin

func (t *RBTree) FindMin(n node) (node, error)

func (*RBTree) FindRoot

func (t *RBTree) FindRoot(n node) (node, error)

find root starting from a node n

func (*RBTree) Get

func (t *RBTree) Get(key string) ([]byte, error)

get value of the key

func (*RBTree) GetKeyByPartialCompositeKey

func (t *RBTree) GetKeyByPartialCompositeKey(objectType string, keys []string) (shim.StateQueryIteratorInterface, error)

func (*RBTree) GetKeyByRange

func (t *RBTree) GetKeyByRange(startKey, endKey string) (shim.StateQueryIteratorInterface, error)

func (*RBTree) GetNode

func (t *RBTree) GetNode(key string) (node, error)

func (*RBTree) GetNodeLedgerKey

func (t *RBTree) GetNodeLedgerKey(n node) string

func (*RBTree) GetRoot

func (t *RBTree) GetRoot() (node, error)

func (*RBTree) GetStateCached

func (t *RBTree) GetStateCached(key string) ([]byte, error)

func (*RBTree) Grandparent

func (t *RBTree) Grandparent(n node) (node, error)

func (*RBTree) Insert

func (t *RBTree) Insert(key string, value []byte) error

func (*RBTree) NewTreeIter

func (t *RBTree) NewTreeIter(startKey string, endKey string, ascending bool) (*TreeIter, error)

startKey (inclusive) and endKey (exclusive)

func (*RBTree) Parent

func (t *RBTree) Parent(n node) (node, error)

Return Parent

func (*RBTree) PrintTree

func (t *RBTree) PrintTree(filename string, currentNode interface{}) error

func (*RBTree) PutStateCached

func (t *RBTree) PutStateCached(key string, value []byte) error

func (*RBTree) Remove

func (t *RBTree) Remove(key string) error

func (*RBTree) RotateLeft

func (t *RBTree) RotateLeft(n node) error

func (*RBTree) RotateRight

func (t *RBTree) RotateRight(n node) error

func (*RBTree) SaveNode

func (t *RBTree) SaveNode(n node) error

func (*RBTree) SaveRoot

func (t *RBTree) SaveRoot(r node) error

func (*RBTree) SaveToLedger

func (t *RBTree) SaveToLedger() error

func (*RBTree) Search

func (t *RBTree) Search(key string) (node, error)

search smallest node n that n.key >= key

func (*RBTree) SearchNext

func (t *RBTree) SearchNext(n node) (node, error)

search next smallest node whose key is greater than current node n

func (*RBTree) Sibling

func (t *RBTree) Sibling(n node) (node, error)

func (*RBTree) Uncle

func (t *RBTree) Uncle(n node) (node, error)

type TreeIter

type TreeIter struct {
	FirstKey    string //inclusive
	LastKey     string //exclusive
	NextNode    node
	CurrentNode node
	Tree        *RBTree
	Closed      bool
	Ascending   bool
}

func (*TreeIter) Close

func (tIter *TreeIter) Close() error

func (*TreeIter) HasNext

func (tIter *TreeIter) HasNext() bool

func (*TreeIter) Next

func (tIter *TreeIter) Next() (*queryresult.KV, error)