/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- * * The contents of this file are subject to the Mozilla Public * License Version 1.1 (the "License"); you may not use this file * except in compliance with the License. You may obtain a copy of * the License at http://www.mozilla.org/MPL/ * * Software distributed under the License is distributed on an "AS * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express oqr * implied. See the License for the specific language governing * rights and limitations under the License. * * The Original Code is nsValueArray.h/nsValueArray.cpp code, released * Dec 28, 2001. * * The Initial Developer of the Original Code is Netscape * Communications Corporation. Portions created by Netscape are * Copyright (C) 2001 Netscape Communications Corporation. All * Rights Reserved. * * Contributor(s): * Garrett Arch Blythe, 20-December-2001 * * Alternatively, the contents of this file may be used under the * terms of the GNU Public License (the "GPL"), in which case the * provisions of the GPL are applicable instead of those above. * If you wish to allow use of your version of this file only * under the terms of the GPL and not to allow others to use your * version of this file under the MPL, indicate your decision by * deleting the provisions above and replace them with the notice * and other provisions required by the GPL. If you do not delete * the provisions above, a recipient may use your version of this * file under either the MPL or the GPL. */ // // nsValueArray.cpp // // Implement an array class to store unsigned integer values. // The maximum value must be known up front. Once known, the // smallest memory representation will be attempted; i.e. if the // maximum value was 1275, then 2 bytes (uint16) would represent each value // in the array instead of 4 bytes (uint32). // #include "nsValueArray.h" #include "nsCRT.h" #include "prmem.h" #include "prbit.h" #define NSVALUEARRAY_LINEAR_GROWBY 8 #define NSVALUEARRAY_LINEAR_THRESHOLD 128 nsValueArray::nsValueArray(nsValueArrayValue aMaxValue, nsValueArrayCount aInitialCapacity) { mCount = 0; mCapacity = 0; mValueArray = nsnull; PRUint8 test8 = (PRUint8)aMaxValue; PRUint16 test16 = (PRUint16)aMaxValue; PRUint32 test32 = (PRUint32)aMaxValue; if ((nsValueArrayValue)test8 == aMaxValue) { mBytesPerValue = sizeof(test8); } else if ((nsValueArrayValue)test16 == aMaxValue) { mBytesPerValue = sizeof(test16); } else if ((nsValueArrayValue)test32 == aMaxValue) { mBytesPerValue = sizeof(test32); } else { NS_ASSERTION(0, "not supported yet, add it yourself..."); mBytesPerValue = 0; } if (aInitialCapacity) { mValueArray = (PRUint8*)PR_Malloc(aInitialCapacity * mBytesPerValue); if (nsnull != mValueArray) { mCapacity = aInitialCapacity; } } } nsValueArray::~nsValueArray() { if (nsnull != mValueArray) { PR_Free(mValueArray); mValueArray = nsnull; } } // // Copy it. // nsValueArray& nsValueArray::operator=(const nsValueArray& aOther) { // // Free off what you know if not enough space, or units differ. // if ((mBytesPerValue != aOther.mBytesPerValue || mCapacity < aOther.mCount) && nsnull != mValueArray) { PR_Free(mValueArray); mValueArray = nsnull; mCount = mCapacity = 0; } // // Copy some attribs. // mBytesPerValue = aOther.mBytesPerValue; mCount = aOther.mCount; // // Anything to do? // if (0 != mCount) { // // May need to allocate our buffer. // if (0 == mCapacity) { mValueArray = (PRUint8*)PR_Malloc(mCount * mBytesPerValue); mCapacity = mCount; } NS_ASSERTION(nsnull != mValueArray, "loss of value array assignment and original data."); if (nsnull != mValueArray) { nsCRT::memcpy(mValueArray, aOther.mValueArray, mCount * mBytesPerValue); } else { mCount = mCapacity = 0; } } return *this; } // // Insert a value into the array. // No validity checking other than index is done. // PRBool nsValueArray::InsertValueAt(nsValueArrayValue aValue, nsValueArrayIndex aIndex) { PRBool retval = PR_FALSE; nsValueArrayCount count = Count(); if (aIndex <= count) { // // If we're at capacity, then we'll need to grow a little. // if (Capacity() == count) { PRUint8* reallocRes = nsnull; nsValueArrayCount growBy = NSVALUEARRAY_LINEAR_GROWBY; // // Up to a particular limit we grow in small increments. // Otherwise, grow exponentially. // if (count >= NSVALUEARRAY_LINEAR_THRESHOLD) { growBy = PR_BIT(PR_CeilingLog2(count + 1)) - count; } if (nsnull == mValueArray) { reallocRes = (PRUint8*)PR_Malloc((count + growBy) * mBytesPerValue); } else { reallocRes = (PRUint8*)PR_Realloc(mValueArray, (count + growBy) * mBytesPerValue); } if (nsnull != reallocRes) { mValueArray = reallocRes; mCapacity += growBy; } } // // Only if we are below capacity do we continue. // if (Capacity() > count) { // // All those at and beyond the insertion point need to move. // if (aIndex < count) { nsCRT::memmove(&mValueArray[(aIndex + 1) * mBytesPerValue], &mValueArray[aIndex * mBytesPerValue], (count - aIndex) * mBytesPerValue); } // // Do the assignment. // switch (mBytesPerValue) { case sizeof(PRUint8): *((PRUint8*)&mValueArray[aIndex * mBytesPerValue]) = (PRUint8)aValue; NS_ASSERTION(*((PRUint8*)&mValueArray[aIndex * mBytesPerValue]) == aValue, "Lossy value array detected. Report a higher maximum upon construction!"); break; case sizeof(PRUint16): *((PRUint16*)&mValueArray[aIndex * mBytesPerValue]) = (PRUint16)aValue; NS_ASSERTION(*((PRUint16*)&mValueArray[aIndex * mBytesPerValue]) == aValue, "Lossy value array detected. Report a higher maximum upon construction!"); break; case sizeof(PRUint32): *((PRUint32*)&mValueArray[aIndex * mBytesPerValue]) = (PRUint32)aValue; NS_ASSERTION(*((PRUint32*)&mValueArray[aIndex * mBytesPerValue]) == aValue, "Lossy value array detected. Report a higher maximum upon construction!"); break; default: NS_ASSERTION(0, "surely you've been warned prior to this!"); break; } // // Up the count by 1. // mCount++; } } return retval; } // // Remove the index from the value array. // The array does not shrink until Compact() is invoked. // PRBool nsValueArray::RemoveValueAt(nsValueArrayIndex aIndex) { PRBool retval = PR_FALSE; nsValueArrayCount count = Count(); if (aIndex < count) { // // Move memory around if appropriate. // if (aIndex != (count - 1)) { nsCRT::memmove(&mValueArray[aIndex * mBytesPerValue], &mValueArray[(aIndex + 1) * mBytesPerValue], (count - aIndex - 1) * mBytesPerValue); } // // Update our count. // mCount--; } return retval; } // // Shrink as much as possible. // void nsValueArray::Compact() { nsValueArrayCount count = Count(); if (Capacity() != count) { if (0 == count) { PR_Free(mValueArray); mValueArray = nsnull; mCapacity = 0; } else { PRUint8* reallocRes = (PRUint8*)PR_Realloc(mValueArray, count * mBytesPerValue); if (nsnull != reallocRes) { mValueArray = reallocRes; mCapacity = count; } } } } // // Return the value at the index. // nsValueArrayValue nsValueArray::ValueAt(nsValueArrayIndex aIndex) const { nsValueArrayValue retval = NSVALUEARRAY_INVALID; if (aIndex < Count()) { switch (mBytesPerValue) { case sizeof(PRUint8): retval = (nsValueArrayIndex)*((PRUint8*)&mValueArray[aIndex * mBytesPerValue]); break; case sizeof(PRUint16): retval = (nsValueArrayIndex)*((PRUint16*)&mValueArray[aIndex * mBytesPerValue]); break; case sizeof(PRUint32): retval = (nsValueArrayIndex)*((PRUint32*)&mValueArray[aIndex * mBytesPerValue]); break; default: NS_ASSERTION(0, "unexpected for sure."); break; } } return retval; } // // Return the first encountered index of the value. // nsValueArrayIndex nsValueArray::IndexOf(nsValueArrayValue aPossibleValue) const { nsValueArrayIndex retval = NSVALUEARRAY_INVALID; nsValueArrayIndex traverse; for (traverse = 0; traverse < Count(); traverse++) { if (aPossibleValue == ValueAt(traverse)) { retval = traverse; break; } } return retval; }