C++ question regarding linked lists

[Adrian Tung]

Hi,

I'm trying to figure out if this is possible to do this, and if so, any ideas on how it might be done.

In the course of my coding experiences, I've found linked lists to be extremely useful in many situation where you want to keep adding and deleting things of unknown quantity to a list. However, in the long run over-use of linked lists can cause bad memory fragmentation. Therefore, I replaced my linked lists with what I call a pooled linked list. Here, I declare a static member of the linked list class and during initialization, allocate a huge number of nodes to this static member. Whenever I need a node, I get one from this pool and when I delete a node, I put it back in the pool. When there are not enough nodes, I allocate another huge bunch of nodes to the pool. The nodes are simple objects that have a pointer to the prev, next, and data pointer.

I also have another type of linked list which is useful when I want to directly store objects in the list itself, and is declared something like this:

class CNode
{
public:
CNode() { m_pPrev = m_pNext = NULL; }
virtual ~CNode() {}
CNode* m_pPrev;
CNode* m_pNext;
}

class CMyLinkedList
{
public:
CMyLinkedList() { m_pHead = m_pTail = m_pCurrent = NULL; m_iCount = 0; }
~CMyLinkedList() { DeleteAll(); }

void DeleteAll(); // delete all nodes
void AddHead(CNode* pNode); // add a Node
void AddTail(CNode* pNode); // add a Node
void Insert(CNode* pNode); // add a Node

private:
CNode* m_pHead;
CNode* m_pTail;
CNode* m_pCurrent;
int m_iCount;
}

As you can see, objects that I want to be stored in this sort of linked list will basically inherit from the base CNode class, then I can easily add and remove these objects to/from the linked list.

The first linked list that I mentioned is good for the system's memory. However, it's disadvantage is that the data isn't stored on the node itself. The node points to the data which has to be allocated somewhere else (which will probably contribute to memory fragmentation).

I like the second linked list because I can even use it in multithreaded applications without worrying about my data being screwed up, since I can easily do read locks and write locks on only the list and not have to worry about having to lock the data separately from the list.

Currently, I am figuring out if I can create a linked list class that has the characteristics of both lists that I just mentioned. The first thing that I thought of was to use a template class, but how do I ensure or guarantee that the user does not use any other data type other than a class derived from the base CNode in the template? And if I use a static member, how would the class be able to differentiate between several objects,

e.g. if someone were to declare
CMyLinkedList<CDerivedNode1> m_list1;
CMyLinkedList<CDerivedNode1> m_list2;
CMyLinkedList<CDerivedNode2> m_list3;

would I be able to initialize the first two lists only once and initialize the third list as well?

I realize that in all my experience in C++, everything I know is telling me that I can't do that with templates. So I'm just throwing the ball, using the template class as an example, to see if anyone else can figure out a nice and clean solution.

Also, I realize that I can keep to my "memory-friendly" architecture if I manually pre-allocate the nodes by myself, but this means that if I have several derived nodes, I have to manually pre-allocate for each and every one of them. I was hoping for a more automated solution, a "generic class" that will handle all.

Any comments, ideas or even criticism is appreciated.


Cheers,
🙂atwl

 

[PCHPlayer]

How about putting the memory allocation into the LinkedList class. Something like this:

template<class T>
class CMyLinkedList
{
private:
class CNode : private T
{
public:
CNode() : T(){...}
CNode(const T &node) : T(node) {...}
CNode *next;
CNode *prev;
};

CNode *head;
CNode *tail;

public:
T & AddHead() { CNode *n = new CNode(); n->next = head; head = n; return *n;} // User responsible for setting returned object's attributes
T & AddHead(const T &) // Uses copy constructor
....
};

There is lots missing here, but it is now completely type safe. Since the linked list class is responsible for allocating the nodes you can implement any kind of memory allocation you wish. You may even want to override the operator new() of the CNode class. I did not completely think this out, but I think it will work.

 

[ElDonAntonio]

Just asking here, why don't you just use an STL list or vector? it basically works in the same way, first allocates a given number of elements, and if you add more, it doubles its size and reallocates itself somewhere else in memory so you don't have any fragmentation. Or you can reserve in advance how much memory you want to allocate.

 

[Adrian Tung]

PCHPlayer:
Nice idea, but I was wondering how I would be able to automatically handle memory allocation here? Lets say that T was a CMyObj1 in one list and CMyObj2 in another list, how can I, during initialization, pre-allocate an n-amount of objects for the list?

ElDonAntonio
Yeah, I looked at it before but didn't think that it would fit my needs. If I wanted to have, say, 10 lists of objects CMyCustomNode, I want them to draw from the same pool of nodes (hence my idea of having a static class member) rather than pre-allocate n nodes for each individual list.


I realize I was a little rushed while posting my question, thus maybe resulting in the message I was trying to state being unclear. Here's a sample scenario of how I would envision my list to be used:

/* sample scenario */

On a game server I would want to create X number of lists of objects CEntity. Each CEntity is derived from the base CNode class. They way my list is envisioned to work, all X lists will draw from the same pool of free CEntity objects.

Now each CEntity will have a unique ID generated for it when the class is allocated data to it (as opposed to when it is first initialized). It will be added to one of the X lists depending on the hash value of its unique ID.

When the server needs to retrieve an Entity with an ID of Y, it calculates the hash value of Y in order to determine which list it should search for. It will then do a read lock on that list, find and retrieve the object, then unlock that list. At the same time, other threads may be accessing and modifying other objects in other lists.

On the other hand, I may also want to create N number of lists of objects CEvent, and each CEvent is also derived from the base CNode class. Also, the way I envision my list class, all N lists should be smart enough to pre-allocate and draw from a single pool of CEvent objects.

/* ~ sample scenario */


This is just a sample scenario and not something I am planning to implement. The reason I thought up of this list is just for academic purposes, you know sometimes when you're in the bathroom and you start thinking about things and stuff like that. 😀


🙂atwl