Hi!

I played a bit with implementing a better memory pool for effects and this is 
what came out.

Sadly it seems to have a bug though. (Segfault)
I reliably can reproduce it by cheating an archangle and just letting it fire. 
Sadly does WZ neither output a crash dump, nor is GDB able to capture a 
backtrace, and it does not crash in Valgrind...
Maybe someone finds an issue by review.

Greetings,
DevU
diff --git a/src/effects.c b/src/effects.c
index 49183f7..c4c68f1 100644
--- a/src/effects.c
+++ b/src/effects.c
@@ -71,8 +71,6 @@
 #include "game.h"
 
 
-#define MAX_EFFECTS	2500
-
 #define	GRAVITON_GRAVITY	((float)-800)
 #define	EFFECT_X_FLIP		0x1
 #define	EFFECT_Y_FLIP		0x2
@@ -165,19 +163,38 @@
 #define	MAX_SHOCKWAVE_SIZE				500
 
 
+#define MAX_EFFECTS 10000
+
+typedef struct _EffectChunk EffectChunk;
+
+struct _EffectChunk {
+	EFFECT effects[MAX_EFFECTS];
+	EffectChunk *next;
+};
+
+struct {
+	EffectChunk *first, *last;
+} chunkList = {
+	NULL, NULL
+};
+
 /* Our list of all game world effects */
-static EFFECT        asEffectsList[MAX_EFFECTS];
-static EFFECT_STATUS effectStatus[MAX_EFFECTS];
+// static size_t numEffects = 10000;
+// static EFFECT *effects = NULL;
+struct {
+	size_t num;
+	EFFECT *first, *last;
+} activeList = {
+	0, NULL, NULL
+}, inactiveList = {
+	0, NULL, NULL
+};
+
 
 /* Tick counts for updates on a particular interval */
 static	UDWORD	lastUpdateDroids[EFFECT_DROID_DIVISION];
 static	UDWORD	lastUpdateStructures[EFFECT_STRUCTURE_DIVISION];
 
-static	UDWORD	freeEffect; /* Current next slot to use - cyclic */
-static	UDWORD	numEffects;
-static	UDWORD	activeEffects;
-static	UDWORD	missCount;
-static	UDWORD	skipped,skippedEffects,letThrough;
 static	UDWORD	auxVar; // dirty filthy hack - don't look for what this does.... //FIXME
 static	UDWORD	auxVarSec; // dirty filthy hack - don't look for what this does.... //FIXME
 static	UDWORD	specifiedSize;
@@ -233,6 +250,131 @@ static void effectDroidUpdates(void);
 static UDWORD effectGetNumFrames(EFFECT *psEffect);
 
 
