T
TBass
Linked lists are a big part of the project I'm working on, and memory
management of the heap seems to be the major problem with the project,
in general. So I decided to write a linked list library that I could
use throughout the program and trust that, with it working correctly,
any memory problems would be in the project code.
So now I'm looking for errors, ideas, suggestions, or warnings on
common pitfalls. The code is below.
For the most part, it has worked without error. However, today a
problem came up that I do not think is the library's fault, but I want
to be sure. My program would call the adcList_Append function and that
function would work fine. However, upon return to the program, the
"head" pointer would not be updated with its new pointer position. I
want to be sure that I've done my job properly in the code below.
If you have the need, feel free to use the code without condition.
Any suggestions or feedback is greatly appreciated, and I thank you in
advance.
NOTE: you can also post responses at http://tbjblog.blogspot.com/
Thanks!
tbj
***************************************************************
* adcList.c
* ADC Linked List Routines
*
* by Thomas C. Bitsky Jr.
* Copyright 2007 Automated Design Corporation
*
*
***************************************************************/
#include "adcList.h"
#include
/***************************************************************
* adcList_Length
* Return the number of elements in a list.
***************************************************************/
int
adcList_Length( ADCLIST *pHead )
{
int ret;
int count;
ADCLIST *pList;
pList = pHead;
count = 0;
while ( pList != NULL )
{
count += 1;
pList = pList->pNext;
}
ret = count;
return ret;
} /* adcList_Length */
/***************************************************************
* adcList_Push
* Push a new item at the head of the list. Returns TRUE if
* successful, FALSE if not.
*
* This function will re-address ppHead. The head
* always stays at the top (last pushed) item on the
* list.
*
* MAKE SURE THAT ppHead IS NULL IF THIS IS THE FIRST
* ITEM ADDED TO THE LIST!
*
* This function is the naturally faster of the two add
* functions -- it has less to do. The compromise is that it
* items are FILO ordered. When order doesn't matter or speed
* is a serious concern, go with the Push function.
***************************************************************/
int
adcList_Push( ADCLIST **ppHead, void *pData )
{
int ret;
ADCLIST *pNewNode;
pNewNode = (ADCLIST *)malloc( sizeof( struct ADCLIST_el ) );
if ( pNewNode != NULL )
{
pNewNode->pData = pData;
pNewNode->pNext = *ppHead;
pNewNode->pPrev = NULL;
*ppHead = (ADCLIST *)pNewNode;
ret = TRUE;
}
else
{
ret = FALSE;
}
return ret;
} /* adcList_Push */
/***************************************************************
* adcList_Append
* Append a new item at the end of the list. Returns TRUE if
* successful, FALSE if not.
*
* This function does not re-address ppHead. The head
* always stays at the top (last pushed) item on the
* list.
*
* MAKE SURE THAT ppHead IS NULL IF THIS IS THE FIRST
* ITEM ADDED TO THE LIST!
*
* This function is the naturally slower of the two add
* functions -- it has more to do. The the items are ordered
* in a nice FIFO list. When order matters, go with Append.
***************************************************************/
int
adcList_Append( ADCLIST **ppHead, void *pData )
{
int ret;
ADCLIST *pList;
ADCLIST *pNewNode;
pList = *ppHead;
if ( pList == NULL )
{
ret = adcList_Push( &pList, pData );
}
else
{
/* LOCATE THE LAST NODE */
while( pList->pNext != NULL )
{
pList = pList->pNext;
}
pNewNode = malloc( sizeof( ADCLIST ) );
if ( pNewNode != NULL )
{
pNewNode->pData = pData;
pNewNode->pNext = NULL;
pNewNode->pPrev = pList;
pList->pNext = pNewNode;
ret = TRUE;
}
else
{
ret = FALSE;
}
}
return ret;
} /* adcList_Append */
/***************************************************************
* adcList_Pop
* Free the passed item on the list.
***************************************************************/
int
adcList_Pop( ADCLIST **ppHead, ADCLIST **ppNode )
{
int ret;
ADCLIST *pList;
ADCLIST *pTemp;
pList = *ppNode;
if ( pList != NULL )
{
/* IS THIS THE HEAD OF THE LIST? */
if ( *ppHead == pList )
{
pTemp = pList->pNext;
pTemp->pPrev = NULL;
*ppHead = pTemp;
}
else
{
/* NO -- SKIP OVER THE ITEM */
pTemp = pList->pPrev;
pTemp->pNext = pList->pNext;
}
/* FREE THE ITEM */
free( pList->pData );
pList->pData = NULL;
free( pList );
*ppNode = NULL;
ret = TRUE;
}
else
{
ret = FALSE;
}
return ret;
} /* adcList_Pop */
/***************************************************************
* adcList_Free
* Free all items on a list, including whatever is
* in the ->pData member. ppHead is set to NULL.
* Always returns TRUE.
***************************************************************/
int
adcList_Free( ADCLIST **ppHead )
{
ADCLIST *pList;
ADCLIST *pTmp;
pList = *ppHead;
while( pList != NULL )
{
free( pList->pData );
pTmp = pList->pNext;
free( pList );
pList = pTmp;
}
*ppHead = NULL;
return TRUE;
} /* adcList_Free */
/***************************************************************
* adcList.h
* ADC Linked List Routines
*
* by Thomas C. Bitsky Jr.
* Copyright 2007 Automated Design Corporation
*
*
***************************************************************/
#ifndef _ADC_LIST_H_
#define _ADC_LIST_H_
#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif
#ifndef NULL
#define NULL 0
#endif
typedef struct ADCLIST_el
{
struct ADCLIST_el *pPrev;
struct ADCLIST_el *pNext;
void *pData;
} ADCLIST_el;
typedef ADCLIST_el ADCLIST;
/***************************************************************
* adcList_Length
* Returns the number of items in a given list.
* A negative result indicates a failure.
***************************************************************/
int
adcList_Length( ADCLIST *pHead );
/***************************************************************
* adcList_Push
* Push a new item at the head of the list. Returns TRUE if
* successful, FALSE if not.
*
* This function is the naturally faster of the two add
* functions -- it has less to do. The compromise is that it
* items are FILO ordered. When order doesn't matter or speed
* is a serious concern, go with the Push function.
***************************************************************/
int
adcList_Push( ADCLIST **ppHead, void *pData );
/***************************************************************
* adcList_Append
* Append a new item at the end of the list. Returns TRUE if
* successful, FALSE if not.
*
* This function is the naturally slower of the two add
* functions -- it has more to do. The the items are ordered
* in a nice FIFO list. When order matters, go with Append.
***************************************************************/
int
adcList_Append( ADCLIST **ppHead, void *pData );
/***************************************************************
* adcList_Pop
* Free the passed item on the list.
***************************************************************/
int
adcList_Pop( ADCLIST **ppHead, ADCLIST **ppNode );
/***************************************************************
* adcList_Free
* Free all items on a list, including whatever is
* in the ->pData member. ppHead is set to NULL.
* Always returns TRUE.
***************************************************************/
int
adcList_Free( ADCLIST **ppHead );
management of the heap seems to be the major problem with the project,
in general. So I decided to write a linked list library that I could
use throughout the program and trust that, with it working correctly,
any memory problems would be in the project code.
So now I'm looking for errors, ideas, suggestions, or warnings on
common pitfalls. The code is below.
For the most part, it has worked without error. However, today a
problem came up that I do not think is the library's fault, but I want
to be sure. My program would call the adcList_Append function and that
function would work fine. However, upon return to the program, the
"head" pointer would not be updated with its new pointer position. I
want to be sure that I've done my job properly in the code below.
If you have the need, feel free to use the code without condition.
Any suggestions or feedback is greatly appreciated, and I thank you in
advance.
NOTE: you can also post responses at http://tbjblog.blogspot.com/
Thanks!
tbj
***************************************************************
* adcList.c
* ADC Linked List Routines
*
* by Thomas C. Bitsky Jr.
* Copyright 2007 Automated Design Corporation
*
*
***************************************************************/
#include "adcList.h"
#include
/***************************************************************
* adcList_Length
* Return the number of elements in a list.
***************************************************************/
int
adcList_Length( ADCLIST *pHead )
{
int ret;
int count;
ADCLIST *pList;
pList = pHead;
count = 0;
while ( pList != NULL )
{
count += 1;
pList = pList->pNext;
}
ret = count;
return ret;
} /* adcList_Length */
/***************************************************************
* adcList_Push
* Push a new item at the head of the list. Returns TRUE if
* successful, FALSE if not.
*
* This function will re-address ppHead. The head
* always stays at the top (last pushed) item on the
* list.
*
* MAKE SURE THAT ppHead IS NULL IF THIS IS THE FIRST
* ITEM ADDED TO THE LIST!
*
* This function is the naturally faster of the two add
* functions -- it has less to do. The compromise is that it
* items are FILO ordered. When order doesn't matter or speed
* is a serious concern, go with the Push function.
***************************************************************/
int
adcList_Push( ADCLIST **ppHead, void *pData )
{
int ret;
ADCLIST *pNewNode;
pNewNode = (ADCLIST *)malloc( sizeof( struct ADCLIST_el ) );
if ( pNewNode != NULL )
{
pNewNode->pData = pData;
pNewNode->pNext = *ppHead;
pNewNode->pPrev = NULL;
*ppHead = (ADCLIST *)pNewNode;
ret = TRUE;
}
else
{
ret = FALSE;
}
return ret;
} /* adcList_Push */
/***************************************************************
* adcList_Append
* Append a new item at the end of the list. Returns TRUE if
* successful, FALSE if not.
*
* This function does not re-address ppHead. The head
* always stays at the top (last pushed) item on the
* list.
*
* MAKE SURE THAT ppHead IS NULL IF THIS IS THE FIRST
* ITEM ADDED TO THE LIST!
*
* This function is the naturally slower of the two add
* functions -- it has more to do. The the items are ordered
* in a nice FIFO list. When order matters, go with Append.
***************************************************************/
int
adcList_Append( ADCLIST **ppHead, void *pData )
{
int ret;
ADCLIST *pList;
ADCLIST *pNewNode;
pList = *ppHead;
if ( pList == NULL )
{
ret = adcList_Push( &pList, pData );
}
else
{
/* LOCATE THE LAST NODE */
while( pList->pNext != NULL )
{
pList = pList->pNext;
}
pNewNode = malloc( sizeof( ADCLIST ) );
if ( pNewNode != NULL )
{
pNewNode->pData = pData;
pNewNode->pNext = NULL;
pNewNode->pPrev = pList;
pList->pNext = pNewNode;
ret = TRUE;
}
else
{
ret = FALSE;
}
}
return ret;
} /* adcList_Append */
/***************************************************************
* adcList_Pop
* Free the passed item on the list.
***************************************************************/
int
adcList_Pop( ADCLIST **ppHead, ADCLIST **ppNode )
{
int ret;
ADCLIST *pList;
ADCLIST *pTemp;
pList = *ppNode;
if ( pList != NULL )
{
/* IS THIS THE HEAD OF THE LIST? */
if ( *ppHead == pList )
{
pTemp = pList->pNext;
pTemp->pPrev = NULL;
*ppHead = pTemp;
}
else
{
/* NO -- SKIP OVER THE ITEM */
pTemp = pList->pPrev;
pTemp->pNext = pList->pNext;
}
/* FREE THE ITEM */
free( pList->pData );
pList->pData = NULL;
free( pList );
*ppNode = NULL;
ret = TRUE;
}
else
{
ret = FALSE;
}
return ret;
} /* adcList_Pop */
/***************************************************************
* adcList_Free
* Free all items on a list, including whatever is
* in the ->pData member. ppHead is set to NULL.
* Always returns TRUE.
***************************************************************/
int
adcList_Free( ADCLIST **ppHead )
{
ADCLIST *pList;
ADCLIST *pTmp;
pList = *ppHead;
while( pList != NULL )
{
free( pList->pData );
pTmp = pList->pNext;
free( pList );
pList = pTmp;
}
*ppHead = NULL;
return TRUE;
} /* adcList_Free */
/***************************************************************
* adcList.h
* ADC Linked List Routines
*
* by Thomas C. Bitsky Jr.
* Copyright 2007 Automated Design Corporation
*
*
***************************************************************/
#ifndef _ADC_LIST_H_
#define _ADC_LIST_H_
#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif
#ifndef NULL
#define NULL 0
#endif
typedef struct ADCLIST_el
{
struct ADCLIST_el *pPrev;
struct ADCLIST_el *pNext;
void *pData;
} ADCLIST_el;
typedef ADCLIST_el ADCLIST;
/***************************************************************
* adcList_Length
* Returns the number of items in a given list.
* A negative result indicates a failure.
***************************************************************/
int
adcList_Length( ADCLIST *pHead );
/***************************************************************
* adcList_Push
* Push a new item at the head of the list. Returns TRUE if
* successful, FALSE if not.
*
* This function is the naturally faster of the two add
* functions -- it has less to do. The compromise is that it
* items are FILO ordered. When order doesn't matter or speed
* is a serious concern, go with the Push function.
***************************************************************/
int
adcList_Push( ADCLIST **ppHead, void *pData );
/***************************************************************
* adcList_Append
* Append a new item at the end of the list. Returns TRUE if
* successful, FALSE if not.
*
* This function is the naturally slower of the two add
* functions -- it has more to do. The the items are ordered
* in a nice FIFO list. When order matters, go with Append.
***************************************************************/
int
adcList_Append( ADCLIST **ppHead, void *pData );
/***************************************************************
* adcList_Pop
* Free the passed item on the list.
***************************************************************/
int
adcList_Pop( ADCLIST **ppHead, ADCLIST **ppNode );
/***************************************************************
* adcList_Free
* Free all items on a list, including whatever is
* in the ->pData member. ppHead is set to NULL.
* Always returns TRUE.
***************************************************************/
int
adcList_Free( ADCLIST **ppHead );