hamt64

package
v2.0.0+incompatible Latest Latest
Warning

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

 Go to latest Published: Oct 19, 2020 License: Apache-2.0 Imports: 8 Imported by: 0

Documentation

Overview

Package hamt64 defines interface to access a Hamt data structure based on 64bit hash values. The Hamt data structure is built with interior nodes and leaf nodes. The interior nodes are called tables and the leaf nodes are call, well, leafs. Further, the tables come is two varieties fixed size tables and a compressed form to handle sparse tables. Leafs come in two forms the common flat leaf form with a singe key/value pair and the rare form used when two leafs have the same hash value called collision leafs.

The Hamt data structure is implemented with two code bases, which both implement the hamt64.Hamt interface, the transient replace in place code and the functional copy on write code. We define a HamtTransient base data structure and a HamtFunctional base data structure. Both of these data structures are identical, they only have unique names so we can hang the different code implementations off them.

Lastly, the Hamt data structure can be implemented with fixed tables only or with sparse tables only or with a hybrid of the two. Thia hybid form is meant to allow the denser lower inner nodes to be implemented by the faster fixed tables and the much more numerous but sparser higher inner nodes to be implemented by the space conscious sparse tables.

Index

Constants

View Source 
const (
	// HybridTables indicates the structure should use sparseTable
	// initially, then upgrade to fixedTable when appropriate.
	HybridTables = iota
	// FixedTable indicates the structure should use fixedTables ONLY.
	// This was intended to be for speed, as compressed tables use a software
	// bitCount function to access individual cells.
	FixedTables
	// SparseTables indicates the structure should use sparseTables ONLY.
	// This was intended just save space, but also seems to be faster; CPU cache
	// locality maybe?
	SparseTables
)

Configuration contants to be passed to `hamt64.New(int) *Hamt`.

View Source 
const DepthLimit = hashSize / NumIndexBits

DepthLimit is the maximum number of levels of the Hamt. It is calculated as DepthLimit = floor(hashSize / NumIndexBits) or a strict integer division.

View Source 
const DowngradeThreshold uint = IndexLimit / 2 //16 for NumIndexBits=5

DowngradeThreshold is the constant that sets the threshold for the size of a table, such that when a table decreases to the threshold size, the table is converted from a FixedTable to a SparseTable.

This conversion only happens if the Hamt structure has be constructed with the HybridTables option.

View Source 
const IndexLimit = 1 << NumIndexBits

IndexLimit is the maximum number of entries in a Hamt interior node. In other words it is the width of the Hamt data structure.

View Source 
const NumIndexBits uint = 5

NumIndexBits is the fundemental setting for the Hamt data structure. Given that we hash every key ([]byte slice) into a HashVal, that HashVal must be split into DepthLimit number of NumIndexBits wide parts. Each of those parts of the HashVal is used as the index into the given level of the Hamt tree. So NumIndexBits determines how wide and how deep the Hamt can be.

View Source 
const UpgradeThreshold uint = IndexLimit * 5 / 8 //20 for NumIndexBits=5

UpgradeThreshold is the constant that sets the threshold for the size of a table, such that when a table increases to the threshold size, the table is converted from a SparseTable to a FixedTable.

This conversion only happens if the Hamt structure has be constructed with the HybridTables option.

Variables

View Source 
var SizeofBitmap = unsafe.Sizeof(bitmap{})
View Source 
var SizeofFixedTable = unsafe.Sizeof(fixedTable{})
View Source 
var SizeofHamtBase = unsafe.Sizeof(hamtBase{})
View Source 
var SizeofNodeI = unsafe.Sizeof([1]nodeI{})
View Source 
var SizeofSparseTable = unsafe.Sizeof(sparseTable{})
View Source 
var TableOptionName [3]string

TableOptionName is a lookup table to map the integer value of FixedTables, SparseTables, and HybridTables to a string representing that option. 

var option = hamt64.FixedTables
hamt64.TableOptionName[option] == "FixedTables"

Functions

This section is empty.

Types

type ByteSliceKey 

type ByteSliceKey []byte

func (ByteSliceKey) Equals 

func (bsk ByteSliceKey) Equals(K KeyI) bool

func (ByteSliceKey) Hash 

func (bsk ByteSliceKey) Hash() HashVal

type Hamt 

