The cl-bloom Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

The cl-bloom Reference Manual

This is the cl-bloom Reference Manual, generated automatically by Declt version 4.0 beta 2 "William Riker" on Thu Sep 15 03:35:16 2022 GMT+0.

Table of Contents


1 Introduction

A simple Common Lisp implementation of Bloom filters with efficient hashing.

To make an empty filter, use MAKE-FILTER, which takes parameters for capacity and false drop (false positive) rate. If no false drop rate is specified, the value of FALSE-DROP-RATE is used. And also the third parameter specify whether the space is allocated from heap or by using static-vectors:make-static-vector.

;;; the space is allocated from heap by default
(defparameter *my-filter*
  (bloom:make-filter :capacity 1000 :false-drop-rate 1/1000))
;;; by setting the third parameter `:static` to T, 
;;; the space will be allocated statically
(defparameter *my-filter*
  (bloom:make-filter :capacity 1000 :false-drop-rate 1/1000 :static t))

Good values for the "order" (size) and "degree" (number of hashes) are calculated internally to obtain the theoretically ideal dimensions for a Bloom filter having the given parameters.

To add an element to a filter, use ADD:

(bloom:add *my-filter* "Add me")

To test for membership, use MEMBERP:

(bloom:memberp *my-filter* "Add me")
=> T

Since when the space is allocated by using static-vectors:make-static-vector, users must explicitly free the space by using static-vectors:free-static-vector. We thus provide two APIs, destroy-filter and with-filter, to help with that:

destroy-filter

(bloom:destroy-filter *filter*) 
;; => a destroyed filter instance, where all slots are being either set to NIL or freed

with-filter

;;; A 'with-' wrapper around filter, pretty useful when the space is allocated statically;
;;; it will free the space 'automatically'.
CL-USER> (bloom:with-filter (filter :capacity 10 :static t)
           (bloom:add filter "add")
           (bloom:add filter "minus")
           (print (bloom:memberp filter "add"))
           (print (bloom:memberp filter "minus")))

T 
T 
; No value

When filters are used as sets, FILTER-UNION, FILTER-NUNION, FILTER-NINTERSECTION, and FILTER-INTERSECTION behave like their namesakes. FILTER-IOR and FILTER-AND are shorthands for lists of filters.

The other utilities for composing filters are MAKE-COMPATIBLE-FILTER, which takes a filter and returns an empty, compatible filter, and COPY-FILTER, which takes a filter and returns an independent copy.

The utility MAKE-SET-FILTER covers one use case for Bloom filters: given a list, it returns a filter suitable for testing membership in that list, considered as a set.


2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 cl-bloom

Simple Bloom filters with efficient hashing.

Author

Paul M. Rodriguez <pmr@ruricolist.com>

License

MIT

Dependencies
  • cl-murmurhash (system).
  • static-vectors (system).
Source

cl-bloom.asd.

Child Components

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp   [Contents][Index]

3.1.1 cl-bloom/cl-bloom.asd

Source

cl-bloom.asd.

Parent Component

cl-bloom (system).

ASDF Systems

cl-bloom.


3.1.2 cl-bloom/package.lisp

Source

cl-bloom.asd.

Parent Component

cl-bloom (system).

Packages

cl-bloom.


Previous: , Up: Lisp   [Contents][Index]

3.1.3 cl-bloom/cl-bloom.lisp

Dependency

package.lisp (file).

Source

cl-bloom.asd.

Parent Component

cl-bloom (system).

Public Interface
Internals

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 cl-bloom

Source

package.lisp.

Nickname

bloom

Use List
  • cl-murmurhash.
  • common-lisp.
Public Interface
Internals

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Public Interface


Next: , Previous: , Up: Public Interface   [Contents][Index]

5.1.1 Special variables

Special Variable: *false-drop-rate*

Acceptable rate of false drops.

Package

cl-bloom.

Source

cl-bloom.lisp.


5.1.2 Macros

Macro: with-filter ((var &key capacity false-drop-rate static) &body body)

A ’with-’ wrapper around filter, pretty useful when the array space is allocated statically.

Package

cl-bloom.

Source

cl-bloom.lisp.


5.1.3 Ordinary functions

Function: add (filter element)

Make FILTER include ELEMENT.

Package

cl-bloom.

Source

cl-bloom.lisp.

Function: bloom-filter-p (object)
Package

cl-bloom.

Source

cl-bloom.lisp.

Function: copy-filter (filter)

Return a new Bloom filter like FILTER.

Package

cl-bloom.

Source

cl-bloom.lisp.

Function: destroy-filter (filter)

Destroy a Bloom filter instance. When its bit array is allocated statically,
then free the memory and set the reference of each slot to a default value by its type; otherwise, set all the references of slots to a default value by its type.

Package

cl-bloom.

Source

cl-bloom.lisp.

Function: filter-and (&rest filters)

Return intersection of all FILTERS as a new filter.

Package

cl-bloom.

Source

cl-bloom.lisp.

Function: filter-intersection (filter1 filter2)

Return the intersection of FILTER1 and FILTER2 as a new filter.

