Programming Forums > Application Development > C

Jessehk · Jul 20th, 2006, 12:05 AM

As a beginner, I thought it would be neat to see if I could create some somewhat reusable linked list code. You'll need rake ( http://docs.rubyrake.org/ ) to build it, and I have included some API docs using doxygen.

This was mostly for fun, so I haven't done any real testing. However, of the tests I have run, valgrind reports 0 memory leaks and 0 errors.

I am posting this to get some feedback on my coding style, and maybe learn of some best practises in C I don't yet know. I would appreciate any advice you could provide, though I'm not expecting anybody to take this too seriously.

Make changes to main.c and simply run rake to alter the program.

On a side note, how would I make this code easily include-able in other programs? I realize that my int-dependant version is not that useful, but I would like to know for future application.

Regardless, thanks for looking.

Narue · Jul 20th, 2006, 10:44 AM

At a glance, it looks pretty good. However, there are a few points that I would like to make.

1) At a minor space cost in the list object, you can save the length of the list and not have to recalculate it. That turns list_length from an O(n) operation to an O(1) operation.

2) Operations that are strictly owned by the library (eg. the new_node function) should be static so that they're only visible to the library.

3) Libraries should be minimal and extensible. That means that you think really hard about your design so that you can give people the smallest possible library that's safe, and then let them extend it for things that aren't absolutely required in the base library. A good example is C++'s iterators. If you provide something like that as a framework, you can make a separate algorithms library that holds a lot of the functionality that you're hardcoding now. That promotes reuse and makes your maintenance job easier. The downside is that you have to work harder on the design.

Something like this might be interesting:

(Toggle Plain Text)

#include <stdlib.h>

typedef struct jsw_node *jsw_list_iterator;

// Private helpers for the library
static void *move_next ( void *obj );
static void *get_data ( void *obj );
static void *set_data ( void *obj, void *data );
static void *add_node ( void *obj, void *data );
static struct jsw_node *new_node ( void *init_data, struct jsw_node *init_next );

struct jsw_node {
  void            *_data;
  struct jsw_node *_next;

  // Forward iterator behaviors
  void *(*next) ( void *obj );
  void *(*data) ( void *obj );
  void *(*set) ( void *obj, void *data );
  void *(*add) ( void *obj, void *data );
};

struct jsw_list {
  struct jsw_node *head;
};

static void *move_next ( void *obj )
{
  return ((struct jsw_node *)obj)->_next;
}

static void *get_data ( void *obj )
{
  return ((struct jsw_node *)obj)->_data;
}

static void *set_data ( void *obj, void *data )
{
  struct jsw_node *node = obj;
  void *old_data = node->_data;

  node->_data = data;

  return old_data;
}

static void *add_node ( void *obj, void *data )
{
  struct jsw_node *node = obj;
  struct jsw_node *nn = new_node ( data, node->_next );

  node->_next = nn;

  return nn;
}

static struct jsw_node *new_node ( void *init_data, struct jsw_node *init_next )
{
  struct jsw_node *node = malloc ( sizeof *node );

  if ( node == NULL )
    return NULL;

  node->_data = init_data;
  node->_next = init_next;
  node->next = move_next;
  node->data = get_data;
  node->set = set_data;
  node->add = add_node;

  return node;
}

struct jsw_list *new_list ( void )
{
  struct jsw_list *list = malloc ( sizeof *list );

  if ( list == NULL )
    return NULL;

  list->head = new_node ( NULL, NULL );

  if ( list->head == NULL ) {
    free ( list );
    return NULL;
  }

  return list;
}

jsw_list_iterator jsw_list_begin ( struct jsw_list *list )
{
  // Before the first real node
  return list->head;
}

jsw_list_iterator jsw_list_end ( struct jsw_list *list )
{
  // After the last real node
  return NULL;
}


// Quickie test, no cleanup done
#include <stdio.h>

void *make_data ( int x )
{
  int *new_data = malloc ( sizeof *new_data );

  *new_data = x;

  return new_data;
}

int main ( void )
{
  struct jsw_list *list = new_list();

  if ( list != NULL ) {
    jsw_list_iterator it = jsw_list_begin ( list );
    jsw_list_iterator end;
    int i;

    for ( i = 1; i < 7; i++ )
      it = it->add ( it, make_data ( i ) );

    it = jsw_list_begin ( list );
    end = jsw_list_end ( list );

    while ( ( it = it->next ( it ) ) != end )
      printf ( "%d ", *(int *)it->data ( it ) );

    printf ( "\n" );
  }

  return 0;
}

#include <stdlib.h>

typedef struct jsw_node *jsw_list_iterator;