type Hamt interface {
	IsEmpty() bool
	Nentries() uint
	ToFunctional() Hamt
	ToTransient() Hamt
	DeepCopy() Hamt
	Get(KeyI) (interface{}, bool)
	Put(KeyI, interface{}) (Hamt, bool)
	Del(KeyI) (Hamt, interface{}, bool)
	String() string
	LongString(string) string
	Range(func(KeyI, interface{}) bool)
	Stats() *Stats
	// contains filtered or unexported methods
}

Hamt defines the interface that both the HamtFunctional and HamtTransient data structures must (and do) implement.

func New 

func New(functional bool, tblOpt int) Hamt

New constructs a datastucture that implements the Hamt interface.

When the functional argument is true it implements a HamtFunctional data structure. When the functional argument is false it implements a HamtTransient data structure.

The tblOpt argument is the table option defined by the constants HybridTables, SparseTables, xor FixedTables.

type HamtFunctional 

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

HamtFunctional is the data structure which the Funcitonal Hamt methods are called upon. In fact it is identical to the HamtTransient data structure and all the table and leaf data structures it uses are the same ones used by the HamtTransient implementation. It is its own type so that the methods it calls are the functional version of the Hamt interface.

Basically the functional versions implement a copy-on-write inmplementation of Put() and Del(). The original HamtFuncitonal isn't modified and Put() and Del() return a slightly modified copy of the HamtFunctional data structure. So sharing this data structure between threads is safe.

func NewFunctional 

func NewFunctional(tblOpt int) *HamtFunctional

NewFunctional constructs a new HamtFunctional data structure.

The tblOpt argument is the table option defined by the constants HybridTables, SparseTables, xor FixedTables.

func (*HamtFunctional) DeepCopy 

func (h *HamtFunctional) DeepCopy() Hamt

DeepCopy() copies the HamtFunctional data structure and every table it contains recursively. This method gets more expensive the deeper the Hamt becomes.

func (*HamtFunctional) Del 

func (h *HamtFunctional) Del(key KeyI) (Hamt, interface{}, bool)

Del searches the HamtFunctional for the key argument and returns three values: a Hamt interface, a value, and a bool.

If the key was found then the bool returned is true and the value is the value related to that key and the returned Hamt is the new HamtFunctional data structure pointer.

If key was not found, then the bool is false, the value is nil, and the Hamt value is the original HamtFunctional data structure pointer.

func (*HamtFunctional) Get 

func (h *HamtFunctional) Get(key KeyI) (interface{}, bool)

Get retrieves the value related to the key in the HamtFunctional data structure. It also return a bool to indicate the value was found. This allows you to store nil values in the HamtFunctional data structure.

func (*HamtFunctional) IsEmpty 

func (h *HamtFunctional) IsEmpty() bool

IsEmpty simply returns if the HamtFunctional data structure has no entries.

func (*HamtFunctional) LongString 

func (h *HamtFunctional) LongString(indent string) string

LongString returns a complete recusive listing of the entire HamtFunctional data structure.

func (*HamtFunctional) Nentries 

func (h *HamtFunctional) Nentries() uint

Nentries return the number of (key,value) pairs are stored in the HamtFunctional data structure.

func (*HamtFunctional) Put 

func (h *HamtFunctional) Put(key KeyI, val interface{}) (Hamt, bool)

Put stores a new (key,value) pair in the HamtFunctional data structure. It returns a bool indicating if a new pair was added (true) or if the value replaced (false). Either way it returns a new HamtFunctional data structure containing the modification.

func (*HamtFunctional) Range 

func (h *HamtFunctional) Range(fn func(KeyI, interface{}) bool)

Range executes the given function for every KeyVal pair in the Hamt. KeyVal pairs are visited in a seeminly random order.

Note: we say "seemingly random order", becuase there is a predictable order based on the hash value of the Keys and the insertion order of the KeyVal pairs, so you cannot reley on the "randomness" of the order of KeyVal pairs.

func (*HamtFunctional) Stats 

func (h *HamtFunctional) Stats() *Stats

Stats walks the Hamt in a pre-order traversal and populates a Stats data struture which it returns.

func (*HamtFunctional) String 

func (h *HamtFunctional) String() string

String returns a simple string representation of the HamtFunctional data structure.

func (*HamtFunctional) ToFunctional 

func (h *HamtFunctional) ToFunctional() Hamt

