My linked list

[cuiyouzhi0000]

Dear friends,

I implemented a linked list in C, make, vim, gcc and gdb, could you
please verify me if I am wrong?
and how to improve them?
thanks very much!

------------Makefile-----------------------------
all: test
test: clean
gcc -g test.c linkedlist.c -o test.exe
clean:
-rm -rf test.exe
..PHONEY: clean all
---------------end-------------------------------

---------------constant.h---------------------
#ifndef _CONSTANT_
#define _CONSTANT_

#define JC_ERR_NO_MEMORY 10001

#define JC_ERR_NOT_FOUND 60001
#define JC_ERR_EMPTY_LIST 60002
#define JC_ERR_NOT_STACK_AND_QUEUE 60003

#define STACK 1
#define QUEUE 0

#endif

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

static
ErrorMap errorMap[] = {
{JC_ERR_NO_MEMORY, "no memory can be used"},
{JC_ERR_NOT_FOUND, "element not found in list"},
{JC_ERR_EMPTY_LIST, "empty list"},
{JC_ERR_NOT_STACK_AND_QUEUE, "pop not in stack and queue"},
};
#endif

----------------end-----------------------
---------------JC.h---------------------

#ifndef _JC_
#define _JC_
#include<stdio.h>
#include<stdlib.h>
#include "constant.h"
#include "errormap.h"
#endif

----------------end-------------------------
---------------linkedlist.h---------------------

#include "JC.h"
struct JCLinkedNode {
char *elem;
struct JCLinkedNode *next;
struct JCLinkedNode *prev;
};

struct JCLinkedList{
struct JCLinkedNode *first;
struct JCLinkedNode *last;
};

typedef struct JCLinkedNode JCLinkedNode;
typedef struct JCLinkedList JCLinkedList;

int JCLinkedList_Init(JCLinkedList **list);
int JCLinkedList_Free(JCLinkedList **list);
int JCLinkedList_Insert(JCLinkedList *list, const char* elem);
int JCLinkedList_Pop(JCLinkedList *list, int flag);
int JCLinkedList_Output(JCLinkedList *list);
------------------------end--------------------------------

--------------------linkedlist.c-------------------------------------
/* linked list*/
#include "linkedlist.h"

int
JCLinkedList_Init (JCLinkedList **list)
{
int status = 0;

*list = (JCLinkedList*) malloc(sizeof(JCLinkedList));
if ( NULL == *list ) {
status = JC_ERR_NO_MEMORY;
}

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

TERMINATE:

return status;
} /* End of JCLinkedList_Init */


/* Free the list*/
int
JCLinkedList_Free (JCLinkedList **list)
{
int status = 0;

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

TERMINATE:

return status;
} /* End of JCLinkedList_Free */

int
JCLinkedList_Insert (JCLinkedList *list,
const char* elem)
{
int status = 0;

if ( list->first == NULL &&
list->last == NULL ) {
list->first =
(JCLinkedNode*) malloc (sizeof(JCLinkedNode));
list->last = list->first;

list->first->elem = (char*) malloc (strlen (elem) + 1);
if ( list->first->elem != NULL ) {
strcpy (list->first->elem, elem);
}
list->first->next = list->last->next = NULL;
list->first->prev = list->last->prev = NULL;
}
else {
list->last->next =
(JCLinkedNode*) malloc (sizeof(JCLinkedNode));

list->last->next->elem = (char*) malloc (strlen (elem) + 1);
if ( list->last->next->elem != NULL ) {
strcpy(list->last->next->elem, elem);
}
list->last->next->prev = list->last;
list->last->next->next = NULL;

list->last = list->last->next;
}

TERMINATE:

return status;
} /* END of JCLinkedList_Insert */

int
JCLinkedList_Output (JCLinkedList *list)
{
int count = 0;
struct JCLinkedNode *p;

if ( list->first != NULL &&
list->last != NULL ) {
p = list->first;
while ( p != list->last ) {
++count;
printf ("%s; ", p->elem);
p = p->next;
}
printf("%s.", p->elem);
++count;
printf ("\n");
printf("Have %d elements in this list\n\n", count);
}

return 0;
} /* End of JCLinkedList_Output */

// Pop is a method used in both stack and queue with flag
int
JCLinkedList_Pop (JCLinkedList *list, int flag)
{
int status = 0;
JCLinkedNode *p;

if ( flag == STACK) {
if ( list->first != NULL) {
p = list->first;
list->first = list->first->next;
free(p->elem);
p->elem = NULL;
}
else {
status = JC_ERR_EMPTY_LIST;
}
}
else if ( flag == QUEUE ) {
if ( list->last != NULL) {
p = list->last;
list->last = list->last->prev;
free(p->elem);
p->elem = NULL;
}
else {
status = JC_ERR_EMPTY_LIST;
}
}
else {
status = JC_ERR_NOT_STACK_AND_QUEUE;
}

TERMINATE:

return status;
} /* End of JCLinkedList_Pop */

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

-----------------------test.c--------------------------------
#include "linkedlist.h"

