Jump to content
  • Advertisement
Sign in to follow this  
Hacksaw2201

C++ new operator and delete

This topic is 3771 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

GameDev.net decided to retire my earlier post. I now have a complete link list routine that will accomplish what I was looking into earlier. Have some source:
// basic windows and ogl headers
#include "standard.h"

#pragma once

class CEventList
{
public:

	// constructor and destructor
	CEventList();
	~CEventList();

	void Init();

	int Add(CEventList* eventList);
	int Delete(CEventList* eventList);
	int DeleteList();

	int		type;
	int		client;

	timer_s	time;

	CEventList*	prevItem;
	CEventList*	nextItem;

private:

	// allocate some work pointers
	CEventList*	listEntry;
	CEventList*	newItem;

};

#include "standard.h"

#include "CEventList.h"

//=========================================================================================
//
// Class Constructor
//
//=========================================================================================
CEventList::CEventList()
{
	prevItem = 0;
	nextItem = 0;

	type	= 0;
	client	= 0;

	memset(&time, 0x00, sizeof(timer_s));

	listEntry = 0;
	newItem   = 0;

}

//=========================================================================================
//
// Class Destructor
//
//=========================================================================================
CEventList::~CEventList()
{
}

//=========================================================================================
//
// Initialize the list
//
// Cannot put this in the constructor because of the new command.
// The class has not been allocated until the constructor has
// completed its execution.
//
//=========================================================================================
void CEventList::Init()
{

	// head points to nothing
	prevItem = 0;

	// head sequence variable
	time.startTime = 0;

	// make the tail for the list
	nextItem = new CEventList;

	// point the tail to the head
	nextItem->prevItem = this;

	// set the next pointer of the tail to null
	// marks the end of the list
	nextItem->nextItem = 0;

	// tail sequence variable
	// making a tail so it's the highest amount possible
	nextItem->time.startTime = 99999999;

}

//=========================================================================================
//
// Insert an event into the list
//
//=========================================================================================
int CEventList::Add(CEventList* eventIn)
{
	// start at the beginning of the list
	// skip the head of the list
	listEntry	= nextItem;

	// loop until the tail entry is found
	while(listEntry != 0)
	{
		// maintaining a sequenced order

		// if the current event's key being added is
		// less than or equal to the current entry's key
		// then it's a valid insertion point
		// because the two events happened at the same time

		if(eventIn->time.startTime <= listEntry->time.startTime)
		{
			// allocate the item
			newItem = new CEventList;

			// copy in the values
			//
			// trying to keep this simple
			// could use a structure to do one memcpy or
			// copy each variable from the incoming structure
			// to the class variables
			memcpy(&newItem->time, &eventIn->time, sizeof(timer_s));

			newItem->client = eventIn->client;

			newItem->prevItem = listEntry->prevItem;

			newItem->nextItem = listEntry;

			newItem->prevItem->nextItem = newItem;
			newItem->nextItem->prevItem = newItem;

			// item added
			return TRUE;
		}

		// jump to the next item in the list
		listEntry = listEntry->nextItem;
	}

	// item was not added
	return FALSE;
}

//=========================================================================================
//
// Delete an event from the list
//
//=========================================================================================
int CEventList::Delete(CEventList* eventIn)
{
	// start at the head of the list
	listEntry = nextItem;

	// while not at the end of the list
	while(listEntry->nextItem != 0)
	{
		// is this the item to be deleted?
		if(eventIn->time.startTime == listEntry->time.startTime)
		{
			// set the previous item's next pointer in the list
			// to point to the current list item's next pointer
			listEntry->prevItem->nextItem = listEntry->nextItem;

			// set the next item's previous pointer in the list
			// to point to the current list item's previous pointer
			listEntry->nextItem->prevItem = listEntry->prevItem;

			// delete the item
			// this sets the memory of the deleted item to (0xfeeefeee)
			//
			// I think the value means freefree but since there
			// is no "r" in hexadecimal feeefeee must have been deemed appropriate
			// 
			// :-)

			delete listEntry;

			// entry deleted
			return TRUE;
		}

		// jump to the next item in the list
		listEntry = listEntry->nextItem;
	}

	// exit the method
	return FALSE;
}

//=========================================================================================
//
// Delete all events from the list
//
// Source to delete a single item from the list is the same.
// Just remove the while and pass the entry to be deleted
// to Delete()
//=========================================================================================
int CEventList::DeleteList()
{
	listEntry = nextItem;

	while(listEntry->nextItem != 0)
	{
		// hang onto the next item in the list
		// otherwise you will loose this link
		CEventList* temp = listEntry->nextItem;

		// delete the entry
		Delete(listEntry);

		// iterate to the next item
		listEntry = temp;
	}

	return TRUE;

}





[Edited by - Hacksaw2201 on February 22, 2008 12:10:48 PM]

Share this post


Link to post
Share on other sites
Advertisement
Question or Answer?

I don't think it's a good idea to write your own containers (Linked Lists, Hash tables, Array lists, etc...)
use STL, they're probably more optimized and complete... good job anyway.

Share this post


Link to post
Share on other sites
After seeing prior conversations about node types and vectors and other C++ Gobble-D-Gook, I decided to write my own. Why?

IT Dept - Ease of use for all levels/types of programming
Marketing - Could get it done faster this way and out to the public sooner
Management - Could get it done faster this way cutting cost
Legal - Does this need a copyright?
Myself - Maybe I should teach


"I don't think it's a good idea to write your own containers (Linked Lists, Hash tables, Array lists, etc...) use STL"

Does Mac, IBM, HP, DEC, Java have STL?

by the way(btw) if you are thinking about getting into computer programming, memento_mori's repsonse is typical in the field .... an immediate critique.

26 years later ..... I don't miss it a bit.

