Documentation
¶
Index ¶
- Variables
- func Hasher(key int64, depth int64) int64
- func IsHash(index *HashIndex) (bool, error)
- func MurmurHasher(key int64, size int64) uint
- func WriteHashTable(bucketPager *pager.Pager, table *HashTable) error
- func XxHasher(key int64, size int64) uint
- type BucketLockType
- type HashBucket
- func (bucket *HashBucket) Delete(key int64) error
- func (bucket *HashBucket) Find(key int64) (utils.Entry, bool)
- func (bucket *HashBucket) GetDepth() int64
- func (bucket *HashBucket) GetPage() *pager.Page
- func (bucket *HashBucket) Insert(key int64, value int64) (bool, error)
- func (bucket *HashBucket) Print(w io.Writer)
- func (bucket *HashBucket) RLock()
- func (bucket *HashBucket) RUnlock()
- func (bucket *HashBucket) Select() (entries []utils.Entry, err error)
- func (bucket *HashBucket) Update(key int64, value int64) error
- func (bucket *HashBucket) WLock()
- func (bucket *HashBucket) WUnlock()
- type HashCursor
- type HashEntry
- type HashIndex
- func (index *HashIndex) Close() error
- func (index *HashIndex) Delete(key int64) error
- func (index *HashIndex) Find(key int64) (utils.Entry, error)
- func (table *HashIndex) GetName() string
- func (table *HashIndex) GetPager() *pager.Pager
- func (index *HashIndex) GetTable() *HashTable
- func (index *HashIndex) Insert(key int64, value int64) error
- func (index *HashIndex) Print(w io.Writer)
- func (index *HashIndex) PrintPN(pn int, w io.Writer)
- func (index *HashIndex) Select() ([]utils.Entry, error)
- func (table *HashIndex) TableStart() (utils.Cursor, error)
- func (index *HashIndex) Update(key int64, value int64) error
- type HashTable
- func (table *HashTable) Delete(key int64) error
- func (table *HashTable) ExtendTable()
- func (table *HashTable) Find(key int64) (utils.Entry, error)
- func (table *HashTable) GetAndLockBucket(hash int64, lock BucketLockType) (*HashBucket, error)
- func (table *HashTable) GetAndLockBucketByPN(pn int64, lock BucketLockType) (*HashBucket, error)
- func (table *HashTable) GetBucket(hash int64) (*HashBucket, error)
- func (table *HashTable) GetBucketByPN(pn int64) (*HashBucket, error)
- func (table *HashTable) GetBuckets() []int64
- func (table *HashTable) GetDepth() int64
- func (table *HashTable) GetPager() *pager.Pager
- func (table *HashTable) Insert(key int64, value int64) error
- func (table *HashTable) Print(w io.Writer)
- func (table *HashTable) PrintPN(pn int, w io.Writer)
- func (table *HashTable) RLock()
- func (table *HashTable) RUnlock()
- func (table *HashTable) Select() ([]utils.Entry, error)
- func (table *HashTable) Split(bucket *HashBucket, hash int64) error
- func (table *HashTable) Update(key int64, value int64) error
- func (table *HashTable) WLock()
- func (table *HashTable) WUnlock()
Constants ¶
This section is empty.
Variables ¶
var BUCKETSIZE int64 = (PAGESIZE-BUCKET_HEADER_SIZE)/ENTRYSIZE - 1 // num entries
var BUCKET_HEADER_SIZE int64 = DEPTH_SIZE + NUM_KEYS_SIZE
var DEPTH_OFFSET int64 = 0
var DEPTH_SIZE int64 = binary.MaxVarintLen64
var DIRECTORY_HEADER_SIZE int64 = binary.MaxVarintLen64 * 2 // Must store global depth and next pointer
var ENTRYSIZE int64 = binary.MaxVarintLen64 * 2 // int64 key, int64 value
var NUM_KEYS_OFFSET int64 = DEPTH_OFFSET + DEPTH_SIZE
var NUM_KEYS_SIZE int64 = binary.MaxVarintLen64
var PAGESIZE int64 = pager.PAGESIZE
var ROOT_PN int64 = 0
Hash table variables
Functions ¶
func MurmurHasher ¶
MurmurHasher returns the MurmurHash3 hash of the given key, bounded by size.
func WriteHashTable ¶
Write hash table out to memory.
Types ¶
type BucketLockType ¶
type BucketLockType int
Lock Types
const ( NO_LOCK BucketLockType = 0 WRITE_LOCK BucketLockType = 1 READ_LOCK BucketLockType = 2 )
type HashBucket ¶
type HashBucket struct {
// contains filtered or unexported fields
}
HashBucket.
func NewHashBucket ¶
func NewHashBucket(pager *pager.Pager, depth int64) (*HashBucket, error)
Construct a new HashBucket.
func (*HashBucket) Delete ¶
func (bucket *HashBucket) Delete(key int64) error
Delete the given key-value pair, does not coalesce.
func (*HashBucket) Find ¶
func (bucket *HashBucket) Find(key int64) (utils.Entry, bool)
Finds the entry with the given key.
func (*HashBucket) Insert ¶
func (bucket *HashBucket) Insert(key int64, value int64) (bool, error)
Inserts the given key-value pair, splits if necessary.
func (*HashBucket) RLock ¶
func (bucket *HashBucket) RLock()
[CONCURRENCY] Grab a read lock on the hash table index
func (*HashBucket) RUnlock ¶
func (bucket *HashBucket) RUnlock()
[CONCURRENCY] Release a read lock on the hash table index
func (*HashBucket) Select ¶
func (bucket *HashBucket) Select() (entries []utils.Entry, err error)
Select all entries in this bucket.
func (*HashBucket) Update ¶
func (bucket *HashBucket) Update(key int64, value int64) error
Update the given key-value pair, should never split. Find the bucket we want based on key, then update the entry using updateValueAt.
func (*HashBucket) WLock ¶
func (bucket *HashBucket) WLock()
[CONCURRENCY] Grab a write lock on the hash table index
func (*HashBucket) WUnlock ¶
func (bucket *HashBucket) WUnlock()
[CONCURRENCY] Release a write lock on the hash table index
type HashCursor ¶
type HashCursor struct {
// contains filtered or unexported fields
}
HashCursor points to a spot in the hash table.
func (*HashCursor) GetEntry ¶
func (cursor *HashCursor) GetEntry() (utils.Entry, error)
GetEntry returns the entry currently pointed to by the cursor.
func (*HashCursor) StepForward ¶
func (cursor *HashCursor) StepForward() bool
StepForward moves the cursor ahead by one entry.
type HashEntry ¶
type HashEntry struct {
// contains filtered or unexported fields
}
HashEntry is a single entry in a hashtable. Implements utils.Entry.
type HashIndex ¶
type HashIndex struct {
// contains filtered or unexported fields
}
HashIndex is an index that uses a HashTable as its datastructure. Implements db.Index.
func (*HashIndex) TableStart ¶
TableStart returns a cursor to the first entry in the hash table.
type HashTable ¶
type HashTable struct {
// contains filtered or unexported fields
}
HashTable definitions.
func NewHashTable ¶
Returns a new HashTable.
func ReadHashTable ¶
Read hash table in from memory.
func (*HashTable) ExtendTable ¶
func (table *HashTable) ExtendTable()
ExtendTable increases the global depth of the table by 1.
func (*HashTable) GetAndLockBucket ¶
func (table *HashTable) GetAndLockBucket(hash int64, lock BucketLockType) (*HashBucket, error)
Returns the bucket in the hash table, and increments the bucket ref count.
func (*HashTable) GetAndLockBucketByPN ¶
func (table *HashTable) GetAndLockBucketByPN(pn int64, lock BucketLockType) (*HashBucket, error)
Returns the bucket in the hash table using its page number, and increments the bucket ref count.
func (*HashTable) GetBucket ¶
func (table *HashTable) GetBucket(hash int64) (*HashBucket, error)
Returns the bucket in the hash table, and increments the bucket ref count.
func (*HashTable) GetBucketByPN ¶
func (table *HashTable) GetBucketByPN(pn int64) (*HashBucket, error)
Returns the bucket in the hash table using its page number, and increments the bucket ref count.
func (*HashTable) GetBuckets ¶
Get bucket page numbers.
func (*HashTable) RLock ¶
func (table *HashTable) RLock()
[CONCURRENCY] Grab a read lock on the hash table index
func (*HashTable) RUnlock ¶
func (table *HashTable) RUnlock()
[CONCURRENCY] Release a read lock on the hash table index
func (*HashTable) Split ¶
func (table *HashTable) Split(bucket *HashBucket, hash int64) error
Split the given bucket into two, extending the table if necessary.