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