ToFunctional does nothing to a HamtFunctional pointer. This method only here for conformance with the Hamt interface.

func (*HamtFunctional) ToTransient 

func (h *HamtFunctional) ToTransient() Hamt

ToTransient just recasts the HamtFunctional pointer to a HamtTransient underneath the Hamt interface.

If you want a copy of the HamtFunctional data structure over to a completely independent HamtTransient data structure, you should first do a DeepCopy followed by a ToTransient call.

type HamtTransient 

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

HamtTransient is the data structure which the Transient Hamt methods are called upon. In fact it is identical to the HamtFunctional data structure and all the table and leaf data structures it uses are the same ones used by the HamtTransient implementation. It is its own type so that the methods it calls are the transient version of the Hamt interface.

The Transient version of the Hamt data structure, does all modifications in-place. So sharing this datastruture between threads is NOT safe unless you were to implement a locking stategy CORRECTLY.

func NewTransient 

func NewTransient(tblOpt int) *HamtTransient

NewTransient constructs a new HamtTransient data structure.

The tblOpt argument is the table option defined by the constants HybridTables, SparseTables, xor FixedTables.

func (*HamtTransient) DeepCopy 

func (h *HamtTransient) DeepCopy() Hamt

DeepCopy() copies the HamtTransient data structure and every table it contains recursively.

func (*HamtTransient) Del 

func (h *HamtTransient) Del(key KeyI) (Hamt, interface{}, bool)

Del searches the HamtTransient for the key argument and returns three values: a Hamt data structure, a value, and a bool.

If the key was found, then the bool returned is true and the value is the value related to that key.

If key was not found, then the bool returned is false and the value is nil.

In either case, the Hamt value is the original HamtTransient pointer as a Hamt interface.

func (*HamtTransient) Get 

func (h *HamtTransient) Get(key KeyI) (interface{}, bool)

Get retrieves the value related to the key in the HamtTransient data structure. It also return a bool to indicate the value was found. This allows you to store nil values in the HamtTransient data structure.

func (*HamtTransient) IsEmpty 

func (h *HamtTransient) IsEmpty() bool

IsEmpty simply returns if the HamtTransient datastucture has no entries.

func (*HamtTransient) LongString 

func (h *HamtTransient) LongString(indent string) string

LongString returns a complete recusive listing of the entire HamtTransient data structure.

func (*HamtTransient) Nentries 

func (h *HamtTransient) Nentries() uint

Nentries return the number of (key,value) pairs are stored in the HamtTransient data structure.

func (*HamtTransient) Put 

func (h *HamtTransient) Put(key KeyI, val interface{}) (Hamt, bool)

Put stores a new (key,value) pair in the HamtTransient data structure. It returns a bool indicating if a new pair were added or if the value replaced the value in a previously stored (key,value) pair. Either way it returns and new HamtTransient data structure containing the modification.

func (*HamtTransient) Range 

func (h *HamtTransient) Range(fn func(KeyI, interface{}) bool)

Range executes the given function for every KeyVal pair in the Hamt. KeyVal pairs are visited in a seeminly random order.

Note: we say "seemingly random order", becuase there is a predictable order based on the hash value of the Keys and the insertion order of the KeyVal pairs, so you cannot reley on the "randomness" of the order of KeyVal pairs.

func (*HamtTransient) Stats 

func (h *HamtTransient) Stats() *Stats

Stats walks the Hamt in a pre-order traversal and populates a Stats data struture which it returns.

func (*HamtTransient) String 

func (h *HamtTransient) String() string

String returns a simple string representation of the HamtTransient data structure.

func (*HamtTransient) ToFunctional 

func (h *HamtTransient) ToFunctional() Hamt

ToFunctional just recasts the HamtFunctional pointer to a HamtFunctional underneath the Hamt interface.

If you want a copy of the HamtTransient data structure over to a completely independent HamtFunctional data structure, you should first do a DeepCopy followed by a ToFunctional call.

func (*HamtTransient) ToTransient 

func (h *HamtTransient) ToTransient() Hamt

ToTransient does nothing to a HamtTransient pointer. This method only here for conformance with the Hamt interface.

type HashVal 

type HashVal uint64

HashVal sets the numberer of bits of the hash value by being an alias to uint64 and establishes a type we can hang methods, like Index(), off of.

