BloomFilter.h

/*
 * Copyright (c) 2008-2014, Pedigree Developers
 *
 * Please see the CONTRIB file in the root of the source tree for a full
 * list of contributors.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */
 
#ifndef KERNEL_UTILITIES_BLOOMFILTER_H
#define KERNEL_UTILITIES_BLOOMFILTER_H
 
#include "pedigree/kernel/processor/types.h"
#include "pedigree/kernel/utilities/ExtensibleBitmap.h"
#include "pedigree/kernel/utilities/smhasher/MurmurHash3.h"
 
template <class T>
class BloomFilter {
  friend class CacheMemoryTestPeer;
 
 public:
  BloomFilter(size_t length, size_t hashcount)
      : m_Bitmap(), m_nLength(length), m_nHashCount(hashcount) {}
  virtual ~BloomFilter() {};
 
  void add(const T& data) {
    add(&data, sizeof(T));
  }
 
  void add(const T* data, size_t length) {
    uint64_t baseHash[2];
    MurmurHash3_x64_128(data, length, 0, baseHash);
 
    for (size_t i = 0; i < m_nHashCount; ++i) {
      uint64_t n = (baseHash[0] + (i * baseHash[1])) % m_nLength;
      m_Bitmap.set(n);
    }
  }
 
  bool contains(const T& data) {
    return contains(&data, sizeof(T));
  }
 
  bool contains(const T* data, size_t length) {
    uint64_t baseHash[2];
    MurmurHash3_x64_128(data, length, 0, baseHash);
 
    for (size_t i = 0; i < m_nHashCount; ++i) {
      uint64_t n = (baseHash[0] + (i * baseHash[1])) % m_nLength;
      if (!m_Bitmap.test(n)) {
        return false;
      }
    }
 
    return true;
  }
 
  void clear() {
    for (size_t i = 0; i < m_nLength; ++i) {
      m_Bitmap.clear(i);
    }
  }
 
 private:
  ExtensibleBitmap m_Bitmap;
  size_t m_nLength;
  size_t m_nHashCount;
};
 
extern template class BloomFilter<void*>;     // IWYU pragma: keep
extern template class BloomFilter<int8_t>;    // IWYU pragma: keep
extern template class BloomFilter<int16_t>;   // IWYU pragma: keep
extern template class BloomFilter<int32_t>;   // IWYU pragma: keep
extern template class BloomFilter<int64_t>;   // IWYU pragma: keep
extern template class BloomFilter<uint8_t>;   // IWYU pragma: keep
extern template class BloomFilter<uint16_t>;  // IWYU pragma: keep
extern template class BloomFilter<uint32_t>;  // IWYU pragma: keep
extern template class BloomFilter<uint64_t>;  // IWYU pragma: keep
 
#endif