// Private helpers for the library
static void *move_next ( void *obj );
static void *get_data ( void *obj );
static void *set_data ( void *obj, void *data );
static void *add_node ( void *obj, void *data );
static struct jsw_node *new_node ( void *init_data, struct jsw_node *init_next );

struct jsw_node {
  void            *_data;
  struct jsw_node *_next;

  // Forward iterator behaviors
  void *(*next) ( void *obj );
  void *(*data) ( void *obj );
  void *(*set) ( void *obj, void *data );
  void *(*add) ( void *obj, void *data );
};

struct jsw_list {
  struct jsw_node *head;
};

static void *move_next ( void *obj )
{
  return ((struct jsw_node *)obj)->_next;
}

static void *get_data ( void *obj )
{
  return ((struct jsw_node *)obj)->_data;
}

static void *set_data ( void *obj, void *data )
{
  struct jsw_node *node = obj;
  void *old_data = node->_data;

  node->_data = data;

  return old_data;
}

static void *add_node ( void *obj, void *data )
{
  struct jsw_node *node = obj;
  struct jsw_node *nn = new_node ( data, node->_next );

  node->_next = nn;

  return nn;
}

static struct jsw_node *new_node ( void *init_data, struct jsw_node *init_next )
{
  struct jsw_node *node = malloc ( sizeof *node );

  if ( node == NULL )
    return NULL;

  node->_data = init_data;
  node->_next = init_next;
  node->next = move_next;
  node->data = get_data;
  node->set = set_data;
  node->add = add_node;

  return node;
}

struct jsw_list *new_list ( void )
{
  struct jsw_list *list = malloc ( sizeof *list );

  if ( list == NULL )
    return NULL;

  list->head = new_node ( NULL, NULL );

  if ( list->head == NULL ) {
    free ( list );
    return NULL;
  }

  return list;
}

jsw_list_iterator jsw_list_begin ( struct jsw_list *list )
{
  // Before the first real node
  return list->head;
}

jsw_list_iterator jsw_list_end ( struct jsw_list *list )
{
  // After the last real node
  return NULL;
}


// Quickie test, no cleanup done
#include <stdio.h>

void *make_data ( int x )
{
  int *new_data = malloc ( sizeof *new_data );

  *new_data = x;

  return new_data;
}

int main ( void )
{
  struct jsw_list *list = new_list();

  if ( list != NULL ) {
    jsw_list_iterator it = jsw_list_begin ( list );
    jsw_list_iterator end;
    int i;

    for ( i = 1; i < 7; i++ )
      it = it->add ( it, make_data ( i ) );

    it = jsw_list_begin ( list );
    end = jsw_list_end ( list );

    while ( ( it = it->next ( it ) ) != end )
      printf ( "%d ", *(int *)it->data ( it ) );

    printf ( "\n" );
  }

  return 0;
}

Sorry for taking so long, I kept getting pulled away. :p

Jessehk · Jul 20th, 2006, 11:01 AM

Thanks Narue. Helpful as usual.

A few things I'll be doing in the future:

prefix with something like jhk_<function> to avoid naming clashes.
prefix important struct fields with underscores.
study that code untill I fully understand it :p

Thanks again

EDIT: There's a new forum highlighting tag. use [ highlight=c ] and [ /highlight ] which uses syntax highlighting.

Narue · Jul 20th, 2006, 11:09 AM

>prefix with something like jhk_<function> to avoid naming clashes.
Always a good idea in the absence of namespaces.

>prefix important struct fields with underscores.
Be wary of leading underscores. There are times when they're reserved.

>use [ highlight=c ] and [ /highlight ] which uses syntax highlighting.
Not until it preserves my precise formatting.

The Dark · Jul 20th, 2006, 8:33 PM

I've only looked at the linked.c so far, but the first function caught my eye:

(Toggle Plain Text)

int one_node(const struct LinkedList *list) {
    return list->first->next == NULL;
}

Its looks like list->first can be NULL for an empty list, so this would cause a NULL pointer dereference when called with an empty list.

You should also put some sort of error checking on your calls to malloc.

In new_linked_list, you don't need all the if tests, just push nodes for whatever ints are passed in

In delete_linked_list, again all 3 paths through the code end up doing the same thing, so you don't need the special cases for 0 and 1 nodes. Also delete_linked_list should set the first pointer to NULL, so you can reuse the list straight away.

Actually the same goes for a lot (but not all) of the tests for one_node and empty lists.

Similarly to Narue's point, having a "last" or "tail" pointer as well as a "first" pointer in your linked list will make operations like last_node (and hence push_node and everything that use that) a lot faster. It does lead to more housekeeping by your library functions, however.

