xpcom/glue/nsTArray.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim:set ts=2 sw=2 sts=2 et cindent: */
   3 /* ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is C++ array template.
  17  *
  18  * The Initial Developer of the Original Code is Google Inc.
  19  * Portions created by the Initial Developer are Copyright (C) 2005
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *  Darin Fisher <darin@meer.net>
  24  *
  25  * Alternatively, the contents of this file may be used under the terms of
  26  * either the GNU General Public License Version 2 or later (the "GPL"), or
  27  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  28  * in which case the provisions of the GPL or the LGPL are applicable instead
  29  * of those above. If you wish to allow use of your version of this file only
  30  * under the terms of either the GPL or the LGPL, and not to allow others to
  31  * use your version of this file under the terms of the MPL, indicate your
  32  * decision by deleting the provisions above and replace them with the notice
  33  * and other provisions required by the GPL or the LGPL. If you do not delete
  34  * the provisions above, a recipient may use your version of this file under
  35  * the terms of any one of the MPL, the GPL or the LGPL.
  36  *
  37  * ***** END LICENSE BLOCK ***** */
  38
  39 #include <string.h>
  40 #include "nsTArray.h"
  41 #include "nsXPCOM.h"
  42 #include "nsDebug.h"
  43
  44 nsTArray_base::Header nsTArray_base::sEmptyHdr = { 0, 0, 0 };
  45
  46 nsTArray_base::nsTArray_base()
  47   : mHdr(&sEmptyHdr) {
  48   MOZ_COUNT_CTOR(nsTArray_base);
  49 }
  50
  51 nsTArray_base::~nsTArray_base() {
  52   if (mHdr != &sEmptyHdr && !UsesAutoArrayBuffer()) {
  53     NS_Free(mHdr);
  54   }
  55   MOZ_COUNT_DTOR(nsTArray_base);
  56 }
  57
  58 PRBool
  59 nsTArray_base::EnsureCapacity(size_type capacity, size_type elemSize) {
  60   // This should be the most common case so test this first
  61   if (capacity <= mHdr->mCapacity)
  62     return PR_TRUE;
  63
  64   // If the requested memory allocation exceeds size_type(-1)/2, then our
  65   // doubling algorithm may not be able to allocate it.  Additionally we
  66   // couldn't fit in the Header::mCapacity member. Just bail out in cases
  67   // like that.  We don't want to be allocating 2 GB+ arrays anyway.
  68   if ((PRUint64)capacity * elemSize > size_type(-1)/2) {
  69     NS_ERROR("Attempting to allocate excessively large array");
  70     return PR_FALSE;
  71   }
  72
  73   if (mHdr == &sEmptyHdr) {
  74     // NS_Alloc new data
  75     Header *header = static_cast<Header*>
  76                                 (NS_Alloc(sizeof(Header) + capacity * elemSize));
  77     if (!header)
  78       return PR_FALSE;
  79     header->mLength = 0;
  80     header->mCapacity = capacity;
  81     header->mIsAutoArray = 0;
  82     mHdr = header;
  83
  84     return PR_TRUE;
  85   }
  86
  87   // Use doubling algorithm when forced to increase available capacity.
  88   capacity = PR_MAX(capacity, mHdr->mCapacity << 1);
  89
  90   Header *header;
  91   if (UsesAutoArrayBuffer()) {
  92     // NS_Alloc and copy
  93     header = static_cast<Header*>
  94                         (NS_Alloc(sizeof(Header) + capacity * elemSize));
  95     if (!header)
  96       return PR_FALSE;
  97
  98     memcpy(header, mHdr, sizeof(Header) + Length() * elemSize);
  99   } else {
 100     // NS_Realloc existing data
 101     size_type size = sizeof(Header) + capacity * elemSize;
 102     header = static_cast<Header*>(NS_Realloc(mHdr, size));
 103     if (!header)
 104       return PR_FALSE;
 105   }
 106
 107   header->mCapacity = capacity;
 108   mHdr = header;
 109
 110   return PR_TRUE;
 111 }
 112
 113 void
 114 nsTArray_base::ShrinkCapacity(size_type elemSize) {
 115   if (mHdr == &sEmptyHdr || UsesAutoArrayBuffer())
 116     return;
 117
 118   if (mHdr->mLength >= mHdr->mCapacity)  // should never be greater than...
 119     return;
 120
 121   size_type length = Length();
 122
 123   if (IsAutoArray() && GetAutoArrayBuffer()->mCapacity >= length) {
 124     Header* header = GetAutoArrayBuffer();
 125
 126     // Copy data, but don't copy the header to avoid overwriting mCapacity
 127     header->mLength = length;
 128     memcpy(header + 1, mHdr + 1, length * elemSize);
 129
 130     NS_Free(mHdr);
 131     mHdr = header;
 132     return;
 133   }
 134
 135   if (length == 0) {
 136     NS_ASSERTION(!IsAutoArray(), "autoarray should have fit 0 elements");
 137     NS_Free(mHdr);
 138     mHdr = &sEmptyHdr;
 139     return;
 140   }
 141
 142   size_type size = sizeof(Header) + length * elemSize;
 143   void *ptr = NS_Realloc(mHdr, size);
 144   if (!ptr)
 145     return;
 146   mHdr = static_cast<Header*>(ptr);
 147   mHdr->mCapacity = length;
 148 }
 149
 150 void
 151 nsTArray_base::ShiftData(index_type start, size_type oldLen, size_type newLen,
 152                          size_type elemSize) {
 153   if (oldLen == newLen)
 154     return;
 155
 156   // Determine how many elements need to be shifted
 157   size_type num = mHdr->mLength - (start + oldLen);
 158
 159   // Compute the resulting length of the array
 160   mHdr->mLength += newLen - oldLen;
 161   if (mHdr->mLength == 0) {
 162     ShrinkCapacity(elemSize);
 163   } else {
 164     // Maybe nothing needs to be shifted
 165     if (num == 0)
 166       return;
 167     // Perform shift (change units to bytes first)
 168     start *= elemSize;
 169     newLen *= elemSize;
 170     oldLen *= elemSize;
 171     num *= elemSize;
 172     char *base = reinterpret_cast<char*>(mHdr + 1) + start;
 173     memmove(base + newLen, base + oldLen, num);
 174   }
 175 }
 176
 177 PRBool
 178 nsTArray_base::InsertSlotsAt(index_type index, size_type count,
 179                              size_type elementSize) {
 180   NS_ASSERTION(index <= Length(), "Bogus insertion index");
 181   size_type newLen = Length() + count;
 182
 183   EnsureCapacity(newLen, elementSize);
 184
 185   // Check for out of memory conditions
 186   if (Capacity() < newLen)
 187     return PR_FALSE;
 188
 189   // Move the existing elements as needed.  Note that this will
 190   // change our mLength, so no need to call IncrementLength.
 191   ShiftData(index, 0, count, elementSize);
 192
 193   return PR_TRUE;
 194 }
 195
 196 PRBool
 197 nsTArray_base::SwapArrayElements(nsTArray_base& other, size_type elemSize)
 198 {
 199 #ifdef DEBUG
 200   PRBool isAuto = IsAutoArray();
 201   PRBool otherIsAuto = other.IsAutoArray();
 202 #endif
 203
 204   if (!EnsureNotUsingAutoArrayBuffer(elemSize) ||
 205       !other.EnsureNotUsingAutoArrayBuffer(elemSize)) {
 206     return PR_FALSE;
 207   }
 208
 209   NS_ASSERTION(isAuto == IsAutoArray(), "lost auto info");
 210   NS_ASSERTION(otherIsAuto == other.IsAutoArray(), "lost auto info");
 211   NS_ASSERTION(!UsesAutoArrayBuffer() && !other.UsesAutoArrayBuffer(),
 212                "both should be using an alloced buffer now");
 213
 214   // If the two arrays have different mIsAutoArray values (i.e. one is an
 215   // autoarray and one is not) then simply switching the buffers is going to
 216   // make that bit wrong. We therefore adjust these mIsAutoArray bits before
 217   // switching the buffers so that once the buffers are switched the
 218   // mIsAutoArray bits are right again.
 219   // However, we have to watch out so that we don't set the bit on
 220   // sEmptyHeader. If an array (A) uses the empty header (and the other (B)
 221   // therefore must be an nsAutoTArray) we make A point to the B's autobuffer
 222   // so that when the buffers are switched B points to its own autobuffer.
 223
 224   // Adjust mIsAutoArray flags before swapping the buffers
 225   if (IsAutoArray() && !other.IsAutoArray()) {
 226     if (other.mHdr == &sEmptyHdr) {
 227       // Set other to use our built-in buffer so that we use it
 228       // after the swap below.
 229       other.mHdr = GetAutoArrayBuffer();
 230       other.mHdr->mLength = 0;
 231     }
 232     else {
 233       other.mHdr->mIsAutoArray = 1;
 234     }
 235     mHdr->mIsAutoArray = 0;
 236   }
 237   else if (!IsAutoArray() && other.IsAutoArray()) {
 238     if (mHdr == &sEmptyHdr) {
 239       // Set us to use other's built-in buffer so that other use it
 240       // after the swap below.
 241       mHdr = other.GetAutoArrayBuffer();
 242       mHdr->mLength = 0;
 243     }
 244     else {
 245       mHdr->mIsAutoArray = 1;
 246     }
 247     other.mHdr->mIsAutoArray = 0;
 248   }
 249
 250   // Swap the buffers
 251   Header *h = other.mHdr;
 252   other.mHdr = mHdr;
 253   mHdr = h;
 254
 255   NS_ASSERTION(isAuto == IsAutoArray(), "lost auto info");
 256   NS_ASSERTION(otherIsAuto == other.IsAutoArray(), "lost auto info");
 257
 258   return PR_TRUE;
 259 }
 260
 261 PRBool
 262 nsTArray_base::EnsureNotUsingAutoArrayBuffer(size_type elemSize)
 263 {
 264   if (UsesAutoArrayBuffer()) {
 265     size_type size = sizeof(Header) + Length() * elemSize;
 266
 267     Header* header = static_cast<Header*>(NS_Alloc(size));
 268     if (!header)
 269       return PR_FALSE;
 270
 271     memcpy(header, mHdr, size);
 272     header->mCapacity = Length();
 273     mHdr = header;
 274   }
 275
 276   return PR_TRUE;
 277 }