Documentation ¶
Overview ¶
Package redblacktree provides a pure Golang implementation of a red-black tree as described by Thomas H. Cormen's et al. in their seminal Algorithms book (3rd ed). This data structure is not multi-goroutine safe.
Index ¶
- Constants
- Variables
- func AssociationComparator(o1, o2 interface{}) int
- func Debug(value string)
- func Info(value string)
- func IntComparator(o1, o2 interface{}) int
- func KeyComparator(o1, o2 interface{}) int
- func OpenDBRead(filename string) (bool, *os.File)
- func PointerValueComparator(o1, o2 interface{}) int
- func SetOutput(w io.Writer)
- func StringComparator(o1, o2 interface{}) int
- func TraceOff()
- func TraceOn()
- func UInt64Comparator(o1, o2 interface{}) int
- func UniqueAssociationComparator(o1, o2 interface{}) int
- func UniqueAssociationExtComparator(o1, o2 interface{}) int
- func UniqueValueComparator(o1, o2 interface{}) int
- func ValueComparator(o1, o2 interface{}) int
- type Association
- type AssociationExt
- type ChanVisitor
- type Collection
- type CollectionKey
- type Color
- type Comparator
- type Direction
- type Entry
- type FileEntry
- type FileIndexer
- type FileMod
- type InnerJoinVisitor
- type InorderVisitor
- type InternalCollection
- func (ic *InternalCollection) Add(key string, value1 string, value2 string) *Association
- func (ic *InternalCollection) AssociateExt(entry1, relation_collection, relation, entry2_collection, entry2 string) *Association
- func (ic *InternalCollection) BufToAssociation(buf []byte, pos int64) Association
- func (ic *InternalCollection) BufToAssociationExt(buf []byte, pos int64) AssociationExt
- func (ic *InternalCollection) BufToEntry(buf []byte, pos int64) Entry
- func (ic *InternalCollection) CloseDB()
- func (ic *InternalCollection) Collection(name string) Collection
- func (ic *InternalCollection) DBWriter()
- func (ic *InternalCollection) Delete(key string, value1 string, value2 string) (bool, string)
- func (ic *InternalCollection) DeleteAssociation(tree *Tree, key UniqueAssociation, a *Association)
- func (ic *InternalCollection) DeleteEntry(e *Entry)
- func (ic *InternalCollection) Get(key string, value1 string) (bool, *StringSliceSet)
- func (ic *InternalCollection) GetAssociations(value string) (bool, *Tree)
- func (ic *InternalCollection) GetAssociationsExt(value string, entryCollection string) (bool, *Tree)
- func (ic *InternalCollection) GetAssociationsExtFromEntry(e *Entry) *Tree
- func (ic *InternalCollection) GetAssociationsFromEntry(e *Entry) *Tree
- func (ic *InternalCollection) GetEntry(level int, id uint64) *Entry
- func (ic *InternalCollection) GetEntryFromString(value string) (bool, *Entry)
- func (ic *InternalCollection) GetTotalEntries() uint64
- func (ic *InternalCollection) GetUniqueAssociation(key *Entry, value1 *Entry, value2 *Entry) (bool, *Association)
- func (ic *InternalCollection) GetValue(level int, id uint64) []byte
- func (ic *InternalCollection) GetValueString(level int, id uint64) string
- func (ic *InternalCollection) GetValueStringFromEntry(e *Entry) string
- func (ic *InternalCollection) Insert(value string) *Entry
- func (ic *InternalCollection) InsertAllEntries()
- func (ic *InternalCollection) InsertAssociation(level int, a *Association)
- func (ic *InternalCollection) InsertAssociationAdder(level int)
- func (ic *InternalCollection) InsertAssociationExt(level int, a *AssociationExt)
- func (ic *InternalCollection) InsertAssociationExtAdder(level int)
- func (ic *InternalCollection) InsertEntry(level int, e *Entry)
- func (t *InternalCollection) InsertEntryAdder(level int)
- func (ic *InternalCollection) InsertValue(level int, parentId uint64, value []byte) *Entry
- func (ic *InternalCollection) InternalCollection(level int, id uint64) *InternalCollection
- func (ic *InternalCollection) InternalCollectionFromString(name string) *InternalCollection
- func (t *InternalCollection) LoadDB(db *os.File)
- func (ic *InternalCollection) NextID() uint64
- func (t *InternalCollection) OpenDBUpdate() *os.File
- func (t *InternalCollection) OpenDBWrite() *os.File
- func (ic *InternalCollection) SecureLevelInIndex(level int)
- func (ic *InternalCollection) SetToString(value string, relationFilter string, s *Tree) (*StringSliceSet, []*Tree)
- func (ic *InternalCollection) SetToString2(value string, relationFilter string, s *Tree) (*StringSliceSet, []*Tree)
- func (ic *InternalCollection) SimpleUpdate(key string, value1 string, newValue2 string, addOnFail bool) (bool, string)
- func (ic *InternalCollection) SimpleUpdateUsingSet(key string, value1 string, newValue2 string, addOnFail bool, ...) (bool, string)
- func (ic *InternalCollection) Sync()
- func (ic *InternalCollection) Update(key string, value1 string, value2 string, newValue2 string) (bool, string)
- func (ic *InternalCollection) UpdateAdd(key string, value1 string, value2 string, newValue2 string) (bool, string)
- func (ic *InternalCollection) ValueExists(level int, parentId uint64, value []byte) (bool, *Entry)
- func (t *InternalCollection) WriteRandomDB(filename string)
- type Node
- type Set
- type StringSliceSet
- type Tree
- func (t *Tree) Delete(key interface{})
- func (t *Tree) Get(key interface{}) (bool, interface{})
- func (db *Tree) GetCollection(key CollectionKey) Collection
- func (t *Tree) GetKey(key interface{}) (bool, interface{})
- func (t *Tree) GetParent(key interface{}) (found bool, parent *Node, dir Direction)
- func (t *Tree) Has(key interface{}) bool
- func (t *Tree) HasKeyComparator(cmp Comparator, key interface{}) bool
- func (t1 *Tree) InnerJoin(t2 *Tree, cmp Comparator) *Tree
- func (t *Tree) Put(key interface{}, data interface{}) error
- func (t *Tree) RotateLeft(x *Node)
- func (t *Tree) RotateRight(y *Node)
- func (t *Tree) Size() uint64
- func (t *Tree) SizeNested() uint64
- func (t *Tree) Walk(visitor Visitor)
- type UniqueAssociation
- type UniqueAssociationExt
- type UniqueValue
- type Visitable
- type Visitor
Constants ¶
const ( ENTRY_SIZE = SIZE_DATATYPE + SIZE_LEVEL + SIZE_ID + SIZE_PARENTID + SIZE_VALUE SIZE_DATATYPE = 2 SIZE_LEVEL = 8 SIZE_ID = 8 SIZE_PARENTID = SIZE_ID // SIZE_VALUE = 72 // 12 * 8 - 3 * 8 SIZE_VALUE = 24 // 6 * 8 - 3 * 8 MaxFreespace = 1000000 FILE_APPEND = iota FILE_UPDATE FILE_DELETE // Do not change order; these values get written to the db files TYPE_DELETE = iota TYPE_ENTRY TYPE_ASSOCIATION TYPE_ASSOCIATIONEXT ASSOCIATED = "associated" )
Variables ¶
var ( ErrorKeyIsNil = errors.New("The literal nil not allowed as keys") ErrorKeyDisallowed = errors.New("Disallowed key type") )
Functions ¶
func AssociationComparator ¶
func AssociationComparator(o1, o2 interface{}) int
func IntComparator ¶
func IntComparator(o1, o2 interface{}) int
Default comparator expects keys to be of type `int`. Warning: if either one of `o1` or `o2` cannot be asserted to `int`, it panics.
func KeyComparator ¶
func KeyComparator(o1, o2 interface{}) int
func PointerValueComparator ¶
func PointerValueComparator(o1, o2 interface{}) int
func StringComparator ¶
func StringComparator(o1, o2 interface{}) int
Keys of type `string`. Warning: if either one of `o1` or `o2` cannot be asserted to `string`, it panics.
func UInt64Comparator ¶
func UInt64Comparator(o1, o2 interface{}) int
func UniqueAssociationComparator ¶
func UniqueAssociationComparator(o1, o2 interface{}) int
func UniqueAssociationExtComparator ¶
func UniqueAssociationExtComparator(o1, o2 interface{}) int
func UniqueValueComparator ¶
func UniqueValueComparator(o1, o2 interface{}) int
func ValueComparator ¶
func ValueComparator(o1, o2 interface{}) int
Types ¶
type Association ¶
type Association struct { // CollectionLevel int // Collection uint64 EntryId uint64 Level int // AssociationCollectionLevel int // AssociationCollection uint64 AssociationLevel int AssociateTo uint64 // RelationCollectionLevel int // RelationCollection uint64 RelationLevel int Relation uint64 Position int64 }
func (*Association) GetPosition ¶
func (a *Association) GetPosition() int64
func (*Association) SetPosition ¶
func (a *Association) SetPosition(pos int64)
func (*Association) ToBytes ¶
func (a *Association) ToBytes() []byte
type AssociationExt ¶
type AssociationExt struct { AssociateTo uint64 Relation uint64 AssociationCollectionLevel int AssociationCollection uint64 RelationCollectionLevel int RelationCollection uint64 Position int64 }
func (*AssociationExt) GetPosition ¶
func (a *AssociationExt) GetPosition() int64
func (*AssociationExt) SetPosition ¶
func (a *AssociationExt) SetPosition(pos int64)
func (*AssociationExt) ToBytes ¶
func (a *AssociationExt) ToBytes() []byte
type ChanVisitor ¶
type ChanVisitor struct {
Ch chan interface{}
}
Chan visitor visitis each node in a tree and puts the payload on channel
func (*ChanVisitor) Visit ¶
func (v *ChanVisitor) Visit(node *Node)
type Collection ¶
type Collection interface { Collection(name string) Collection Add(key, value1, value2 string) *Association Get(key string, value1 string) (bool, *StringSliceSet) GetAssociations(value string) (bool, *Tree) GetAssociationsExt(value string, entryCollection string) (bool, *Tree) SetToString(value string, relationFilter string, s *Tree) (*StringSliceSet, []*Tree) Update(key string, value1 string, value2 string, newValue2 string) (bool, string) UpdateAdd(key string, value1 string, value2 string, newValue2 string) (bool, string) SimpleUpdate(key string, value1 string, newValue2 string, addOnFail bool) (bool, string) SimpleUpdateUsingSet(key string, value1 string, newValue2 string, addOnFail bool, set *StringSliceSet) (bool, string) Delete(key string, value1 string, value2 string) (bool, string) CloseDB() }
type CollectionKey ¶
type Comparator ¶
type Comparator func(o1, o2 interface{}) int
Keys must be comparable. It's mandatory to provide a Comparator, which returns zero if o1 == o2, -1 if o1 < o2, 1 if o1 > o2
type Entry ¶
type Entry struct { Id uint64 Level int UniqueValue UniqueValue Position int64 }
func (*Entry) GetPosition ¶
func (*Entry) SetPosition ¶
type FileIndexer ¶
type FileIndexer interface {
// contains filtered or unexported methods
}
type InnerJoinVisitor ¶
type InnerJoinVisitor struct {
Tree *Tree
}
func (*InnerJoinVisitor) Visit ¶
func (v *InnerJoinVisitor) Visit(cmp Comparator, node *Node, tree *Tree)
type InorderVisitor ¶
type InorderVisitor struct {
// contains filtered or unexported fields
}
InorderVisitor walks the tree in inorder fashion. This visitor maintains internal state; thus do not reuse after the completion of a walk.
func (*InorderVisitor) Eq ¶
func (v *InorderVisitor) Eq(other *InorderVisitor) bool
func (*InorderVisitor) String ¶
func (v *InorderVisitor) String() string
func (*InorderVisitor) Visit ¶
func (v *InorderVisitor) Visit(node *Node)
type InternalCollection ¶
type InternalCollection struct { TotalEntries uint64 TotalAsses uint64 InserterWG sync.WaitGroup InserterWGAssociation sync.WaitGroup InserterWGAssociationExt sync.WaitGroup InserterWGDynTrie sync.WaitGroup Root Entry RootAss Association Entries []*Tree EntryAdder []chan *Entry AssociationAdder []chan *Association AssociationExtAdder []chan *AssociationExt UniqueValues []*Tree Values *Tree Associations []*Tree AssociationsExt []*Tree SubCollections []*Tree Freespace chan FileEntry DBPath string DBName string DBFullPath string DBWriteQueue chan FileMod DBCloseWriter chan bool WriteToDisk bool // Finished chan bool Finished sync.WaitGroup Level int Id uint64 // contains filtered or unexported fields }
func Initialize ¶
func Initialize(path string, dbname string, clearExistingDB bool, writeToDisk bool) *InternalCollection
func (*InternalCollection) Add ¶
func (ic *InternalCollection) Add(key string, value1 string, value2 string) *Association
func (*InternalCollection) AssociateExt ¶
func (ic *InternalCollection) AssociateExt(entry1, relation_collection, relation, entry2_collection, entry2 string) *Association
TODO: Rename relation to value1, entry1 = key, entry2 = value2
func (*InternalCollection) BufToAssociation ¶
func (ic *InternalCollection) BufToAssociation(buf []byte, pos int64) Association
out = append(datatype[:], entry_level[:]...) out = append(out, entry_id[:]...) out = append(out, association_level[:]...) out = append(out, association[:]...) out = append(out, relation_level[:]...) out = append(out, relation[:]...)
func (*InternalCollection) BufToAssociationExt ¶
func (ic *InternalCollection) BufToAssociationExt(buf []byte, pos int64) AssociationExt
func (*InternalCollection) BufToEntry ¶
func (ic *InternalCollection) BufToEntry(buf []byte, pos int64) Entry
func (*InternalCollection) CloseDB ¶
func (ic *InternalCollection) CloseDB()
func (*InternalCollection) Collection ¶
func (ic *InternalCollection) Collection(name string) Collection
func (*InternalCollection) DBWriter ¶
func (ic *InternalCollection) DBWriter()
func (*InternalCollection) DeleteAssociation ¶
func (ic *InternalCollection) DeleteAssociation(tree *Tree, key UniqueAssociation, a *Association)
func (*InternalCollection) DeleteEntry ¶
func (ic *InternalCollection) DeleteEntry(e *Entry)
func (*InternalCollection) Get ¶
func (ic *InternalCollection) Get(key string, value1 string) (bool, *StringSliceSet)
func (*InternalCollection) GetAssociations ¶
func (ic *InternalCollection) GetAssociations(value string) (bool, *Tree)
func (*InternalCollection) GetAssociationsExt ¶
func (ic *InternalCollection) GetAssociationsExt(value string, entryCollection string) (bool, *Tree)
func (*InternalCollection) GetAssociationsExtFromEntry ¶
func (ic *InternalCollection) GetAssociationsExtFromEntry(e *Entry) *Tree
func (*InternalCollection) GetAssociationsFromEntry ¶
func (ic *InternalCollection) GetAssociationsFromEntry(e *Entry) *Tree
func (*InternalCollection) GetEntry ¶
func (ic *InternalCollection) GetEntry(level int, id uint64) *Entry
func (*InternalCollection) GetEntryFromString ¶
func (ic *InternalCollection) GetEntryFromString(value string) (bool, *Entry)
func (*InternalCollection) GetTotalEntries ¶
func (ic *InternalCollection) GetTotalEntries() uint64
func (*InternalCollection) GetUniqueAssociation ¶
func (ic *InternalCollection) GetUniqueAssociation(key *Entry, value1 *Entry, value2 *Entry) (bool, *Association)
func (*InternalCollection) GetValue ¶
func (ic *InternalCollection) GetValue(level int, id uint64) []byte
Returns a copy of full value
func (*InternalCollection) GetValueString ¶
func (ic *InternalCollection) GetValueString(level int, id uint64) string
func (*InternalCollection) GetValueStringFromEntry ¶
func (ic *InternalCollection) GetValueStringFromEntry(e *Entry) string
func (*InternalCollection) Insert ¶
func (ic *InternalCollection) Insert(value string) *Entry
func (*InternalCollection) InsertAllEntries ¶
func (ic *InternalCollection) InsertAllEntries()
func (*InternalCollection) InsertAssociation ¶
func (ic *InternalCollection) InsertAssociation(level int, a *Association)
func (*InternalCollection) InsertAssociationAdder ¶
func (ic *InternalCollection) InsertAssociationAdder(level int)
func (*InternalCollection) InsertAssociationExt ¶
func (ic *InternalCollection) InsertAssociationExt(level int, a *AssociationExt)
func (*InternalCollection) InsertAssociationExtAdder ¶
func (ic *InternalCollection) InsertAssociationExtAdder(level int)
func (*InternalCollection) InsertEntry ¶
func (ic *InternalCollection) InsertEntry(level int, e *Entry)
func (*InternalCollection) InsertEntryAdder ¶
func (t *InternalCollection) InsertEntryAdder(level int)
func (*InternalCollection) InsertValue ¶
func (ic *InternalCollection) InsertValue(level int, parentId uint64, value []byte) *Entry
func (*InternalCollection) InternalCollection ¶
func (ic *InternalCollection) InternalCollection(level int, id uint64) *InternalCollection
func (*InternalCollection) InternalCollectionFromString ¶
func (ic *InternalCollection) InternalCollectionFromString(name string) *InternalCollection
func (*InternalCollection) LoadDB ¶
func (t *InternalCollection) LoadDB(db *os.File)
func (*InternalCollection) NextID ¶
func (ic *InternalCollection) NextID() uint64
func (*InternalCollection) OpenDBUpdate ¶
func (t *InternalCollection) OpenDBUpdate() *os.File
func (*InternalCollection) OpenDBWrite ¶
func (t *InternalCollection) OpenDBWrite() *os.File
func (*InternalCollection) SecureLevelInIndex ¶
func (ic *InternalCollection) SecureLevelInIndex(level int)
func (*InternalCollection) SetToString ¶
func (ic *InternalCollection) SetToString(value string, relationFilter string, s *Tree) (*StringSliceSet, []*Tree)
func (*InternalCollection) SetToString2 ¶
func (ic *InternalCollection) SetToString2(value string, relationFilter string, s *Tree) (*StringSliceSet, []*Tree)
New implementation of SetToString using new output format
func (*InternalCollection) SimpleUpdate ¶
func (ic *InternalCollection) SimpleUpdate(key string, value1 string, newValue2 string, addOnFail bool) (bool, string)
Update first occurence of a value2. More expensive SimpleUpdateUsingSet - use that if udating many values
func (*InternalCollection) SimpleUpdateUsingSet ¶
func (ic *InternalCollection) SimpleUpdateUsingSet(key string, value1 string, newValue2 string, addOnFail bool, set *StringSliceSet) (bool, string)
Update first occurence of a value2
func (*InternalCollection) Sync ¶
func (ic *InternalCollection) Sync()
func (*InternalCollection) UpdateAdd ¶
func (ic *InternalCollection) UpdateAdd(key string, value1 string, value2 string, newValue2 string) (bool, string)
Try to update value2 to newvalue2. Add if unsuccessful. TODO: Add error checking
func (*InternalCollection) ValueExists ¶
func (*InternalCollection) WriteRandomDB ¶
func (t *InternalCollection) WriteRandomDB(filename string)
Used for testing worst-case scenario
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
A node needs to be able to answer the query: (i) Who is my parent node ? (ii) Who is my grandparent node ? The zero value for Node has color Red.
type StringSliceSet ¶
func (*StringSliceSet) FirstValue1 ¶
func (set *StringSliceSet) FirstValue1() string
Returns first Value1 or empty string if non-existant
func (*StringSliceSet) FirstValue2 ¶
func (set *StringSliceSet) FirstValue2() string
Returns first Value2 or empty string if non-existant
type Tree ¶
type Tree struct {
// contains filtered or unexported fields
}
Tree encapsulates the data structure.
func NewTree ¶
NewTree returns an empty Tree with default comparator `IntComparator`. `IntComparator` expects keys to be type-assertable to `int`.
func NewTreeWith ¶
func NewTreeWith(c Comparator, writeToDisk bool) *Tree
NewTreeWith returns an empty Tree with a supplied `Comparator`.
func (*Tree) Delete ¶
func (t *Tree) Delete(key interface{})
Delete removes the item identified by the supplied key. Delete is a noop if the supplied key doesn't exist.
func (*Tree) Get ¶
Get looks for the node with supplied key and returns its mapped payload. Return value in 1st position indicates whether any payload was found.
func (*Tree) GetCollection ¶
func (db *Tree) GetCollection(key CollectionKey) Collection
func (*Tree) GetParent ¶
GetParent looks for the node with supplied key and returns the parent node.
func (*Tree) HasKeyComparator ¶
func (t *Tree) HasKeyComparator(cmp Comparator, key interface{}) bool
func (*Tree) InnerJoin ¶
func (t1 *Tree) InnerJoin(t2 *Tree, cmp Comparator) *Tree
Returns intersection of two trees
func (*Tree) Put ¶
Put saves the mapping (key, data) into the tree. If a mapping identified by `key` already exists, it is overwritten. Constraint: Not everything can be a key.
func (*Tree) RotateLeft ¶
Side-effect: red-black tree properties is maintained.