Jessehk · Jul 20th, 2006, 8:59 PM

Thanks, The Dark.

I didn't catch a lot of those. :o

Jul 20th, 2006, 10:44 AM	#2
Narue Professional Programmer Join Date: Sep 2005 Posts: 419 Rep Power: 4	At a glance, it looks pretty good. However, there are a few points that I would like to make. 1) At a minor space cost in the list object, you can save the length of the list and not have to recalculate it. That turns list_length from an O(n) operation to an O(1) operation. 2) Operations that are strictly owned by the library (eg. the new_node function) should be static so that they're only visible to the library. 3) Libraries should be minimal and extensible. That means that you think really hard about your design so that you can give people the smallest possible library that's safe, and then let them extend it for things that aren't absolutely required in the base library. A good example is C++'s iterators. If you provide something like that as a framework, you can make a separate algorithms library that holds a lot of the functionality that you're hardcoding now. That promotes reuse and makes your maintenance job easier. The downside is that you have to work harder on the design. Something like this might be interesting: (Toggle Plain Text) #include <stdlib.h> typedef struct jsw_node jsw_list_iterator; // Private helpers for the library static void move_next ( void obj ); static void get_data ( void obj ); static void set_data ( void obj, void data ); static void add_node ( void obj, void data ); static struct jsw_node new_node ( void init_data, struct jsw_node init_next ); struct jsw_node { void _data; struct jsw_node _next; // Forward iterator behaviors void (next) ( void obj ); void (data) ( void obj ); void (set) ( void obj, void data ); void (add) ( void obj, void data ); }; struct jsw_list { struct jsw_node head; }; static void move_next ( void obj ) { return ((struct jsw_node )obj)->_next; } static void get_data ( void obj ) { return ((struct jsw_node )obj)->_data; } static void set_data ( void obj, void data ) { struct jsw_node node = obj; void old_data = node->_data; node->_data = data; return old_data; } static void add_node ( void obj, void data ) { struct jsw_node node = obj; struct jsw_node nn = new_node ( data, node->_next ); node->_next = nn; return nn; } static struct jsw_node new_node ( void init_data, struct jsw_node init_next ) { struct jsw_node node = malloc ( sizeof node ); if ( node == NULL ) return NULL; node->_data = init_data; node->_next = init_next; node->next = move_next; node->data = get_data; node->set = set_data; node->add = add_node; return node; } struct jsw_list new_list ( void ) { struct jsw_list list = malloc ( sizeof list ); if ( list == NULL ) return NULL; list->head = new_node ( NULL, NULL ); if ( list->head == NULL ) { free ( list ); return NULL; } return list; } jsw_list_iterator jsw_list_begin ( struct jsw_list list ) { // Before the first real node return list->head; } jsw_list_iterator jsw_list_end ( struct jsw_list list ) { // After the last real node return NULL; } // Quickie test, no cleanup done #include <stdio.h> void make_data ( int x ) { int new_data = malloc ( sizeof new_data ); new_data = x; return new_data; } int main ( void ) { struct jsw_list list = new_list(); if ( list != NULL ) { jsw_list_iterator it = jsw_list_begin ( list ); jsw_list_iterator end; int i; for ( i = 1; i < 7; i++ ) it = it->add ( it, make_data ( i ) ); it = jsw_list_begin ( list ); end = jsw_list_end ( list ); while ( ( it = it->next ( it ) ) != end ) printf ( "%d ", (int )it->data ( it ) ); printf ( "\n" ); } return 0; } #include <stdlib.h> typedef struct jsw_node jsw_list_iterator; // Private helpers for the library static void move_next ( void obj ); static void get_data ( void obj ); static void set_data ( void obj, void data ); static void add_node ( void obj, void data ); static struct jsw_node new_node ( void init_data, struct jsw_node init_next ); struct jsw_node { void _data; struct jsw_node _next; // Forward iterator behaviors void (next) ( void obj ); void (data) ( void obj ); void (set) ( void obj, void data ); void (add) ( void obj, void data ); }; struct jsw_list { struct jsw_node head; }; static void move_next ( void obj ) { return ((struct jsw_node )obj)->_next; } static void get_data ( void obj ) { return ((struct jsw_node )obj)->_data; } static void set_data ( void obj, void data ) { struct jsw_node node = obj; void old_data = node->_data; node->_data = data; return old_data; } static void add_node ( void obj, void data ) { struct jsw_node node = obj; struct jsw_node nn = new_node ( data, node->_next ); node->_next = nn; return nn; } static struct jsw_node new_node ( void init_data, struct jsw_node init_next ) { struct jsw_node node = malloc ( sizeof node ); if ( node == NULL ) return NULL; node->_data = init_data; node->_next = init_next; node->next = move_next; node->data = get_data; node->set = set_data; node->add = add_node; return node; } struct jsw_list new_list ( void ) { struct jsw_list list = malloc ( sizeof list ); if ( list == NULL ) return NULL; list->head = new_node ( NULL, NULL ); if ( list->head == NULL ) { free ( list ); return NULL; } return list; } jsw_list_iterator jsw_list_begin ( struct jsw_list list ) { // Before the first real node return list->head; } jsw_list_iterator jsw_list_end ( struct jsw_list list ) { // After the last real node return NULL; } // Quickie test, no cleanup done #include <stdio.h> void make_data ( int x ) { int new_data = malloc ( sizeof new_data ); new_data = x; return new_data; } int main ( void ) { struct jsw_list list = new_list(); if ( list != NULL ) { jsw_list_iterator it = jsw_list_begin ( list ); jsw_list_iterator end; int i; for ( i = 1; i < 7; i++ ) it = it->add ( it, make_data ( i ) ); it = jsw_list_begin ( list ); end = jsw_list_end ( list ); while ( ( it = it->next ( it ) ) != end ) printf ( "%d ", (int )it->data ( it ) ); printf ( "\n" ); } return 0; } Sorry for taking so long, I kept getting pulled away. :p __________________ Even if the voices aren't real, they have some pretty good ideas. Last edited by Narue; Jul 20th, 2006 at 11:10 AM.

