Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
bitset-base.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Lagerkvist <lagerkvist@gecode.org>
5 *
6 * Contributing authors:
7 * Linnea Ingmar <linnea.ingmar@hotmail.com>
8 * Christian Schulte <schulte@gecode.org>
9 *
10 * Copyright:
11 * Linnea Ingmar, 2017
12 * Mikael Lagerkvist, 2007
13 * Christian Schulte, 2007
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.org
18 *
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 *
38 */
39
40#include <climits>
41
42#ifdef _MSC_VER
43
44#include <intrin.h>
45
46#if defined(_M_IX86)
47#pragma intrinsic(_BitScanForward)
48#pragma intrinsic(__popcnt)
49#define GECODE_SUPPORT_MSVC_32
50#endif
51
52#if defined(_M_X64) || defined(_M_IA64)
53#pragma intrinsic(_BitScanForward64)
54#pragma intrinsic(__popcnt64)
55#define GECODE_SUPPORT_MSVC_64
56#endif
57
58#endif
59
60namespace Gecode { namespace Support {
61
62 class RawBitSetBase;
63
65 class BitSetData {
66 friend class RawBitSetBase;
67 protected:
68#if defined(GECODE_SUPPORT_MSVC_32)
70 typedef unsigned long int Base;
71#else
73 typedef unsigned long long int Base;
74#endif
77 public:
79 static const unsigned int bpb =
80 static_cast<unsigned int>(CHAR_BIT * sizeof(Base));
82 void init(bool setbits=false);
84 static unsigned int data(unsigned int s);
86 bool operator ()(unsigned int i=0U) const;
88 bool get(unsigned int i) const;
90 void set(unsigned int i);
92 void clear(unsigned int i);
94 unsigned int next(unsigned int i=0U) const;
96 bool all(void) const;
98 bool all(unsigned int i) const;
100 bool none(void) const;
102 bool none(unsigned int i) const;
104 unsigned int ones(void) const;
106 unsigned int zeroes(void) const;
108 bool one(void) const;
110 void a(BitSetData a);
112 void a(BitSetData a, unsigned int i);
116 void o(BitSetData a);
118 void o(BitSetData a, unsigned int i);
122 bool operator ==(BitSetData a) const;
124 bool operator !=(BitSetData a) const;
126 BitSetData operator ~(void) const;
127 };
128
135
137 class RawBitSetBase {
138 protected:
140 static const unsigned int bpb = BitSetData::bpb;
143 private:
145 RawBitSetBase(const RawBitSetBase&);
147 RawBitSetBase& operator =(const RawBitSetBase&);
148 public:
150 RawBitSetBase(void);
152 template<class A>
153 RawBitSetBase(A& a, unsigned int sz, bool setbits=false);
155 template<class A>
156 RawBitSetBase(A& a, unsigned int sz, const RawBitSetBase& bs);
158 template<class A>
159 void allocate(A& a, unsigned int sz);
161 template<class A>
162 void init(A& a, unsigned int sz, bool setbits=false);
164 void clearall(unsigned int sz, bool setbits=false);
166 void copy(unsigned int sz, const RawBitSetBase& bs);
168 bool get(unsigned int i) const;
170 void set(unsigned int i);
172 void clear(unsigned int i);
174 unsigned int next(unsigned int i) const;
176 BitSetStatus status(unsigned int sz) const;
178 bool all(unsigned int sz) const;
180 bool none(unsigned int sz) const;
182 template<class A>
183 void resize(A& a, unsigned int sz, unsigned int n, bool setbits=false);
185 template<class A>
186 void dispose(A& a, unsigned int sz);
187 };
188
190 class BitSetBase : public RawBitSetBase {
191 protected:
193 unsigned int sz;
194 private:
196 BitSetBase(const BitSetBase&);
198 BitSetBase& operator =(const BitSetBase&);
199 public:
201 BitSetBase(void);
203 template<class A>
204 BitSetBase(A& a, unsigned int s, bool setbits=false);
206 template<class A>
207 BitSetBase(A& a, const BitSetBase& bs);
209 template<class A>
210 void init(A& a, unsigned int s, bool setbits=false);
212 void clearall(bool setbits=false);
214 void copy(const BitSetBase& bs);
216 unsigned int size(void) const;
218 bool get(unsigned int i) const;
220 void set(unsigned int i);
222 void clear(unsigned int i);
224 unsigned int next(unsigned int i) const;
226 BitSetStatus status(void) const;
228 bool all(void) const;
230 bool none(void) const;
232 template<class A>
233 void resize(A& a, unsigned int n, bool setbits=false);
235 template<class A>
236 void dispose(A& a);
237 };
238
239
240 /*
241 * Bitset data
242 *
243 */
244
245 forceinline void
246 BitSetData::init(bool setbits) {
247 bits = setbits ? ~static_cast<Base>(0) : static_cast<Base>(0);
248 }
249 forceinline unsigned int
250 BitSetData::data(unsigned int s) {
251 return s == 0 ? 0 : ((s-1) / bpb + 1);
252 }
253 forceinline bool
254 BitSetData::operator ()(unsigned int i) const {
255 return (bits >> i) != static_cast<Base>(0U);
256 }
257 forceinline bool
258 BitSetData::get(unsigned int i) const {
259 return (bits & (static_cast<Base>(1U) << i)) != static_cast<Base>(0U);
260 }
261 forceinline void
262 BitSetData::set(unsigned int i) {
263 bits |= (static_cast<Base>(1U) << i);
264 }
265 forceinline void
266 BitSetData::clear(unsigned int i) {
267 bits &= ~(static_cast<Base>(1U) << i);
268 }
269 forceinline unsigned int
270 BitSetData::next(unsigned int i) const {
271 assert(bits != static_cast<Base>(0));
272#if defined(GECODE_SUPPORT_MSVC_32)
273 assert(bpb == 32);
274 unsigned long int p;
275 _BitScanForward(&p,bits >> i);
276 return static_cast<unsigned int>(p)+i;
277#elif defined(GECODE_SUPPORT_MSVC_64)
278 assert(bpb == 64);
279 unsigned long int p;
280 _BitScanForward64(&p,bits >> i);
281 return static_cast<unsigned int>(p)+i;
282#elif defined(GECODE_HAS_BUILTIN_FFSLL)
283 if (bpb == 64) {
284 int p = __builtin_ffsll(bits >> i);
285 assert(p > 0);
286 return static_cast<unsigned int>(p-1)+i;
287 }
288#else
289 while (!get(i)) i++;
290 return i;
291#endif
292 }
293 forceinline bool
294 BitSetData::all(void) const {
295 return bits == ~static_cast<Base>(0U);
296 }
297 forceinline bool
298 BitSetData::all(unsigned int i) const {
299 const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
300 return (bits & mask) == mask;
301 }
302 forceinline bool
303 BitSetData::none(void) const {
304 return bits == static_cast<Base>(0U);
305 }
306 forceinline bool
307 BitSetData::none(unsigned int i) const {
308 const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
309 return (bits & mask) == static_cast<Base>(0U);
310 }
311
312 forceinline unsigned int
313 BitSetData::ones(void) const {
314#if defined(GECODE_SUPPORT_MSVC_32)
315 assert(bpb == 32);
316 return static_cast<unsigned int>(__popcnt(bits));
317#elif defined(GECODE_SUPPORT_MSVC_64)
318 assert(bpb == 64);
319 return static_cast<unsigned int>(__popcnt64(bits));
320#elif defined(GECODE_HAS_BUILTIN_POPCOUNTLL)
321 if (bpb == 64)
322 return static_cast<unsigned int>(__builtin_popcountll(bits));
323#else
324 const unsigned long long int m1 = 0x5555555555555555;
325 const unsigned long long int m2 = 0x3333333333333333;
326 const unsigned long long int m4 = 0x0f0f0f0f0f0f0f0f;
327 unsigned long long int b = bits;
328 b -= (b >> 1) & m1;
329 b = (b & m2) + ((b >> 2) & m2);
330 b = (b + (b >> 4)) & m4;
331 b += b >> 8; b += b >> 16; b += b >> 32;
332 return static_cast<unsigned int>(b & 0x7f);
333#endif
334 }
335 forceinline unsigned int
336 BitSetData::zeroes(void) const {
337 return bpb - ones();
338 }
339 forceinline bool
340 BitSetData::one(void) const {
341 return (bits & (bits - static_cast<Base>(1U))) ==
342 static_cast<Base>(0U);
343 }
344
345 forceinline void
347 bits &= a.bits;
348 }
349 forceinline void
350 BitSetData::a(BitSetData a, unsigned int i) {
351 const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
352 bits &= (a.bits & mask);
353 }
356 BitSetData ab;
357 ab.bits = a.bits & b.bits;
358 return ab;
359 }
360
361 forceinline void
363 bits |= a.bits;
364 }
365 forceinline void
366 BitSetData::o(BitSetData a, unsigned int i) {
367 const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
368 bits |= (a.bits & mask);
369 }
372 BitSetData ab;
373 ab.bits = a.bits | b.bits;
374 return ab;
375 }
376
379 BitSetData iv;
380 iv.bits = ~bits;
381 return iv;
382 }
383 forceinline bool
385 return bits == a.bits;
386 }
387 forceinline bool
389 return bits != a.bits;
390 }
391
392
393 /*
394 * Basic bit sets
395 *
396 */
397
398 forceinline bool
399 RawBitSetBase::get(unsigned int i) const {
400 return data[i / bpb].get(i % bpb);
401 }
402 forceinline void
403 RawBitSetBase::set(unsigned int i) {
404 data[i / bpb].set(i % bpb);
405 }
406 forceinline void
407 RawBitSetBase::clear(unsigned int i) {
408 data[i / bpb].clear(i % bpb);
409 }
410
411 template<class A>
412 void
413 RawBitSetBase::resize(A& a, unsigned int sz, unsigned int n, bool setbits) {
414 if (n>sz) {
415 data = a.template realloc<BitSetData>(data,BitSetData::data(sz+1),
416 BitSetData::data(n+1));
417 for (unsigned int i=BitSetData::data(sz)+1;
418 i<BitSetData::data(n+1); i++) {
419 data[i].init(setbits);
420 }
421 for (unsigned int i=(sz%bpb); i<bpb; i++)
422 if (setbits)
423 data[sz / bpb].set(i);
424 else
425 data[sz / bpb].clear(i);
426 }
427 set(n);
428 }
429
430 template<class A>
431 forceinline void
432 RawBitSetBase::dispose(A& a, unsigned int sz) {
433 a.template free<BitSetData>(data,BitSetData::data(sz+1));
434 }
435
438 : data(NULL) {}
439
440 template<class A>
442 RawBitSetBase::RawBitSetBase(A& a, unsigned int sz, bool setbits)
443 : data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
444 for (unsigned int i=0U; i<BitSetData::data(sz+1); i++)
445 data[i].init(setbits);
446 // Set a bit at position sz as sentinel (for efficient next)
447 set(sz);
448 }
449
450 template<class A>
452 RawBitSetBase::RawBitSetBase(A& a, unsigned int sz, const RawBitSetBase& bs)
453 : data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
454 for (unsigned int i=0U; i<BitSetData::data(sz+1); i++)
455 data[i] = bs.data[i];
456 // Set a bit at position sz as sentinel (for efficient next)
457 set(sz);
458 }
459
460 template<class A>
461 forceinline void
462 RawBitSetBase::allocate(A& a, unsigned int sz) {
463 assert(data == NULL);
464 data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
465 }
466
467 template<class A>
468 forceinline void
469 RawBitSetBase::init(A& a, unsigned int sz, bool setbits) {
470 assert(data == NULL);
471 data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
472 for (unsigned int i=0U; i<BitSetData::data(sz+1); i++)
473 data[i].init(setbits);
474 // Set a bit at position sz as sentinel (for efficient next)
475 set(sz);
476 }
477
478 forceinline void
479 RawBitSetBase::copy(unsigned int sz, const RawBitSetBase& bs) {
480 for (unsigned int i=0U; i<BitSetData::data(sz+1); i++)
481 data[i] = bs.data[i];
482 }
483
484 forceinline void
485 RawBitSetBase::clearall(unsigned int sz, bool setbits) {
486 for (unsigned int i=0U; i<BitSetData::data(sz+1); i++)
487 data[i].init(setbits);
488 }
489
490 forceinline unsigned int
491 RawBitSetBase::next(unsigned int i) const {
492 unsigned int pos = i / bpb;
493 unsigned int bit = i % bpb;
494 if (data[pos](bit))
495 return pos * bpb + data[pos].next(bit);
496 // The sentinel bit guarantees that this loop always terminates
497 do {
498 pos++;
499 } while (!data[pos]());
500 return pos * bpb + data[pos].next();
501 }
502
504 RawBitSetBase::status(unsigned int sz) const {
505 unsigned int pos = sz / bpb;
506 unsigned int bits = sz % bpb;
507 if (pos > 0) {
508 if (data[0].all()) {
509 for (unsigned int i=1; i<pos; i++)
510 if (!data[i].all())
511 return BSS_SOME;
512 return data[pos].all(bits) ? BSS_ALL : BSS_SOME;
513 } else if (data[0].none()) {
514 for (unsigned int i=1; i<pos; i++)
515 if (!data[i].none())
516 return BSS_SOME;
517 return data[pos].none(bits) ? BSS_NONE : BSS_SOME;
518 } else {
519 return BSS_SOME;
520 }
521 }
522 if (data[0].all(bits))
523 return BSS_ALL;
524 if (data[0].none(bits))
525 return BSS_NONE;
526 return BSS_SOME;
527 }
528
529 forceinline bool
530 RawBitSetBase::all(unsigned int sz) const {
531 return status(sz) == BSS_ALL;
532 }
533
534 forceinline bool
535 RawBitSetBase::none(unsigned int sz) const {
536 return status(sz) == BSS_NONE;
537 }
538
539
540 template<class A>
541 void
542 BitSetBase::resize(A& a, unsigned int n, bool setbits) {
543 RawBitSetBase::resize(a,sz,n,setbits); sz=n;
544 }
545
546 template<class A>
547 forceinline void
551
554 : sz(0U) {}
555
556 template<class A>
558 BitSetBase::BitSetBase(A& a, unsigned int s, bool setbits)
559 : RawBitSetBase(a,s,setbits), sz(s) {}
560
561 template<class A>
563 BitSetBase::BitSetBase(A& a, const BitSetBase& bs)
564 : RawBitSetBase(a,bs.sz,bs), sz(bs.sz) {}
565
566 template<class A>
567 forceinline void
568 BitSetBase::init(A& a, unsigned int s, bool setbits) {
569 assert(sz == 0);
570 RawBitSetBase::init(a,s,setbits); sz=s;
571 }
572
573 forceinline void
574 BitSetBase::copy(const BitSetBase& bs) {
575 assert(sz == bs.sz);
577 }
578
579 forceinline void
580 BitSetBase::clearall(bool setbits) {
582 }
583
584 forceinline unsigned int
585 BitSetBase::size(void) const {
586 return sz;
587 }
588
589 forceinline bool
590 BitSetBase::get(unsigned int i) const {
591 assert(i < sz);
592 return RawBitSetBase::get(i);
593 }
594 forceinline void
595 BitSetBase::set(unsigned int i) {
596 assert(i < sz);
598 }
599 forceinline void
600 BitSetBase::clear(unsigned int i) {
601 assert(i < sz);
603 }
604
605 forceinline unsigned int
606 BitSetBase::next(unsigned int i) const {
607 assert(i <= sz);
608 return RawBitSetBase::next(i);
609 }
610
612 BitSetBase::status(void) const {
614 }
615
616 forceinline bool
617 BitSetBase::all(void) const {
618 return RawBitSetBase::all(sz);
619 }
620
621 forceinline bool
622 BitSetBase::none(void) const {
623 return RawBitSetBase::none(sz);
624 }
625
626}}
627
628#ifdef GECODE_SUPPORT_MSVC_32
629#undef GECODE_SUPPORT_MSVC_32
630#endif
631#ifdef GECODE_SUPPORT_MSVC_64
632#undef GECODE_SUPPORT_MSVC_64
633#endif
634
635// STATISTICS: support-any
BitSetBase(void)
Default constructor (yields empty set)
void dispose(A &a)
Dispose memory for bit set.
BitSetStatus status(void) const
Return status of bitset.
bool all(void) const
Test whether all bits are set.
void init(A &a, unsigned int s, bool setbits=false)
Initialize for s bits and allocator a (only after default constructor)
bool get(unsigned int i) const
Access value at bit i.
void clearall(bool setbits=false)
Clear sz bits.
void copy(const BitSetBase &bs)
Copy sz bits from bs.
unsigned int size(void) const
Return size of bitset (number of bits)
void clear(unsigned int i)
Clear bit i.
bool none(void) const
Test whether no bits are set.
void set(unsigned int i)
Set bit i.
unsigned int sz
Size of bitset (number of bits)
unsigned int next(unsigned int i) const
Return position greater or equal i of next set bit (i is allowed to be equal to size)
void resize(A &a, unsigned int n, bool setbits=false)
Resize bitset to n elememts.
Date item for bitsets.
bool all(void) const
Whether all bits are set.
bool operator==(BitSetData a) const
Check if bits are the same as for a.
bool operator()(unsigned int i=0U) const
Test wether any bit with position greater or equal to i is set.
void clear(unsigned int i)
Clear bit i.
unsigned int zeroes(void) const
Return the number of bits not set.
static const unsigned int bpb
Bits per base.
bool operator!=(BitSetData a) const
Check if bits are not the same as for a.
bool get(unsigned int i) const
Access value at bit i.
void init(bool setbits=false)
Initialize with all bits set if setbits.
unsigned long long int Base
Basetype for bits.
bool one(void) const
Check whether exactly one bit is set.
void a(BitSetData a)
Perform "and" with a.
bool none(void) const
Whether no bits are set.
unsigned int ones(void) const
Return the number of bits set.
unsigned int next(unsigned int i=0U) const
Return next set bit with position greater or equal to i (there must be a bit)
BitSetData operator~(void) const
Invert all bits in b.
void o(BitSetData a)
Perform "or" with a.
static unsigned int data(unsigned int s)
Get number of data elements for s bits.
void set(unsigned int i)
Set bit i.
Basic bitset support (without stored size information)
RawBitSetBase(void)
Default constructor (yields empty set)
bool get(unsigned int i) const
Access value at bit i.
void resize(A &a, unsigned int sz, unsigned int n, bool setbits=false)
Resize bitset from sz to n elememts.
void init(A &a, unsigned int sz, bool setbits=false)
Initialize for sz bits and allocator a (only after default constructor)
static const unsigned int bpb
Bits per base.
void allocate(A &a, unsigned int sz)
Allocate for sz bits and allocator a (only after default constructor)
BitSetStatus status(unsigned int sz) const
Return status of bitset.
bool none(unsigned int sz) const
Test whether no bits are set.
void clear(unsigned int i)
Clear bit i.
BitSetData * data
Stored bits.
void set(unsigned int i)
Set bit i.
bool all(unsigned int sz) const
Test whether all bits are set.
void clearall(unsigned int sz, bool setbits=false)
Clear sz bits.
void copy(unsigned int sz, const RawBitSetBase &bs)
Copy sz bits from bs.
void dispose(A &a, unsigned int sz)
Dispose memory for bit set.
unsigned int next(unsigned int i) const
Return position greater or equal i of next set bit (i is allowed to be equal to size)
Support algorithms and datastructures
BitSetStatus
Status of a bitset.
@ BSS_NONE
No bits set.
@ BSS_ALL
All bits set.
@ BSS_SOME
Some but not all bits set.
Gecode toplevel namespace
#define forceinline
Definition config.hpp:194