tree

README

libart

This library provides a C99 implementation of the Adaptive Radix Tree or ART. The ART operates similar to a traditional radix tree but avoids the wasted space of internal nodes by changing the node size. It makes use of 4 node sizes (4, 16, 48, 256), and can guarantee that the overhead is no more than 52 bytes per key, though in practice it is much lower.

As a radix tree, it provides the following:

• O(k) operations. In many cases, this can be faster than a hash table since the hash function is an O(k) operation, and hash tables have very poor cache locality.
• Minimum / Maximum value lookups
• Prefix compression
• Ordered iteration
• Prefix based iteration

References

Related works:

• The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases

Documentation

Index

• func BTreeInt64Compare() uintptr
• func Sleep(nanos time.Duration)
• func SleepUnsafe(nanos time.Duration)
• type ART
  • func NewART() (*ART, int)
  • func NewARTThreadSafe(threadSafe bool) (*ART, int)
  • func (t *ART) Bytes() int64
  • func (r *ART) Delete(key memory.Pointer, size int) memory.Pointer
  • func (r *ART) DeleteBytes(key memory.Bytes) memory.Pointer
  • func (r *ART) Find(key memory.Pointer, size int) Value
  • func (r *ART) FindBytes(key memory.Bytes) Value
  • func (r *ART) Free()
  • func (r *ART) Insert(key memory.Pointer, size int, value Value) Value
  • func (r *ART) InsertBytes(key memory.Bytes, value Value) Value
  • func (r *ART) InsertNoReplace(key memory.Pointer, size int, value Value) Value
  • func (r *ART) InsertNoReplaceBytes(key memory.Bytes, value Value) Value
  • func (r *ART) InsertNoReplaceSlice(key []byte, value Value) Value
  • func (r *ART) InsertNoReplaceString(key string, value Value) Value
  • func (r *ART) InsertSlice(key []byte, value Value) Value
  • func (r *ART) InsertString(key string, value Value) Value
  • func (t *ART) Lock() *RWLock
  • func (r *ART) Maximum() *Leaf
  • func (r *ART) MinMax() (*Leaf, *Leaf)
  • func (r *ART) Minimum() *Leaf
  • func (t *ART) Size() int64
• type BTree
  • func NewBTree(elsize, maxItems, compare, udata uintptr) *BTree
  • func (r *BTree) Delete(key int64) uintptr
  • func (r *BTree) DeleteHint(key int64, hint *uint64) uintptr
  • func (m *BTree) Free()
  • func (r *BTree) Get(key int64) uintptr
  • func (r *BTree) GetHint(key int64, hint *uint64) uintptr
  • func (r *BTree) Set(key int64, value uintptr) uintptr
  • func (r *BTree) SetHint(key int64, value uintptr, hint *uint64) uintptr
• type BTreeI64
• type BTreeRecordInt64
• type Leaf
  • func (l *Leaf) Data() memory.Pointer
  • func (l *Leaf) Key() memory.FatPointer
• type RWLock
  • func NewLock() *RWLock
  • func (l *RWLock) Free()
  • func (l *RWLock) Lock()
  • func (l *RWLock) LockShared()
  • func (l *RWLock) LockSharedUnsafe()
  • func (l *RWLock) LockUnsafe()
  • func (l *RWLock) Unlock()
  • func (l *RWLock) UnlockShared()
  • func (l *RWLock) UnlockSharedUnsafe()
  • func (l *RWLock) UnlockUnsafe()
• type Value

Functions

func BTreeInt64Compare

func BTreeInt64Compare() uintptr

func Sleep

func Sleep(nanos time.Duration)

func SleepUnsafe

func SleepUnsafe(nanos time.Duration)

Types

type ART

type ART C.art_tree

func NewART

func NewART() (*ART, int)

func NewARTThreadSafe

func NewARTThreadSafe(threadSafe bool) (*ART, int)

func (*ART) Bytes

func (t *ART) Bytes() int64

