Source/WTF/wtf/RefCountedArray.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 RefCountedArray_h
  27 #define RefCountedArray_h
  28
  29 #include <wtf/FastMalloc.h>
  30 #include <wtf/StdLibExtras.h>
  31 #include <wtf/Vector.h>
  32
  33 // This implements a reference counted array for POD** values, which is optimized for:
  34 // - An empty array only uses one word.
  35 // - A copy of the array only uses one word (i.e. assignment means aliasing).
  36 // - The vector can't grow beyond 2^32-1 elements.
  37 // - In all other regards this has similar space usage to a Vector.
  38 //
  39 // ** This could be modified to support non-POD values quite easily. It just
  40 //    hasn't been, so far, because there has been no need. Moreover, even now,
  41 //    it's used for things that aren't quite POD according to the official
  42 //    defintion, such as JSC::Instruction.
  43
  44 namespace WTF {
  45
  46 template<typename T>
  47 class RefCountedArray {
  48 public:
  49     RefCountedArray()
  50         : m_data(0)
  51     {
  52     }
  53
  54     RefCountedArray(const RefCountedArray& other)
  55         : m_data(other.m_data)
  56     {
  57         if (m_data)
  58             Header::fromPayload(m_data)->refCount++;
  59     }
  60
  61     explicit RefCountedArray(const Vector<T>& other)
  62     {
  63         if (other.isEmpty()) {
  64             m_data = 0;
  65             return;
  66         }
  67
  68         m_data = (static_cast<Header*>(fastMalloc(Header::size() + sizeof(T) * other.size())))->payload();
  69         Header::fromPayload(m_data)->refCount = 1;
  70         Header::fromPayload(m_data)->length = other.size();
  71         ASSERT(Header::fromPayload(m_data)->length == other.size());
  72         memcpy(m_data, other.begin(), sizeof(T) * other.size());
  73     }
  74
  75     RefCountedArray& operator=(const RefCountedArray& other)
  76     {
  77         T* oldData = m_data;
  78         m_data = other.m_data;
  79         if (m_data)
  80             Header::fromPayload(m_data)->refCount++;
  81
  82         if (!oldData)
  83             return *this;
  84         if (--Header::fromPayload(oldData)->refCount)
  85             return *this;
  86         fastFree(Header::fromPayload(oldData));
  87         return *this;
  88     }
  89
  90     ~RefCountedArray()
  91     {
  92         if (!m_data)
  93             return;
  94         if (--Header::fromPayload(m_data)->refCount)
  95             return;
  96         fastFree(Header::fromPayload(m_data));
  97     }
  98
  99     size_t size() const
 100     {
 101         if (!m_data)
 102             return 0;
 103         return Header::fromPayload(m_data)->length;
 104     }
 105
 106     T* data() { return m_data; }
 107     T* begin() { return m_data; }
 108     T* end()
 109     {
 110         if (!m_data)
 111             return 0;
 112         return m_data + Header::fromPayload(m_data)->length;
 113     }
 114
 115     const T* data() const { return m_data; }
 116     const T* begin() const { return m_data; }
 117     const T* end() const { return const_cast<RefCountedArray*>(this)->end(); }
 118
 119     T& at(size_t i)
 120     {
 121         ASSERT(i < size());
 122         return begin()[i];
 123     }
 124
 125     const T& at(size_t i) const
 126     {
 127         ASSERT(i < size());
 128         return begin()[i];
 129     }
 130
 131     T& operator[](size_t i) { return at(i); }
 132     const T& operator[](size_t i) const { return at(i); }
 133
 134 private:
 135     struct Header {
 136         unsigned refCount;
 137         unsigned length;
 138
 139         static size_t size()
 140         {
 141             return (sizeof(Header) + 7) & ~7;
 142         }
 143
 144         T* payload()
 145         {
 146             char* result = reinterpret_cast<char*>(this) + size();
 147             ASSERT(!(bitwise_cast<uintptr_t>(result) & 7));
 148             return reinterpret_cast_ptr<T*>(result);
 149         }
 150
 151         static Header* fromPayload(T* payload)
 152         {
 153             return reinterpret_cast_ptr<Header*>(reinterpret_cast<char*>(payload) - size());
 154         }
 155     };
 156
 157     T* m_data;
 158 };
 159
 160 } // namespace WTF
 161
 162 using WTF::RefCountedArray;
 163
 164 #endif // RefCountedArray_h
 165