Google OR-Tools v9.15
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
bitset.cc File Reference
#include "ortools/util/bitset.h"
#include <cstdint>
#include "absl/flags/flag.h"
#include "absl/log/check.h"

Go to the source code of this file.

Namespaces

namespace  operations_research
 OR-Tools root namespace.

Macros

#define BIT_COUNT_RANGE(size, zero)
#define IS_EMPTY_RANGE(size)
#define LEAST_SIGNIFCANT_BIT_POSITION(size)
#define MOST_SIGNIFICANT_BIT_POSITION(size)
#define UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(size)
#define UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(size)

Functions

 ABSL_FLAG (int, bitset_small_bitset_count, 8, "threshold to count bits with buckets")

Macro Definition Documentation

◆ BIT_COUNT_RANGE

#define BIT_COUNT_RANGE ( size,
zero )

Definition at line 28 of file bitset.cc.

◆ IS_EMPTY_RANGE

#define IS_EMPTY_RANGE ( size)
Value:
bool IsEmptyRange##size(const uint##size##_t* const bits, \
uint##size##_t start, uint##size##_t end) { \
const int offset_start = BitOffset##size(start); \
const int pos_start = BitPos##size(start); \
const int offset_end = BitOffset##size(end); \
const int pos_end = BitPos##size(end); \
if (offset_end == offset_start) { \
if (bits[offset_start] & OneRange##size(pos_start, pos_end)) { \
return false; \
} \
} else { \
if (bits[offset_start] & IntervalUp##size(pos_start)) { \
return false; \
} \
for (int offset = offset_start + 1; offset < offset_end; ++offset) { \
if (bits[offset]) { \
return false; \
} \
} \
if (bits[offset_end] & IntervalDown##size(pos_end)) { \
return false; \
} \
} \
return true; \
}

Definition at line 66 of file bitset.cc.

◆ LEAST_SIGNIFCANT_BIT_POSITION

#define LEAST_SIGNIFCANT_BIT_POSITION ( size)

Definition at line 98 of file bitset.cc.

◆ MOST_SIGNIFICANT_BIT_POSITION

#define MOST_SIGNIFICANT_BIT_POSITION ( size)

Definition at line 149 of file bitset.cc.

◆ UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION

#define UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION ( size)
Value:
int##size##_t UnsafeLeastSignificantBitPosition##size( \
const uint##size##_t* const bits, uint##size##_t start, \
uint##size##_t end) { \
DCHECK_LE(start, end); \
DCHECK(IsBitSet##size(bits, end)); \
if (IsBitSet##size(bits, start)) { \
return start; \
} \
const int offset_start = BitOffset##size(start); \
const int offset_end = BitOffset##size(end); \
const int pos_start = BitPos##size(start); \
const uint##size##_t start_mask = \
bits[offset_start] & IntervalUp##size(pos_start); \
if (start_mask) { \
return BitShift##size(offset_start) + \
LeastSignificantBitPosition##size(start_mask); \
} \
for (int offset = offset_start + 1; offset <= offset_end; ++offset) { \
if (bits[offset]) { \
return BitShift##size(offset) + \
LeastSignificantBitPosition##size(bits[offset]); \
} \
} \
return -1; \
}

Definition at line 201 of file bitset.cc.

◆ UNSAFE_MOST_SIGNIFICANT_BIT_POSITION

#define UNSAFE_MOST_SIGNIFICANT_BIT_POSITION ( size)
Value:
int##size##_t UnsafeMostSignificantBitPosition##size( \
const uint##size##_t* const bits, uint##size##_t start, \
uint##size##_t end) { \
DCHECK_GE(end, start); \
DCHECK(IsBitSet##size(bits, start)); \
if (IsBitSet##size(bits, end)) { \
return end; \
} \
const int offset_start = BitOffset##size(start); \
const int offset_end = BitOffset##size(end); \
const int pos_end = BitPos##size(end); \
const uint##size##_t end_mask = \
bits[offset_end] & IntervalDown##size(pos_end); \
if (end_mask) { \
return BitShift##size(offset_end) + \
MostSignificantBitPosition##size(end_mask); \
} \
for (int offset = offset_end - 1; offset >= offset_start; --offset) { \
if (bits[offset]) { \
return BitShift##size(offset) + \
MostSignificantBitPosition##size(bits[offset]); \
} \
} \
return -1; \
}

Definition at line 233 of file bitset.cc.

Function Documentation

◆ ABSL_FLAG()

ABSL_FLAG ( int ,
bitset_small_bitset_count ,
8 ,
"threshold to count bits with buckets"  )