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             : #include "ds/Bitmap.h"
       8             : 
       9             : using namespace js;
      10             : 
      11           0 : SparseBitmap::~SparseBitmap()
      12             : {
      13           0 :     if (data.initialized()) {
      14           0 :         for (Data::Range r(data.all()); !r.empty(); r.popFront())
      15           0 :             js_delete(r.front().value());
      16             :     }
      17           0 : }
      18             : 
      19             : size_t
      20           0 : SparseBitmap::sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf)
      21             : {
      22           0 :     size_t size = data.sizeOfExcludingThis(mallocSizeOf);
      23           0 :     for (Data::Range r(data.all()); !r.empty(); r.popFront())
      24           0 :         size += mallocSizeOf(r.front().value());
      25           0 :     return size;
      26             : }
      27             : 
      28             : SparseBitmap::BitBlock&
      29          81 : SparseBitmap::createBlock(Data::AddPtr p, size_t blockId)
      30             : {
      31          81 :     MOZ_ASSERT(!p);
      32         162 :     AutoEnterOOMUnsafeRegion oomUnsafe;
      33          81 :     BitBlock* block = js_new<BitBlock>();
      34          81 :     if (!block || !data.add(p, blockId, block))
      35           0 :         oomUnsafe.crash("Bitmap OOM");
      36          81 :     PodZero(block);
      37         162 :     return *block;
      38             : }
      39             : 
      40             : bool
      41      368011 : SparseBitmap::getBit(size_t bit) const
      42             : {
      43      368011 :     size_t word = bit / JS_BITS_PER_WORD;
      44      368011 :     size_t blockWord = blockStartWord(word);
      45             : 
      46      368011 :     BitBlock* block = getBlock(blockWord / WordsInBlock);
      47      368006 :     if (block)
      48      368006 :         return (*block)[word - blockWord] & (uintptr_t(1) << (bit % JS_BITS_PER_WORD));
      49           0 :     return false;
      50             : }
      51             : 
      52             : void
      53           0 : SparseBitmap::bitwiseAndWith(const DenseBitmap& other)
      54             : {
      55           0 :     for (Data::Enum e(data); !e.empty(); e.popFront()) {
      56           0 :         BitBlock& block = *e.front().value();
      57           0 :         size_t blockWord = e.front().key() * WordsInBlock;
      58           0 :         bool anySet = false;
      59           0 :         size_t numWords = wordIntersectCount(blockWord, other);
      60           0 :         for (size_t i = 0; i < numWords; i++) {
      61           0 :             block[i] &= other.word(blockWord + i);
      62           0 :             anySet |= !!block[i];
      63             :         }
      64           0 :         if (!anySet) {
      65           0 :             js_delete(&block);
      66           0 :             e.removeFront();
      67             :         }
      68             :     }
      69           0 : }
      70             : 
      71             : void
      72          15 : SparseBitmap::bitwiseOrWith(const SparseBitmap& other)
      73             : {
      74          57 :     for (Data::Range r(other.data.all()); !r.empty(); r.popFront()) {
      75          42 :         const BitBlock& otherBlock = *r.front().value();
      76          42 :         BitBlock& block = getOrCreateBlock(r.front().key());
      77       21546 :         for (size_t i = 0; i < WordsInBlock; i++)
      78       21504 :             block[i] |= otherBlock[i];
      79             :     }
      80          15 : }
      81             : 
      82             : void
      83           0 : SparseBitmap::bitwiseOrInto(DenseBitmap& other) const
      84             : {
      85           0 :     for (Data::Range r(data.all()); !r.empty(); r.popFront()) {
      86           0 :         BitBlock& block = *r.front().value();
      87           0 :         size_t blockWord = r.front().key() * WordsInBlock;
      88           0 :         size_t numWords = wordIntersectCount(blockWord, other);
      89             : #ifdef DEBUG
      90             :         // Any words out of range in other should be zero in this bitmap.
      91           0 :         for (size_t i = numWords; i < WordsInBlock; i++)
      92           0 :             MOZ_ASSERT(!block[i]);
      93             : #endif
      94           0 :         for (size_t i = 0; i < numWords; i++)
      95           0 :             other.word(blockWord + i) |= block[i];
      96             :     }
      97           0 : }
      98             : 
      99             : void
     100           0 : SparseBitmap::bitwiseOrRangeInto(size_t wordStart, size_t numWords, uintptr_t* target) const
     101             : {
     102           0 :     size_t blockWord = blockStartWord(wordStart);
     103             : 
     104             :     // We only support using a single bit block in this API.
     105           0 :     MOZ_ASSERT(numWords && (blockWord == blockStartWord(wordStart + numWords - 1)));
     106             : 
     107           0 :     BitBlock* block = getBlock(blockWord / WordsInBlock);
     108           0 :     if (block) {
     109           0 :         for (size_t i = 0; i < numWords; i++)
     110           0 :             target[i] |= (*block)[wordStart - blockWord + i];
     111             :     }
     112           0 : }