Board index » C Language

All times are UTC



 My new linked list: request for comment please 
Author Message
james C. Georga
#1 / 10
 My new linked list: request for comment please

Here's an implementation of a linked list I did today. Comments and
suggestions would be great.

The list holds pointers to unspecified types ( void* ), and the user of
the list is wholly responsible for the objects he's adding to the list.

I tried to make the user as unaware of the list internals as possible. I
did this by only exposing opaque pointers in the public header file and
forcing the user to use the public interface functions.

I'm especially interested in what y'all think of the iterator, as this
is the first one I've ever written.

( I realllllly love opaque pointers )!

Public header file:
------------------------------------------------------------
/* List.h
 * by J. C. Georgas
 * 2001-08-30
 * Public header file for List.c
 */

#ifndef LIST_H
#define LIST_H

typedef struct _ListRec* List;
typedef struct _ListNodeRec** ListIter;

/* constructor: */
List newList( void );

/* destructor: */
void deleteList( List list );

/* modifiers: */
void listAdd( List list, void* data );
void listRemove( List list, void* data );

/* iterator functions: */
/**
  * Returns an iterator pointing to the first node of the given list.
  */
ListIter listIter( List list );

/**
  * Iterates to the next node of the given iterator's list.
  */
void listIterNext( ListIter iter );

/**
  * Returns a pointer to the contents of the iterator's current node.
  */
void* listIterData( ListIter iter );

#endif /* LIST_H */
------------------------------------------------------------

Private header file:
------------------------------------------------------------
/* ListP.h
 * by J. C. Georgas
 * 2001-08-30
 * Private header file for List.c
 */

#ifndef LIST_P_H
#define LIST_P_H

#include "List.h"

typedef struct _ListNodeRec
{
 void* data;
 struct _ListNodeRec* next;

Quote:
} ListNodeRec, *ListNode;

typedef struct _ListRec
{
 ListNode head;
 ListNode tail;

Quote:
} ListRec;

/* node functions: */
static ListNode newListNode( void* data );
static void deleteListNode( ListNode node );

#endif /* LIST_P_H */
------------------------------------------------------------

Implementation:
------------------------------------------------------------
/* List.c
 * by J. C. Georgas
 * 2001-08-30
 * Linked List class
 */

#include <stdio.h>
#include <stdlib.h> /* malloc(), free() */

#include "ListP.h"

List newList( void )
{
 List list = NULL;

 /* allocate the space for the list: */
 if ( NULL != ( list = malloc( sizeof( struct _ListRec ))))
 {
  list->head = NULL;
  list->tail = list->head;
 }

 return list;

Quote:
}

void deleteList( List list )
{
 ListNode current = list->head;

 /* delete the nodes: */
 while ( current )
 {
  ListNode temp = current->next;
  deleteListNode( temp );
  current = temp;
 }

 /* delete the list: */
 free( list );

Quote:
}

void listAdd( List list, void* data )
{
 ListNode node = newListNode( data );

 /* check for an empty list: */
 if ( list->tail )
 {
  /* add the node to the end of the list: */
  list->tail->next = node;
  list->tail = list->tail->next;
 }
 else
 {
  /* add to an empty list: */
  list->head = node;
  list->tail = list->head;
 }

Quote:
}

void listRemove( List list, void* data )
{
 ListNode prev = NULL;
 ListNode current = list->head;

 while ( current )
 {
  if ( current->data == data )
  {
   /* unlink the node: */
   if ( prev )
    prev->next = current->next;
   else
    list->head = current->next;

   /* tie off the end: */
   if ( current == list->tail )
    list->tail = prev;

   /* delete the node: */
   deleteListNode( current );
   break;
  }

  /* iterate to the next node: */
  prev = current;
  current = current->next;
 };

Quote:
}

/* iterator function definitions: */
/**
  * Returns an iterator pointing to the first node of the given list.
  */
ListIter listIter( List list )
{
 return &list->head;

Quote:
}

/**
  * Iterates to the next node of the given iterator's list.
  */
void listIterNext( ListIter iter )
{
 *iter = (*iter)->next;

Quote:
}

/**
  * Returns a pointer to the contents of the iterator's current node.
  */
void* listIterData( ListIter iter )
{
 return (*iter)->data;

Quote:
}

/* node functions: */
static ListNode newListNode( void* data )
{
 ListNode node = NULL;

 /* allocate the space for the node: */
 if ( NULL != ( node = malloc( sizeof( struct _ListNodeRec ))))
 {
  node->data = data;
  node->next = NULL;
 }

 return node;

Quote:
}

