dynarr.h

#pragma message("touching: "__FILE__)
#include "common.h"
#include <string.h>
#include <assert.h>
#include <math.h>

//#define MAXSEG 5
//#define DYNARR_DATA_TYPE int
//#define TYPED_NAME(name) TOKEN_PASTE(DYNARR_DATA_TYPE, name)
/*	Assuming MAXSEG is defined.
	Size of each block of the dynamic array.
	Must be a positive integer.*/
/*	Assuming DYNARR_DATA_TYPE is defined.
	The data type of the array. 
	Must be a valid one-word type without space, *, etc. (use typedef if necessary) 
	*/
#ifndef MAXSEG
// #pragma message("MAXSEG must be defined before including " __FILE__)
// must be pow of 2
#define MAXSEG 1024
#elif MAXSEG <= 0
#pragma message("MAXSEG has non positive value: " MAXSEG)
#elif !defined(DYNARR_DATA_TYPE)
#pragma message("DYNARR_DATA_TYPE must be defined before including " __FILE__)
#endif


// everything is fine
#ifndef __dynarr_only_once__
#define __dynarr_only_once__


// the struct FreeSegNode will be used multiple times, so we do not want to redefine it
struct FreeSegNode{
	int index;
	struct FreeSegNode* next;
};
typedef struct FreeSegNode FreeSegNode;



#define _FreeSegNodeMalloc() \
	( (struct FreeSegNode*) malloc(sizeof(struct FreeSegNode)) )
// Swaps two 32-bit intergers without using temporary variables
#define	_SEG_ARR_INT_SWAP(var1, var2)	(\
	(var1)	= (FreeSegNode*) (((int) (void*) var1) ^ ((int) (void*) var2) ),	\
	(var2)	= (FreeSegNode*) (((int) (void*) var1) ^ ((int) (void*) var2) ),	\
	(var1)	= (FreeSegNode*) (((int) (void*) var1) ^ ((int) (void*) var2) )	)
// Given two lists A and B, moves the head of A in front of the
// head of B. Head of A must be non-null.
//
// Before:
//		A-->1-2-3-4-5
//		B-->a-b-c-d-e
// After:
//		A-->2-3-4-5
//		B-->1-a-b-c-d-e
//
#define _SEG_ARR_MOVE_LIST_HEAD(listFrom, listTo)	(\
		_SEG_ARR_INT_SWAP( listFrom->next, listTo), \
		_SEG_ARR_INT_SWAP( listFrom, listTo )	\
	)

#ifndef TYPED_NAME
// prefix the name with the type
#define TYPED_NAME(type, name ) TOKEN_PASTE(type, name)
#endif

#if defined(_MSC_VER)

// inlining
#define INLINE _inline /* use _inline (VC++ specific) */
// #define INLINE __forceinline /* use __forceinline (VC++ specific) */
//#elif __GNUC__ && !__GNUC_STDC_INLINE__
//#define INLINE inline
#else
#define INLINE inline        /* use standard inline */
#endif

#endif // __dynarr_only_once__




/* The segment structure. These are the nodes of the linked list */
#define DYNARR_SEG_TYPE(type)	TYPED_NAME(type, Sseg)
typedef struct {
	int index; // my position
	int nextIndex; // next node's position
	DYNARR_DATA_TYPE data;
}DYNARR_SEG_TYPE(DYNARR_DATA_TYPE);

// true if the index is 0
#define DYNARR_SEG_NULL(value_seg) ( (value_seg).index == EMPTY_INDEX ) 
#define DYNARR_SEG_NOT_NULL(value_seg) ( (value_seg).index != EMPTY_INDEX ) 
#define MAKE_DYNARR_SEG_NULL(value_seg) ( (value_seg).index = EMPTY_INDEX ) 


