Tip: Coding generic lists of objects in C/C++

Virtual lists and class lists do it better

Thomas Burger (twburger@bigfoot.com), Owner, Thomas Wolfgang Burger Consulting

Thomas Wolfgang Burger is the owner of Thomas Wolfgang Burger Consulting. He has been a consultant, instructor, analyst, and applications developer since 1978. He can be reached at twburger@bigfoot.com.

Summary: Have you ever had a project that required you to have an indeterminate number of different objects in memory? For some purposes a binary tree is the best solution, but usually the simpler linked list is the obvious choice.

Tag this!

Date: 01 Oct 2001
Level: Advanced
Activity: 1530 views

A simplified example of the problem

The trouble with lists is that list handler functions for manipulating lists must be duplicated to handle different objects, even though the logic is exactly the same. For example:

struct Struct_Object_A
{
	int a;
	int b;
	Struct_Object_A *next;
} OBJECT_A;
typedef struct Struct_Object_B
{
	int a;
	int b;
	int c;
	Struct_Object_B *next;
} OBJECT_B;

There is very little difference between the two structures defined here. OBJECT_B differs from OBJECT_A only by the one integer variable. However, they are still very different in the eyes of the compiler. The functions that add, delete, or search the lists must be duplicated for each object that is to be stored in the list. To solve this problem, a union or a structure that has all three variables where integer c is not used in all cases could be used. This can become complicated and leads to poor programming style.

The C code solution: The virtual list

One of the better solutions to this problem is the virtual list. It is a list that only contains list pointers. The objects are stored behind the list structure. This is done by allocating memory for a list node plus the memory for the object and assigning the memory to the list node pointer as follows:

typedef struct liststruct
{
	liststruct *next;
} LIST, *pLIST;

pLIST Head = NULL;

pLIST AddToList( pLIST Head, void * data, size_t datasize )
{
pLIST newlist=NULL;
void *p;

    // Allocate the node and data memory
    newlist = (pLIST) malloc( datasize + sizeof( LIST ) );

    // assign a pointer to the data buffer
    p = (void *)( newlist + 1 );

    // copy the data
    memcpy( p, data, datasize );

    // assign the node to the head of the list
    if( Head )
    {
	newlist->next = Head;
    }
    else
	newlist->next = NULL;
	
    Head = newlist;

    return Head;
}

The list node now "piggy-backs" the copy of the data values. This version is fine for scalar values but will not handle objects that have elements allocated using malloc or new. To do this, the LIST structure needs to include a generic destructor function pointer that can be used to free the memory (or close files or call shutdown methods) before the node is removed from the list and destroyed.

typedef void (*ListNodeDestructor)( void * );
typedef struct liststruct
{
	ListNodeDestructor DestructFunc;
	liststruct *next;
	
} LIST, *pLIST;

pLIST AddToList( pLIST Head, void * data, size_t datasize,
ListNodeDestructor Destructor )
{
pLIST newlist=NULL;
void *p;

    // Allocate the node and data memory
    newlist = (pLIST) malloc( datasize + sizeof( LIST ) );

    // assign a pointer to the data buffer
    p = (void *)( newlist + 1 );

    // copy the data
    memcpy( p, data, datasize );

	newlist->DestructFunc = Destructor;
    
	// assign the node to the head of the list
    if( Head )
    {
		newlist->next = Head;
    }
    else
		newlist->next = NULL;
		
    Head = newlist;

	return Head;
}

void DeleteList( pLIST Head )
{
	pLIST Next;
	while( Head )
	{
		Next = Head->next;
		Head->DestructFunc( (void *) Head );
		free( Head );
		Head = Next;
	}
}
typedef struct ListDataStruct
{
	LPSTR p;
} LIST_DATA, *pLIST_DATA;

void ListDataDestructor( void *p )
{
	// cast the node pointer
	pLIST pl = (pLIST)p;
	
	// cast the data pointer
	pLIST_DATA pLD = (pLIST_DATA) ( pl + 1 );
	
	delete pLD->p;
}
pLIST Head = NULL;

void TestList()
{
	pLIST_DATA d = new LIST_DATA;
	d->p = new char[24];
	strcpy( d->p, "Hello" ); 
	Head = AddToList( Head, (void *) d, sizeof( pLIST_DATA ),
	ListDataDestructor );
	// the object is copied so now delete the original
	delete d;
	
	d = new LIST_DATA;
	d->p = new char[24];
	strcpy( d->p, "World" ); 
	Head = AddToList( Head, (void *) d, sizeof( pLIST_DATA ),
	ListDataDestructor );
	delete d;
	
	// free the list
	DeleteList( Head );
}

Including the same pointer to the same destructor in each list node looks like a waste of memory space. It is, but only if the list always contains the same object. Programming the list this way allows you to place any object in the list in any place. Most list function requires that the object is always the same type or class. The virtual list does not. All that is required is a way to differentiate the objects from one another. This could be done by testing the value of the destructor pointer or by adding a type value to the front of all of the structures used on the list and testing the value. Of course, the pointer to the destructor could be set and stored only once if the list were to be programmed as a C++ class.

The C++ solution: The list as a class

This solution defines the class CList as a class derived from the LIST structure and it stores a single destructor value to handle a single stored type. Note the added function GetCurrentData() that does the list node pointer to data offset pointer math for you.

// define the destructor function pointer 
		
typedef void (*ListNodeDestructor)( void * );

// List with no destructor pointer added

typedef struct ndliststruct
{
	ndliststruct *next;
	
} ND_LIST, *pND_LIST;

