| 1 | /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
|
|---|
| 2 | *
|
|---|
| 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 nsValueArray.h/nsValueArray.cpp code, released
|
|---|
| 17 | * Dec 28, 2001.
|
|---|
| 18 | *
|
|---|
| 19 | * The Initial Developer of the Original Code is
|
|---|
| 20 | * Netscape Communications Corporation.
|
|---|
| 21 | * Portions created by the Initial Developer are Copyright (C) 2001
|
|---|
| 22 | * the Initial Developer. All Rights Reserved.
|
|---|
| 23 | *
|
|---|
| 24 | * Contributor(s):
|
|---|
| 25 | * Garrett Arch Blythe, 20-December-2001
|
|---|
| 26 | *
|
|---|
| 27 | * Alternatively, the contents of this file may be used under the terms of
|
|---|
| 28 | * either of the GNU General Public License Version 2 or later (the "GPL"),
|
|---|
| 29 | * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
|
|---|
| 30 | * in which case the provisions of the GPL or the LGPL are applicable instead
|
|---|
| 31 | * of those above. If you wish to allow use of your version of this file only
|
|---|
| 32 | * under the terms of either the GPL or the LGPL, and not to allow others to
|
|---|
| 33 | * use your version of this file under the terms of the MPL, indicate your
|
|---|
| 34 | * decision by deleting the provisions above and replace them with the notice
|
|---|
| 35 | * and other provisions required by the GPL or the LGPL. If you do not delete
|
|---|
| 36 | * the provisions above, a recipient may use your version of this file under
|
|---|
| 37 | * the terms of any one of the MPL, the GPL or the LGPL.
|
|---|
| 38 | *
|
|---|
| 39 | * ***** END LICENSE BLOCK ***** */
|
|---|
| 40 |
|
|---|
| 41 | //
|
|---|
| 42 | // nsValueArray.cpp
|
|---|
| 43 | //
|
|---|
| 44 | // Implement an array class to store unsigned integer values.
|
|---|
| 45 | // The maximum value must be known up front. Once known, the
|
|---|
| 46 | // smallest memory representation will be attempted; i.e. if the
|
|---|
| 47 | // maximum value was 1275, then 2 bytes (uint16) would represent each value
|
|---|
| 48 | // in the array instead of 4 bytes (uint32).
|
|---|
| 49 | //
|
|---|
| 50 | #include "nsValueArray.h"
|
|---|
| 51 | #include "nsCRT.h"
|
|---|
| 52 | #include "prmem.h"
|
|---|
| 53 | #include "prbit.h"
|
|---|
| 54 |
|
|---|
| 55 | #define NSVALUEARRAY_LINEAR_GROWBY 8
|
|---|
| 56 | #define NSVALUEARRAY_LINEAR_THRESHOLD 128
|
|---|
| 57 |
|
|---|
| 58 | nsValueArray::nsValueArray(nsValueArrayValue aMaxValue, nsValueArrayCount aInitialCapacity) {
|
|---|
| 59 | mCount = 0;
|
|---|
| 60 | mCapacity = 0;
|
|---|
| 61 | mValueArray = nsnull;
|
|---|
| 62 |
|
|---|
| 63 | PRUint8 test8 = (PRUint8)aMaxValue;
|
|---|
| 64 | PRUint16 test16 = (PRUint16)aMaxValue;
|
|---|
| 65 | PRUint32 test32 = (PRUint32)aMaxValue;
|
|---|
| 66 | if ((nsValueArrayValue)test8 == aMaxValue) {
|
|---|
| 67 | mBytesPerValue = sizeof(test8);
|
|---|
| 68 | }
|
|---|
| 69 | else if ((nsValueArrayValue)test16 == aMaxValue) {
|
|---|
| 70 | mBytesPerValue = sizeof(test16);
|
|---|
| 71 | }
|
|---|
| 72 | else if ((nsValueArrayValue)test32 == aMaxValue) {
|
|---|
| 73 | mBytesPerValue = sizeof(test32);
|
|---|
| 74 | }
|
|---|
| 75 | else {
|
|---|
| 76 | NS_ASSERTION(0, "not supported yet, add it yourself...");
|
|---|
| 77 | mBytesPerValue = 0;
|
|---|
| 78 | }
|
|---|
| 79 |
|
|---|
| 80 | if (aInitialCapacity) {
|
|---|
| 81 | mValueArray = (PRUint8*)PR_Malloc(aInitialCapacity * mBytesPerValue);
|
|---|
| 82 | if (nsnull != mValueArray) {
|
|---|
| 83 | mCapacity = aInitialCapacity;
|
|---|
| 84 | }
|
|---|
| 85 | }
|
|---|
| 86 | }
|
|---|
| 87 |
|
|---|
| 88 | nsValueArray::~nsValueArray() {
|
|---|
| 89 | if (nsnull != mValueArray) {
|
|---|
| 90 | PR_Free(mValueArray);
|
|---|
| 91 | mValueArray = nsnull;
|
|---|
| 92 | }
|
|---|
| 93 | }
|
|---|
| 94 |
|
|---|
| 95 | //
|
|---|
| 96 | // Copy it.
|
|---|
| 97 | //
|
|---|
| 98 | nsValueArray& nsValueArray::operator=(const nsValueArray& aOther) {
|
|---|
| 99 | //
|
|---|
| 100 | // Free off what you know if not enough space, or units differ.
|
|---|
| 101 | //
|
|---|
| 102 | if ((mBytesPerValue != aOther.mBytesPerValue || mCapacity < aOther.mCount) && nsnull != mValueArray) {
|
|---|
| 103 | PR_Free(mValueArray);
|
|---|
| 104 | mValueArray = nsnull;
|
|---|
| 105 | mCount = mCapacity = 0;
|
|---|
| 106 | }
|
|---|
| 107 |
|
|---|
| 108 | //
|
|---|
| 109 | // Copy some attribs.
|
|---|
| 110 | //
|
|---|
| 111 | mBytesPerValue = aOther.mBytesPerValue;
|
|---|
| 112 | mCount = aOther.mCount;
|
|---|
| 113 |
|
|---|
| 114 | //
|
|---|
| 115 | // Anything to do?
|
|---|
| 116 | //
|
|---|
| 117 | if (0 != mCount) {
|
|---|
| 118 | //
|
|---|
| 119 | // May need to allocate our buffer.
|
|---|
| 120 | //
|
|---|
| 121 | if (0 == mCapacity) {
|
|---|
| 122 | mValueArray = (PRUint8*)PR_Malloc(mCount * mBytesPerValue);
|
|---|
| 123 | mCapacity = mCount;
|
|---|
| 124 | }
|
|---|
| 125 |
|
|---|
| 126 | NS_ASSERTION(nsnull != mValueArray, "loss of value array assignment and original data.");
|
|---|
| 127 | if (nsnull != mValueArray) {
|
|---|
| 128 | memcpy(mValueArray, aOther.mValueArray, mCount * mBytesPerValue);
|
|---|
| 129 | }
|
|---|
| 130 | else {
|
|---|
| 131 | mCount = mCapacity = 0;
|
|---|
| 132 | }
|
|---|
| 133 | }
|
|---|
| 134 |
|
|---|
| 135 | return *this;
|
|---|
| 136 | }
|
|---|
| 137 |
|
|---|
| 138 | //
|
|---|
| 139 | // Insert a value into the array.
|
|---|
| 140 | // No validity checking other than index is done.
|
|---|
| 141 | //
|
|---|
| 142 | PRBool nsValueArray::InsertValueAt(nsValueArrayValue aValue, nsValueArrayIndex aIndex) {
|
|---|
| 143 | PRBool retval = PR_FALSE;
|
|---|
| 144 |
|
|---|
| 145 | nsValueArrayCount count = Count();
|
|---|
| 146 | if (aIndex <= count) {
|
|---|
| 147 | //
|
|---|
| 148 | // If we're at capacity, then we'll need to grow a little.
|
|---|
| 149 | //
|
|---|
| 150 | if (Capacity() == count) {
|
|---|
| 151 | PRUint8* reallocRes = nsnull;
|
|---|
| 152 | nsValueArrayCount growBy = NSVALUEARRAY_LINEAR_GROWBY;
|
|---|
| 153 |
|
|---|
| 154 | //
|
|---|
| 155 | // Up to a particular limit we grow in small increments.
|
|---|
| 156 | // Otherwise, grow exponentially.
|
|---|
| 157 | //
|
|---|
| 158 | if (count >= NSVALUEARRAY_LINEAR_THRESHOLD) {
|
|---|
| 159 | growBy = PR_BIT(PR_CeilingLog2(count + 1)) - count;
|
|---|
| 160 | }
|
|---|
| 161 |
|
|---|
| 162 | if (nsnull == mValueArray) {
|
|---|
| 163 | reallocRes = (PRUint8*)PR_Malloc((count + growBy) * mBytesPerValue);
|
|---|
| 164 | }
|
|---|
| 165 | else {
|
|---|
| 166 | reallocRes = (PRUint8*)PR_Realloc(mValueArray, (count + growBy) * mBytesPerValue);
|
|---|
| 167 | }
|
|---|
| 168 | if (nsnull != reallocRes) {
|
|---|
| 169 | mValueArray = reallocRes;
|
|---|
| 170 | mCapacity += growBy;
|
|---|
| 171 | }
|
|---|
| 172 | }
|
|---|
| 173 |
|
|---|
| 174 | //
|
|---|
| 175 | // Only if we are below capacity do we continue.
|
|---|
| 176 | //
|
|---|
| 177 | if (Capacity() > count) {
|
|---|
| 178 | //
|
|---|
| 179 | // All those at and beyond the insertion point need to move.
|
|---|
| 180 | //
|
|---|
| 181 | if (aIndex < count) {
|
|---|
| 182 | memmove(&mValueArray[(aIndex + 1) * mBytesPerValue], &mValueArray[aIndex * mBytesPerValue], (count - aIndex) * mBytesPerValue);
|
|---|
| 183 | }
|
|---|
| 184 |
|
|---|
| 185 | //
|
|---|
| 186 | // Do the assignment.
|
|---|
| 187 | //
|
|---|
| 188 | switch (mBytesPerValue) {
|
|---|
| 189 | case sizeof(PRUint8):
|
|---|
| 190 | *((PRUint8*)&mValueArray[aIndex * mBytesPerValue]) = (PRUint8)aValue;
|
|---|
| 191 | NS_ASSERTION(*((PRUint8*)&mValueArray[aIndex * mBytesPerValue]) == aValue, "Lossy value array detected. Report a higher maximum upon construction!");
|
|---|
| 192 | break;
|
|---|
| 193 | case sizeof(PRUint16):
|
|---|
| 194 | *((PRUint16*)&mValueArray[aIndex * mBytesPerValue]) = (PRUint16)aValue;
|
|---|
| 195 | NS_ASSERTION(*((PRUint16*)&mValueArray[aIndex * mBytesPerValue]) == aValue, "Lossy value array detected. Report a higher maximum upon construction!");
|
|---|
| 196 | break;
|
|---|
| 197 | case sizeof(PRUint32):
|
|---|
| 198 | *((PRUint32*)&mValueArray[aIndex * mBytesPerValue]) = (PRUint32)aValue;
|
|---|
| 199 | NS_ASSERTION(*((PRUint32*)&mValueArray[aIndex * mBytesPerValue]) == aValue, "Lossy value array detected. Report a higher maximum upon construction!");
|
|---|
| 200 | break;
|
|---|
| 201 | default:
|
|---|
| 202 | NS_ASSERTION(0, "surely you've been warned prior to this!");
|
|---|
| 203 | break;
|
|---|
| 204 | }
|
|---|
| 205 |
|
|---|
| 206 | //
|
|---|
| 207 | // Up the count by 1.
|
|---|
| 208 | //
|
|---|
| 209 | mCount++;
|
|---|
| 210 | }
|
|---|
| 211 | }
|
|---|
| 212 |
|
|---|
| 213 | return retval;
|
|---|
| 214 | }
|
|---|
| 215 |
|
|---|
| 216 | //
|
|---|
| 217 | // Remove the index from the value array.
|
|---|
| 218 | // The array does not shrink until Compact() is invoked.
|
|---|
| 219 | //
|
|---|
| 220 | PRBool nsValueArray::RemoveValueAt(nsValueArrayIndex aIndex) {
|
|---|
| 221 | PRBool retval = PR_FALSE;
|
|---|
| 222 |
|
|---|
| 223 | nsValueArrayCount count = Count();
|
|---|
| 224 | if (aIndex < count) {
|
|---|
| 225 | //
|
|---|
| 226 | // Move memory around if appropriate.
|
|---|
| 227 | //
|
|---|
| 228 | if (aIndex != (count - 1)) {
|
|---|
| 229 | memmove(&mValueArray[aIndex * mBytesPerValue], &mValueArray[(aIndex + 1) * mBytesPerValue], (count - aIndex - 1) * mBytesPerValue);
|
|---|
| 230 | }
|
|---|
| 231 |
|
|---|
| 232 | //
|
|---|
| 233 | // Update our count.
|
|---|
| 234 | //
|
|---|
| 235 | mCount--;
|
|---|
| 236 | }
|
|---|
| 237 |
|
|---|
| 238 | return retval;
|
|---|
| 239 | }
|
|---|
| 240 |
|
|---|
| 241 | //
|
|---|
| 242 | // Shrink as much as possible.
|
|---|
| 243 | //
|
|---|
| 244 | void nsValueArray::Compact() {
|
|---|
| 245 | nsValueArrayCount count = Count();
|
|---|
| 246 | if (Capacity() != count)
|
|---|
| 247 | {
|
|---|
| 248 | if (0 == count) {
|
|---|
| 249 | PR_Free(mValueArray);
|
|---|
| 250 | mValueArray = nsnull;
|
|---|
| 251 | mCapacity = 0;
|
|---|
| 252 | }
|
|---|
| 253 | else {
|
|---|
| 254 | PRUint8* reallocRes = (PRUint8*)PR_Realloc(mValueArray, count * mBytesPerValue);
|
|---|
| 255 | if (nsnull != reallocRes) {
|
|---|
| 256 | mValueArray = reallocRes;
|
|---|
| 257 | mCapacity = count;
|
|---|
| 258 | }
|
|---|
| 259 | }
|
|---|
| 260 | }
|
|---|
| 261 | }
|
|---|
| 262 |
|
|---|
| 263 | //
|
|---|
| 264 | // Return the value at the index.
|
|---|
| 265 | //
|
|---|
| 266 | nsValueArrayValue nsValueArray::ValueAt(nsValueArrayIndex aIndex) const {
|
|---|
| 267 | nsValueArrayValue retval = NSVALUEARRAY_INVALID;
|
|---|
| 268 |
|
|---|
| 269 | if (aIndex < Count()) {
|
|---|
| 270 | switch (mBytesPerValue) {
|
|---|
| 271 | case sizeof(PRUint8):
|
|---|
| 272 | retval = (nsValueArrayIndex)*((PRUint8*)&mValueArray[aIndex * mBytesPerValue]);
|
|---|
| 273 | break;
|
|---|
| 274 | case sizeof(PRUint16):
|
|---|
| 275 | retval = (nsValueArrayIndex)*((PRUint16*)&mValueArray[aIndex * mBytesPerValue]);
|
|---|
| 276 | break;
|
|---|
| 277 | case sizeof(PRUint32):
|
|---|
| 278 | retval = (nsValueArrayIndex)*((PRUint32*)&mValueArray[aIndex * mBytesPerValue]);
|
|---|
| 279 | break;
|
|---|
| 280 | default:
|
|---|
| 281 | NS_ASSERTION(0, "unexpected for sure.");
|
|---|
| 282 | break;
|
|---|
| 283 | }
|
|---|
| 284 | }
|
|---|
| 285 |
|
|---|
| 286 | return retval;
|
|---|
| 287 | }
|
|---|
| 288 |
|
|---|
| 289 | //
|
|---|
| 290 | // Return the first encountered index of the value.
|
|---|
| 291 | //
|
|---|
| 292 | nsValueArrayIndex nsValueArray::IndexOf(nsValueArrayValue aPossibleValue) const {
|
|---|
| 293 | nsValueArrayIndex retval = NSVALUEARRAY_INVALID;
|
|---|
| 294 | nsValueArrayIndex traverse;
|
|---|
| 295 |
|
|---|
| 296 | for (traverse = 0; traverse < Count(); traverse++) {
|
|---|
| 297 | if (aPossibleValue == ValueAt(traverse)) {
|
|---|
| 298 | retval = traverse;
|
|---|
| 299 | break;
|
|---|
| 300 | }
|
|---|
| 301 | }
|
|---|
| 302 |
|
|---|
| 303 | return retval;
|
|---|
| 304 | }
|
|---|