Jul 20th, 2006, 11:01 AM	#3
Jessehk The Oblivious One Join Date: May 2005 Location: Ontario, Canada Posts: 648 Rep Power: 4	Thanks Narue. Helpful as usual. A few things I'll be doing in the future: prefix with something like jhk_<function> to avoid naming clashes. prefix important struct fields with underscores. study that code untill I fully understand it :p Thanks again EDIT: There's a new forum highlighting tag. use [ highlight=c ] and [ /highlight ] which uses syntax highlighting. __________________ Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

Jul 20th, 2006, 11:09 AM	#4
Narue Professional Programmer Join Date: Sep 2005 Posts: 419 Rep Power: 4	>prefix with something like jhk_<function> to avoid naming clashes. Always a good idea in the absence of namespaces. >prefix important struct fields with underscores. Be wary of leading underscores. There are times when they're reserved. >use [ highlight=c ] and [ /highlight ] which uses syntax highlighting. Not until it preserves my precise formatting. __________________ Even if the voices aren't real, they have some pretty good ideas.

Jul 20th, 2006, 8:33 PM	#5
The Dark Expert Programmer Join Date: Jun 2005 Posts: 894 Rep Power: 4	I've only looked at the linked.c so far, but the first function caught my eye: (Toggle Plain Text) int one_node(const struct LinkedList list) { return list->first->next == NULL; } int one_node(const struct LinkedList list) { return list->first->next == NULL; } Its looks like list->first can be NULL for an empty list, so this would cause a NULL pointer dereference when called with an empty list. You should also put some sort of error checking on your calls to malloc. In new_linked_list, you don't need all the if tests, just push nodes for whatever ints are passed in In delete_linked_list, again all 3 paths through the code end up doing the same thing, so you don't need the special cases for 0 and 1 nodes. Also delete_linked_list should set the first pointer to NULL, so you can reuse the list straight away. Actually the same goes for a lot (but not all) of the tests for one_node and empty lists. Similarly to Narue's point, having a "last" or "tail" pointer as well as a "first" pointer in your linked list will make operations like last_node (and hence push_node and everything that use that) a lot faster. It does lead to more housekeeping by your library functions, however.

Jul 20th, 2006, 8:59 PM	#6
Jessehk The Oblivious One Join Date: May 2005 Location: Ontario, Canada Posts: 648 Rep Power: 4	Thanks, The Dark. I didn't catch a lot of those. :o __________________ Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
dev c++ software, template problem	cairo	C++	11	Jun 2nd, 2006 1:42 PM
Singly Linked List Help	Firebar	Java	3	May 22nd, 2005 11:56 AM
User-defined creatNode and deleteNode functions for a doubly-linked list	jgs	C	2	Apr 28th, 2005 9:53 AM
Linked List Part 2	Nish	C++	0	Mar 4th, 2005 4:56 PM
airport Log program using 3D linked List : problem reading from file	gemini_shooter	C++	0	Mar 2nd, 2005 5:12 PM

Programming Forums > Application Development > C

Appreciate comments on some linked list code