Back to index

enigmail  1.4.3
Public Member Functions | Private Member Functions | Static Private Member Functions | Private Attributes | Static Private Attributes
mozilla::BloomFilter< KeySize, T > Class Template Reference

#include <BloomFilter.h>

List of all members.

Public Member Functions

 BloomFilter ()
void clear ()
void add (const T *t)
void remove (const T *t)
bool mightContain (const T *t) const
void add (uint32_t hash)
void remove (uint32_t hash)
bool mightContain (uint32_t hash) const

Private Member Functions

uint8_tfirstSlot (uint32_t hash)
uint8_tsecondSlot (uint32_t hash)
const uint8_tfirstSlot (uint32_t hash) const
const uint8_tsecondSlot (uint32_t hash) const

Static Private Member Functions

static uint32_t hash1 (uint32_t hash)
static uint32_t hash2 (uint32_t hash)
static bool full (const uint8_t &slot)

Private Attributes

uint8_t counters [arraySize]

Static Private Attributes

static const size_t arraySize = (1 << KeySize)
static const uint32_t keyMask = (1 << KeySize) - 1
static const uint32_t keyShift = 16

Detailed Description

template<unsigned KeySize, class T>
class mozilla::BloomFilter< KeySize, T >

Definition at line 55 of file BloomFilter.h.


Constructor & Destructor Documentation

template<unsigned KeySize, class T >
mozilla::BloomFilter< KeySize, T >::BloomFilter ( ) [inline]

Definition at line 105 of file BloomFilter.h.

                  {
        MOZ_STATIC_ASSERT(KeySize <= keyShift, "KeySize too big");

        // Should we have a custom operator new using calloc instead and
        // require that we're allocated via the operator?
        clear();
    }

Here is the call graph for this function:


Member Function Documentation

template<unsigned KeySize, class T >
MOZ_ALWAYS_INLINE void mozilla::BloomFilter< KeySize, T >::add ( const T *  t)

Definition at line 185 of file BloomFilter.h.

{
    uint32_t hash = t->hash();
    return add(hash);
}
template<unsigned KeySize, class T >
void mozilla::BloomFilter< KeySize, T >::add ( uint32_t  hash) [inline]

Definition at line 172 of file BloomFilter.h.

{
    uint8_t& slot1 = firstSlot(hash);
    if (MOZ_LIKELY(!full(slot1)))
        ++slot1;

    uint8_t& slot2 = secondSlot(hash);
    if (MOZ_LIKELY(!full(slot2)))
        ++slot2;
}
template<unsigned KeySize, class T >
void mozilla::BloomFilter< KeySize, T >::clear ( ) [inline]

Definition at line 165 of file BloomFilter.h.

{
    memset(counters, 0, arraySize);
}

Here is the caller graph for this function:

template<unsigned KeySize, class T >
uint8_t& mozilla::BloomFilter< KeySize, T >::firstSlot ( uint32_t  hash) [inline, private]

Definition at line 153 of file BloomFilter.h.

{ return counters[hash1(hash)]; }

Here is the call graph for this function:

template<unsigned KeySize, class T >
const uint8_t& mozilla::BloomFilter< KeySize, T >::firstSlot ( uint32_t  hash) const [inline, private]

Definition at line 155 of file BloomFilter.h.

{ return counters[hash1(hash)]; }

Here is the call graph for this function:

template<unsigned KeySize, class T >
static bool mozilla::BloomFilter< KeySize, T >::full ( const uint8_t slot) [inline, static, private]

Definition at line 158 of file BloomFilter.h.

{ return slot == UINT8_MAX; }
template<unsigned KeySize, class T >
static uint32_t mozilla::BloomFilter< KeySize, T >::hash1 ( uint32_t  hash) [inline, static, private]

Definition at line 150 of file BloomFilter.h.

{ return hash & keyMask; }

Here is the caller graph for this function:

template<unsigned KeySize, class T >
static uint32_t mozilla::BloomFilter< KeySize, T >::hash2 ( uint32_t  hash) [inline, static, private]

Definition at line 151 of file BloomFilter.h.

{ return (hash >> keyShift) & keyMask; }

Here is the caller graph for this function:

template<unsigned KeySize, class T >
MOZ_ALWAYS_INLINE bool mozilla::BloomFilter< KeySize, T >::mightContain ( const T *  t) const

Definition at line 224 of file BloomFilter.h.

{
    uint32_t hash = t->hash();
    return mightContain(hash);
}
template<unsigned KeySize, class T >
MOZ_ALWAYS_INLINE bool mozilla::BloomFilter< KeySize, T >::mightContain ( uint32_t  hash) const

Definition at line 216 of file BloomFilter.h.

{
    // Check that all the slots for this hash contain something
    return firstSlot(hash) && secondSlot(hash);
}
template<unsigned KeySize, class T >
MOZ_ALWAYS_INLINE void mozilla::BloomFilter< KeySize, T >::remove ( const T *  t)

Definition at line 208 of file BloomFilter.h.

{
    uint32_t hash = t->hash();
    remove(hash);
}
template<unsigned KeySize, class T >
void mozilla::BloomFilter< KeySize, T >::remove ( uint32_t  hash) [inline]

Definition at line 193 of file BloomFilter.h.

{
    // If the slots are full, we don't know whether we bumped them to be
    // there when we added or not, so just leave them full.
    uint8_t& slot1 = firstSlot(hash);
    if (MOZ_LIKELY(!full(slot1)))
        --slot1;

    uint8_t& slot2 = secondSlot(hash);
    if (MOZ_LIKELY(!full(slot2)))
        --slot2;
}
template<unsigned KeySize, class T >
uint8_t& mozilla::BloomFilter< KeySize, T >::secondSlot ( uint32_t  hash) [inline, private]

Definition at line 154 of file BloomFilter.h.

{ return counters[hash2(hash)]; }

Here is the call graph for this function:

template<unsigned KeySize, class T >
const uint8_t& mozilla::BloomFilter< KeySize, T >::secondSlot ( uint32_t  hash) const [inline, private]

Definition at line 156 of file BloomFilter.h.

{ return counters[hash2(hash)]; }

Here is the call graph for this function:


Member Data Documentation

template<unsigned KeySize, class T >
const size_t mozilla::BloomFilter< KeySize, T >::arraySize = (1 << KeySize) [static, private]

Definition at line 146 of file BloomFilter.h.

template<unsigned KeySize, class T >
uint8_t mozilla::BloomFilter< KeySize, T >::counters[arraySize] [private]

Definition at line 160 of file BloomFilter.h.

template<unsigned KeySize, class T >
const uint32_t mozilla::BloomFilter< KeySize, T >::keyMask = (1 << KeySize) - 1 [static, private]

Definition at line 147 of file BloomFilter.h.

template<unsigned KeySize, class T >
const uint32_t mozilla::BloomFilter< KeySize, T >::keyShift = 16 [static, private]

Definition at line 148 of file BloomFilter.h.


The documentation for this class was generated from the following file: