2001-08-03 Daniel Berlin <dan@cgsoftware.com>
[official-gcc.git] / libstdc++-v3 / src / bitset.cc
blob0c3fc5f40734e732f1050af8f2c0ada708d968ee
1 // Bitset definitions -*- C++ -*-
3 // Copyright (C) 2001 Free Software Foundation
4 //
5 // This file is part of GNU CC.
6 //
7 // GNU CC is free software; you can redistribute it and/or modify
8 // it under the terms of the GNU General Public License as published by
9 // the Free Software Foundation; either version 2, or (at your option)
10 // any later version.
11 //
12 // GNU CC is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
16 //
17 // You should have received a copy of the GNU General Public License
18 // along with GNU CC; see the file COPYING. If not, write to
19 // the Free Software Foundation, 59 Temple Place - Suite 330,
20 // Boston, MA 02111-1307, USA.
22 // As a special exception, you may use this file as part of a free software
23 // library without restriction. Specifically, if other files instantiate
24 // templates or use macros or inline functions from this file, or you compile
25 // this file and link it with other files to produce an executable, this
26 // file does not by itself cause the resulting executable to be covered by
27 // the GNU General Public License. This exception does not however
28 // invalidate any other reasons why the executable file might be covered by
29 // the GNU General Public License.
32 * Copyright (c) 1998
33 * Silicon Graphics Computer Systems, Inc.
35 * Permission to use, copy, modify, distribute and sell this software
36 * and its documentation for any purpose is hereby granted without fee,
37 * provided that the above copyright notice appear in all copies and
38 * that both that copyright notice and this permission notice appear
39 * in supporting documentation. Silicon Graphics makes no
40 * representations about the suitability of this software for any
41 * purpose. It is provided "as is" without express or implied warranty.
42 */
44 #include <bits/std_bitset.h>
47 // Definitions of non-inline functions from the single-word version of
48 // _Base_bitset.
51 std::size_t
52 std::_Base_bitset<1>::_M_do_find_first(std::size_t __not_found) const
54 _WordT __thisword = _M_w;
56 if ( __thisword != static_cast<_WordT>(0) ) {
57 // find byte within word
58 for (std::size_t __j = 0; __j < sizeof(_WordT); __j++ ) {
59 unsigned char __this_byte
60 = static_cast<unsigned char>(__thisword & (~(unsigned char)0));
61 if ( __this_byte )
62 return __j*CHAR_BIT + _First_one<true>::_S_first_one[__this_byte];
64 __thisword >>= CHAR_BIT;
67 // not found, so return a value that indicates failure.
68 return __not_found;
71 std::size_t
72 std::_Base_bitset<1>::_M_do_find_next(std::size_t __prev,
73 std::size_t __not_found) const
75 // make bound inclusive
76 ++__prev;
78 // check out of bounds
79 if ( __prev >= _GLIBCPP_BITSET_BITS_PER_WORD )
80 return __not_found;
82 // search first (and only) word
83 _WordT __thisword = _M_w;
85 // mask off bits below bound
86 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
88 if ( __thisword != static_cast<_WordT>(0) ) {
89 // find byte within word
90 // get first byte into place
91 __thisword >>= _S_whichbyte(__prev) * CHAR_BIT;
92 for ( std::size_t __j = _S_whichbyte(__prev); __j < sizeof(_WordT); __j++ ) {
93 unsigned char __this_byte
94 = static_cast<unsigned char>(__thisword & (~(unsigned char)0));
95 if ( __this_byte )
96 return __j*CHAR_BIT + _First_one<true>::_S_first_one[__this_byte];
98 __thisword >>= CHAR_BIT;
102 // not found, so return a value that indicates failure.
103 return __not_found;
104 } // end _M_do_find_next
106 // ------------------------------------------------------------
107 // Lookup tables for find and count operations.
109 template<bool __dummy>
110 unsigned char std::_Bit_count<__dummy>::_S_bit_count[] = {
111 0, /* 0 */ 1, /* 1 */ 1, /* 2 */ 2, /* 3 */ 1, /* 4 */
112 2, /* 5 */ 2, /* 6 */ 3, /* 7 */ 1, /* 8 */ 2, /* 9 */
113 2, /* 10 */ 3, /* 11 */ 2, /* 12 */ 3, /* 13 */ 3, /* 14 */
114 4, /* 15 */ 1, /* 16 */ 2, /* 17 */ 2, /* 18 */ 3, /* 19 */
115 2, /* 20 */ 3, /* 21 */ 3, /* 22 */ 4, /* 23 */ 2, /* 24 */
116 3, /* 25 */ 3, /* 26 */ 4, /* 27 */ 3, /* 28 */ 4, /* 29 */
117 4, /* 30 */ 5, /* 31 */ 1, /* 32 */ 2, /* 33 */ 2, /* 34 */
118 3, /* 35 */ 2, /* 36 */ 3, /* 37 */ 3, /* 38 */ 4, /* 39 */
119 2, /* 40 */ 3, /* 41 */ 3, /* 42 */ 4, /* 43 */ 3, /* 44 */
120 4, /* 45 */ 4, /* 46 */ 5, /* 47 */ 2, /* 48 */ 3, /* 49 */
121 3, /* 50 */ 4, /* 51 */ 3, /* 52 */ 4, /* 53 */ 4, /* 54 */
122 5, /* 55 */ 3, /* 56 */ 4, /* 57 */ 4, /* 58 */ 5, /* 59 */
123 4, /* 60 */ 5, /* 61 */ 5, /* 62 */ 6, /* 63 */ 1, /* 64 */
124 2, /* 65 */ 2, /* 66 */ 3, /* 67 */ 2, /* 68 */ 3, /* 69 */
125 3, /* 70 */ 4, /* 71 */ 2, /* 72 */ 3, /* 73 */ 3, /* 74 */
126 4, /* 75 */ 3, /* 76 */ 4, /* 77 */ 4, /* 78 */ 5, /* 79 */
127 2, /* 80 */ 3, /* 81 */ 3, /* 82 */ 4, /* 83 */ 3, /* 84 */
128 4, /* 85 */ 4, /* 86 */ 5, /* 87 */ 3, /* 88 */ 4, /* 89 */
129 4, /* 90 */ 5, /* 91 */ 4, /* 92 */ 5, /* 93 */ 5, /* 94 */
130 6, /* 95 */ 2, /* 96 */ 3, /* 97 */ 3, /* 98 */ 4, /* 99 */
131 3, /* 100 */ 4, /* 101 */ 4, /* 102 */ 5, /* 103 */ 3, /* 104 */
132 4, /* 105 */ 4, /* 106 */ 5, /* 107 */ 4, /* 108 */ 5, /* 109 */
133 5, /* 110 */ 6, /* 111 */ 3, /* 112 */ 4, /* 113 */ 4, /* 114 */
134 5, /* 115 */ 4, /* 116 */ 5, /* 117 */ 5, /* 118 */ 6, /* 119 */
135 4, /* 120 */ 5, /* 121 */ 5, /* 122 */ 6, /* 123 */ 5, /* 124 */
136 6, /* 125 */ 6, /* 126 */ 7, /* 127 */ 1, /* 128 */ 2, /* 129 */
137 2, /* 130 */ 3, /* 131 */ 2, /* 132 */ 3, /* 133 */ 3, /* 134 */
138 4, /* 135 */ 2, /* 136 */ 3, /* 137 */ 3, /* 138 */ 4, /* 139 */
139 3, /* 140 */ 4, /* 141 */ 4, /* 142 */ 5, /* 143 */ 2, /* 144 */
140 3, /* 145 */ 3, /* 146 */ 4, /* 147 */ 3, /* 148 */ 4, /* 149 */
141 4, /* 150 */ 5, /* 151 */ 3, /* 152 */ 4, /* 153 */ 4, /* 154 */
142 5, /* 155 */ 4, /* 156 */ 5, /* 157 */ 5, /* 158 */ 6, /* 159 */
143 2, /* 160 */ 3, /* 161 */ 3, /* 162 */ 4, /* 163 */ 3, /* 164 */
144 4, /* 165 */ 4, /* 166 */ 5, /* 167 */ 3, /* 168 */ 4, /* 169 */
145 4, /* 170 */ 5, /* 171 */ 4, /* 172 */ 5, /* 173 */ 5, /* 174 */
146 6, /* 175 */ 3, /* 176 */ 4, /* 177 */ 4, /* 178 */ 5, /* 179 */
147 4, /* 180 */ 5, /* 181 */ 5, /* 182 */ 6, /* 183 */ 4, /* 184 */
148 5, /* 185 */ 5, /* 186 */ 6, /* 187 */ 5, /* 188 */ 6, /* 189 */
149 6, /* 190 */ 7, /* 191 */ 2, /* 192 */ 3, /* 193 */ 3, /* 194 */
150 4, /* 195 */ 3, /* 196 */ 4, /* 197 */ 4, /* 198 */ 5, /* 199 */
151 3, /* 200 */ 4, /* 201 */ 4, /* 202 */ 5, /* 203 */ 4, /* 204 */
152 5, /* 205 */ 5, /* 206 */ 6, /* 207 */ 3, /* 208 */ 4, /* 209 */
153 4, /* 210 */ 5, /* 211 */ 4, /* 212 */ 5, /* 213 */ 5, /* 214 */
154 6, /* 215 */ 4, /* 216 */ 5, /* 217 */ 5, /* 218 */ 6, /* 219 */
155 5, /* 220 */ 6, /* 221 */ 6, /* 222 */ 7, /* 223 */ 3, /* 224 */
156 4, /* 225 */ 4, /* 226 */ 5, /* 227 */ 4, /* 228 */ 5, /* 229 */
157 5, /* 230 */ 6, /* 231 */ 4, /* 232 */ 5, /* 233 */ 5, /* 234 */
158 6, /* 235 */ 5, /* 236 */ 6, /* 237 */ 6, /* 238 */ 7, /* 239 */
159 4, /* 240 */ 5, /* 241 */ 5, /* 242 */ 6, /* 243 */ 5, /* 244 */
160 6, /* 245 */ 6, /* 246 */ 7, /* 247 */ 5, /* 248 */ 6, /* 249 */
161 6, /* 250 */ 7, /* 251 */ 6, /* 252 */ 7, /* 253 */ 7, /* 254 */
162 8 /* 255 */
163 }; // end _Bit_count
165 template<bool __dummy>
166 unsigned char std::_First_one<__dummy>::_S_first_one[] = {
167 0, /* 0 */ 0, /* 1 */ 1, /* 2 */ 0, /* 3 */ 2, /* 4 */
168 0, /* 5 */ 1, /* 6 */ 0, /* 7 */ 3, /* 8 */ 0, /* 9 */
169 1, /* 10 */ 0, /* 11 */ 2, /* 12 */ 0, /* 13 */ 1, /* 14 */
170 0, /* 15 */ 4, /* 16 */ 0, /* 17 */ 1, /* 18 */ 0, /* 19 */
171 2, /* 20 */ 0, /* 21 */ 1, /* 22 */ 0, /* 23 */ 3, /* 24 */
172 0, /* 25 */ 1, /* 26 */ 0, /* 27 */ 2, /* 28 */ 0, /* 29 */
173 1, /* 30 */ 0, /* 31 */ 5, /* 32 */ 0, /* 33 */ 1, /* 34 */
174 0, /* 35 */ 2, /* 36 */ 0, /* 37 */ 1, /* 38 */ 0, /* 39 */
175 3, /* 40 */ 0, /* 41 */ 1, /* 42 */ 0, /* 43 */ 2, /* 44 */
176 0, /* 45 */ 1, /* 46 */ 0, /* 47 */ 4, /* 48 */ 0, /* 49 */
177 1, /* 50 */ 0, /* 51 */ 2, /* 52 */ 0, /* 53 */ 1, /* 54 */
178 0, /* 55 */ 3, /* 56 */ 0, /* 57 */ 1, /* 58 */ 0, /* 59 */
179 2, /* 60 */ 0, /* 61 */ 1, /* 62 */ 0, /* 63 */ 6, /* 64 */
180 0, /* 65 */ 1, /* 66 */ 0, /* 67 */ 2, /* 68 */ 0, /* 69 */
181 1, /* 70 */ 0, /* 71 */ 3, /* 72 */ 0, /* 73 */ 1, /* 74 */
182 0, /* 75 */ 2, /* 76 */ 0, /* 77 */ 1, /* 78 */ 0, /* 79 */
183 4, /* 80 */ 0, /* 81 */ 1, /* 82 */ 0, /* 83 */ 2, /* 84 */
184 0, /* 85 */ 1, /* 86 */ 0, /* 87 */ 3, /* 88 */ 0, /* 89 */
185 1, /* 90 */ 0, /* 91 */ 2, /* 92 */ 0, /* 93 */ 1, /* 94 */
186 0, /* 95 */ 5, /* 96 */ 0, /* 97 */ 1, /* 98 */ 0, /* 99 */
187 2, /* 100 */ 0, /* 101 */ 1, /* 102 */ 0, /* 103 */ 3, /* 104 */
188 0, /* 105 */ 1, /* 106 */ 0, /* 107 */ 2, /* 108 */ 0, /* 109 */
189 1, /* 110 */ 0, /* 111 */ 4, /* 112 */ 0, /* 113 */ 1, /* 114 */
190 0, /* 115 */ 2, /* 116 */ 0, /* 117 */ 1, /* 118 */ 0, /* 119 */
191 3, /* 120 */ 0, /* 121 */ 1, /* 122 */ 0, /* 123 */ 2, /* 124 */
192 0, /* 125 */ 1, /* 126 */ 0, /* 127 */ 7, /* 128 */ 0, /* 129 */
193 1, /* 130 */ 0, /* 131 */ 2, /* 132 */ 0, /* 133 */ 1, /* 134 */
194 0, /* 135 */ 3, /* 136 */ 0, /* 137 */ 1, /* 138 */ 0, /* 139 */
195 2, /* 140 */ 0, /* 141 */ 1, /* 142 */ 0, /* 143 */ 4, /* 144 */
196 0, /* 145 */ 1, /* 146 */ 0, /* 147 */ 2, /* 148 */ 0, /* 149 */
197 1, /* 150 */ 0, /* 151 */ 3, /* 152 */ 0, /* 153 */ 1, /* 154 */
198 0, /* 155 */ 2, /* 156 */ 0, /* 157 */ 1, /* 158 */ 0, /* 159 */
199 5, /* 160 */ 0, /* 161 */ 1, /* 162 */ 0, /* 163 */ 2, /* 164 */
200 0, /* 165 */ 1, /* 166 */ 0, /* 167 */ 3, /* 168 */ 0, /* 169 */
201 1, /* 170 */ 0, /* 171 */ 2, /* 172 */ 0, /* 173 */ 1, /* 174 */
202 0, /* 175 */ 4, /* 176 */ 0, /* 177 */ 1, /* 178 */ 0, /* 179 */
203 2, /* 180 */ 0, /* 181 */ 1, /* 182 */ 0, /* 183 */ 3, /* 184 */
204 0, /* 185 */ 1, /* 186 */ 0, /* 187 */ 2, /* 188 */ 0, /* 189 */
205 1, /* 190 */ 0, /* 191 */ 6, /* 192 */ 0, /* 193 */ 1, /* 194 */
206 0, /* 195 */ 2, /* 196 */ 0, /* 197 */ 1, /* 198 */ 0, /* 199 */
207 3, /* 200 */ 0, /* 201 */ 1, /* 202 */ 0, /* 203 */ 2, /* 204 */
208 0, /* 205 */ 1, /* 206 */ 0, /* 207 */ 4, /* 208 */ 0, /* 209 */
209 1, /* 210 */ 0, /* 211 */ 2, /* 212 */ 0, /* 213 */ 1, /* 214 */
210 0, /* 215 */ 3, /* 216 */ 0, /* 217 */ 1, /* 218 */ 0, /* 219 */
211 2, /* 220 */ 0, /* 221 */ 1, /* 222 */ 0, /* 223 */ 5, /* 224 */
212 0, /* 225 */ 1, /* 226 */ 0, /* 227 */ 2, /* 228 */ 0, /* 229 */
213 1, /* 230 */ 0, /* 231 */ 3, /* 232 */ 0, /* 233 */ 1, /* 234 */
214 0, /* 235 */ 2, /* 236 */ 0, /* 237 */ 1, /* 238 */ 0, /* 239 */
215 4, /* 240 */ 0, /* 241 */ 1, /* 242 */ 0, /* 243 */ 2, /* 244 */
216 0, /* 245 */ 1, /* 246 */ 0, /* 247 */ 3, /* 248 */ 0, /* 249 */
217 1, /* 250 */ 0, /* 251 */ 2, /* 252 */ 0, /* 253 */ 1, /* 254 */
218 0, /* 255 */
219 }; // end _First_one
221 // Explicitly instantiate them.
223 template unsigned char std::_Bit_count<false>::_S_bit_count[];
224 template unsigned char std::_Bit_count<true>::_S_bit_count[];
226 template unsigned char std::_First_one<false>::_S_first_one[];
227 template unsigned char std::_First_one<true>::_S_first_one[];