Method insert_range

src/common/bitset_set.h:199–219

Efficiently insert a range of values. When N is small, this is * essentially an O(1) algorithm, although technically it is O(N) */

   * essentially an O(1) algorithm, although technically it is O(N)
   */
  void insert_range(const KeyT start, int length) {
    unsigned start_word = int(start) / bits_per_uint64_t;
    // This is not an off-by-one error. Conventionally this would have length
    // - 1, but the logic below is simpler with it as follows.
    unsigned end_word = (int(start) + length) / bits_per_uint64_t;
    ceph_assert(end_word < word_count + 1);

    if (start_word == end_word) {
      words[start_word] |=
        ((1ULL << length) - 1) << (int(start) % bits_per_uint64_t);
    } else {
      words[start_word] |= -1ULL << (int(start) % bits_per_uint64_t);
      while (++start_word < end_word) {
        words[start_word] = -1ULL;
      }
      if (end_word < word_count) {
        words[end_word] |=
          (1ULL << ((int(start) + length) % bits_per_uint64_t)) - 1;
      }
    }
  }

  /** Efficiently erase a range of values. When N is small, this is
   * essentially an O(1) algorithm, although technically it is O(N)