From 2aa4a82499d4becd2284cdb482213d541b8804dd Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 16:29:10 +0200 Subject: Adding upstream version 86.0.1. Signed-off-by: Daniel Baumann --- js/src/ds/Bitmap.h | 176 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 176 insertions(+) create mode 100644 js/src/ds/Bitmap.h (limited to 'js/src/ds/Bitmap.h') diff --git a/js/src/ds/Bitmap.h b/js/src/ds/Bitmap.h new file mode 100644 index 0000000000..74b04bfe3f --- /dev/null +++ b/js/src/ds/Bitmap.h @@ -0,0 +1,176 @@ +/* -*- 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 + * 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 +#include +#include + +#include "js/AllocPolicy.h" +#include "js/HashTable.h" +#include "js/HeapAPI.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 +// table whose entries are fixed length malloc'ed blocks of bits. + +namespace js { + +class DenseBitmap { + using Data = Vector; + + 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]; } + + template + typename std::enable_if_t, void> + copyBitsFrom(size_t wordStart, size_t numWords, T* source) { + MOZ_ASSERT(wordStart + numWords <= data.length()); + for (size_t i = 0; i < numWords; i++) { + data[wordStart + i] = source[i]; + } + } + + template + typename std::enable_if_t, void> + bitwiseOrRangeInto(size_t wordStart, size_t numWords, T* target) const { + 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. + static const size_t WordsInBlock = 4096 / sizeof(uintptr_t); + + using BitBlock = mozilla::Array; + using Data = + HashMap, SystemAllocPolicy>; + + Data data; + + static size_t blockStartWord(size_t word) { + 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) { + long count = other.numWords() - blockWord; + return std::min((size_t)WordsInBlock, std::max(count, 0)); + } + + 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 { + 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); + 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); + 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 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; + + 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. + template + typename std::enable_if_t, void> + bitwiseOrRangeInto(size_t wordStart, size_t numWords, T* target) const { + size_t blockWord = blockStartWord(wordStart); + + // We only support using a single bit block in this API. + MOZ_ASSERT(numWords && + (blockWord == blockStartWord(wordStart + numWords - 1))); + + BitBlock* block = getBlock(blockWord / WordsInBlock); + if (block) { + for (size_t i = 0; i < numWords; i++) { + target[i] |= (*block)[wordStart - blockWord + i]; + } + } + } +}; + +} // namespace js + +#endif // ds_Bitmap_h -- cgit v1.2.3