int main(void)
{
int i;
int status = 0;
struct JCLinkedList* mylist = NULL;

status = JCLinkedList_Init (&mylist);
if ( status ) goto TERMINATE;

// insert 10 elements
for (i = 0; i < 10; ++i) {
status = JCLinkedList_Insert (mylist, "a");
if ( status ) goto TERMINATE;
}

status = JCLinkedList_Output (mylist);
if ( status ) goto TERMINATE;

// insert 10 elements too
for (i = 0; i < 10; ++i) {
status = JCLinkedList_Insert (mylist, "b");
if ( status ) goto TERMINATE;
}
status = JCLinkedList_Output (mylist);
if ( status ) goto TERMINATE;

// pop like stack
for (i = 0; i < 5; ++i) {
status = JCLinkedList_Pop (mylist, STACK);
if ( status ) goto TERMINATE;
}
status = JCLinkedList_Output (mylist);
if ( status ) goto TERMINATE;

// pop like queue
for (i = 0; i < 5; ++i) {
status = JCLinkedList_Pop (mylist, QUEUE);
if ( status ) goto TERMINATE;
}
status = JCLinkedList_Output (mylist);
if ( status ) goto TERMINATE;


status = JCLinkedList_Free (&mylist);
if ( status ) goto TERMINATE;

if ( NULL == mylist ) printf ("free list successfully!\n");

TERMINATE:
if ( status ) {
int nErrors = sizeof (errorMap) / sizeof (ErrorMap);

for (i = 0; i < nErrors; ++i) {
if ( errorMap.error == status ) {
printf ("JC Error: %s\n", errorMap.str);
}
}
JCLinkedList_Free (&mylist);
}

return 0;
}
--------------end-----------------------------------

--------------------------------------------------------------------
output:
a; a; a; a; a; a; a; a; a; a.
Have 10 elements in this list

a; a; a; a; a; a; a; a; a; a; b; b; b; b; b; b; b; b; b; b.
Have 20 elements in this list

a; a; a; a; a; b; b; b; b; b; b; b; b; b; b.
Have 15 elements in this list

a; a; a; a; a; b; b; b; b; b.
Have 10 elements in this list

free list successfully!

 

[Ben Bacarisse]

I implemented a linked list in C, make, vim, gcc and gdb, could you
please verify me if I am wrong?
and how to improve them?
thanks very much!

------------Makefile-----------------------------
all: test
test: clean
gcc -g test.c linkedlist.c -o test.exe
clean:
-rm -rf test.exe
.PHONEY: clean all

That's a bit odd but this is a C group. Not sure where to ask about
make.

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

---------------constant.h---------------------
#ifndef _CONSTANT_
#define _CONSTANT_

Names like this a reserved for use by the implementation. A good
pattern for guards is H_CONSTANT. Add a trailing _ if you prefer.

#define JC_ERR_NO_MEMORY 10001

#define JC_ERR_NOT_FOUND 60001
#define JC_ERR_EMPTY_LIST 60002
#define JC_ERR_NOT_STACK_AND_QUEUE 60003

#define STACK 1
#define QUEUE 0

After taking care to prefix most of your names STACK and QUEUE are
left plain.

#endif

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

static
ErrorMap errorMap[] = {
{JC_ERR_NO_MEMORY, "no memory can be used"},
{JC_ERR_NOT_FOUND, "element not found in list"},
{JC_ERR_EMPTY_LIST, "empty list"},
{JC_ERR_NOT_STACK_AND_QUEUE, "pop not in stack and queue"},
};
#endif

----------------end-----------------------
---------------JC.h---------------------

#ifndef _JC_
#define _JC_
#include<stdio.h>
#include<stdlib.h>
#include "constant.h"
#include "errormap.h"
#endif

----------------end-------------------------
---------------linkedlist.h---------------------

#include "JC.h"
struct JCLinkedNode {
char *elem;
struct JCLinkedNode *next;
struct JCLinkedNode *prev;
};

struct JCLinkedList{
struct JCLinkedNode *first;
struct JCLinkedNode *last;
};

typedef struct JCLinkedNode JCLinkedNode;
typedef struct JCLinkedList JCLinkedList;

int JCLinkedList_Init(JCLinkedList **list);
int JCLinkedList_Free(JCLinkedList **list);
int JCLinkedList_Insert(JCLinkedList *list, const char* elem);
int JCLinkedList_Pop(JCLinkedList *list, int flag);
int JCLinkedList_Output(JCLinkedList *list);

I don't much like flags. Why not provide pop and dequeue? Will there
really be a need to choose which to use under control of some data?
If so, I'd still write both and a one-line wrapper decide which to
call.

If you have both removes, why is there only one way to insert?

There should be at least a function to test for empty.

Finally, XXX_Free takes ** because it frees the list structure. This
means I can't use an automatic variable. In general, I'd want to
permit this.

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

--------------------linkedlist.c-------------------------------------
/* linked list*/
#include "linkedlist.h"

int
JCLinkedList_Init (JCLinkedList **list)
{
int status = 0;

*list = (JCLinkedList*) malloc(sizeof(JCLinkedList));

I'd write

*list = malloc(sizeof **list);

if ( NULL == *list ) {
status = JC_ERR_NO_MEMORY;
}

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

TERMINATE:

return status;
} /* End of JCLinkedList_Init */

Personally, I'd separate initialisation from allocation so I can use a
local variable for the JCLinkedList.

/* Free the list*/
int
JCLinkedList_Free (JCLinkedList **list)
{
int status = 0;

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

Why these last two?

free (oldp);
oldp = NULL;

Why this? oldp is about to vanish!

}
(*list)->first = (*list)->last = NULL;
Ditto.

free (*list);
*list = NULL;

TERMINATE:

return status;
} /* End of JCLinkedList_Free */

int
JCLinkedList_Insert (JCLinkedList *list,
const char* elem)
{
int status = 0;

if ( list->first == NULL &&
list->last == NULL ) {
list->first =
(JCLinkedNode*) malloc (sizeof(JCLinkedNode));

I'd write

list->first = malloc(sizeof *list->first);

(I promise I won't say the same thing again!)

list->last = list->first;

You don't check the malloc worked.

list->first->elem = (char*) malloc (strlen (elem) + 1);
if ( list->first->elem != NULL ) {
strcpy (list->first->elem, elem);
}
list->first->next = list->last->next = NULL;
list->first->prev = list->last->prev = NULL;
}
else {
list->last->next =
(JCLinkedNode*) malloc (sizeof(JCLinkedNode));

list->last->next->elem = (char*) malloc (strlen (elem) + 1);
if ( list->last->next->elem != NULL ) {
strcpy(list->last->next->elem, elem);
}
list->last->next->prev = list->last;
list->last->next->next = NULL;

list->last = list->last->next;
}

I would try to avoid the duplicated code. At the very least I would
have an allocate function the does the malloc of the two parts (you
can combine them if you want) and copies the string. It would be used
to set status right at the start.

int status = node_alloc_and_init(elem);

TERMINATE:

return status;
} /* END of JCLinkedList_Insert */

int
JCLinkedList_Output (JCLinkedList *list)
{
int count = 0;
struct JCLinkedNode *p;

if ( list->first != NULL &&
list->last != NULL ) {
p = list->first;
while ( p != list->last ) {

When there is only one element, surely this is false right away? Your
test code should include all the odd cases like having only one element.

++count;
printf ("%s; ", p->elem);
p = p->next;
}
printf("%s.", p->elem);
++count;
printf ("\n");
printf("Have %d elements in this list\n\n", count);

Is such a rigid output function really useful? You could at least
allow the stream to be passed in!

}

return 0;
} /* End of JCLinkedList_Output */

// Pop is a method used in both stack and queue with flag
int
JCLinkedList_Pop (JCLinkedList *list, int flag)
{
int status = 0;
JCLinkedNode *p;

if ( flag == STACK) {
if ( list->first != NULL) {
p = list->first;
list->first = list->first->next;
free(p->elem);
p->elem = NULL;
}
else {
status = JC_ERR_EMPTY_LIST;
}
}
else if ( flag == QUEUE ) {
if ( list->last != NULL) {
p = list->last;
list->last = list->last->prev;
free(p->elem);
p->elem = NULL;
}
else {
status = JC_ERR_EMPTY_LIST;
}
}
else {
status = JC_ERR_NOT_STACK_AND_QUEUE;
}

You don't free the list node.

TERMINATE:

return status;
} /* End of JCLinkedList_Pop */

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

-----------------------test.c--------------------------------
#include "linkedlist.h"

int main(void)
{
int i;
int status = 0;
struct JCLinkedList* mylist = NULL;

status = JCLinkedList_Init (&mylist);
if ( status ) goto TERMINATE;

I don't like neutral names like status. A "true" (non-zero) values
indicates a problem, so I'd call it "error". You then get to write:

if (error) ...;

// insert 10 elements
for (i = 0; i < 10; ++i) {
status = JCLinkedList_Insert (mylist, "a");
if ( status ) goto TERMINATE;
}

status = JCLinkedList_Output (mylist);
if ( status ) goto TERMINATE;

// insert 10 elements too
for (i = 0; i < 10; ++i) {
status = JCLinkedList_Insert (mylist, "b");
if ( status ) goto TERMINATE;
}
status = JCLinkedList_Output (mylist);
if ( status ) goto TERMINATE;

// pop like stack
for (i = 0; i < 5; ++i) {
status = JCLinkedList_Pop (mylist, STACK);
if ( status ) goto TERMINATE;
}
status = JCLinkedList_Output (mylist);
if ( status ) goto TERMINATE;

// pop like queue
for (i = 0; i < 5; ++i) {
status = JCLinkedList_Pop (mylist, QUEUE);
if ( status ) goto TERMINATE;
}
status = JCLinkedList_Output (mylist);
if ( status ) goto TERMINATE;


status = JCLinkedList_Free (&mylist);
if ( status ) goto TERMINATE;

if ( NULL == mylist ) printf ("free list successfully!\n");

TERMINATE:
if ( status ) {
int nErrors = sizeof (errorMap) / sizeof (ErrorMap);

I had to go check the definition of ErrorMap. If you'd written:

int nErrors = sizeof errorMap / sizeof errorMap[0];

I would not have had to check.

for (i = 0; i < nErrors; ++i) {
if ( errorMap.error == status ) {
printf ("JC Error: %s\n", errorMap.str);
}
}
JCLinkedList_Free (&mylist);
}

return 0;
}
--------------end-----------------------------------

 

[Nick Keighley]

Dear friends,

he thinks comp.lang.c is going to be his friends...

I implemented a linked list in C, make, vim, gcc and gdb,  could you
please verify me if I am wrong?
and how to improve them?
thanks very much!

My first suggestion would be "write a test program.
But you did that already!

Looks pretty good to me.

---------------constant.h---------------------
#ifndef _CONSTANT_
#define _CONSTANT_

variables starting with underscores (the rules are slightly more
complicated, but my rule errs on the side of caution) are reserved
for the implementation (the compiler and standard library writers).

--------------------linkedlist.c-------------------------------------
/* linked list*/
#include "linkedlist.h"

   int
JCLinkedList_Init (JCLinkedList **list)
{
   int status = 0;

   *list = (JCLinkedList*) malloc(sizeof(JCLinkedList));

there's not need for the cast and it might hide an error
(that you'd forgotten to include stdlib.h)

   if ( NULL == *list ) {
      status = JC_ERR_NO_MEMORY;
   }

   (*list)->first = NULL;

and if list were NULL what would happen?

   (*list)->last  = NULL;

TERMINATE:

I don't like the TERMINATE labels. But then again you don't
use most of them...

   return status;

} /* End of JCLinkedList_Init */

   int
JCLinkedList_Output (JCLinkedList *list)
{
   int count = 0;
   struct JCLinkedNode *p;

   if ( list->first != NULL &&
         list->last  != NULL   ) {
      p = list->first;
      while ( p != list->last ) {
         ++count;
         printf ("%s; ", p->elem);
         p = p->next;
      }
      printf("%s.", p->elem);
      ++count;
      printf ("\n");
      printf("Have %d elements in this list\n\n", count);
   }

   return 0;

why return zero?

} /* End of JCLinkedList_Output */

-----------------------test.c--------------------------------
#include "linkedlist.h"

int main(void)
{
   int i;
   int status = 0;
   struct JCLinkedList* mylist = NULL;

   status = JCLinkedList_Init (&mylist);
   if ( status )  goto TERMINATE;

   // insert 10 elements
   for (i = 0; i < 10; ++i) {
      status = JCLinkedList_Insert (mylist, "a");
      if ( status )  goto TERMINATE;
   }

I'm really not a fan of goto...

   status = JCLinkedList_Output (mylist);
   if ( status )  goto TERMINATE;

   // insert 10 elements too
   for (i = 0; i < 10; ++i) {
      status = JCLinkedList_Insert (mylist, "b");
      if ( status )  goto TERMINATE;
   }
   status = JCLinkedList_Output (mylist);
   if ( status )  goto TERMINATE;

   // pop like stack
   for (i = 0; i < 5; ++i) {
      status  = JCLinkedList_Pop (mylist, STACK);
      if ( status )  goto TERMINATE;
   }
   status = JCLinkedList_Output (mylist);
   if ( status )  goto TERMINATE;

   // pop like queue
   for (i = 0; i < 5; ++i) {
      status  = JCLinkedList_Pop (mylist, QUEUE);
      if ( status )  goto TERMINATE;
   }
   status = JCLinkedList_Output (mylist);
   if ( status )  goto TERMINATE;

   status = JCLinkedList_Free (&mylist);
   if ( status )  goto TERMINATE;

   if ( NULL == mylist )  printf ("free list successfully!\n");

TERMINATE:
   if ( status ) {
      int nErrors = sizeof (errorMap) / sizeof (ErrorMap);

      for (i = 0; i < nErrors; ++i) {
         if ( errorMap.error == status ) {
            printf ("JC Error: %s\n", errorMap.str);
         }
      }
      JCLinkedList_Free (&mylist);
   }

   return 0;}

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

--------------------------------------------------------------------
output:
a; a; a; a; a; a; a; a; a; a.
Have 10 elements in this list

a; a; a; a; a; a; a; a; a; a; b; b; b; b; b; b; b; b; b; b.
Have 20 elements in this list

a; a; a; a; a; b; b; b; b; b; b; b; b; b; b.
Have 15 elements in this list

a; a; a; a; a; b; b; b; b; b.
Have 10 elements in this list

free list successfully!

--
Nick Keighley

"Half-assed programming was a time-filler that, like knitting,
must date to the beginning of human experience."
"A Fire Upon The Deep" by Verne Vinge

 

[JC]

Thanks for Ben and Nick's help. following is the version 1.1
Looking forward to your suggestion!

###########test.c#################
#include "linkedlist.h"


int test_one_element(void)
{
int i;
int error = 0;
JCLinkedList* mylist = NULL;

error = JCLinkedList_Init (&mylist);
if ( error ) goto TERMINATE;

// insert 1 elements
error = JCLinkedList_Insert (mylist, "a");
if ( error ) goto TERMINATE;

error = JCLinkedList_Output (mylist);

// pop like stack
error = JCLinkedList_Pop (mylist, STACK);
if ( error ) goto TERMINATE;
error = JCLinkedList_Output (mylist);
if ( error ) goto TERMINATE;

// insert 1 elements
error = JCLinkedList_Insert (mylist, "b");
if ( error ) goto TERMINATE;

error = JCLinkedList_Output (mylist);

// pop like queue
error = JCLinkedList_Pop (mylist, QUEUE);
if ( error ) goto TERMINATE;
error = JCLinkedList_Output (mylist);
if ( error ) goto TERMINATE;

// insert 10 elements again
for (i = 0; i < 10; ++i) {
error = JCLinkedList_Insert (mylist, "a");
if ( error ) goto TERMINATE;
}

error = JCLinkedList_Output (mylist);
if ( error ) goto TERMINATE;

error = JCLinkedList_Free (&mylist);
if ( error ) goto TERMINATE;

if ( NULL == mylist ) printf ("free list successfully!\n\n");

TERMINATE:

if ( mylist ) JCLinkedList_Free (&mylist);
return error;
}
int test_many_elements()
{
int i;
int error = 0;
JCLinkedList* mylist = NULL;

error = JCLinkedList_Init (&mylist);
if ( error ) goto TERMINATE;

// insert 10 elements
for (i = 0; i < 10; ++i) {
error = JCLinkedList_Insert (mylist, "a");
if ( error ) goto TERMINATE;
}

error = JCLinkedList_Output (mylist);
if ( error ) goto TERMINATE;

// insert 10 elements too
for (i = 0; i < 10; ++i) {
error = JCLinkedList_Insert (mylist, "b");
if ( error ) goto TERMINATE;
}
error = JCLinkedList_Output (mylist);
if ( error ) goto TERMINATE;

// pop like stack
for (i = 0; i < 5; ++i) {
error = JCLinkedList_Pop (mylist, STACK);
if ( error ) goto TERMINATE;
}
error = JCLinkedList_Output (mylist);
if ( error ) goto TERMINATE;

// pop like queue
for (i = 0; i < 5; ++i) {
error = JCLinkedList_Pop (mylist, QUEUE);
if ( error ) goto TERMINATE;
}
error = JCLinkedList_Output (mylist);
if ( error ) goto TERMINATE;

// pop like stack
for (i = 0; i < 10; ++i) {
error = JCLinkedList_Pop (mylist, STACK);
if ( error ) goto TERMINATE;
}
error = JCLinkedList_Output (mylist);
if ( error ) goto TERMINATE;

// insert 10 elements again
for (i = 0; i < 10; ++i) {
error = JCLinkedList_Insert (mylist, "a");
if ( error ) goto TERMINATE;
}

error = JCLinkedList_Output (mylist);
if ( error ) goto TERMINATE;

error = JCLinkedList_Free (&mylist);
if ( error ) goto TERMINATE;

if ( NULL == mylist ) printf ("free list successfully!\n\n");

TERMINATE:

if ( mylist ) JCLinkedList_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);

for (i = 0; i < nErrors; ++i) {
if ( errorMap.error == error ) {
printf ("JC Error: %s\n", errorMap.str);
}
}
}

return 0;
}
#############end####################################

