gocuckoo

package
v0.0.0-...-41bdb7a Latest Latest
Warning

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

 Go to latest Published: May 10, 2024 License: MIT Imports: 6 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	CF_DEFAULT_MAX_ITERATIONS = 20
	CF_DEFAULT_BUCKETSIZE     = 2
	CF_DEFAULT_EXPANSION      = 1
	CF_MAX_EXPANSION          = 32768
	CF_MAX_ITERATIONS         = 65535
	CF_MAX_BUCKET_SIZE        = 255                // 8 bits, see struct SubCF
	CF_MAX_NUM_BUCKETS        = 0x00FFFFFFFFFFFFFF // 56 bits, see struct SubCF
	CF_MAX_NUM_FILTERS        = math.MaxUint16     // 16 bits, see struct CuckooFilter

)

Constants equivalent to #define macros

Variables

View Source 
var (
	ErrNoSpace  = errors.New("no space")
	ErrRelocate = errors.New("relocate failed")
)
View Source 
var DefaultBuildCuckooOptions = CuckooBuildOptions{
	MaxIterations: 20,
	Expansion:     1,
	BucketSize:    2,
	Entries:       1024,
}

DefaultBuildBloomOptions is the default options for building a new bloom filter. The options values same as the redisbloom C version.

Functions

func GetNextN2 

func GetNextN2(n uint64) uint64

GetNextN2 这个函数的目的是找到大于或等于输入 n 的最小的2的幂次方数。

func IsPower2 

func IsPower2(num uint64) bool

func RedisStringToBytes 

func RedisStringToBytes(s string) []byte

StringToBytes converts string to byte slice without memory allocation.

Types

type CuckooBucket 

type CuckooBucket []uint8

func (CuckooBucket) Delete 

func (bucket CuckooBucket) Delete(fp CuckooFingerprint) bool

Delete removes the fingerprint from the bucket, returning true if the fingerprint was found. static int Bucket_Delete(CuckooBucket bucket, uint16_t bucketSize, CuckooFingerprint fp)

func (CuckooBucket) Find 

func (bucket CuckooBucket) Find(fp CuckooFingerprint) int

static uint8_t *Bucket_Find(CuckooBucket bucket, uint16_t bucketSize, CuckooFingerprint fp) Find returns the index of the fingerprint in the bucket, or -1 if not found.

func (CuckooBucket) TryInsert 

func (bucket CuckooBucket) TryInsert(fp CuckooFingerprint) bool

FindAvailable returns a pointer to the first available slot in the bucket, or nil if none are available. static uint8_t *Bucket_FindAvailable(CuckooBucket bucket, uint16_t bucketSize)

type CuckooBuildOptions 

type CuckooBuildOptions struct {
	Entries       uint64
	BucketSize    uint16
	MaxIterations uint16
	Expansion     uint16
}

type CuckooFilter 

type CuckooFilter struct {
}

CuckooFilter struct equivalent

type CuckooFingerprint 

type CuckooFingerprint uint8

Equivalent to `typedef uint8_t CuckooFingerprint;`

type CuckooHash 

type CuckooHash uint64

Equivalent to `typedef uint64_t CuckooHash;`

func GetAltHash 

func GetAltHash(fp CuckooFingerprint, index CuckooHash) CuckooHash

GetAltHash computes an alternative hash value based on a fingerprint and an initial hash (index).

type GoCuckooFilter 

type GoCuckooFilter interface {
	Insert(val []byte) error
	Check(val []byte) bool
	Delete(val []byte) bool
	LoadFrom(data interface{}) error
}

type GoCuckooFilterImpl 

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

func NewGoCuckooFilter 

func NewGoCuckooFilter(options CuckooBuildOptions) *GoCuckooFilterImpl

NewGoCuckooFilter creates a new instance of a GoCuckooFilter. This filter is an implementation of the Cuckoo Filter algorithm, inspired by the implementation found in the RedisBloom project. A Cuckoo Filter is an efficient data structure for fast determination of element membership with a low false positive rate, particularly suitable for scenarios requiring quick lookups and storage for large datasets.

Parameters:

  • capacity: The initial capacity of the filter, indicating the number of elements it can store. The actual capacity is adjusted to the nearest power of two based on the bucketSize.
  • bucketSize: The number of elements each bucket can store. Buckets are the basic storage units used within the filter.
  • maxIterations: The maximum number of iterations for an element to be kicked out of its original position and attempt to find a new position during insertion. This parameter helps prevent the insertion operation from entering an infinite loop.
  • expansion: The multiplier for filter expansion. Expansion is achieved by increasing the number of buckets, and this parameter controls the degree of expansion.

