bpf-bitset.cxx

   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 #include "bpf-bitset.h"
  10
  11 namespace bpf {
  12
  13 void
  14 throw_out_of_range(const char *where)
  15 {
  16   throw std::out_of_range(where);
  17 }
  18
  19 namespace bitset {
  20
  21 bool
  22 set1_const_ref::empty () const
  23 {
  24   for (size_t i = 0; i < words; ++i)
  25     if (data[i])
  26       return false;
  27   return true;
  28 }
  29
  30 bool
  31 set1_const_ref::operator== (const set1_const_ref &o) const
  32 {
  33   if (words != o.words)
  34     return false;
  35   for (size_t i = 0; i < words; ++i)
  36     if (data[i] != o.data[i])
  37       return false;
  38   return true;
  39 }
  40
  41 bool
  42 set1_const_ref::is_subset_of(const set1_const_ref &o) const
  43 {
  44   size_t n = std::min(words, o.words);
  45
  46   for (size_t i = 0; i < n; ++i)
  47     if (data[i] & ~o.data[i])
  48       return false;
  49   for (; n < words; ++n)
  50     if (data[n])
  51       return false;
  52
  53   return true;
  54 }
  55
  56 size_t
  57 set1_const_ref::find_first() const
  58 {
  59   for (size_t i = 0; i < words; ++i)
  60     if (data[i])
  61       return i * bits_per_word + __builtin_ctzl (data[i]);
  62   return npos;
  63 }
  64
  65 size_t
  66 set1_const_ref::find_next(size_t last) const
  67 {
  68   size_t i = (last + 1) / bits_per_word;
  69   size_t o = (last + 1) % bits_per_word;
  70
  71   if (__builtin_expect (i >= words, 0))
  72     return npos;
  73
  74   word_t w = data[i] & ((word_t)-1 << o);
  75   for (; w == 0; w = data[i])
  76     if (++i >= words)
  77       return npos;
  78   return i * bits_per_word + __builtin_ctzl (w);
  79 }
  80
  81 size_t
  82 set1_const_ref::find_next_zero(size_t last) const
  83 {
  84   size_t i = (last + 1) / bits_per_word;
  85   size_t o = (last + 1) % bits_per_word;
  86
  87   if (__builtin_expect (i >= words, 0))
  88     return npos;
  89
  90   word_t w = ~data[i] & ((word_t)-1 << o);
  91   for (; w == 0; w = ~data[i])
  92     if (++i >= words)
  93       return npos;
  94   return i * bits_per_word + __builtin_ctzl (w);
  95 }
  96
  97 set1::set1(size_t bits)
  98   : set1_ref(new word_t[round_words(bits)], round_words(bits))
  99 {
 100   memset(data, 0, words * sizeof(word_t));
 101 }
 102
 103 set1::set1(const set1_const_ref &o)
 104   : set1_ref(new word_t[o.words], o.words)
 105 {
 106   memcpy(data, o.data, words * sizeof(word_t));
 107 }
 108
 109 set1::~set1()
 110 {
 111   delete[] data;
 112 }
 113
 114 set2::set2(size_t m1, size_t m2)
 115   : n1(m1), w2(round_words(m2)), data(new word_t[m1 * w2])
 116 {
 117   memset(data, 0, n1 * w2 * sizeof(word_t));
 118 }
 119
 120 set2::set2(const set2 &o)
 121   : n1(o.n1), w2(o.w2), data(new word_t[o.n1 * o.w2])
 122 {
 123   memcpy(data, o.data, n1 * w2 * sizeof(word_t));
 124 }
 125
 126 set2::~set2()
 127 {
 128   delete[] data;
 129 }
 130
 131
 132 std::ostream&
 133 operator<< (std::ostream &o, const set1_const_ref &s)
 134 {
 135   char sep = '{';
 136   for (size_t n = s.size(), i = 0; i < n; ++i)
 137     if (s.test(i))
 138       {
 139         o << sep << i;
 140         sep = ',';
 141       }
 142   if (sep == '{')
 143     o << sep;
 144   return o << '}';
 145 }
 146
 147 } // namespace bitset
 148 } // namespace bpf