• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Dissipate

Cloned Texture not displayed with Linked List

30 posts in this topic

I have a clone function that succesfully clones the vertex and index buffers of a square with a texture. It displays it correctly. The linked list uses nodes with pData of type VOID that is statically cast to a CSprTex. The CSprTexdisplays and updates correctly but the texture is not displayed and I dont know why.

class CNode
{
public:
    CNode(void);
    ~CNode(void);

    UINT m_uNodeType; // Leaf or non leaf-(head or end)

    VOID* pData;      // Can be cast to any class type eg CSprite*
    
    CNode* pNext;     // Pointer to the next object
    CNode* pPrev;     // Pointer to the previous object
private:

};// CNode

CLinked list's Add Node function:

void CLinkedList::AddNode(VOID* pData)
{
    g_FileDebug->Write("Add a Node\n");

    CNode* pNewNode = new CNode;      // Create the Node
    pNewNode->pData = pData;          // Assign the Sprite data
    pNewNode->m_uNodeType = CNODE_NODE;

    ...// insert behind Node End
    
    m_iNumberOfNodes++;  // Keep track of how many nodes there are
    g_FileDebug->WriteEx("Number of nodes = ", m_iNumberOfNodes);
}// AddNode

And this is how I draw it. with a loop that accesses the nodes.

        CNode* pCurrentNode = m_LLFaces.m_HeadNode.pNext;     // Point to first in list
        while (pCurrentNode != &m_LLFaces.m_EndNode)
        {
            CSprTex* pSprCurrent = static_cast<CSprTex*>(pCurrentNode->pData); // Void to CSprite
            if (pSprCurrent != NULL)
            {
                pSprCurrent->Orbit(index, 0.0f, index);
                pSprCurrent->Rotate(m_fRotateXClone, m_fRotateY, m_fRotateZ);
                pSprCurrent->SetTransformTransByRotXYZ();
                pSprCurrent->SelectBuffers();
                pSprCurrent->Draw();
            }
            pCurrentNode = pCurrentNode->pNext;                 // Go to next in the list
        }// end while*>

This is the cloning function:

int CSpriteManager::Clone(CSprTex* pSource, CSprTex* pDest)
{
    // vertex and index buffers
    pDest->SetVertexBuffer(pSource->GetVertexBuffer());
    pDest->SetIndexBuffer(pSource->GetIndexBuffer());

    //pDest->m_pVertexBuffer = pSource->m_pVertexBuffer;
    //pDest->m_pIndexBuffer  = pSource->m_pIndexBuffer;

    // number of verticies and indicies and primitive count
    pDest->m_iNumOfVertices  = pSource->m_iNumOfVertices;
    pDest->m_iNumOfIndicies  = pSource->m_iNumOfIndicies;
    pDest->m_iPrimCount      = pSource->m_iPrimCount;
    
    // rotational and translational matricies
    pDest->m_matRotateX      = pSource->m_matRotateX;
    pDest->m_matRotateY      = pSource->m_matRotateY;
    pDest->m_matRotateZ      = pSource->m_matRotateZ;
    pDest->m_matTranslate    = pSource->m_matTranslate;
    
    return (1);
}// Clone (overloaded)

So why doesn't the texture display? The square does display though and I can move (any number of them) independantly of the master. Cloning an object outside of the Linked list structure displays the texture fine. What am I missing?

0

Share this post


Link to post
Share on other sites

1. You didn't specify what data you're passing when calling CLinkedList::AddNode(VOID*...).

2. With static_cast, you need to be sure that target type is compatible in all terms, i.e. you should not cast statically from base class to an object that derives from it, unless you're absolutely sure of its content. Remember that it will always return something that may not be valid. The null check will only protect you if source pData is null.

3. You also didn't write, how and where Clone is being used, and whether is works, when you Clone more than once.

4. Do you actually set CNode's pNext to the next node's pointer ?

If the m_LLFaces.m_HeadNode points to the first CNode, then m_LLFaces.m_HeadNode.pNext will most likely be the second. That's how LL works, pNext is always the second or "this" is the last if it's NULL.

 

More details please.

0

Share this post


Link to post
Share on other sites

Thanks for the reply. Sorry I have become one of those people who dont give enough pertinent information.

 

