or-tools/src/util/bitset.cc File Reference

#include "util/bitset.h"
#include "base/commandlineflags.h"
#include "base/logging.h"

Go to the source code of this file.

Namespaces
namespace	operations_research
Defines
#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
	DEFINE_int32 (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.

---

Define Documentation

#define BIT_COUNT_RANGE	(	size,
		zero		)

Bit Operations.

Definition at line 26 of file bitset.cc.

#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;                                                        \
  }

#define LEAST_SIGNIFCANT_BIT_POSITION

(

size

)

#define MOST_SIGNIFICANT_BIT_POSITION

(

size

)

#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;                                                          \
  }

#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;                                                          \
  }

---

Function Documentation

DEFINE_int32	(	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.