################linkedlist.h########################

#include "JC.h"
struct JCLinkedNode {
char *elem;
struct JCLinkedNode *next;
struct JCLinkedNode *prev;
};

struct JCLinkedList{
struct JCLinkedNode *first;
struct JCLinkedNode *last;
};

typedef struct JCLinkedNode JCLinkedNode;
typedef struct JCLinkedList JCLinkedList;

int JCLinkedList_Init(JCLinkedList **list);
int JCLinkedList_Free(JCLinkedList **list);
int JCLinkedList_Insert(JCLinkedList *list, const char* elem);
int JCLinkedList_Pop(JCLinkedList *list, int flag);
int JCLinkedList_Output(JCLinkedList *list);
int JCLinkedList_Length(JCLinkedList *list);

###################End################################

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

int
JCLinkedList_Init (JCLinkedList **list)
{
int error = 0;

*list = malloc(sizeof **list);
if ( NULL == *list ) {
error = JC_ERR_NO_MEMORY;
}

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

TERMINATE:

return error;
} /* End of JCLinkedList_Init */


/* Free the list*/
int
JCLinkedList_Free (JCLinkedList **list)
{
int error = 0;

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

TERMINATE:

return error;
} /* End of JCLinkedList_Free */

int
JCLinkedList_Insert (JCLinkedList *list,
const char* elem)
{
int error = 0;

if ( list->first == NULL &&
list->last == NULL ) {
list->first = malloc (sizeof (*list->first));
if ( NULL == list->first ) {
error = JC_ERR_NO_MEMORY;
}

list->last = list->first;

list->first->elem = (char*) malloc (strlen (elem) + 1);
if ( list->first->elem != NULL ) {
strcpy (list->first->elem, elem);
}
list->first->next = list->last->next = NULL;
list->first->prev = list->last->prev = NULL;
}
else {
list->last->next = malloc (sizeof(*(list->last->next)));
if ( NULL == list->last->next ) {
error = JC_ERR_NO_MEMORY;
}

list->last->next->elem = (char*) malloc (strlen (elem) + 1);
if ( list->last->next->elem != NULL ) {
strcpy(list->last->next->elem, elem);
}
list->last->next->prev = list->last;
list->last->next->next = NULL;

list->last = list->last->next;
}

TERMINATE:

return error;
} /* END of JCLinkedList_Insert */