1. You didn't specify what data you're passing when calling CLinkedList::AddNode(VOID*...).

I am passing my CSprTex class which is inherited from CShape:

class CSprTex: public CShape 
{
public:
	CSprTex(void);
	~CSprTex(void);

	int SetFilename(char* cFilename);
	void SetTexture(void);

	inline LPDIRECT3DTEXTURE9 GetTexture(void) { return m_Texture; }

	void ReleaseTexture(void);

	LPDIRECT3DTEXTURE9 m_Texture;

private:

	char* m_cFilename;

};// CSprTex

 

2. With static_cast, you need to be sure that target type is compatible in all terms, i.e. you should not cast statically from base class to an object that derives from it, unless you're absolutely sure of its content. Remember that it will always return something that may not be valid. The null check will only protect you if source pData is null.

The NULL check was just for safety. I am casting from a derived class to a derived class. That's ok isn't it? They both will have the same functions.

 

 

3. You also didn't write, how and where Clone is being used, and whether is works, when you Clone more than once.

Used like this from the CSpriteManager class:

int Clone(CSprTex* pSource, CSprTex* pDest);

See above for CSpriteManager::Clone(...) function. The function is being called when the space bar is pressed (key repeat is handled) and is called like this:

CSprTex* SprTest = new CSprTex;              // Allocate space 
m_pSpriteManager->Clone(m_pSquare, SprTest); // Clone master CSprTex to CSprTest
SprTest->Move(0.0f, 0.0f, 0.0f);             // Initialise to start at this position

m_LLFaces.AddNode(SprTest);                  // Linked List add node

See above for how it is drawn. Note: that the clone function works and I can draw from it and the texture is displayed if I do not use the linked list(LL) but I create only 1. Using the LL I can display maybe 150 squares all moving independantly around the screen in 3D. 

 

 

4. Do you actually set CNode's pNext to the next node's pointer ?

Ok heres the code I cut out of ::AddNode to abbreviate it for you :P

m_EndNode.pPrev->pNext = pNewNode;  // Last ==> New
pNewNode->pNext  = &m_EndNode;      //          New ==> End
pNewNode->pPrev  = m_EndNode.pPrev; // Last <== New
m_EndNode.pPrev  = pNewNode;        //          New <== End

I have stepped through the creation and deletion of the nodes within a separate solution and am confident that all the nodes point to the right addresses and that Add, DeleteNode and DelAllNodes work impeccabley.

 

 

If the m_LLFaces.m_HeadNode points to the first CNode, then m_LLFaces.m_HeadNode.pNext will most likely be the second. That's how LL works, pNext is always the second or "this" is the last if it's NULL.

No sorry what I have done I is to create separate Head and End nodes that exist on their own. The m_HeadNode.pNext points to the first CNode. That way I can delete all the CNodes and have a structure to place nodes back into... hmmm maybe its not the lightest of lightweight solutions but anyway.

 

Please don't hesitate to ask for any further clarification. (Thanks in advance)

0

Share this post


Link to post
Share on other sites

I am wondering about this part:

 

    // vertex and index buffers
    pDest->SetVertexBuffer(pSource->GetVertexBuffer());
    pDest->SetIndexBuffer(pSource->GetIndexBuffer());

 

I don't know what those buffers are, but mostly they are an area of memory. If that is the case, depending on your implementation it is possible that you are not creating a copy here, but assigning the same pointer to the two objects (this is also know as aliasing and is can be dangereous).

0

Share this post


Link to post
Share on other sites

I am trying to use a Master Object then create another object that just points to the data that the master holds. Re-using its data. The clones are not deleted but the Master is.

Here is the header:

inline LPDIRECT3DVERTEXBUFFER9 GetVertexBuffer(void)    { return m_pVertexBuffer; }
inline LPDIRECT3DINDEXBUFFER9  GetIndexBuffer(void)     { return m_pIndexBuffer; }
inline void SetVertexBuffer(LPDIRECT3DVERTEXBUFFER9 pV) { m_pVertexBuffer = pV; }
inline void SetIndexBuffer(LPDIRECT3DINDEXBUFFER9 pI)   { m_pIndexBuffer = pI; }
0

Share this post


Link to post
Share on other sites

