1 /*
2    Copyright (c) 2010, 2011, Oracle and/or its affiliates. All rights reserved.
3 
4    This program is free software; you can redistribute it and/or modify
5    it under the terms of the GNU General Public License, version 2.0,
6    as published by the Free Software Foundation.
7 
8    This program is also distributed with certain software (including
9    but not limited to OpenSSL) that is licensed under separate terms,
10    as designated in a particular file or component or in included license
11    documentation.  The authors of MySQL hereby grant you an additional
12    permission to link the program and your derivative works with the
13    separately licensed software that they have included with MySQL.
14 
15    This program is distributed in the hope that it will be useful,
16    but WITHOUT ANY WARRANTY; without even the implied warranty of
17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
18    GNU General Public License, version 2.0, for more details.
19 
20    You should have received a copy of the GNU General Public License
21    along with this program; if not, write to the Free Software
22    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA
23 */
24 
25 #ifndef NDB_SPARSE_BITMASK_H
26 #define NDB_SPARSE_BITMASK_H
27 
28 #include <ndb_global.h>
29 #include <util/Vector.hpp>
30 #include <util/BaseString.hpp>
31 
32 class SparseBitmask {
33   unsigned m_max_size;
34   Vector<unsigned> m_vec;
35 
36 public:
37   STATIC_CONST( NotFound = (unsigned)-1 );
38 
SparseBitmask(unsigned max_size=NotFound-1)39   SparseBitmask(unsigned max_size = NotFound - 1) : m_max_size(max_size) {}
40 
max_size() const41   unsigned max_size() const { return m_max_size; }
42 
43   /* Set bit n */
set(unsigned n)44   void set(unsigned n) {
45     assert(n <= m_max_size);
46 
47     unsigned i = m_vec.size();
48     while (i > 0)
49     {
50       const unsigned j = m_vec[i-1];
51       if (n == j)
52         return; // Bit n already set
53 
54       if (j < n)
55         break;
56       i--;
57     }
58 
59     m_vec.push(n, i);
60   }
61 
62   /* Get bit n */
get(unsigned n) const63   bool get(unsigned n) const {
64     assert(n <= m_max_size);
65 
66     for (unsigned i = 0; i < m_vec.size(); i++)
67     {
68       const unsigned j = m_vec[i];
69       if (j < n)
70         continue;
71 
72       return (j == n);
73     }
74     return false;
75   }
76 
77   /* Clear bit n */
clear(unsigned n)78   int clear(unsigned n) {
79     assert(n <= m_max_size);
80     for (unsigned i = 0; i < m_vec.size(); i++)
81     {
82       const unsigned j = m_vec[i];
83       if (j != n)
84         continue;
85 
86       m_vec.erase(i);
87       return 1;
88     }
89     return 0;
90   }
91 
92   /* Clear all bits */
clear(void)93   void clear(void) {
94     m_vec.clear();
95   }
96 
97   /* Find first bit >= n */
find(unsigned n) const98   unsigned find(unsigned n) const {
99     for (unsigned i = 0; i < m_vec.size(); i++)
100     {
101       const unsigned j = m_vec[i];
102       if (j >= n)
103         return j;
104     }
105     return NotFound;
106   }
107 
108   /* Number of bits set */
count() const109   unsigned count() const { return m_vec.size(); }
110 
isclear() const111   bool isclear() const { return count() == 0; }
112 
getBitNo(unsigned n) const113   unsigned getBitNo(unsigned n) const {
114     assert(n < m_vec.size());
115     return m_vec[n];
116   }
117 
print(void) const118   void print(void) const {
119     for (unsigned i = 0; i < m_vec.size(); i++)
120     {
121       const unsigned j = m_vec[i];
122       printf("[%u]: %u\n", i, j);
123     }
124   }
125 
equal(const SparseBitmask & obj) const126   bool equal(const SparseBitmask& obj) const {
127     if (obj.count() != count())
128       return false;
129 
130     for (unsigned i = 0; i<count(); i++)
131       if (!obj.get(m_vec[i]))
132         return false;
133 
134     return true;
135   }
136 
overlaps(const SparseBitmask & obj) const137   bool overlaps(const SparseBitmask& obj) const {
138     for (unsigned i = 0; i<count(); i++)
139       if (!obj.get(m_vec[i]))
140         return true;
141 
142     for (unsigned i = 0; i<obj.count(); i++)
143       if (!get(obj.getBitNo(i)))
144         return true;
145     return false;
146   }
147 
str() const148   BaseString str() const {
149     BaseString tmp;
150     const char* sep="";
151     for (unsigned i = 0; i<m_vec.size(); i++)
152     {
153       tmp.appfmt("%s%u", sep, m_vec[i]);
154       sep=",";
155     }
156     return tmp;
157   }
158 };
159 
160 #endif
161