+static void initEffectPool(EFFECT *first, EFFECT *last)
+{
+	for (EFFECT *it = first; it < last; it++)
+	{
+		 // We do not need a double-linked-list for inactiveeffects, since we always pick from the front:
+		it->prev = NULL;
+		it->next = it+1;
+	}
+
+	last->prev = NULL;
+	last->next = NULL;
+}
+
+
+static EFFECT *Effect_mallocImpl(void)
+{
+	printf("** Allocating effect No. %zd\n", activeList.num);
+
+	EFFECT *instance = inactiveList.first;
+
+	inactiveList.first = instance->next; // Remove from inactiveList (singly linked)
+	instance->next = NULL; // We are the last in activeList now
+
+	/* Append to activeList */
+	instance->prev = activeList.last;
+
+	if (instance->prev == NULL) {
+		activeList.first = instance; // activeList was empty, so fill it
+	}
+	else {
+		activeList.last->next = instance;
+	}
+
+	activeList.last = instance;
+
+	/* Adjust counts */
+	activeList.num++;
+	inactiveList.num--;
+
+	/* Ensure the next search will have something to feed its hunger with */
+	if (inactiveList.first == NULL)
+	{
+		printf("** Requiring more than %zd effects\n", activeList.num);
+
+		EffectChunk *chunk = malloc(sizeof(EffectChunk));
+		chunk->next = NULL;
+
+		chunkList.last->next = chunk;
+
+		inactiveList.num = MAX_EFFECTS;
+		inactiveList.first = &chunk->effects[0];
+		inactiveList.last = &chunk->effects[MAX_EFFECTS-1];
+
+		initEffectPool(inactiveList.first, inactiveList.last);
+	}
+
+	return instance;
+}
+
+
+static void Effect_freeImpl(void *self)
+{
+	printf("** Freeing an effect %zd\n", inactiveList.num);
+
+	EFFECT *instance = self;
+
+	/* Remove from activeList and fixup endings if necessary */
+	if (instance->prev != NULL) {
+		instance->prev->next = instance->next;
+	}
+	else {
+		activeList.first = instance->next; // We were the first in activeList
+	}
+	if (instance->next != NULL) {
+		instance->next->prev = instance->prev;
+	}
+	else {
+		activeList.last = instance->prev; // We were the last in activeList
+	}
+
+	/* Append to inactiveList */
+	instance->prev = NULL; // Singly linked
+	instance->next = NULL; // Last element
+
+	 // inactiveList is never empty (guaranteed in mallocImpl)
+	inactiveList.last->next = instance;
+	inactiveList.last = instance;
+
+	/* Adjust counts */
+	inactiveList.num++;
+	activeList.num--;
+}
+
+
+void initEffectsSystem(void)
+{
+	EffectChunk *chunk;
+	for (chunk = chunkList.first; chunk != NULL;)
+	{
+		EffectChunk *chunkNext = chunk->next;
+		free(chunk);
+		chunk = chunkNext;
+	}
+
+	chunk = malloc(sizeof(EffectChunk));
+	chunk->next = NULL;
+
+	chunkList.first = chunk;
+	chunkList.last = chunk;
+
+	// activeList is empty at start
+	activeList.num = 0;
+	activeList.first = NULL;
+	activeList.last = NULL;
+
+	// inactiveList contains all elements
+	inactiveList.num = MAX_EFFECTS;
+	inactiveList.first = &chunk->effects[0];
+	inactiveList.last = &chunk->effects[MAX_EFFECTS-1];
+
+	// Initialise free-effects pool
+	initEffectPool(inactiveList.first, inactiveList.last);
+}
+
+
 static void positionEffect(const EFFECT *psEffect)
 {
 	int rx, rz;
@@ -272,76 +414,8 @@ static void killEffect(EFFECT *e)
 			psTile->tileInfoBits &= ~BITS_ON_FIRE;	// clear fire bit
 		}
 	}
-	effectStatus[e-asEffectsList] = ES_INACTIVE;
-	e->control = (UBYTE) 0;
-}
-
-static BOOL	essentialEffect(EFFECT_GROUP group, EFFECT_TYPE type)
-{
-	switch(group)
-	{
-	case	EFFECT_FIRE:
-	case	EFFECT_WAYPOINT:
-	case	EFFECT_DESTRUCTION:
-	case	EFFECT_SAT_LASER:
-	case	EFFECT_STRUCTURE:
-		return(true);
-		break;
-	case	EFFECT_EXPLOSION:
-		if(type == EXPLOSION_TYPE_LAND_LIGHT)
-		{
-			return(true);
-		}
-	default:
-		return(false);
-	}
-}
-
-static BOOL utterlyReject( EFFECT_GROUP group )
-{
-	switch(group)
-	{
-	case EFFECT_BLOOD:
-	case EFFECT_DUST_BALL:
-	case EFFECT_CONSTRUCTION:
-		return(true);
-	default:
-		return(false);
-	}
-}
-
-/**	Simply sets the free pointer to the start - actually this isn't necessary
-	as it will work just fine anyway. This WOULD be necessary were we to change
-	the system so that it seeks FREE slots rather than the oldest one. This is because
-	different effects last for different times and the oldest effect may have
-	just got going (if it was a long effect).
-*/
-void	initEffectsSystem( void )
-{
-	UDWORD	i;
-	EFFECT	*psEffect;
-
-	/* Set position to first */
-	freeEffect = 0;
-
-	/* None are active */
-	numEffects = 0;
-
-	activeEffects = 0;
 
-	missCount=0;
-
-	skipped = letThrough = 0;
-
-	for(i=0; i<MAX_EFFECTS; i++)
-	{
-		/* Get a pointer - just cos our macro requires it, speeds not an issue here */
-		psEffect = &asEffectsList[i];
-		/* Clear all the control bits */
-		psEffect->control = (UBYTE)0;
-		/* All effects are initially inactive */
-		effectStatus[i] = ES_INACTIVE;
-	}
+	Effect_freeImpl(e);
 }
 
 void	effectSetLandLightSpec(LAND_LIGHT_SPEC spec)