int
JCLinkedList_Output (JCLinkedList *list)
{
JCLinkedNode *p;

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

return 0;
} /* End of JCLinkedList_Output */

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

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

// If not only 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 = JC_ERR_EMPTY_LIST;
}
}
else if ( flag == 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 = JC_ERR_EMPTY_LIST;
}
}
else {
error = JC_ERR_NOT_STACK_AND_QUEUE;
}

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

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

free(p);
p = NULL;

TERMINATE:

return error;
} /* End of JCLinkedList_Pop */
int
JCLinkedList_Length(JCLinkedList *list)
{
int length = 0;
JCLinkedNode *p = NULL;

if ( list != NULL) {
if ( list->first == list->last ) {
if ( list->first == NULL ) {
length = 0;
}
else {
length = 1;
}
}
else {
p = list->first;
while ( p != NULL) {
++length;
p = p->next;
}
}
}

return length;
} /* END of JCLinkedList_Length */

###############END############################

####################constant.h and errormap.h and JC.h########

#ifndef H_CONSTANT
#define H_CONSTANT
#define LIST_INIT_SIZE 5
#define LISTINCREMENT 5

#define JC_ERR_NO_MEMORY 10001
#define JC_ERR_NOTVALID_INDEX 10002

#define JC_ERR_NOT_FOUND 60001
#define JC_ERR_EMPTY_LIST 60002
#define JC_ERR_NOT_STACK_AND_QUEUE 60003

