cbf

README

Counting Bloom Filter (CBF)

This is a project that implements a CBF in Go that uses 1-byte per entry. It uses the following hash functions, but could be re-written easily to use any hash function(s):

• Adler32 (from hash/adler32)
• FNV32 (from hash/fnv)
• Murmur3-32 (from github.com/spaolacci/murmur3)

Usage

Here's the interface:

type CountingBloomFilter interface {
  Add(s string)
  Remove(s string)
  Test(s string) bool
}

You can create an instance using CreateCBF(size uint32). You can wrap an instance with logging via CreateLoggingCBF(cbf CountingBloomFilter). Here's an example:

package main

import (
  "fmt"

  "github.com/everettcaleb/cbf"
)

func main() {
  f := cbf.CreateLoggingCBF(cbf.CreateCBF(1024 * 1024)) // 1 MB w/ logging
  f.Add("test")
  f.Add("test2")
  fmt.Printf("Test for 'test': %t\n", f.Test("test"))
  fmt.Printf("Test for 'test2': %t\n", f.Test("test2"))
  fmt.Printf("Test for 'test3': %t\n", f.Test("test3"))
  f.Remove("test2")
  fmt.Printf("Test for 'test': %t\n", f.Test("test"))
  fmt.Printf("Test for 'test2': %t\n", f.Test("test2"))
  fmt.Printf("Test for 'test3': %t\n", f.Test("test3"))
}

License

MIT License

Copyright 2018 Caleb Everett

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Documentation

Index

• type CountingBloomFilter
  • func CreateCBF(size uint32) CountingBloomFilter
  • func CreateLoggingCBF(cbf CountingBloomFilter) CountingBloomFilter

Types

type CountingBloomFilter

type CountingBloomFilter interface {
	// Add hashes the input string and adds it to the filter by incrementing the entry at the hash % size
	Add(s string)
	// Remove hashes the input string and removes it from the filter by decrementing the entry at the hash % size
	Remove(s string)
	// Test hashes the input string and checks the entries at hash % size to say whether that string has possibly been added to the filter
	Test(s string) bool
	// contains filtered or unexported methods
}

CountingBloomFilter is an interface for a Bloom Filter that supports removal through counting

func CreateCBF

func CreateCBF(size uint32) CountingBloomFilter

CreateCBF creates an implementation of CountingBloomFilter that uses 1-byte entries

func CreateLoggingCBF

func CreateLoggingCBF(cbf CountingBloomFilter) CountingBloomFilter

CreateLoggingCBF wraps an existing CBF with logging to STDOUT