1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/ds/BitArray.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,75 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#ifndef ds_BitArray_h
1.11 +#define ds_BitArray_h
1.12 +
1.13 +#include "mozilla/TemplateLib.h"
1.14 +
1.15 +#include <limits.h>
1.16 +
1.17 +#include "jstypes.h"
1.18 +
1.19 +namespace js {
1.20 +
1.21 +template <size_t nbits>
1.22 +class BitArray
1.23 +{
1.24 + private:
1.25 + static const size_t bitsPerElement = sizeof(uintptr_t) * CHAR_BIT;
1.26 + static const size_t numSlots = nbits / bitsPerElement + (nbits % bitsPerElement == 0 ? 0 : 1);
1.27 + static const size_t paddingBits = (numSlots * bitsPerElement) - nbits;
1.28 + static_assert(paddingBits < bitsPerElement, "More padding bits than expected.");
1.29 + static const uintptr_t paddingMask = uintptr_t(-1) >> paddingBits;
1.30 +
1.31 + uintptr_t map[numSlots];
1.32 +
1.33 + public:
1.34 + void clear(bool value) {
1.35 + memset(map, value ? 0xFF : 0, sizeof(map));
1.36 + if (value)
1.37 + map[numSlots - 1] &= paddingMask;
1.38 + }
1.39 +
1.40 + inline bool get(size_t offset) const {
1.41 + uintptr_t index, mask;
1.42 + getMarkWordAndMask(offset, &index, &mask);
1.43 + return map[index] & mask;
1.44 + }
1.45 +
1.46 + void set(size_t offset) {
1.47 + uintptr_t index, mask;
1.48 + getMarkWordAndMask(offset, &index, &mask);
1.49 + map[index] |= mask;
1.50 + }
1.51 +
1.52 + void unset(size_t offset) {
1.53 + uintptr_t index, mask;
1.54 + getMarkWordAndMask(offset, &index, &mask);
1.55 + map[index] &= ~mask;
1.56 + }
1.57 +
1.58 + bool isAllClear() const {
1.59 + for (size_t i = 0; i < numSlots; i++) {
1.60 + if (map[i])
1.61 + return false;
1.62 + }
1.63 + return true;
1.64 + }
1.65 +
1.66 + private:
1.67 + inline void getMarkWordAndMask(size_t offset,
1.68 + uintptr_t *indexp, uintptr_t *maskp) const {
1.69 + static_assert(bitsPerElement == 32 || bitsPerElement == 64,
1.70 + "unexpected bitsPerElement value");
1.71 + *indexp = offset / bitsPerElement;
1.72 + *maskp = uintptr_t(1) << (offset % bitsPerElement);
1.73 + }
1.74 +};
1.75 +
1.76 +} /* namespace js */
1.77 +
1.78 +#endif /* ds_BitArray_h */