#define Type int
#define STACK 1
#define QUEUE 0

#endif

#ifndef H_ERRORMAP
#define H_ERRORMAP
typedef struct {
int error;
const char *str;
} ErrorMap;

static
ErrorMap errorMap[] = {
{JC_ERR_NO_MEMORY, "no memory can be used"},
{JC_ERR_NOTVALID_INDEX, "not valid index"},
{JC_ERR_NOT_FOUND, "element not found in list"},
{JC_ERR_EMPTY_LIST, "empty list"},
{JC_ERR_NOT_STACK_AND_QUEUE, "pop not in stack and queue"},
};
#endif

#ifndef H_JC
#define H_JC
#include<stdio.h>
#include<stdlib.h>
#include "constant.h"
#include "errormap.h"
#endif

################END############################################

John Cui

 

[JC]

Ben, looks you didn't get my reply received? yes?

 

[JC]

That's a bit odd but this is a C group.  Not sure where to ask about
make.

I am newbie of make tool, so please give me some suggestion if I am
wrong.

After taking care to prefix most of your names STACK and QUEUE are
left plain.

I didn't understand here.

I don't much like flags.  Why not provide pop and dequeue?  Will there
really be a need to choose which to use under control of some data?
If so, I'd still write both and a one-line wrapper decide which to
call.

If you have both removes, why is there only one way to insert?

Because the list in python mix the stack and queue, and I think it is
good, so I design my linked list like this.

Finally, XXX_Free takes ** because it frees the list structure.  This
means I can't use an automatic variable.  In general, I'd want to
permit this.

I didn't understand either here.

I'd write

  *list = malloc(sizeof **list);

Then what is the excactly diff between these 2 method of using malloc.

Personally, I'd separate initialisation from allocation so I can use a
local variable for the JCLinkedList.

Why separate can use local variable? could you please give me an
example for the advantage?

Why these last two?


Why this?  oldp is about to vanish!


Ditto.

Here, because node of list has char* data type, so I should use oldp
to store list->first temp,
then free(oldp->elem) and free(oldp).After that, assign NULL to them.

I would try to avoid the duplicated code.  At the very least I would
have an allocate function the does the malloc of the two parts (you
can combine them if you want) and copies the string.  It would be used
to set status right at the start.

To avoid duplicated code here, I thought about it ago, but didn't get
any idea,
So, could you give me some suggestion?

  int status = node_alloc_and_init(elem);





When there is only one element, surely this is false right away?  Your
test code should include all the odd cases like having only one element.


Is such a rigid output function really useful?  You could at least
allow the stream to be passed in!

I want to display all elements in list, so provide this function,
seems you hava better way?

I don't like neutral names like status.  A "true" (non-zero) values
indicates a problem, so I'd call it "error".  You then get to write:

  if (error) ...;

error is better than status, while, "true" doesn't exsit in C lang,
correct?

