Linked List Library

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 );
 
U

user923005

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 athttp://tbjblog.blogspot.com/

Thanks!
tbj
Click to expand...
[snip]
What you have done here is a naughty no-no.
#ifndef _ADC_LIST_H_
#define _ADC_LIST_H_
Click to expand...

While making header files idempotent is a very good idea, you have
used macros that begin with an underscore followed by a capital
letter. That's not allowed because it belongs to the implementation
namespace.

From:
ISO/IEC ISO/IEC 9899:1999 (E)

6.10.8 Predefined macro names
1 The following macro names148) shall be defined by the
implementation:
__DATE__ The date of translation of the preprocessing translation
unit: a character string literal of the form "Mmm dd yyyy", where the
names of the months are the same as those generated by the asctime
function, and the first character of dd is a space character if the
value is less than 10. If the date of translation is not available, an
implementation-defined valid date shall be supplied.
__FILE__ The presumed name of the current source file (a character
string literal).149)
__LINE__ The presumed line number (within the current source file) of
the current source line (an integer constant).149)
__STDC__ The integer constant 1, intended to indicate a conforming
implementation.
__STDC_HOSTED__ The integer constant 1 if the implementation is a
hosted implementation or the integer constant 0 if it is not.
__STDC_VERSION__ The integer constant 199901L.150)
__TIME__ The time of translation of the preprocessing translation
unit: a character string literal of the form "hh:mm:ss" as in the time
generated by the asctime function. If the time of translation is not
available, an implementation-defined valid time shall be supplied.
2 The following macro names are conditionally defined by the
implementation:
__STDC_IEC_559__ The integer constant 1, intended to indicate
conformance to the specifications in annex F (IEC 60559 floating-point
arithmetic).
__STDC_IEC_559_COMPLEX__ The integer constant 1, intended to indicate
adherence to the specifications in informative annex G (IEC 60559
compatible complex arithmetic).
__STDC_ISO_10646__ An integer constant of the form yyyymmL (for
example, 199712L), intended to indicate that values of type wchar_t
are the coded representations of the characters defined by ISO/IEC
10646, along with all amendments and technical corrigenda as of the
specified year and month.
3 The values of the predefined macros (except for __FILE__ and
__LINE__) remain constant throughout the translation unit.
4 None of these macro names, nor the identifier defined, shall be the
subject of a #define or a #undef preprocessing directive. Any other
predefined macro names shall begin with a leading underscore followed
by an uppercase letter or a second underscore.
5 The implementation shall not predefine the macro __cplusplus, nor
shall it define it in any standard header.

Forward references: the asctime function (7.23.3.1), standard headers
(7.1.2).

Footnotes:
148) See ''future language directions'' (6.11.9).
149) The presumed source file name and line number can be changed by
the #line directive.
150) This macro was not specified in ISO/IEC 9899:1990 and was
specified as 199409L in ISO/IEC 9899/AMD1:1995. The intention is that
this will remain an integer constant of type long int that is
increased with each revision of this International Standard.
 
B

Ben Pfaff

TBass said:
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.
Click to expand...

Then writing a good test suite for your library should be a high
priority. Have you written a test suite?
 
T

TBass

[snip]
Then writing a good test suite for your library should be a high
priority. Have you written a test suite?
--
Click to expand...
[/snip]


It was, and everything checked out in testing. Then today I ran into
this problem:


typedef struct DGRIDCOL_el
{

char name[255];
int type;
int colnum;
BOOL IsKey;

} DGRIDCOL_el;

typedef DGRIDCOL_el DGRIDCOL;

typedef struct DGRIDINT_el
{

char pDBLocation[255];
char pDBName[255];
char pTBName[255];

int iDisplayRows;
int iDisplayCols;

unsigned int iRowHeight;
unsigned int iColWidth;

DFONT *dfont;

ADCLIST *listCells;
ADCLIST *listColumns;
sqlite3 *pDB;


sqlite3_stmt *pDB_result;
/* STORES THE NUMBER OF COLUMNS IN A RESULT */
int resultCols;

/* STORES THE NUMBER OF ROWS CURRENTLY ON DISPLAY */
int rowsDisplayed;
/* STORES THE NUMBER OF COLS CURRENTLY ON DISPLAY */
int colsDisplayed;


} DGRIDINT_el;

