bpf-bitset.h

   1 // -*- C++ -*-
   2 // Copyright (C) 2016 Red Hat Inc.
   3 //
   4 // This file is part of systemtap, and is free software.  You can
   5 // redistribute it and/or modify it under the terms of the GNU General
   6 // Public License (GPL); either version 2, or (at your option) any
   7 // later version.
   8
   9 // This differs from std::bitset in being runtime sized, and from
  10 // boost::dynamic_bitset in being space efficient in multiple dimensions.
  11 //
  12 // ??? Could be templatized to n-dimensions.
  13
  14 #ifndef BPF_BITSET_H
  15 #define BPF_BITSET_H
  16
  17 #include <stdexcept>
  18 #include <iostream>
  19 #include <cstdlib>
  20 #include <cstring>
  21 #include <climits>
  22
  23 namespace bpf {
  24
  25 void throw_out_of_range(const char *) __attribute__((noreturn));
  26
  27 namespace bitset {
  28
  29 typedef size_t word_t;
  30 static size_t const bits_per_word = sizeof(word_t) * CHAR_BIT;
  31
  32 inline size_t round_words(size_t bits)
  33 {
  34   return (bits + bits_per_word - 1) / bits_per_word;
  35 }
  36
  37 class bit_ref
  38 {
  39 private:
  40   word_t * const word;
  41   size_t const index;
  42
  43   bit_ref();    // not present
  44
  45 public:
  46   bit_ref(word_t *w, size_t i) : word(w), index(i) { }
  47
  48   void reset()      { *word &= ~((word_t)1 << index); }
  49   void set()        { *word |= (word_t)1 << index; }
  50   void flip()       { *word ^= (word_t)1 << index; }
  51   void set(bool v)  { if (v) set(); else reset(); }
  52   bool test() const { return (*word >> index) & 1; }
  53
  54   operator bool() const { return test(); }
  55   bool operator!() const { return !test(); }
  56
  57   bool operator|= (bool o)
  58   {
  59     if (test())
  60       return true;
  61     else if (o)
  62       {
  63         set();
  64         return true;
  65       }
  66     return false;
  67   }
  68
  69   bool operator&= (bool o)
  70   {
  71     if (test())
  72       {
  73         if (o)
  74           return true;
  75         reset();
  76       }
  77     return false;
  78   }
  79
  80   bool operator-= (bool o)
  81   {
  82     if (test())
  83       {
  84         if (!o)
  85           return true;
  86         reset();
  87       }
  88     return false;
  89   }
  90
  91   bool operator^= (bool o)
  92   {
  93     if (o)
  94       flip();
  95     return test();
  96   }
  97 };
  98
  99 class set1;
 100 class set1_ref;
 101 class set1_const_ref
 102 {
 103   friend class set1;
 104   friend class set1_ref;
 105
 106 private:
 107   set1_const_ref();                                     // not present
 108   set1_const_ref& operator= (const set1_const_ref &);   // not present
 109
 110 protected:
 111   word_t *data;
 112   size_t words;
 113
 114 public:
 115   static const size_t npos = -1;
 116
 117   set1_const_ref(word_t *d, size_t w) : data(d), words(w) { }
 118   set1_const_ref(const set1_const_ref &o) : data(o.data), words(o.words) { }
 119
 120   bool operator!= (const set1_const_ref &o) const
 121   {
 122     return !(*this == o);
 123   }
 124
 125   size_t size() const { return words * bits_per_word; }
 126
 127   bool test(size_t i) const
 128   {
 129     size_t w = i / bits_per_word;
 130     size_t o = i % bits_per_word;
 131     if (w >= words)
 132       throw_out_of_range("bpf::bitset::set1_ref::test");
 133     return (data[w] >> o) & 1;
 134   }
 135
 136   bool operator[] (size_t i) const { return test(i); }
 137
 138   bool empty() const;
 139   bool operator== (const set1_const_ref &o) const;
 140   bool is_subset_of(const set1_const_ref &o) const;
 141   size_t find_first() const;
 142   size_t find_next(size_t i) const;
 143   size_t find_next_zero(size_t i) const;
 144 };
 145
 146 class set1_ref : public set1_const_ref
 147 {
 148 private:
 149   set1_ref();                                   // not present
 150
 151 public:
 152   set1_ref(size_t *d, size_t w) : set1_const_ref(d, w) { }
 153   set1_ref(const set1_ref &o) : set1_const_ref(o.data, o.words) { }
 154
 155   bit_ref operator[] (size_t i)
 156   {
 157     size_t w = i / bits_per_word;
 158     size_t o = i % bits_per_word;
 159     if (w >= words)
 160       throw_out_of_range("bpf::bitset::set1_ref::operator[]");
 161     return bit_ref(data + w, o);
 162   }
 163
 164   set1_ref& operator= (const set1_const_ref &o)
 165   {
 166     if (words != o.words)
 167       throw_out_of_range("bpf::bitset::set1_ref::operator=");
 168     memcpy(data, o.data, words * sizeof(*data));
 169     return *this;
 170   }
 171
 172   set1_ref& operator= (const set1_ref &o)
 173   {
 174     return operator=(static_cast<const set1_const_ref &>(o));
 175   }
 176
 177   set1_ref& operator|= (const set1_const_ref &o)
 178   {
 179     if (words != o.words)
 180       throw_out_of_range("bpf::bitset::set1_ref::operator|=");
 181     for (size_t i = 0; i < words; ++i)
 182       data[i] |= o.data[i];
 183     return *this;
 184   }
 185
 186   set1_ref& operator&= (const set1_const_ref &o)
 187   {
 188     if (words != o.words)
 189       throw_out_of_range("bpf::bitset::set1_ref::operator&=");
 190     for (size_t i = 0; i < words; ++i)
 191       data[i] &= o.data[i];
 192     return *this;
 193   }
 194
 195   set1_ref& operator-= (const set1_const_ref &o)
 196   {
 197     if (words != o.words)
 198       throw_out_of_range("bpf::bitset::set1_ref::operator-=");
 199     for (size_t i = 0; i < words; ++i)
 200       data[i] &= ~o.data[i];
 201     return *this;
 202   }
 203
 204   void clear() { memset(data, 0, words * sizeof(*data)); }
 205
 206   void reset(size_t i) { (*this)[i].reset(); }
 207   void set(size_t i) { (*this)[i].set(); }
 208   void set(size_t i, bool v) { (*this)[i].set(v); }
 209 };
 210
 211 class set1 : public set1_ref
 212 {
 213 private:
 214   set1();                                       // not present
 215
 216 public:
 217   set1(size_t bits);
 218   set1(const set1_const_ref &o);
 219   ~set1();
 220 };
 221
 222 class set2
 223 {
 224 private:
 225   size_t n1;
 226   size_t w2;
 227   word_t *data;
 228
 229   set2();                                       // not present
 230
 231 public:
 232   set2(size_t m1, size_t m2);
 233   set2(const set2 &o);
 234   ~set2();
 235
 236   size_t size() const { return n1; }
 237
 238   set2& operator= (const set2 &o)
 239   {
 240     if (n1 != o.n1 || w2 != o.w2)
 241       throw_out_of_range("bpf::bitset::set2::operator=");
 242     memcpy(data, o.data, n1 * w2 * sizeof(word_t));
 243   }
 244
 245   set1_ref operator[] (size_t i)
 246   {
 247     if (i >= n1)
 248       throw_out_of_range("set2::operator[]");
 249     return set1_ref(data + w2 * i, w2);
 250   }
 251
 252   set1_const_ref operator[] (size_t i) const
 253   {
 254     if (i >= n1)
 255       throw_out_of_range("set2::operator[]");
 256     return set1_const_ref(data + w2 * i, w2);
 257   }
 258
 259   void clear() { memset(data, 0, n1 * w2 * sizeof(*data)); }
 260 };
 261
 262 std::ostream& operator<< (std::ostream &o, const set1_const_ref &s);
 263
 264 } // namespace bitset
 265 } // namespace bpf
 266
 267 #endif // BPF_BITSET_H