libbf  0.1
 All Classes Functions Typedefs Friends Pages
counter_vector.cc
1 #include <bf/counter_vector.h>
2 
3 #include <cassert>
4 
5 namespace bf {
6 
7 counter_vector::counter_vector(size_t cells, size_t width)
8  : bits_(cells * width), width_(width)
9 {
10  assert(cells > 0);
11  assert(width > 0);
12 }
13 
14 bool counter_vector::increment(size_t cell, size_t value)
15 {
16  assert(cell < size());
17  assert(value != 0);
18  size_t lsb = cell * width_;
19  if (value >= max())
20  {
21  bool r = false;
22  for (size_t i = 0; i < width_; ++i)
23  if (! bits_[lsb + i])
24  {
25  bits_[lsb + i] = true;
26  if (! r)
27  r = true;
28  }
29  return r;
30  }
31  bool carry = false;
32  for (size_t i = 0; i < width_; ++i)
33  {
34  bool b1 = bits_[lsb + i];
35  bool b2 = value & (1 << i);
36  bits_[lsb + i] ^= b2 != carry; // bit1 ^ bit2 ^ carry
37  carry = carry ? b1 || b2 : b1 && b2;
38  }
39  if (! carry)
40  return true;
41  for (size_t i = 0; i < width_; ++i)
42  bits_[lsb + i] = true;
43  return false;
44 }
45 
46 bool counter_vector::decrement(size_t cell, size_t value)
47 {
48  assert(value == 1); // TODO: adapt function to values > 1.
49  assert(cell < size());
50  size_t lsb = cell * width_;
51  for (auto i = lsb; i < lsb + width_; ++i)
52  if (bits_[i])
53  {
54  bits_[i] = false;
55  while (i && i > lsb)
56  bits_[--i] = true;
57  return true;
58  }
59  return false;
60 }
61 
62 size_t counter_vector::count(size_t cell) const
63 {
64  assert(cell < size());
65  size_t cnt = 0, order = 1;
66  size_t lsb = cell * width_;
67  for (auto i = lsb; i < lsb + width_; ++i, order <<= 1)
68  if (bits_[i])
69  cnt |= order;
70  return cnt;
71 }
72 
73 void counter_vector::set(size_t cell, size_t value)
74 {
75  assert(cell < size());
76  assert(value <= max());
77  bitvector bits(width_, value);
78  auto lsb = cell * width_;
79  for (size_t i = 0; i < width_; ++i)
80  bits_[lsb + i] = bits[i];
81 }
82 
84 {
85  bits_.reset();
86 }
87 
88 size_t counter_vector::size() const
89 {
90  return bits_.size() / width_;
91 }
92 
93 size_t counter_vector::max() const
94 {
95  using limits = std::numeric_limits<size_t>;
96  return limits::max() >> (limits::digits - width());
97 }
98 
99 size_t counter_vector::width() const
100 {
101  return width_;
102 }
103 
104 std::string to_string(counter_vector const& v, bool all, size_t cut_off)
105 {
106  return to_string(v.bits_, false, all, cut_off);
107 }
108 
109 } // namespace bf