nsVoidArray.cpp revision 677833bc953b6cb418c701facbdcf4aa18d6c44e
/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2; c-file-offsets: ((substatement-open . 0)) -*- */
/* ***** BEGIN LICENSE BLOCK *****
* Version: MPL 1.1/GPL 2.0/LGPL 2.1
*
* 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
*
* Software distributed under the License is distributed on an "AS IS" basis,
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
* for the specific language governing rights and limitations under the
* License.
*
* The Original Code is mozilla.org code.
*
* The Initial Developer of the Original Code is
* Netscape Communications Corporation.
* Portions created by the Initial Developer are Copyright (C) 1998
* the Initial Developer. All Rights Reserved.
*
* Contributor(s):
*
* Alternatively, the contents of this file may be used under the terms of
* either of the GNU General Public License Version 2 or later (the "GPL"),
* or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
* in which case the provisions of the GPL or the LGPL are applicable instead
* of those above. If you wish to allow use of your version of this file only
* under the terms of either the GPL or the LGPL, and not to allow others to
* use your version of this file under the terms of the MPL, indicate your
* decision by deleting the provisions above and replace them with the notice
* and other provisions required by the GPL or the LGPL. If you do not delete
* the provisions above, a recipient may use your version of this file under
* the terms of any one of the MPL, the GPL or the LGPL.
*
* ***** END LICENSE BLOCK ***** */
#include "nsVoidArray.h"
#include "nsQuickSort.h"
#include "prmem.h"
#include "nsCRT.h"
#include "nsString.h"
#include "prbit.h"
/**
* Grow the array by at least this many elements at a time.
*/
/**
* This is the threshold (in bytes) of the mImpl struct, past which
* we'll force the array to grow geometrically
*/
/**
* Compute the number of bytes requires for the mImpl struct that will
* hold |n| elements.
*/
/**
* Compute the number of elements that an mImpl struct of |n| bytes
* will hold.
*/
#if DEBUG_VOIDARRAY
#define MAXVOID 10
class VoidStats {
public:
VoidStats();
~VoidStats();
};
static int sizesUsed; // number of the elements of the arrays used
// these are per-allocation
// statistics macros
{ \
if (sizesAlloced[i] == (int)(size)) \
{ ((x)[i])++; break; } \
} \
((x)[sizesUsed++])++; break; \
} \
} while (0)
{ \
if (sizesAlloced[i] == (int)(size)) \
{ ((x)[i])--; break; } \
} \
} while (0)
{
sizesUsed = 1;
sizesAlloced[0] = 0;
}
{
int i;
for (i = 0; i < sizesUsed; i++)
{
}
printf("Max Size of VoidArray:\n");
for (i = 0; i < (int)(sizeof(MaxElements)/sizeof(MaxElements[0])); i++)
{
if (MaxElements[i])
}
}
// Just so constructor/destructor's get called
#endif
inline void
{
(owner ? kArrayOwnerMask : 0);
}
// This does all allocation/reallocation of the array.
// It also will compact down to N - good for things that might grow a lot
// at times, but usually are smaller, like JS deferred GC releases.
{
return PR_TRUE; // no change
if (aSize <= 0)
{
// free the array if allocated
if (mImpl)
{
if (IsArrayOwner())
{
}
else
{
}
}
return PR_TRUE;
}
if (mImpl && IsArrayOwner())
{
// We currently own an array impl. Resize it appropriately.
{
// XXX Note: we could also just resize to mCount
return PR_TRUE; // can't make it that small, ignore request
}
if (!newImpl)
return PR_FALSE;
#if DEBUG_VOIDARRAY
{
if (oldsize)
if (mIsAuto)
{
}
}
#endif
return PR_TRUE;
}
// just allocate an array
// allocate the exact size requested
if (!newImpl)
return PR_FALSE;
#if DEBUG_VOIDARRAY
{
}
#endif
if (mImpl)
{
#if DEBUG_VOIDARRAY
#endif
// We must be growing an nsAutoVoidArray - copy since we didn't
// realloc.
}
// no memset; handled later in ReplaceElementAt if needed
return PR_TRUE;
}
{
// We have to grow the array. Grow by kMinGrowArrayBy slots if we're
// smaller than kLinearThreshold bytes, or a power of two if we're
// larger. This is much more efficient with most memory allocators,
// especially if it's very large, or of the allocator is binned.
if (aGrowBy < kMinGrowArrayBy)
{
// newCount includes enough space for at least kMinGrowArrayBy new
// slots. Select the next power-of-two size in bytes above or
// equal to that.
// Also, limit the increase in size to about a VM page or two.
if (GetArraySize() >= kMaxGrowArrayBy)
{
}
else
{
}
}
// frees old mImpl IF this succeeds
if (!SizeTo(newCapacity))
return PR_FALSE;
return PR_TRUE;
}
{
#if DEBUG_VOIDARRAY
mMaxCount = 0;
mMaxSize = 0;
MaxElements[0]++;
#endif
}
{
#if DEBUG_VOIDARRAY
mMaxCount = 0;
mMaxSize = 0;
MaxElements[0]++;
#endif
}
{
if (otherCount)
{
if (otherCount > maxCount)
{
// frees old mImpl IF this succeeds
return *this; // XXX The allocation failed - don't do anything
}
else
{
// the old array can hold the new array
// if it shrank a lot, compact it anyways
{
Compact(); // shrank by at least 50 entries
}
}
#if DEBUG_VOIDARRAY
{
MaxElements[mMaxCount]--;
}
#endif
}
else
{
if (mImpl && IsArrayOwner())
}
return *this;
}
{
if (mImpl && IsArrayOwner())
}
{
if (mImpl)
{
{
if (*ap == aPossibleElement)
{
}
ap++;
}
}
return -1;
}
{
{
// An invalid index causes the insertion to fail
// Invalid indexes are ones that add more than one entry to the
// array (i.e., they can append).
return PR_FALSE;
}
if (oldCount >= GetArraySize())
{
if (!GrowArrayBy(1))
return PR_FALSE;
}
// else the array is already large enough
if (0 != slide)
{
// Slide data over to make room for the insertion
}
#if DEBUG_VOIDARRAY
{
MaxElements[mMaxCount]--;
}
#endif
return PR_TRUE;
}
{
{
// An invalid index causes the insertion to fail
// Invalid indexes are ones that are more than one entry past the end of
// the array (i.e., they can append).
return PR_FALSE;
}
{
if (!GrowArrayBy(otherCount))
return PR_FALSE;;
}
// else the array is already large enough
if (0 != slide)
{
// Slide data over to make room for the insertion
}
for (PRInt32 i = 0; i < otherCount; i++)
{
// copy all the elements (destroys aIndex)
}
#if DEBUG_VOIDARRAY
{
MaxElements[mMaxCount]--;
}
#endif
return PR_TRUE;
}
{
if (aIndex < 0)
return PR_FALSE;
// Unlike InsertElementAt, ReplaceElementAt can implicitly add more
// than just the one element to the array.
{
// frees old mImpl IF this succeeds
if (!GrowArrayBy(growDelta))
return PR_FALSE;
}
{
// Make sure that any entries implicitly added to the array by this
// ReplaceElementAt are cleared to 0. Some users of this assume that.
// This code means we don't have to memset when we allocate an array.
{
// For example, if mCount is 2, and we do a ReplaceElementAt for
// element[5], then we need to set three entries ([2], [3], and [4])
// to 0.
}
#if DEBUG_VOIDARRAY
{
MaxElements[mMaxCount]--;
}
#endif
}
return PR_TRUE;
}
// useful for doing LRU arrays
{
void *tempElement;
return PR_TRUE;
{
// can't extend the array when moving an element. Also catches mImpl = null
return PR_FALSE;
}
{
// Moving one element closer to the head; the elements inbetween move down
}
else // already handled aFrom == aTo
{
// Moving one element closer to the tail; the elements inbetween move up
}
return PR_TRUE;
}
{
{
// An invalid index causes the replace to fail
return PR_FALSE;
}
// Limit to available entries starting at aIndex
// We don't need to move any elements if we're removing the
// last element in the array
{
}
return PR_TRUE;
}
{
if (theIndex != -1)
return RemoveElementAt(theIndex);
return PR_FALSE;
}
void nsVoidArray::Clear()
{
if (mImpl)
{
}
}
void nsVoidArray::Compact()
{
if (mImpl)
{
// XXX NOTE: this is quite inefficient in many cases if we're only
// compacting by a little, but some callers care more about memory use.
if (GetArraySize() > Count())
{
}
}
}
// Needed because we want to pass the pointer to the item in the array
// to the comparator function, not a pointer to the pointer in the array.
struct VoidArrayComparatorContext {
void* mData;
};
PR_STATIC_CALLBACK(int)
{
*NS_STATIC_CAST(void* const*, aElement2),
}
{
{
}
}
{
if (mImpl)
{
{
}
}
return running;
}
{
if (mImpl)
{
{
}
}
return running;
}
//----------------------------------------------------------------
// nsAutoVoidArray
: nsVoidArray()
{
// Don't need to clear it. Some users just call ReplaceElementAt(),
// but we'll clear it at that time if needed to save CPU cycles.
#if DEBUG_VOIDARRAY
ADD_TO_STATS(MaxAuto,0);
#endif
}
void nsAutoVoidArray::Clear()
{
// We don't have to free on Clear, but since we have a built-in buffer,
// it's worth considering.
nsVoidArray::Clear();
SizeTo(0); // we override CompactTo - delete and repoint at auto array
}
{
return PR_FALSE;
if (!mImpl)
{
// reset the array to point to our autobuf
}
return PR_TRUE;
}
void nsAutoVoidArray::Compact()
{
nsVoidArray::Compact();
if (!mImpl)
{
// reset the array to point to our autobuf
}
}
//----------------------------------------------------------------
// nsStringArray
nsStringArray::nsStringArray(void)
: nsVoidArray()
{
}
{
}
nsStringArray::~nsStringArray(void)
{
Clear();
}
{
// Copy the pointers
nsVoidArray::operator=(other);
// Now copy the strings
{
}
return *this;
}
void
{
{
}
else
{
}
}
{
}
{
if (mImpl)
{
{
{
}
ap++;
}
}
return -1;
}
{
{
return PR_TRUE;
}
delete string;
return PR_FALSE;
}
{
{
return PR_TRUE;
}
return PR_FALSE;
}
{
if (-1 < index)
{
return RemoveStringAt(index);
}
return PR_FALSE;
}
{
{
delete string;
return PR_TRUE;
}
return PR_FALSE;
}
void
nsStringArray::Clear(void)
{
while (0 <= --index)
{
delete string;
}
nsVoidArray::Clear();
}
PR_STATIC_CALLBACK(int)
{
}
void nsStringArray::Sort(void)
{
}
{
}
{
if (mImpl)
{
{
}
}
return running;
}
{
if (mImpl)
{
{
}
}
return running;
}
//----------------------------------------------------------------
// nsCStringArray
nsCStringArray::nsCStringArray(void)
: nsVoidArray()
{
}
// Parses a given string using the delimiter passed in and appends items
// parsed to the array.
void
{
char *newStr;
while (token) {
if (*token) {
/* calling AppendElement(void*) to avoid extra nsCString copy */
}
}
}
}
{
}
nsCStringArray::~nsCStringArray(void)
{
Clear();
}
{
// Copy the pointers
nsVoidArray::operator=(other);
// Now copy the strings
{
}
return *this;
}
void
{
{
}
else
{
}
}
{
}
{
if (mImpl)
{
{
{
}
ap++;
}
}
return -1;
}
{
if (mImpl)
{
{
{
}
ap++;
}
}
return -1;
}
{
{
return PR_TRUE;
}
delete string;
return PR_FALSE;
}
{
{
return PR_TRUE;
}
return PR_FALSE;
}
{
if (-1 < index)
{
return RemoveCStringAt(index);
}
return PR_FALSE;
}
{
if (-1 < index)
{
return RemoveCStringAt(index);
}
return PR_FALSE;
}
{
{
delete string;
return PR_TRUE;
}
return PR_FALSE;
}
void
nsCStringArray::Clear(void)
{
while (0 <= --index)
{
delete string;
}
nsVoidArray::Clear();
}
PR_STATIC_CALLBACK(int)
{
}
PR_STATIC_CALLBACK(int)
{
}
void nsCStringArray::Sort(void)
{
}
void nsCStringArray::SortIgnoreCase(void)
{
}
{
}
{
if (mImpl)
{
{
}
}
return running;
}
{
if (mImpl)
{
{
}
}
return running;
}
//----------------------------------------------------------------------
// NOTE: nsSmallVoidArray elements MUST all have the low bit as 0.
// This means that normally it's only used for pointers, and in particular
// structures or objects.
{
}
{
if (HasVector())
{
delete vector;
}
}
{
if (HasVector())
{
{
// if both are real arrays, just use array= */
*ourArray = *otherArray;
}
else
{
// we have an array, but the other doesn't.
if (otherArray)
*ourArray = *otherArray;
}
}
else
{
{
// we have no array, but other does
ourArray = SwitchToVector();
if (ourArray)
*ourArray = *otherArray;
}
else
{
// neither has an array (either may have 0 or 1 items)
}
}
return *this;
}
nsSmallVoidArray::GetArraySize() const
{
if (vector)
return vector->GetArraySize();
return 1;
}
nsSmallVoidArray::Count() const
{
if (HasSingleChild())
{
return 1;
}
else {
if (vector)
}
return 0;
}
void*
{
if (HasSingleChild())
{
if (0 == aIndex)
return (void*)GetSingleChild();
}
else
{
if (vector)
}
return nsnull;
}
{
if (HasSingleChild())
{
if (aPossibleElement == (void*)GetSingleChild())
return 0;
}
else
{
if (vector)
}
return -1;
}
{
NS_ASSERTION(!(PtrBits(aElement) & 0x1),"Attempt to add element with 0x1 bit set to nsSmallVoidArray");
if (HasSingleChild())
{
vector = SwitchToVector();
}
else
{
vector = GetChildVector();
if (!vector)
{
if (0 == aIndex)
{
return PR_TRUE;
}
return PR_FALSE;
}
}
}
{
if (count == 0)
return PR_TRUE;
#ifdef DEBUG
for (int i = 0; i < count; i++)
{
NS_ASSERTION(!(PtrBits(other.ElementAt(i)) & 0x1),"Attempt to add element with 0x1 bit set to nsSmallVoidArray");
}
#endif
if (!HasVector())
{
{
vector = SwitchToVector();
}
else
{
// count == 1, aIndex == 0, no elements already
SetSingleChild(other[0]);
return PR_TRUE;
}
}
else
{
vector = GetChildVector();
}
if (vector)
{
}
return PR_TRUE;
}
{
NS_ASSERTION(!(PtrBits(aElement) & 0x1),"Attempt to add element with 0x1 bit set to nsSmallVoidArray");
if (HasSingleChild())
{
if (aIndex == 0)
{
return PR_TRUE;
}
return PR_FALSE;
}
else
{
if (vector)
return PR_FALSE;
}
}
{
NS_ASSERTION(!(PtrBits(aElement) & 0x1),"Attempt to add element with 0x1 bit set to nsSmallVoidArray");
if (HasSingleChild())
{
vector = SwitchToVector();
}
else
{
vector = GetChildVector();
if (!vector)
{
return PR_TRUE;
}
}
}
{
if (HasSingleChild())
{
if (aElement == GetSingleChild())
{
return PR_TRUE;
}
}
else
{
if (vector)
}
return PR_FALSE;
}
{
if (HasSingleChild())
{
if (0 == aIndex)
{
return PR_TRUE;
}
}
else
{
if (vector)
{
}
}
return PR_FALSE;
}
{
if (aCount == 0)
return PR_TRUE;
if (HasSingleChild())
{
if (aIndex == 0)
return PR_TRUE;
}
if (!vector)
return PR_TRUE;
// complex case; remove entries from an array
}
void
{
if (HasVector())
{
}
else
{
}
}
{
if (!HasVector())
{
if (aMin <= 1)
return PR_TRUE;
vector = SwitchToVector();
}
else
{
vector = GetChildVector();
if (aMin <= 1)
{
{
}
delete vector;
return PR_TRUE;
}
}
}
void
{
if (!HasSingleChild())
{
if (vector)
}
}
void
{
if (HasVector())
{
}
}
{
if (HasVector())
{
}
if (HasSingleChild())
{
}
return PR_TRUE;
}
{
if (HasVector())
{
}
if (HasSingleChild())
{
}
return PR_TRUE;
}
void
{
if (aChild)
else
}
{
void* child = GetSingleChild();
mChildren = (void*)new nsAutoVoidArray();
return vector;
}