this repo has no description
dekker.one
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
64 /// Date item for bitsets
65 class BitSetData {
66 friend class RawBitSetBase;
67 protected:
68#if defined(GECODE_SUPPORT_MSVC_32)
69 /// Basetype for bits
70 typedef unsigned long int Base;
71#else
72 /// Basetype for bits
73 typedef unsigned long long int Base;
74#endif
75 /// The bits
76 Base bits;
77 public:
78 /// Bits per base
79 static const unsigned int bpb =
80 static_cast<unsigned int>(CHAR_BIT * sizeof(Base));
81 /// Initialize with all bits set if \a setbits
82 void init(bool setbits=false);
83 /// Get number of data elements for \a s bits
84 static unsigned int data(unsigned int s);
85 /// Test wether any bit with position greater or equal to \a i is set
86 bool operator ()(unsigned int i=0U) const;
87 /// Access value at bit \a i
88 bool get(unsigned int i) const;
89 /// Set bit \a i
90 void set(unsigned int i);
91 /// Clear bit \a i
92 void clear(unsigned int i);
93 /// Return next set bit with position greater or equal to \a i (there must be a bit)
94 unsigned int next(unsigned int i=0U) const;
95 /// Whether all bits are set
96 bool all(void) const;
97 /// Whether all bits from bit 0 to bit \a i are set
98 bool all(unsigned int i) const;
99 /// Whether no bits are set
100 bool none(void) const;
101 /// Whether no bits from bit 0 to bit \a i are set
102 bool none(unsigned int i) const;
103 /// Return the number of bits set
104 unsigned int ones(void) const;
105 /// Return the number of bits not set
106 unsigned int zeroes(void) const;
107 /// Check whether exactly one bit is set
108 bool one(void) const;
109 /// Perform "and" with \a a
110 void a(BitSetData a);
111 /// Perform "and" with \a a for bits 0 to \a i
112 void a(BitSetData a, unsigned int i);
113 /// Return "and" of \a a and \a b
114 static BitSetData a(BitSetData a, BitSetData b);
115 /// Perform "or" with \a a
116 void o(BitSetData a);
117 /// Perform "or" with \a a for bits 0 to \a i
118 void o(BitSetData a, unsigned int i);
119 /// Return "or" of \a a and \a b
120 static BitSetData o(BitSetData a, BitSetData b);
121 /// Check if bits are the same as for \a a
122 bool operator ==(BitSetData a) const;
123 /// Check if bits are not the same as for \a a
124 bool operator !=(BitSetData a) const;
125 /// Invert all bits in \a b
126 BitSetData operator ~(void) const;
127 };
128
129 /// Status of a bitset
130 enum BitSetStatus {
131 BSS_NONE, ///< No bits set
132 BSS_ALL, ///< All bits set
133 BSS_SOME ///< Some but not all bits set
134 };
135
136 /// Basic bitset support (without stored size information)
137 class RawBitSetBase {
138 protected:
139 /// Bits per base
140 static const unsigned int bpb = BitSetData::bpb;
141 /// Stored bits
142 BitSetData* data;
143 private:
144 /// Copy constructor (disabled)
145 RawBitSetBase(const RawBitSetBase&);
146 /// Assignment operator (disabled)
147 RawBitSetBase& operator =(const RawBitSetBase&);
148 public:
149 /// Default constructor (yields empty set)
150 RawBitSetBase(void);
151 /// Initialize for \a sz bits and allocator \a a
152 template<class A>
153 RawBitSetBase(A& a, unsigned int sz, bool setbits=false);
154 /// Copy from bitset \a bs with allocator \a a
155 template<class A>
156 RawBitSetBase(A& a, unsigned int sz, const RawBitSetBase& bs);
157 /// Allocate for \a sz bits and allocator \a a (only after default constructor)
158 template<class A>
159 void allocate(A& a, unsigned int sz);
160 /// Initialize for \a sz bits and allocator \a a (only after default constructor)
161 template<class A>
162 void init(A& a, unsigned int sz, bool setbits=false);
163 /// Clear \a sz bits
164 void clearall(unsigned int sz, bool setbits=false);
165 /// Copy \a sz bits from \a bs
166 void copy(unsigned int sz, const RawBitSetBase& bs);
167 /// Access value at bit \a i
168 bool get(unsigned int i) const;
169 /// Set bit \a i
170 void set(unsigned int i);
171 /// Clear bit \a i
172 void clear(unsigned int i);
173 /// Return position greater or equal \a i of next set bit (\a i is allowed to be equal to size)
174 unsigned int next(unsigned int i) const;
175 /// Return status of bitset
176 BitSetStatus status(unsigned int sz) const;
177 /// Test whether all bits are set
178 bool all(unsigned int sz) const;
179 /// Test whether no bits are set
180 bool none(unsigned int sz) const;
181 /// Resize bitset from \a sz to \a n elememts
182 template<class A>
183 void resize(A& a, unsigned int sz, unsigned int n, bool setbits=false);
184 /// Dispose memory for bit set
185 template<class A>
186 void dispose(A& a, unsigned int sz);
187 };
188
189 /// Basic bitset support
190 class BitSetBase : public RawBitSetBase {
191 protected:
192 /// Size of bitset (number of bits)
193 unsigned int sz;
194 private:
195 /// Copy constructor (disabled)
196 BitSetBase(const BitSetBase&);
197 /// Assignment operator (disabled)
198 BitSetBase& operator =(const BitSetBase&);
199 public:
200 /// Default constructor (yields empty set)
201 BitSetBase(void);
202 /// Initialize for \a s bits and allocator \a a
203 template<class A>
204 BitSetBase(A& a, unsigned int s, bool setbits=false);
205 /// Copy from bitset \a bs with allocator \a a
206 template<class A>
207 BitSetBase(A& a, const BitSetBase& bs);
208 /// Initialize for \a s bits and allocator \a a (only after default constructor)
209 template<class A>
210 void init(A& a, unsigned int s, bool setbits=false);
211 /// Clear \a sz bits
212 void clearall(bool setbits=false);
213 /// Copy \a sz bits from \a bs
214 void copy(const BitSetBase& bs);
215 /// Return size of bitset (number of bits)
216 unsigned int size(void) const;
217 /// Access value at bit \a i
218 bool get(unsigned int i) const;
219 /// Set bit \a i
220 void set(unsigned int i);
221 /// Clear bit \a i
222 void clear(unsigned int i);
223 /// Return position greater or equal \a i of next set bit (\a i is allowed to be equal to size)
224 unsigned int next(unsigned int i) const;
225 /// Return status of bitset
226 BitSetStatus status(void) const;
227 /// Test whether all bits are set
228 bool all(void) const;
229 /// Test whether no bits are set
230 bool none(void) const;
231 /// Resize bitset to \a n elememts
232 template<class A>
233 void resize(A& a, unsigned int n, bool setbits=false);
234 /// Dispose memory for bit set
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
346 BitSetData::a(BitSetData a) {
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 }
354 forceinline BitSetData
355 BitSetData::a(BitSetData a, BitSetData b) {
356 BitSetData ab;
357 ab.bits = a.bits & b.bits;
358 return ab;
359 }
360
361 forceinline void
362 BitSetData::o(BitSetData a) {
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 }
370 forceinline BitSetData
371 BitSetData::o(BitSetData a, BitSetData b) {
372 BitSetData ab;
373 ab.bits = a.bits | b.bits;
374 return ab;
375 }
376
377 forceinline BitSetData
378 BitSetData::operator ~(void) const {
379 BitSetData iv;
380 iv.bits = ~bits;
381 return iv;
382 }
383 forceinline bool
384 BitSetData::operator ==(BitSetData a) const {
385 return bits == a.bits;
386 }
387 forceinline bool
388 BitSetData::operator !=(BitSetData a) const {
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
436 forceinline
437 RawBitSetBase::RawBitSetBase(void)
438 : data(nullptr) {}
439
440 template<class A>
441 forceinline
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>
451 forceinline
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 == nullptr);
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 == nullptr);
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
503 forceinline BitSetStatus
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
548 BitSetBase::dispose(A& a) {
549 RawBitSetBase::dispose(a,sz);
550 }
551
552 forceinline
553 BitSetBase::BitSetBase(void)
554 : sz(0U) {}
555
556 template<class A>
557 forceinline
558 BitSetBase::BitSetBase(A& a, unsigned int s, bool setbits)
559 : RawBitSetBase(a,s,setbits), sz(s) {}
560
561 template<class A>
562 forceinline
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);
576 RawBitSetBase::copy(sz,bs);
577 }
578
579 forceinline void
580 BitSetBase::clearall(bool setbits) {
581 RawBitSetBase::clearall(sz,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);
597 RawBitSetBase::set(i);
598 }
599 forceinline void
600 BitSetBase::clear(unsigned int i) {
601 assert(i < sz);
602 RawBitSetBase::clear(i);
603 }
604
605 forceinline unsigned int
606 BitSetBase::next(unsigned int i) const {
607 assert(i <= sz);
608 return RawBitSetBase::next(i);
609 }
610
611 forceinline BitSetStatus
612 BitSetBase::status(void) const {
613 return RawBitSetBase::status(sz);
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