Back to index

lightning-sunbird  0.9+nobinonly
nsValueArray.cpp
Go to the documentation of this file.
00001 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
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 nsValueArray.h/nsValueArray.cpp code, released
00017  * Dec 28, 2001.
00018  *
00019  * The Initial Developer of the Original Code is
00020  * Netscape Communications Corporation.
00021  * Portions created by the Initial Developer are Copyright (C) 2001
00022  * the Initial Developer. All Rights Reserved.
00023  *
00024  * Contributor(s):
00025  *   Garrett Arch Blythe, 20-December-2001
00026  *
00027  * Alternatively, the contents of this file may be used under the terms of
00028  * either of the GNU General Public License Version 2 or later (the "GPL"),
00029  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00030  * in which case the provisions of the GPL or the LGPL are applicable instead
00031  * of those above. If you wish to allow use of your version of this file only
00032  * under the terms of either the GPL or the LGPL, and not to allow others to
00033  * use your version of this file under the terms of the MPL, indicate your
00034  * decision by deleting the provisions above and replace them with the notice
00035  * and other provisions required by the GPL or the LGPL. If you do not delete
00036  * the provisions above, a recipient may use your version of this file under
00037  * the terms of any one of the MPL, the GPL or the LGPL.
00038  *
00039  * ***** END LICENSE BLOCK ***** */
00040 
00041 //
00042 // nsValueArray.cpp
00043 //
00044 // Implement an array class to store unsigned integer values.
00045 // The maximum value must be known up front.  Once known, the
00046 //  smallest memory representation will be attempted; i.e. if the
00047 //  maximum value was 1275, then 2 bytes (uint16) would represent each value
00048 //  in the array instead of 4 bytes (uint32).
00049 //
00050 #include "nsValueArray.h"
00051 #include "nsCRT.h"
00052 #include "prmem.h"
00053 #include "prbit.h"
00054 
00055 #define NSVALUEARRAY_LINEAR_GROWBY 8
00056 #define NSVALUEARRAY_LINEAR_THRESHOLD  128
00057 
00058 nsValueArray::nsValueArray(nsValueArrayValue aMaxValue, nsValueArrayCount aInitialCapacity) {
00059     mCount = 0;
00060     mCapacity = 0;
00061     mValueArray = nsnull;
00062 
00063     PRUint8 test8 = (PRUint8)aMaxValue;
00064     PRUint16 test16 = (PRUint16)aMaxValue;
00065     PRUint32 test32 = (PRUint32)aMaxValue;
00066     if ((nsValueArrayValue)test8 == aMaxValue) {
00067         mBytesPerValue = sizeof(test8);
00068     }
00069     else if ((nsValueArrayValue)test16 == aMaxValue) {
00070         mBytesPerValue = sizeof(test16);
00071     }
00072     else if ((nsValueArrayValue)test32 == aMaxValue) {
00073         mBytesPerValue = sizeof(test32);
00074     }
00075     else {
00076         NS_ASSERTION(0, "not supported yet, add it yourself...");
00077         mBytesPerValue = 0;
00078     }
00079 
00080     if (aInitialCapacity) {
00081         mValueArray = (PRUint8*)PR_Malloc(aInitialCapacity * mBytesPerValue);
00082         if (nsnull != mValueArray) {
00083             mCapacity = aInitialCapacity;
00084         }
00085     }
00086 }
00087 
00088 nsValueArray::~nsValueArray() {
00089     if (nsnull != mValueArray) {
00090         PR_Free(mValueArray);
00091         mValueArray = nsnull;
00092     }
00093 }
00094 
00095 //
00096 // Copy it.
00097 //
00098 nsValueArray& nsValueArray::operator=(const nsValueArray& aOther) {
00099     //
00100     // Free off what you know if not enough space, or units differ.
00101     //
00102     if ((mBytesPerValue != aOther.mBytesPerValue || mCapacity < aOther.mCount) && nsnull != mValueArray) {
00103         PR_Free(mValueArray);
00104         mValueArray = nsnull;
00105         mCount = mCapacity = 0;
00106     }
00107 
00108     //
00109     // Copy some attribs.
00110     //
00111     mBytesPerValue = aOther.mBytesPerValue;
00112     mCount = aOther.mCount;
00113 
00114     //
00115     // Anything to do?
00116     //
00117     if (0 != mCount) {
00118         //
00119         // May need to allocate our buffer.
00120         //
00121         if (0 == mCapacity) {
00122             mValueArray = (PRUint8*)PR_Malloc(mCount * mBytesPerValue);
00123             mCapacity = mCount;
00124         }
00125 
00126         NS_ASSERTION(nsnull != mValueArray, "loss of value array assignment and original data.");
00127         if (nsnull != mValueArray) {
00128             memcpy(mValueArray, aOther.mValueArray, mCount * mBytesPerValue);
00129         }
00130         else {
00131             mCount = mCapacity = 0;
00132         }
00133     }
00134     
00135     return *this;
00136 }
00137 
00138 //
00139 // Insert a value into the array.
00140 // No validity checking other than index is done.
00141 //
00142 PRBool nsValueArray::InsertValueAt(nsValueArrayValue aValue, nsValueArrayIndex aIndex) {
00143     PRBool retval = PR_FALSE;
00144 
00145     nsValueArrayCount count = Count();
00146     if (aIndex <= count) {
00147         //
00148         // If we're at capacity, then we'll need to grow a little.
00149         //
00150         if (Capacity() == count) {
00151             PRUint8* reallocRes = nsnull;
00152             nsValueArrayCount growBy = NSVALUEARRAY_LINEAR_GROWBY;
00153 
00154             //
00155             // Up to a particular limit we grow in small increments.
00156             // Otherwise, grow exponentially.
00157             //
00158             if (count >= NSVALUEARRAY_LINEAR_THRESHOLD) {
00159                 growBy = PR_BIT(PR_CeilingLog2(count + 1)) - count;
00160             }
00161 
00162             if (nsnull == mValueArray) {
00163                 reallocRes = (PRUint8*)PR_Malloc((count + growBy) * mBytesPerValue);
00164             }
00165             else {
00166                 reallocRes = (PRUint8*)PR_Realloc(mValueArray, (count + growBy) * mBytesPerValue);
00167             }
00168             if (nsnull != reallocRes) {
00169                 mValueArray = reallocRes;
00170                 mCapacity += growBy;
00171             }
00172         }
00173 
00174         //
00175         // Only if we are below capacity do we continue.
00176         //
00177         if (Capacity() > count) {
00178             //
00179             // All those at and beyond the insertion point need to move.
00180             //
00181             if (aIndex < count) {
00182                 memmove(&mValueArray[(aIndex + 1) * mBytesPerValue], &mValueArray[aIndex * mBytesPerValue], (count - aIndex) * mBytesPerValue);
00183             }
00184 
00185             //
00186             // Do the assignment.
00187             //
00188             switch (mBytesPerValue) {
00189                 case sizeof(PRUint8):
00190                     *((PRUint8*)&mValueArray[aIndex * mBytesPerValue]) = (PRUint8)aValue;
00191                     NS_ASSERTION(*((PRUint8*)&mValueArray[aIndex * mBytesPerValue]) == aValue, "Lossy value array detected.  Report a higher maximum upon construction!");
00192                     break;
00193                 case sizeof(PRUint16):
00194                     *((PRUint16*)&mValueArray[aIndex * mBytesPerValue]) = (PRUint16)aValue;
00195                     NS_ASSERTION(*((PRUint16*)&mValueArray[aIndex * mBytesPerValue]) == aValue, "Lossy value array detected.  Report a higher maximum upon construction!");
00196                     break;
00197                 case sizeof(PRUint32):
00198                     *((PRUint32*)&mValueArray[aIndex * mBytesPerValue]) = (PRUint32)aValue;
00199                     NS_ASSERTION(*((PRUint32*)&mValueArray[aIndex * mBytesPerValue]) == aValue, "Lossy value array detected.  Report a higher maximum upon construction!");
00200                     break;
00201                 default:
00202                     NS_ASSERTION(0, "surely you've been warned prior to this!");
00203                     break;
00204             }
00205 
00206             //
00207             // Up the count by 1.
00208             //
00209             mCount++;
00210         }
00211     }
00212 
00213     return retval;
00214 }
00215 
00216 //
00217 // Remove the index from the value array.
00218 // The array does not shrink until Compact() is invoked.
00219 //
00220 PRBool nsValueArray::RemoveValueAt(nsValueArrayIndex aIndex) {
00221     PRBool retval = PR_FALSE;
00222 
00223     nsValueArrayCount count = Count();
00224     if (aIndex < count) {
00225         //
00226         // Move memory around if appropriate.
00227         //
00228         if (aIndex != (count - 1)) {
00229             memmove(&mValueArray[aIndex * mBytesPerValue], &mValueArray[(aIndex + 1) * mBytesPerValue], (count - aIndex - 1) * mBytesPerValue);
00230         }
00231 
00232         //
00233         // Update our count.
00234         //
00235         mCount--;
00236     }
00237 
00238     return retval;
00239 }
00240 
00241 //
00242 // Shrink as much as possible.
00243 //
00244 void nsValueArray::Compact() {
00245     nsValueArrayCount count = Count();
00246     if (Capacity() != count)
00247     {
00248         if (0 == count) {
00249             PR_Free(mValueArray);
00250             mValueArray = nsnull;
00251             mCapacity = 0;
00252         }
00253         else {
00254             PRUint8* reallocRes = (PRUint8*)PR_Realloc(mValueArray, count * mBytesPerValue);
00255             if (nsnull != reallocRes) {
00256                 mValueArray = reallocRes;
00257                 mCapacity = count;
00258             }
00259         }
00260     }
00261 }
00262 
00263 //
00264 // Return the value at the index.
00265 //
00266 nsValueArrayValue nsValueArray::ValueAt(nsValueArrayIndex aIndex) const {
00267     nsValueArrayValue retval = NSVALUEARRAY_INVALID;
00268     
00269     if (aIndex < Count()) {
00270         switch (mBytesPerValue) {
00271             case sizeof(PRUint8):
00272                 retval = (nsValueArrayIndex)*((PRUint8*)&mValueArray[aIndex * mBytesPerValue]);
00273                 break;
00274             case sizeof(PRUint16):
00275                 retval = (nsValueArrayIndex)*((PRUint16*)&mValueArray[aIndex * mBytesPerValue]);
00276                 break;
00277             case sizeof(PRUint32):
00278                 retval = (nsValueArrayIndex)*((PRUint32*)&mValueArray[aIndex * mBytesPerValue]);
00279                 break;
00280             default:
00281                 NS_ASSERTION(0, "unexpected for sure.");
00282                 break;
00283         }
00284     }
00285     
00286     return retval;
00287 }
00288 
00289 //
00290 // Return the first encountered index of the value.
00291 //
00292 nsValueArrayIndex nsValueArray::IndexOf(nsValueArrayValue aPossibleValue) const {
00293     nsValueArrayIndex retval = NSVALUEARRAY_INVALID;
00294     nsValueArrayIndex traverse;
00295     
00296     for (traverse = 0; traverse < Count(); traverse++) {
00297         if (aPossibleValue == ValueAt(traverse)) {
00298             retval = traverse;
00299             break;
00300         }
00301     }
00302     
00303     return retval;
00304 }