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
	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 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"	)

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.