Back to index

lightning-sunbird  0.9+nobinonly
nsUInt32Array.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
00002  *
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 mozilla.org code.
00017  *
00018  * The Initial Developer of the Original Code is
00019  * Netscape Communications Corporation.
00020  * Portions created by the Initial Developer are Copyright (C) 1998
00021  * the Initial Developer. All Rights Reserved.
00022  *
00023  * Contributor(s):
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either of the GNU General Public License Version 2 or later (the "GPL"),
00027  * or 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  * This Original Code has been modified by IBM Corporation. Modifications made by IBM 
00039  * described herein are Copyright (c) International Business Machines Corporation, 2000.
00040  * Modifications to Mozilla code or documentation identified per MPL Section 3.3
00041  *
00042  * Date             Modified by     Description of modification
00043  * 04/20/2000       IBM Corp.      OS/2 VisualAge build.
00044  */
00045 
00046 #include "msgCore.h"    // precompiled header...
00047 #include "prlog.h"
00048 
00049 #include "MailNewsTypes.h"
00050 #include "nsUInt32Array.h"
00051 #include "nsQuickSort.h"
00052 
00053 MOZ_DECL_CTOR_COUNTER(nsUInt32Array)
00054 
00055 nsUInt32Array::nsUInt32Array()
00056 {
00057   MOZ_COUNT_CTOR(nsUInt32Array);
00058   m_nSize = 0;
00059   m_nMaxSize = 0;
00060   m_nGrowBy = 0;
00061   m_pData = NULL;
00062 }
00063 
00064 nsUInt32Array::~nsUInt32Array()
00065 {
00066   MOZ_COUNT_DTOR(nsUInt32Array);
00067   SetSize(0);
00068 }
00069 
00071 
00072 PRUint32 nsUInt32Array::GetSize() const
00073 {
00074   return m_nSize;
00075 }
00076 
00077 PRBool nsUInt32Array::SetSize(PRUint32 nSize,
00078                               PRBool adjustGrowth,
00079                               PRUint32 nGrowBy)
00080 {
00081   if (adjustGrowth)
00082     m_nGrowBy = nGrowBy;
00083   
00084 #ifdef MAX_ARR_ELEMS
00085   if (nSize > MAX_ARR_ELEMS);
00086   {
00087     PR_ASSERT(nSize <= MAX_ARR_ELEMS); // Will fail
00088     return PR_FALSE;
00089   }
00090 #endif
00091   
00092   if (nSize == 0)
00093   {
00094     // Remove all elements
00095     PR_Free(m_pData);
00096     m_nSize = 0;
00097     m_nMaxSize = 0;
00098     m_pData = NULL;
00099   }
00100   else if (m_pData == NULL)
00101   {
00102     // Create a new array
00103     m_nMaxSize = PR_MAX(8, nSize);
00104     m_pData = (PRUint32 *)PR_Calloc(1, m_nMaxSize * sizeof(PRUint32));
00105     if (m_pData)
00106       m_nSize = nSize;
00107     else
00108       m_nSize = m_nMaxSize = 0;
00109   }
00110   else if (nSize <= m_nMaxSize)
00111   {
00112     // The new size is within the current maximum size, make sure new
00113     // elements are to initialized to zero
00114     if (nSize > m_nSize)
00115       memset(&m_pData[m_nSize], 0, (nSize - m_nSize) * sizeof(PRUint32));
00116     
00117     m_nSize = nSize;
00118   }
00119   else
00120   {
00121     // The array needs to grow, figure out how much
00122     PRUint32 nMaxSize;
00123     nGrowBy  = PR_MAX(m_nGrowBy, PR_MIN(1024, PR_MAX(8, m_nSize / 8)));
00124     nMaxSize = PR_MAX(nSize, m_nMaxSize + nGrowBy);
00125 #ifdef MAX_ARR_ELEMS
00126     nMaxSize = PR_MIN(MAX_ARR_ELEMS, nMaxSize);
00127 #endif
00128     
00129     PRUint32 *pNewData = (PRUint32 *)PR_Malloc(nMaxSize * sizeof(PRUint32));
00130     if (pNewData)
00131     {
00132       // Copy the data from the old array to the new one
00133       memcpy(pNewData, m_pData, m_nSize * sizeof(PRUint32));
00134       
00135       // Zero out the remaining elements
00136       memset(&pNewData[m_nSize], 0, (nSize - m_nSize) * sizeof(PRUint32));
00137       m_nSize = nSize;
00138       m_nMaxSize = nMaxSize;
00139       
00140       // Free the old array
00141       PR_Free(m_pData);
00142       m_pData = pNewData;
00143     }
00144   }
00145   
00146   return nSize == m_nSize;
00147 }
00148 
00150 
00151 PRUint32 &nsUInt32Array::ElementAt(PRUint32 nIndex)
00152 {
00153   NS_ASSERTION(nIndex < m_nSize, "array index out of bounds");
00154   return m_pData[nIndex];
00155 }
00156 
00157 PRUint32 nsUInt32Array::GetAt(PRUint32 nIndex) const
00158 {
00159   NS_ASSERTION(nIndex < m_nSize, "array index out of bounds");
00160   return m_pData[nIndex];
00161 }
00162 
00163 PRUint32 *nsUInt32Array::GetData() 
00164 {
00165   return m_pData;
00166 }
00167 
00168 void nsUInt32Array::SetAt(PRUint32 nIndex, PRUint32 newElement)
00169 {
00170   NS_ASSERTION(nIndex < m_nSize, "array index out of bounds");
00171   m_pData[nIndex] = newElement;
00172 }
00173 
00175 
00176 PRUint32 nsUInt32Array::Add(PRUint32 newElement)
00177 {
00178   PRUint32 nIndex = m_nSize;
00179   
00180 #ifdef MAX_ARR_ELEMS
00181   if (nIndex >= MAX_ARR_ELEMS) 
00182     return -1;            
00183 #endif               
00184   
00185   SetAtGrow(nIndex, newElement);
00186   return nIndex;
00187 }
00188 
00189 PRUint32 nsUInt32Array::Add(PRUint32 *elementPtr, PRUint32 numElements) 
00190 { 
00191   if (SetSize(m_nSize + numElements))
00192     memcpy(m_pData + m_nSize - numElements, elementPtr, numElements * sizeof(PRUint32)); 
00193   
00194   return m_nSize; 
00195 } 
00196 
00197 PRUint32 *nsUInt32Array::CloneData() 
00198 { 
00199   PRUint32 *copyOfData = (PRUint32 *)PR_Malloc(m_nSize * sizeof(PRUint32)); 
00200   if (copyOfData) 
00201     memcpy(copyOfData, m_pData, m_nSize * sizeof(PRUint32)); 
00202   
00203   return copyOfData; 
00204 } 
00205 
00206 void nsUInt32Array::InsertAt(PRUint32 nIndex, PRUint32 newElement, PRUint32 nCount)
00207 {
00208   NS_ASSERTION(nCount > 0, "can't insert 0 elements");
00209   
00210   if (nIndex >= m_nSize)
00211   {
00212     // If the new element is after the end of the array, grow the array
00213     SetSize(nIndex + nCount);
00214   }
00215   else
00216   {
00217     // The element is being insert inside the array
00218     int nOldSize = m_nSize;
00219     SetSize(m_nSize + nCount);
00220     
00221     // Move the data after the insertion point
00222     memmove(&m_pData[nIndex + nCount], &m_pData[nIndex],
00223       (nOldSize - nIndex) * sizeof(PRUint32));
00224   }
00225   
00226   // Insert the new elements
00227   NS_ASSERTION(nIndex + nCount <= m_nSize, "setting size failed");
00228   while (nCount--)
00229     m_pData[nIndex++] = newElement;
00230 }
00231 
00232 void nsUInt32Array::InsertAt(PRUint32 nStartIndex, const nsUInt32Array *pNewArray)
00233 {
00234   NS_ASSERTION(pNewArray, "inserting null array");
00235   
00236   if (pNewArray)
00237   {
00238     if (pNewArray->GetSize() > 0)
00239     {
00240       InsertAt(nStartIndex, pNewArray->GetAt(0), pNewArray->GetSize());
00241       for (PRUint32 i = 1; i < pNewArray->GetSize(); i++)
00242         m_pData[nStartIndex + i] = pNewArray->GetAt(i);
00243     }
00244   }
00245 }
00246 
00247 void nsUInt32Array::RemoveAll()
00248 {
00249   SetSize(0);
00250 }
00251 
00252 void nsUInt32Array::RemoveAt(PRUint32 nIndex, PRUint32 nCount)
00253 {
00254   NS_ASSERTION(nIndex + nCount <= m_nSize, "removing past end of array");
00255   
00256   if (nCount > 0)
00257   {
00258     // Make sure not to overstep the end of the array
00259     int nMoveCount = m_nSize - (nIndex + nCount);
00260     if (nCount && nMoveCount)
00261       memmove(&m_pData[nIndex], &m_pData[nIndex + nCount],
00262       nMoveCount * sizeof(PRUint32));
00263     
00264     m_nSize -= nCount;
00265   }
00266 }
00267 
00268 void nsUInt32Array::SetAtGrow(PRUint32 nIndex, PRUint32 newElement)
00269 {
00270   if (nIndex >= m_nSize)
00271     SetSize(nIndex+1);
00272   m_pData[nIndex] = newElement;
00273 }
00274 
00275 PRBool nsUInt32Array:: RemoveElement(PRUint32 element)
00276 {
00277   for (PRUint32 i = 0; i < GetSize(); i++)
00278   {
00279     if ((PRUint32)(m_pData[i]) == element)
00280     {
00281       RemoveAt(i, 1);
00282       return PR_TRUE;
00283     }
00284   }
00285   return PR_FALSE;
00286 }
00287 
00288 
00289 PRUint32 nsUInt32Array::IndexOf(PRUint32 element)
00290 {
00291   for (PRUint32 i = 0; i < GetSize(); i++)
00292   {
00293     if ((PRUint32)(m_pData[i]) == element)
00294     {
00295       return i;
00296     }
00297   }
00298   return (PRUint32) kNotFound;
00299 }
00300 
00302 
00303 void nsUInt32Array::CopyArray(nsUInt32Array *oldA)
00304 {
00305   CopyArray(*oldA);
00306 }
00307 
00308 void nsUInt32Array::CopyArray(nsUInt32Array &oldA)
00309 {
00310   if (m_pData)
00311     PR_Free(m_pData);
00312   m_nSize = oldA.m_nSize;
00313   m_nMaxSize = oldA.m_nSize;
00314   m_pData = (PRUint32 *)PR_Malloc(m_nSize * sizeof(PRUint32));
00315   if (m_pData)
00316     memcpy(m_pData, oldA.m_pData, m_nSize * sizeof(PRUint32));
00317 }
00318 
00320 
00321 static int PR_CALLBACK CompareDWord (const void *v1, const void *v2, void *)
00322 {
00323   // QuickSort callback to compare array values
00324   PRUint32 i1 = *(PRUint32 *)v1;
00325   PRUint32 i2 = *(PRUint32 *)v2;
00326   return i1 < i2 ? -1 : (i1 == i2 ? 0 : 1);
00327 }
00328 
00329 void nsUInt32Array::QuickSort (int (* PR_CALLBACK compare) (const void *elem1, const void *elem2, void *data))
00330 {
00331   if (m_nSize > 1)
00332     NS_QuickSort(m_pData, m_nSize, sizeof(PRUint32), compare ? compare : CompareDWord, nsnull);
00333 }
00334 
00335 // Does a binary search - assumes array is sorted in ascending order.
00336 PRUint32 nsUInt32Array::IndexOfSorted(PRUint32 element)
00337 {
00338   PRInt32 msgIndex = 0;
00339   PRInt32 hi = m_nSize - 1;
00340   PRInt32 lo = 0;
00341   
00342   while (lo <= hi)
00343   {
00344     msgIndex = (lo + hi) / 2;
00345     if (m_pData[msgIndex] == element)
00346       return msgIndex;
00347     if (m_pData[msgIndex] > element)
00348       hi = msgIndex -1;
00349     else if (m_pData[msgIndex] <  element)
00350       lo = msgIndex + 1;
00351   }
00352   return kNotFound;
00353 }
00354