OR-Tools  8.1
Namespaces | Macros | Functions
bitset.cc File Reference

Go to the source code of this file.

Namespaces

 operations_research
 The vehicle routing library lets one model and solve generic vehicle routing problems ranging from the Traveling Salesman Problem to more complex problems such as the Capacitated Vehicle Routing Problem with Time Windows.
 

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 
)
Value:
uint##size BitCountRange##size(const uint##size* const bits, \
uint##size start, uint##size end) { \
if (end - start > absl::GetFlag(FLAGS_bitset_small_bitset_count)) { \
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) { \
return BitCount##size(bits[offset_start] & \
OneRange##size(pos_start, pos_end)); \
} else { \
uint##size bit_count = zero; \
bit_count += \
BitCount##size(bits[offset_start] & IntervalUp##size(pos_start)); \
for (int offset = offset_start + 1; offset < offset_end; ++offset) { \
bit_count += BitCount##size(bits[offset]); \
} \
bit_count += \
BitCount##size(bits[offset_end] & IntervalDown##size(pos_end)); \
return bit_count; \
} \
} else { \
uint##size bit_count = zero; \
for (uint##size i = start; i <= end; ++i) { \
bit_count += IsBitSet##size(bits, i); \
} \
return bit_count; \
} \
}

Definition at line 26 of file bitset.cc.

◆ IS_EMPTY_RANGE

#define IS_EMPTY_RANGE (   size)
Value:
bool IsEmptyRange##size(const uint##size* const bits, uint##size start, \
uint##size 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 62 of file bitset.cc.

◆ LEAST_SIGNIFCANT_BIT_POSITION

#define LEAST_SIGNIFCANT_BIT_POSITION (   size)

Definition at line 94 of file bitset.cc.

◆ MOST_SIGNIFICANT_BIT_POSITION

#define MOST_SIGNIFICANT_BIT_POSITION (   size)

Definition at line 144 of file bitset.cc.

◆ UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION

#define UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION (   size)
Value:
int##size UnsafeLeastSignificantBitPosition##size( \
const uint##size* const bits, uint##size start, uint##size 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 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 195 of file bitset.cc.

◆ UNSAFE_MOST_SIGNIFICANT_BIT_POSITION

#define UNSAFE_MOST_SIGNIFICANT_BIT_POSITION (   size)
Value:
int##size UnsafeMostSignificantBitPosition##size( \
const uint##size* const bits, uint##size start, uint##size 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 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 226 of file bitset.cc.

Function Documentation

◆ ABSL_FLAG()

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