My linked list

[Ben Bacarisse]

[...]
     (*node)->elem = (char*) malloc (strlen (elem) + 1);
     if ( NULL == (*node)->elem ) {
        error = C_ERR_NO_MEMORY;
     }
     strncpy ((*node)->elem, elem, strlen ((*node)->elem) + 1);

(*node)->elem does not point to a string (yet); you cannot pass it
to strlen().  Either you want

      strncpy ((*node)->elem, elem, strlen (elem) + 1);

or (simpler)

      strcpy ((*node)->elem, elem);

NO, I don't agree.
Because (*node->elem) have been malloced to char*.
And when we copy elem to (*node->elem), we should make sure copy strlen
((*node)->elem) + 1 length at most.
So, here should be :

strncpy ((*node)->elem, elem, strlen ((*node)->elem) + 1);

Am I correct?

No. Lets leave the fact the *node can be NULL out of this (I pointed
that out in another message). After:

(*node)->elem = (char*) malloc (strlen (elem) + 1);

There are two problems. (1) Even when you see that the allocation
failed all you do is set error. You then go on to use (*node)->elem
even though it might be NULL. (2) In the best outcome, when the
allocation worked, you still can't call strlen((*node)->elem) because
the contents of the newly allocated storage are indeterminate.

 

[Ben Bacarisse]

That's reason c) then

Well at most b), I'd say

 

[Ben Bacarisse]

char t1[11];
char s1[] =3D "0123456789";
strncpy(t1, s1, 11);

Is it correct?

In theory, yes. In practice, since you _will_ use strncpy() with strings
where the lengths don't add up so nicely and aren't known in advance in
the first place, use strncat() instead.

In the general case, to use strncpy() safely, you need to do:

  char dest[DEST_SIZE];
  char *source=init_to_unknown_length_string();

  strncpy(dest, source, DEST_SIZE);
  dest[DEST_SIZE-1]='\0';

which is at least safe, but can waste time writing more zeroes than
necessary. Instead, this:

  char dest[DEST_SIZE];
  char *source=init_to_unknown_length_string();

  dest[0]='\0';
  strncat(dest, source, DEST_SIZE);

is equally safe, and doesn't bother writing those padding zeroes.

Richard

It's best not to quote sig blocks (even sort ones).

yes, I found your method is better.

OK, but you go on to show code that does not use it.

and if dest is a dynamic char* in my function CNode_Alloc_and_Init,

we should get the length of source first, then malloc my char* elem
field, at this time, the strncpy should be written:

if ( elem != NULL) {
(*node)->elem = (char*) malloc (strlen (elem) + 1);
if ( NULL == (*node)->elem ) {
error = C_ERR_NO_MEMORY;
}
strncpy ((*node)->elem, elem, strlen ((*node)->elem));
(*node)->elem[strlen((elem))] = '\0';
}

correct?

No. First, Richard Bos is advising against using strncpy. Second the
second call to strlen is wrong (see various other messages about
that).

My preference would be to remember the length (I often prefer to
remember the size since it is the length + 1 we keep needing) and to
call memcpy which does exactly the right thing always and it does not
need to check for null bytes since it works using only the size:

size_t s_size = strlen(elem) + 1;
(*node)->elem = malloc(s_size);
if (NULL == (*node)->elem)
error = C_ERR_NO_MEMORY;
else memcpy((*node)->elem, elem, s_size);

Note the *else* part: only copy if the malloc succeeded.

 

[JC]