Package

cl-bloom.

Source

cl-bloom.lisp.

Function: filter-ior (&rest filters)

Return union of all FILTERS as a new filter.

Package

cl-bloom.

Source

cl-bloom.lisp.

Function: filter-nintersection (filter1 filter2)

Return the intersection of FILTER1 and FILTER2, overwriting FILTER1.

Package

cl-bloom.

Source

cl-bloom.lisp.

Function: filter-nunion (filter1 filter2)

Return the union of FILTER1 and FILTER2, overwriting FILTER1.

Package

cl-bloom.

Source

cl-bloom.lisp.

Function: filter-union (filter1 filter2)

Return the union of FILTER1 and FILTER2 as a new filter.

Package

cl-bloom.

Source

cl-bloom.lisp.

Function: make-compatible-filter (filter)

Return a new Bloom filter having the same order, degree, and seed as FILTER.

Package

cl-bloom.

Source

cl-bloom.lisp.

Function: make-filter (&key capacity false-drop-rate static)

Return a Bloom filter long enough to hold CAPACITY entries with the specified FALSE-DROP-RATE.

Package

cl-bloom.

Source

cl-bloom.lisp.

Function: make-set-filter (list &key static)

Make a Bloom filter from the elements of LIST, optimizing the order and degree of the filter according to the size of the set.

Package

cl-bloom.

Source

cl-bloom.lisp.

Function: memberp (filter element)

Return NIL if ELEMENT is definitely not present in FILTER. Return T if it might be present.

Package

cl-bloom.

Source

cl-bloom.lisp.


5.1.4 Standalone methods

Method: initialize-instance :after ((filter bloom-filter) &key order static)
Source

cl-bloom.lisp.


5.2 Internals


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.1 Ordinary functions

Function: compatible? (filter1 filter2)
Package

cl-bloom.

Source

cl-bloom.lisp.

Function: fake-hash (hash1 hash2 index order)
Package

cl-bloom.

Source

cl-bloom.lisp.

Function: make-bit-vector (size &key allocation)
Package

cl-bloom.

Source

cl-bloom.lisp.

Function: opt-degree ()
Package

cl-bloom.

Source

cl-bloom.lisp.

Function: opt-order (capacity)
Package

cl-bloom.

Source

cl-bloom.lisp.


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.2 Generic functions

Generic Reader: filter (condition)
Package

cl-bloom.

Methods
Reader Method: filter ((condition incompatible-filter))
Source

cl-bloom.lisp.

Target Slot

filter.

Generic Reader: filter-array (object)
Package

cl-bloom.

Methods
Reader Method: filter-array ((bloom-filter bloom-filter))

automatically generated reader method

Source

cl-bloom.lisp.

Target Slot

array.

Generic Writer: (setf filter-array) (object)
Package

cl-bloom.

Methods
Writer Method: (setf filter-array) ((bloom-filter bloom-filter))

automatically generated writer method

Source

cl-bloom.lisp.

Target Slot

array.

Generic Reader: filter-array-static-p (object)
Package

cl-bloom.

Methods
Reader Method: filter-array-static-p ((bloom-filter bloom-filter))

automatically generated reader method

Source

cl-bloom.lisp.

Target Slot

%array-static-p%.

Generic Writer: (setf filter-array-static-p) (object)
Package

cl-bloom.

Methods
Writer Method: (setf filter-array-static-p) ((bloom-filter bloom-filter))

automatically generated writer method

Source

cl-bloom.lisp.

Target Slot

%array-static-p%.

Generic Reader: filter-degree (object)
Package

cl-bloom.

Methods
Reader Method: filter-degree ((bloom-filter bloom-filter))

automatically generated reader method

Source

cl-bloom.lisp.

Target Slot

degree.

Generic Writer: (setf filter-degree) (object)
Package

cl-bloom.

Methods
Writer Method: (setf filter-degree) ((bloom-filter bloom-filter))

automatically generated writer method

Source

cl-bloom.lisp.

Target Slot

degree.

Generic Reader: filter-order (object)
Package

cl-bloom.

Methods
Reader Method: filter-order ((bloom-filter bloom-filter))

automatically generated reader method

Source

cl-bloom.lisp.

Target Slot

order.

Generic Writer: (setf filter-order) (object)
Package

cl-bloom.

Methods
Writer Method: (setf filter-order) ((bloom-filter bloom-filter))

automatically generated writer method

Source

cl-bloom.lisp.

Target Slot

order.

Generic Reader: filter-seed (object)
Generic Writer: (setf filter-seed) (object)
Package

cl-bloom.

Methods
Reader Method: filter-seed ((bloom-filter bloom-filter))
Writer Method: (setf filter-seed) ((bloom-filter bloom-filter))

Cache the value of MURMURHASH:*DEFAULT-SEED*
at the time the filter was created, lest changing the default seed invalidate the filter.

Source

cl-bloom.lisp.

Target Slot

seed.


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.3 Conditions

Condition: incompatible-filter
Package

cl-bloom.

Source

