tiedb

package module
v0.0.0-...-e06bc93 Latest Latest
Warning

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

 Go to latest Published: Apr 5, 2021 License: GPL-3.0 Imports: 11 Imported by: 1

README

tiedb

Golang package to associate and relate bytes/strings using a trie and red-black-trees.

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

View Source 
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"
)
View Source 
const (
	BLACK, RED Color     = true, false
	LEFT       Direction = iota
	RIGHT
	NODIR
)

Variables

View Source 
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 Debug 

func Debug(value string)

func Info 

func Info(value string)

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 OpenDBRead 

func OpenDBRead(filename string) (bool, *os.File)

func PointerValueComparator 

func PointerValueComparator(o1, o2 interface{}) int

func SetOutput 

func SetOutput(w io.Writer)

SetOutput redirects log output

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 TraceOff 

func TraceOff()

TraceOff turns off logging. By default logging is turned off.

func TraceOn 

func TraceOn()

TraceOn turns on logging output to Stderr

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
	GetAssociations(value string) (bool, *Tree)
	GetAssociationsExt(value string, entryCollection string) (bool, *Tree)
	SetToString(value string, relationFilter string, s *Tree) (*StringSliceSet, []*Tree)
	Update(entry1 string, entry2 string, relation string, newEntry2 string) (bool, string)
	Delete(entry1 string, entry2 string, relation string) (bool, string)
	CloseDB()
}

type CollectionKey 

type CollectionKey struct {
	Database   string
	Collection string
}

type Color 

type Color bool

Color of a redblack tree node is either `Black` (true) & `Red` (false)

func (Color) String 

func (c Color) String() string

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 Direction 

type Direction byte

Direction points to either the Left or Right subtree

func (Direction) String 

func (d Direction) String() string

type Entry 

type Entry struct {
	Id          uint64
	Level       int
	UniqueValue UniqueValue
	Position    int64
}

func (*Entry) GetPosition 

func (e *Entry) GetPosition() int64

func (*Entry) SetPosition 

func (e *Entry) SetPosition(pos int64)

func (*Entry) ToBytes 

func (e *Entry) ToBytes() []byte

type FileEntry 

type FileEntry interface {
	ToBytes() []byte
	SetPosition(int64)
	GetPosition() int64
}

type FileIndexer 

type FileIndexer interface {
	// contains filtered or unexported methods
}

type FileMod 

type FileMod struct {
	Mode  int
	Entry FileEntry
}

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
	// 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) *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) Delete 

func (ic *InternalCollection) Delete(entry1 string, entry2 string, relation string) (bool, string)

func (*InternalCollection) DeleteAssociation 

func (ic *InternalCollection) DeleteAssociation(tree *Tree, key UniqueAssociation, a *Association)

func (*InternalCollection) DeleteEntry 

func (ic *InternalCollection) DeleteEntry(e *Entry)

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)

TODO: Bug - does not return if no associations func SetToString(value string, s *Tree, ic *InternalCollection, cf CollectionFunc) *StringSliceSet { 

func (ic *InternalCollection) SetToString(value string, s *Tree) *StringSliceSet {
	, valueCollection string,
}

func (*InternalCollection) Sync 

func (ic *InternalCollection) Sync()

func (*InternalCollection) Update 

func (ic *InternalCollection) Update(entry1 string, entry2 string, relation string, newEntry2 string) (bool, string)

func (*InternalCollection) ValueExists 

func (ic *InternalCollection) ValueExists(level int, parentId uint64, value []byte) (bool, *Entry)

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.

func (*Node) Color 

func (n *Node) Color() Color

func (*Node) Parent 

func (n *Node) Parent() *Node

func (*Node) SetColor 

func (n *Node) SetColor(color Color)

func (*Node) String 

func (n *Node) String() string

type StringSliceSet 

type StringSliceSet struct {
	Item         string
	Keys         []string
	Associations []string
	Relations    []string
}

type Tree 

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

Tree encapsulates the data structure.

func NewDB 

func NewDB() *Tree

func NewTree 

func NewTree() *Tree

NewTree returns an empty Tree with default comparator `IntComparator`. `IntComparator` expects keys to be type-assertable to `int`.

func NewTreeWith 

func NewTreeWith(c Comparator) *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 

func (t *Tree) Get(key interface{}) (bool, interface{})

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) GetKey 

func (t *Tree) GetKey(key interface{}) (bool, interface{})

func (*Tree) GetParent 

func (t *Tree) GetParent(key interface{}) (found bool, parent *Node, dir Direction)

GetParent looks for the node with supplied key and returns the parent node.

func (*Tree) Has 

func (t *Tree) Has(key interface{}) bool

Has checks for existence of a item identified by supplied key.

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 

func (t *Tree) Put(key interface{}, data interface{}) error

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 

func (t *Tree) RotateLeft(x *Node)

Side-effect: red-black tree properties is maintained.

func (*Tree) RotateRight 

func (t *Tree) RotateRight(y *Node)

Reverses actions of RotateLeft

func (*Tree) Size 

func (t *Tree) Size() uint64

Size returns the number of items in the tree.

func (*Tree) SizeNested 

func (t *Tree) SizeNested() uint64

func (*Tree) Walk 

func (t *Tree) Walk(visitor Visitor)

Walk accepts a Visitor

type UniqueAssociation 

type UniqueAssociation struct {
	// AssociateToCollectionLevel int
	// AssociateToCollection uint64
	AssociateTo uint64
	// RelationCollectionLevel    int
	// RelationCollection uint64
	Relation uint64
}

type UniqueAssociationExt 

type UniqueAssociationExt struct {
	// AssociateToCollectionLevel int
	AssociateToCollection uint64
	AssociateTo           uint64
	// RelationCollectionLevel int
	RelationCollection uint64
	Relation           uint64
}

type UniqueValue 

type UniqueValue struct {
	ParentId uint64
	Value    *[]byte
}

type Visitable 

type Visitable interface {
	Walk(Visitor)
}

A redblack tree is `Visitable` by a `Visitor`.

type Visitor 

type Visitor interface {
	Visit(*Node)
}

Source Files

View all Source files

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.