/* The dynamic array data structure */
#define DYNARR_STATE(type)	TYPED_NAME(type, DynArr)
typedef struct{
	////////// basics //////////
	//unsigned int		MaxSeg;		
	/*	Base-2 log */
	unsigned int		LogMaxSeg; 
	/* MAXSEG-1; MAXSEG must be a power of 2 */
	unsigned int		MaxSegRemainderBitMask;	

	DYNARR_SEG_TYPE(DYNARR_DATA_TYPE)* pSegArr;
	//real_t* pSegNextArr;
	int iInsertPos;
	/////////////////// Free nodes list ////////////////
	struct FreeSegNode	*pFreeSegList, *pFreeSegInvalidList;
	int iSizeOfFreeSegList;
	struct FreeSegNode* pTempFreeNode1, *pTempFreeNode2;
	////////////// temporaries //////////////
	int iTempIndex1, iTempIndex2;
	DYNARR_SEG_TYPE(DYNARR_DATA_TYPE) tempSeg1;
	DYNARR_SEG_TYPE(DYNARR_DATA_TYPE) emptySeg;
	//////////// Segment banks ////////////
	DYNARR_SEG_TYPE(DYNARR_DATA_TYPE)** pSegBanksArr;
	int* pSegBankSizeArr;
	int* pSegBankIndexLimitArr;
	int NumSegBanks;
	int MaxSegBanks;
	int	SegBankAllocViolation;

} DYNARR_STATE(DYNARR_DATA_TYPE);
#pragma message(TO_STRING(DYNARR_STATE(DYNARR_DATA_TYPE)))
// dynarr variable name; contains all state variables
#define DYNARR_VARS(type)			TYPED_NAME(type, Vars)

// create a global dynarr struct containing all state variables for given type
#define SEG_ARR_CREATE(type) \
	DYNARR_STATE(type) DYNARR_VARS(type);

// use the global dynarr struct containing all state variables for given type
#define SEG_ARR_USE(type) \
	extern SEG_ARR_CREATE(type);

/* Declare state variables to be used by functions below */
SEG_ARR_USE(DYNARR_DATA_TYPE);


/* Shortcuts to important variables */
#define LOGMAXSEG(type)						MEMBER(DYNARR_VARS(type),.,LogMaxSeg)
#pragma message(TO_STRING(LOGMAXSEG(DYNARR_DATA_TYPE)))
#define MAXSEG_REMAINDER_BITMASK(type)		MEMBER(DYNARR_VARS(type),.,MaxSegRemainderBitMask)
#pragma message(TO_STRING(MAXSEG_REMAINDER_BITMASK(DYNARR_DATA_TYPE)))
#define SEG_ARR(type)						MEMBER(DYNARR_VARS(type),.,pSegArr)
#pragma message(TO_STRING(SEG_ARR(DYNARR_DATA_TYPE)))
#define SEG_INSERT_POS(type)				MEMBER(DYNARR_VARS(type),.,iInsertPos)
#pragma message(TO_STRING(SEG_INSERT_POS(DYNARR_DATA_TYPE)))
#define FREESEG_LIST(type)				MEMBER(DYNARR_VARS(type),.,pFreeSegList)
#pragma message(TO_STRING(FREESEG_LIST(DYNARR_DATA_TYPE)))
#define FREESEG_INVALID_LIST(type)		MEMBER(DYNARR_VARS(type),.,pFreeSegInvalidList)
#pragma message(TO_STRING(FREESEG_INVALID_LIST(DYNARR_DATA_TYPE)))
#define FREESEG_LIST_SIZE(type)			DYNARR_VARS(type).iSizeOfFreeSegList
#pragma message(TO_STRING(FREESEG_LIST_SIZE(DYNARR_DATA_TYPE)))
#define TEMP_FREESEGNODE_1(type)			DYNARR_VARS(type).pTempFreeNode1
#pragma message(TO_STRING(TEMP_FREESEGNODE_1(DYNARR_DATA_TYPE)))
#define TEMP_FREESEGNODE_2(type)			DYNARR_VARS(type).pTempFreeNode2
#pragma message(TO_STRING(TEMP_FREESEGNODE_2(DYNARR_DATA_TYPE)))
#define TEMP_INDEX_1(type)				MEMBER(DYNARR_VARS(type),.,iTempIndex1)
#pragma message(TO_STRING(TEMP_INDEX_1(DYNARR_DATA_TYPE)))
#define TEMP_INDEX_2(type)				MEMBER(DYNARR_VARS(type),.,iTempIndex2)
#pragma message(TO_STRING(TEMP_INDEX_2(DYNARR_DATA_TYPE)))
#define TEMP_SEG_1(type)					DYNARR_VARS(type).iTempIndex1
#pragma message(TO_STRING(TEMP_SEG_1(DYNARR_DATA_TYPE)))
#define NULL_SEG(type)					DYNARR_VARS(type).emptySeg
#pragma message(TO_STRING(SEG_INSERT_POS(DYNARR_DATA_TYPE)))
#pragma message(TO_STRING(SEG_INSERT_POS(DYNARR_DATA_TYPE)))
#define SEG_BANK_ALLOC_VIOLATION(type)	DYNARR_VARS(type).SegBankAllocViolation
#pragma message(TO_STRING(SEG_INSERT_POS(DYNARR_DATA_TYPE)))
// maximum number of segment banks
// this should be a very big number
// this number should never be reached
#define MAX_SEG_BANKS(type)		MEMBER(DYNARR_VARS(type),.,MaxSegBanks)

