ssp_bfilter.h

Go to the documentation of this file.

/* Copyright 2005 Ben Hyde
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/** \file ssp_bfilter.h
 * \brief The API for a bloom filter.
 *
 * This API defines an opaque type ssp_bfilter_t used to represent a
 * set of symbols, but with only two operations on that set.
 * membership, and insert.
 *
 * That algorithum used is known as a Bloom filter, see
 * <> for additional info.  As such it is possible for the
 * membership query to return false positives.
 *
 * \dot
 * digraph {
 *   rankdir=LR; 
 *   node [shape=plaintext];
 *   create -> use -> retire [style=dotted];
 *   {rank=same; use; ssp_bfilter_t; bloom_insert; bloom_member_p;  }
 *   {rank=same; create; bloom_make; }
 *   {rank=same; retire; apr_clear_pool; }
 *   bloom_make -> ssp_bfilter_t -> apr_clear_pool;
 *   ssp_bfilter_t -> {bloom_insert; bloom_member_p } -> ssp_bfilter_t;
 *   { node [shape=rectangle,label="a ssp_bfilter_t"];  ssp_bfilter_t;}  
 * }
 * \enddot
 *
 */

#include "ssp_items.h"
#include <apr_pools.h>

/** \brief The type ssp_bfilter_t is the cornerstone of this API.
 *
 * Instances are allocated in an APR pool and survive until
 * that pool is cleared.  You may insert symbols into the
 * set, and enquire if a symbol is a member of a set.
 *
 */
typedef struct ssp_bfilter_s ssp_bfilter_t;

/** \brief Create a ssp_bfilter_t, i.e. bloom filter.
 *
 * Instantiate a fresh ssp_bfilter_t in the pool given.  The user provides
 * two hash functions that will be used to map symbols into the
 * state of the filter.  Two parameters filter_scale and filter_phase
 * configure how accurate the filter is.
 *
 * Scales, a small integer, sets the size of the bit map.  The bit
 * map is 2^scale in size.  While the phase sets how many bits
 * are set in the bitmap for each symbol inserted.
 */
extern ssp_bfilter_t *ssp_bfilter_create(apr_pool_t *pool,
                                         ssp_hash_function_t *h1,
                                         ssp_hash_function_t *h2,
                                         apr_uint16_t filter_scale,
                                         apr_uint16_t filter_phase);

/** The number of one bits in the underlying bitmap.
 *
 * Since 2^scale is the total number of bits you can use this
 * to get a feel for how likely false positives are becoming.
 * This can be used to compute how saturated the filter is, and
 * in combination with the phase estimate the chance for false
 * positives.
 */
extern apr_uint32_t ssp_bfilter_density(ssp_bfilter_t *f);

/** \brief Insert a symbol into the filter.
 * 
 * Calls on bloom_insert adds a symbol to the set of symbols
 * in the bloom filter.
 **/
extern void ssp_bfilter_insert(ssp_bfilter_t *b, void *symbol);

/** \brief Return false if symbol is not a member of the set.
 *
 * This never returns a false negative but may occationally
 * return a false positive.
 **/
int ssp_bfilter_member_p(ssp_bfilter_t *h, void *symbol);

/** \brief The bloom filter including bitmap, hash functions, etc. etc.
 *
 * It's unlikely users will need access to the internals of
 * ssp_bfilter_t, but it might be useful.
 */
struct ssp_bfilter_s {
  apr_pool_t *object_pool;    /**< This and it's children reside in this pool */
  ssp_hash_function_t *h1;  /**< ... */
  ssp_hash_function_t *h2;  /**< ... */
  apr_uint32_t scale;         /**< The bit map has 2^scale bits in it */
  apr_uint32_t phase;       /**< Each symbol sets this many bits */
  apr_uint32_t mask;          /**< 2^scale-1, used to map hash into bitmap index */
  apr_uint64_t *bitmap;       /**< The bitmap of scale */
};

---