|
9.2.1.3 Generalised List Data Type
In many C programs you will see various implementations and
re-implementations of lists and stacks, each tied to its own particular
project. It is surprisingly simple to write a catch-all implementation,
as I have done here with a generalised list operation API in
`list.h':
|
#ifndef SIC_LIST_H
#define SIC_LIST_H 1
#include <sic/common.h>
BEGIN_C_DECLS
typedef struct list {
struct list *next; /* chain forward pointer*/
void *userdata; /* incase you want to use raw Lists */
} List;
extern List *list_new (void *userdata);
extern List *list_cons (List *head, List *tail);
extern List *list_tail (List *head);
extern size_t list_length (List *head);
END_C_DECLS
#endif /* !SIC_LIST_H */
|
The trick is to ensure that any structures you want to chain together
have their forward pointer in the first field. Having done that, the
generic functions declared above can be used to manipulate any such
chain by casting it to List * and back again as necessary.
For example:
| struct foo {
struct foo *next;
char *bar;
struct baz *qux;
...
};
...
struct foo *foo_list = NULL;
foo_list = (struct foo *) list_cons ((List *) new_foo (),
(List *) foo_list);
...
|
The implementation of the list manipulation functions is in
`list.c':
|
#include "list.h"
List *
list_new (void *userdata)
{
List *new = XMALLOC (List, 1);
new->next = NULL;
new->userdata = userdata;
return new;
}
List *
list_cons (List *head, List *tail)
{
head->next = tail;
return head;
}
List *
list_tail (List *head)
{
return head->next;
}
size_t
list_length (List *head)
{
size_t n;
for (n = 0; head; ++n)
head = head->next;
return n;
}
|
|