source: trunk/gcc/libstdc++-v3/src/bitset.cc

Last change on this file was 1392, checked in by bird, 21 years ago

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