ceph/src/common/bloom_filter.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 #include "common/bloom_filter.hpp"
   5
   6 #include <numeric>
   7 #include "include/intarith.h"
   8
   9 using ceph::bufferlist;
  10 using ceph::bufferptr;
  11 using ceph::Formatter;
  12
  13 double bloom_filter::density() const
  14 {
  15   // TODO: use transform_reduce() in GCC-9 and up
  16   unsigned set = std::accumulate(
  17     bit_table_.begin(),
  18     bit_table_.begin() + table_size_,
  19     0u, [](unsigned set, cell_type cell) {
  20       return set + popcount(cell);
  21     });
  22   return (double)set / (table_size_ * sizeof(cell_type) * CHAR_BIT);
  23 }
  24
  25 void bloom_filter::encode(bufferlist& bl) const
  26 {
  27   ENCODE_START(2, 2, bl);
  28   encode((uint64_t)salt_count_, bl);
  29   encode((uint64_t)insert_count_, bl);
  30   encode((uint64_t)target_element_count_, bl);
  31   encode((uint64_t)random_seed_, bl);
  32   encode(bit_table_, bl);
  33   ENCODE_FINISH(bl);
  34 }
  35
  36 void bloom_filter::decode(bufferlist::const_iterator& p)
  37 {
  38   DECODE_START(2, p);
  39   uint64_t v;
  40   decode(v, p);
  41   salt_count_ = v;
  42   decode(v, p);
  43   insert_count_ = v;
  44   decode(v, p);
  45   target_element_count_ = v;
  46   decode(v, p);
  47   random_seed_ = v;
  48   salt_.clear();
  49   generate_unique_salt();
  50   decode(bit_table_, p);
  51   table_size_ = bit_table_.size();
  52   DECODE_FINISH(p);
  53 }
  54
  55 void bloom_filter::dump(Formatter *f) const
  56 {
  57   f->dump_unsigned("salt_count", salt_count_);
  58   f->dump_unsigned("table_size", table_size_);
  59   f->dump_unsigned("insert_count", insert_count_);
  60   f->dump_unsigned("target_element_count", target_element_count_);
  61   f->dump_unsigned("random_seed", random_seed_);
  62
  63   f->open_array_section("salt_table");
  64   for (std::vector<bloom_type>::const_iterator i = salt_.begin(); i != salt_.end(); ++i)
  65     f->dump_unsigned("salt", *i);
  66   f->close_section();
  67
  68   f->open_array_section("bit_table");
  69   for (auto byte : bit_table_) {
  70     f->dump_unsigned("byte", (unsigned)byte);
  71   }
  72   f->close_section();
  73 }
  74
  75 void bloom_filter::generate_test_instances(std::list<bloom_filter*>& ls)
  76 {
  77   ls.push_back(new bloom_filter(10, .5, 1));
  78   ls.push_back(new bloom_filter(10, .5, 1));
  79   ls.back()->insert("foo");
  80   ls.back()->insert("bar");
  81   ls.push_back(new bloom_filter(50, .5, 1));
  82   ls.back()->insert("foo");
  83   ls.back()->insert("bar");
  84   ls.back()->insert("baz");
  85   ls.back()->insert("boof");
  86   ls.back()->insert("boogggg");
  87 }
  88
  89
  90 void compressible_bloom_filter::encode(bufferlist& bl) const
  91 {
  92   ENCODE_START(2, 2, bl);
  93   bloom_filter::encode(bl);
  94
  95   uint32_t s = size_list.size();
  96   encode(s, bl);
  97   for (std::vector<size_t>::const_iterator p = size_list.begin();
  98        p != size_list.end(); ++p)
  99     encode((uint64_t)*p, bl);
 100
 101   ENCODE_FINISH(bl);
 102 }
 103
 104 void compressible_bloom_filter::decode(bufferlist::const_iterator& p)
 105 {
 106   DECODE_START(2, p);
 107   bloom_filter::decode(p);
 108
 109   uint32_t s;
 110   decode(s, p);
 111   size_list.resize(s);
 112   for (unsigned i = 0; i < s; i++) {
 113     uint64_t v;
 114     decode(v, p);
 115     size_list[i] = v;
 116   }
 117
 118   DECODE_FINISH(p);
 119 }
 120
 121 void compressible_bloom_filter::dump(Formatter *f) const
 122 {
 123   bloom_filter::dump(f);
 124
 125   f->open_array_section("table_sizes");
 126   for (std::vector<size_t>::const_iterator p = size_list.begin();
 127        p != size_list.end(); ++p)
 128     f->dump_unsigned("size", (uint64_t)*p);
 129   f->close_section();
 130 }
 131
 132 void compressible_bloom_filter::generate_test_instances(std::list<compressible_bloom_filter*>& ls)
 133 {
 134   ls.push_back(new compressible_bloom_filter(10, .5, 1));
 135   ls.push_back(new compressible_bloom_filter(10, .5, 1));
 136   ls.back()->insert("foo");
 137   ls.back()->insert("bar");
 138   ls.push_back(new compressible_bloom_filter(50, .5, 1));
 139   ls.back()->insert("foo");
 140   ls.back()->insert("bar");
 141   ls.back()->insert("baz");
 142   ls.back()->insert("boof");
 143   ls.back()->compress(20);
 144   ls.back()->insert("boogggg");
 145 }