Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Namespaces | Macros | Functions
bitset.cc File Reference
#include "ortools/util/bitset.h"
#include "ortools/base/commandlineflags.h"
#include "ortools/base/logging.h"

Go to the source code of this file.

Namespaces

namespace  operations_research
 In SWIG mode, we don't want anything besides these top-level includes.
 

Macros

#define BIT_COUNT_RANGE(size, zero)
 -------— Bit Operations -------—
 
#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 )

-------— Bit Operations -------—

Definition at line 26 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; \
}
size
IntegerValue size
Definition 2d_rectangle_presolve.cc:235
end
std::optional< int64_t > end
Definition sparse_submatrix.cc:37
start
int64_t start
Definition sparse_submatrix.cc:36

Definition at line 64 of file bitset.cc.

◆ LEAST_SIGNIFCANT_BIT_POSITION

#define LEAST_SIGNIFCANT_BIT_POSITION ( size)

Definition at line 96 of file bitset.cc.

◆ MOST_SIGNIFICANT_BIT_POSITION

#define MOST_SIGNIFICANT_BIT_POSITION ( size)

Definition at line 147 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 199 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 231 of file bitset.cc.

Function Documentation

◆ ABSL_FLAG()

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

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.