cl-bloom.lisp.

Direct superclasses

error.

Direct methods

filter.

Direct slots
Slot: filter
Initargs

:filter

Readers

filter.

Writers

This slot is read-only.


Previous: , Up: Internals   [Contents][Index]

5.2.4 Classes

Class: bloom-filter
Package

cl-bloom.

Source

cl-bloom.lisp.

Direct methods
Direct Default Initargs
InitargValue
:degree(opt-degree)
:order256
:seed*default-seed*
Direct slots
Slot: array
Package

common-lisp.

Type

simple-bit-vector

Initargs

:array

Readers

filter-array.

Writers

(setf filter-array).

Slot: %array-static-p%
Type

symbol

Initargs

:array-static-p

Readers

filter-array-static-p.

Writers

(setf filter-array-static-p).

Slot: order
Type

integer

Initargs

:order

Readers

filter-order.

Writers

(setf filter-order).

Slot: degree
Type

integer

Initargs

:degree

Readers

filter-degree.

Writers

(setf filter-degree).

Slot: seed

Cache the value of MURMURHASH:*DEFAULT-SEED*
at the time the filter was created, lest changing the default seed invalidate the filter.

Type

integer

Initargs

:seed

Readers

filter-seed.

Writers

(setf filter-seed).


Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts


Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   (  
A   B   C   D   F   G   I   M   O   W  
Index Entry  Section

(
(setf filter-array): Private generic functions
(setf filter-array): Private generic functions
(setf filter-array-static-p): Private generic functions
(setf filter-array-static-p): Private generic functions
(setf filter-degree): Private generic functions
(setf filter-degree): Private generic functions
(setf filter-order): Private generic functions
(setf filter-order): Private generic functions
(setf filter-seed): Private generic functions
(setf filter-seed): Private generic functions

A
add: Public ordinary functions

B
bloom-filter-p: Public ordinary functions

C
compatible?: Private ordinary functions
copy-filter: Public ordinary functions

D
destroy-filter: Public ordinary functions

F
fake-hash: Private ordinary functions
filter: Private generic functions
filter: Private generic functions
filter-and: Public ordinary functions
filter-array: Private generic functions
filter-array: Private generic functions
filter-array-static-p: Private generic functions
filter-array-static-p: Private generic functions
filter-degree: Private generic functions
filter-degree: Private generic functions
filter-intersection: Public ordinary functions
filter-ior: Public ordinary functions
filter-nintersection: Public ordinary functions
filter-nunion: Public ordinary functions
filter-order: Private generic functions
filter-order: Private generic functions
filter-seed: Private generic functions
filter-seed: Private generic functions
filter-union: Public ordinary functions
Function, add: Public ordinary functions
Function, bloom-filter-p: Public ordinary functions
Function, compatible?: Private ordinary functions
Function, copy-filter: Public ordinary functions
Function, destroy-filter: Public ordinary functions
Function, fake-hash: Private ordinary functions
Function, filter-and: Public ordinary functions
Function, filter-intersection: Public ordinary functions
Function, filter-ior: Public ordinary functions
Function, filter-nintersection: Public ordinary functions
Function, filter-nunion: Public ordinary functions
Function, filter-union: Public ordinary functions
Function, make-bit-vector: Private ordinary functions
Function, make-compatible-filter: Public ordinary functions
Function, make-filter: Public ordinary functions
Function, make-set-filter: Public ordinary functions
Function, memberp: Public ordinary functions
Function, opt-degree: Private ordinary functions
Function, opt-order: Private ordinary functions

G
Generic Function, (setf filter-array): Private generic functions
Generic Function, (setf filter-array-static-p): Private generic functions
Generic Function, (setf filter-degree): Private generic functions
Generic Function, (setf filter-order): Private generic functions
Generic Function, (setf filter-seed): Private generic functions
Generic Function, filter: Private generic functions
Generic Function, filter-array: Private generic functions
Generic Function, filter-array-static-p: Private generic functions
Generic Function, filter-degree: Private generic functions
Generic Function, filter-order: Private generic functions
Generic Function, filter-seed: Private generic functions

I
initialize-instance: Public standalone methods

M
Macro, with-filter: Public macros
make-bit-vector: Private ordinary functions
make-compatible-filter: Public ordinary functions
make-filter: Public ordinary functions
make-set-filter: Public ordinary functions
memberp: Public ordinary functions
Method, (setf filter-array): Private generic functions
Method, (setf filter-array-static-p): Private generic functions
Method, (setf filter-degree): Private generic functions
Method, (setf filter-order): Private generic functions
Method, (setf filter-seed): Private generic functions
Method, filter: Private generic functions
Method, filter-array: Private generic functions
Method, filter-array-static-p: Private generic functions
Method, filter-degree: Private generic functions
Method, filter-order: Private generic functions
Method, filter-seed: Private generic functions
Method, initialize-instance: Public standalone methods

O
opt-degree: Private ordinary functions
opt-order: Private ordinary functions

W
with-filter: Public macros

Jump to:   (  
A   B   C   D   F   G   I   M   O   W