Are LPDIRECT3DVERTEXBUFFER9 and LPDIRECT3DINDEXBUFFER9 pointers, structs or classes? If they are a class, do they overload the "=" operator?

Edited by KnolanCross
0

Share this post


Link to post
Share on other sites

Well, then you are not cloning the object, if the buffer on the source is deleted or changed it will affect all its clones (and the clones of the clone). I wouldn't really recommend this at all.

 

You said the master is deleted, are you sure you are not removing the buffer when doing this? If you do it will affect all the clones, if you don't you will have a hard time to determine when to free this buffer (assuming this is dynamically allocated memory).

0

Share this post


Link to post
Share on other sites

No you dont understand. The master holds the information for, lets say the texture. The clones all point to the master so that there need only be 1 copy of a texture in memory. Then all the clones get their own properties set to what ever independant of the master as only the texture is pointed at!

The Master is deleted at program end.

 

But this isnt the problem the problem (I think) something to do with the static_cast. Maybe its not pointing to the memory. But it works if I dont use the Linked list. I tried re-cloning the object after it is cast - but that didn't work. (I'm blind on this).

0

Share this post


Link to post
Share on other sites

Hm, ok. I pointed that because it is a bad pratice and could be the error, seems I was wrong, sorry.

Have you tried loging the pointer by using %p to check if the memory addresses are correct (or using the debugger to check them)?

 

Can you post the code where you add to the list?

Edited by KnolanCross
0

Share this post


Link to post
Share on other sites

Confirmed: .log shows:

m_pSquare->GetVertexBuffer() = 64896640   // this is the master object
pSprCurrent->GetVertexBuffer() = 64896640 // this is the cloned one

The code for adding to the list is displayed above.

(back at computer at 9:30pm)

0

Share this post


Link to post
Share on other sites

Well, I am out of ideas now, sorry.

The only thing that comes to my mind is that the clone method is losing some information (normals, maybe?) and the drawn is not displaying.

0

Share this post


Link to post
Share on other sites
Just one more question for clarity. How does SetTexture get called and m_Texture set in effect ?

EDIT(2):
I think there's either something wrong with the LinkedList, so that for some reason, things get reset.
EDIT: removed invalid statement.

Other than that, check pointers to m_Texture when calling Draw for every item on the list, and compare to the root one from m_pSquare (I believe).

It maybe easier if you could post complete code of the AddNode, CLinkedList constructor that is being used, and ==/!= overloads, only any code dealing with CNode and head/end objects. Edited by Mercile55
0

Share this post


Link to post
Share on other sites
How does SetTexture get called and m_Texture set in effect ?

It is called only within the Render() by the master CSprTex object like this:

 

    // SQUARE
    if (m_pSquare != NULL) // only draw if this has been set
    {    
        m_pSquare->Rotate(m_fRotateX, m_fRotateY, m_fRotateZ);
        m_pSquare->Move(m_fMoveX, m_fMoveY, m_fMoveZ);
        m_pSquare->SetTransformTransByRotXYZ();
        m_pSquare->SelectBuffers();
        m_pSquare->SetTexture();
        m_pSquare->Draw();
    }

 

The clones (m_pSquareCloneArray[20]) get drawn the same way but without the SetTexture() being called and they display and fly around fine.

m_Texture is set as follows:

void CSprTex::SetTexture(void)
{
    g_App.GetDevice()->SetTexture(0, m_Texture); // Device is LPDIRECT3DDEVICE9
}// SetTexture

This is not called by the clones as they do not have thier texture property assigned. Note: that the colour of the squares are brown...! as are all the meshes (box and teapot non-clones) and not 50% grey as they should be. This, I noticed, only happens when I am setting the texture for the master object. If I change only the top left pixel of the graphic file (.png), I get strange results... Purple gives me blank purple square and green gives me a mauve, green gives me a pink square... hmm interesting... what is happening the teh texture...? Also... They are drawn upside down (rotated 180deg on X-axis).

 

 

I think there's either something wrong with the LinkedList, so that for some reason, things get reset. It may not necessarily be noticed, as static_cast will call constructor on CSprTex, so the instance will appear correct, therefore, if all objects in linked list are invalid, then they are all gonna be created anew when statically cast.