typedef DGRIDINT_el DGRIDINT;


int
dGrid_testColumnList( DGRIDINT *pGrid )
{
int ret;
DGRIDCOL *p_col;
int x;

p_col = malloc( sizeof( DGRIDCOL ) );
if ( p_col == NULL )
{
ret = FALSE;
goto Quit;
}


pGrid->listColumns = NULL;

printf("BEGIN TEST LIST:: pGrid->listColumns = %d\n", pGrid-
listColumns );
Click to expand...

/* OUTPUT: BEGIN TEST LIST:: pGrid->listColumns = 0 */

strcpy(p_col->name, "Mytestcol" );
p_col->type = 1;
p_col->IsKey = FALSE;


for( x=0;x<5;x++ )
{
p_col->colnum = x;

if ( !adcList_Append( &pGrid->listColumns, (void *)p_col ) )
{
ret = FALSE;
goto Quit;
}
else
{
printf("APPEND GOOD:: pGrid->listColumns = %d\n", pGrid-
listColumns );
Click to expand...
/* OUTPUT: APPEND GOOD:: pGrid->listColumns =
0 */
/* pGrid->listColumns is still NULL, even
though Append malloc'd memory for it and */
/* set the value of the pointer */
/* For everything else in the program, the
ADCLIST library works. But for this member of */
/* of this structure, when _Append returns,
its is still set to NULL */

}

}

ret = TRUE;

Quit:
return ret;

}
 
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.
Click to expand...
So now I'm looking for errors, ideas, suggestions, or warnings on
common pitfalls. The code is below.
Click to expand...
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.
Click to expand...
If you have the need, feel free to use the code without condition.
Click to expand...
Any suggestions or feedback is greatly appreciated, and I thank you in
advance.
Click to expand...
NOTE: you can also post responses athttp://tbjblog.blogspot.com/
Click to expand...
Thanks!
tbj
Click to expand...

[snip]
What you have done here is a naughty no-no.
#ifndef _ADC_LIST_H_
#define _ADC_LIST_H_
Click to expand...

While making header files idempotent is a very good idea, you have
used macros that begin with an underscore followed by a capital
letter. That's not allowed because it belongs to the implementation
namespace.

From:
ISO/IEC ISO/IEC 9899:1999 (E)

6.10.8 Predefined macro names
1 The following macro names148) shall be defined by the
implementation:
__DATE__ The date of translation of the preprocessing translation
unit: a character string literal of the form "Mmm dd yyyy", where the
names of the months are the same as those generated by the asctime
function, and the first character of dd is a space character if the
value is less than 10. If the date of translation is not available, an
implementation-defined valid date shall be supplied.
__FILE__ The presumed name of the current source file (a character
string literal).149)
__LINE__ The presumed line number (within the current source file) of
the current source line (an integer constant).149)
__STDC__ The integer constant 1, intended to indicate a conforming
implementation.
__STDC_HOSTED__ The integer constant 1 if the implementation is a
hosted implementation or the integer constant 0 if it is not.
__STDC_VERSION__ The integer constant 199901L.150)
__TIME__ The time of translation of the preprocessing translation
unit: a character string literal of the form "hh:mm:ss" as in the time
generated by the asctime function. If the time of translation is not
available, an implementation-defined valid time shall be supplied.
2 The following macro names are conditionally defined by the
implementation:
__STDC_IEC_559__ The integer constant 1, intended to indicate
conformance to the specifications in annex F (IEC 60559 floating-point
arithmetic).
__STDC_IEC_559_COMPLEX__ The integer constant 1, intended to indicate
adherence to the specifications in informative annex G (IEC 60559
compatible complex arithmetic).
__STDC_ISO_10646__ An integer constant of the form yyyymmL (for
example, 199712L), intended to indicate that values of type wchar_t
are the coded representations of the characters defined by ISO/IEC
10646, along with all amendments and technical corrigenda as of the
specified year and month.
3 The values of the predefined macros (except for __FILE__ and
__LINE__) remain constant throughout the translation unit.
4 None of these macro names, nor the identifier defined, shall be the
subject of a #define or a #undef preprocessing directive. Any other
predefined macro names shall begin with a leading underscore followed
by an uppercase letter or a second underscore.
5 The implementation shall not predefine the macro __cplusplus, nor
shall it define it in any standard header.