*node may be NULL.  You check for that but all you do set error and
keep going.  (I'd also loose the cast.)


Eek!  Now either *node or (*node)->elem can be NULL and both
conditions cause trouble!

Ah, this is a stupid bug I made. thanks.
and also, strncpy should be called like:

strncpy ((*node)->elem, elem, strlen (elem));
(*node)->elem[strlen(elem)] = '\0';

I am not sure that it is a good idea to leave the node allocated when
the string allocation failed.  I would free the node if the string
could not allocated.  Also, if you really feel you must handle the
case where the user passes in a NULL string pointer, I'd treat that as
an empty string.  You might even pack the string in the same
allocation as the node:

 static int CNode_Alloc_and_Init(CLinkedNode **node, const char* elem)
 {
     size_t s_size = elem == NULL ? 1 : strlen(elem) + 1;
     *node = malloc(sizeof **node + s_size);

malloc can used like this to malloc for struct and string,
I never saw it.

     if (*node != NULL) {
         (*node)->elem = (char *)(*node + 1);
         memcpy((*node)->elem, elem == NULL ? "" : elem, s_size);
         (*node)->prev = (*node)->next = NULL;
         return 0;
     }
     return C_ERR_NO_MEMORY;
 }

Of course, this is a Very Bad Design if you intend to ever pass the
string pointer out from any list functions; or is you plan to allow
sharing of string between lists, but you don't seem to be going that
way.

The better design is only give CLinkedNode **node parameter to
C_Node_Alloc_and_Init
function?

Here, I can remove oldp->elem == NULL; oldp->next = NULL;?
because oldp is a local variable?

remove oldp = NULL; here too?

You still have lots of (to my mind) pointless assignments.








There two lines are still almost duplicated.


Why not (I am copying your style here -- I'd do it slightly differently):

  int CLinkedList_Append (CLinkedList *list, const char* elem)
  {
     CLinkedNode *new_node;
     int error = CNode_Alloc_and_Init (&new_node, elem);
     if ( error )  goto TERMINATE;

     if ( list->first == NULL && list->last  == NULL ) {
        list->last = list->first = new_node;
     }
     else {
        new_node->prev = list->last;
        list->last->next = new_node;
        list->last = new_node;
     }

  TERMINATE:

     return error;
  } /* END of CLinkedList_Insert */

<snip>
Excellent!!



This whole if is not needed.  The else case below produces exactly the
same effect as the code above.



I.e. all you need is:

  int CLinkedList_Length(CLinkedList *list)
  {
     int length = 0;
     CLinkedNode *p = list->first;
     while ( p != NULL) {
          ++length;
          p = p->next;
     }
     return length;
  } /* END of CLinkedList_Length */

Excellent!!

Ben, you are really expert's expert!
sure, I am newbie...

Thanks very much!

John Cui

 

[JC]

char t1[11];
char s1[] =3D "0123456789";
strncpy(t1, s1, 11);
Is it correct?

In theory, yes. In practice, since you _will_ use strncpy() with strings
where the lengths don't add up so nicely and aren't known in advance in
the first place, use strncat() instead.

In the general case, to use strncpy() safely, you need to do:

  char dest[DEST_SIZE];
  char *source=init_to_unknown_length_string();

  strncpy(dest, source, DEST_SIZE);
  dest[DEST_SIZE-1]='\0';

which is at least safe, but can waste time writing more zeroes than
necessary. Instead, this:

  char dest[DEST_SIZE];
  char *source=init_to_unknown_length_string();

  dest[0]='\0';
  strncat(dest, source, DEST_SIZE);

is equally safe, and doesn't bother writing those padding zeroes.

Richard

yes, I found your method is better.

and if dest is a dynamic char* in my function CNode_Alloc_and_Init,

we should get the length of source first, then malloc my char* elem
field, at this time, the strncpy should be written:

if ( elem != NULL) {
   (*node)->elem = (char*) malloc (strlen (elem) + 1);
   if ( NULL == (*node)->elem ) {
      error = C_ERR_NO_MEMORY;
   }
   strncpy ((*node)->elem, elem, strlen ((*node)->elem));
   (*node)->elem[strlen((elem))] = '\0';

sorry,
Here should be

strncpy ((*node)->elem, elem, strlen (elem);
(*node)->elem[strlen((elem))] = '\0';

John Cui

 

[JC]

Dear all,
bug fixed version CLinkedList.c
--------------------------------------------------------------------

/* linked list by John Cui*/
#include "linkedlist.h"

static int
CNode_Alloc_and_Init (CLinkedNode **node,
const char* elem)
{
int error = 0;

*node = malloc (sizeof **node);
if ( NULL == *node ) {
error = C_ERR_NO_MEMORY;
goto TERMINATE;
}

if ( elem != NULL) {
size_t s_size = strlen (elem) + 1;
(*node)->elem = malloc (s_size);

if (NULL == (*node)->elem) {
error = C_ERR_NO_MEMORY;
goto TERMINATE;
}
else {
memcpy ((*node)->elem, elem, s_size);
}
}
else {
(*node)->elem = NULL;
}

(*node)->next = NULL;
(*node)->prev = NULL;

TERMINATE:
if ( ( *node != NULL) &&
((*node)->elem == NULL) ) {
free (*node);
*node = NULL;
}
return error;
}
int
CLinkedList_Init (CLinkedList **list)
{
int error = 0;

*list = malloc (sizeof **list);
if ( NULL == *list ) {
error = C_ERR_NO_MEMORY;
goto TERMINATE;
}

(*list)->first = NULL;
(*list)->last = NULL;

TERMINATE:

return error;
} /* End of CLinkedList_Init */


/* Free the list*/
int
CLinkedList_Free (CLinkedList **list)
{
int error = 0;

while ( (*list)->first != NULL ) {
CLinkedNode* oldp = (*list)->first;
(*list)->first = (*list)->first->next;
free (oldp->elem);
free (oldp);
}
(*list)->first = (*list)->last = NULL;
free (*list);
*list = NULL;

TERMINATE:

return error;
} /* End of CLinkedList_Free */

int
CLinkedList_Append (CLinkedList *list,
const char* elem)
{
CLinkedNode *new_node = NULL;

int error = CNode_Alloc_and_Init (&new_node, elem);
if ( error ) goto TERMINATE;

if ( list->first == NULL &&
list->last == NULL ) {
list->last = list->first = new_node;
}
else {
new_node->prev = list->last;
list->last->next = new_node;
list->last = new_node;
}

TERMINATE:

return error;
} /* END of CLinkedList_Append */

int
CLinkedList_Output (CLinkedList *list,
const char* sp)
{
CLinkedNode *p;

if ( list->first != NULL &&
list->last != NULL ) {
p = list->first;
while ( p != NULL) {
printf ("%s %s ", p->elem, sp);
p = p->next;
}
printf ("\n");
printf ("Have %d elements in this list\n\n", CLinkedList_Length
(list));
}
else {
printf ("This is an empty list now\n\n");
}

return 0;
} /* End of CLinkedList_Output */

// Pop is a method used in both stack and queue with flag
int
CLinkedList_Pop (CLinkedList *list,
int flag)
{
int error = 0;
CLinkedNode *p = NULL;

if ( flag == C_STACK ) {
if ( list->first != NULL) {
p = list->first;

// If more than one elememt
if ( list->first->next != NULL) {
list->first = list->first->next;
list->first->prev = NULL;
}
// If only one element
else {
list->first = NULL;
list->last = NULL;
}
}
else {
error = C_ERR_EMPTY_LIST;
goto TERMINATE;
}
}
else if ( flag == C_QUEUE ) {
if ( list->last != NULL) {
p = list->last;

if ( list->last->prev != NULL ) {
list->last = list->last->prev;
list->last->next = NULL;
}
else {
list->first = NULL;
list->last = NULL;
}
}
else {
error = C_ERR_EMPTY_LIST;
goto TERMINATE;
}
}
else {
error = C_ERR_NOT_STACK_AND_QUEUE;
goto TERMINATE;
}

printf ("%s was deleted\n", p->elem);

free (p->elem);
p->elem = NULL;

free (p);
p = NULL;

TERMINATE:

return error;
} /* End of CLinkedList_Pop */
int
CLinkedList_Length (CLinkedList *list)
{
int length = 0;
CLinkedNode *p = list->first;

while ( p != NULL) {
++length;
p = p->next;
}

return length;
} /* END of CLinkedList_Length */

----------------------end------------------------------

Thanks,

John Cui

 

[Ben Bacarisse]

On Jun 18, 11:28 pm, Ben Bacarisse <[email protected]> wrote:

Eek!  Now either *node or (*node)->elem can be NULL and both
conditions cause trouble!

Ah, this is a stupid bug I made. thanks.
and also, strncpy should be called like:

strncpy ((*node)->elem, elem, strlen (elem));
(*node)->elem[strlen(elem)] = '\0';

I can't emphasise enough: strncpy should not be called at all! It
works fine as you first had it:

strncpy ((*node)->elem, elem, strlen (elem) + 1);

but it has to do more work than is needed (it must test for a null
that comes only when the counter runs out and it must test the counter
that runs out only at the null) and getting used to using it is a bug
waiting to happen.

I have been programming in C for nearly 30 years and I last used
strncpy about 29 years ago when it was exactly what was needed to copy
Unix file names into directory entries because these were not
null-terminated unless they were < 14 characters long (in which case
you had to pack the space with nulls). I think it was invented
because of this format, and I have never used it since (except in an
embarrassingly erroneous posting here a few years ago). It is almost
never the best function for the job: strcpy does what you want
and is simpler; memcpy does it better if you have the length already.

malloc can used like this to malloc for struct and string,
I never saw it.

This is a hack. Please be aware of that. For example, it works
because char has no alignment needs. If you ever switch to wide
characters this code will break.

My real point was this: allocate both or neither. You had a situation
where you allocate the node and then return an error because the
string could not be allocated. This is (depending on exactly how you
use the result) a memory leak.

The better design is only give CLinkedNode **node parameter to
C_Node_Alloc_and_Init
function?

I am not sure what you mean.

Here, I can remove oldp->elem == NULL; oldp->next = NULL;?
Yes.

because oldp is a local variable?

No, because you are going to call free:

Everything that oldp pointed at has now gone. Why set something that
is going to be thrown away?

remove oldp = NULL; here too?

Yes. At the end of the loop...

.... oldp vanishes. You get a new oldp at the start of the next loop
iteration (or you leave the loop and there is nothing called oldp
anymore). There is no point in setting a variable to anything just
before the end of its lifetime.

Excellent!!

Ben, you are really expert's expert!

<blush>

 

[Ben Bacarisse]

bug fixed version CLinkedList.c
Almost!
--------------------------------------------------------------------

/* linked list by John Cui*/
#include "linkedlist.h"

static int
CNode_Alloc_and_Init (CLinkedNode **node,
const char* elem)
{
int error = 0;

*node = malloc (sizeof **node);
if ( NULL == *node ) {
error = C_ERR_NO_MEMORY;
goto TERMINATE;
}

if ( elem != NULL) {
size_t s_size = strlen (elem) + 1;
(*node)->elem = malloc (s_size);

if (NULL == (*node)->elem) {
error = C_ERR_NO_MEMORY;

At this point I think you should free *node. See later for any (and
other options).

goto TERMINATE;
}
else {
memcpy ((*node)->elem, elem, s_size);
}
}
else {
(*node)->elem = NULL;
}

(*node)->next = NULL;
(*node)->prev = NULL;

TERMINATE:
if ( ( *node != NULL) &&
((*node)->elem == NULL) ) {
free (*node);
*node = NULL;
}
return error;
}

int
CLinkedList_Append (CLinkedList *list,
const char* elem)
{
CLinkedNode *new_node = NULL;

int error = CNode_Alloc_and_Init (&new_node, elem);
if ( error ) goto TERMINATE;

If you don't free above, you should free now. The error may be the
string allocation, not the node allocation.

if ( list->first == NULL &&
list->last == NULL ) {
list->last = list->first = new_node;
}
else {
new_node->prev = list->last;
list->last->next = new_node;
list->last = new_node;
}

TERMINATE:

return error;
} /* END of CLinkedList_Append */

There is still the question of why you provide two remove operations
but only one append.

 

[JC]

At this point I think you should free *node.  See later for any (and
other options).

I free *node here if malloc (*node)->elem failed.
but I prefer your position to free (*node) at

if (NULL == (*node)->elem) {
error = C_ERR_NO_MEMORY;
free(*node);
*node = NULL;
}

If you don't free above, you should free now.  The error may be the
string allocation, not the node allocation.

See above.

There is still the question of why you provide two remove operations
but only one append.

Yes, insert funciton is in my todo list.

Thanks,
John Cui

 

[JC]

Ah, this is a stupid bug I made. thanks.
and also, strncpy should be called like:

strncpy ((*node)->elem, elem, strlen (elem));
(*node)->elem[strlen(elem)] = '\0';

I can't emphasise enough: strncpy should not be called at all!  It
works fine as you first had it:

  strncpy ((*node)->elem, elem, strlen (elem) + 1);

I will never use it.

but it has to do more work than is needed (it must test for a null
that comes only when the counter runs out and it must test the counter
that runs out only at the null) and getting used to using it is a bug
waiting to happen.

I have been programming in C for nearly 30 years and I last used
strncpy about 29 years ago when it was exactly what was needed to copy
Unix file names into directory entries because these were not
null-terminated unless they were < 14 characters long (in which case
you had to pack the space with nulls).  I think it was invented
because of this format, and I have never used it since (except in an
embarrassingly erroneous posting here a few years ago).  It is almost
never the best function for the job: strcpy does what you want
and is simpler; memcpy does it better if you have the length already.

strcpy or memcpy will replace strncpy in my code.

This is a hack.  Please be aware of that.  For example, it works
because char has no alignment needs.  If you ever switch to wide
characters this code will break.

My real point was this: allocate both or neither.  You had a situation
where you allocate the node and then return an error because the
string could not be allocated.  This is (depending on exactly how you
use the result) a memory leak.

Yes, what I do is add free(*node) when malloc string failed.

I am not sure what you mean.

What I said here is the design of CNode_Alloc_and_Init function.
the current version is :
static int
CNode_Alloc_and_Init (CLinkedNode **node,
const char* elem)
but you said it is a bad design, in fact, I didn't understand where it
is bad.

What you prefer is, I think,
static int
CNode_Alloc_and_Init (CLinkedNode **node)
to let elem NULL and alloc/init in list functions?


John Cui

 

[Ben Bacarisse]

On Jun 19, 1:02 am, Ben Bacarisse <[email protected]> wrote:

Yes, what I do is add free(*node) when malloc string failed.

So I now see. I missed that. Sorry.

What I said here is the design of CNode_Alloc_and_Init function.
the current version is :
static int
CNode_Alloc_and_Init (CLinkedNode **node,
const char* elem)
but you said it is a bad design, in fact, I didn't understand where it
is bad.

Ah! What I meant was my design (allocating both the node and the
string together) was bad is some cases. Not yours.

<snip>

 

[JC]

Dear Ben and friends,
Thanks for your suggestions about my code.
Refer to your ideas, I post the latest version of linkedlist here.
and also, I wrote a arraylist, also post here.
Welcome your suggestion!!!

1. include files:
file struct{
C.h
constant.h
errormap.h
}
--------C.h--------
#ifndef H_C
#define H_C
#include<stdio.h>
#include<stdlib.h>
#include "constant.h"
#include "errormap.h"
#endif
--------end--------
--------constant.h--------
#ifndef H_CONSTANT
#define H_CONSTANT
#define C_LIST_INIT_SIZE 5
#define C_LISTINCREMENT 5

#define C_ERR_NO_MEMORY 10001
#define C_ERR_NOTVALID_INDEX 10002

#define C_ERR_NOT_FOUND 60001
#define C_ERR_EMPTY_LIST 60002
#define C_ERR_NOT_STACK_AND_QUEUE 60003

#define C_TYPE int
#define C_STACK 1
#define C_QUEUE 0

#endif
--------end--------
--------errormap.h--------
#ifndef H_ERRORMAP
#define H_ERRORMAP
typedef struct {
int error;
const char *str;
} ErrorMap;

static
ErrorMap errorMap[] = {
{C_ERR_NO_MEMORY, "No memory can be used"},
{C_ERR_NOTVALID_INDEX, "Not valid index"},
{C_ERR_NOT_FOUND, "Element not found in list"},
{C_ERR_EMPTY_LIST, "Empty list"},
{C_ERR_NOT_STACK_AND_QUEUE, "Pop not in stack and queue"},
};
#endif
--------end--------

2. sort (only select sort and bubble sort in this version)
file struct {
sort.h
sort.c
}
--------sort.h--------
#include "../include/constant.h"
void CBubble_Sort(C_TYPE *a, int len);
void CSelect_Sort(C_TYPE *a, int len);
--------end--------
--------sort.c--------
#include "sort.h"

void
CSelect_Sort(C_TYPE *a,
int len)
{
int i, j, min;
C_TYPE t;

for (i = 0; i < len; ++i) {
min = i;
for (j = i + 1; j < len; ++j) {
if (a[j] < a[min]) {
min = j;
}
}

if ( i != min ) {
t = a;
a = a[min];
a[min] = t;
}
}

} /* End of CSelect_Sort*/

void
CBubble_Sort(C_TYPE *a,
int len)
{
int i, j;
C_TYPE t;

for (i = 0; i < len; ++i) {
for (j = i + 1; j < len; ++j) {
if (a[j] < a) {
t = a;
a = a[j];
a[j] = t;
}
}
}

} /* End of CBubble_Sort*/

--------end--------

3. seqlist
file struct{
seqlist.c
seqlist.h
Makefile
main.c
}
--------Makefile.h--------
all: clean
gcc -g main.c seqlist.c ../sort/sort.c -o mylist.exe
clean:
-rm -rf mylist.exe
..PHONEY: clean all
--------end-----------

--------seqlist.h--------
#ifndef H_SEQLIST
#define H_SEQLIST
#include "../include/C.h"
typedef struct {
C_TYPE *elem_p; /* The basic address of list */
int length; /* The length of list */
int capacity; /* The capacity of list*/
} CSeqList;

int CSeqList_Init(CSeqList **list);
int CSeqList_Free(CSeqList **list);
int CSeqList_Clear(CSeqList *list);
int CSeqList_Insert(CSeqList *list, int index, const C_TYPE elem);
int CSeqList_Delete(CSeqList *list, int index, C_TYPE* e);
int CSeqList_Output(CSeqList *list);
int CSeqList_Sort(CSeqList *list, int length);
int CSeqList_Find(CSeqList *list, const C_TYPE elem, int *index);
#endif
--------end-----------

--------seqlist.c--------
/* sequence list by John Cui*/
#include "seqlist.h"
#include "../sort/sort.h"

int
CSeqList_Init (CSeqList **list)
{
int error = 0;

*list = malloc(sizeof **list);

(*list)->elem_p = (C_TYPE*) malloc(C_LIST_INIT_SIZE * sizeof
(C_TYPE));
if ( (*list)->elem_p == NULL ) {
error = C_ERR_NO_MEMORY;
goto TERMINATE;
}
(*list)->length = 0;
(*list)->capacity = C_LIST_INIT_SIZE;

TERMINATE:

return error;
} /* End of CSeqList_Init */

/* Free the list*/
int
CSeqList_Free (CSeqList **list)
{
int error = 0;
int temp;

if ( (*list)->elem_p != NULL) {
while ((*list)->length != 0) {
error = CSeqList_Delete(*list, 0, &temp);
if ( error ) goto TERMINATE;
}
free((*list)->elem_p);
(*list)->elem_p = NULL;
(*list)->capacity = 0;
}
free(*list);
*list = NULL;

TERMINATE:

return error;
} /* End of CSeqList_Free */

/* Clear the whole list*/
int
CSeqList_Clear (CSeqList *list)
{
int error = 0;
C_TYPE temp;

while (list->length != 0) {
error = CSeqList_Delete(list, 0, &temp);
if ( error ) goto TERMINATE;
}

TERMINATE:

return error;
} /* End of CSeqList_Clear*/

int
CSeqList_Insert (CSeqList *list,
int index,
const C_TYPE elem)
{
int error = 0;

C_TYPE *p = NULL;
C_TYPE *q = NULL;

//check index
if ( index < 0 ||
index > list->length ) {
error = C_ERR_NOTVALID_INDEX;
goto TERMINATE;
}

//extend capacity if length >= capacity in realloc
if ( list-> length == list->capacity) {
list->elem_p =
(C_TYPE*) realloc (list->elem_p,
sizeof (C_TYPE) * (list->capacity + C_LISTINCREMENT));
if ( list->elem_p == NULL ) {
error = C_ERR_NO_MEMORY;
goto TERMINATE;
}
list->capacity += C_LISTINCREMENT;
}

//move elements which is after list[index] to next
p = &(list->elem_p[index]);
for (q = &(list->elem_p[list->length - 1]); q >= p; --q) {
*(q+1) = *q;
}

//insert elem and increase the length of list
*p = elem;
++list->length;

TERMINATE:

return error;
} /* END of CSeqList_Insert */

int
CSeqList_Delete (CSeqList *list,
int index,
C_TYPE *e)
{
int error = 0;

C_TYPE *p = NULL;
C_TYPE *q = NULL;

//check index
if ( index < 0 ||
index > list->length ) {
error = C_ERR_NOTVALID_INDEX;
goto TERMINATE;
}

//keep the deleted element
e = &(list->elem_p[index]);

//move the element which after list

• to previous
  p = &list->elem_p[index];
  for (q = p; q <= &(list->elem_p[list->length-1]); ++q) {
  *q = *(q+1);
  }
  --list->length;
  
  TERMINATE:
  
  return error;
  } /* End of CSeqList_Delete */
  
  int
  CSeqList_Output (CSeqList *list)
  {
  int i;
  
  printf ("list->length = %d\n", list->length);
  printf ("list->capacity = %d\n", list->capacity);
  printf ("elements:\n");
  
  if ( list->length != 0 ) {
  for (i = 0; i < list->length; ++i) {
  printf ("%d ", list->elem_p);
  }
  }
  else {
  printf("This is a NULL list!");
  }
  printf ("\n\n");
  
  return 0;
  } /* End of CSeqList_Output */
  
  int
  CSeqList_Sort (CSeqList *list,
  int length)
  {
  int error = 0;
  
  if (length > list->length) {
  length = list->length;
  }
  CSelect_Sort(list->elem_p, length);
  //CBubble_Sort(list, list->length);
  
  return error;
  }
  
  int
  CSeqList_Find (CSeqList *list,
  const C_TYPE elem,
  int *index)
  {
  int error = 0;
  int i;
  
  *index = -1;
  
  // Search algrithm can be extended here
  for (i = 0; i < list->length; ++i) {
  if ( list->elem_p == elem ) {
  *index = i;
  }
  }
  
  if ( *index == -1) {
  error = C_ERR_NOT_FOUND;
  }
  
  TERMINATE:
  return error;
  
  } /* End of CSeqList_Find */
  
  --------end-----------
  
  --------main.c--------
  #include "seqlist.h"
  
  int main(void)
  {
  int i;
  int error = 0;
  int ind;
  C_TYPE e;
  CSeqList* mylist = NULL;
  
  error = CSeqList_Init (&mylist);
  if ( error ) goto TERMINATE;
  
  error = CSeqList_Insert (mylist, 0, 1);
  if ( error ) goto TERMINATE;
  error = CSeqList_Insert (mylist, 1, 10);
  if ( error ) goto TERMINATE;
  error = CSeqList_Insert (mylist, 2, 0);
  if ( error ) goto TERMINATE;
  error = CSeqList_Insert (mylist, 3, 5);
  if ( error ) goto TERMINATE;
  
  error = CSeqList_Find (mylist, 5, &ind);
  if ( error ) goto TERMINATE;
  printf ("index of element is %d\n", ind);
  
  CSeqList_Output (mylist);
  CSeqList_Sort (mylist, mylist->length);
  CSeqList_Output (mylist);
  
  error = CSeqList_Insert (mylist, 1, 8);
  if ( error ) goto TERMINATE;
  
  CSeqList_Sort (mylist, mylist->length);
  CSeqList_Output (mylist);
  
  error = CSeqList_Insert (mylist, 0, 100);
  if ( error ) goto TERMINATE;
  error = CSeqList_Insert (mylist, 2, 1000);
  if ( error ) goto TERMINATE;
  
  CSeqList_Sort(mylist, mylist->length);
  CSeqList_Output (mylist);
  
  error = CSeqList_Delete (mylist, 3, &e);
  if ( error ) goto TERMINATE;
  
  CSeqList_Output (mylist);
  CSeqList_Sort (mylist, mylist->length);
  error = CSeqList_Clear (mylist);
  
  CSeqList_Output (mylist);
  error = CSeqList_Insert (mylist, 0, 100);
  if ( error ) goto TERMINATE;
  error = CSeqList_Insert (mylist, 1, 1000);
  CSeqList_Output (mylist);
  if ( error ) goto TERMINATE;
  
  error = CSeqList_Free (&mylist);
  if ( error ) goto TERMINATE;
  
  if ( mylist == NULL ) printf("sqlist free successfully!");
  TERMINATE:
  if ( error ) {
  int nErrors = sizeof (errorMap) / sizeof (errorMap[0]);
  
  for (i = 0; i < nErrors; ++i) {
  if ( errorMap.error == error ) {
  printf ("C Error: %s\n", errorMap.str);
  }
  }
  CSeqList_Free (&mylist);
  }
  
  return 0;
  }
  --------end-----------
  
  4. linkedlist
  file struct:
  likedlist{
  linkedlist.c
  linkedlist.h
  main.c
  Makefile
  }
  
  --------Makefile--------
  all: clean
  gcc -g main.c linkedlist.c -o mylist.exe
  clean:
  -rm -rf mylist.exe
  ..PHONEY: clean all
  --------end-----------
  
  --------linkedlist.h--------
  #ifndef H_LINKEDLIST
  #define H_LINKEDLIST
  #include "../include/C.h"
  struct CLinkedNode {
  char *elem;
  struct CLinkedNode *next;
  struct CLinkedNode *prev;
  };
  
  struct CLinkedList{
  struct CLinkedNode *first;
  struct CLinkedNode *last;
  };
  
  typedef struct CLinkedNode CLinkedNode;
  typedef struct CLinkedList CLinkedList;
  
  int CLinkedList_Init(CLinkedList **list);
  int CLinkedList_Free(CLinkedList **list);
  int CLinkedList_Append(CLinkedList *list, const char* elem);
  int CLinkedList_Insert(CLinkedList *list, int pos, const char* elem);
  int CLinkedList_Pop(CLinkedList *list, int flag);
  int CLinkedList_Output(CLinkedList *list, const char* sp);
  int CLinkedList_Length(CLinkedList *list);
  #endif
  --------end-----------
  
  --------linkedlist.c--------
  /* linked list by John Cui*/
  #include "linkedlist.h"
  
  static int
  CNode_Alloc_and_Init (CLinkedNode **node,
  const char* elem)
  {
  int error = 0;
  
  *node = malloc (sizeof **node);
  if ( NULL == *node ) {
  error = C_ERR_NO_MEMORY;
  goto TERMINATE;
  }
  
  if ( elem != NULL ) {
  size_t s_size = strlen (elem) + 1;
  (*node)->elem = malloc (s_size);
  
  if (NULL == (*node)->elem) {
  // free *node if alloc elem failed.
  free(*node);
  *node = NULL;
  
  error = C_ERR_NO_MEMORY;
  goto TERMINATE;
  }
  else {
  memcpy ((*node)->elem, elem, s_size);
  }
  }
  else {
  (*node)->elem = NULL;
  }
  
  (*node)->next = NULL;
  (*node)->prev = NULL;
  
  TERMINATE:
  
  return error;
  }
  int
  CLinkedList_Init (CLinkedList **list)
  {
  int error = 0;
  
  *list = malloc (sizeof **list);
  if ( NULL == *list ) {
  error = C_ERR_NO_MEMORY;
  goto TERMINATE;
  }
  
  (*list)->first = NULL;
  (*list)->last = NULL;
  
  TERMINATE:
  
  return error;
  } /* End of CLinkedList_Init */
  
  
  /* Free the list*/
  int
  CLinkedList_Free (CLinkedList **list)
  {
  int error = 0;
  
  while ( (*list)->first != NULL ) {
  CLinkedNode* oldp = (*list)->first;
  (*list)->first = (*list)->first->next;
  free (oldp->elem);
  free (oldp);
  }
  (*list)->first = (*list)->last = NULL;
  free (*list);
  *list = NULL;
  
  TERMINATE:
  
  return error;
  } /* End of CLinkedList_Free */
  
  int
  CLinkedList_Append (CLinkedList *list,
  const char* elem)
  {
  CLinkedNode *new_node = NULL;
  
  int error = CNode_Alloc_and_Init (&new_node, elem);
  if ( error ) goto TERMINATE;
  
  if ( list->first == NULL &&
  list->last == NULL ) {
  list->last = list->first = new_node;
  }
  else {
  new_node->prev = list->last;
  list->last->next = new_node;
  list->last = new_node;
  }
  
  TERMINATE:
  
  return error;
  } /* END of CLinkedList_Append */
  
  //insert the new_node after "p"
  int
  CLinkedList_Insert (CLinkedList *list,
  int pos,
  const char* elem)
  {
  int error;
  int len = CLinkedList_Length(list);
  
  // If list is an empty list, then ignore pos
  // and the new_node is the list->first and list->last
  if ( len == 0 ) {
  CLinkedNode *new_node = NULL;
  error = CNode_Alloc_and_Init (&new_node, elem);
  if ( error ) goto TERMINATE;
  list->first = list->last = new_node;
  }
  else {
  // if pos == len, then just append it
  if ( pos == len ) {
  error = CLinkedList_Append (list, elem);
  if ( error ) goto TERMINATE;
  }
  // if pos in the middle of list
  else {
  // check pos
  if ( pos < 1 ||
  pos > len ) {
  error = C_ERR_NOTVALID_INDEX;
  goto TERMINATE;
  }
  
  // find the node at pos "p"
  int j = 0;
  CLinkedNode *p = list->first;
  while (p && j < pos-1) {
  p = p->next;
  ++j;
  }
  
  // creat new_node
  CLinkedNode *new_node = NULL;
  error = CNode_Alloc_and_Init (&new_node, elem);
  if ( error ) goto TERMINATE;
  
  // insert the new_node after "p"
  new_node->next = p->next;
  new_node->prev = p;
  p->next = new_node;
  }
  }
  
  
  TERMINATE:
  
  return error;
  }
  int
  CLinkedList_Output (CLinkedList *list,
  const char* sp)
  {
  CLinkedNode *p;
  
  if ( list->first != NULL &&
  list->last != NULL ) {
  p = list->first;
  while ( p != NULL) {
  printf ("%s %s ", p->elem, sp);
  p = p->next;
  }
  printf ("\n");
  printf ("Have %d elements in this list\n\n", CLinkedList_Length
  (list));
  }
  else {
  printf ("This is an empty list now\n\n");
  }
  
  return 0;
  } /* End of CLinkedList_Output */
  
  // Pop is a method used in both stack and queue with flag
  int
  CLinkedList_Pop (CLinkedList *list,
  int flag)
  {
  int error = 0;
  CLinkedNode *p = NULL;
  
  if ( flag == C_STACK ) {
  if ( list->first != NULL ) {
  p = list->first;
  
  // If more than one elememt
  if ( list->first->next != NULL ) {
  list->first = list->first->next;
  list->first->prev = NULL;
  }
  // If only one element
  else {
  list->first = NULL;
  list->last = NULL;
  }
  }
  else {
  error = C_ERR_EMPTY_LIST;
  goto TERMINATE;
  }
  }
  else if ( flag == C_QUEUE ) {
  if ( list->last != NULL ) {
  p = list->last;
  
  if ( list->last->prev != NULL ) {
  list->last = list->last->prev;
  list->last->next = NULL;
  }
  else {
  list->first = NULL;
  list->last = NULL;
  }
  }
  else {
  error = C_ERR_EMPTY_LIST;
  goto TERMINATE;
  }
  }
  else {
  error = C_ERR_NOT_STACK_AND_QUEUE;
  goto TERMINATE;
  }
  
  printf ("%s was deleted\n", p->elem);
  
  free (p->elem);
  free (p);
  
  TERMINATE:
  
  return error;
  } /* End of CLinkedList_Pop */
  int
  CLinkedList_Length(CLinkedList *list)
  {
  int length = 0;
  CLinkedNode *p = list->first;
  
  while ( p != NULL) {
  ++length;
  p = p->next;
  }
  
  return length;
  } /* END of CLinkedList_Length */
  --------end-----------
  
  --------main.c--------
  #include "linkedlist.h"
  
  int test_one_element(void)
  {
  int i;
  int error = 0;
  CLinkedList* mylist = NULL;
  
  error = CLinkedList_Init (&mylist);
  if ( error ) goto TERMINATE;
  
  // append 1 elements
  error = CLinkedList_Append (mylist, "a");
  if ( error ) goto TERMINATE;
  
  error = CLinkedList_Output (mylist, ":");
  
  // pop like stack
  error = CLinkedList_Pop (mylist, C_STACK);
  if ( error ) goto TERMINATE;
  error = CLinkedList_Output (mylist, ":");
  if ( error ) goto TERMINATE;
  
  // append 1 elements
  error = CLinkedList_Append (mylist, "b");
  if ( error ) goto TERMINATE;
  
  error = CLinkedList_Output (mylist, ":");
  
  // pop like queue
  error = CLinkedList_Pop (mylist, C_QUEUE);
  if ( error ) goto TERMINATE;
  error = CLinkedList_Output (mylist, ":");
  if ( error ) goto TERMINATE;
  
  // append 10 elements again
  for (i = 0; i < 10; ++i) {
  error = CLinkedList_Append (mylist, "a");
  if ( error ) goto TERMINATE;
  }
  
  error = CLinkedList_Output (mylist, ":");
  if ( error ) goto TERMINATE;
  
  error = CLinkedList_Free (&mylist);
  if ( error ) goto TERMINATE;
  
  if ( NULL == mylist ) printf ("free list successfully!\n\n");
  
  TERMINATE:
  
  if ( mylist ) CLinkedList_Free (&mylist);
  return error;
  }
  int test_many_elements()
  {
  int i;
  int error = 0;
  CLinkedList* mylist = NULL;
  
  error = CLinkedList_Init (&mylist);
  if ( error ) goto TERMINATE;
  
  // insert elements here
  error = CLinkedList_Insert (mylist, 0, "1");
  if ( error ) goto TERMINATE;
  error = CLinkedList_Insert (mylist, 1, "2");
  if ( error ) goto TERMINATE;
  error = CLinkedList_Insert (mylist, CLinkedList_Length(mylist),
  "end");
  if ( error ) goto TERMINATE;
  error = CLinkedList_Output (mylist, ":");
  if ( error ) goto TERMINATE;
  
  // append 10 elements
  for (i = 0; i < 10; ++i) {
  error = CLinkedList_Append (mylist, "a");
  if ( error ) goto TERMINATE;
  }
  
  error = CLinkedList_Output (mylist, ":");
  if ( error ) goto TERMINATE;
  
  // append 10 elements too
  for (i = 0; i < 10; ++i) {
  error = CLinkedList_Append (mylist, "b");
  if ( error ) goto TERMINATE;
  }
  error = CLinkedList_Output (mylist, ":");
  if ( error ) goto TERMINATE;
  
  // insert elements here
  error = CLinkedList_Insert (mylist, 1, "3");
  if ( error ) goto TERMINATE;
  error = CLinkedList_Insert (mylist, 2, "4");
  if ( error ) goto TERMINATE;
  error = CLinkedList_Insert (mylist, CLinkedList_Length(mylist),
  "end");
  if ( error ) goto TERMINATE;
  error = CLinkedList_Output (mylist, ":");
  if ( error ) goto TERMINATE;
  
  // pop like stack
  for (i = 0; i < 5; ++i) {
  error = CLinkedList_Pop (mylist, C_STACK);
  if ( error ) goto TERMINATE;
  }
  error = CLinkedList_Output (mylist, ":");
  if ( error ) goto TERMINATE;
  
  // pop like queue
  for (i = 0; i < 5; ++i) {
  error = CLinkedList_Pop (mylist, C_QUEUE);
  if ( error ) goto TERMINATE;
  
  }
  error = CLinkedList_Output (mylist, ":");
  if ( error ) goto TERMINATE;
  
  // pop like stack
  for (i = 0; i < 10; ++i) {
  error = CLinkedList_Pop (mylist, C_STACK);
  if ( error ) goto TERMINATE;
  }
  error = CLinkedList_Output (mylist, ":");
  if ( error ) goto TERMINATE;
  
  // insert 10 elements again
  for (i = 0; i < 10; ++i) {
  error = CLinkedList_Append (mylist, "a");
  if ( error ) goto TERMINATE;
  }
  
  error = CLinkedList_Output (mylist, ":");
  if ( error ) goto TERMINATE;
  
  error = CLinkedList_Free (&mylist);
  if ( error ) goto TERMINATE;
  
  if ( NULL == mylist ) printf ("free list successfully!\n\n");
  
  TERMINATE:
  
  if ( mylist ) CLinkedList_Free (&mylist);
  return error;
  }
  
  int main(void)
  {
  int i;
  int error = 0;
  
  error = test_many_elements();
  if ( error ) goto TERMINATE;
  
  error = test_one_element();
  if ( error ) goto TERMINATE;
  
  TERMINATE:
  if ( error ) {
  int nErrors = sizeof (errorMap) / sizeof (errorMap[0]);
  
  for (i = 0; i < nErrors; ++i) {
  if ( errorMap.error == error ) {
  printf ("Cui Error: %s\n", errorMap.str);
  }
  }
  }
  
  return 0;
  }
  --------end-----------
  
  -----------
  |readme.txt |
  -----------
  1. open any .h or .c file
  2. :make
  3. :!mylist.exe
  All things did in vim.
  
  #END#END#END#END#END#END#
  
  Thanks,
  
  John Cui

 

[Richard Bos]

yes, I found your method is better.

So why do you ignore it?

and if dest is a dynamic char* in my function CNode_Alloc_and_Init,
we should get the length of source first, then malloc my char* elem
field, at this time, the strncpy should be written:

_NO!_ Never use strncpy(), unless you're messing about with the internal
structures of whatever benighted version of Unix that function was
invented for.
If you may or may not have enough room for the entire string you're
copying, still _do not_ use strncpy(), use strncat() instead.
In your case, though, you know that you either have enough memory, or no
memory at all. In that case, simply use strcpy().

if ( elem != NULL) {
(*node)->elem = (char*) malloc (strlen (elem) + 1);
if ( NULL == (*node)->elem ) {
error = C_ERR_NO_MEMORY;
}
strncpy ((*node)->elem, elem, strlen ((*node)->elem));
(*node)->elem[strlen((elem))] = '\0';
}

correct?

Utterly bogus. You cast malloc(), if it returns a null pointer you
merrily clobber through it, and you still use strncpy(). _This_ is
correct (at least, as far as only that fragment is concerned):

if (elem != NULL) {
(*node)->elem = malloc(strlen(elem) + 1);
if ((*node)->elem == NULL)
error = C_ERR_NO_MEMORY;
else
strcpy((*node)->elem, elem);
}

_Forget_ strncpy() completely. It will never be the right function for
you to use.

Richard

 

[JC]

So why do you ignore it?

I have changed it in the latest version(the last posted message).
Could you please review my code in the last post message and give me
some suggestions?

if ( elem != NULL) {
   (*node)->elem = (char*) malloc (strlen (elem) + 1);
   if ( NULL == (*node)->elem ) {
      error = C_ERR_NO_MEMORY;
   }
   strncpy ((*node)->elem, elem, strlen ((*node)->elem));
   (*node)->elem[strlen((elem))] = '\0';
}

correct?

Utterly bogus. You cast malloc(), if it returns a null pointer you
merrily clobber through it, and you still use strncpy(). _This_ is
correct (at least, as far as only that fragment is concerned):

  if (elem != NULL) {
    (*node)->elem = malloc(strlen(elem) + 1);
    if ((*node)->elem == NULL)
      error = C_ERR_NO_MEMORY;
    else
      strcpy((*node)->elem, elem);
  }

_Forget_ strncpy() completely. It will never be the right function for
you to use.

Thanks, and do you mean we should _Forget_ convert the return value of
malloc when we allocate memory?

John Cui

 

[Nick Keighley]

Could you please review my code in the last post message and give me
some suggestions?

if ( elem != NULL) {
   (*node)->elem = (char*) malloc (strlen (elem) + 1);
   if ( NULL == (*node)->elem ) {
      error = C_ERR_NO_MEMORY;
   }
   strncpy ((*node)->elem, elem, strlen ((*node)->elem));
   (*node)->elem[strlen((elem))] = '\0';
}
correct?

Utterly bogus. You cast malloc(), if it returns a null pointer you
merrily clobber through it, and you still use strncpy(). _This_ is
correct (at least, as far as only that fragment is concerned):

  if (elem != NULL) {
    (*node)->elem = malloc(strlen(elem) + 1);
    if ((*node)->elem == NULL)
      error = C_ERR_NO_MEMORY;
    else
      strcpy((*node)->elem, elem);
  }

_Forget_ strncpy() completely. It will never be the right function for
you to use.

Thanks, and do you mean we should _Forget_ convert the return value of
malloc when we allocate memory?

he said "forget strncpy" NOT "_Forget_ convert the return value of
malloc when we allocate memory?". There is no need to explicitly
convert the return value of malloc as an implicit conversion is done.
void* is automatically converted to any other pointer type as
necessary.
So the cast (a) means more characters to type and (b) may hide
an error (as I remarked some time ago...)


--
Nick Keighley

Casting is almost always wrong,
and the places where it's right are rarely the places you'd guess.
Richard Heathfield
(that really *was* the next quote in the quote file)

 

[JC]

Thanks, and do you mean we should _Forget_ convert the return value of

he said "forget strncpy" NOT "_Forget_ convert the return value of
malloc when we allocate memory?". There is no need to explicitly
convert the return value of malloc as an implicit conversion is done.
void* is automatically converted to any other pointer type as
necessary.
So the cast (a) means more characters to type and (b) may hide
an error (as I remarked some time ago...)

malloc return void* which can be converted automatically to any other
pointer type, then, when we use malloc function and assign the return
value to any pointer don't need explicitly convert.

So, I think we can _forget_ convert the return value of malloc for any
type pointer like:
ANY_TYPE_POINTER p = malloc(...);

Thanks,
John Cui

 

[JC]

Dear all,
I wrote the following function to read and filter "malloc" from file
to mylist.
Is there anywhere to improve?

------------------------------------------------
int
readfile(const char * filename)
{
int error = 0;
FILE *fp = NULL;
char line[256];

fp = fopen (filename, "r");
CLinkedList* mylist = NULL;
error = CLinkedList_Init (&mylist);
if ( error ) goto TERMINATE;

while (fgets (line, 256, fp) != NULL) {
if ( strstr (line, "malloc") != NULL ||
strstr (line, "malloc") != NULL ) {
error = CLinkedList_Append (mylist, line);
if ( error ) goto TERMINATE;
}
}

fclose (fp);
CLinkedList_Output (mylist, NULL);
CLinkedList_Free (&mylist);

TERMINATE:

return error;
}


Thanks,
John Cui

 

[Ike Naar]

Dear all,
I wrote the following function to read and filter "malloc" from file
to mylist.
Is there anywhere to improve?

------------------------------------------------
int
readfile(const char * filename)
{
int error = 0;
FILE *fp = NULL;

The assigned values are never used.

char line[256];

fp = fopen (filename, "r");

You should check if fopen() succeeds.

CLinkedList* mylist = NULL;
error = CLinkedList_Init (&mylist);

What is CLinkedList_Init?

if ( error ) goto TERMINATE;

while (fgets (line, 256, fp) != NULL) {
if ( strstr (line, "malloc") != NULL ||
strstr (line, "malloc") != NULL ) {

What's the point in calling strstr(line,"malloc") twice?
What if line[] contains "int gammallocci = 42;\n" ?

error = CLinkedList_Append (mylist, line);

What is CLinkedList_Append?

if ( error ) goto TERMINATE;
}
}

fclose (fp);
CLinkedList_Output (mylist, NULL);
CLinkedList_Free (&mylist);

What are CLinkedList_Output and CLinkedList_Free?

TERMINATE:

return error;
}

You should fclose(fp) when error is nonzero and fopen() succeeded.

 

[JC]

------------------------------------------------

The assigned values are never used.

While, once decare a pointer, then assign NULL to it, which is a good
practice. IMO.

  char line[256];

  fp = fopen (filename, "r");

You should check if fopen() succeeds.

good point

What is CLinkedList_Init?



What's the point in calling strstr(line,"malloc") twice?

sorry, this is my typo, I should call strstr only once.

What if line[] contains "int gammallocci = 42;\n" ?

good point, then how to filter malloc function only?
do you have any idea?

What is CLinkedList_Append?



What are CLinkedList_Output and CLinkedList_Free?

The functions CLinkedList_*, which are the functions I implemented in
the last messages in this thread.
You can get them.

You should fclose(fp) when error is nonzero and fopen() succeeded.

yes!

Thanks,
John Cui