hamt64

Documentation

Overview

Package hamt64 implements a functional Hash Array Mapped Trie (HAMT). It is called hamt64 because this package is using 64 nodes for each level of the Trie. The term functional is used to imply immutable and persistent.

The key to the hamt64 datastructure is imported from the "github.com/lleogo-hamt-key" module. We get the 60 bits of hash value from key. The 60bits of hash are separated into ten 6 bit values that constitue the hash path of any Key in this Trie. However, not all ten levels of the Trie are used. As many levels (ten or less) are used to find a unique location for the leaf to be placed within the Trie.

If all ten levels of the Trie are used for two or more key/val pairs, then a special collision leaf will be used to store those key/val pairs at the tenth level of the Trie.

Index

• Constants
• Variables
• type Hamt
  • func (h Hamt) Del(k key.Key) (nh Hamt, val interface{}, deleted bool)
  • func (h Hamt) Get(k key.Key) (val interface{}, found bool)
  • func (h Hamt) IsEmpty() bool
  • func (h Hamt) LongString(indent string) string
  • func (h Hamt) Nentries() uint
  • func (h Hamt) Put(k key.Key, v interface{}) (nh Hamt, added bool)
  • func (h Hamt) String() string
• type KeyVals

Constants

const MaxDepth uint = key.MaxDepth60

MaxDepth constant is the maximum depth(6) of Nbits values that constitute the path in a HAMT, from [0..MaxDepth] for a total of MaxDepth+1(9) levels. Nbits*(MaxDepth+1) == HASHBITS (ie 6*(6+1) == 60). We actually get this value from key.MaxDepth60 in "github.com/lleo/go-hamt-key". const MaxDepth uint = 6

const Nbits uint = key.BitsPerLevel60

Nbits constant is the number of bits(6) a 60bit hash value is split into, to provied the indexes of a HAMT. We actually get this value from key.BitsPerLevel60 in "github.com/lleo/go-hamt-key". const Nbits uint = 6

const TableCapacity uint = 1 << key.BitsPerLevel60

TableCapacity constant is the number of table entries in a each node of a HAMT datastructure; its value is 1<<Nbits (ie 2^6 == 64). const TableCapacity uint = 1 << Nbits

Variables

var DowngradeThreshold = TableCapacity / 4

DowngradeThreshold is a variable that defines when a fullTable becomes lower than that number of entries, then that table will be downgraded to a compressedTable. This only applies when HybridTables option is chosen. The current value is TableCapacity/4.

var FullTableInit = false

FullTableInit variable controls whether the initial new table type is fullTable, else the initial new table type is compressedTable. Default: false

var GradeTables = true

GradeTables variable controls whether Hamt structures will upgrade/ downgrade compressed/full tables. This variable and FullTableInit should not be changed during the lifetime of any Hamt structure. Default: true

var UpgradeThreshold = TableCapacity * 2 / 3

UpgradeThreshold is a variable that defines when a compressedTable meats or exceeds that number of entries, then that table will be upgraded to a fullTable. This only applies when HybridTables option is chosen. The current value is TableCapacity/2.

Types

type Hamt

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

func (Hamt) Del

func (h Hamt) Del(k key.Key) (nh Hamt, val interface{}, deleted bool)

Hamt.Del(k) returns a Hamt structure, a value, and a boolean that specifies whether or not the key was found (and therefor deleted). If the key was found & deleted it returns the value assosiated with the key and a new persistent Hamt structure, otherwise it returns a nil value and the original (immutable) Hamt structure

func (Hamt) Get

func (h Hamt) Get(k key.Key) (val interface{}, found bool)

Get(k) retrieves the value for a given key from the Hamt. The bool represents whether the key was found.

func (Hamt) IsEmpty

func (h Hamt) IsEmpty() bool

func (Hamt) LongString

func (h Hamt) LongString(indent string) string

func (Hamt) Nentries

func (h Hamt) Nentries() uint

func (Hamt) Put

func (h Hamt) Put(k key.Key, v interface{}) (nh Hamt, added bool)

Put inserts a key/val pair into Hamt, returning a new persistent Hamt and a bool indicating if the key/val pair was added(true) or mearly updated(false).

func (Hamt) String

func (h Hamt) String() string

type KeyVals

type KeyVals []key.KeyVal