Back to index

lightning-sunbird  0.9+nobinonly
nsTArray.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 /* vim:set ts=2 sw=2 sts=2 et cindent: */
00003 /* ***** BEGIN LICENSE BLOCK *****
00004  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00005  *
00006  * The contents of this file are subject to the Mozilla Public License Version
00007  * 1.1 (the "License"); you may not use this file except in compliance with
00008  * the License. You may obtain a copy of the License at
00009  * http://www.mozilla.org/MPL/
00010  *
00011  * Software distributed under the License is distributed on an "AS IS" basis,
00012  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00013  * for the specific language governing rights and limitations under the
00014  * License.
00015  *
00016  * The Original Code is C++ array template.
00017  *
00018  * The Initial Developer of the Original Code is Google Inc.
00019  * Portions created by the Initial Developer are Copyright (C) 2005
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *  Darin Fisher <darin@meer.net>
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either the GNU General Public License Version 2 or later (the "GPL"), or
00027  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00028  * in which case the provisions of the GPL or the LGPL are applicable instead
00029  * of those above. If you wish to allow use of your version of this file only
00030  * under the terms of either the GPL or the LGPL, and not to allow others to
00031  * use your version of this file under the terms of the MPL, indicate your
00032  * decision by deleting the provisions above and replace them with the notice
00033  * and other provisions required by the GPL or the LGPL. If you do not delete
00034  * the provisions above, a recipient may use your version of this file under
00035  * the terms of any one of the MPL, the GPL or the LGPL.
00036  *
00037  * ***** END LICENSE BLOCK ***** */
00038 
00039 #include <string.h>
00040 #include "nsTArray.h"
00041 #include "nsXPCOM.h"
00042 #include "nsDebug.h"
00043 
00044 const nsTArray_base::Header nsTArray_base::sEmptyHdr = { 0, 0 };
00045 
00046 PRBool
00047 nsTArray_base::EnsureCapacity(size_type capacity, size_type elemSize) {
00048   // If the requested memory allocation exceeds size_type(-1)/2, then our
00049   // doubling algorithm may not be able to allocate it.  Just bail out in
00050   // cases like that.  We don't want to be allocating 2 GB+ arrays anyway.
00051   if ((PRUint64)capacity * elemSize > size_type(-1)/2) {
00052     NS_ERROR("Attempting to allocate excessively large array");
00053     return PR_FALSE;
00054   }
00055   if (mHdr == &sEmptyHdr) {
00056     // NS_Alloc new data
00057     Header *header = NS_STATIC_CAST(Header*,
00058                          NS_Alloc(sizeof(Header) + capacity * elemSize));
00059     if (!header)
00060       return PR_FALSE;
00061     header->mLength = 0;
00062     header->mCapacity = capacity;
00063     mHdr = header;
00064   } else {
00065     // NS_Realloc existing data
00066     if (capacity <= mHdr->mCapacity)
00067       return PR_TRUE;
00068 
00069     // Use doubling algorithm when forced to increase available capacity.
00070     if (mHdr->mCapacity > 0) {
00071       size_type temp = mHdr->mCapacity;
00072       while (temp < capacity)
00073         temp <<= 1;
00074       capacity = temp;
00075     }
00076 
00077     size_type size = sizeof(Header) + capacity * elemSize;
00078     void *ptr = NS_Realloc(mHdr, size);
00079     if (!ptr)
00080       return PR_FALSE;
00081     mHdr = NS_STATIC_CAST(Header*, ptr);
00082     mHdr->mCapacity = capacity;
00083   }
00084   return PR_TRUE;
00085 }
00086 
00087 void
00088 nsTArray_base::ShrinkCapacity(size_type elemSize) {
00089   if (mHdr == &sEmptyHdr)
00090     return;
00091 
00092   if (mHdr->mLength >= mHdr->mCapacity)  // should never be greater than...
00093     return;
00094 
00095   if (mHdr->mLength == 0) {
00096     NS_Free(mHdr);
00097     mHdr = NS_CONST_CAST(Header *, &sEmptyHdr);
00098     return;
00099   }
00100 
00101   size_type size = sizeof(Header) + mHdr->mLength * elemSize;
00102   void *ptr = NS_Realloc(mHdr, size);
00103   if (!ptr)
00104     return;
00105   mHdr = NS_STATIC_CAST(Header*, ptr);
00106   mHdr->mCapacity = mHdr->mLength;
00107 }
00108 
00109 void
00110 nsTArray_base::ShiftData(index_type start, size_type oldLen, size_type newLen,
00111                          size_type elemSize) {
00112   if (oldLen == newLen)
00113     return;
00114 
00115   // Determine how many elements need to be shifted
00116   size_type num = mHdr->mLength - (start + oldLen);
00117 
00118   // Compute the resulting length of the array
00119   mHdr->mLength += newLen - oldLen;
00120   if (mHdr->mLength == 0) {
00121     ShrinkCapacity(elemSize);
00122   } else {
00123     // Maybe nothing needs to be shifted
00124     if (num == 0)
00125       return;
00126     // Perform shift (change units to bytes first)
00127     start *= elemSize;
00128     newLen *= elemSize;
00129     oldLen *= elemSize;
00130     num *= elemSize;
00131     char *base = NS_REINTERPRET_CAST(char*, mHdr + 1) + start;
00132     memmove(base + newLen, base + oldLen, num);
00133   }
00134 }