@@ -392,96 +466,21 @@ void addMultiEffect(const Vector3i *basePos, Vector3i *scatter, EFFECT_GROUP gro
 	}
 }
 
-UDWORD	getNumActiveEffects( void )
-{
-	return(activeEffects);
-}
-
-UDWORD	getMissCount( void )
-{
-	return(missCount);
-}
-
-UDWORD	getNumSkippedEffects(void)
-{
-	return(skippedEffects);
-}
-
-UDWORD	getNumEvenEffects(void)
-{
-	return(letThrough);
-}
-
 
 void addEffect(const Vector3i *pos, EFFECT_GROUP group, EFFECT_TYPE type, bool specified, iIMDShape *imd, bool lit)
 {
-	static unsigned int aeCalls = 0;
-	UDWORD	essentialCount;
-	UDWORD	i;
-	EFFECT	*psEffect = NULL;
-
-	aeCalls++;
+	EFFECT *psEffect = NULL;
 
 	if(gamePaused())
 	{
 		return;
 	}
 
-	/* Quick optimsation to reject every second non-essential effect if it's off grid */
-	if(clipXY(pos->x, pos->z) == false)
-	{
-		/* 	If effect is essentail - then let it through */
-	  	if(!essentialEffect(group,type) )
-		{
-			bool bSmoke = false;
-
-			/* Some we can get rid of right away */
-			if ( utterlyReject( group ) )
-			{
-				skipped++;
-				return;
-			}
-			/* Smoke gets culled more than most off grid effects */
-			if(group == EFFECT_SMOKE)
-			{
-				bSmoke = true;
-			}
+	psEffect = Effect_mallocImpl();
 
-			/* Others intermittently (50/50 for most and 25/100 for smoke */
-			if(bSmoke ? (aeCalls & 0x03) : (aeCalls & 0x01) )
-			{
-				/* Do one */
-				skipped++;
-				return;
-			}
-			letThrough++;
-		}
-	}
+	printf("*** Type: %d, Group: %d\n", type, group);
 
-
-	for (i = freeEffect, essentialCount = 0; (asEffectsList[i].control & EFFECT_ESSENTIAL)
-		&& essentialCount < MAX_EFFECTS; i++)
-	{
-		/* Check for wrap around */
-		if (i >= (MAX_EFFECTS-1))
-		{
-			/* Go back to the first one */
-			i = 0;
-		}
-		essentialCount++;
-		missCount++;
-	}
-
-	/* Check the list isn't just full of essential effects */
-	if (essentialCount >= MAX_EFFECTS)
-	{
-		/* All of the effects are essential!?!? */
-		return;
-	}
-
-	freeEffect = i;
-
-	psEffect = &asEffectsList[freeEffect];
+	psEffect->control = 0;
 
 	/* Store away it's position - into FRACTS */
 	psEffect->position.x = pos->x;
@@ -499,7 +498,6 @@ void addEffect(const Vector3i *pos, EFFECT_GROUP group, EFFECT_TYPE type, bool s
 	{
 		psEffect->frameNumber = lit;
 	}
-
 	else
 	{
 		/* Starts off on frame zero */
@@ -562,9 +560,6 @@ void addEffect(const Vector3i *pos, EFFECT_GROUP group, EFFECT_TYPE type, bool s
 			break;
 	}
 
-	/* Make the effect active */
-	effectStatus[freeEffect] = ES_ACTIVE;
-
 	/* As of yet, it hasn't bounced (or whatever)... */
 	if(type!=EXPLOSION_TYPE_LAND_LIGHT)
 	{
@@ -572,43 +567,28 @@ void addEffect(const Vector3i *pos, EFFECT_GROUP group, EFFECT_TYPE type, bool s
 	}
 
 	ASSERT(psEffect->imd != NULL || group == EFFECT_DESTRUCTION || group == EFFECT_FIRE || group == EFFECT_SAT_LASER, "null effect imd");
-
-	/* No more slots available? */
-	if(freeEffect++ >= (MAX_EFFECTS-1))
-	{
-		/* Go back to the first one */
-		freeEffect = 0;
-	}
 }
 
 
 /* Calls all the update functions for each different currently active effect */
 void processEffects(void)
 {
-	unsigned int i;
-
-	/* Establish how long the last game frame took */
-	missCount = 0;
-
-	/* Reset counter */
-	numEffects = 0;
-
+	printf("STARTING FRAME: %d\n", frameGetFrameNumber());
 	/* Traverse the list */
-	for (i = 0; i < MAX_EFFECTS; i++)
+	for (EFFECT *it = activeList.first; it != NULL;)
 	{
-		/* Don't bother unless it's active */
-		if(effectStatus[i] == ES_ACTIVE)
+		EFFECT *itNext = it->next; // If updateEffect deletes something, we would be screwed...
+
+		updateEffect(it);
+
+		/* Is it on the grid */
+		if (clipXY(it->position.x, it->position.z))
 		{
-			updateEffect(&asEffectsList[i]);
-			/* One more is active */
-			numEffects++;
-			/* Is it on the grid */
-			if (clipXY(asEffectsList[i].position.x, asEffectsList[i].position.z))
-			{
-				/* Add it to the bucket */
-				bucketAddTypeToList(RENDER_EFFECT,&asEffectsList[i]);
-			}
+			/* Add it to the bucket */
+			bucketAddTypeToList(RENDER_EFFECT, it);
 		}
+
+		it = itNext;
 	}
 
 	/* Add any droid effects */
@@ -616,15 +596,14 @@ void processEffects(void)
 
 	/* Add any structure effects */
 	effectStructureUpdates();
-
-	activeEffects = numEffects;
-	skippedEffects = skipped;
 }
 
 
 /* The general update function for all effects - calls a specific one for each */
 static void updateEffect(EFFECT *psEffect)
 {
+	printf("S: %p E: %p G: %d T: %d NOW: %d LAST: %d DEL: %d FRAME: %d NFRA: %d\n", activeList.first, psEffect, psEffect->group, psEffect->type, gameTime, psEffect->lastFrame, psEffect->frameDelay, psEffect->frameNumber, effectGetNumFrames(psEffect));
+
 	/* What type of effect are we dealing with? */
 	switch(psEffect->group)
 	{
@@ -2552,8 +2531,6 @@ static const char FXData_file_identifier[] = "FXData";
 /** This will save out the effects data */
 bool writeFXData(const char* fileName)
 {
-	unsigned int count, i;
-
 	if (!tagOpenWrite(FXData_tag_definition, fileName))
 	{
 		ASSERT(false, "writeFXData: error while opening file (%s)", fileName);
@@ -2562,45 +2539,30 @@ bool writeFXData(const char* fileName)
 
 	tagWriteString(0x01, FXData_file_identifier);
 
-	// Count all the active EFFECTs
-	for (i = 0, count = 0; i < MAX_EFFECTS; ++i)
-	{
-		if(effectStatus[i] == ES_ACTIVE)
-		{
-			++count;
-		}
-	}
-
 	// Enter effects group and dump all EFFECTs
-	tagWriteEnter(0x02, count);
-	for (i = 0; i < MAX_EFFECTS; ++i)
-	{
-		const EFFECT* curEffect = &asEffectsList[i];
-
-		// Don't save inactive effects
-		if (effectStatus[i] != ES_ACTIVE)
-			continue;
-
-		tagWrite(0x01, curEffect->control);
-		tagWrite(0x02, curEffect->group);
-		tagWrite(0x03, curEffect->type);
-		tagWrite(0x04, curEffect->frameNumber);
-		tagWrite(0x05, curEffect->size);
-		tagWrite(0x06, curEffect->baseScale);
-		tagWrite(0x07, curEffect->specific);
-
-		tagWritefv   (0x08, 3, &curEffect->position.x);
-		tagWritefv   (0x09, 3, &curEffect->velocity.x);
-		tagWrites32v (0x0A, 3, &curEffect->rotation.x);
-		tagWrites32v (0x0B, 3, &curEffect->spin.x);
-
-		tagWrite(0x0C, curEffect->birthTime);
-		tagWrite(0x0D, curEffect->lastFrame);
-		tagWrite(0x0E, curEffect->frameDelay);
-		tagWrite(0x0F, curEffect->lifeSpan);
-		tagWrite(0x10, curEffect->radius);
-
-		tagWriteString(0x11, resGetNamefromData("IMD", curEffect->imd));
+	tagWriteEnter(0x02, activeList.num);
+	for (EFFECT *it = activeList.first; it != NULL; it = it->next)
+	{
+		tagWrite(0x01, it->control);
+		tagWrite(0x02, it->group);
+		tagWrite(0x03, it->type);
+		tagWrite(0x04, it->frameNumber);
+		tagWrite(0x05, it->size);
+		tagWrite(0x06, it->baseScale);
+		tagWrite(0x07, it->specific);
+
+		tagWritefv   (0x08, 3, &it->position.x);
+		tagWritefv   (0x09, 3, &it->velocity.x);
+		tagWrites32v (0x0A, 3, &it->rotation.x);
+		tagWrites32v (0x0B, 3, &it->spin.x);
+
+		tagWrite(0x0C, it->birthTime);
+		tagWrite(0x0D, it->lastFrame);
+		tagWrite(0x0E, it->frameDelay);
+		tagWrite(0x0F, it->lifeSpan);
+		tagWrite(0x10, it->radius);
+
+		tagWriteString(0x11, resGetNamefromData("IMD", it->imd));
 
 		// Move on to reading the next effect group
 		tagWriteNext();
@@ -2642,11 +2604,9 @@ bool readFXData(const char* fileName)
 	count = tagReadEnter(0x02);
 	for(i = 0; i < count; ++i)
 	{
-		EFFECT* curEffect = &asEffectsList[i];
+		EFFECT* curEffect = Effect_mallocImpl();
 		char imd_name[PATH_MAX];
 
-		ASSERT(i < MAX_EFFECTS, "readFXData: more effects in this file than our array can contain");
-
 		curEffect->control      = tagRead(0x01);
 		curEffect->group        = tagRead(0x02);
 		curEffect->type         = tagRead(0x03);
@@ -2676,17 +2636,12 @@ bool readFXData(const char* fileName)
 			curEffect->imd = NULL;
 		}
 
-		effectStatus[i] = ES_ACTIVE;
-
 		// Move on to reading the next effect group
 		tagReadNext();
 	}
 	// Leave the effects group again...
 	tagReadLeave(0x02);
 
-	/* Ensure free effects kept up to date */
-	freeEffect = i;
-
 	// Close the file
 	tagClose();
 
diff --git a/src/effects.h b/src/effects.h
index b0ddb6e..e678775 100644
--- a/src/effects.h
+++ b/src/effects.h
@@ -113,14 +113,6 @@ typedef enum
 } EFFECT_TYPE;
 
 
-/* Is the slot currently being used and is it active? */
-typedef enum
-{
-	ES_INACTIVE,
-	ES_ACTIVE
-} EFFECT_STATUS;
-
-
 typedef enum
 {
 	LL_MIDDLE,
@@ -149,6 +141,7 @@ struct _effect_def
 	uint16_t          lifeSpan;    // what is it's life expectancy?
 	uint16_t          radius;      // Used for area effects
 	iIMDShape         *imd;        // pointer to the imd the effect uses.
+	EFFECT *prev, *next; // Previous and next element in linked list
 };
 
 

Attachment: signature.asc
Description: This is a digitally signed message part.

_______________________________________________
Warzone-dev mailing list
Warzone-dev@gna.org
https://mail.gna.org/listinfo/warzone-dev

Reply via email to