static void deleteListNode( ListNode node )
{
 free( node );
Quote:
}

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

sample main(), using the list:
------------------------------------------------------------
/* main.c
 * by J. C. Georgas
 * 2001-08-30
 */

#include <stdio.h>

#include "List.h"

int main( int argc, char* argv[] )
{
 List list = newList();
 ListIter iter = NULL;
 char* name1 = "James";
 char* name2 = "Brent";
 char* name3 = "Abdul";
 char* name4 = "Katey";
 char* name5 = "Therese";

 listAdd( list, name1 );
 listAdd( list, name2 );
 listAdd( list, name3 );
 listAdd( list, name4 );
 listAdd( list, name5 );

 iter = listIter( list );

 while ( *iter )
 {
  fprintf( stderr, "%s\n", (char*) listIterData( iter ));
  listIterNext( iter );
 }

 deleteList( list );

 return 0;

Quote:
}

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



Tue, 17 Feb 2004 09:54:54 GMT  
Scott Fluhre
#2 / 10
 My new linked list: request for comment please


Quote:
> Here's an implementation of a linked list I did today. Comments and
> suggestions would be great.

> The list holds pointers to unspecified types ( void* ), and the user of
> the list is wholly responsible for the objects he's adding to the list.

> I tried to make the user as unaware of the list internals as possible. I
> did this by only exposing opaque pointers in the public header file and
> forcing the user to use the public interface functions.

> I'm especially interested in what y'all think of the iterator, as this
> is the first one I've ever written.

> ( I realllllly love opaque pointers )!

> Public header file:
> ------------------------------------------------------------
> /* List.h
>  * by J. C. Georgas
>  * 2001-08-30
>  * Public header file for List.c
>  */

> #ifndef LIST_H
> #define LIST_H

> typedef struct _ListRec* List;
> typedef struct _ListNodeRec** ListIter;

> /* constructor: */
> List newList( void );

> /* destructor: */
> void deleteList( List list );

> /* modifiers: */
> void listAdd( List list, void* data );
> void listRemove( List list, void* data );

> /* iterator functions: */
> /**
>   * Returns an iterator pointing to the first node of the given list.
>   */
> ListIter listIter( List list );

> /**
>   * Iterates to the next node of the given iterator's list.
>   */
> void listIterNext( ListIter iter );

> /**
>   * Returns a pointer to the contents of the iterator's current node.
>   */
> void* listIterData( ListIter iter );

> #endif /* LIST_H */
> ------------------------------------------------------------

> Private header file:
> ------------------------------------------------------------
> /* ListP.h
>  * by J. C. Georgas
>  * 2001-08-30
>  * Private header file for List.c
>  */

> #ifndef LIST_P_H
> #define LIST_P_H

> #include "List.h"

> typedef struct _ListNodeRec
> {
>  void* data;
>  struct _ListNodeRec* next;
> } ListNodeRec, *ListNode;

> typedef struct _ListRec
> {
>  ListNode head;
>  ListNode tail;
> } ListRec;

> /* node functions: */
> static ListNode newListNode( void* data );
> static void deleteListNode( ListNode node );

IMHO: declarations of static functions shouldn't be in header files, even if
you intend that the header file be included by one source file -- that may
change latter on...

- Show quoted text -

Quote:

> #endif /* LIST_P_H */
> ------------------------------------------------------------

> Implementation:
> ------------------------------------------------------------
> /* List.c
>  * by J. C. Georgas
>  * 2001-08-30
>  * Linked List class
>  */

> #include <stdio.h>
> #include <stdlib.h> /* malloc(), free() */

> #include "ListP.h"

> List newList( void )
> {
>  List list = NULL;

>  /* allocate the space for the list: */
>  if ( NULL != ( list = malloc( sizeof( struct _ListRec ))))
>  {
>   list->head = NULL;
>   list->tail = list->head;
>  }

>  return list;
> }

> void deleteList( List list )
> {
>  ListNode current = list->head;

>  /* delete the nodes: */
>  while ( current )
>  {
>   ListNode temp = current->next;
>   deleteListNode( temp );
>   current = temp;

Danger, Will Robinson, Danger!  deleteListNode frees what you pass it, and
hence you just set current to a dangling value, giving Undefined Behavior.
I think you meant:

  deleteListNode(current);

above...

Quote:
>  }

>  /* delete the list: */
>  free( list );
> }

