🔒 Locked

Memory problem (confused, please help)

Started by goldsword Jun 13, 2002 at 4:08 PM 5 replies 250+ views

Original Post

Jun 13, 2002 at 4:08 PM

Hi, I''m having some problem with my linked list. My data gets corrupted! I''m using void pointers to store any type of data, so when I''d like to add something to the list i call my funcion: Add(void *pData,DWORD dwSize) Inside this funcion i use malloc in the following way: cpNewNode->pData = malloc(dwSize); if (!cpNewNode->pData) return false; Then later on when i fetch data i typecast the data into a proper datatype like: int a = *((int*)my_list[5]); When I output my values to a file however I''ve noticed something really strange, if I were to add 4 integers to my list, everything works correct but if I add more stuff to my list some data gets corrupted, here''s an example of what I mean: // CODE CList list; int iArray[6] = {1,2,3,4,5,6}; for (int i = 0; i < 6; i++) list.Add((void*)&iArray,sizeof(int)); for (i = 0; i < 6; i++) file << *((int*)list[i]) << endl; // END CODE // FILE OUTPUT 1 2 3 4 4 // Corrupted! 6 // END OUTPUT Could someone explain this and tell me how to fix this problem? It would be really nice, I guess it''s something to do with malloc. When I read about the function it said it might sometimes allocate some extra memory, but I don''t know. / Thanks!

IndirectX

Jun 13, 2002 at 4:18 PM

First let me say that you should be using templates. If you haven''t read about them yet, it might be best to wait writing your own list class, because using void * for a linked list is a Bad Thing.

That said, if you insist on writing your list with void * and malloc instead of templates and new, we need more information. How is your node declared and how are the nodes stored in the list?

James555

Jun 13, 2002 at 4:20 PM

Hi Goldsword

A couple of things

CList list;
int iArray[6] = {1,2,3,4,5,6};
for (int i = 0; i < 6; i++)
list.Add((void*)&iArray,sizeof(int));
^^^^^^^^^^^^^^^^^^^^^^^^

I think you mean

  
list.Add((void*)&iArray[i],sizeof(int*));

This will create a pointer to each element in the array, the way you have it you are storing the address of the first location in the array over and over again.

Good Luck,
- James

[edited by - James555 on June 13, 2002 5:54:20 PM]

[edited by - James555 on June 13, 2002 5:54:50 PM]

goldsword

Author

goldsword

Jun 13, 2002 at 4:26 PM

Sorry, it should be: list.Add( (void*)&iArray, sizeof(int) );
Forgot the [i]!

Anyway, I''m storing the things like this:

CNode
{
CNode *pNext; // ptr 2 next node
CNode *pPrev; // ptr 2 prev node
void *pData; // pointer to allocated memory
DWORD dwSize; // Size in byte of data stored @ pData
}

Then when I add an item i:
1. Create a new node (dynamical)
2. Allocate memory for the data to hold and assign it to the node
3. Increase the counter of items in the list

When I delete something my node destructor is called...
~CNode
{
if (pData)
free(pData);
}

We can simplify and type my class like:

class CList
{
CNode *m_cpRoot, *m_cpLast;

bool Add(void *pData,DWORD dwSize);
}

// VERY SIMPLIFIED!

Hope that helps!

Bashar

Jun 13, 2002 at 4:34 PM

You''ve shown us everything but the most important part! The Add() implementation. I''m sure you''re not append or prepending your elements correctly - prolly forgetting to initialize to NULL or checking for NULL. Either way, show us Add().

goldsword

Author

goldsword

Jun 13, 2002 at 4:46 PM

  
bool CList::Add(void *pData,DWORD dwSize)
{
	// Create a new node

	CNode* cpNode = new CNode;

	// Valide the pointer

	if (!cpNode)
		return false;

	// Setup the node

	cpNode->dwSize = dwSize;

	// Allocate memory to hold the new data

	cpNode->pData = malloc(dwSize)

	// Return false if the allocation failed

	if (!cpNode->pData)
	{
		delete cpNode;
		return false;
	}

	// Copy the source data

	memcpy(cpNode->pData,pData,dwSize);
	
	// Is this the first item in the list?

	if (m_dwCount == 0)
	{
		// Make this the root item

		m_cpRoot = cpNode;
		m_cpLast = cpNode;
		cpNode->pPrev = 0;
	}
	else
	{
		cpNode->pPrev = m_cpLast;
		m_cpLast->pNext = cpNode;
		m_cpLast = cpNode;
	}

	// Increase the item counter

	m_dwCount++;

	// Return success

	return true;
}

// Name: Replace

// Desc: Replaces an item in the list

bool CList::Replace(void *pData,DWORD dwSize,DWORD dwIndex)
{
	// Validate the index

	if (dwIndex >= m_dwCount)
		return false;

	// Create a pointer to point to the node we should replace

	CNode* cpNode;

	// Are we trying to get the first item?

	if (dwIndex == 0)
	{
		// Retrieve the first node

		cpNode = m_cpRoot;
	}
	else
	{
		if ( dwIndex == (m_dwCount - 1 ) )
		{
			// Retrieve the last pointer

			cpNode = m_cpLast;
		}
		else
		{
			// Calculate the fastest way to iterate the list

			if ( (float)(m_dwCount / dwIndex) >= 2.0f )
			{
				// We should start from the front

				cpNode = m_cpRoot;

				// Traverse the list

				while (dwIndex--)
					cpNode = cpNode->pNext;
			}
			else
			{
				// We should start from the back

				cpNode = m_cpLast;

				// Traverse the list

				while ( dwIndex++ != m_dwCount)
					cpNode = cpNode->pPrev;
			}
		}
	}

	// Deallocate old data

	free(cpNode->pData);

	// Try to allocate the memory

	cpNode->pData = malloc(dwSize);

	// Validate the pointer

	if (!cpNode->pData)
		return false;

	// Save the size

	cpNode->dwSize = dwSize;

	return true;
}

Edit by Stoffel: Added [ source ] and [ /source ] tags.

That's the add function...

[edited by - Stoffel on June 13, 2002 7:01:46 PM]

Bashar

Jun 14, 2002 at 9:29 AM

well, Add() looks fine, you''re appending normally, except, you''re forgetting to set pNext = NULL - I think this will be helpful when traversing the list, as opposed to constantly comparing against the m_cpLast member.

ummm...seeing as how you don''t touch replace(), don''t worry bout that (for now). I think your problem could only lie in one place: the overloading of [] in CList

I''d suggest posting that function.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.