The cl-bloom Reference Manual

Table of Contents

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

The cl-bloom Reference Manual

This is the cl-bloom Reference Manual, generated automatically by Declt version 2.3 "Robert April" on Tue Jan 09 13:26:32 2018 GMT+0.


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

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.


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

2 Systems

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


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

2.1 cl-bloom

Author

Paul M. Rodriguez <pmr@ruricolist.com>

License

MIT

Description

Simple Bloom filters with efficient hashing.

Dependencies
Source

cl-bloom.asd (file)

Components

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

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 files   [Contents][Index]

3.1.1 cl-bloom.asd

Location

cl-bloom.asd

Systems

cl-bloom (system)


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

3.1.2 cl-bloom/package.lisp

Parent

cl-bloom (system)

Location

package.lisp

Packages

cl-bloom


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

3.1.3 cl-bloom/cl-bloom.lisp

Dependency

package.lisp (file)

Parent

cl-bloom (system)

Location

cl-bloom.lisp

Exported Definitions
Internal Definitions

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

4 Packages

Packages are listed by definition order.


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

4.1 cl-bloom

Source

package.lisp (file)

Nickname

bloom

Use List
Exported Definitions
Internal Definitions

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

5 Definitions

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


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

5.1 Exported definitions


Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Special variables

Special Variable: *false-drop-rate*

Acceptable rate of false drops.

Package

cl-bloom

Source

cl-bloom.lisp (file)


Next: , Previous: , Up: Exported definitions   [Contents][Index]

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 (file)


Previous: , Up: Exported definitions   [Contents][Index]

5.1.3 Functions

Function: add FILTER ELEMENT

Make FILTER include ELEMENT.

Package

cl-bloom

Source

cl-bloom.lisp (file)

Function: bloom-filter-p OBJECT
Package

cl-bloom

Source

cl-bloom.lisp (file)

Function: copy-filter FILTER

Return a new Bloom filter like FILTER.

Package

cl-bloom

Source

cl-bloom.lisp (file)

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 (file)

Function: filter-and &rest FILTERS

Return intersection of all FILTERS as a new filter.

Package

cl-bloom

Source

cl-bloom.lisp (file)

Function: filter-intersection FILTER1 FILTER2

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

Package

cl-bloom

Source

cl-bloom.lisp (file)

Function: filter-ior &rest FILTERS

Return union of all FILTERS as a new filter.

Package

cl-bloom

Source

cl-bloom.lisp (file)

Function: filter-nintersection FILTER1 FILTER2

Return the intersection of FILTER1 and FILTER2, overwriting FILTER1.

Package

cl-bloom

Source

cl-bloom.lisp (file)

Function: filter-nunion FILTER1 FILTER2

Return the union of FILTER1 and FILTER2, overwriting FILTER1.

Package

cl-bloom

Source

cl-bloom.lisp (file)

Function: filter-union FILTER1 FILTER2

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

Package

cl-bloom

Source

cl-bloom.lisp (file)

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 (file)

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 (file)

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 (file)

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 (file)


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

5.2 Internal definitions


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Functions

Function: compatible? FILTER1 FILTER2
Package

cl-bloom

Source

cl-bloom.lisp (file)

Function: fake-hash HASH1 HASH2 INDEX ORDER
Package

cl-bloom

Source

cl-bloom.lisp (file)

Function: make-bit-vector SIZE &key ALLOCATION
Package

cl-bloom

Source

cl-bloom.lisp (file)

Function: opt-degree ()
Package

cl-bloom

Source

cl-bloom.lisp (file)

Function: opt-order CAPACITY
Package

cl-bloom

Source

