Source/WTF/wtf/PackedIntVector.h

   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
  31 namespace 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
  40 template<typename T, unsigned bitCount>
  41 class PackedIntVector {
  42 public:
  43     PackedIntVector()
  44     {
  45         ASSERT(bitCount);
  46         ASSERT(bitCount < sizeof(void*) * 8);
  47     }
  48
  49     PackedIntVector(const PackedIntVector& other)
  50         : m_bits(other.m_bits)
  51     {
  52     }
  53
  54     PackedIntVector& operator=(const PackedIntVector& other)
  55     {
  56         m_bits = other.m_bits;
  57         return *this;
  58     }
  59
  60     size_t size() const
  61     {
  62         return m_bits.size() / bitCount;
  63     }
  64
  65     void ensureSize(size_t numInts)
  66     {
  67         m_bits.ensureSize(numInts * bitCount);
  68     }
  69
  70     void resize(size_t numInts)
  71     {
  72         m_bits.resize(numInts * bitCount);
  73     }
  74
  75     void clearAll()
  76     {
  77         m_bits.clearAll();
  78     }
  79
  80     T get(size_t index) const
  81     {
  82         uintptr_t result = 0;
  83         for (unsigned subIndex = 0; subIndex < bitCount; ++subIndex) {
  84             result <<= 1;
  85             result |= (m_bits.quickGet(index * bitCount + subIndex) ? 1 : 0);
  86         }
  87         return static_cast<T>(result);
  88     }
  89
  90     void set(size_t index, T value)
  91     {
  92         // Do arithmetic using uintptr_t, because (1) we know what it is
  93         // (T might be an enum) and (2) it's the largest integer type that
  94         // is likely to perform decently well.
  95         uintptr_t myValue = static_cast<uintptr_t>(value);
  96
  97         // Preliminary sanity check that the value is not out of range.
  98         ASSERT((myValue & mask()) == myValue);
  99
 100         for (unsigned subIndex = bitCount; subIndex-- > 0;) {
 101             m_bits.quickSet(index * bitCount + subIndex, !!(myValue & 1));
 102             myValue >>= 1;
 103         }
 104
 105         // Final sanity check that we stored what the user thought we
 106         // stored.
 107         ASSERT(get(index) == value);
 108     }
 109 private:
 110     // This returns the mask, and is careful to not step on the wrap-around
 111     // semantics of the shift amount (1 << 32 is 1 since 32 wraps to 0). There
 112     // is the separate question of why you would ever use this to store 32-bit
 113     // or 64-bit values, but it's probably better to have this work as expected
 114     // in such situations regardless.
 115     static uintptr_t mask() { return (static_cast<uintptr_t>(2) << (bitCount - 1)) - 1; }
 116
 117     // Stores integers bit by bit in big endian.
 118     BitVector m_bits;
 119 };
 120
 121 } // namespace WTF
 122
 123 using WTF::PackedIntVector;
 124
 125 #endif // PackedIntVector_h
 126