// array containing size (# of segments) of each segment bank
#define SEG_BANK_SIZE_ARR(type)	MEMBER(DYNARR_VARS(type),.,pSegBankSizeArr)

// array containing last valid index of each segment bank
#define SEG_BANK_INDEX_LIMIT_ARR(type)	MEMBER(DYNARR_VARS(type),.,pSegBankIndexLimitArr)

// Number of active segment banks
#define NUM_SEG_BANKS(type)		MEMBER(DYNARR_VARS(type),.,NumSegBanks)
#define CURRENT_SEG_BANK(type)	(NUM_SEG_BANKS(type) - 1)
// actual segment banks
#define SEG_BANKS_ARR(type)		MEMBER(DYNARR_VARS(type),.,pSegBanksArr)



// external declarations for allocating/resizing blocks
#define SEG_ARR_ALLOC_NEXT_FUNC(type)			TYPED_NAME(type, _seg_bank_alloc_next)
#define SEG_ARR_INC_MAX_FUNC(type)				TYPED_NAME(type, _seg_bank_increase_max)
// early declarations
extern int SEG_ARR_ALLOC_NEXT_FUNC(DYNARR_DATA_TYPE)();
extern int SEG_ARR_INC_MAX_FUNC(DYNARR_DATA_TYPE)();


#define EMPTY_INDEX		0
#define EMPTY_BYTE		0
#define SEG_INSERT_POS_BEGIN	1

// segment banks
#if _REGION_


// coordinates in the 2-D segment allocation
#define BANK_INDEX_FROM_SEG_INDEX(type, index)	\
	( ((unsigned int)(index)) >> LOG_MAXSEG(type) )

#define BANK_FROM_SEG_INDEX(type, index)	SEG_BANKS_ARR[BANK_INDEX_FROM_SEG_INDEX(type, index)]
#define SLOT_FROM_SEG_INDEX(type, index)	(((unsigned int)(index)) & MAXSEG_REMAINDER_BITMASK(type))

// pointer to the segment
#define PTR_SEG_FROM_INDEX(type, index)	\
	(BANK_FROM_SEG_INDEX(type, index) + SLOT_FROM_SEG_INDEX(type, index) )
#endif

// Free segment list methods
#if _REGION_

// returns index
#define _SEG_ARR_FREE_LIST_ADD_VALIDLIST(type, value_seg) (\
	(!FREESEG_LIST(type))\
	?(\
		FREESEG_LIST(type) = _FreeSegNodeMalloc(), \
		/*assert(FREESEG_LIST(type) != NULL );*/ \
			FREESEG_LIST(type)->next = NULL, \
			FREESEG_LIST(type)->index = ((value_seg).index) \
	) : (\
		TEMP_FREESEGNODE_1(type) = _FreeSegNodeMalloc(), \
		/*assert(pTempFreeNode1 != NULL );*/ \
		TEMP_FREESEGNODE_1(type)->next = FREESEG_LIST(type); \
		FREESEG_LIST(type) = TEMP_FREESEGNODE_1(type); \
		FREESEG_LIST(type)->index = ((value_seg).index) \
	) \
	)

