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 MEMPOOL_DEFINE_FACTORY(unsigned char, byte, bloom_filter);
   7
   8 void bloom_filter::encode(bufferlist& bl) const
   9 {
  10   ENCODE_START(2, 2, bl);
  11   ::encode((uint64_t)salt_count_, bl);
  12   ::encode((uint64_t)insert_count_, bl);
  13   ::encode((uint64_t)target_element_count_, bl);
  14   ::encode((uint64_t)random_seed_, bl);
  15   bufferptr bp((const char*)bit_table_, table_size_);
  16   ::encode(bp, bl);
  17   ENCODE_FINISH(bl);
  18 }
  19
  20 void bloom_filter::decode(bufferlist::iterator& p)
  21 {
  22   DECODE_START(2, p);
  23   uint64_t v;
  24   ::decode(v, p);
  25   salt_count_ = v;
  26   ::decode(v, p);
  27   insert_count_ = v;
  28   ::decode(v, p);
  29   target_element_count_ = v;
  30   ::decode(v, p);
  31   random_seed_ = v;
  32   bufferlist t;
  33   ::decode(t, p);
  34
  35   salt_.clear();
  36   generate_unique_salt();
  37   table_size_ = t.length();
  38   delete[] bit_table_;
  39   if (table_size_) {
  40     bit_table_ = new cell_type[table_size_];
  41     t.copy(0, table_size_, (char *)bit_table_);
  42   } else {
  43     bit_table_ = NULL;
  44   }
  45
  46   DECODE_FINISH(p);
  47 }
  48
  49 void bloom_filter::dump(Formatter *f) const
  50 {
  51   f->dump_unsigned("salt_count", salt_count_);
  52   f->dump_unsigned("table_size", table_size_);
  53   f->dump_unsigned("insert_count", insert_count_);
  54   f->dump_unsigned("target_element_count", target_element_count_);
  55   f->dump_unsigned("random_seed", random_seed_);
  56
  57   f->open_array_section("salt_table");
  58   for (std::vector<bloom_type>::const_iterator i = salt_.begin(); i != salt_.end(); ++i)
  59     f->dump_unsigned("salt", *i);
  60   f->close_section();
  61
  62   f->open_array_section("bit_table");
  63   for (unsigned i = 0; i < table_size_; ++i)
  64     f->dump_unsigned("byte", (unsigned)bit_table_[i]);
  65   f->close_section();
  66 }
  67
  68 void bloom_filter::generate_test_instances(std::list<bloom_filter*>& ls)
  69 {
  70   ls.push_back(new bloom_filter(10, .5, 1));
  71   ls.push_back(new bloom_filter(10, .5, 1));
  72   ls.back()->insert("foo");
  73   ls.back()->insert("bar");
  74   ls.push_back(new bloom_filter(50, .5, 1));
  75   ls.back()->insert("foo");
  76   ls.back()->insert("bar");
  77   ls.back()->insert("baz");
  78   ls.back()->insert("boof");
  79   ls.back()->insert("boogggg");
  80 }
  81
  82
  83 void compressible_bloom_filter::encode(bufferlist& bl) const
  84 {
  85   ENCODE_START(2, 2, bl);
  86   bloom_filter::encode(bl);
  87
  88   uint32_t s = size_list.size();
  89   ::encode(s, bl);
  90   for (std::vector<size_t>::const_iterator p = size_list.begin();
  91        p != size_list.end(); ++p)
  92     ::encode((uint64_t)*p, bl);
  93
  94   ENCODE_FINISH(bl);
  95 }
  96
  97 void compressible_bloom_filter::decode(bufferlist::iterator& p)
  98 {
  99   DECODE_START(2, p);
 100   bloom_filter::decode(p);
 101
 102   uint32_t s;
 103   ::decode(s, p);
 104   size_list.resize(s);
 105   for (unsigned i = 0; i < s; i++) {
 106     uint64_t v;
 107     ::decode(v, p);
 108     size_list[i] = v;
 109   }
 110
 111   DECODE_FINISH(p);
 112 }
 113
 114 void compressible_bloom_filter::dump(Formatter *f) const
 115 {
 116   bloom_filter::dump(f);
 117
 118   f->open_array_section("table_sizes");
 119   for (std::vector<size_t>::const_iterator p = size_list.begin();
 120        p != size_list.end(); ++p)
 121     f->dump_unsigned("size", (uint64_t)*p);
 122   f->close_section();
 123 }
 124
 125 void compressible_bloom_filter::generate_test_instances(std::list<compressible_bloom_filter*>& ls)
 126 {
 127   ls.push_back(new compressible_bloom_filter(10, .5, 1));
 128   ls.push_back(new compressible_bloom_filter(10, .5, 1));
 129   ls.back()->insert("foo");
 130   ls.back()->insert("bar");
 131   ls.push_back(new compressible_bloom_filter(50, .5, 1));
 132   ls.back()->insert("foo");
 133   ls.back()->insert("bar");
 134   ls.back()->insert("baz");
 135   ls.back()->insert("boof");
 136   ls.back()->compress(20);
 137   ls.back()->insert("boogggg");
 138 }