1/* 2 * Copyright (C) 2011 Apple Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26#ifndef PackedIntVector_h 27#define PackedIntVector_h 28 29#include <wtf/BitVector.h> 30 31namespace WTF { 32 33// This class allows you to create an array of integers, where those 34// integers have only a handful of bits each. It is not meant to be 35// efficient in time, but only in space. (Though making it efficient 36// in time for power-of-2 values of bitCount would not be difficult.) 37// Note that this does not work as expected for signed types, if you 38// are relying on the sign being preserved. 39 40template<typename T, unsigned bitCount> 41class PackedIntVector { 42public: 43 static_assert(bitCount, "bitCount must not be zero!"); 44 static_assert(bitCount < sizeof(void*) * 8, "bitCount must not exceed the address space limit!"); 45 46 PackedIntVector() 47 { 48 } 49 50 PackedIntVector(const PackedIntVector& other) 51 : m_bits(other.m_bits) 52 { 53 } 54 55 PackedIntVector& operator=(const PackedIntVector& other) 56 { 57 m_bits = other.m_bits; 58 return *this; 59 } 60 61 size_t size() const 62 { 63 return m_bits.size() / bitCount; 64 } 65 66 void ensureSize(size_t numInts) 67 { 68 m_bits.ensureSize(numInts * bitCount); 69 } 70 71 void resize(size_t numInts) 72 { 73 m_bits.resize(numInts * bitCount); 74 } 75 76 void clearAll() 77 { 78 m_bits.clearAll(); 79 } 80 81 T get(size_t index) const 82 { 83 uintptr_t result = 0; 84 for (unsigned subIndex = 0; subIndex < bitCount; ++subIndex) { 85 result <<= 1; 86 result |= (m_bits.quickGet(index * bitCount + subIndex) ? 1 : 0); 87 } 88 return static_cast<T>(result); 89 } 90 91 void set(size_t index, T value) 92 { 93 // Do arithmetic using uintptr_t, because (1) we know what it is 94 // (T might be an enum) and (2) it's the largest integer type that 95 // is likely to perform decently well. 96 uintptr_t myValue = static_cast<uintptr_t>(value); 97 98 // Preliminary sanity check that the value is not out of range. 99 ASSERT((myValue & mask()) == myValue); 100 101 for (unsigned subIndex = bitCount; subIndex-- > 0;) { 102 m_bits.quickSet(index * bitCount + subIndex, !!(myValue & 1)); 103 myValue >>= 1; 104 } 105 106 // Final sanity check that we stored what the user thought we 107 // stored. 108 ASSERT(get(index) == value); 109 } 110private: 111 // This returns the mask, and is careful to not step on the wrap-around 112 // semantics of the shift amount (1 << 32 is 1 since 32 wraps to 0). There 113 // is the separate question of why you would ever use this to store 32-bit 114 // or 64-bit values, but it's probably better to have this work as expected 115 // in such situations regardless. 116 static uintptr_t mask() { return (static_cast<uintptr_t>(2) << (bitCount - 1)) - 1; } 117 118 // Stores integers bit by bit in big endian. 119 BitVector m_bits; 120}; 121 122} // namespace WTF 123 124using WTF::PackedIntVector; 125 126#endif // PackedIntVector_h 127 128