// Algorithm:
// If (an invalid node exists) Then
//		move it to the front of valid list
//		set its index as the index of value_seg
// Else
//		Allocate new node in the valid list
//
#define _SEG_ARR_FREE_LIST_ADD(type, value_seg) (\
	( FREESEG_INVALID_LIST(type) )	\
	? (	\
		_SEG_ARR_MOVE_LIST_HEAD( FREESEG_INVALID_LIST(type), FREESEG_LIST(type) ), \
		FREESEG_LIST(type)->index = ((value_seg).index) \
		)	\
	: ( _SEG_ARR_FREE_LIST_ADD_VALIDLIST_FUNC(type)(value_seg) )	\
	)


#define _SEG_ARR_REMOVE_LIST_HEAD(type, list) (\
		TEMP_FREESEGNODE_1(type) = list, \
		list = list->next, \
		FREE_SAFE( TEMP_FREESEGNODE_1(type) ) )\

// Algorithm:
// If (a valid node exists) Then
//		output its index, and
//		move it to the front of invalid list
// Else
//		output null index
//
#define _SEG_ARR_FREE_LIST_GRAB_INDEX(type, value_seg)	(\
	( FREESEG_LIST(type) ) ?(\
		(value_seg).index = FREESEG_LIST(type)->index, \
		(value_seg).nextIndex = EMPTY_INDEX, \
		_SEG_ARR_MOVE_LIST_HEAD( type, FREESEG_LIST(type), FREESEG_INVALID_LIST(type) ), \
		(value_seg)	\
	):(\
		MAKE_DYNARR_SEG_NULL(value_seg), \
		(value_seg)	\
	) )\


#define _SEG_ARR_FREE_LIST_CLEANUP(type) {\
	while( FREESEG_LIST(type) ) {\
		_SEG_ARR_REMOVE_LIST_HEAD(type, FREESEG_LIST(type)); \
	} \
	while( FREESEG_INVALID_LIST(type) ) {\
		_SEG_ARR_REMOVE_LIST_HEAD(type, FREESEG_INVALID_LIST(type)); \
	} \
} \

#endif


/* DynArr methods*/
#if _REGION_

// SEG_ARR_USE() and SEG_ARR_CREATE() has already been defined

// initialize all state variables in the global dynarr struct for given type
#define SEG_ARR_INIT(type) \
	/*MaxSeg should be already assigned	*/	\
	assert(MAXSEG > 0 );	\
	LOGMAXSEG(type) = (unsigned int) (log(MAXSEG+0.0f)/log(2.0f)); \
	MAXSEG_REMAINDER_BITMASK(type) = (unsigned int) (MAXSEG - 1);	\
	NULL_SEG(type).index = NULL_SEG(type).nextIndex = EMPTY_INDEX; \
	/* seg-arr management */	\
	SEG_ARR(type) = ( DYNARR_SEG_TYPE(type) *) malloc( sizeof(DYNARR_SEG_TYPE(type) ) * MAXSEG ); \
	assert(SEG_ARR(type) != NULL ); \
	memset(SEG_ARR(type),	0, sizeof(DYNARR_SEG_TYPE(type)) * MAXSEG ); \
	SEG_INSERT_POS(type) = SEG_INSERT_POS_BEGIN; \
	/*------------------------------------*/ \
	/* multiple segment banks */	\
	/* In test mode, do not initalize MaxSegBanks here so that */ \
	/* it can be initialized by other code before calling SEG_BANKS_INIT()	*/	\
	/*if (!TestEnabled) MAX_SEG_BANKS(type) = 1;	*/ \
	NUM_SEG_BANKS(type) = 1; /* Default value */	\
	MAX_SEG_BANKS(type) = 1; /* Default value */	\
	SEG_BANK_ALLOC_VIOLATION(type) = 0;	\
	/* segment banks*/ \
	SEG_BANKS_ARR(type) = (DYNARR_SEG_TYPE(type)**)malloc(MAX_SEG_BANKS(type) * sizeof(DYNARR_SEG_TYPE(type)*));	\
	memset(SEG_BANKS_ARR(type), 0, MAX_SEG_BANKS(type) * sizeof(DYNARR_SEG_TYPE(type)*));	\
	/* segment bank sizes*/ \
	SEG_BANK_SIZE_ARR(type) = (int*)malloc(MAX_SEG_BANKS(type) * sizeof(int));	\
	memset(SEG_BANK_SIZE_ARR(type), 0, MAX_SEG_BANKS(type) * sizeof(int));	\
	/* segment bank index limits */ \
	SEG_BANK_INDEX_LIMIT_ARR(type) = (int*)malloc(MAX_SEG_BANKS(type) * sizeof(int));	\
	memset(SEG_BANK_INDEX_LIMIT_ARR(type), 0, MAX_SEG_BANKS(type) * sizeof(int));	\
	/* first segment bacnk already allocated */ \
	SEG_BANKS_ARR(type)[0] = SEG_ARR(type);	\
	SEG_BANK_SIZE_ARR(type)[0] = MAXSEG;	\
	SEG_BANK_INDEX_LIMIT_ARR(type)[0] = MAXSEG - 1; \
	NUM_SEG_BANKS(type) = 1;