cl-bloom.lisp (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Generic functions

Generic Function: filter CONDITION
Package

cl-bloom

Methods
Method: filter (CONDITION incompatible-filter)
Source

cl-bloom.lisp (file)

Generic Function: filter-array OBJECT
Generic Function: (setf filter-array) NEW-VALUE OBJECT
Package

cl-bloom

Methods
Method: filter-array (BLOOM-FILTER bloom-filter)

automatically generated reader method

Source

cl-bloom.lisp (file)

Method: (setf filter-array) NEW-VALUE (BLOOM-FILTER bloom-filter)

automatically generated writer method

Source

cl-bloom.lisp (file)

Generic Function: filter-array-static-p OBJECT
Generic Function: (setf filter-array-static-p) NEW-VALUE OBJECT
Package

cl-bloom

Methods
Method: filter-array-static-p (BLOOM-FILTER bloom-filter)

automatically generated reader method

Source

cl-bloom.lisp (file)

Method: (setf filter-array-static-p) NEW-VALUE (BLOOM-FILTER bloom-filter)

automatically generated writer method

Source

cl-bloom.lisp (file)

Generic Function: filter-degree OBJECT
Generic Function: (setf filter-degree) NEW-VALUE OBJECT
Package

cl-bloom

Methods
Method: filter-degree (BLOOM-FILTER bloom-filter)

automatically generated reader method

Source

cl-bloom.lisp (file)

Method: (setf filter-degree) NEW-VALUE (BLOOM-FILTER bloom-filter)

automatically generated writer method

Source

cl-bloom.lisp (file)

Generic Function: filter-order OBJECT
Generic Function: (setf filter-order) NEW-VALUE OBJECT
Package

cl-bloom

Methods
Method: filter-order (BLOOM-FILTER bloom-filter)

automatically generated reader method

Source

cl-bloom.lisp (file)

Method: (setf filter-order) NEW-VALUE (BLOOM-FILTER bloom-filter)

automatically generated writer method

Source

cl-bloom.lisp (file)

Generic Function: filter-seed OBJECT
Generic Function: (setf filter-seed) NEW-VALUE OBJECT
Package

cl-bloom

Methods
Method: filter-seed (BLOOM-FILTER bloom-filter)
Method: (setf filter-seed) NEW-VALUE (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 (file)


Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.3 Conditions

Condition: incompatible-filter ()
Package

cl-bloom

Source

cl-bloom.lisp (file)

Direct superclasses

error (condition)

Direct methods

filter (method)

Direct slots
Slot: filter
Initargs

:filter

Readers

filter (generic function)


Previous: , Up: Internal definitions   [Contents][Index]

5.2.4 Classes

Class: bloom-filter ()
Package

cl-bloom

Source

cl-bloom.lisp (file)

Direct superclasses

standard-object (class)

Direct methods
Direct slots
Slot: array
Type

simple-bit-vector

Initargs

:array

Readers

filter-array (generic function)

Writers

(setf filter-array) (generic function)

Slot: %array-static-p%
Type

symbol

Initargs

:array-static-p

Readers

filter-array-static-p (generic function)

Writers

(setf filter-array-static-p) (generic function)

Slot: order
Type

integer

Initargs

:order

Readers

filter-order (generic function)

Writers

(setf filter-order) (generic function)

Slot: degree
Type

integer

Initargs

:degree

Readers

filter-degree (generic function)

Writers

(setf filter-degree) (generic function)

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 (generic function)

Writers

(setf filter-seed) (generic function)

Direct Default Initargs
InitargValue
:degree(cl-bloom::opt-degree)
:order256
:seedcl-murmurhash:*default-seed*

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

Appendix A Indexes


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

A.1 Concepts

Jump to:   C   F   L  
Index Entry  Section

C
cl-bloom.asd: The cl-bloom<dot>asd file
cl-bloom/cl-bloom.lisp: The cl-bloom/cl-bloom<dot>lisp file
cl-bloom/package.lisp: The cl-bloom/package<dot>lisp file

F
File, Lisp, cl-bloom.asd: The cl-bloom<dot>asd file
File, Lisp, cl-bloom/cl-bloom.lisp: The cl-bloom/cl-bloom<dot>lisp file
File, Lisp, cl-bloom/package.lisp: The cl-bloom/package<dot>lisp file

L
Lisp File, cl-bloom.asd: The cl-bloom<dot>asd file
Lisp File, cl-bloom/cl-bloom.lisp: The cl-bloom/cl-bloom<dot>lisp file
Lisp File, cl-bloom/package.lisp: The cl-bloom/package<dot>lisp file

Jump to:   C   F   L  

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

A.2 Functions

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

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

A
add: Exported functions

B
bloom-filter-p: Exported functions

C
compatible?: Internal functions
copy-filter: Exported functions

D
destroy-filter: Exported functions

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

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

M
Macro, with-filter: Exported macros
make-bit-vector: Internal functions
make-compatible-filter: Exported functions
make-filter: Exported functions
make-set-filter: Exported functions
memberp: Exported functions
Method, (setf filter-array): Internal generic functions
Method, (setf filter-array-static-p): Internal generic functions
Method, (setf filter-degree): Internal generic functions
Method, (setf filter-order): Internal generic functions
Method, (setf filter-seed): Internal generic functions
Method, filter: Internal generic functions
Method, filter-array: Internal generic functions
Method, filter-array-static-p: Internal generic functions
Method, filter-degree: Internal generic functions
Method, filter-order: Internal generic functions
Method, filter-seed: Internal generic functions

O
opt-degree: Internal functions
opt-order: Internal functions

W
with-filter: Exported macros

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

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

A.3 Variables

Jump to:   %   *  
A   D   F   O   S  
Index Entry  Section

%
%array-static-p%: Internal classes

*
*false-drop-rate*: Exported special variables

A
array: Internal classes

D
degree: Internal classes

F
filter: Internal conditions

O
order: Internal classes

S
seed: Internal classes
Slot, %array-static-p%: Internal classes
Slot, array: Internal classes
Slot, degree: Internal classes
Slot, filter: Internal conditions
Slot, order: Internal classes
Slot, seed: Internal classes
Special Variable, *false-drop-rate*: Exported special variables

Jump to:   %   *  
A   D   F   O   S  

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

A.4 Data types

Jump to:   B   C   I   P   S  
Index Entry  Section

B
bloom-filter: Internal classes

C
cl-bloom: The cl-bloom system
cl-bloom: The cl-bloom package
Class, bloom-filter: Internal classes
Condition, incompatible-filter: Internal conditions

I
incompatible-filter: Internal conditions

P
Package, cl-bloom: The cl-bloom package

S
System, cl-bloom: The cl-bloom system

Jump to:   B   C   I   P   S