Documentation
¶
Overview ¶
Package libcombindex is a hash to ordered integers index.
It allows you to store hashes, which are mapped to a successive height integers.
The Table is a probabilistic data structure, in the sense that it does not simply allow you to Get the right height value. Instead, it provides a successive height guesses, one of which is guaranteed to be correct, and the remaining ones may be incorrect. The number of guesses can be reduced by decreasing the MaxLoad or Hops.
Index ¶
- type Bucket
- func (b *Bucket) Cap() uint32
- func (b *Bucket) Delete(height uint32, hashes []uint32) uint32
- func (b *Bucket) Get(hash uint32, maxHeight uint32) (ret Continuation)
- func (b *Bucket) HeightMask() uint32
- func (b *Bucket) Insert(height uint32, hash uint32) bool
- func (b *Bucket) Len() uint32
- func (b *Bucket) UsedPercent() byte
- type Continuation
- type LoopDetector
- type Table
- func (c *Table) Cap() (ret uint64)
- func (c *Table) ConfiguredCorrectly() bool
- func (c *Table) Delete(hashes [][32]byte, height uint64) (success bool)
- func (c *Table) Get(hash [32]byte, maxHeight uint64, cb func(uint64) bool) bool
- func (c *Table) Insert(hash [32]byte, height uint64)
- func (c *Table) Len() (ret uint64)
- func (c *Table) UsedPercent() byte
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Bucket ¶
type Bucket struct {
Min, Max uint64 // place holders, define the height range stored in this bucket
// contains filtered or unexported fields
}
Bucket is an internal data holder type used by the Table structure. It can optionally also hold the Min, Max describing the height range stored by this bucket. Note: Max bucket size is around 4GB.
func BucketInit ¶
BucketInit initializes a new bucket. It only fails when OOM.
func (*Bucket) Delete ¶
Delete deletes the height values at a specific hashes keys from the bucket. It returns the number of items successfully deleted. All hashes are at the same height, the height must be the highest height that exists in the bucket.
func (*Bucket) Get ¶
func (b *Bucket) Get(hash uint32, maxHeight uint32) (ret Continuation)
Get creates the Continuation to get a hash height that was inserted at height which is less or equal to maxHeight.
func (*Bucket) HeightMask ¶
HeightMask returns the height mask, that is, how many successive heights can this bucket hold.
func (*Bucket) Insert ¶
Insert inserts the height value at a specific hash key into the bucket. It returns true when it succeeded, false when it gave up. The height inserted must be higher or equal to any height previously inserted. The same hash can be inserted repeadedly, but it performs better when each hash is unique.
func (*Bucket) UsedPercent ¶
UsedPercent returns the percentage occupied in this bucket. Empty bucket returns 0%.
type Continuation ¶
type Continuation struct {
// contains filtered or unexported fields
}
Continuation is a get reading continuation. It is used to read out successive height guesses for any hash that exists or not exists in the bucket.
func (*Continuation) Bucket ¶
func (c *Continuation) Bucket() *Bucket
Bucket returns the Bucket from which the Continuation Gets data.
func (*Continuation) Get ¶
func (c *Continuation) Get() (height uint32)
Get returns the next height guess. If there is no more guess, it returns 0.
func (*Continuation) Order ¶
func (c *Continuation) Order() uint32
Order returns the importance of this continuation relative to other continuations.
type LoopDetector ¶
type LoopDetector [2][32]uint32
LoopDetector is a detector capable of detecting loops in an infinite sequence of 32bit integers, as well as providing information whether we are not yet in loop.
func (*LoopDetector) Add ¶
func (c *LoopDetector) Add(n uint32) (ret bool)
Add adds a specific number n into the loop detector. It ocasionally reports true when we are not in a loop (when Add changes the loop detector state).
func (*LoopDetector) Seen ¶
func (c *LoopDetector) Seen(n uint32) bool
Seen reports whether a specific number n was already seen in the sequence. This means we are in a loop.
type Table ¶
type Table struct {
Seed uint32 // a true random seed should be provided to randomize the structure
Bytes byte // number of bytes per stored entry in the table, usually 3
Mega uint16 // number of millions of entries per bucket, when creating a new one. The size is a slightly higher pseudoprime.
MaxLoad byte // Max load percentage of the last bucket, when exceeded, it creates a new bucket.
Hops uint16 // Number of hops after which to give up and make a new bucket. Used to break loops.
Tweak uint16 // Tweak is a multiplication factor when hopping to another hash position.
// contains filtered or unexported fields
}
Table is the main libcombindex table. It maps a 256bit hash to successive 64bit height integers. Important: Seed may not be changed when the Table is in use.
func (*Table) ConfiguredCorrectly ¶
ConfiguredCorrectly reports whether the Table is configured correctly and therefore it can be used.
func (*Table) Delete ¶
Delete deletes a specific height value from a specific 32byte hash key. The height must be equal or higher than the highest existing height in the table.
func (*Table) Get ¶
Get repeatedly guesses the height for a 32byte key hash, using the callback. The callback cb can report success true to stop the get iteration, or false to continue guessing. MaxHeight is used to limit the height values guessed to heights lower than the provided maxHeight parameter.
func (*Table) Insert ¶
Insert inserts a specific height value at a specific 32byte hash key. The height must be equal or higher than the highest previously inserted height.
func (*Table) UsedPercent ¶
UsedPercent returns the percentage occupied in this table. Empty table returns 0%.
Source Files