func CalcHash 

func CalcHash(bs []byte) HashVal

CalcHash deterministically calculates a randomized uint64 of a given byte slice .

func (HashVal) HashPathString 

func (hv HashVal) HashPathString(limit uint) string

HashPathString returns a string representation of the index path of a HashVal. It will be string of the form "/idx0/idx1/..." where each idxN value will be a zero padded number between 0 and maxIndex. There will be limit number of such values where limit <= DepthLimit. If the limit parameter is 0 then the method will simply return "/". Example: "/00/24/46/17" for limit=4 of a NumIndexBits=5 hash value represented by "/00/24/46/17/34/08".

func (HashVal) Index 

func (hv HashVal) Index(depth uint) uint

Index returns the NumIndexBits bit value of the HashVal at 'depth' number of NumIndexBits number of bits into HashVal.

func (HashVal) String 

func (hv HashVal) String() string

String returns a string representation of a full HashVal. This is simply hv.HashPathString(DepthLimit).

type Int32Key 

type Int32Key int32

func (Int32Key) Equals 

func (ik Int32Key) Equals(K KeyI) bool

func (Int32Key) Hash 

func (ik Int32Key) Hash() HashVal

type Int64Key 

type Int64Key int64

func (Int64Key) Equals 

func (ik Int64Key) Equals(K KeyI) bool

func (Int64Key) Hash 

func (ik Int64Key) Hash() HashVal

type KeyI 

type KeyI interface {
	Hash() HashVal
	Equals(KeyI) bool
}

KeyI interface specifies the two methods a datatype must implement to be used as a key in this HAMT implementation.

For provided types that popular data structures used as keys in other Map implementations see the ByteSliceKey, StringKey, Int{32,64}Key, and Uint{32,64}Key types provided by this library.

For instace, you can map "foo"->"bar" with a call to h.Put(hamt64.StringKey("foo"), "bar") .

type KeyVal 

type KeyVal struct {
	Key KeyI
	Val interface{}
}

KeyVal is a simple struct used to transfer lists ([]KeyVal) from one function to another.

func (KeyVal) String 

func (kv KeyVal) String() string

type Stats 

type Stats struct {
	// Depth of deepest table
	MaxDepth uint

	// TableCountsByNentries is a Hash table of the number of tables with each
	// given number of entries in the tatble. There are slots for
	// [0..IndexLimit] inclusive (so there are IndexLimit+1 slots). Technically,
	// there should never be a table with zero entries, but I allow counting
	// tables with zero entries just to catch those errors.
	TableCountsByNentries [IndexLimit + 1]uint // [0..IndexLimit] inclusive

	// TableCountsByDepth is a Hash table of the number of tables at a given
	// depth. There are slots for [0..DepthLimit).
	TableCountsByDepth [DepthLimit]uint // [0..DepthLimit)

	// Nils is the total count of allocated slots that are unused in the HAMT.
	Nils uint

	// Nodes is the total count of nodeI capable structs in the HAMT.
	Nodes uint

	// Tables is the total count of tableI capable structs in the HAMT.
	Tables uint

	// Leafs is the total count of leafI capable structs in the HAMT.
	Leafs uint

	// FixedTables is the total count of fixedTable structs in the HAMT.
	FixedTables uint

	// SparseTables is the total count of sparseTable structs in the HAMT.
	SparseTables uint

	// FlatLeafs is the total count of flatLeaf structs in the HAMT.
	FlatLeafs uint

	// CollisionLeafs is the total count of collisionLeaf structs in the HAMT.
	CollisionLeafs uint

	// KeyVals is the total number of KeyVal pairs int the HAMT.
	KeyVals uint
}

type StringKey 

type StringKey string

func (StringKey) Equals 

func (sk StringKey) Equals(K KeyI) bool

func (StringKey) Hash 

func (sk StringKey) Hash() HashVal

type Uint32Key 

type Uint32Key int32

func (Uint32Key) Equals 

func (ik Uint32Key) Equals(K KeyI) bool

func (Uint32Key) Hash 

func (ik Uint32Key) Hash() HashVal

type Uint64Key 

type Uint64Key int64

func (Uint64Key) Equals 

func (ik Uint64Key) Equals(K KeyI) bool

func (Uint64Key) Hash 

func (ik Uint64Key) Hash() HashVal

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.