Returns: A GoCuckooFilter instance that has been initialized and is ready for element addition and lookup operations.

Note: If the provided capacity or expansion is not a power of two, they will be adjusted to the nearest larger power of two. This adjustment optimizes the internal structure of the filter for efficiency.

func (*GoCuckooFilterImpl) Add 

func (cf *GoCuckooFilterImpl) Add(value []byte) bool

func (*GoCuckooFilterImpl) Check 

func (cf *GoCuckooFilterImpl) Check(val []byte) bool

Check returns true if the filter contains the given fingerprint. static int CuckooFilter_CheckFP(const CuckooFilter *filter, const LookupParams *params)

func (*GoCuckooFilterImpl) Delete 

func (cf *GoCuckooFilterImpl) Delete(val []byte) bool

Delete removes the fingerprint from the filter, returning true if the fingerprint was found. int CuckooFilter_Delete(CuckooFilter *filter, CuckooHash hash)

func (*GoCuckooFilterImpl) GetFilter 

func (cf *GoCuckooFilterImpl) GetFilter(index int) *SubCF

func (*GoCuckooFilterImpl) GetFiltersNum 

func (cf *GoCuckooFilterImpl) GetFiltersNum() int

func (*GoCuckooFilterImpl) GetNumItems 

func (cf *GoCuckooFilterImpl) GetNumItems() uint64

func (*GoCuckooFilterImpl) Grow 

func (filter *GoCuckooFilterImpl) Grow()

func (*GoCuckooFilterImpl) Insert 

func (cf *GoCuckooFilterImpl) Insert(val []byte) error

InsertFP inserts a fingerprint into the filter, returning an error if the filter is full. static CuckooInsertStatus CuckooFilter_InsertFP(CuckooFilter *filter, const LookupParams *params)

func (*GoCuckooFilterImpl) KOInsert 

func (cf *GoCuckooFilterImpl) KOInsert(params *LookupParams, curFilter *SubCF) error

KOInsert attempts to insert a fingerprint into the filter, returning an error if the filter is full. static CuckooInsertStatus Filter_KOInsert(CuckooFilter *filter, SubCF *curFilter, 

const LookupParams *params)

type LookupParams 

type LookupParams struct {
	H1     CuckooHash        // First hash value
	H2     CuckooHash        // Second hash value
	Fp     CuckooFingerprint // Fingerprint
	Unique bool
}

func NewLookupParams 

func NewLookupParams(hash CuckooHash) *LookupParams

type MyCuckooBucket 

type MyCuckooBucket uint8

`typedef uint8_t MyCuckooBucket;` is directly equivalent to defining a new type based on uint8. This is a straightforward type definition in Go as well.

type RedisCFHeader 

type RedisCFHeader struct {
	NumItems      uint64
	NumBuckets    uint64
	NumDeletes    uint64
	NumFilters    uint64
	BucketSize    uint16
	MaxIterations uint16
	Expansion     uint16
}

func (*RedisCFHeader) NewRedisCuckooFilterImpl 

func (header *RedisCFHeader) NewRedisCuckooFilterImpl() *GoCuckooFilterImpl

type RedisDump 

type RedisDump struct {
	Data string
	Iter uint64
}

type SubCF 

type SubCF struct {
	NumBuckets uint64 // This field was 56 bits in the C version
	BucketSize uint8  // This field was 8 bits in the C version, matches Go's uint8
	Data       []CuckooBucket
}

SubCF struct equivalent without bit fields

func (*SubCF) Delete 

func (filter *SubCF) Delete(params *LookupParams) bool

Delete removes the fingerprint from the SubCF, returning true if the fingerprint was found. static int Filter_Delete(const SubCF *filter, const LookupParams *params)

func (*SubCF) Find 

func (filter *SubCF) Find(params *LookupParams) bool

Find returns true if the fingerprint is found in the SubCF, false otherwise. static int Filter_Find(const SubCF *filter, const LookupParams *params)

func (*SubCF) GetIndex 

func (subCF *SubCF) GetIndex(hash CuckooHash) uint32
uint32_t SubCF_GetIndex(const SubCF *subCF, CuckooHash hash) {
    return (hash % subCF->numBuckets) * subCF->bucketSize;
}

GetIndex returns the index of the bucket in the SubCF that corresponds to the given hash.

func (*SubCF) TryInsert 

func (filter *SubCF) TryInsert(params *LookupParams) bool

static uint8_t *Filter_FindAvailable(SubCF *filter, const LookupParams *params) FindAvailable returns a pointer to the first available slot in the SubCF, or nil if none are available. static uint8_t *Filter_FindAvailable(SubCF *filter, const LookupParams *params)

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.