30 replies to this topic

[Dissipate]

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

[rip-off]

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.

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

 

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

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.

[Dissipate]

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.

[rip-off]

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 rule of three, 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:

•  (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

[Mercile55]

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.

[Mercile55]

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

 

If you're setting same texture on all sprites, shouldn't those pointers be all the same then, or have I missed something?

[rip-off]

Please note that while I'm giving "rule of thumb" advice here, where it matters one should always measure.

 

 

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

This is a common misconception. Linked lists have a smaller worst case asymptotic complexity for "management" tasks. That isn't the full story.

 

The most glaring weakness is that complexity analysis treats the allocation/deallocation routines as just another O(1) operation, rather than a potentially complex algorithm/data structure in it's own right. Default allocators tend to be "expensive", in that they are not O(1), or otherwise incur asynchronous costs (such as garbage collection in managed languages).

 

A more subtle problem is that it ignores the affects of the cache, which favour contiguity in dynamic arrays and the reduced memory overhead compared to linked list node pointers.

 

Finally, they take a very pessimistic view. Sometimes this is reasonable, but one must also understand that most data structures in a typical application never get a chance to reach the sizes where asymptotic complexity dominates. The constant factors that are eliminated can make up a non-negligible amount of time. The OP is probably going to be dealing with a couple of hundred sprites at most, depending on the exact nature of the game. If there were millions, or billions of sprites, then there are lot of other problems to solve, not just the performance of the game but the gameplay affects of all that complexity on the poor player!

 

In any case:

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. 

When implemented using "amortised constant time" algorithms, add/insert rarely causes reallocation. Most implementations do not deallocate when removing entries. The cost of insert/remove is the cost of copying the elements to "fill the gap". This can be offset by a variety of techniques, from "swap and pop", std::partition() to std::remove_if() depending on what you are doing.

 

In comparison, link list add/insert/delete do incur an allocation or deallocation of a node for each operation.

[Dissipate]

@rip-off:  I'm looking into making those changes and will give a reply to that when done. (learning and implementing)

 

 In comparison, link list add/insert/delete do incur an allocation or deallocation of a node for each operation.

I bet you can sneakily just 'turn off' some nodes to later reuse them. But with the cost of finding them again. Unless another list is created that points to dead nodes. Or is that extravagent?

 

If you're setting same texture on all sprites, shouldn't those pointers be all the same then, or have I missed something?

This is the bit I don't understand. Even the array of clones (which works fine) has NULL for the m_Texure. I dont copy need to copy the texure (i dont think) as I am just pointing to the vertex buffer of the master - you know how cloneing works !! Or can this not be done the way I am attempting. Maybe I will find out what's happening as I implement a user defined copy constructor and an assignment operator then just try

m_SquareClone = m_pSquare 

Is the memory being moved around inside LPDIRECT3DVERTEXBUFFER9 ? to cause the texture to be lost.

 

[Mercile55]

Are you sure that SetVertexBuffer will copy not only texture coords, but the texture resource too?

[Dissipate]

 Are you sure that SetVertexBuffer will copy not only texture coords, but the texture resource too?

What that function in Clone does is:

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; // It does this
	//pDest->m_pIndexBuffer  = pSource->m_pIndexBuffer;  // It does this

        // Copy Num of vertices, indicies and primitive count
        ...
}

Somehow the texture is tied to the device but I dont understand how see here:

g_App.GetDevice()->SetTexture(0, m_Texture); // get device is LPDIRECT3DDEVICE9

but and again here:

void CShape::Create(int iNumOfVertices, 
	  	    int iNumOfIndicies, 
		    int iPrimCount,
		    CUSTOMVERTEX* pVertices,
		    size_t iSizeOfVertices,
		    short* pIndicies,
		    size_t iSizeOfIndicies)
{	
	// Save the primitive count and number of vertices for the draw function later
	m_iNumOfVertices = iNumOfVertices;
	m_iNumOfIndicies = iNumOfIndicies;
	m_iPrimCount	 = iPrimCount;

    // Create a vertex buffer interface called m_VertexBuffer
    g_App.GetDevice()->CreateVertexBuffer(iNumOfVertices*sizeof(CUSTOMVERTEX),
 					  0,
					  CUSTOMFVF,
					  D3DPOOL_MANAGED,
					  &m_pVertexBuffer,
					  NULL);
...
    // Lock vertex buffer and load the vertices into it
...
    // Create an index buffer interface called i_buffer
...
}

Somehow they reside inside the LPDIRECT3DDEVICE9 attached in some manner. So then how do diffferant objects that call the functions, like create and set, get assigned a differant vertex buffer or texture?

 

(...still working on implementing rip-offs suggestions)

[Dissipate]

Posted 24 January 2013 - 05:49 PM

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 rule of three, 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:
(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

I have made all the changes you suggested, making a Circular, templated, doubley linked list and applying the rule of three. Implementing this into my project and utilising it does not solve the problem (I'll research dynamic arrays later!). Please can you help me understand whats happening as I can't continue otherwise. Maybe someone can post a short excerpt/code-list on how to clone and draw a textured quad. My D3DXSprite clones fine.
(hoping...!)