hphp/util/bloom-filter.h

   1 /*
   2    +----------------------------------------------------------------------+
   3    | HipHop for PHP                                                       |
   4    +----------------------------------------------------------------------+
   5    | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com)  |
   6    +----------------------------------------------------------------------+
   7    | This source file is subject to version 3.01 of the PHP license,      |
   8    | that is bundled with this package in the file LICENSE, and is        |
   9    | available through the world-wide-web at the following url:           |
  10    | http://www.php.net/license/3_01.txt                                  |
  11    | If you did not receive a copy of the PHP license and are unable to   |
  12    | obtain it through the world-wide-web, please send a note to          |
  13    | license@php.net so we can mail you a copy immediately.               |
  14    +----------------------------------------------------------------------+
  15    */
  16 #ifndef HPHP_BLOOM_FILTER_H
  17 #define HPHP_BLOOM_FILTER_H
  18
  19 #include <boost/dynamic_bitset.hpp>
  20
  21 #include "hphp/util/hash.h"
  22
  23 namespace HPHP {
  24
  25 template<size_t NBITS> struct BloomFilter {
  26   BloomFilter() : bits_{NBITS} {}
  27   using T = const void*;
  28   static size_t h1(size_t h) { return h % NBITS; }
  29   static size_t h2(size_t h) { return (h / NBITS) % NBITS; }
  30   void insert(T x) {
  31     auto h = hash_int64(intptr_t(x));
  32     bits_.set(h1(h)).set(h2(h));
  33   }
  34   bool test(T x) const {
  35     auto h = hash_int64(intptr_t(x));
  36     return bits_.test(h1(h)) & bits_.test(h2(h));
  37   }
  38   void clear() {
  39     bits_.reset();
  40     static_assert(NBITS < (1LL << 32), "");
  41   }
  42   private:
  43   boost::dynamic_bitset<> bits_;
  44 };
  45 }
  46
  47 #endif // HPHP_BLOOM_FILTER_H