LINKLLIST HELP

edited March 2012 in Help request
we created a hash table that uses the pointer addresses of our object enemies as the hash keys. we are storing LINKLIS's of shot in the hash table. however we do a remove from one of the LINKLIST 's in the hash table, the remove is successful, but the counter in the LINKLIST's counter does not get decremented. Also we add a enemy object to one of the LINKLIST's in the hash table, the counter gets incremented but then when we loop back and grab the same LINKLIST that corresponds to the same hash key the LINKLIST's counter is zero.

here is the code where we are doing the remove and add
orxSHOT *nodeSelected;
orxLINKLIST shotList = *((orxLINKLIST *)orxHashTable_Get(shotsHomingEnemy, hashKey)),
			    newShotList;
	orxBANK     *memBankClonedNode;
	orxSHOT 	*clonedShot;

	orxLOG("Old target to be replace  is : %d", hashKey);

	orxLOG("BEFORE ENTERING THE WHILE, THE HASH KEY IS %d THE OLD LIST HAS THIS MANY SHOTS  %d",hashKey, orxLinkList_GetCounter(&shotList));

	while(orxLinkList_GetCounter(&shotList) > 0)
	{

		// Moving to the first node in the list to be reassigned
		nodeSelected = (orxSHOT *)orxLinkList_GetFirst(&shotList);

		// Selecting new enemy target
		nodeSelected->enemy = SelectTarget(nodeSelected->shot);

		if(nodeSelected->enemy == orxNULL)
		orxLOG("Enemy Selected was NULL and was not added to the new list");

		orxLOG("New target is :  %d", (orxU32)nodeSelected->enemy);

		// Getting list of shots of the neares enemy
		newShotList = *((orxLINKLIST *)orxHashTable_Get(shotsHomingEnemy, (orxU32)nodeSelected->enemy));

		orxLOG("THE NEW SHOT LIST FROM THE NEW ENEMY HAS %d SHOTS", orxLinkList_GetCounter(&newShotList));

		memBankClonedNode = orxBank_Create(1, sizeof(orxSHOT), orxBANK_KU32_FLAG_NONE, orxMEMORY_TYPE_MAIN);
		clonedShot = (orxSHOT *)orxBank_Allocate(memBankClonedNode);

		clonedShot->shot = nodeSelected->shot;
		clonedShot->enemy = nodeSelected->enemy;

		// Getting rid off the old node wether was added or no to a new list
		if(orxLinkList_Remove((orxLINKLIST_NODE *)nodeSelected) == orxSTATUS_SUCCESS )
		{
			shotList.u32Counter--;

			orxLOG ("none'REASSIGN_ENEMY'I REMOVED THE NODE FROM THE LIST AND NOW THE LIST HAS %d SHOT IN THE OLD LIST", orxLinkList_GetCounter(&shotList));
			// Adding cloned node to the new list
			if (orxLinkList_AddEnd (&newShotList, (orxLINKLIST_NODE *)clonedShot) == orxSTATUS_SUCCESS)
			{
				orxLOG ("NODE ADDED TO THE END OG THE LIST BC OF SUCESSFUL REMOVE IN 'REASSIGN_ENEMY' ");
			}
			orxLOG("THE OLD LIST HAS %d SHOT AFTER THE REMOVE",orxLinkList_GetCounter(&shotList));
		}
		else
		{
			// TODO: High-importance bug fix. If this bug is not fixed, everything crashes.
			// orxLinkList_Clean(&shotList);
			orxLOG("I COULDNT REMOVE THE NODE in 'REASSIGN_ENEMY'");
		}


	}

	return;
}

