hash

Documentation

Overview

Package hash provides a HTree implementation to provide key-value storage functionality for a StorageManager.

The HTree provides a persistent hashtable. Storing values in buckets on pages as the tree gorws. It is not possible to store nil values. Storing a nil value is equivalent to removing a key.

As the tree grows each tree level contains pages with links to underlying pages. The last link is always to a bucket. The default tree has 4 levels each with 256 possible children. A hash code for the tree has 32 bits = 4 levels * 8 bit.

Hash buckets are on the lowest level of the tree and contain actual keys and values. The object stores multiple keys and values if there are hash collisions. In a sparsely populated tree buckets can also be found on the upper levels.

Iterator

Entries in the HTree can be iterated by using an HTreeIterator. The HTree may change behind the iterator's back. The iterator will try to cope with best effort and only report an error as a last resort.

Hash function

The HTree uses an implementation of Austin Appleby's MurmurHash3 (32bit) function as hash function.

Reference implementation: http://code.google.com/p/smhasher/wiki/MurmurHash3

Index

• Constants
• Variables
• func MurMurHashData(data []byte, offset int, size int, seed int) (uint32, error)
• type HTree
  • func LoadHTree(sm storage.Manager, loc uint64) (*HTree, error)
  • func NewHTree(sm storage.Manager) (*HTree, error)
  • func (t *HTree) Exists(key []byte) (bool, error)
  • func (t *HTree) Get(key []byte) (interface{}, error)
  • func (t *HTree) GetValueAndLocation(key []byte) (interface{}, uint64, error)
  • func (t *HTree) Location() uint64
  • func (t *HTree) Put(key []byte, value interface{}) (interface{}, error)
  • func (t *HTree) Remove(key []byte) (interface{}, error)
  • func (t *HTree) String() string
• type HTreeIterator
  • func NewHTreeIterator(tree *HTree) *HTreeIterator
  • func (it *HTreeIterator) HasNext() bool
  • func (it *HTreeIterator) Next() ([]byte, interface{})
  • func (it *HTreeIterator) String() string

Constants

const MaxBucketElements = 8

MaxBucketElements is the maximum umber of elements a bucket can contain before it is converted into a page except leaf buckets which grow indefinitely

const MaxPageChildren = 256

MaxPageChildren is the maximum of children per page - (stored in PageLevelBits bits)

const MaxTreeDepth = 3

MaxTreeDepth is the maximum number of non-leaf levels in the tree (i.e. the complete tree has a total of MAX_DEPTH+1 levels)

const PageLevelBits = 8

PageLevelBits is the number of significant bits per page level

Variables

var ErrNoMoreItems = errors.New("No more items to iterate")

ErrNoMoreItems is assigned to LastError when Next() is called and there are no more items to iterate.

Functions

func MurMurHashData

func MurMurHashData(data []byte, offset int, size int, seed int) (uint32, error)

MurMurHashData hashes a given array of bytes. This is an implementation of Austin Appleby's MurmurHash3 (32bit) function.

Reference implementation: http://code.google.com/p/smhasher/wiki/MurmurHash3

Types

type HTree

type HTree struct {
	Root *htreePage // Root page of the HTree
	// contains filtered or unexported fields
}

HTree data structure

func LoadHTree

func LoadHTree(sm storage.Manager, loc uint64) (*HTree, error)

LoadHTree fetches a HTree from storage

func NewHTree

func NewHTree(sm storage.Manager) (*HTree, error)

NewHTree creates a new HTree.

func (*HTree) Exists

func (t *HTree) Exists(key []byte) (bool, error)

Exists checks if an element exists.

func (*HTree) Get

func (t *HTree) Get(key []byte) (interface{}, error)

Get gets a value for a given key.

func (*HTree) GetValueAndLocation

func (t *HTree) GetValueAndLocation(key []byte) (interface{}, uint64, error)

GetValueAndLocation returns the value and the storage location for a given key.

func (*HTree) Location

func (t *HTree) Location() uint64

Location returns the HTree location on disk.

func (*HTree) Put

func (t *HTree) Put(key []byte, value interface{}) (interface{}, error)

Put adds or updates a new key / value pair.

func (*HTree) Remove

func (t *HTree) Remove(key []byte) (interface{}, error)

Remove removes a key / value pair.

func (*HTree) String

func (t *HTree) String() string

String returns a string representation of this tree.

type HTreeIterator

type HTreeIterator struct {
	LastError error // Last encountered error
	// contains filtered or unexported fields
}

HTreeIterator data structure

func NewHTreeIterator

func NewHTreeIterator(tree *HTree) *HTreeIterator

NewHTreeIterator creates a new HTreeIterator.

func (*HTreeIterator) HasNext

func (it *HTreeIterator) HasNext() bool

HasNext returns if there is a next key / value pair.

func (*HTreeIterator) Next

func (it *HTreeIterator) Next() ([]byte, interface{})

Next returns the next key / value pair.

func (*HTreeIterator) String

func (it *HTreeIterator) String() string

Return a string representation of the iterator.