Forward references: the asctime function (7.23.3.1), standard headers
(7.1.2).

Footnotes:
148) See ''future language directions'' (6.11.9).
149) The presumed source file name and line number can be changed by
the #line directive.
150) This macro was not specified in ISO/IEC 9899:1990 and was
specified as 199409L in ISO/IEC 9899/AMD1:1995. The intention is that
this will remain an integer constant of type long int that is
increased with each revision of this International Standard.
[snip]
What you have done here is a naughty no-no.
#ifndef _ADC_LIST_H_
#define _ADC_LIST_H_
Click to expand...

While making header files idempotent is a very good idea, you have
used macros that begin with an underscore followed by a capital
letter. That's not allowed because it belongs to the implementation
namespace.
Click to expand...
[/snip]

I was not aware of that. So I shall plan to change to:

#ifndef ADC_LIST_H
#define ADC_LIST_H
 
B

Ben Pfaff

TBass said:
Then writing a good test suite for your library should be a high
priority. Have you written a test suite?
Click to expand...

It was, and everything checked out in testing. Then today I ran into
this problem: [...]
Click to expand...

That leaves two possibilities. First, your test suite may not be
thorough enough. Second, your program may be using it
incorrectly, for example by passing to it memory that it does not
own, or by writing beyond the end of allocated memory. In either
case, one good approach to debugging can be to use a memory
debugger, such as Electric Fence or valgrind on Linux or
system-specific tools on other platforms. Have you tried such
tools?
 
T

TBass

[snip]
Have you tried such
tools?
Click to expand...
[/snip]

No, I'm on Win32 and don't have any. Any recommendations?

It was, and everything checked out in testing. Then today I ran into
this problem: [...]
Click to expand...