Comments

  • edited March 2012
    Mmh, can I see the definition of your orxSHOT structure?
    Is there an orxLINKLIST_NODE there as the first field?

    Also, may I suggest not storing the lists in hashtables but directly bind them to you enemy instead?

    If you don't use the UserData pointer already, you can store your list in your enemy with orxObject_SetUserData() and retrieve it with orxObject_GetUserData().
    If you're already using the UserData with one of your structure, simply add the linklist to that structure.

    This way you'll save yourself all the hastable query/handling costs and it'll still work on 64b architectures where pointers are too large to fit as a hashtable key.
  • edited March 2012
    Thanks so much that's a great idea.I'm guessing i would have to allocate memory for each linklist in the structure. here im sending you the deffinition of the shot structure.
    typedef struct
    {
    	orxLINKLIST_NODE llNode;
    	orxOBJECT        *shot,
    			 *enemy;
    
    } orxSHOT;
    


    this is my structure for each enemy
    typedef struct
    {
    	orxLINKLIST_NODE llNode;
    	orxOBJECT        *enemy;
    	orxS32           health;
    } orxENEMY;
    

    would i have to add a LINKLIST field?.. and then allocate memory for a LINKLIST every time an enemy is spawned?

    thanks for your help
  • edited March 2012
    Ok, I was asking for the linklist node as you don't initialize that field on your copy node. Make sure you always initialize all fields after allocating memory as the memory is not certified to be cleared to 0 (actually, it'll contain whatever was there before).

    So yes, in your case set your orxENEMY like this:
    typedef struct
    {
      orxLINKLIST_NODE llNode;
      orxOBJECT        *enemy;
      orxS32           health;
      orxLINKLIST      stShotList;
    } orxENEMY;
    

    At init clears the stShotList with orxMemory_Zero(&MyEnemy->stShotList, sizeof(orxLINKLIST)) and you don't need to allocate any extra memory for linklists/linklist_nodes as they're part of your orxENEMY/orxSHOT structure.

    Just make sure to clear them at first, that's all. :)
  • edited March 2012
    i got rid off the hash table and added a link list field into the enemy structure, here is the enemy structure
    typedef struct
    {
    	orxLINKLIST_NODE llNode;
    	orxOBJECT        *enemy;
    	orxLINKLIST	 shotlist;
    	orxS32           health;
    } orxENEMY;
    

    and this is how i am adding the enemies into a link list and initializing their link lists. this is done in my Event handler in the spawning event
    if (!strcmp(orxConfig_GetString("Type"), "Enemy"))
    			{
    				orxBANK *memBankShotList = orxBank_Create(1, sizeof(orxLINKLIST), orxBANK_KU32_FLAG_NONE, orxMEMORY_TYPE_MAIN);
    				orxLINKLIST shotLinkList = *((orxLINKLIST *)orxBank_Allocate(memBankShotList));
    				orxMemory_Zero(&shotLinkList, sizeof(orxLINKLIST));
    				orxBANK *memBank = orxBank_Create(1, sizeof(orxENEMY), orxBANK_KU32_FLAG_NONE, orxMEMORY_TYPE_MAIN);
    				orxENEMY *llEnemy = (orxENEMY *)orxBank_Allocate(memBank);
    				llEnemy->enemy = recipient;
    				llEnemy->health = orxConfig_GetS32("Health");
    				llEnemy->shotlist = shotLinkList;
    				orxObject_SetUserData(recipient, llEnemy);
    				if (orxLinkList_AddEnd(&enemyList, (orxLINKLIST_NODE *)llEnemy) == orxSTATUS_SUCCESS)
    					orxLOG("AN ENEMY WAS SPAWNED IN THE EVH AND ADDED TO THE ENEMY LINK LIST %d", (orxU32)llEnemy->enemy);
    
    				// add linklist to hash table
    //				if(orxHashTable_Add(shotsHomingEnemy, (orxU32)recipient, shotLinkList)== orxSTATUS_SUCCESS)
    //					orxLOG("AN ENEMY WAS SPAWNED IN THE EVH AND ADDED TO THE HASHTABLE %d", (orxU32)llEnemy->enemy);
    			}
    

    as u can see i got reed of the hash table. however i have a function that take an enemy node and graves the link list init and reassign all the shots to a different enemy's link list. however whenever i remove a node from the old enemy's structure the counter of the list does not get decremented. when i do an add_end it does not increment the pointer either. i have set the user data as you said.. this is the code
    void reassign_enemy(orxENEMY *enemyNode)
    {
    	orxSHOT     *nodeSelected;
    	orxLINKLIST shotList = enemyNode->shotlist,
    			    newShotList;
    	orxBANK     *memBankClonedNode;
    	orxSHOT 	*clonedShot;
    
    	orxENEMY *newEnemyTargetNode;
    
    	orxOBJECT *enemyTargeted;
    
    
    
    	orxLOG("none'reassign_enemy'Enemy Shot list to be reassigned %d has %d shots",(orxU32)enemyNode->enemy, orxLinkList_GetCounter(&shotList));
    
    	while(orxLinkList_GetCounter(&shotList) > 0)
    	{
    		// Getting first shot store in the  shotlist
    		nodeSelected = (orxSHOT *)orxLinkList_GetFirst(&shotList);
    
    		// Selecting new enemy target
    		enemyTargeted = SelectTarget(nodeSelected->shot);
    
    		if (enemyTargeted != orxNULL)
    		{
    			newEnemyTargetNode  =  orxObject_GetUserData(enemyTargeted);
    
    			orxLOG("New target is :  %d", newEnemyTargetNode->enemy);
    
    			// Getting list of shots of the neares enemy
    			newShotList = newEnemyTargetNode->shotlist;
    
    			orxLOG("THE NEW SHOT LIST FROM THE NEW ENEMY HAS %d SHOTS", orxLinkList_GetCounter(&newShotList));
    
    			memBankClonedNode = orxBank_Create(1, sizeof(orxSHOT), orxBANK_KU32_FLAG_NONE, orxMEMORY_TYPE_MAIN);
    			clonedShot = (orxSHOT *)orxBank_Allocate(memBankClonedNode);
    
    			clonedShot->shot = nodeSelected->shot;
    			orxObject_SetUserData(clonedShot->shot, clonedShot);
    
    			// Adding cloned node to the new list
    			if (orxLinkList_AddEnd (&newShotList, (orxLINKLIST_NODE *)clonedShot) == orxSTATUS_SUCCESS)
    			{
    				orxLOG ("none'REASSIGN_ENEMY' NODE ADDED TO THE END OF THE NEW ENEMY'S LIST THAS HAS %s SHOTS",orxLinkList_GetCounter(&newShotList));
    			}
    		}
    
    		// Removing shot from the Old Enemy's shotlist
    
    		if(orxLinkList_Remove((orxLINKLIST_NODE *)nodeSelected) == orxSTATUS_SUCCESS )
    		{
    			orxLOG ("none'REASSIGN_ENEMY'I REMOVED THE NODE FROM THE LIST AND NOW THE LIST HAS %d SHOT IN THE OLD LIST", orxLinkList_GetCounter(&shotList));
    		}
    		else
    		{
    			orxLOG("I COULDNT REMOVE THE NODE in 'REASSIGN_ENEMY'");
    		}
    
    
    	}
    
    	return;
    }
    

    thanks so much for your help, sorry for asking so much
  • edited March 2012
    javierely1 wrote:
    i got rid off the hash table and added a link list field into the enemy structure, here is the enemy structure
    typedef struct
    {
    	orxLINKLIST_NODE llNode;
    	orxOBJECT        *enemy;
    	orxLINKLIST	 shotlist;
    	orxS32           health;
    } orxENEMY;
    

    Nice, looks good so far! :)
    and this is how i am adding the enemies into a link list and initializing their link lists. this is done in my Event handler in the spawning event
    if (!strcmp(orxConfig_GetString("Type"), "Enemy"))
    			{
    				orxBANK *memBankShotList = orxBank_Create(1, sizeof(orxLINKLIST), orxBANK_KU32_FLAG_NONE, orxMEMORY_TYPE_MAIN);
    

    Mmh, you're creating a new bank that will never get deleted so you're leaking memory here everytime you handle this event!
    Why not having a static bank somewhere that you initialize once and reuse everytime you handle an event?
    				orxLINKLIST shotLinkList = *((orxLINKLIST *)orxBank_Allocate(memBankShotList));
    

    As I mentioned in my last post, you do not need to (and should not!) allocate memory for the linklist itself as it's already allocated in your enemy structure (the "shotlist" field is directly the linklist, not a pointer to a linklist, that means the memory is already allocated within your enemy structure).
    				orxBANK *memBank = orxBank_Create(1, sizeof(orxENEMY), orxBANK_KU32_FLAG_NONE, orxMEMORY_TYPE_MAIN);
    

    Same remark here, you're creating a new bank everytime you handle the event, which means you're leaking them very fast. The solution, as for the list, is to have a static enemy bank that you initialize in your Init() function and you reuse here when you need it.
    				llEnemy->shotlist = shotLinkList;
    

    This line copy all the field from the list you allocated manually to the one stored in your enemy structure. The issue is that, as it's not a pointer copy that you're doing but a full structure copy, you end up with 2 distinctive lists. So adding an element to one will not add it to the other.
    				if (orxLinkList_AddEnd(&enemyList, (orxLINKLIST_NODE *)llEnemy) == orxSTATUS_SUCCESS)
    

    Instead of casting I recommend to actually use the llNode field here (the casting is only needed when going from the field to the owner, not the other way).

    Also, I did not see where you actually add your shot to your linklist, but if you do something similar to the allocation/copy we've just seen, it's very likely that your shot doesn't end up to the list stored in your enemy structure but to one that you have manually allocated.

    Well, actually after re-reading your code, you create a local linklist (not a pointer!) and copy the enemy linklist to it. But as it's not a pointer pointing to the same linklist stored in your enemy, you actually end up with 2 distincts list.
    The local one is actually invalid and when you remove shots from the actual real linklist (the one in your enemy), the local one doesn't get updated: the counter doesn't change and, much worse, its pointer to the first item is now dangling!
    thanks so much for your help, sorry for asking so much

    My pleasure, and no worries for the questions, that's exactly why we have a forum so that we can help you and others coming after you with a similar problem! :)

    Here's a revised version, let me know what you think of it:
    if (!strcmp(orxConfig_GetString("Type"), "Enemy"))
    {
      // Allocates enemy from the static enemy bank (same bank for all enemies)
      orxENEMY *llEnemy = (orxENEMY *)orxBank_Allocate(staticEnemyBank);
    
      // Clears it (including the linklist inside)
      orxMemory_Zero(llEnemy, sizeof(orxENEMY));
    
      // Inits & binds it
      llEnemy->enemy = recipient;
      llEnemy->health = orxConfig_GetS32("Health");
      orxObject_SetUserData(recipient, llEnemy);
    
      // Adds it to the static enemy list
      orxLinkList_AddEnd(&staticEnemyList, &(llEnemy->llNode);
    }
    
    void reassign_enemy(orxENEMY *enemyNode)
    {
      // While enemy still has shots
      while(orxLinkList_GetCounter(&enemyNode->shotList) > 0)
      {
        orxENEMY *newEnemyTargetNode;
        orxSHOT  *nodeSelected;
    
        // Gets the first shot
        nodeSelected = (orxSHOT *)orxLinkList_GetFirst(&enemyNode->shotList);
    
        // Removes it from the enemy
        orxLinkList_Remove(nodeSelected);
    
        // Selects new enemy target
        enemyTargeted = SelectTarget(nodeSelected->shot);
    
        // Valid?
        if(enemyTargeted != orxNULL)
        {
          orxENEMY *newEnemyTargetNode;
    
          // Gets its enemy data
          newEnemyTargetNode = (orxENEMY *)orxObject_GetUserData(enemyTargeted);
    
          // Assigns the shot to the new enemy (no need to clone anything unless there's something I'm not aware of)
          orxLinkList_AddEnd(&newEnemyTargetNode->shotList, nodeSelected);
        }
        else
        {
          // Maybe it's time to dispose of that shot? :)
        }
      }
    }
    

    EDIT: As I wrote the code directly in the forum, it might not compile. :) It was simply to give an idea on how to simplify/rectify a few things.
  • edited March 2012
    Do orxBANKs automatically expand if you need more space? If not, is there any way to increase the size of an orxBANK?
  • edited March 2012
    Yes they do by default.

    The size you give is the actual number of items contained in each segment of a bank. Usually try for a power of two for better memory alignment friendliness, something like 32, 64, 128 or 256 depending on your needs.
    Then when the first segment is full, a new segment will be allocated, and so on.
    Memory is never given back nor segments are deleted, for performance reasons.

    If you give the orxBANK_KU32_FLAG_NOT_EXPANDABLE as a parameter when creating a bank, when the first segment is full no new segment will get created and allocations will fail (and you get an error message in debug too).
Sign In or Register to comment.