Ok so I commented out the NULL in the constructor and that still didnt work...

CSprTex::CSprTex(void)
{
	m_Texture = NULL; // Commenting out makes no differance
	m_iNum    = 0;    // The class keeps this value and logs it during the render for proof
}// CSprTex

Plus I can confirm the constructors get called in the static_cast as I logged them during the Render().

So should I be using dynamic_cast or safe_cast instead? How can I access the object in the linked list. If I dont use VOID* then I will need to have linked lists of every class of object. They need to be cast some how, howelse could I access the members.

 

 

Other than that, check pointers to m_Texture when calling Draw for every item on the list, and compare to the root one from m_pSquare (I believe).

Aha here is the .log called in the Render() for 3 nodes:

*** Start Drawing Nodes ********************************
iNum = 1
m_pSquare->GetTexture() =39384576
pSprCurrent->GetTexture() =135168096

iNum = 2
m_pSquare->GetTexture() =39384576
pSprCurrent->GetTexture() =135170848

iNum = 3
m_pSquare->GetTexture() =39384576
pSprCurrent->GetTexture() =140321984

 

Here is the AddNode function:

void CLinkedList::AddNode(VOID* pData)
{
	g_FileDebug->Write("Add a Node\n");

	CNode* pNewNode = new CNode;      // Create the Node
	pNewNode->pData = pData;          // Assign the Sprite data
	pNewNode->m_uNodeType = CNODE_NODE;

	//m_pTempNode = m_pEndNode->pPrev;  // Save Prev
	//m_pTempNode->pNext = pNewNode;    // Prev ==> New
	//m_pEndNode->pPrev  = pNewNode;    //          New <== End
	//pNewNode->pNext    = m_pEndNode;  //          New ==> End
	//pNewNode->pPrev    = m_pTempNode; // Prev <== New 

	m_EndNode.pPrev->pNext = pNewNode;  // Last ==> New
	pNewNode->pNext  = &m_EndNode;      //          New ==> End
	pNewNode->pPrev  = m_EndNode.pPrev; // Last <== New
	m_EndNode.pPrev  = pNewNode;        //          New <== End
	
	m_iNumberOfNodes++;  // Keep track of how many nodes there are
	g_FileDebug->WriteEx("Number of nodes = ", m_iNumberOfNodes);
}// AddNode

Called like this:

if(KEY_DOWN(VK_SPACE))	
	if (bToggleSpace) 
	{
		bToggleSpace = false; // run once
		
		// Create a sprite within a linked list and 
		// display it randomly on the screen
		CSprTex* SprHappyFace = new CSprTex;
		SprHappyFace->m_iNum = iNumIncrementor;
		m_pSpriteManager->Clone(m_pSquare, SprHappyFace);
		SprHappyFace->Move(0.0f, 0.0f, 1.0);
		SprHappyFace->SetFilename(FILE_TEX2);

		m_LLFaces.AddNode(SprHappyFace);
		iNumIncrementor++;
	}

Please dont laugh at the SprHappyFace variable I thought it would cheer me up (highly unprofessional though)

Here is the LL constructor:

CLinkedList::CLinkedList(void)
{
	//g_FileDebug->Write("CLinkedList Constructor\n");

	m_iNumberOfNodes = 0;
	
	// Set the non leaf node types
	m_HeadNode.m_uNodeType = CNODE_HEAD;
	m_EndNode.m_uNodeType  = CNODE_END;

	m_HeadNode.pNext = &m_EndNode;  //          Head ==> End
	m_EndNode.pPrev  = &m_HeadNode; //          Head <== End 
	m_HeadNode.pPrev = NULL;        // NULL <== Head
	m_EndNode.pNext  = NULL;        //                   End ==> NULL
	m_HeadNode.pData = NULL;
	m_EndNode.pData  = NULL;
}// Constructor

The following is in the Initialisation part and displays the texture fine:

for (int i = 0; i < 20; i++)
{
	m_pSquareCloneArray[i] = new CSprTex;
	m_pSpriteManager->Clone(m_pSquare, m_pSquareCloneArray[i]);
	m_pSquareCloneArray[i]->Move((rand() % 20) - 10,
				     (rand() % 20) - 10,
				     (rand() % 20) - 10);
	m_pSquareCloneArray[i]->m_iNum = i + 100; // Just to keep an identity for these elements
}

 

