Easier Linked Lists: A real world application of code reviews

  • Article

Last year, I recommended that everyone read Steve Maguire's Writing Solid Code.  Today, I was reminded why I made that recommendation.

I have been working on a native (C/C++) application recently and decided that my logging code would be best served by a linked list.  During the code review, it was pointed out that I did things the hard way.

Please note that the following applies to all snippets contained in this text.
//--------------------------------------------------------------------- //THIS CODE AND INFORMATION ARE PROVIDED AS IS WITHOUT WARRANTY OF ANY //KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE //IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR A //PARTICULAR PURPOSE. //---------------------------------------------------------------------

Before I go into the before and after examples, we need a definition for the linked list node structure. 
typedef struct _ListNode{    struct _ListNode *pNext;    int Data;} LISTNODE, *PLISTNODE;

I also created a module variable to point to my list.
PLISTNODE _pList = NULL;

And now back to the story...

I mentioned that my original implementation did things the hard way.  By "hard way", I mean that my code had to special case a few scenarios, as you can see from the snippets below.

First, adding an element to the list (note the special case, highlighted in purple, for if the new node is to be the head of the list).
HRESULT AddElement(int data){    PLISTNODE pList = _pList;    PLISTNODE pNode = LocalAlloc(LMEM_FIXED, sizeof(LISTNODE));    if(NULL == pNode)    {        // failed to allocate memory        return E_OUTOFMEMORY;    }    // populate the node    pNode->pNext = NULL;    pNode->Data = data;    // append the new node    if(NULL == pList) { // make the new node the list head _pList = pNode; }    else    {        // append the new node to the end of the list        while(pList)        {            pList = pList->pNext;        }        pList->pNext = pNode;    }    return S_OK;}

Next up, the removal code (again, note the special case, highlighted in purple, for removing the list head).  For my purposes, the data was typically going to be added to the list only once.  Since I was not checking for duplication when adding to the list, the removal function will remove the first instance of the data in the list.  If duplicates are an issue, or if removing an exact list element is important, a more robust system would need to be employed.
HRESULT RemoveElement(int data){    PLISTNODE pList = _pList;    PLISTNODE pPrev = NULL;    PLISTNODE pNode = NULL;    pPrev = NULL;    while(pList)    {        if(data == pList->Data)        {            // remove pNode            pNode = pList;            // check for removing the head of the list if(NULL == pPrev) { // TODO: Remove the list head }            else            {                // TODO: Remove a non-head list element            }        }        else        {            // we have not yet found the element we are looking for            //   update where we are in the list            pPrev = pList;            pList = pList->pNext;        }    }    return S_OK;}

Now that I could add and remove from my list, I could use the data.
HRESULT ProcessListData(){    PLISTNODE pList = _pList;    while(pList)    {        // TODO: Process the data in the node        pList = pList->pNext;    }    return S_OK;}

This is all pretty straight forward and how I often see list code written.  After some quick testing, I was satisfied with the behavior (pending more testing, of course) and requested my code review.  During the review, I was reminded that if you pre-allocate the list head, the add and remove functions become much easier to write and to test.  The special casing for the list head is no longer needed.

We start by changing the module variable from a pointer to the list to be the head element.
LISTNODE _List;

Then update the add and remove functions.
HRESULT AddElement(int data){    PLISTNODE pList = &_List;    PLISTNODE pNode = LocalAlloc(LMEM_FIXED, sizeof(LISTNODE));    if(NULL == pNode)   {        // failed to allocate memory        return E_OUTOFMEMORY;    }    // populate the new node    pNode->pNext = NULL;    pNode->Data = data;    // append the new node to the end of the list    while(pList->pNext)    {        pList = pList->pNext;    }    pList->pNext = pNode;    return S_OK;}

HRESULT RemoveElement(int data){    PLISTNODE pList = &_List;    PLISTNODE pPrev = NULL;    PLISTNODE pNode = NULL;    while(pList)    {        pPrev = pList;        if(data == pList->Data)        {            pNode = pList;            // TODO: remove pNode        }        else        {            // we have not yet found the element we are looking for            //   update where we are in the list            pList = pList->pNext;        }    }    return S_OK;}

The only place where special handling of the list head is required is in data processing.
HRESULT ProcessListData(){    PLISTNODE pList = &_List;    // bypass the head of the list at the start of the loop     while(pList->pNext)    {        // TODO: Process the data in the node        pList = pList->pNext;    }    return S_OK;}

Special casing is typically where bugs creep into code.  Whenever a special case is implemented, it must have a test which specifically covers that scenario.  By eliminating this extra code, the same algorithm is run every time the function is called.  Even though we "special cased" the skipping of the list head when processing the data, the code runs the same way every time (the head is always bypassed).  Of course, there are times where you cannot avoid implementing and testing special case code (failing to allocate memory, for example) though these scenarios are likely part of your normal error handling logic.

Take care,
-- DK

Disclaimer(s):
This posting is provided "AS IS" with no warranties, and confers no rights.

Comments

  • Anonymous
    April 25, 2006
    The comment has been removed