// cleanup all state variables in the global dynarr struct for given type
#define SEG_ARR_CLEANUP(type) \
	FREE_SAFE( SEG_ARR(type) ); \
	SEG_INSERT_POS(type) = SEG_INSERT_POS_BEGIN; \
	/*-------------------------------*/ \
	/* multiple segment banks */	\
	for(TEMP_INDEX_1(type) = 1; TEMP_INDEX_1(type) < NUM_SEG_BANKS(type); TEMP_INDEX_1(type)++){	\
		FREE_SAFE(SEG_BANKS_ARR(type)[TEMP_INDEX_1(type)]);	\
	}	\
	FREE_SAFE(SEG_BANKS_ARR(type));	\
	FREE_SAFE(SEG_BANK_SIZE_ARR(type));	\
	FREE_SAFE(SEG_BANK_INDEX_LIMIT_ARR(type));	\
	SEG_BANK_ALLOC_VIOLATION(type) = 0; \
	_SEG_ARR_FREE_LIST_CLEANUP(type); \

#endif // _REGION

//#define SEG_ARR_EXISTS()	( pSegArr != NULL )
//#define SEG_ARR_SIZE		NUM_SEG_ARR_ITEMS

#define SEG_ARR_SEG_NEXT_INDEX(type, value_seg) (PTR_SEG_FROM_INDEX(type, (value_seg).index)->nextIndex)
// segment allocation/free/access
#if 1 //_REGION_
/* Accessor methods */
#define SEG_ARR_GET_SEG(type, segIndex)	\
	(	(segIndex)	!= EMPTY_INDEX && \
		(segIndex)  >= 0 && \
		(segIndex)	< SEG_INSERT_POS(type) )\
	? (	(TEMP_SEG_1(type)).index = (segIndex),\
		TEMP_SEG_1(type).nextIndex = \
			(int) (SEG_ARR_SEG_NEXT_INDEX(type, TEMP_SEG_1(type))),\
		TEMP_SEG_1(type))\
	: NULL_SEG(type)

#define SEG_ARR_FREE_SET(type, value_seg)		\
	(	_SEG_ARR_FREE_LIST_ADD(type, (value_seg)), \
		/*TOTALSEGS_DECR(),	*/\
		SEG_ARR_SEG_NEXT_INDEX(type, (value_seg)) = EMPTY_INDEX,	\
		(value_seg).index = (value_seg).nextIndex = EMPTY_INDEX	\
	)

#define SEG_ARR_FREE_GET(type, value_seg)		(\
		_SEG_ARR_FREE_LIST_GRAB_INDEX(type, (value_seg)), \
		(value_seg)		\
	)