So if I am losing the texture then that means that the clone isn't working, or the static_cast isnt working. Hmm what so I do?

0

Share this post


Link to post
Share on other sites
Is there a reason you are not using the standard library for this?

Only std::vector is brand new to me, I have no experience of it. It was easier to code the thing myself and I have no idea how much junk it will add in... Will it resolve the problem? Im looking it up now and will create a test (somehow).

0

Share this post


Link to post
Share on other sites

I cannot say that switching to the standard library will necessarily resolve the problem. However, using the standard library would rule out many bugs that would hide in a typical beginner's hand rolled linked list implementation.

 

While I would encourage any beginner to write a linked list implementation to get familiar with the data structure, I would advise them against using this implementation in an actual project.

 

The standard containers will not add in "junk". At most it will contain some functionality that you won't use (yet), but the linker should strip all that out of the final build. Most implementations will add some sanity checks to debug builds, which will catch some bugs where you use the standard library incorrectly.

 

I cannot comment on the algorithmic complexity of code I cannot see. You'd have to post your entire linked list class for us to check the O(?) of those functions.

0

Share this post


Link to post
Share on other sites
It may not necessarily be noticed, as static_cast will call constructor on CSprTex, so the instance will appear correct, therefore, if all objects in linked list are invalid, then they are all gonna be created anew when statically cast.

 

This is incorrect. Using static_cast<> with a pointer type will not call any constructors for the pointed at type.

Edited by rip-off
0

Share this post


Link to post
Share on other sites
I cannot say that switching to the standard library will necessarily resolve the problem. However, using the standard library would rule out many bugs that would hide in a typical beginner's hand rolled linked list implementation.

I have carefully stepped through the code in a separate solution and checked all the addresses and I am confident that the LL is bullet proof!!! The std::vector (as you know) uses dynamically allocated arrays that it 'grows' periodically. Do you really think the performance would be better (travering the array) than my LL. Besides I can code all the functions that the vector has anyway.

 

This is incorrect. Using static_cast<> with a pointer type will not call any constructors for the pointed at type.

Oops... yeah I just checked. Sorry for agreeing with previous poster (hehe)

 

Ok here is the entire class to check to see why the texture is not being displayed:

CLinkedList.h: http://www.filehosting.org/file/details/414390/CLinkedList.h

ClinkedList.cpp: http://www.filehosting.org/file/details/414396/CLinkedList.cpp

CNode.h: http://www.filehosting.org/file/details/414392/CNode.h

CNode.cpp: http://www.filehosting.org/file/details/414393/CNode.cpp

(ahh for the good of the community)

 

Hope this helps to find the problem

0

Share this post


Link to post
Share on other sites

[quote]

The std::vector (as you know) uses dynamically allocated arrays that it 'grows' periodically. Do you really think the performance would be better (travering the array) than my LL.

[/quote]

Amortised growth dynamic arrays outperform linked lists for most typical use. This is due to cache coherency. 

 

[quote]

Ok here is the entire class to check to see why the texture is not being displayed:

[/quote]

Please post the code here, or if you must on a site that has no barriers to download. I don't want to submit any email addresses to that website, I don't want to create any accounts.

0

Share this post


Link to post
Share on other sites

Amortised growth dynamic arrays outperform linked lists for most typical use. This is due to cache coherency.

hmm Amortised - something to do with death (mort). I looked up this is reference to what you said http://en.wikipedia.org/wiki/Cache_coherence

 

 
Please post the code here

Ok thanks, It'll be good to understand what going wrong:

 

CLinkedList.h

#ifndef CLinkedList_h
#define CLinkedList_h

#include "Windows.h" // for VOID
#include "CNode.h"
#include "CSprTex.h"
#include "Main.h"

class CLinkedList
{
public:
	CLinkedList(void);
	~CLinkedList(void);

	void AddNode(VOID* pData);      // Insert at end
	void DeleteNode(CNode* pNode);  
	void DeleteAllNodes(void);  
	
	void Initialise(void);
	
	CNode m_HeadNode;
	CNode m_EndNode;
	
	int m_iNumberOfNodes;
};

#endif // CLinkedList_h