That leaves two possibilities. First, your test suite may not be
thorough enough. Second, your program may be using it
incorrectly, for example by passing to it memory that it does not
own, or by writing beyond the end of allocated memory. In either
case, one good approach to debugging can be to use a memory
debugger, such as Electric Fence or valgrind on Linux or
system-specific tools on other platforms. Have you tried such
tools?
--
char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa67f6aaa,0xaa9aa9f6,0x11f6},*p
=b,i=24;for(;p+=!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
2:{i++;if(i)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}
Click to expand...
 
T

TBass

[snip]
or by writing beyond the end of allocated memory.
[/snip]


That leads to a question I have. When I malloc the structure, I use
the following statement:


pNewNode = (ADCLIST *)malloc( sizeof( ADCLIST ) );

Where:

typedef struct ADCLIST_el
{
struct ADCLIST_el *pPrev;
struct ADCLIST_el *pNext;
void *pData;

} ADCLIST_el;

typedef ADCLIST_el ADCLIST;

Is that the proper way to get the size of memory that the structure
will contain?
 
B

Ben Pfaff

TBass said:
When I malloc the structure, I use
the following statement:


pNewNode = (ADCLIST *)malloc( sizeof( ADCLIST ) );
Click to expand...

I don't recommend casting the return value of malloc():

* The cast is not required in ANSI C.

* Casting its return value can mask a failure to #include
<stdlib.h>, which leads to undefined behavior.

* If you cast to the wrong type by accident, odd failures can
result.

In unusual circumstances it may make sense to cast the return value of
malloc(). P. J. Plauger, for example, has good reasons to want his
code to compile as both C and C++, and C++ requires the cast, as he
explained in article <[email protected]>.
However, Plauger's case is rare indeed. Most programmers should write
their code as either C or C++, not in the intersection of the two.

When calling malloc(), I recommend using the sizeof operator on
the object you are allocating, not on the type. For instance,
*don't* write this:

int *x = malloc (128 * sizeof (int)); /* Don't do this! */

Instead, write it this way:

int *x = malloc (128 * sizeof *x);

There's a few reasons to do it this way:

* If you ever change the type that `x' points to, it's not
necessary to change the malloc() call as well.

This is more of a problem in a large program, but it's still
convenient in a small one.

* Taking the size of an object makes writing the statement
less error-prone. You can verify that the sizeof syntax is
correct without having to look at the declaration.
Where:

typedef struct ADCLIST_el
{
struct ADCLIST_el *pPrev;
struct ADCLIST_el *pNext;
void *pData;

} ADCLIST_el;

typedef ADCLIST_el ADCLIST;
Click to expand...

That's two more 'typedef's than you really need. I rarely see
more than one for any given structure. I personally don't use
any at all for structures, in ordinary circumstances.
Is that the proper way to get the size of memory that the structure
will contain?
Click to expand...

It's OK, but not the way that I would write it.
 
T

TBass

Thank you very much for your insights.


My other question is this:

Let's say I malloc that structure:

pNewList = malloc( sizeof *pNewList );

And now I want to point the pData member to a piece of data (usually a
structure) that I have already malloc'd elsewhere. I just want to
store a pointer to it. My thinking was, when I wrote the library, that
all I had to do was:

pNewList->pData = (void *)p_MyStructure;

But now I'm wondering if what I need to do is add a size member and:

pNewList->data_size = sizeof *p_MyStructure;
pNewList->pData = malloc( sizeof *p_MyStructure );
memcpy( pNewList->pData, p_MyStructure, sizeof *pMyStructure );
/* or maybe movmem */

And maybe that will keep the memory better organized.


TBass said:
When I malloc the structure, I use
the following statement:
Click to expand...
pNewNode = (ADCLIST *)malloc( sizeof( ADCLIST ) );
Click to expand...

I don't recommend casting the return value of malloc():

* The cast is not required in ANSI C.

* Casting its return value can mask a failure to #include
<stdlib.h>, which leads to undefined behavior.

* If you cast to the wrong type by accident, odd failures can
result.

In unusual circumstances it may make sense to cast the return value of
malloc(). P. J. Plauger, for example, has good reasons to want his
code to compile as both C and C++, and C++ requires the cast, as he
explained in article <[email protected]>.
However, Plauger's case is rare indeed. Most programmers should write
their code as either C or C++, not in the intersection of the two.

When calling malloc(), I recommend using the sizeof operator on
the object you are allocating, not on the type. For instance,
*don't* write this:

int *x = malloc (128 * sizeof (int)); /* Don't do this! */

Instead, write it this way:

int *x = malloc (128 * sizeof *x);

There's a few reasons to do it this way:

* If you ever change the type that `x' points to, it's not
necessary to change the malloc() call as well.

This is more of a problem in a large program, but it's still
convenient in a small one.

* Taking the size of an object makes writing the statement
less error-prone. You can verify that the sizeof syntax is
correct without having to look at the declaration.
Where:
Click to expand...
typedef struct ADCLIST_el
{
struct ADCLIST_el *pPrev;
struct ADCLIST_el *pNext;
void *pData;
Click to expand...
} ADCLIST_el;
Click to expand...
typedef ADCLIST_el ADCLIST;
Click to expand...

That's two more 'typedef's than you really need. I rarely see
more than one for any given structure. I personally don't use
any at all for structures, in ordinary circumstances.
Is that the proper way to get the size of memory that the structure
will contain?
Click to expand...

It's OK, but not the way that I would write it.
--
char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa67f6aaa,0xaa9aa9f6,0x11f6},*p
=b,i=24;for(;p+=!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
2:{i++;if(i)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}
Click to expand...
 
I

Ian Collins

TBass said:
Thank you very much for your insights.


My other question is this:

Let's say I malloc that structure:

pNewList = malloc( sizeof *pNewList );

And now I want to point the pData member to a piece of data (usually a
structure) that I have already malloc'd elsewhere. I just want to
store a pointer to it. My thinking was, when I wrote the library, that
all I had to do was:

pNewList->pData = (void *)p_MyStructure;
Click to expand...
You don't have to cast to void*.
But now I'm wondering if what I need to do is add a size member and:

pNewList->data_size = sizeof *p_MyStructure;
pNewList->pData = malloc( sizeof *p_MyStructure );
memcpy( pNewList->pData, p_MyStructure, sizeof *pMyStructure );
/* or maybe movmem */

And maybe that will keep the memory better organized.
Click to expand...
How?

What reason do you a=have for keeping the size?
 
T

TBass

[snip]
How?
Click to expand...
[/snip]

It doesn't. I thought about it some more and can't find a good reason
it would help.

Anyway, I think I solved the problem. It's in the Append function:

int
adcList_Append( ADCLIST **ppHead, void *pData )
{
int ret;
ADCLIST *pList;
ADCLIST *pNewNode;

pList = *ppHead;

if ( pList == NULL )
{
ret = adcList_Push( &pList, pData );
^^^^^^^^^
}


replaced with:
ret = adcList_Push( ppHead, pData );
^^^^^^^^^

Stupid, stupid, stupid.
 
D

Duncan Muirhead

On Thu, 20 Sep 2007 18:33:27 -0700, TBass wrote:

So now I'm looking for errors, ideas, suggestions, or warnings on
common pitfalls. The code is below.
Click to expand...
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;
Click to expand...

You need to update the pPrev field of pNewNodes's successor, ie
pNewNode->pNext->pPrev = pNewNode;

/***************************************************************
* 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;
Click to expand...

You need top update the pPrev field of pTemp's successor ie
pTemp->pNext->pPrev = pTemp;

<snip>
 
P

pete

TBass wrote:
/***************************************************************
* 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 );
Click to expand...

My append list function, returns the tail.
It's used like this:
http://www.mindspring.com/~pfilandr/C/list_library/string_sort.c

tail = head = NULL;
for (index = 0; index != NMEMB(string); ++index) {
tail = append_string(&head, tail, string[index]);
if (tail == NULL) {
list_free(head, free);
puts("malloc trouble!");
exit(EXIT_FAILURE);
}
}


http://www.mindspring.com/~pfilandr/C/list_library/list_string.c

struct list_node *append_string(struct list_node **head,
struct list_node *tail,
char *string)
{
struct list_node *node;

node = malloc(sizeof *node);
if (node != NULL) {
node -> next = NULL;
node -> data = malloc(strlen(string) + 1);
if (node -> data != NULL) {
strcpy(node -> data, string);
if (*head != NULL) {
tail -> next = node;
} else {
*head = node;
}
} else {
free(node);
node = NULL;
}
}
return node;
}
 
M

Michal Nazarewicz

TBass said:
***************************************************************
Click to expand...

Missing "/".
* adcList.c
* ADC Linked List Routines
*
* by Thomas C. Bitsky Jr.
* Copyright 2007 Automated Design Corporation
*
*
***************************************************************/

#include "adcList.h"
#include
Click to expand...

Missing header name.

int
Click to expand...

How about size_t? Or at least unsigned?
adcList_Length( ADCLIST *pHead ) {
int ret;
Click to expand...

Remove, see below.
int count;
Click to expand...

int count = 0;
ADCLIST *pList;

pList = pHead;
count = 0;
Click to expand...

Remove this one line.
while ( pList != NULL ) {
count += 1;
pList = pList->pNext;
}
Click to expand...

for (pList = pHead; pList; pList = pList->pNext) {
++count;
}
ret = count;
return ret;
Click to expand...

Uhm... What's wrong with "return count;"?
} /* adcList_Length */

int adcList_Push( ADCLIST **ppHead, void *pData ) {
int ret;
ADCLIST *pNewNode;

pNewNode = (ADCLIST *)malloc( sizeof( struct ADCLIST_el ) );
Click to expand...

pNewNode = malloc(sizeof *pNewNode);
if ( pNewNode != NULL ) {

pNewNode->pData = pData;
pNewNode->pNext = *ppHead;
pNewNode->pPrev = NULL;
Click to expand...

If this is double linked list you are missing some code:

if (*ppHead) {
(*ppHead)->pPrev = pNewNode;
}
*ppHead = (ADCLIST *)pNewNode;
Click to expand...

*ppHead = pNewNode;
ret = TRUE;
} else {
ret = FALSE;
}

return ret;

} /* adcList_Push */

int adcList_Append( ADCLIST **ppHead, void *pData ) {
int ret;
ADCLIST *pList;
ADCLIST *pNewNode;

pList = *ppHead;

if ( pList == NULL ) {
ret = adcList_Push( &pList, pData );
} else {
Click to expand...

pNewNode = malloc(sizeof *pNewNode);
if (!pNewNode) {
ret = FALSE;
} else {
/* LOCATE THE LAST NODE */
while( pList->pNext != NULL ) pList = pList->pNext;

pNewNode = malloc( sizeof( ADCLIST ) );
if ( pNewNode != NULL ) {
Click to expand...

Remove those two lines (see above).
pNewNode->pData = pData;
pNewNode->pNext = NULL;
pNewNode->pPrev = pList;
pList->pNext = pNewNode;

ret = TRUE;
}
else { ret = FALSE; }
Click to expand...

Remove the last line.
}

return ret;

} /* adcList_Append */

int adcList_Pop( ADCLIST **ppHead, ADCLIST **ppNode ) {
Click to expand...

There's no reason for ppNode to be a pointer to pointer to ADCLIST.
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;
Click to expand...

if (pTemp->pNext) {
pTemp->pNext->pPrev = pTemp;
}
}


/* FREE THE ITEM */
free( pList->pData );
pList->pData = NULL;
Click to expand...

The last line is not needed.
free( pList );
*ppNode = NULL;

ret = TRUE;

}
else
{
ret = FALSE;
}

return ret;

} /* adcList_Pop */

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 */


#ifndef _ADC_LIST_H_
#define _ADC_LIST_H_
Click to expand...

#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
Click to expand...

In general I would not define those values and use plain 0 and 1.
typedef struct ADCLIST_el
{
struct ADCLIST_el *pPrev;
struct ADCLIST_el *pNext;
void *pData;

} ADCLIST_el;

typedef ADCLIST_el ADCLIST;
Click to expand...

Why two typedefs? If you really want a typedef use:

typedef struct ADCLIST_el {
struct ADCLIST_el *pPrev;
struct ADCLIST_el *pNext;
void *pData;
} ADCLIST;

But still I wouldn't use upper case, ie.:

typedef struct adcList {
struct adcList *pPrev;
struct adcList *pNext;
void *pData;
} adcList;

But still I wouldn't use typedef at all.

BTW. You may find reading this useful:
http://www.joelonsoftware.com/articles/Wrong.html
 
T

TBass

[snip]
You need to update the pPrev field of pNewNodes's successor, ie
pNewNode->pNext->pPrev = pNewNode;
....

You need top update the pPrev field of pTemp's successor ie
pTemp->pNext->pPrev = pTemp;
Click to expand...
[/snip]


Thanks!
 
P

pete

TBass wrote:
/***************************************************************
* 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 */
Click to expand...
typedef struct ADCLIST_el
{
struct ADCLIST_el *pPrev;
struct ADCLIST_el *pNext;
void *pData;

} ADCLIST_el;

typedef ADCLIST_el ADCLIST;
Click to expand...

adcList_Free won't work if (pList->pData)
is the head of another list.
 
R

Roland Pibinger

I don't recommend casting the return value of malloc(): [...]
* If you cast to the wrong type by accident, odd failures can
result.
Click to expand...

which is a real advantage compared to not casting at all :)
 
T

TBass

[snip]
adcList_Free won't work if (pList->pData)
is the head of another list.
Click to expand...
[/snip]

That's true, and I should probably mention that in the header file.
The library isn't intended to host sub-lists in the pData member, but
the Pop function could be used in that situation.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Memory allocation problem 8
Linked-list problem - compiles but segfaults 13
pointer question. 4
A container library in C: Part 3. List container implementation 5
How does a HEAD pointer end up pointing to the first node in a linked list? 3
Mergesort algorithm for linked lists 0
Reversing a linked list 116
reading the source of calling a singly-linked list 4

Members online

No members online now.
Total: 26 (members: 1, guests: 25)
Robots: 344

Forum statistics

Threads
473,769
Messages
2,569,582
Members
45,062
Latest member
OrderKetozenseACV

Latest Threads

Top