DXR will be turned off on Tuesday, December 29th. It will redirect to Searchfox.
See the announcement on Discourse.

DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Implementation

Mercurial (c68fe15a81fc)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * vim: set ts=8 sts=2 et sw=2 tw=80:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef ds_Bitmap_h
#define ds_Bitmap_h


#include "mozilla/Array.h"
#include "mozilla/Assertions.h"
#include "mozilla/Attributes.h"
#include "mozilla/MemoryChecking.h"


#include <algorithm>
#include <stddef.h>
#include <stdint.h>

#include "js/AllocPolicy.h"
#include "js/AllocPolicy.h"
#include "js/HashTable.h"
#include "js/Vector.h"

// This file provides two classes for representing bitmaps.
//
//
// DenseBitmap is an array of words of bits, with size linear in the maximum
// bit which has been set on it.
//
// SparseBitmap provides a reasonably simple, reasonably efficient (in time and
// space) implementation of a sparse bitmap. The basic representation is a hash
// space) implementation of a sparse bitmap. The basic representation is a hash
// table whose entries are fixed length malloc'ed blocks of bits.

namespace js {

class DenseBitmap {
class DenseBitmap {
  using Data = Vector<uintptr_t, 0, SystemAllocPolicy>;

  Data data;
  Data data;

 public:
  size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) {
    return data.sizeOfExcludingThis(mallocSizeOf);
  }
  }

  bool ensureSpace(size_t numWords) {
    MOZ_ASSERT(data.empty());
    return data.appendN(0, numWords);
  }
  }

  size_t numWords() const { return data.length(); }
  uintptr_t word(size_t i) const { return data[i]; }
  uintptr_t& word(size_t i) { return data[i]; }


  void copyBitsFrom(size_t wordStart, size_t numWords, uintptr_t* source) {
    MOZ_ASSERT(wordStart + numWords <= data.length());
    // Use std::copy and not std::copy_n because the former requires no
    // overlap and so provides extra opportunity to optimize.
    std::copy(source, source + numWords, &data[wordStart]);
    std::copy(source, source + numWords, &data[wordStart]);
  }

  void bitwiseOrRangeInto(size_t wordStart, size_t numWords,
                          uintptr_t* target) const {
    for (size_t i = 0; i < numWords; i++) {
    for (size_t i = 0; i < numWords; i++) {
      target[i] |= data[wordStart + i];
    }
  }
};


class SparseBitmap {
  // The number of words of bits to use for each block mainly affects the
  // memory usage of the bitmap. To minimize overhead, bitmaps which are
  // expected to be fairly dense should have a large block size, and bitmaps
  // which are expected to be very sparse should have a small block size.
  // which are expected to be very sparse should have a small block size.
  static const size_t WordsInBlock = 4096 / sizeof(uintptr_t);

  using BitBlock = mozilla::Array<uintptr_t, WordsInBlock>;
  using Data =
      HashMap<size_t, BitBlock*, DefaultHasher<size_t>, SystemAllocPolicy>;
      HashMap<size_t, BitBlock*, DefaultHasher<size_t>, SystemAllocPolicy>;

  Data data;

  static size_t blockStartWord(size_t word) {
    return word & ~(WordsInBlock - 1);
    return word & ~(WordsInBlock - 1);
  }

  // Return the number of words in a BitBlock starting at |blockWord| which
  // are in |other|.
  static size_t wordIntersectCount(size_t blockWord, const DenseBitmap& other) {
  static size_t wordIntersectCount(size_t blockWord, const DenseBitmap& other) {
    long count = other.numWords() - blockWord;
    return std::min<size_t>((size_t)WordsInBlock, std::max<long>(count, 0));
  }

  BitBlock& createBlock(Data::AddPtr p, size_t blockId,
  BitBlock& createBlock(Data::AddPtr p, size_t blockId,
                        AutoEnterOOMUnsafeRegion& oomUnsafe);

  BitBlock* createBlock(Data::AddPtr p, size_t blockId);

  MOZ_ALWAYS_INLINE BitBlock* getBlock(size_t blockId) const {
  MOZ_ALWAYS_INLINE BitBlock* getBlock(size_t blockId) const {
    Data::Ptr p = data.lookup(blockId);
    return p ? p->value() : nullptr;
  }


  MOZ_ALWAYS_INLINE BitBlock& getOrCreateBlock(size_t blockId) {
    // The lookupForAdd() needs protection against injected OOMs, as does
    // the add() within createBlock().
    AutoEnterOOMUnsafeRegion oomUnsafe;
    Data::AddPtr p = data.lookupForAdd(blockId);
    Data::AddPtr p = data.lookupForAdd(blockId);
    if (p) {
      return *p->value();
    }
    return createBlock(p, blockId, oomUnsafe);
  }
  }

  MOZ_ALWAYS_INLINE BitBlock* getOrCreateBlockFallible(size_t blockId) {
    Data::AddPtr p = data.lookupForAdd(blockId);
    if (p) {
      return p->value();
    }
    return createBlock(p, blockId);
  }


 public:
  ~SparseBitmap();

  size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf);


  MOZ_ALWAYS_INLINE void setBit(size_t bit) {
    size_t word = bit / JS_BITS_PER_WORD;
    size_t blockWord = blockStartWord(word);
    BitBlock& block = getOrCreateBlock(blockWord / WordsInBlock);
    BitBlock& block = getOrCreateBlock(blockWord / WordsInBlock);
    block[word - blockWord] |= uintptr_t(1) << (bit % JS_BITS_PER_WORD);
  }

  MOZ_ALWAYS_INLINE bool setBitFallible(size_t bit) {
    size_t word = bit / JS_BITS_PER_WORD;
    size_t word = bit / JS_BITS_PER_WORD;
    size_t blockWord = blockStartWord(word);
    BitBlock* block = getOrCreateBlockFallible(blockWord / WordsInBlock);
    if (!block) {
      return false;
    }
    }
    (*block)[word - blockWord] |= uintptr_t(1) << (bit % JS_BITS_PER_WORD);
    return true;
  }

  bool getBit(size_t bit) const;
  bool getBit(size_t bit) const;

  void bitwiseAndWith(const DenseBitmap& other);
  void bitwiseOrWith(const SparseBitmap& other);
  void bitwiseOrInto(DenseBitmap& other) const;


  // Currently, this API only supports a range of words that is in a single bit
  // block.
  void bitwiseOrRangeInto(size_t wordStart, size_t numWords,
                          uintptr_t* target) const;
};
};

}  // namespace js

#endif  // ds_Bitmap_h