And CLinkedList.cpp

#include "CLinkedList.h"
#include "CFile.h"

// *********************************************************************   //
// Name: CLinkedList													   //
// Description: Create the Head and End nodes and point them to each other //
// *********************************************************************   //
CLinkedList::CLinkedList(void)
{
	//g_FileDebug->Write("CLinkedList Constructor\n");

	m_iNumberOfNodes = 0;
	
	// Set the non leaf node types
	m_HeadNode.m_uNodeType = CNODE_HEAD;
	m_EndNode.m_uNodeType  = CNODE_END;

	m_HeadNode.pNext = &m_EndNode;  //          Head ==> End
	m_EndNode.pPrev  = &m_HeadNode; //          Head <== End 
	m_HeadNode.pPrev = NULL;        // NULL <== Head
	m_EndNode.pNext  = NULL;        //                   End ==> NULL
	m_HeadNode.pData = NULL;
	m_EndNode.pData  = NULL;
}// Constructor

// ********************************************************************* //
// Name:AddNode								 //
// Description: Insert a node of the given type (pData) at the end of    //
//		list.                                                    //
// ********************************************************************* //
void CLinkedList::AddNode(VOID* pData)
{
	g_FileDebug->Write("Add a Node\n");

	CNode* pNewNode = new CNode;      // Create the Node
	pNewNode->pData = pData;          // Assign the Sprite data
	pNewNode->m_uNodeType = CNODE_NODE;

	m_EndNode.pPrev->pNext = pNewNode;  // Last ==> New
	pNewNode->pNext  = &m_EndNode;      //          New ==> End
	pNewNode->pPrev  = m_EndNode.pPrev; // Last <== New
	m_EndNode.pPrev  = pNewNode;        //          New <== End
	
	m_iNumberOfNodes++;  // Keep track of how many nodes there are
	g_FileDebug->WriteEx("Number of nodes = ", m_iNumberOfNodes);
}// AddNode

// ********************************************************************* //
// Name: DeleteNode														 //
// Description: Delete a given CNode and point the left and right sides  //
//              past it.												 //
// ********************************************************************* //
void CLinkedList::DeleteNode(CNode* pNode)
{
	CNode* pPrev = pNode->pPrev; 
	CNode* pNext = pNode->pNext;

	pPrev->pNext = pNext; // P ==> N
	pNext->pPrev = pPrev; // P <== N

	delete pNode;
	m_iNumberOfNodes--;
}// DeleteNode

// ********************************************************************* //
// Name: DeleteAllNodes							 //
// Description: Cycle through the list and delete all nodes one by one   //
// ********************************************************************* //
void CLinkedList::DeleteAllNodes(void)
{
	//g_FileDebug->WriteEx("Number of nodes to delete = ", m_iNumberOfNodes);
	if (m_iNumberOfNodes > 0)
	{
		// Cycle through and delete
		CNode* pCurrentNode = m_HeadNode.pNext; // Point to first in list
		while (pCurrentNode != &m_EndNode)
		{
			g_FileDebug->Write("Delete a Node\n");
			CNode* pTempNode = pCurrentNode;    // Save this node
			pCurrentNode = pCurrentNode->pNext; // Go to next in the list
			delete pTempNode;		    // Delete saved node
			m_iNumberOfNodes--;                 // Decrement node count 
		}// end while
	}// end if 
}// DeleteAllNodes

// ********************************************************************* //
// Name: Initialise						         //
// Description: Initialise the Liknked list structure and set the        //
//              non leaf nodes				 		 //
// ********************************************************************* //
void CLinkedList::Initialise(void)
{
	m_HeadNode.m_uNodeType = CNODE_HEAD;
	m_EndNode.m_uNodeType  = CNODE_END;
}// Initialise

// ********************************************************************* //
// Name: ~CLinkedList							 //
// Description: Destructor				 		 //
// ********************************************************************* //
CLinkedList::~CLinkedList(void)
{
}// ~CLinkedList

 

CNode.h

#ifndef CNode_h
#define CNode_h

#include "Windows.h" // For VOID

#define CNODE_UNDEF 13
#define CNODE_HEAD  1
#define CNODE_END   2
#define CNODE_NODE  3

