# HG changeset patch # User Sean Halle # Date 1374262063 25200 # Node ID 3ed337b6a04f1b0dee05f67fc21f33d208c35a04 # Parent 958dcb7754caf25a52d77224aa3ad4d6c07bfaeb creating version of dyn array that keeps info in prolog instead of 2nd var diff -r 958dcb7754ca -r 3ed337b6a04f DynArray2.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/DynArray2.c Fri Jul 19 12:27:43 2013 -0700 @@ -0,0 +1,158 @@ +/* + * Copyright 2010 OpenSourceCodeStewardshipFoundation + * + * Licensed under BSD + */ + + + +#include +#include + +#include "DynArray.h" + +//== declarations +#define giveInfoFor( array ) &(((PrivDynArrayInfo*)array)[-1]) +//== + +/*This updates the contents of the array variable, by side-effect. There can + * only ever be one variable that holds a pointer to the dyn array, and all + * accesses must use that variable. An add can cause the contents of that + * variable to change! (Meaning the position of the array has moved) + */ +void * +makePrivDynArray2( void ***addrOfArrayVar, int32 numElemsToAllocate, int32 sizeOfElem ) + { PrivDynArrayInfo *info; + int32 bytesInArray = numElemsToAllocate * sizeOfElem; + + info = PR_int__malloc( sizeof(PrivDynArrayInfo) + bytesInArray ); + info->addrOfPtrToArray = addrOfArrayVar; + info->sizeOfArray = numElemsToAllocate; + info->sizeOfElem = sizeOfElem; + info->numInArray = 0; + return &(info[1]); //skip over prolog -- info is prolog + } + + +/*A dynamic array is same as any other array, but add a DynArrayInfo next + * to it. Accesses and updates of array indexes are done normally, it's + * only when add a new element into array that use the extra info. + * An add can cause the pointer to the normal array to change.. so must + * be protected to single VP at a time. + * + *Only need to use this Fn when need a new index, higher than any previous + */ +int32 +addToDynArray2( void *value, void **array ) + { int32 numInArray, sizeOfArray; + PrivDynArrayInfo *info = giveInfoFor(array); //go backward to prolog + + numInArray = info->numInArray; + sizeOfArray = info->sizeOfArray; + + if( numInArray >= sizeOfArray ) + { + array = increaseSizeOfDynArrayTo2( array, sizeOfArray * 2 ); + info = giveInfoFor( array ); + } + + array[ numInArray ] = value; + info->numInArray++; + + return numInArray; //index of last elem is one less than num in array + } + + +/*Sets num in array to exactly value give + *Use this when know how many things going to add in -- then can do this + * once and use as normal array afterwards. If later add another chunk, + * do this again. Note, this makes new size be just big enough to hold + * highest index, so will do a linear number of copies if use only this. + *To cut down on number of copies, can use the increaseSizeTo Fn to + * exponentially increase size.. + */ +void +makeNumInArrayBe2( void **array, int32 numInArray ) + { PrivDynArrayInfo *info = giveInfoFor( array ); + + if( info->sizeOfArray <= numInArray ) + { + array = increaseSizeOfDynArrayTo2( array, numInArray ); + info = giveInfoFor( array ); + } + info->numInArray = numInArray; //num is highest index plus 1 + } + +/*Allows highest index to remain higher than index give*/ +void +makeHighestDynArrayIndexBeAtLeast2( void **array, int32 index) + { PrivDynArrayInfo *info = giveInfoFor( array ); + + if( index < info->numInArray ) return; //num added diff than size + else makeNumInArrayBe2( array, index ); + } + + +/*Only use this if certain new size is bigger than current size + */ +void ** +increaseSizeOfDynArrayTo2( void **oldArray, int32 newSize ) + { int32 oldsizeOfArray, i, numBytesToCopy; + void **newArray; + PrivDynArrayInfo *oldInfo = giveInfoFor( oldArray ); + PrivDynArrayInfo *newInfo; + + oldsizeOfArray = oldInfo->sizeOfArray; + if( newSize <= oldsizeOfArray ) return; + + newInfo = PR_int__malloc( newSize * oldInfo->sizeOfElem + sizeof(PrivDynArrayInfo) ); + newArray = &(newInfo[1]); + + numBytesToCopy = oldInfo->numInArray * oldInfo->sizeOfElem + sizeof(PrivDynArrayInfo); + memcpy( newInfo, oldInfo, numBytesToCopy ); //copies info + array contents + + *(newInfo->addrOfPtrToArray) = newArray; //change contents of array var + newInfo->sizeOfArray = newSize; + + PR_int__free( oldInfo ); + + return newArray; + } + + +/* Frees the array, plus the info + */ +void +freeDynArrayDeep2( void *array, FreeFnPtr freeFnPtr ) + { PrivDynArrayInfo *info = giveInfoFor( array ); + + forAllInDynArrayDo2( array, freeFnPtr ); + PR_int__free( info ); + } + +/* Only frees the info + */ +void +freeDynArrayFlat2( void *array ) + { PrivDynArrayInfo *info = giveInfoFor( array ); + + PR_int__free( info ); + } + + +/*The function has a fixed prototype: takes a void * returns void + * So, the function has to internally cast void * to whatever data struc.. + */ +void +forAllInDynArrayDo2( void *array, DynArrayFnPtr fnPtr ) + { PrivDynArrayInfo *info = giveInfoFor( array ); + int32 idx, sizeOfElem; + void *addrOfElem; + + sizeOfElem = info->sizeOfElem; + for( idx = 0; idx < info->numInArray; idx++ ) + { addrOfElem = ((int8 *)array) + idx * sizeOfElem; + (*fnPtr)( addrOfElem ); + } + } + diff -r 958dcb7754ca -r 3ed337b6a04f DynArray3.c --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/DynArray3.c Fri Jul 19 12:27:43 2013 -0700 @@ -0,0 +1,213 @@ +/* + * Copyright 2010 OpenSourceCodeStewardshipFoundation + * + * Licensed under BSD + */ + + + +#include + +#include "DynArray.h" + +//== declarations +void +increaseSizeOfDynArrayTo_Ext( PtrToPrivDynArray *info, int32 newSize ); +//== + +PtrToPrivDynArray * +makePrivDynArrayInfoFrom( void ***addrOfPtrToArray, int32 sizeOfArray ) + { PtrToPrivDynArray *info; + + info = PR_int__malloc( sizeof(PtrToPrivDynArray) ); + + info->addrOfPtrToArray = addrOfPtrToArray; + info->sizeOfArray = sizeOfArray; + info->numInArray = 0; + return info; + } + +PtrToPrivDynArray * +makePrivDynArrayOfSize( void ***addrOfPtrToArray, int32 sizeOfArray ) + { PtrToPrivDynArray *info; + + info = PR_int__malloc( sizeof(PtrToPrivDynArray) ); + + info->addrOfPtrToArray = addrOfPtrToArray; + + *(addrOfPtrToArray) = PR_int__malloc( sizeOfArray * sizeof(void *) ); + info->sizeOfArray = sizeOfArray; + info->numInArray = 0; + return info; + } + +PtrToPrivDynArray * +makePrivDynArrayOfSize_Ext( void ***addrOfPtrToArray, int32 sizeOfArray ) + { PtrToPrivDynArray *info; + + info = malloc( sizeof(PtrToPrivDynArray) ); + + info->addrOfPtrToArray = addrOfPtrToArray; + + *(addrOfPtrToArray) = malloc( sizeOfArray * sizeof(void *) ); + info->sizeOfArray = sizeOfArray; + info->numInArray = 0; + } + + +/*A dynamic array is same as any other array, but add a DynArrayInfo next + * to it. Accesses and updates of array indexes are done normally, it's + * only when add a new element into array that use the extra info. + * An add can cause the pointer to the normal array to change.. so must + * be protected to single VP at a time. + * + *Only need to use this Fn when need a new index, higher than any previous + */ +int32 +addToDynArray( void *value, PtrToPrivDynArray *info ) + { int32 numInArray, sizeOfArray; + void **array; + + numInArray = info->numInArray; + sizeOfArray = info->sizeOfArray; + + if( numInArray >= sizeOfArray ) + { + increaseSizeOfDynArrayTo( info, sizeOfArray * 2 ); + } + + array = *(info->addrOfPtrToArray); + array[ numInArray ] = value; + info->numInArray++; + + return numInArray; //pre-incr value is the index put value into + } +int32 +addToDynArray_Ext( void *value, PtrToPrivDynArray *ptrToArray ) + { int32 numInArray, sizeOfArray; + void **array; + + numInArray = ptrToArray->numInArray; + sizeOfArray = ptrToArray->sizeOfArray; + + if( numInArray >= sizeOfArray ) + { + increaseSizeOfDynArrayTo_Ext( ptrToArray, sizeOfArray * 2 ); + } + + array = *(ptrToArray->addrOfPtrToArray); + array[ numInArray ] = value; + ptrToArray->numInArray++; + + return numInArray; //pre-incr value is the index put value into + } + + +/*Use this when know how many things going to add in -- then can do this + * once and use as normal array afterwards. If later add another chunk, + * do this again. Note, this makes new size be just big enough to hold + * highest index, so will do a linear number of copies if use only this. + *To cut down on number of copies, can use the increaseSizeTo Fn to + * exponentially increase size.. + */ +void +makeHighestDynArrayIndexBe( PtrToPrivDynArray *info, int32 highestIndex ) + { + if( info->sizeOfArray <= highestIndex ) + { + increaseSizeOfDynArrayTo( info, highestIndex + 1 ); + } + info->numInArray = highestIndex + 1; + } + +void +makeHighestDynArrayIndexBeAtLeast(PtrToPrivDynArray *info, int32 index) + { + if( index < info->numInArray ) return; + else makeHighestDynArrayIndexBe( info, index ); + } + + +/*Only use this if certain new size is bigger than current size + */ +void +increaseSizeOfDynArrayTo( PtrToPrivDynArray *info, int32 newSize ) + { int32 oldSizeOfArray, i; + void **newArray, **oldArray; + + oldSizeOfArray = info->sizeOfArray; + if( newSize <= oldSizeOfArray ) return; + + oldArray = *(info->addrOfPtrToArray); + newArray = PR_int__malloc( newSize * sizeof(void *) ); + + for( i = 0; i < oldSizeOfArray; i++ ) + { + newArray[i] = oldArray[i]; + } + *(info->addrOfPtrToArray) = newArray; //change location of array-ptr + info->sizeOfArray = newSize; + + PR_int__free( oldArray ); + } + +/*Can't mix PR_int__malloc locations with external malloc locations -- so use + * this version inside PR, which will perform normal malloc in the core + * loop -- hopefully avoiding the annoying system-stack bugs.. + */ +void +increaseSizeOfDynArrayTo_Ext( PtrToPrivDynArray *info, int32 newSize ) + { int32 oldSizeOfArray, i; + void **newArray, **oldArray; + + oldSizeOfArray = info->sizeOfArray; + if( newSize <= oldSizeOfArray ) return; + + oldArray = *(info->addrOfPtrToArray); + newArray = malloc( newSize * sizeof(void *) ); + + for( i = 0; i < oldSizeOfArray; i++ ) + { + newArray[i] = oldArray[i]; + } + *(info->addrOfPtrToArray) = newArray; //change location of array-ptr + info->sizeOfArray = newSize; + + free( oldArray ); + } + + +/* Frees the array, plus the info + */ +void +freeDynArrayDeep( PtrToPrivDynArray *info, FreeFnPtr freeFnPtr ) + { + forAllInDynArrayDo( info, freeFnPtr ); + PR_int__free( *(info->addrOfPtrToArray) ); + PR_int__free( info ); + } + +/* Only frees the info + */ +void +freeDynArrayFlat( PtrToPrivDynArray *info ) + { + PR_int__free( info ); + } + + +/*The function has a fixed prototype: takes a void * returns void + * So, the function has to internally cast void * to whatever data struc.. + */ +void +forAllInDynArrayDo( PtrToPrivDynArray *info, DynArrayFnPtr fnPtr ) + { int32 idx; + void **array; + + array = *(info->addrOfPtrToArray); + for( idx = 0; idx < info->numInArray; idx++ ) + { + (*fnPtr)(array[idx]); + } + } + diff -r 958dcb7754ca -r 3ed337b6a04f DynArray3.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/DynArray3.h Fri Jul 19 12:27:43 2013 -0700 @@ -0,0 +1,97 @@ +/* + * File: Vector.h + * Author: Me + * + * Created on May 14, 2010, 3:08 PM + */ + +#ifndef _DYNARRAY_H +#define _DYNARRAY_H + +#include "PR_impl/PR_primitive_data_types.h" +#include "PR_impl/Services_Offered_by_PR/Memory_Handling/vmalloc.h" + + +/*WARNING: Passing a DynArray as a param is dangerous if add to the DynArray + * inside the function called! After adding or other operation that might + * change the size, must re-read the addr of the chunk of memory that is the + * array, via the DynArrayInfo. + *Here's why: An array variable is a location, either on the stack + * or in a field of a struct, whose contents is an addr. That addr is of the + * first location of a chunk of locations. The DynArray works by changing + * the chunk of locations, then modifying the contents of the original + * array variable. It overwrites the addr of the old chunk of locations + * with the addr of the new chunk. + *But when the array variable is passed as a parameter, such as + * in this: "foo( myDynArray )", then there are now two locations that hold + * the addr of the same chunk of locations. So when a call is made that + * adds to the DynArray, and inside the DynArray expands, it only updates + * the original location with the new addr. Hence, the function will begin + * overwriting memory past the end of the old chunk, because it still has + * the pointer to the old chunk of locations. + * + *A dynamic array is accessed same as any other array. However, must use + * dyn array calls, defined in here, in order to add or increase the size. + * Must re-read the original array variable after any size-changing calls. + *To pass a DynArray as a parameter to a function, can only pass the + * DynArrayInfo, then inside the function, to read the addr of the first + * location in the chunk of locations that is the array, do this: + * "localArrayCopy = *(myDynArrayInfo->addrOfPtrToArray). After that, can + * treat localArrayCopy as a normal array, as long as don't make any calls + * that add or otherwise could increase the size of the array. If do make + * such a call, then re-copy the array via the above. Can then use the + * copy up until another add to the array. + * + */ +typedef struct + { + void ***addrOfPtrToArray; //addr of array of ptrs == triple * + int32 numInArray; + int32 sizeOfArray; + } +PrivDynArrayInfo; + + +typedef struct + { + void **ptrToLocations; //must be in first position + int32 numInArray; + int32 sizeOfArray; + } +PrivDynArray; + + +PrivDynArrayInfo * +makePrivDynArrayOfSize( int32 sizeOfArray ); + +PrivDynArrayInfo * +makePrivDynArrayOfSize_Ext( int32 sizeOfArray ); + +int32 +addToDynArray( void *value, void *array ); + +void +makeHighestDynArrayIndexBe( void *array, int32 highestIndex ); + +void +makeHighestDynArrayIndexBeAtLeast( void *array, int32 highestIndex); + +void +increaseSizeOfDynArrayTo( void *array, int32 newSize ); + +typedef void (*FreeFnPtr) ( void * ); //fn has to cast void * to whatever + +void +freeDynArrayDeep( void *array, FreeFnPtr freeFnPtr ); + +void +freeDynArrayFlat( void *array ); + + +typedef void (*DynArrayFnPtr) ( void * ); //fn has to cast void * + +void +forAllInDynArrayDo( void *array, DynArrayFnPtr fnPtr ); + +#endif /* _DYNARRAY_H */ + diff -r 958dcb7754ca -r 3ed337b6a04f __brch__Dev_prolog_vers --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/__brch__Dev_prolog_vers Fri Jul 19 12:27:43 2013 -0700 @@ -0,0 +1,4 @@ +This branch is for the project structure defined Jan 2012.. the #includes reflect this directory structure. + +More importantly, the MC_shared version of PR requires a separat malloc implemeted by PR code.. so this branch has modified the library to use the PR-specific malloc. + diff -r 958dcb7754ca -r 3ed337b6a04f __brch__Renamed_VMS_to_PR --- a/__brch__Renamed_VMS_to_PR Fri Mar 08 05:37:45 2013 -0800 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,4 +0,0 @@ -This branch is for the project structure defined Jan 2012.. the #includes reflect this directory structure. - -More importantly, the MC_shared version of PR requires a separat malloc implemeted by PR code.. so this branch has modified the library to use the PR-specific malloc. -