diff options
author | warren%netscape.com <devnull@localhost> | 1998-07-28 02:07:17 +0000 |
---|---|---|
committer | warren%netscape.com <devnull@localhost> | 1998-07-28 02:07:17 +0000 |
commit | a96e71027ecfd1fbaabb375e89e1ccca640c6cf6 (patch) | |
tree | ae08ac844c47233bf9c8ab14622743beeee14b55 | |
parent | 4a964862b78d579e7868cc85e5e07e41ded9e026 (diff) | |
download | nspr-hg-a96e71027ecfd1fbaabb375e89e1ccca640c6cf6.tar.gz |
Committed from OJI_19980618_TIP_MERGE1.OJI_19980727_BASE
-rw-r--r-- | lib/ds/plvector.c | 318 | ||||
-rw-r--r-- | lib/ds/plvector.h | 100 |
2 files changed, 418 insertions, 0 deletions
diff --git a/lib/ds/plvector.c b/lib/ds/plvector.c new file mode 100644 index 00000000..e37dff40 --- /dev/null +++ b/lib/ds/plvector.c @@ -0,0 +1,318 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* + * The contents of this file are subject to the Netscape Public License + * Version 1.0 (the "NPL"); you may not use this file except in + * compliance with the NPL. You may obtain a copy of the NPL at + * http://www.mozilla.org/NPL/ + * + * Software distributed under the NPL is distributed on an "AS IS" basis, + * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the NPL + * for the specific language governing rights and limitations under the + * NPL. + * + * The Initial Developer of this code under the NPL is Netscape + * Communications Corporation. Portions created by Netscape are + * Copyright (C) 1998 Netscape Communications Corporation. All Rights + * Reserved. + */ + +#include "plvector.h" +#include "prmem.h" +#include <string.h> + +#ifdef XP_WIN16 +#define SIZE_T_MAX 0xFF80 /* a little less than 64K, the max alloc size on win16. */ +#define MAX_ARR_ELEMS SIZE_T_MAX/sizeof(void*) +#endif + +PR_IMPLEMENT(PLVector*) +PL_NewVector(PRUint32 initialSize, PRInt32 initialGrowBy) +{ + PLVector* v = (PLVector*)PR_Malloc(sizeof(PLVector*)); + if (v == NULL) + return NULL; + PL_VectorInitialize(v, initialSize, initialGrowBy); + return v; +} + +PR_IMPLEMENT(void) +PL_VectorDestroy(PLVector* v) +{ + PL_VectorFinalize(v); + PR_Free(v); +} + +/* Initializes an existing vector */ +PR_IMPLEMENT(void) +PL_VectorInitialize(PLVector* v, PRUint32 initialSize, PRInt32 initialGrowBy) +{ + v->data = NULL; + v->size = v->maxSize = v->growBy = 0; + if (initialSize > 0 || initialGrowBy > 0) + PL_VectorSetSize(v, initialSize, initialGrowBy); +} + +/* Destroys the elements, but doesn't free the vector */ +PR_IMPLEMENT(void) +PL_VectorFinalize(PLVector* v) +{ + /* This implementation doesn't do anything to delete the elements + in the vector -- that's up to the caller. (Don't shoot me, + I just copied the code from libmsg.) */ + PR_Free(v->data); +} + +PR_IMPLEMENT(PRBool) +PL_VectorSetSize(PLVector* v, PRUint32 newSize, PRInt32 growBy) +{ + if (growBy != -1) + v->growBy = growBy; /* set new size */ + + if (newSize == 0) { + /* shrink to nothing */ + PR_Free(v->data); + v->data = NULL; + v->size = v->maxSize = 0; + } + else if (v->data == NULL) { + /* create one with exact size */ +#ifdef SIZE_T_MAX + PR_ASSERT(newSize <= SIZE_T_MAX/sizeof(void*)); /* no overflow */ +#endif + v->data = (void**)PR_Malloc(newSize * sizeof(void *)); + if (v->data == NULL) { + v->size = 0; + return PR_FALSE; + } + + memset(v->data, 0, newSize * sizeof(void *)); /* zero fill */ + + v->size = v->maxSize = newSize; + } + else if (newSize <= v->maxSize) { + /* it fits */ + if (newSize > v->size) { + /* initialize the new elements */ + + memset(&v->data[v->size], 0, (newSize-v->size) * sizeof(void *)); + } + v->size = newSize; + } + else { + /* otherwise, grow array */ + PRUint32 newMax; + void** newData; + PRInt32 growBy = v->growBy; + if (growBy == 0) { + /* heuristically determine growth when growBy == 0 + (this avoids heap fragmentation in many situations) */ + growBy = PR_MIN(1024, PR_MAX(4, v->size / 8)); + } +#ifdef MAX_ARR_ELEMS + if (v->size + growBy > MAX_ARR_ELEMS) + growBy = MAX_ARR_ELEMS - v->size; +#endif + if (newSize < v->maxSize + growBy) + newMax = v->maxSize + growBy; /* granularity */ + else + newMax = newSize; /* no slush */ + +#ifdef SIZE_T_MAX + if (newMax >= SIZE_T_MAX/sizeof(void*)) + return PR_FALSE; + PR_ASSERT(newMax <= SIZE_T_MAX/sizeof(void*)); /* no overflow */ +#endif + PR_ASSERT(newMax >= v->maxSize); /* no wrap around */ + newData = (void**)PR_Malloc(newMax * sizeof(void*)); + + if (newData != NULL) { + /* copy new data from old */ + memcpy(newData, v->data, v->size * sizeof(void*)); + + /* construct remaining elements */ + PR_ASSERT(newSize > v->size); + + memset(&newData[v->size], 0, (newSize-v->size) * sizeof(void*)); + + /* get rid of old stuff (note: no destructors called) */ + PR_Free(v->data); + v->data = newData; + v->size = newSize; + v->maxSize = newMax; + } + else { + return PR_FALSE; + } + } + return PR_TRUE; +} + +PR_IMPLEMENT(PRBool) +PL_VectorIsValidIndex(PLVector* v, PRUint32 index) +{ + return (index < v->size) ? PR_TRUE : PR_FALSE; +} + + +PR_IMPLEMENT(void) +PL_VectorCompact(PLVector* v) +{ + if (v->size != v->maxSize) { + /* shrink to desired size */ +#ifdef SIZE_T_MAX + PR_ASSERT(v->size <= SIZE_T_MAX/sizeof(void *)); /* no overflow */ +#endif + void ** newData = NULL; + if (v->size != 0) { + newData = (void **)PR_Malloc(v->size * sizeof(void *)); + /* copy new data from old */ + memcpy(newData, v->data, v->size * sizeof(void *)); + } + + /* get rid of old stuff (note: no destructors called) */ + PR_Free(v->data); + v->data = newData; + v->maxSize = v->size; + } +} + +#if 0 /* becomes Copy */ +PR_IMPLEMENT(void) +PL_VectorSplice(PLVector* v, PRUint32 startIndex, PLVector* newVector) +{ + PRUint32 i; + PR_ASSERT(newVector != NULL); + + if (PL_VectorGetSize(newVector) > 0) { + PL_VectorInsert(v, startIndex, PL_VectorGet(newVector, 0), + PL_VectorGetSize(newVector)); + for (i = 0; i < PL_VectorGetSize(newVector); i++) + PL_VectorSet(v, startIndex + i, PL_VectorGet(newVector, i)); + } +} +#endif + +PR_IMPLEMENT(void) +PL_VectorCopy(PLVector* dstVector, PRUint32 dstPosition, + PLVector* srcVector, PRUint32 srcPosition, PRUint32 length) +{ + PR_ASSERT(0); /* XXX not implemented yet */ +#if 0 + PL_VectorSetSize(dstVector, PR_MAX(PL_VectorGetSize(dstVector), + PL_VectorGetSize(srcVector)), + PL_VECTOR_GROW_DEFAULT); + + if (v->data) + PR_Free(v->data); + v->size = oldA->v->size; + v->maxSize = oldA->v->maxSize; + v->growBy = oldA->v->growBy; + v->data = (void**)PR_Malloc(v->size * sizeof(void *)); + if (v->data == NULL) { + v->size = 0; + } + else { + memcpy(v->data, oldA->v->data, v->size * sizeof(void *)); + } +#endif +} + +PR_IMPLEMENT(PLVector*) +PL_VectorClone(PLVector* v) +{ + PLVector* newVec = PL_NewVector(v->size, v->growBy); + PL_VectorCopy(newVec, 0, v, 0, v->size); + return newVec; +} + +/* Accessing elements */ + +PR_IMPLEMENT(void) +PL_VectorSet(PLVector* v, PRUint32 index, void* newElement) +{ + if (index >= v->size) { + if (!PL_VectorSetSize(v, index+1, PL_VECTOR_GROW_DEFAULT)) + return; + } + v->data[index] = newElement; +} + +/* Adds at the end */ +PR_IMPLEMENT(PRInt32) +PL_VectorAdd(PLVector* v, void* newElement) +{ + PRUint32 index = v->size; +#ifdef XP_WIN16 + if (index >= SIZE_T_MAX / 4L) { + return -1; + } +#endif + PL_VectorSet(v, index, newElement); + return (PRInt32)index; +} + +/* Inserts new element count times at index */ +PR_IMPLEMENT(void) +PL_VectorInsert(PLVector* v, PRUint32 index, void* newElement, PRUint32 count) +{ + PR_ASSERT(count > 0); /* zero or negative size not allowed */ + + if (index >= v->size) { + /* adding after the end of the array */ + if (!PL_VectorSetSize(v, index + count, PL_VECTOR_GROW_DEFAULT)) + return; /* grow so index is valid */ + } + else { + /* inserting in the middle of the array */ + PRUint32 nOldSize = v->size; + if (!PL_VectorSetSize(v, v->size + count, PL_VECTOR_GROW_DEFAULT)) + return; /* grow it to new size */ + /* shift old data up to fill gap */ + memmove(&v->data[index+count], &v->data[index], + (nOldSize-index) * sizeof(void *)); + + /* re-init slots we copied from */ + memset(&v->data[index], 0, count * sizeof(void *)); + } + + /* insert new value in the gap */ + PR_ASSERT(index + count <= v->size); + while (count--) + v->data[index++] = newElement; +} + +/* Removes count elements at index */ +PR_IMPLEMENT(void) +PL_VectorRemove(PLVector* v, PRUint32 index, PRUint32 count) +{ + PRUint32 moveCount; + PR_ASSERT(count >= 0); + PR_ASSERT(index + count <= v->size); + + /* just remove a range */ + moveCount = v->size - (index + count); + + if (moveCount) + memmove(&v->data[index], &v->data[index + count], + moveCount * sizeof(void *)); + v->size -= count; +} + +#ifdef DEBUG + +PR_IMPLEMENT(void) +PL_VectorAssertValid(PLVector* v) +{ + if (v->data == NULL) { + PR_ASSERT(v->size == 0); + PR_ASSERT(v->maxSize == 0); + } + else { + PR_ASSERT(v->size >= 0); + PR_ASSERT(v->maxSize >= 0); + PR_ASSERT(v->size <= v->maxSize); + } +} + +#endif + diff --git a/lib/ds/plvector.h b/lib/ds/plvector.h new file mode 100644 index 00000000..e71a152f --- /dev/null +++ b/lib/ds/plvector.h @@ -0,0 +1,100 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* + * The contents of this file are subject to the Netscape Public License + * Version 1.0 (the "NPL"); you may not use this file except in + * compliance with the NPL. You may obtain a copy of the NPL at + * http://www.mozilla.org/NPL/ + * + * Software distributed under the NPL is distributed on an "AS IS" basis, + * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the NPL + * for the specific language governing rights and limitations under the + * NPL. + * + * The Initial Developer of this code under the NPL is Netscape + * Communications Corporation. Portions created by Netscape are + * Copyright (C) 1998 Netscape Communications Corporation. All Rights + * Reserved. + */ + +#ifndef plvector_h__ +#define plvector_h__ + +#include "prtypes.h" +#include "prlog.h" + +PR_BEGIN_EXTERN_C + +/* Vectors are extensible arrays */ + +typedef struct PLVector { + void** data; /* the actual array of data */ + PRUint32 size; /* # of elements (upperBound - 1) */ + PRUint32 maxSize; /* max allocated */ + PRInt32 growBy; /* grow amount */ +} PLVector; + +PR_EXTERN(PLVector*) +PL_NewVector(PRUint32 initialSize, PRInt32 initialGrowBy); + +PR_EXTERN(void) +PL_VectorDestroy(PLVector* v); + +/* Initializes an existing vector */ +PR_EXTERN(void) +PL_VectorInitialize(PLVector* v, PRUint32 initialSize, PRInt32 initialGrowBy); + +/* Destroys the elements, but doesn't free the vector */ +PR_EXTERN(void) +PL_VectorFinalize(PLVector* v); + +#define PL_VectorGetSize(v) ((v)->size) + +#define PL_VECTOR_GROW_DEFAULT (-1) + +PR_EXTERN(PRBool) +PL_VectorSetSize(PLVector* v, PRUint32 newSize, PRInt32 growBy); + +PR_EXTERN(PRBool) +PL_VectorIsValidIndex(PLVector* v, PRUint32 index); + +PR_EXTERN(void) +PL_VectorCompact(PLVector* v); + +PR_EXTERN(void) +PL_VectorCopy(PLVector* dstVector, PRUint32 dstPosition, + PLVector* srcVector, PRUint32 srcPosition, PRUint32 length); + +PR_EXTERN(PLVector*) +PL_VectorClone(PLVector* v); + +/* Accessing elements */ + +#define PL_VectorGetAddr(v, index) (PR_ASSERT((index) < (v)->size), &(v)->data[index]) + +#define PL_VectorGet(v, index) (*PL_VectorGetAddr(v, index)) + +PR_EXTERN(void) +PL_VectorSet(PLVector* v, PRUint32 index, void* newElement); + +/* Adds at the end */ +PR_EXTERN(PRInt32) +PL_VectorAdd(PLVector* v, void* newElement); + +/* Inserts new element count times at index */ +PR_EXTERN(void) +PL_VectorInsert(PLVector* v, PRUint32 index, void* newElement, PRUint32 count); + +/* Removes count elements at index */ +PR_EXTERN(void) +PL_VectorRemove(PLVector* v, PRUint32 index, PRUint32 count); + +#ifdef DEBUG + +PR_EXTERN(void) +PL_VectorAssertValid(PLVector* v); + +#endif + +PR_END_EXTERN_C + +#endif /* plvector_h__ */ |