> void listAdd( List list, void* data )
> {
>  ListNode node = newListNode( data );

You should handle malloc failure better here...

- Show quoted text -

Quote:

>  /* check for an empty list: */
>  if ( list->tail )
>  {
>   /* add the node to the end of the list: */
>   list->tail->next = node;
>   list->tail = list->tail->next;
>  }
>  else
>  {
>   /* add to an empty list: */
>   list->head = node;
>   list->tail = list->head;
>  }
> }

> void listRemove( List list, void* data )
> {
>  ListNode prev = NULL;
>  ListNode current = list->head;

>  while ( current )
>  {
>   if ( current->data == data )
>   {
>    /* unlink the node: */
>    if ( prev )
>     prev->next = current->next;
>    else
>     list->head = current->next;

>    /* tie off the end: */
>    if ( current == list->tail )
>     list->tail = prev;

>    /* delete the node: */
>    deleteListNode( current );
>    break;
>   }

>   /* iterate to the next node: */
>   prev = current;
>   current = current->next;
>  };
> }

> /* iterator function definitions: */
> /**
>   * Returns an iterator pointing to the first node of the given list.
>   */
> ListIter listIter( List list )
> {
>  return &list->head;
> }

> /**
>   * Iterates to the next node of the given iterator's list.
>   */
> void listIterNext( ListIter iter )
> {
>  *iter = (*iter)->next;
> }

Your next project: come up with an iterator that works even if the function
that calls the iterator deletes the node that the iterator just returned, as
in:

   for (iter = listIter( list ); *iter; listIterNext( iter )) {
      if (this_node_is_evil( listIterData( iter ) ))
         listRemove( list, listIterData( iter ) );
   }

(Hint: you may find it useful to change the "has more data" expression from
*iter into an explicit function call)

- Show quoted text -

Quote:
> /**
>   * Returns a pointer to the contents of the iterator's current node.
>   */
> void* listIterData( ListIter iter )
> {
>  return (*iter)->data;
> }

> /* node functions: */
> static ListNode newListNode( void* data )
> {
>  ListNode node = NULL;

>  /* allocate the space for the node: */
>  if ( NULL != ( node = malloc( sizeof( struct _ListNodeRec ))))
>  {
>   node->data = data;
>   node->next = NULL;
>  }

>  return node;
> }

> static void deleteListNode( ListNode node )
> {
>  free( node );
> }
> ------------------------------------------------------------

> sample main(), using the list:
> ------------------------------------------------------------
> /* main.c
>  * by J. C. Georgas
>  * 2001-08-30
>  */

> #include <stdio.h>

> #include "List.h"

> int main( int argc, char* argv[] )
> {
>  List list = newList();
>  ListIter iter = NULL;
>  char* name1 = "James";
>  char* name2 = "Brent";
>  char* name3 = "Abdul";
>  char* name4 = "Katey";
>  char* name5 = "Therese";

>  listAdd( list, name1 );
>  listAdd( list, name2 );
>  listAdd( list, name3 );
>  listAdd( list, name4 );
>  listAdd( list, name5 );

>  iter = listIter( list );

>  while ( *iter )
>  {
>   fprintf( stderr, "%s\n", (char*) listIterData( iter ));
>   listIterNext( iter );
>  }

>  deleteList( list );

>  return 0;
> }
> ------------------------------------------------------------
> --


--



