Line data    Source code

       1             : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
       2             :  * vim: set ts=8 sts=4 et sw=4 tw=99:
       3             :  * This Source Code Form is subject to the terms of the Mozilla Public
       4             :  * License, v. 2.0. If a copy of the MPL was not distributed with this
       5             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
       6             : 
       7             : #ifndef ds_Bitmap_h
       8             : #define ds_Bitmap_h
       9             : 
      10             : #include <algorithm>
      11             : 
      12             : #include "jsalloc.h"
      13             : 
      14             : #include "js/HashTable.h"
      15             : #include "js/Vector.h"
      16             : 
      17             : // This file provides two classes for representing bitmaps.
      18             : //
      19             : // DenseBitmap is an array of words of bits, with size linear in the maximum
      20             : // bit which has been set on it.
      21             : //
      22             : // SparseBitmap provides a reasonably simple, reasonably efficient (in time and
      23             : // space) implementation of a sparse bitmap. The basic representation is a hash
      24             : // table whose entries are fixed length malloc'ed blocks of bits.
      25             : 
      26             : namespace js {
      27             : 
      28           0 : class DenseBitmap
      29             : {
      30             :     typedef Vector<uintptr_t, 0, SystemAllocPolicy> Data;
      31             :     Data data;
      32             : 
      33             :   public:
      34             :     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) {
      35             :         return data.sizeOfExcludingThis(mallocSizeOf);
      36             :     }
      37             : 
      38           0 :     bool ensureSpace(size_t numWords) {
      39           0 :         MOZ_ASSERT(data.empty());
      40           0 :         return data.appendN(0, numWords);
      41             :     }
      42             : 
      43           0 :     size_t numWords() const { return data.length(); }
      44           0 :     uintptr_t word(size_t i) const { return data[i]; }
      45           0 :     uintptr_t& word(size_t i) { return data[i]; }
      46             : 
      47           0 :     void copyBitsFrom(size_t wordStart, size_t numWords, uintptr_t* source) {
      48           0 :         MOZ_ASSERT(wordStart + numWords <= data.length());
      49           0 :         mozilla::PodCopy(&data[wordStart], source, numWords);
      50           0 :     }
      51             : 
      52           0 :     void bitwiseOrRangeInto(size_t wordStart, size_t numWords, uintptr_t* target) const {
      53           0 :         for (size_t i = 0; i < numWords; i++)
      54           0 :             target[i] |= data[wordStart + i];
      55           0 :     }
      56             : };
      57             : 
      58          31 : class SparseBitmap
      59             : {
      60             :     // The number of words of bits to use for each block mainly affects the
      61             :     // memory usage of the bitmap. To minimize overhead, bitmaps which are
      62             :     // expected to be fairly dense should have a large block size, and bitmaps
      63             :     // which are expected to be very sparse should have a small block size.
      64             :     static const size_t WordsInBlock = 4096 / sizeof(uintptr_t);
      65             : 
      66             :     typedef mozilla::Array<uintptr_t, WordsInBlock> BitBlock;
      67             :     typedef HashMap<size_t, BitBlock*, DefaultHasher<size_t>, SystemAllocPolicy> Data;
      68             :     Data data;
      69             : 
      70      570755 :     static size_t blockStartWord(size_t word) {
      71      570755 :         return word & ~(WordsInBlock - 1);
      72             :     }
      73             : 
      74             :     // Return the number of words in a BitBlock starting at |blockWord| which
      75             :     // are in |other|.
      76           0 :     static size_t wordIntersectCount(size_t blockWord, const DenseBitmap& other) {
      77           0 :         long count = other.numWords() - blockWord;
      78           0 :         return std::min<size_t>((size_t)WordsInBlock, std::max<long>(count, 0));
      79             :     }
      80             : 
      81             :     BitBlock& createBlock(Data::AddPtr p, size_t blockId);
      82             : 
      83      368011 :     MOZ_ALWAYS_INLINE BitBlock* getBlock(size_t blockId) const {
      84      368011 :         Data::Ptr p = data.lookup(blockId);
      85      368012 :         return p ? p->value() : nullptr;
      86             :     }
      87             : 
      88      202346 :     MOZ_ALWAYS_INLINE BitBlock& getOrCreateBlock(size_t blockId) {
      89      202346 :         Data::AddPtr p = data.lookupForAdd(blockId);
      90      202347 :         if (p)
      91      202265 :             return *p->value();
      92          81 :         return createBlock(p, blockId);
      93             :     }
      94             : 
      95             :   public:
      96          31 :     bool init() { return data.init(); }
      97             :     ~SparseBitmap();
      98             : 
      99             :     size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf);
     100             : 
     101      202304 :     MOZ_ALWAYS_INLINE void setBit(size_t bit) {
     102      202304 :         size_t word = bit / JS_BITS_PER_WORD;
     103      202304 :         size_t blockWord = blockStartWord(word);
     104      202304 :         BitBlock& block = getOrCreateBlock(blockWord / WordsInBlock);
     105      202299 :         block[word - blockWord] |= uintptr_t(1) << (bit % JS_BITS_PER_WORD);
     106      202299 :     }
     107             : 
     108             :     bool getBit(size_t bit) const;
     109             : 
     110             :     void bitwiseAndWith(const DenseBitmap& other);
     111             :     void bitwiseOrWith(const SparseBitmap& other);
     112             :     void bitwiseOrInto(DenseBitmap& other) const;
     113             : 
     114             :     // Currently, this API only supports a range of words that is in a single bit block.
     115             :     void bitwiseOrRangeInto(size_t wordStart, size_t numWords, uintptr_t* target) const;
     116             : };
     117             : 
     118             : } // namespace js
     119             : 
     120             : #endif // ds_Bitmap_h