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
|