Share this post


Link to post
Share on other sites
Quote:
Original post by Hacksaw2201
After seeing prior conversations about node types and vectors and other C++ Gobble-D-Gook, I decided to write my own. Why?

IT Dept - Ease of use for all levels/types of programming
Marketing - Could get it done faster this way and out to the public sooner
Management - Could get it done faster this way cutting cost
Legal - Does this need a copyright?
Myself - Maybe I should teach


"I don't think it's a good idea to write your own containers (Linked Lists, Hash tables, Array lists, etc...) use STL"

Does Mac, IBM, HP, DEC, Java have STL?

by the way(btw) if you are thinking about getting into computer programming, memento_mori's repsonse is typical in the field .... an immediate critique.

26 years later ..... I don't miss it a bit.


heh i didn't mean it in an offensive way... i was just being practical: if you're going to write everything from scratch and go THAT down, you may never start working on the actual game, thats what i meant.

Share this post


Link to post
Share on other sites
Quote:
Original post by Hacksaw2201
Does Mac, IBM, HP, DEC, Java have STL?


It's called the STL because S=Standard. i.e. it's part of the C++ standard so you find it everywhere you have a C++ compiler. It's no different than int, char, bool: it's an inherrent part of C++.

I don't want to start a flamewar but:

Quote:

IT Dept - Ease of use for all levels/types of programming
Marketing - Could get it done faster this way and out to the public sooner
Management - Could get it done faster this way cutting cost


I don't see how these are true. The STL containers are already written and anyone that knows C++ should know how to use them. In my experience teams find it harder to use custom containers because they don't obey the STL syntax that we all already know how to use.

For instance, the crappy custom containers in unreal .Empty() means clear the list and free memory; .empty() in STL is a bool check to see if the container is empty. So all a custom container does is make me continually have to open the header file to remember which method to use for the STL method i actually want to use; add to that a lack of functionality: no std::sort, no custom allocators, broken iterators, etc and you get a headache.

Custom containers obviously have a place in certain performance critical sections where you have identified STL algorithms as the culprits.

-me

Share this post


Link to post
Share on other sites
Quote:
Original post by Hacksaw2201
IT Dept - Ease of use for all levels/types of programming

False Every programmer in your team will need to learn your interface. The Standard C++ Libraries interface is... well, standard. That is the point. Your implementation is tightly coupled to the current use (Events sorted by time), and will require duplication for other uses. This makes maintenance more complicated: a bug found in one implementation requires all be updated.
Quote:

Marketing - Could get it done faster this way and out to the public sooner

False The Standard C++ Libraries version is already written. The one time cost of learning to use it would make all future use faster than writing your own.
Quote:

Management - Could get it done faster this way cutting cost

False The programmer time taken to write,debug and maintain this exceeds the cost of learning the Standard C++ Library. You last thread dates from last year. In that time you could have easily learned the parts of the standard library to code a similar class.
Quote:

Legal - Does this need a copyright?

Irrelevant All source code, as the work of a person or persons, is automatically under copy protection. On all major C++ compilers I know, making use of the Standard Library does not affect your own program in any way WRT licensing (which is perhaps what you intended this statement to mean).
Quote:

Myself - Maybe I should teach

False Well, not yet anyway, if you are unwilling to learn the standard way of doing this.

Quote:

Does Mac, IBM, HP, DEC, Java have STL?


Java is a programming language, and has its own standard library with similar constructs. A standards compliant C++ compiler on a Mac must include it. Most platforms of interest will have (at the very least) a port of GCC so will have a reasonably compliant C++ compiler, including a full standard library.

Quote:

26 years later ..... I don't miss it a bit.


[wink]

The standard method:

struct Event
{
int type, client;
timer_s time;
};

bool operator<(const Event &one, const Event &two)
{
return one.time < two.time;
}

typedef std::set<Event> EventList;

// for a variable of type EventList:
EventList eventList;

// to add
eventList.insert(someEvent);

// to remove
eventList.erase(someEvent);

// to empty the list
eventList.clear()

// to iterate over its elements in order, and do foo(const Event &) to them
for( EventList::iterator it = eventList.begin() ; it != eventList.end() ; ++it )
{
foo(*it);
}

// or using some of the standard libraries algorithms:
std::for_each(eventList.begin(),eventList.end(),&foo);





Total time to write: less than 5 minutes

Share this post


Link to post
Share on other sites
There is one reason to use a custom rolled linked list - that is when you want the object to remove itself from its container without doing something more fancy like firing an event back at the container. if the object maintains its own node pointers then it can safely remove itself in O(1) time complexity and without having to know about the container. You cant embed an stl::iterator in the object unfortunately because of iterator invalidation.

otherwise c++ has contiguous, sorted, heap and balanced data structures available across all platforms with about 10 keystrokes of work.

Share this post


Link to post
Share on other sites
Quote:
Original post by chairthrower
You cant embed an stl::iterator in the object unfortunately because of iterator invalidation.


For std::list, an iterator to a given node is only invalidated that node is erased. Any other modification to the list will not invalidate the iterator.

Share this post


Link to post
Share on other sites
Quote:
Original post by Palidine
For instance, the crappy custom containers in unreal .Empty() means clear the list and free memory; .empty() in STL is a bool check to see if the container is empty. So all a custom container does is make me continually have to open the header file to remember which method to use for the STL method i actually want to use; add to that a lack of functionality: no std::sort, no custom allocators, broken iterators, etc and you get a headache.


Ugh, Unreal containers. The Empty() thing still trips me up from time to time, and it took me forever to get used to how their iterators work. And yeah, their sort function is a real PITA to use.

The lesson to learn here is that, in general, reinventing the std containers is not only more work for the implementer, but it's more work for the people that have to use them as well.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!