michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef ds_BitArray_h
michael@0: #define ds_BitArray_h
michael@0: 
michael@0: #include "mozilla/TemplateLib.h"
michael@0: 
michael@0: #include <limits.h>
michael@0: 
michael@0: #include "jstypes.h"
michael@0: 
michael@0: namespace js {
michael@0: 
michael@0: template <size_t nbits>
michael@0: class BitArray
michael@0: {
michael@0:   private:
michael@0:     static const size_t bitsPerElement = sizeof(uintptr_t) * CHAR_BIT;
michael@0:     static const size_t numSlots = nbits / bitsPerElement + (nbits % bitsPerElement == 0 ? 0 : 1);
michael@0:     static const size_t paddingBits = (numSlots * bitsPerElement) - nbits;
michael@0:     static_assert(paddingBits < bitsPerElement, "More padding bits than expected.");
michael@0:     static const uintptr_t paddingMask = uintptr_t(-1) >> paddingBits;
michael@0: 
michael@0:     uintptr_t map[numSlots];
michael@0: 
michael@0:   public:
michael@0:     void clear(bool value) {
michael@0:         memset(map, value ? 0xFF : 0, sizeof(map));
michael@0:         if (value)
michael@0:             map[numSlots - 1] &= paddingMask;
michael@0:     }
michael@0: 
michael@0:     inline bool get(size_t offset) const {
michael@0:         uintptr_t index, mask;
michael@0:         getMarkWordAndMask(offset, &index, &mask);
michael@0:         return map[index] & mask;
michael@0:     }
michael@0: 
michael@0:     void set(size_t offset) {
michael@0:         uintptr_t index, mask;
michael@0:         getMarkWordAndMask(offset, &index, &mask);
michael@0:         map[index] |= mask;
michael@0:     }
michael@0: 
michael@0:     void unset(size_t offset) {
michael@0:         uintptr_t index, mask;
michael@0:         getMarkWordAndMask(offset, &index, &mask);
michael@0:         map[index] &= ~mask;
michael@0:     }
michael@0: 
michael@0:     bool isAllClear() const {
michael@0:         for (size_t i = 0; i < numSlots; i++) {
michael@0:             if (map[i])
michael@0:                 return false;
michael@0:         }
michael@0:         return true;
michael@0:     }
michael@0: 
michael@0:   private:
michael@0:     inline void getMarkWordAndMask(size_t offset,
michael@0:                                    uintptr_t *indexp, uintptr_t *maskp) const {
michael@0:         static_assert(bitsPerElement == 32 || bitsPerElement == 64,
michael@0:                       "unexpected bitsPerElement value");
michael@0:         *indexp = offset / bitsPerElement;
michael@0:         *maskp = uintptr_t(1) << (offset % bitsPerElement);
michael@0:     }
michael@0: };
michael@0: 
michael@0: } /* namespace js */
michael@0: 
michael@0: #endif /* ds_BitArray_h */