// define the list class that handles one data type

class CList : public ND_LIST
{
public:
	CList(ListNodeDestructor);
	~CList();
	pND_LIST AddToList( void * data, size_t datasize );
	void *GetCurrentData();
	void DeleteList( pND_LIST Head );
	
private:
	pND_LIST m_HeadOfList;
	pND_LIST m_CurrentNode;
	ListNodeDestructor m_DestructFunc;
};
// construct  this list class object  with the correct starting values

CList::CList(ListNodeDestructor Destructor)
	: m_HeadOfList(NULL), m_CurrentNode(NULL)
{
	m_DestructFunc = Destructor;
}

// delete the list when the object is destroyed

CList::~CList()
{
	DeleteList(m_HeadOfList);
}
// add a new node to the list
pND_LIST CList::AddToList( void * data, size_t datasize )
{
pND_LIST newlist=NULL;
void *p;

    // Allocate the node and data memory
    newlist = (pND_LIST) malloc( datasize + sizeof( ND_LIST ) );

    // assign a pointer to the data buffer
    p = (void *)( newlist + 1 );

    // copy the data
    memcpy( p, data, datasize );

	// assign the node to the head of the list
    if( m_HeadOfList )
    {
		newlist->next = m_HeadOfList;
    }
    else
		newlist->next = NULL;
		
    m_HeadOfList = newlist;

	return m_HeadOfList;
}

// return the current node data as void so calling function can cast it to any type

void * CList::GetCurrentData()
{
	return (void *)(m_CurrentNode+1);
}

// delete the allocated list

void CList::DeleteList( pND_LIST Head )
{
	pND_LIST Next;
	while( Head )
	{
		Next = Head->next;
		m_DestructFunc( (void *) Head );
		free( Head );
		Head = Next;
	}
}

// create a structure to create and store in a list

typedef struct ListDataStruct
{
	LPSTR p;
	
} LIST_DATA, *pND_LIST_DATA;

// define the standard destructor

void ClassListDataDestructor( void *p )
{
	// cast the node pointer
	pND_LIST pl = (pND_LIST)p;
	
	// cast the data pointer
	pND_LIST_DATA pLD = (pND_LIST_DATA) ( pl + 1 );
	
	delete pLD->p;
}

// test the above code

void MyCListClassTest()
{
	// create the list class
	
	CList* pA_List_of_Data = new CList(ClassListDataDestructor);
	
	// create a data object
	
	pND_LIST_DATA d = new LIST_DATA;
	d->p = new char[24];
	strcpy( d->p, "Hello" ); 
	
	// create a local pointer to the top of the list
	
	pND_LIST Head = NULL;
	
	//add some stuff to the list
	
	Head = pA_List_of_Data->AddToList( (void *) d, 
	sizeof( pND_LIST_DATA ) );
	// the object is copied so now delete the original
	delete d;
	
	// confirm it is stored
	char * p = ((pND_LIST_DATA) pA_List_of_Data->GetCurrentData())->p;
	
	d = new LIST_DATA;
	d->p = new char[24];
	strcpy( d->p, "World" ); 
	Head = pA_List_of_Data->AddToList( (void *) d, sizeof( pND_LIST_DATA ) );
	// the object is copied so now delete the original
	delete d;
	
	// confirm it is stored
	p = ((pND_LIST_DATA) pA_List_of_Data->GetCurrentData())->p;
	
	// remove the list class and the deconstructor will remove the list
	delete pA_List_of_Data;
}

Conclusion

This might look like a lot of work just to program a simple list, but it only has to be done once. It's a simple matter to expand this code into a C++ class that handles sorts, searches, and sundry other tasks and can also handle any data object or class (in one project it handles about twenty different objects). The code will never have to be written again.

Resources

Build robust, object-oriented applications on AIX with IBM's VisualAge C++.
Read about developing C/C++ applications for the AS/400.
Develop applications on the OS/390 platform with IBM's OS/390 C/C++.
Learn about the Lotus C API Toolkit for Domino.
Subscribe to the Linux C Programming Lists, which aim to help people programming Linux with C and include links to FAQs, tutorials, and more.
Browse more Linux resources on developerWorks.
Browse more Open source resources on developerWorks.

About the author

Comments (Undergoing maintenance)

Trademarks | My developerWorks terms and conditions

Close [x]

Help: Update or add to My dW interests

What's this?

This little timesaver lets you update your My developerWorks profile with just one click! The general subject of this content (AIX and UNIX, Information Management, Lotus, Rational, Tivoli, WebSphere, Java, Linux, Open source, SOA and Web services, Web development, or XML) will be added to the interests section of your profile, if it's not there already. You only need to be logged in to My developerWorks.

And what's the point of adding your interests to your profile? That's how you find other users with the same interests as yours, and see what they're reading and contributing to the community. Your interests also help us recommend relevant developerWorks content to you.

View your My developerWorks profile

Return from help

Close [x]

Help: Remove from My dW interests

What's this?

Removing this interest does not alter your profile, but rather removes this piece of content from a list of all content for which you've indicated interest. In a future enhancement to My developerWorks, you'll be able to see a record of that content.

View your My developerWorks profile

Return from help

static.content.url=http://www.ibm.com/developerworks/js/artrating/

SITE_ID=1

Zone=Linux

ArticleID=11041

ArticleTitle=Tip: Coding generic lists of objects in C/C++

publish-date=10012001

author1-email=twburger@bigfoot.com

author1-email-cc=