Scippy

SCIP

Solving Constraint Integer Programs

stpbitset.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file stpbitset.h
17  * @brief header only, simple implementation of a bitset
18  * @author Daniel Rehfeldt
19  *
20  * Implements a simple bitset. Should be set to NULL if undefined.
21  * NOTE: for efficiency reasons the bitset type is based on an STP_Vector and thus
22  * uses a non-SCIP-standard allocation method. In this way we avoid indirections, because
23  * we directly access the raw array.
24  * todo if too slow use extra fixed-size vector that uses standard memory allocs, or even
25  * cache-aligned mallocs
26  *
27  */
28 
29 
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31 
32 
33 #ifndef APPLICATIONS_STP_SRC_STPBITSET_H_
34 #define APPLICATIONS_STP_SRC_STPBITSET_H_
35 
36 #include "scip/scip.h"
37 #include "stpvector.h"
38 
39 #ifdef __cplusplus
40 extern "C" {
41 #endif
42 
43 
44 #define STP_Bitset STP_Vectype(uint64_t)
45 
46 
47 /** todo: do that more efficiently; currently just a text-book implementation.
48  * probably want to have case distinction for compilers and use intrinsics
49  * at least for gcc, clang, and intel */
50 static
52  uint64_t number /**< to get popcount for */
53  )
54 {
55  const uint64_t stpbit_m1 = 0x5555555555555555;
56  const uint64_t stpbit_m2 = 0x3333333333333333;
57  const uint64_t stpbit_m4 = 0x0f0f0f0f0f0f0f0f;
58  const uint64_t stpbit_powseries = 0x0101010101010101;
59  uint64_t n = number;
60 
61  n -= (n >> 1) & stpbit_m1;
62  n = (n & stpbit_m2) + ((n >> 2) & stpbit_m2);
63  n = (n + (n >> 4)) & stpbit_m4;
64 
65  return (int) ((n * stpbit_powseries) >> 56);
66 }
67 
68 
69 /*
70  * Interface methods
71  */
72 
73 /** initializes clean (all-0) bitset and returns it */
74 static
76  SCIP* scip, /**< SCIP data structure */
77  int maxnbits /**< size of bitset */
78  )
79 {
80  STP_Bitset bitset = NULL;
81  const int size = (maxnbits + 63) / 64;
82 
83  assert(maxnbits > 0);
84  assert(size > 0);
85 
86  StpVecReserve(scip, bitset, size);
87 
88  // todo do that more efficiently with new Stp_Vector reserve method
89  for( int i = 0; i < size; i++ )
90  {
91  StpVecPushBack(scip, bitset, (uint64_t) 0);
92  }
93 
94  return bitset;
95 }
96 
97 
98 /** frees */
99 static
100 inline void stpbitset_free(
101  SCIP* scip, /**< SCIP data structure */
102  STP_Bitset* bitset /**< bitset pointer */
103  )
104 {
105  assert(scip && bitset);
106  assert(*bitset);
107 
108  StpVecFree(scip, *bitset);
109 
110  assert(NULL == *bitset);
111 }
112 
113 
114 /** gets number of bits that can be stored */
115 static
117  STP_Bitset bitset /**< bitset */
118  )
119 {
120  assert(bitset);
121  assert(StpVecGetcapacity(bitset) == StpVecGetSize(bitset));
122 
123  return (StpVecGetcapacity(bitset) * 64);
124 }
125 
126 
127 /** sets bit to TRUE (1) */
128 static
130  STP_Bitset bitset, /**< bitset */
131  int index /**< bit index */
132  )
133 {
134  assert(bitset);
135  assert(0 <= index && index < stpbitset_getCapacity(bitset));
136 
137  bitset[index / 64] |= (uint64_t) 1 << (((uint64_t) index) & 63);
138 }
139 
140 
141 /** sets bit to FALSE (0) */
142 static
144  STP_Bitset bitset, /**< bitset */
145  int index /**< bit index */
146  )
147 {
148  assert(bitset);
149  assert(0 <= index && index < stpbitset_getCapacity(bitset));
150 
151  bitset[index / 64] &= ~((uint64_t) 1 << (((uint64_t) index) & 63));
152 }
153 
154 
155 /** are given bitsets compatible? */
156 static
158  STP_Bitset bitset1, /**< bitset */
159  STP_Bitset bitset2 /**< bitset */
160  )
161 {
162  assert(bitset1 && bitset2);
163 
164  if( stpbitset_getCapacity(bitset1) != stpbitset_getCapacity(bitset2) )
165  {
166  return FALSE;
167  }
168 
169  assert(StpVecGetSize(bitset1) == StpVecGetSize(bitset2));
170 
171  return TRUE;
172 }
173 
174 
175 /** do bitsets (of same size) intersect? */
176 static
178  STP_Bitset bitset1, /**< bitset */
179  STP_Bitset bitset2 /**< bitset */
180  )
181 {
182  const int vecsize = StpVecGetSize(bitset1);
183 
184  assert(bitset1 && bitset2);
185  assert(stpbitset_setsAreCompatible(bitset1, bitset2));
186  assert(vecsize > 0);
187 
188  for( int i = 0; i < vecsize; i++ )
189  {
190  if( (bitset1[i] & bitset2[i]) != 0 )
191  return TRUE;
192  }
193 
194  return FALSE;
195 }
196 
197 
198 /** are bitsets the same? */
199 static
201  STP_Bitset bitset1, /**< bitset */
202  STP_Bitset bitset2 /**< bitset */
203  )
204 {
205  const int vecsize = StpVecGetSize(bitset1);
206 
207  assert(bitset1 && bitset2);
208  assert(stpbitset_setsAreCompatible(bitset1, bitset2));
209  assert(vecsize > 0);
210 
211  if( memcmp(bitset1, bitset2, sizeof(bitset1[0]) * vecsize) != 0 )
212  {
213  return FALSE;
214 
215  }
216 
217  return TRUE;
218 }
219 
220 
221 /** is bit at given index set? */
222 static
224  STP_Bitset bitset, /**< bitset */
225  int index /**< bit index */
226  )
227 {
228  const uint64_t i = (uint64_t) index;
229 
230  assert(bitset);
231  assert(0 <= index && index < stpbitset_getCapacity(bitset));
232 
233  if( ((bitset[i / 64] >> ((i & 63)) & (uint64_t) 1)) == 0 )
234  {
235  return FALSE;
236  }
237  else
238  {
239  return TRUE;
240  }
241 }
242 
243 
244 
245 /** gets number of 1-bits */
246 static
248  STP_Bitset bitset /**< bitset */
249  )
250 {
251  int popcount = 0;
252  const int vecsize = StpVecGetSize(bitset);
253 
254  assert(vecsize > 0);
255 
256  for( int i = 0; i < vecsize; i++ )
257  {
258  popcount += bitsetinternalPopcount(bitset[i]);
259  }
260 
261  return popcount;
262 }
263 
264 
265 /** gets copy */
266 static
268  SCIP* scip, /**< SCIP data structure */
269  STP_Bitset bitsetOrg /**< bitset */
270  )
271 {
272  const int vecsize = StpVecGetSize(bitsetOrg);
273  STP_Bitset bitset = stpbitset_new(scip, stpbitset_getCapacity(bitsetOrg));
274 
275  assert(stpbitset_setsAreCompatible(bitsetOrg, bitset));
276  assert(vecsize > 0);
277 
278  BMScopyMemoryArray(bitset, bitsetOrg, vecsize);
279 
280  return bitset;
281 }
282 
283 
284 /** sets AND bitset */
285 static
286 inline void stpbitset_and(
287  SCIP* scip, /**< SCIP data structure */
288  STP_Bitset bitset1, /**< bitset */
289  STP_Bitset bitset2, /**< bitset */
290  STP_Bitset bitsetAnd /**< bitset to set */
291  )
292 {
293  const int vecsize = StpVecGetSize(bitsetAnd);
294 
295  assert(stpbitset_setsAreCompatible(bitset1, bitset2));
296  assert(stpbitset_setsAreCompatible(bitsetAnd, bitset2));
297  assert(vecsize > 0);
298 
299  for( int i = 0; i < vecsize; i++ )
300  {
301  bitsetAnd[i] = (bitset1[i] & bitset2[i]);
302  }
303 }
304 
305 
306 /** sets OR bitset */
307 static
308 inline void stpbitset_or(
309  SCIP* scip, /**< SCIP data structure */
310  STP_Bitset bitset1, /**< bitset */
311  STP_Bitset bitset2, /**< bitset */
312  STP_Bitset bitsetOr /**< bitset to set */
313  )
314 {
315  const int vecsize = StpVecGetSize(bitsetOr);
316 
317  assert(stpbitset_setsAreCompatible(bitset1, bitset2));
318  assert(stpbitset_setsAreCompatible(bitsetOr, bitset2));
319  assert(vecsize > 0);
320 
321  for( int i = 0; i < vecsize; i++ )
322  {
323  bitsetOr[i] = (bitset1[i] | bitset2[i]);
324  }
325 }
326 
327 
328 /** gets new AND bitset */
329 static
331  SCIP* scip, /**< SCIP data structure */
332  STP_Bitset bitset1, /**< bitset */
333  STP_Bitset bitset2 /**< bitset */
334  )
335 {
336  STP_Bitset bitset = stpbitset_new(scip, stpbitset_getCapacity(bitset1));
337 
338  assert(stpbitset_setsAreCompatible(bitset1, bitset2));
339 
340  stpbitset_and(scip, bitset1, bitset2, bitset);
341 
342  return bitset;
343 }
344 
345 
346 /** gets new OR bitset */
347 static
349  SCIP* scip, /**< SCIP data structure */
350  STP_Bitset bitset1, /**< bitset */
351  STP_Bitset bitset2 /**< bitset */
352  )
353 {
354  STP_Bitset bitset = stpbitset_new(scip, stpbitset_getCapacity(bitset1));
355 
356  assert(stpbitset_setsAreCompatible(bitset1, bitset2));
357 
358  stpbitset_or(scip, bitset1, bitset2, bitset);
359 
360  return bitset;
361 }
362 
363 
364 /** gets new XOR bitset */
365 static
367  SCIP* scip, /**< SCIP data structure */
368  STP_Bitset bitset1, /**< bitset */
369  STP_Bitset bitset2 /**< bitset */
370  )
371 {
372  const int vecsize = StpVecGetSize(bitset1);
373  STP_Bitset bitset = stpbitset_new(scip, stpbitset_getCapacity(bitset1));
374 
375  assert(stpbitset_setsAreCompatible(bitset1, bitset2));
376  assert(StpVecGetSize(bitset) == StpVecGetSize(bitset1));
377  assert(vecsize > 0);
378 
379  for( int i = 0; i < vecsize; i++ )
380  {
381  bitset[i] = (bitset1[i] ^ bitset2[i]);
382  }
383 
384  return bitset;
385 }
386 
387 
388 /** gets new Not bitset */
389 static
391  SCIP* scip, /**< SCIP data structure */
392  STP_Bitset bitset1, /**< bitset for not */
393  int size /**< size to apply not operation to */
394  )
395 {
396  const int vecsize_cut = size / 64;
397  STP_Bitset bitset = stpbitset_new(scip, stpbitset_getCapacity(bitset1));
398 
399  assert(StpVecGetSize(bitset) == StpVecGetSize(bitset1));
400  assert(0 <= size && size <= stpbitset_getCapacity(bitset));
401 
402  for( int i = 0; i < vecsize_cut; i++ )
403  {
404  bitset[i] = ~(bitset1[i]);
405  }
406 
407  if( (vecsize_cut * 64) != size )
408  {
409  const int nremaining = size - vecsize_cut * 64;
410  assert(nremaining > 0);
411 
412  bitset[vecsize_cut] = ~bitset1[vecsize_cut];
413 
414  for( int i = nremaining; i < 64; i++ )
415  {
416  bitset[vecsize_cut] &= ~((uint64_t) 1 << ((uint64_t) i));
417  }
418  }
419 
420  assert((size == stpbitset_getCapacity(bitset))
421  || !stpbitset_bitIsTrue(bitset, size));
422 
423  return bitset;
424 }
425 
426 
427 /** initializes all TRUE bitset and returns it
428  * todo more efficiently */
429 static
431  SCIP* scip, /**< SCIP data structure */
432  int maxnbits /**< size of bitset */
433  )
434 {
435  STP_Bitset bitset = stpbitset_new(scip, maxnbits);
436  const int cap = stpbitset_getCapacity(bitset);
437 
438  assert(cap > 0);
439 
440  for( int i = 0; i < cap; i++ )
441  {
442  assert(!stpbitset_bitIsTrue(bitset, i));
443  stpbitset_setBitTrue(bitset, i);
444  }
445 
446  return bitset;
447 }
448 
449 
450 /** prints bitset (0,1) ... for debugging */
451 static
452 inline void stpbitset_print(
453  STP_Bitset bitset /**< bitset to print*/
454  )
455 {
456  const int cap = stpbitset_getCapacity(bitset);
457 
458  assert(cap > 0);
459 
460  printf("bit-set (cap=%d): ", cap);
461 
462  for( int i = 0; i < cap; i++ )
463  {
464  printf("%d", stpbitset_bitIsTrue(bitset, i));
465  }
466 
467  printf("\n");
468 }
469 
470 
471 /** bitset1 > bitset2? */
472 static
474  STP_Bitset bitset1, /**< bitset */
475  STP_Bitset bitset2 /**< bitset */
476  )
477 {
478  const int vecsize = StpVecGetSize(bitset1);
479  int ret;
480 
481  assert(stpbitset_setsAreCompatible(bitset1, bitset2));
482  assert(vecsize > 0);
483 
484  ret = memcmp(bitset1, bitset2, sizeof(bitset1[0]) * vecsize);
485 
486  return (ret > 0);
487 }
488 
489 
490 /** bitset1 < bitset2? */
491 static
493  STP_Bitset bitset1, /**< bitset */
494  STP_Bitset bitset2 /**< bitset */
495  )
496 {
497  const int vecsize = StpVecGetSize(bitset1);
498  int ret;
499 
500  assert(stpbitset_setsAreCompatible(bitset1, bitset2));
501  assert(vecsize > 0);
502 
503  ret = memcmp(bitset1, bitset2, sizeof(bitset1[0]) * vecsize);
504 
505  return (ret < 0);
506 }
507 
508 
509 #ifdef __cplusplus
510 }
511 #endif
512 
513 
514 #endif /* APPLICATIONS_STP_SRC_STPBITSET_H_ */
#define StpVecGetSize(vec)
Definition: stpvector.h:139
static STP_Bitset stpbitset_newXor(SCIP *scip, STP_Bitset bitset1, STP_Bitset bitset2)
Definition: stpbitset.h:366
static SCIP_Bool stpbitset_haveIntersection(STP_Bitset bitset1, STP_Bitset bitset2)
Definition: stpbitset.h:177
#define FALSE
Definition: def.h:87
static int stpbitset_getCapacity(STP_Bitset bitset)
Definition: stpbitset.h:116
#define TRUE
Definition: def.h:86
static void stpbitset_print(STP_Bitset bitset)
Definition: stpbitset.h:452
#define StpVecReserve(scip, vec, _size_)
Definition: stpvector.h:182
static STP_Bitset stpbitset_newAnd(SCIP *scip, STP_Bitset bitset1, STP_Bitset bitset2)
Definition: stpbitset.h:330
static void stpbitset_and(SCIP *scip, STP_Bitset bitset1, STP_Bitset bitset2, STP_Bitset bitsetAnd)
Definition: stpbitset.h:286
header only, simple implementation of an STL like vector
static int bitsetinternalPopcount(uint64_t number)
Definition: stpbitset.h:51
#define StpVecGetcapacity(vec)
Definition: stpvector.h:129
static SCIP_Bool stpbitset_LT(STP_Bitset bitset1, STP_Bitset bitset2)
Definition: stpbitset.h:492
static SCIP_Bool stpbitset_setsAreCompatible(STP_Bitset bitset1, STP_Bitset bitset2)
Definition: stpbitset.h:157
static SCIP_Bool stpbitset_areEqual(STP_Bitset bitset1, STP_Bitset bitset2)
Definition: stpbitset.h:200
#define NULL
Definition: lpi_spx1.cpp:155
#define STP_Bitset
Definition: stpbitset.h:44
static STP_Bitset stpbitset_newNot(SCIP *scip, STP_Bitset bitset1, int size)
Definition: stpbitset.h:390
static void stpbitset_or(SCIP *scip, STP_Bitset bitset1, STP_Bitset bitset2, STP_Bitset bitsetOr)
Definition: stpbitset.h:308
#define SCIP_Bool
Definition: def.h:84
static STP_Bitset stpbitset_newCopy(SCIP *scip, STP_Bitset bitsetOrg)
Definition: stpbitset.h:267
static STP_Bitset stpbitset_new(SCIP *scip, int maxnbits)
Definition: stpbitset.h:75
static void stpbitset_free(SCIP *scip, STP_Bitset *bitset)
Definition: stpbitset.h:100
static SCIP_Bool stpbitset_bitIsTrue(STP_Bitset bitset, int index)
Definition: stpbitset.h:223
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
static void stpbitset_setBitFalse(STP_Bitset bitset, int index)
Definition: stpbitset.h:143
static long * number
static SCIP_Bool stpbitset_GT(STP_Bitset bitset1, STP_Bitset bitset2)
Definition: stpbitset.h:473
static STP_Bitset stpbitset_newOr(SCIP *scip, STP_Bitset bitset1, STP_Bitset bitset2)
Definition: stpbitset.h:348
#define StpVecFree(scip, vec)
Definition: stpvector.h:149
static int stpbitset_getPopcount(STP_Bitset bitset)
Definition: stpbitset.h:247
static STP_Bitset stpbitset_newAllTrue(SCIP *scip, int maxnbits)
Definition: stpbitset.h:430
#define StpVecPushBack(scip, vec, value)
Definition: stpvector.h:163
static void stpbitset_setBitTrue(STP_Bitset bitset, int index)
Definition: stpbitset.h:129
SCIP callable library.