// should return NULL_SEG if alloc fails
#define SEG_ARR_ALLOC_SEG(type, value_seg) (\
		(SEG_BANK_ALLOC_VIOLATION(type)) \
		? ((value_seg).index = (value_seg).nextIndex = EMPTY_INDEX, (value_seg) ) \
		: (	\
			(value_seg).index = SEG_INSERT_POS(type), \
			(value_seg).nextIndex = EMPTY_INDEX, \
			(SEG_INSERT_POS(type) >= SEG_BANK_INDEX_LIMIT_ARR(type)[NUM_SEG_BANKS(type)-1]) \
				? /* last index filled. allocate more banks. */ \
					SEG_ARR_ALLOC_NEXT_FUNC(type)	\
					? /* ok */	(void) 0	\
					: /* further alloc not possible */ (\
						SEG_BANK_ALLOC_VIOLATION(type) = 1, \
						printf("\nFatal error: No more segment allocation possible."	\
								"\n\tSegment index: %d, Last possible index: %d "	\
								"NumSegBanks: %d, MaxSegBanks: %d "	\
								"\n\tFile: %s\n\tLine: %d\n", \
								SEG_INSERT_POS(type), SEG_BANK_INDEX_LIMIT_ARR(type)[CURRENT_SEG_BANK(type)], \
								NUM_SEG_BANKS(type), MAX_SEG_BANKS(type),	\
								__FILE__, __LINE__)	\
				)	\
				: /* last index not filled */ SEG_INSERT_POS(type)++,	\
			(value_seg)\
		)	\
	) \

#endif // _REGION_


/*---------------------------------------*/
/*------- Seg banks methods -------------*/


// when maximum number of segment banks is reached,
// double MaxSegBanks and
// reallocate the bookkeeping machinery
// returns 0 if bad, 1 if ok
static INLINE int SEG_ARR_INC_MAX_FUNC(DYNARR_DATA_TYPE)(){
		 void* pVoid;
		 int bSuccess = 1;
		 int prevMaxSegBanks = MAX_SEG_BANKS(DYNARR_DATA_TYPE);
		 // new limit on number of segment banks
		 MAX_SEG_BANKS(DYNARR_DATA_TYPE) <<= 1;

		 // realloc
		 if (pVoid = realloc(SEG_BANKS_ARR(DYNARR_DATA_TYPE), MAX_SEG_BANKS(DYNARR_DATA_TYPE) * sizeof(DYNARR_SEG_TYPE(DYNARR_DATA_TYPE)*))){
			 SEG_BANKS_ARR(DYNARR_DATA_TYPE) = (DYNARR_SEG_TYPE(DYNARR_DATA_TYPE)**)pVoid;
			 memset(SEG_BANKS_ARR(DYNARR_DATA_TYPE) + prevMaxSegBanks, 0, 
				 (MAX_SEG_BANKS(DYNARR_DATA_TYPE) - prevMaxSegBanks) * sizeof(DYNARR_SEG_TYPE(DYNARR_DATA_TYPE)*));
		 }
		 else {
			 printf("\nFatal error: Failed to increase the Maximum number of segment banks."
				 "\n\tFile: %s\n\tLine: %d\n",
				 __FILE__, __LINE__);
			 return 0;
		 }

		 if (pVoid = realloc(SEG_BANK_SIZE_ARR(DYNARR_DATA_TYPE), MAX_SEG_BANKS(DYNARR_DATA_TYPE) * sizeof(int))){
			 SEG_BANK_SIZE_ARR(DYNARR_DATA_TYPE) = (int*)pVoid;
			 memset(SEG_BANK_SIZE_ARR(DYNARR_DATA_TYPE) + prevMaxSegBanks, 0, 
				 (MAX_SEG_BANKS(DYNARR_DATA_TYPE) - prevMaxSegBanks) * sizeof(int));
		 }
		 else {
			 printf("\nFatal error: Failed to increase the Maximum number of segment banks."
				 "\n\tFile: %s\n\tLine: %d\n",
				 __FILE__, __LINE__);
			 return 0;
		 }

		 if (pVoid = realloc(SEG_BANK_INDEX_LIMIT_ARR(DYNARR_DATA_TYPE), MAX_SEG_BANKS(DYNARR_DATA_TYPE) * sizeof(int))){
			 SEG_BANK_INDEX_LIMIT_ARR(DYNARR_DATA_TYPE) = (int*)pVoid;
			 memset(SEG_BANK_INDEX_LIMIT_ARR(DYNARR_DATA_TYPE) + prevMaxSegBanks, 0, 
				 (MAX_SEG_BANKS(DYNARR_DATA_TYPE) - prevMaxSegBanks) * sizeof(int));
		 }
		 else {
			 printf("\nFatal error: Failed to increase the Maximum number of segment banks."
				 "\n\tFile: %s\n\tLine: %d\n",
				 __FILE__, __LINE__);
			 return 0;
		 }

		 // ok
		 return 1;
	 }

