nodetable

Documentation

Overview

Package nodetable implements high performance GC optimized Node lookup table for Nitro index storage. This table is not thread-safe

Golang map does not need to pay the cost of GC scans if you have native fixed size types for both key and value. We use two tables for the node lookup table implementation. Fast table and slow table. Fast table stores maps crc32(key) to a uint64. Value is a pointer to a skiplist node. Highest bit is used to indicate whether there is any hash collision for the crc32 key used. If the bit is set, that means we need to lookup second table, which is the slow table. Slow table has multiple entries which are mapped by the same crc32 key.

Index

• func CompareNodeTable(a, b unsafe.Pointer) int
• func MemoryInUse() (sz int64)
• type EqualKeyFn
• type HashFn
• type NodeTable
  • func New(hfn HashFn, kfn EqualKeyFn) *NodeTable
  • func (nt *NodeTable) Close()
  • func (nt *NodeTable) Get(key []byte) unsafe.Pointer
  • func (nt *NodeTable) MemoryInUse() int64
  • func (nt *NodeTable) Remove(key []byte) (success bool, nptr unsafe.Pointer)
  • func (nt *NodeTable) Stats() string
  • func (nt *NodeTable) Update(key []byte, nptr unsafe.Pointer) (updated bool, oldPtr unsafe.Pointer)

Functions

func CompareNodeTable

func CompareNodeTable(a, b unsafe.Pointer) int

CompareNodeTable implements comparator for nodetable instances

func MemoryInUse

func MemoryInUse() (sz int64)

MemoryInUse returns total memory used by nodetables in a process

Types

type EqualKeyFn

type EqualKeyFn func(unsafe.Pointer, []byte) bool

EqualKeyFn implements key equality check

type HashFn

type HashFn func([]byte) uint32

HashFn implements 32bit hash function on a string

type NodeTable

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

NodeTable describes lookup table

func New

func New(hfn HashFn, kfn EqualKeyFn) *NodeTable

New creates a nodetable instance

func (*NodeTable) Close

func (nt *NodeTable) Close()

Close destroys the nodetable

func (*NodeTable) Get

func (nt *NodeTable) Get(key []byte) unsafe.Pointer

Get returns node pointer for the lookup key

func (*NodeTable) MemoryInUse

func (nt *NodeTable) MemoryInUse() int64

MemoryInUse returns memory used by nodetable instance

func (*NodeTable) Remove

func (nt *NodeTable) Remove(key []byte) (success bool, nptr unsafe.Pointer)

Remove an item from the nodetable

func (*NodeTable) Stats

func (nt *NodeTable) Stats() string

Stats returns nodetable statistics

func (*NodeTable) Update

func (nt *NodeTable) Update(key []byte, nptr unsafe.Pointer) (updated bool, oldPtr unsafe.Pointer)

Update inserts or replaces an existing entry