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

• type ART
  • func NewART(lock LockKind, ownership Ownership, calcMemory bool) (*ART, int)
  • func (art *ART) Close() error
  • func (art *ART) Delete(key nogc.FatPointer) nogc.Pointer
  • func (art *ART) DeleteValue(key nogc.FatPointer) (uint64, bool)
  • func (art *ART) Free()
  • func (art *ART) Get(key nogc.FatPointer) (nogc.Pointer, bool)
  • func (art *ART) GetValue(key nogc.FatPointer) (uint64, bool)
  • func (art *ART) Maximum() *Leaf
  • func (art *ART) Memory() int64
  • func (art *ART) MinMax() (*Leaf, *Leaf)
  • func (art *ART) Minimum() *Leaf
  • func (art *ART) Put(key nogc.FatPointer, value nogc.Pointer) nogc.Pointer
  • func (art *ART) PutNoReplace(key nogc.FatPointer, value nogc.Pointer) nogc.Pointer
  • func (art *ART) PutNoReplaceValue(key nogc.FatPointer, value uint64) (uint64, bool)
  • func (art *ART) PutValue(key nogc.FatPointer, value uint64) (uint64, bool)
  • func (art *ART) Size() int64
• type Leaf
  • func (l *Leaf) Data() Value
  • func (l *Leaf) Key() nogc.FatPointer
• type LockKind
• type Ownership
• type Value

Types

type ART

type ART C.art_tree

func NewART

func NewART(lock LockKind, ownership Ownership, calcMemory bool) (*ART, int)

func (*ART) Close

func (art *ART) Close() error

func (*ART) Delete

func (art *ART) Delete(key nogc.FatPointer) nogc.Pointer

func (*ART) DeleteValue

func (art *ART) DeleteValue(key nogc.FatPointer) (uint64, bool)

func (*ART) Free

func (art *ART) Free()

func (*ART) Get

func (art *ART) Get(key nogc.FatPointer) (nogc.Pointer, bool)

func (*ART) GetValue

func (art *ART) GetValue(key nogc.FatPointer) (uint64, bool)

func (*ART) Maximum

func (art *ART) Maximum() *Leaf

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

func (*ART) Memory

func (art *ART) Memory() int64

func (*ART) MinMax

func (art *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 (art *ART) Minimum() *Leaf

func (*ART) Put

func (art *ART) Put(key nogc.FatPointer, value nogc.Pointer) nogc.Pointer

func (*ART) PutNoReplace

func (art *ART) PutNoReplace(key nogc.FatPointer, value nogc.Pointer) nogc.Pointer

func (*ART) PutNoReplaceValue

func (art *ART) PutNoReplaceValue(key nogc.FatPointer, value uint64) (uint64, bool)

func (*ART) PutValue

func (art *ART) PutValue(key nogc.FatPointer, value uint64) (uint64, bool)

func (*ART) Size

func (art *ART) Size() int64

type Leaf

type Leaf C.art_leaf

func (*Leaf) Data

func (l *Leaf) Data() Value

func (*Leaf) Key

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

type LockKind

type LockKind uintptr

const (
	LockKindNone   LockKind = 0
	LockKindFair   LockKind = 1
	LockKindUnfair LockKind = 2
)

type Ownership

type Ownership uintptr

const (
	OwnershipNotOwned Ownership = 0
	OwnershipOwned    Ownership = 1
)

type Value

type Value struct {
	Data uint64
}