//
// allocate next segment bank and place iInsertPos in appropriate value
//
static INLINE int SEG_ARR_ALLOC_NEXT_FUNC(DYNARR_DATA_TYPE)(){
	// shall we also alloc gpu with cpu?
	int bAllocGpu = 0;

	int numElems = MAXSEG,
		round = 0,
		iHypotheticalTotalSegsUptoLastActiveBank = 0;
	DYNARR_SEG_TYPE(DYNARR_DATA_TYPE)* ptr;
	int bCpuGpuAllocDone = 0;

	//assert(NumSegBanks < MAX_SEG_BANKS);
	if (NUM_SEG_BANKS(DYNARR_DATA_TYPE) >= MAX_SEG_BANKS(DYNARR_DATA_TYPE)) {
		// increase limit on the number of segment banks
		if (!SEG_ARR_ALLOC_NEXT_FUNC(DYNARR_DATA_TYPE)()){
			// no futher alloc possible
			SEG_BANK_ALLOC_VIOLATION(DYNARR_DATA_TYPE) = 1;

			printf("\nFatal error: Maximum number of segment banks is reached."
				"\n\tFile: %s\n\tLine: %d\n",
				__FILE__, __LINE__);
			return 0;
		}
		else{
			// great, it is possible to have more segment banks
			// continue
		}
	}

	// ok, lets try to allocate one more segment bank
	do{
		// cpu alloc
		do{
			numElems >>= (round++);
			assert(numElems % 4 == 0); // must be a multiple of 4

			ptr = (DYNARR_SEG_TYPE(DYNARR_DATA_TYPE)*)malloc(numElems *  sizeof(DYNARR_SEG_TYPE(DYNARR_DATA_TYPE)));
		} while (numElems > 1 && ptr == NULL);
		assert(ptr != NULL);
		if (ptr == NULL){
			// no futher alloc possible
			SEG_BANK_ALLOC_VIOLATION(DYNARR_DATA_TYPE) = 1;

			printf("\nFatal error: Failed to allocate next segment bank"
				"\n\tFile: %s\n\tLine: %d\n", __FILE__, __LINE__);
			return 0;
		}

		// ok in cpu
		SEG_BANKS_ARR(DYNARR_DATA_TYPE)[NUM_SEG_BANKS(DYNARR_DATA_TYPE)] = ptr;

		// update the size of the bank
		// it is used when allocating bank in gpu
		SEG_BANK_SIZE_ARR(DYNARR_DATA_TYPE)[NUM_SEG_BANKS(DYNARR_DATA_TYPE)] = numElems;

		// now allocate corresponding bank in gpu
		bCpuGpuAllocDone = 1;
	} while (bCpuGpuAllocDone == 0);

	// great
	// initialize everything to zero, this makes all segments initially null
	memset(ptr, 0, numElems * sizeof(DYNARR_SEG_TYPE(DYNARR_DATA_TYPE)));
	iHypotheticalTotalSegsUptoLastActiveBank = NUM_SEG_BANKS(DYNARR_DATA_TYPE) * MAXSEG;
	// pretend that each segment bank is of size MaxSeg
	SEG_BANK_INDEX_LIMIT_ARR(DYNARR_DATA_TYPE)[NUM_SEG_BANKS(DYNARR_DATA_TYPE)] = (iHypotheticalTotalSegsUptoLastActiveBank - 1) + numElems;

	// finally
	SEG_INSERT_POS(DYNARR_DATA_TYPE) = iHypotheticalTotalSegsUptoLastActiveBank;
	NUM_SEG_BANKS(DYNARR_DATA_TYPE)++;

	return 1;
}

// done