TERMINATE:
   if ( status ) {
      int nErrors = sizeof (errorMap) / sizeof (ErrorMap);

I had to go check the definition of ErrorMap.  If you'd written:

  int nErrors = sizeof errorMap / sizeof errorMap[0];

I would not have had to check.

Why? the ErrorMap is the struct which was used to store errorMap.
Anyway, errorMap[0] is more clear for computing nErrors.

Thanks,

John Cui

 

[Ben Bacarisse]

I am newbie of make tool, so please give me some suggestion if I am
wrong.

I can't without getting into long off-topic discussion of make
versions on Windows systems. The simple point is that make has rule
to build files and the rule for test does not make a file called test,
but test.exe.

I didn't understand here.

I don't know how else to say it. Why did you give the other names a
JC_ prefix? If it was for a reason, why did that reason not apply to
names like STACK and QUEUE?

Because the list in python mix the stack and queue, and I think it is
good, so I design my linked list like this.

My point was not about removing from both ends (that's a good idea but
I would do it slightly differently) but about why you can only add to
one end of a list.

I didn't understand either here.

It is sometimes a good idea to let users of your code allocate
structures themselves. This way you can avoid malloc and free for the
list object (you still need it for the nodes). I'd like to be able to
write:

JCLinkedList my_list;
JCLinkedList_Init(&my_list);
/* add and remove items */
JCLinkedList_Free(&my_list);

this avoiding the need to allocate the list object itself.

Then what is the excactly diff between these 2 method of using
malloc.

None. I just prefer the shorter version. Feel free to keep using the
longer version -- it is only a matter of style.

Why separate can use local variable? could you please give me an
example for the advantage?

It is the same point I made further up. There is no need to make the
list object allocated with malloc. It could simply be an ordinary
variable.

Here, because node of list has char* data type, so I should use oldp
to store list->first temp,
then free(oldp->elem) and free(oldp).After that, assign NULL to
them.

I know -- I can read the code! I was asking why you assign NULL to
things that are going to disappear?

To avoid duplicated code here, I thought about it ago, but didn't get
any idea,
So, could you give me some suggestion?

Yes, I gave you one: a function to do the allocation of the node and
the string together with copying of the string.

like this.

I want to display all elements in list, so provide this function,
seems you hava better way?

A print function should be able to print to any stream and should not
print more than is needed. I would even make the separator a string
that is passed in so I can print "a; b; c" or "a:b:c" with the same
function.

error is better than status, while, "true" doesn't exsit in C lang,
correct?

Sorry, I can't understand this.

TERMINATE:
   if ( status ) {
      int nErrors = sizeof (errorMap) / sizeof (ErrorMap);

I had to go check the definition of ErrorMap.  If you'd written:

  int nErrors = sizeof errorMap / sizeof errorMap[0];

I would not have had to check.

Why? the ErrorMap is the struct which was used to store errorMap.
Anyway, errorMap[0] is more clear for computing nErrors.

Yes, that was my point. One reason it is more clear is because I uses
less information. Anyone can tell what sizeof A/sizeof A[0] does
provided they know A is an array.

 

[Joachim Schmitz]

None. I just prefer the shorter version. Feel free to keep using the
longer version -- it is only a matter of style.

There's more to it (and I'm sure Ben knows this):
a) without the cast the compiler can detect and complain about a missing
prototype.
b) should the type of list change (or get renamed, like in my version to
JSLinked List ;-)), the short version doesn't need to get changed

Bye, Jojo

 

[JC]

There's more to it (and I'm sure Ben knows this):
a) without the cast the compiler can detect and complain about a missing
prototype.
b) should the type of list change (or get renamed, like in my version to
JSLinked List ;-)), the short version doesn't need to get changed

Hmm, you got the points!

Thanks

John Cui

 

[JC]

After friends' help, Mylist version 1.2 goes live.

//////////////////////// constant.h ////////////////////////////
#ifndef H_CONSTANT
#define H_CONSTANT

#define C_ERR_NO_MEMORY 10001

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

#define C_STACK 1
#define C_QUEUE 0

#endif

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

//////////////////////// C.h ////////////////////////////
#ifndef H_C
#define H_C
#include<stdio.h>
#include<stdlib.h>
#include "constant.h"
#include "errormap.h"
#endif

//////////////////////// linkedlist.h ////////////////////////////
#ifndef H_LINKEDLIST
#define H_LINKEDLIST
#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_Insert(CLinkedList *list, const char* elem);
int CLinkedList_Pop(CLinkedList *list, int flag);
int CLinkedList_Output(CLinkedList *list, const char* sp);
int CLinkedList_Length(CLinkedList *list);
#endif


//////////////////////// 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;
}

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) + 1);
}
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;
}

(*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);
oldp->elem = NULL;
oldp->next = NULL;
free (oldp);
oldp = NULL;
}
(*list)->first = (*list)->last = NULL;
free (*list);
*list = NULL;

TERMINATE:

return error;
} /* End of CLinkedList_Free */

int
CLinkedList_Append (CLinkedList *list,
const char* elem)
{
int error = 0;

if ( list->first == NULL &&
list->last == NULL ) {
error = CNode_Alloc_and_Init (&(list->first), elem);
if ( error ) goto TERMINATE;

list->last = list->first;
}
else {
error = CNode_Alloc_and_Init (&(list->last->next), elem);
if ( error ) goto TERMINATE;
list->last->next->prev = list->last;
list->last = list->last->next;
}

TERMINATE:

return error;
} /* END of CLinkedList_Insert */

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;
}
}
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;
}
}
else {
error = C_ERR_NOT_STACK_AND_QUEUE;
}

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 = NULL;

if ( list != NULL) {
if ( list->first == list->last ) {
if ( list->first == NULL ) {
length = 0;
}
else {
length = 1;
}
}
else {
p = list->first;
while ( p != NULL) {
++length;
p = p->next;
}
}
}

return length;
} /* END of CLinkedList_Length */

------------------------test.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;

// insert 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;

// insert 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;

// 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 test_many_elements()
{
int i;
int error = 0;
CLinkedList* mylist = NULL;

error = CLinkedList_Init (&mylist);
if ( error ) goto TERMINATE;

// insert 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;

// insert 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;

// 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 ("C Error: %s\n", errorMap.str);
}
}
}

return 0;
}

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

output-----------------------------------------------------------
a : a : a : a : a : a : a : a : a : a :
Have 10 elements in this list