Tue, 17 Feb 2004 16:34:58 GMT  
Au Han Bi
#3 / 10
 My new linked list: request for comment please
 for(each_row = 0; each_row<n;each_row ++)
    {
      B[each_row] = each_row + 1;

      for(j=0;j<n;j++)
      {
        for(i=n*each_row; i< n*(each_row+1); i++)
        {
          {
          A[i] = (j+1) + (each_row+1);
          }
        }
      }

I am trying to pass a matrix in an MPI program. As I am using calloc to
call matrix A, I have to pass A
as a single array.
How do i assign A as an array such that the rows are joined succesively?

This is my draft, which however does not work
A[i][j] = i+1 + j+ 1;
A (1,2) = 1+ 2 in vector notation

Can someone advise or show me where I have gone wrong?


--



Tue, 17 Feb 2004 23:59:59 GMT  
james C. Georga
#4 / 10
 My new linked list: request for comment please

Quote:

> >  /* delete the nodes: */
> >  while ( current )
> >  {
> >   ListNode temp = current->next;
> >   deleteListNode( temp );
> >   current = temp;
> Danger, Will Robinson, Danger!  deleteListNode frees what you pass it, and
> hence you just set current to a dangling value, giving Undefined Behavior.
> I think you meant:

>   deleteListNode(current);

> above...

Yes, thank you. That was a typo. Fixed now.

Quote:
> > /**
> >   * Iterates to the next node of the given iterator's list.
> >   */
> > void listIterNext( ListIter iter )
> > {
> >  *iter = (*iter)->next;
> > }
> Your next project: come up with an iterator that works even if the function
> that calls the iterator deletes the node that the iterator just returned, as
> in:

>    for (iter = listIter( list ); *iter; listIterNext( iter )) {
>       if (this_node_is_evil( listIterData( iter ) ))
>          listRemove( list, listIterData( iter ) );
>    }

> (Hint: you may find it useful to change the "has more data" expression from
> *iter into an explicit function call)

So it should still iterate to the next node, even if I delete the current node?
It'll definitely blow up currently, since I I'll be dereferencing a pointer to
invalid data in listIterNext(), after deleting the node. Ok, so I make the
iterator a struct, with pointers to the current _and_ next elements. Then I can
still get the next element.

Aw, jeez! What if the user has two iterators on the same list, and happens to
free the two critical adjacent elements?

Even better, the iterators should automatically reposition to the next element,
if their current element is deleted.
I'll have to think about this one. Gotta go to work now. Thanks again Scott.

    /\V
--



Wed, 18 Feb 2004 00:00:08 GMT  
Thad Smit
#5 / 10
 My new linked list: request for comment please

Quote:

> Here's an implementation of a linked list I did today. Comments and
> suggestions would be great.

> The list holds pointers to unspecified types ( void* ), and the user of
> the list is wholly responsible for the objects he's adding to the list.

> I tried to make the user as unaware of the list internals as possible. I
> did this by only exposing opaque pointers in the public header file and
> forcing the user to use the public interface functions.

> I'm especially interested in what y'all think of the iterator, as this
> is the first one I've ever written.

Function listAdd() always appends to the end of the list.  It would be
useful to allow the user to insert at an arbitrary point in the list.

It would be useful to have a remove function that deletes at a
particular point in the list.  Function listRemove() has to search the
list for the item.  Furthermore, if an item is inserted more than one
place in the list, listRemove() can only remove the first instance in
the list.

If you have a doubly-linked list, how about providing a function to
access the prior item in the list?

Thad
--



Wed, 18 Feb 2004 23:35:28 GMT  
Kalle Olavi Niemital
#6 / 10
 My new linked list: request for comment please
[followups restricted]


Quote:
> ListIter listIter( List list )
> {
>  return &list->head;
> }
[...]
> void listIterNext( ListIter iter )
> {
>  *iter = (*iter)->next;
> }

So, if I do

  ListIter iter = listIter(list);
  listIterNext(iter);

then that has the same effect as

  list->head = list->head->next;

i.e., it drops the first node of the list and leaks its memory?
I don't think iterating through a list should automatically
modify it.

Also, this scheme does not allow multiple independent iterators
on the same list.  I might want to do:

  /* assuming a list that is large enough */
  ListIter i = listIter(list);
  ListIter j = listIter(list);
  assert(listIterData(i) == listIterData(j); /* both point to 1st node */
  listIterNext(i);
  assert(listIterData(i) != listIterData(j); /* i points to 2nd node */
  listIterNext(j);
  assert(listIterData(i) == listIterData(j); /* both point to 2nd node */

(More likely, i and j would be in nested loops.)

For that to work, you must give each iterator a separate pointer
that listIterNext() updates.  Because the caller is already
creating objects of type ListIter, the easiest way is to make
ListIter that pointer and pass its address to listIterNext:

  ListIter listIter(List);
  void listIterNext(ListIter *);

  ListIter iter = listIter(list);
  listIterNext(&iter);

If you really want ListIterNext() to take a ListIter and not the
address of one, you could make ListIter point to the actual
pointer that is then updated -- like you already do.  But
listIter() would have to allocate the pointers, perhaps with
malloc(), and you'd need another function for deleting iterators.

Finally, a few style issues.

I feel your indentations too narrow to read: I can't easily see
which braces match.  Perhaps I have too small a font.

Quote:
> int main( int argc, char* argv[] )

main can be defined with a void parameter list, and I think it
would be clearer here since you don't use the parameters anyway.

Quote:
>  iter = listIter( list );

>  while ( *iter )
>  {
>   fprintf( stderr, "%s\n", (char*) listIterData( iter ));
>   listIterNext( iter );
>  }

I would like to see this as a "for" loop:

  for (iter = listIter(list); *iter; listIterNext(iter))
    ...

A few weeks ago, I found several bugs where loop counters were
not updated at all.  With "for" loops, such mistakes would have
been more difficult to make.  Of course, there you can instead
put the expressions in the wrong order.  ;-)  I did that once and
stared at the disassembly for quite a while.
--



Wed, 18 Feb 2004 23:35:30 GMT  
Brian Raite
#7 / 10
 My new linked list: request for comment please

Quote:
> typedef struct _ListRec* List;
> typedef struct _ListNodeRec** ListIter;

Minor point: _ListRec and _ListNodeRec are in the "reserved"
namespace, as they begin with an underscore followed by a capital
letter or a second underscore. This means that they could conflict
with, say, a predefined macro, or "hidden" symbol used in one of the
standard headers.

Symbols starting with an underscore followed by a lowercase letter,
are, I believe, guaranteed to be unused by implementations.

b
--



Thu, 19 Feb 2004 23:35:35 GMT  
james C. Georga
#8 / 10
 My new linked list: request for comment please

Quote:


> > Here's an implementation of a linked list I did today. Comments and
> > suggestions would be great.

> > The list holds pointers to unspecified types ( void* ), and the user of
> > the list is wholly responsible for the objects he's adding to the list.

> > I tried to make the user as unaware of the list internals as possible. I
> > did this by only exposing opaque pointers in the public header file and
> > forcing the user to use the public interface functions.

> > I'm especially interested in what y'all think of the iterator, as this
> > is the first one I've ever written.

> Function listAdd() always appends to the end of the list.  It would be
> useful to allow the user to insert at an arbitrary point in the list.

> It would be useful to have a remove function that deletes at a
> particular point in the list.  Function listRemove() has to search the
> list for the item.  Furthermore, if an item is inserted more than one
> place in the list, listRemove() can only remove the first instance in
> the list.

Yes, absolutely. Thank you. One more vote for tying listRemove() to the
iterator, instead of the data. see my reply to Kalle for more on this.

Quote:

> If you have a doubly-linked list, how about providing a function to
> access the prior item in the list?

I thought of doubly linking it, but I wanted to keep it as simple as possible
for the post.

Quote:

> Thad
> --


--



Thu, 19 Feb 2004 23:35:46 GMT  
james C. Georga
#9 / 10
 My new linked list: request for comment please

Quote:

> > typedef struct _ListRec* List;
> > typedef struct _ListNodeRec** ListIter;

> Minor point: _ListRec and _ListNodeRec are in the "reserved"
> namespace, as they begin with an underscore followed by a capital
> letter or a second underscore. This means that they could conflict
> with, say, a predefined macro, or "hidden" symbol used in one of the
> standard headers.

> Symbols starting with an underscore followed by a lowercase letter,
> are, I believe, guaranteed to be unused by implementations.

> b
> --


Thanks. Didn't know that one.
--



Fri, 20 Feb 2004 00:22:56 GMT  
David Thompso
#10 / 10
 My new linked list: request for comment please

....
Quote:
> Minor point: _ListRec and _ListNodeRec are in the "reserved"
> namespace, as they begin with an underscore followed by a capital
> letter or a second underscore. This means that they could conflict
> with, say, a predefined macro, or "hidden" symbol used in one of the
> standard headers.

> Symbols starting with an underscore followed by a lowercase letter,
> are, I believe, guaranteed to be unused by implementations.

Not entirely.  From 7.1.3:
- All identifiers that begin with an underscore and either an uppercase letter
or another
underscore are always reserved for any use.
- All identifiers that begin with an underscore are always reserved for use as
identifiers
with file scope in both the ordinary and tag name spaces.

underscore + lowercase is available for some other uses,
including all use at block scope, but not as a file-scope tag.

--
- David.Thompson 1 now at worldnet.att.net
--



Fri, 27 Feb 2004 11:08:18 GMT  
 
 Page 1 of 1
  [ 10 post ] 

 Relevant Pages 

1. My new linked list: request for comment please

2. link list of a linked list (chained links?)

3. Linked List using dynamic memory allocation (URGENT request for example)

4. linked list request

5. Incompatible NULL Assignments || Linked List inside Linked List

6. Clearing Memory || Linked List INSIDE of a Linked List

7. Freeing a Linked List inside of a Linked List

8. Linked List of Linked Lists

9. Define a linked list of a linked list

10. Link List to Link List, HELP friends

11. why malloc for a new node in linked list

12. help for a new program on linked lists

  

 
Powered by phpBB® Forum Software