class CNode
{
public:
	CNode(void);
	~CNode(void);

	UINT m_uNodeType; // Leaf or non leaf-(head or end)

	VOID* pData;      // Can be cast to any class type eg CSprite*
	
	CNode* pNext;     // Pointer to the next object
	CNode* pPrev;     // Pointer to the previous object
private:

};// CNode

#endif // CNode_h

CNode.cpp

#include "CNode.h"
#include "Main.h"
#include "CFile.h"

// ********************************************************************* //
// Name: CNode								 //
// Description: Constructor				 		 //
// ********************************************************************* //
CNode::CNode(void)
{
	//g_FileDebug->Write("CNode Constructor\n");
	m_uNodeType = CNODE_UNDEF; // 
	pData = NULL;
}// CNode

// ********************************************************************* //
// Name: ~CNode								 //
// Description: Make sure that the Head or End's pData are not deleted	 //
// ********************************************************************* //
CNode::~CNode(void)
{
	//g_FileDebug->Write("CNode Destructor\n");
	if ((m_uNodeType != CNODE_HEAD) || (m_uNodeType != CNODE_END))
		if (pData != NULL) 
			delete pData;

}// ~CNode

(hope I dont get flamed for posting too much code)

You will have to remove the extraneous includes such as #include "CFile.h" and the g_FileDebug->Write("") or ->WriteEx commands dotted around. Theres not many.

See previous posts for how I call Addnode(...) and also loop throught the list and cast. Please ignore CLinkedList::Initialise() as that is taken care of in the constructor instead. Its just that the delete key seems so far away these days!

 

Should I use meshes instead of textured quads. With the (box's) Z depth turned down to zero it would look like a square and I'd also have access to ID3DXBaseMesh::CloneMesh function too. I haven't looked it up yet.

0

Share this post


Link to post
Share on other sites

DeleteAllNodes definitely contains a bug, it fails to clear the "head" and "tail" pointers. CNode calls "delete" on a VOID pointer, which is undefined. You should use templates to maintain type safety. The destructor does not deallocate memory.

 

The lack of copy constructors and assignment operators on the two classes is also problematic. You need to obey the [url="http://en.wikipedia.org/wiki/Rule_of_three_(C%2B%2B_programming)"]rule of three[/url], or "disable" copying and assignment by declaring the copy constructor and assignment operator as private, and not implementing them.

 

I don't see any other major bugs, but due to the unencapsulated implementation every single client access needs to be perfectly correct or it could corrupt the loop.

 

There are a few minor issues too:

[list]

[*] (m_uNodeType != CNODE_HEAD) || (m_uNodeType != CNODE_END) is a tautology. Consider, if X is any number, then (X != 1) || (x != 2) is true.

[*] You don't need to check a pointer is NULL before calling delete - delete does the right thing with null pointers and you are duplicating those checks.

[*] You don't need to have two value nodes in the linked list. Most implementations just have a pair of pointers to nodes. Using such "sentinel" nodes isn't necessarily a bad thing, it is a valid implementation strategy, but you should not force client code to reason about this.

[*] You don't need the "node type" concept. Just have the head and tail contain NULL data pointers.

[*] Don't depend on Windows.h: just use void * rather than VOID * if it was necessary

[*] Use an enum rather than #defines for something like "node type", if it was necessary

[*] Main.h is almost always a poor idea.

[*] In general, strive for as few dependencies as possible, particularly for something generic like a linked list. Avoid coupling this implementation to the rest of your project

[/list]

1

Share this post


Link to post
Share on other sites

Amortised growth dynamic arrays outperform linked lists for most typical use. This is due to cache coherency. 

 

This depends on the case you're testing for performance, whether it's access or management.

In most cases, where add/insert/delete are being called many times, it's not a correct statement, as every such call causes whole array to be reallocated. Random access on the other hand is much faster on an array than linked list, providing that the index is known, and iterator isn't being used to find the item.

 

It may not necessarily be noticed, as static_cast will call constructor on CSprTex, so the instance will appear correct, therefore, if all objects in linked list are invalid, then they are all gonna be created anew when statically cast.

 

This is incorrect. Using static_cast<> with a pointer type will not call any constructors for the pointed at type.

You're absolutely correct, not on a pointer.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0