a : a : a : a : a : a : a : a : a : a : b : b : b : b : b : b : b :
b : b : b :
Have 20 elements in this list

a was deleted
a was deleted
a was deleted
a was deleted
a was deleted
a : a : a : a : a : b : b : b : b : b : b : b : b : b : b :
Have 15 elements in this list

b was deleted
b was deleted
b was deleted
b was deleted
b was deleted
a : a : a : a : a : b : b : b : b : b :
Have 10 elements in this list

a was deleted
a was deleted
a was deleted
a was deleted
a was deleted
b was deleted
b was deleted
b was deleted
b was deleted
b was deleted
This is an empty list now

a : a : a : a : a : a : a : a : a : a :
Have 10 elements in this list

free list successfully!

a :
Have 1 elements in this list

a was deleted
This is an empty list now

b :
Have 1 elements in this list

b was deleted
This is an empty list now

a : a : a : a : a : a : a : a : a : a :
Have 10 elements in this list

free list successfully!


Thanks,

John Cui

 

[Ike Naar]

[...]
(*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);

 

[JC]

[...]
     (*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?

John Cui

 

[Nick Keighley]

[...]
     (*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?

Beware of strcpy() it doesn't always do what people expect.

char t1[10];
char t2[1001];
char s1[] = "0123456789";

strncpy (t1, s1, 10); /* t1 is not null terminated */
strncpy (t2, s1, 1000); /* adds 990 extra nuls onto the end of t2
*/

 

[JC]

Beware of strcpy() it doesn't always do what people expect.

Yes, we should know strncpy very well.

char t1[10];
char t2[1001];
char s1[] = "0123456789";

strncpy (t1, s1, 10);      /* t1 is not null terminated */

Here, we should give 11 size to t1 when decare it.
and call strncpy like: strncpy(t1, s1, strlen(t1));
then t1 is have null terminated.

strncpy (t2, s1, 1000);    /* adds 990 extra nuls onto the end of t2

Yes, extra null will be added to t2.

So the generally usage of strncpy should be:

strncpy(s1, s2, strlen(s1));

And I found a bug in my code,

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

Cheers!

John Cui

 

[JC]

JC said:

Yes, we should know strncpy very well.

char t1[10];
char t2[1001];
char s1[] = "0123456789";
strncpy (t1, s1, 10);      /* t1 is not null terminated */

Here, we should give 11 size to t1 when decare it.
and call strncpy like: strncpy(t1, s1, strlen(t1));

No, that's a terrible idea - especially in this case, where t1 is
known to be indeterminate.

If you don't know it's safe to use strcpy, it probably isn't proper
to use strncpy either.

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

Is it correct?

John Cui

 

[Ben Bacarisse]

There's more to it (and I'm sure Ben knows this):

Yes, I do, but I also think the better method is somewhat "over
sold".

a) without the cast the compiler can detect and complain about a
missing prototype.

The compiler can do that for the version *with* the cast. In fact I'd
go so far as to say that I'd try to use a different one if it did not.
For C99 a diagnostic is required but even for C90 the compiler knows
malloc and can complain that it is being implicitly declared in an
inconsistent way. Furthermore, I'd want to use a compiler that warns
about the conversion from int to pointer.

b) should the type of list change (or get renamed, like in my version
to JSLinked List ;-)), the short version doesn't need to get changed

My preferred argument is that the short form is self-contained. You
don't need to know anything else to know that it is correct (all other
things being correct of course).

 

[Joachim Schmitz]

My preferred argument is that the short form is self-contained. You
don't need to know anything else to know that it is correct (all other
things being correct of course).

That's reason c) then

Bye, Jojo

 

[Richard Bos]

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

 

[Ben Bacarisse]

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;
}

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

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

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

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

}
else {
(*node)->elem = NULL;
}
(*node)->next = NULL;
(*node)->prev = NULL;

TERMINATE:

return error;
}

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

int
CLinkedList_Init (CLinkedList **list)
{
int error = 0;

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

(*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);
oldp->elem = NULL;
oldp->next = NULL;
free (oldp);
oldp = NULL;
}
(*list)->first = (*list)->last = NULL;
free (*list);
*list = NULL;

TERMINATE:

return error;
} /* End of CLinkedList_Free */

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

int
CLinkedList_Append (CLinkedList *list,
const char* elem)
{
int error = 0;

if ( list->first == NULL &&
list->last == NULL ) {
error = CNode_Alloc_and_Init (&(list->first), elem);
if ( error ) goto TERMINATE;

list->last = list->first;
}
else {
error = CNode_Alloc_and_Init (&(list->last->next), elem);
if ( error ) goto TERMINATE;

There two lines are still almost duplicated.

list->last->next->prev = list->last;
list->last = list->last->next;
}

TERMINATE:

return error;
} /* END of CLinkedList_Insert */

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

int
CLinkedList_Length(CLinkedList *list)
{
int length = 0;
CLinkedNode *p = NULL;

if ( list != NULL) {
if ( list->first == list->last ) {
if ( list->first == NULL ) {
length = 0;
}
else {
length = 1;
}
}

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

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

return length;
} /* END of CLinkedList_Length */

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

<snip>

 

[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';
}

correct?

John Cui