func (*ART) Delete

func (r *ART) Delete(key memory.Pointer, size int) memory.Pointer

func (*ART) DeleteBytes

func (r *ART) DeleteBytes(key memory.Bytes) memory.Pointer

func (*ART) Find

func (r *ART) Find(key memory.Pointer, size int) Value

func (*ART) FindBytes

func (r *ART) FindBytes(key memory.Bytes) Value

func (*ART) Free

func (r *ART) Free()

func (*ART) Insert

func (r *ART) Insert(key memory.Pointer, size int, value Value) Value

func (*ART) InsertBytes

func (r *ART) InsertBytes(key memory.Bytes, value Value) Value

func (*ART) InsertNoReplace

func (r *ART) InsertNoReplace(key memory.Pointer, size int, value Value) Value

func (*ART) InsertNoReplaceBytes

func (r *ART) InsertNoReplaceBytes(key memory.Bytes, value Value) Value

func (*ART) InsertNoReplaceSlice

func (r *ART) InsertNoReplaceSlice(key []byte, value Value) Value

func (*ART) InsertNoReplaceString

func (r *ART) InsertNoReplaceString(key string, value Value) Value

func (*ART) InsertSlice

func (r *ART) InsertSlice(key []byte, value Value) Value

func (*ART) InsertString

func (r *ART) InsertString(key string, value Value) Value

func (*ART) Lock

func (t *ART) Lock() *RWLock

func (*ART) Maximum

func (r *ART) Maximum() *Leaf

Maximum Returns the maximum valued leaf @return The maximum leaf or NULL

func (*ART) MinMax

func (r *ART) MinMax() (*Leaf, *Leaf)

MinMax Returns the minimum and maximum valued leaf @return The minimum and maximum leaf or NULL, NULL

func (*ART) Minimum

func (r *ART) Minimum() *Leaf

func (*ART) Size

func (t *ART) Size() int64

type BTree

type BTree C.struct_btree

func NewBTree

func NewBTree(elsize, maxItems, compare, udata uintptr) *BTree

func (*BTree) Delete

func (r *BTree) Delete(key int64) uintptr

func (*BTree) DeleteHint

func (r *BTree) DeleteHint(key int64, hint *uint64) uintptr

func (*BTree) Free

func (m *BTree) Free()

func (*BTree) Get

func (r *BTree) Get(key int64) uintptr

func (*BTree) GetHint

func (r *BTree) GetHint(key int64, hint *uint64) uintptr

func (*BTree) Set

func (r *BTree) Set(key int64, value uintptr) uintptr

func (*BTree) SetHint

func (r *BTree) SetHint(key int64, value uintptr, hint *uint64) uintptr

type BTreeI64

type BTreeI64 C.struct_btree

type BTreeRecordInt64

type BTreeRecordInt64 struct {
	Key   int64
	Value uintptr
}

type Leaf

type Leaf C.art_leaf

func (*Leaf) Data

func (l *Leaf) Data() memory.Pointer

func (*Leaf) Key

func (l *Leaf) Key() memory.FatPointer

type RWLock

type RWLock C.void

func NewLock

func NewLock() *RWLock

func (*RWLock) Free

func (l *RWLock) Free()

func (*RWLock) Lock

func (l *RWLock) Lock()

func (*RWLock) LockShared

func (l *RWLock) LockShared()

func (*RWLock) LockSharedUnsafe

func (l *RWLock) LockSharedUnsafe()

func (*RWLock) LockUnsafe

func (l *RWLock) LockUnsafe()

func (*RWLock) Unlock

func (l *RWLock) Unlock()

func (*RWLock) UnlockShared

func (l *RWLock) UnlockShared()

func (*RWLock) UnlockSharedUnsafe

func (l *RWLock) UnlockSharedUnsafe()

func (*RWLock) UnlockUnsafe

func (l *RWLock) UnlockUnsafe()

type Value

type Value struct {
	File   uint32
	Offset uint32
	Data   uintptr
}