generic linklist

[aditya]

how do we implement a generic linklist?

 

[maverik]

how do we implement a generic linklist?

1.
http://www.google.com/search?q=<you_question_goes_here>

It's not a C related question. Try to do anything by yourself. And if
you have a question about C language then just ask us.

2.
Just a hint.
There are many different ways to implement linked list.
One way to do this is:

struct node {
struct node *next;
int node_data;
};

Or

struct node {
struct node *next;
struct node *prev;
int node_data;
};

 

[Eric Sosman]

how do we implement a generic linklist?

What do we mean by "generic?"

 

[Chris Dollin]

how do we implement a generic linklist?

Implement a specific linklist and then abstract.

 

[John Bode]

how do we implement a generic linklist?

You mean a list that can handle generic data? It's a bit of work, but
you can create a list structure that's type-agnostic by using void
pointers for the list node data and by associating type-aware
functions (for comparison, allocation, and deallocation) via function
pointers.

(no warranties express or implied in the following code -- I'm tossing
this off the top of my head and there are bound to be mistakes, but
hopefully the concept makes sense)

Start with the list node itself:

struct glnode {
void *data;
struct glnode *next;
};

Now we create a list type that allows us to associate type-aware
functions with the list:

struct glist {
struct glnode head;
int (*cmp) (const void *lhs, const void *rhs); /* comparison
function */
void *(*cpy) (const void *data); /* copies data
items */
void (*del) (const void *data); /* deletes data
items */
};

The cmp, cpy, and del function pointers will be used to associate type-
aware functions with the list. For example, the cmp function compares
two data items and returns a value that's less than 0 if lhs < rhs, 0
if lhs == rhs, or >0 if lhs > rhs. If we're storing strings as data,
then our cmp function looks something like this:

int cmpStrings (const void *lhs, const void *rhs)
{
const char *lstr = lhs;
const char *rstr = rhs;

return strcmp(lstr, rstr);
}

Since we're using pointers as our data types, we will need functions
to allocate and deallocate memory. The cpy function will be used to
allocate memory for and copy data to the data item. Again, if we're
storing string data, it would look something like

void *cpyString (const void *data)
{
const char *dataStr = data;
char *copy = malloc(strlen (dataStr) + 1);
if (copy)
{
strcpy(copy, dataStr);
}
return copy;
}

And, similarly, when we remove an object from the list, we will want
to release the memory for it:

void delString (const void *data)
{
/* no need to convert argument in this case */
free(data);
}

So, when we create our list, we can associate these functions with it
to manage string data:

struct glist strlist;

strlist.cmp = cmpStrings;
strlist.cpy = cpyString;
strlist.del = delString;

Although we'd probably want to write a function to handle creating and
initializing the list:

struct glist *newList(int (*cmp)(const void *, const void *),
void *(*cpy)(const void *),
void (*del)(const void *))
{
struct glist *theList = malloc (sizeof *theList);
if (theList)
{
theList->cmp = cmp;
theList->cpy = cpy;
theList->del = del;
theList->head.next = NULL;
}

return theList;
}

When you write your add, find, and delete functions, you'd use the
function pointers in the list type like so:

void addData(struct glist *theList, const void *data)
{
if (theList->head.next == NULL)
{
theList->head.next = malloc(sizeof *theList->head.next);
if (theList->head.next)
{
theList->head.next->data = theList->cpy(data);
}
}
else
{
struct glnode *cur = theList->head.next, *new;
while (cur->next != NULL && theList->cmp(data, cur->next-

data) <= 0)

cur = cur->next;
new = malloc(sizeof *new);
if (new)
{
new->data = theList->cpy(data);
new->next = cur->next;
cur->next = new;
}
}
}

Hopefully you get the idea. With this kind of a setup you can use the
same list type with different types of data; you just associate
different data-aware functions with the list:

struct glist *intList = newList(cmpInts, cpyInt, delInt);
int intData;
....
intData = ...;
addData(intList, &intData);
....

struct glist *doubleList = newList(cmpDoubles, cpyDouble, delDouble);
double doubleData;
....
doubleData = ...;
addData(doubleList, &doubleData);

struct glist *adtList = newList(cmpAdt, cpyAdt, delAdt);
struct adt adtData;
adtData.foo = ...;
adtData.bar = ...;
addData(adtList, &adtData);

etc., etc., etc.

 

[Phil Carmody]

Implement a specific linklist and then abstract.

Post of the week.

Phil

 

[CBFalconer]

how do we implement a generic linklist?

typedef struct listitem {
struct listitem *next;
void *data;
} listitem;

listitem *root = NULL;

Now you can use this in many lists. The difference in the lists
will be in the type of data pointer, and wherever used you need
something like:

T operateon(void *datum) {
DT data = datum;

/* do games with datum */
return whatever; /* which is type T */
}

Here is something I have used for some time:

/* List handling, reversal, sort, merge, split */
/* file listops.h */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */

#ifndef listops_h_
#define listops_h_

#include <stddef.h> /* NULL */
#include <iso646.h> /* not, and */

/* The bare minimum to form a linked list */
typedef struct node {
struct node *next;
void *data;
} node, *nodeptr;

/* ======================================================= */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root);

/* ======================================================= */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p);

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)); /* compare */

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)); /* compare */

#endif
/* end listops.h */

/* List handling, reversal, sort, merge, split */
/* file listops.c */
/* By C.B. Falconer. Public Domain, use as you wish */
/* Attribution appreciated. */
/* ================== 30 April, 2001 ================== */
/* using stdops.h, 16 Sept. 2001 */

#include "stdops.h" /* bool, true, false, not, and, or, xor */
#include "listops.h"

/* ======================================================= */
/* believed necessary and sufficient for NULL terminations */
/* Reverse a singly linked list. Reentrant (pure) code */
nodeptr revlist(nodeptr root)
{
nodeptr curr, nxt;

if (root) { /* non-empty list */
curr = root->next;
root->next = NULL; /* terminate new list */
while (curr) {
nxt = curr->next; /* save for walk */
curr->next = root; /* relink */
root = curr; /* save for next relink */
curr = nxt; /* walk onward */
}
}
/* else empty list is its own reverse; */
return root;
} /* revlist */

/* ======================================================= */
/* split list p into 2 nearly equal lists, return 2nd part */
nodeptr splitlist(nodeptr p)
{
nodeptr p1, p2, p3;

p1 = p2 = p3 = p;
if (not p) return NULL;
do {
p3 = p2;
p2 = p2->next; /* advance 1 */
p1 = p1->next;
if (p1) p1 = p1->next; /* advance 2 */
} while (p1);

/* now form new list after p2 */
p3->next = NULL; /* terminate 1st half */
return p2;
} /* splitlist */

/* ================================ */
/* Merge two ordered lists into one */
nodeptr mergelists(nodeptr p1, nodeptr p2,
int (*cmp)(void *, void*)) /* compare */
{
node n;
nodeptr p;

p = &n;
n.next = p;

while (p1 and p2) {
if (cmp(p1, p2) <= 0) {
p->next = p1; p = p1; p1 = p1->next;
}
else {
p->next = p2; p = p2; p2 = p2->next;
}
}
/* at least one list now empty, copy other */
/* one or both of these operations is null */
if (p1) p->next = p1;
if (p2) p->next = p2;

/* check for empty lists */
if (n.next == &n) return NULL;
return n.next;
} /* mergelists */

/* ================================================== */
/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
nodeptr mergesort(nodeptr root,
int (*cmp)(void *, void*)) /* compare */
{
nodeptr p;

if (root and root->next) { /* 2 up items in list */
p = splitlist(root); /* alters list root */
root = mergelists(mergesort(root, cmp),
mergesort( p, cmp),
cmp);
}
/* else the unit or empty list is already sorted */

return root;
} /* mergesort */

/* end listops.c */

 

[Chris M. Thomasson]

how do we implement a generic linklist?

http://isis.poly.edu/kulesh/stuff/src/klist

 

[xyzzybill]

how do we implement a generic linklist?

It's a good question. C doesn't support generic code, so you have to
make up something yourself. Even C++ originally couldn't do it, so
they added "templates" to the language.

Personally, I feel the C++ template based code sucks. All you want to
do is add a next pointer and possibly a parent pointer to the child
class, and a first pointer in the parent class. Templates only affect
the parent class, so they are incapable of embedding a next pointer
the we do in C. I got so fed up writing the same generic code over
and over in C that I wrote DataDraw (http://datadraw.sourceforge.net).

So, how do you write generic linked lists in C? My answer is code
generators.

 

[Chris M. Thomasson]

Chris M. Thomasson said:


That wasn't very kind.

Well, the overall method is a fairly good one; IMVHO at least... Humm,
efficient intrusive containers have their place indeed.

What has the OP ever done to you?

=^)

 

[Richard]

typedef struct listitem {
struct listitem *next;
void *data;
} listitem;

listitem *root = NULL;

It's funny how you dont tell them to do their own homework when you
actually have a solution.

 

[CBFalconer]

It's funny how you dont tell them to do their own homework when
you actually have a solution.

Now just think about it. Is that a question that would be asked by
a newbie learning the language.

Incidentally, don't is spelled with an apostrophe. It means "do
not". Just to keep up the foolish criticisms.

 

[gw7rib]

how do we implement a generic linklist?

Several people have suggested code in which a node contains a void
pointer, which points to the actual data, but it is possible to do
things differently. This is from a program I wrote a number of years
ago - I've trimmed it down a bit.

Firstly, you include in the struct a pointer to the next one and the
previous one, eg:

struct appoint {
char day;
char mon;
int year;
char text[49];
struct appoint *next;
struct appoint *prior;
} ;

struct address {
char title[8];
char firstname[12];
char surname[20];
struct address *next;
struct address *prior;
} ;

Now, you need functions to get at these pointers. For example:

typedef void * Pointer;

Pointer *pnext(int type, Pointer thing) {
switch (type) {
case ADDRESS: return (Pointer *)
&(((struct address *) thing) -> next);
case APPOINT: return (Pointer *)
&(((struct appoint *) thing) -> next); }
return NULL; }

and a similar one for pprior. You can then write generic function such
as:

void linkin(int type, Pointer thing, Pointer before, Pointer after,
Pointer *first, Pointer *last) {
*pnext(type, thing) = after;
*pprior(type, thing) = before;
if (before) *pnext(type, before) = thing;
else *first = thing;
if (after) *pprior(type, after) = thing;
else *last = thing;
}

You may also want to wruite function that will give you pointers to
the places where the first and last elements of each list are stored.
This would allow you to do things like:

void slinkin(int type, Pointer thing) {
Pointer *pfirst, *plast;

fromtype(type, &pfirst, &plast);
linkin(type, thing, *plast, NULL, pfirst, plast);
}

which will add thing at the end of the appropriate list.

Hope this is helpful.
Paul.

 

[Barry Schwarz]

how do we implement a generic linklist?

Several people have suggested code in which a node contains a void
pointer, which points to the actual data, but it is possible to do
things differently. This is from a program I wrote a number of years
ago - I've trimmed it down a bit.

Firstly, you include in the struct a pointer to the next one and the
previous one, eg:

struct appoint {
char day;
char mon;
int year;
char text[49];
struct appoint *next;
struct appoint *prior;
} ;

struct address {
char title[8];
char firstname[12];
char surname[20];
struct address *next;
struct address *prior;
} ;

Now, you need functions to get at these pointers. For example:

typedef void * Pointer;

I think camouflaging a pointer type this way has created just enough
mental confusion to render your example useless.

Pointer *pnext(int type, Pointer thing) {

Surely you don't mean to return a void**.

switch (type) {
case ADDRESS: return (Pointer *)
&(((struct address *) thing) -> next);

Is the address of next really properly aligned for a void**. If not,
this invokes undefined behavior.

case APPOINT: return (Pointer *)
&(((struct appoint *) thing) -> next); }
return NULL; }

and a similar one for pprior. You can then write generic function such
as:

void linkin(int type, Pointer thing, Pointer before, Pointer after,
Pointer *first, Pointer *last) {
*pnext(type, thing) = after;

If pnext() really returns a void**, the *pnext() evaluates to a void*.
Since the member next (in either struct) is not a void*, this risks
several undesirable results. If void* and pointer to struct have
different sizes, then you either overrun the member or leave residual
data in the member. If they don't have the same representation, the
resulting value could be a trap.

 

[gw7rib]

Surely you don't mean to return a void**.

Ah. I wrote this when I was fairly new to C (I'd previously used BCPL,
which doesn't have this sort of type issues) and, now you come to
mention it, there could well be problems. void ** has the right level
of indirection (I want to find where the next pointer is stored, so
that I can make it point to a different next element) but as you say,
it is not the right type for pointing at something which isn't
actually a void *. I was using a PC under DOS, so I think it would
work on my system, but obviously not in general. Apologies for the
misleadment.

Paul.

 

[Chris M. Thomasson]

how do we implement a generic linklist?

Sorry for the length. Here's a quick example of a doubly-linked list. It's
circular to eliminate special-cases.

#include <assert.h>
#include <stdio.h>

/* Circular doubly-linked list */

typedef struct Node Node;

struct Node
{
Node* next;
Node* prev;
};

[...]

/* Example using list */
typedef struct Foo Foo;

struct Foo
{
Node node; /* must be first */

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This requirement can easily be removed by using the `offsetof' function
macro...

const char* str;
};

static void print_list( Foo* list )
{
[...]
}

int main()
{
[...]
}

 

[Ben Pfaff]

It's a strange way to implement a list.
The nodes of the list are of type (struct Foo),
and the list doesn't contain any pointers to that type.

It's a very common way to implement a generic linked list in C,
in my experience. Every Unix-like kernel whose source I have
read contains a generic linked list of this sort. I suspect that
even some Windows kernels use one, based on reverse-engineering I
did of Windows at runtime some years ago.

 

[Ben Pfaff]

Do you think it's a good way to implement a list in C?

It depends. Sometimes it's much easier to implement a linked
list in C without a generic linked list package. For singly
linked lists, I've never seen a generic linked list package in C
that I liked. I think that this is because their limitations are
too hard to abstract away into something sensible, and because
singly linked lists are so simple that it's much easier to just
do it again. My fingers can type out correct singly linked list
code without my brain ever engaging.

But personally I find doubly linked lists slightly more
challenging. Really simple stuff like adding and removing
elements isn't too hard, and I can often get it right the first
time, but for me the really nice part of having a generic library
is that you can use more powerful routines, like the ones below,
without having to write them all over again:

/* Removes R0...R1 from their current list
and inserts them just before BEFORE. */
void
ll_splice (struct ll *before, struct ll *r0, struct ll *r1)
{
if (before != r0 && r0 != r1)
{
/* Change exclusive range to inclusive. */
r1 = ll_prev (r1);

/* Remove R0...R1 from its list. */
r0->prev->next = r1->next;
r1->next->prev = r0->prev;

/* Insert R0...R1 before BEFORE. */
r0->prev = before->prev;
r1->next = before;
before->prev->next = r0;
before->prev = r1;
}
}

/* Exchanges the positions of A0...A1 and B0...B1,
which may be in the same list or different lists but must not
overlap. */
void
ll_swap_range (struct ll *a0, struct ll *a1, struct ll *b0, struct ll *b1)
{
if (a0 == a1 || a1 == b0)
ll_splice (a0, b0, b1);
else if (b0 == b1 || b1 == a0)
ll_splice (b0, a0, a1);
else
{
struct ll *x0 = ll_prev (a0), *x1 = a1;
struct ll *y0 = ll_prev (b0), *y1 = b1;
a1 = ll_prev (a1);
b1 = ll_prev (b1);
x0->next = b0;
b0->prev = x0;
b1->next = x1;
x1->prev = b1;
y0->next = a0;
a0->prev = y0;
a1->next = y1;
y1->prev = a1;
}
}

I'm also in the habit of writing very thorough unit tests for my
generic libraries (typically, I make sure that they cover every
line of code, every branch, and any corner cases I can think of).
So when I have the opportunity to use my generic libraries, I do
so. Why write more code when you can write less code and be more
certain that it will work? "Performance" is sometimes a good
answer, but I try to ignore performance issues that will only
make a constant-factor improvements and not a big-O improvement
until I can justify them with profiling. And usually I can't.

The worst part of generic linked lists in C is the need for ugly
macros that do pointer arithmetic. I don't know of a better way
to do it, though.

 

[Stephen Sprunk]

how do we implement a generic linklist?

Sorry for the length. Here's a quick example of a doubly-linked list.
It's
circular to eliminate special-cases.

#include <assert.h>
#include <stdio.h>

/* Circular doubly-linked list */

typedef struct Node Node;

struct Node
{
Node* next;
Node* prev;
};

[...]

/* Example using list */
typedef struct Foo Foo;

struct Foo
{
Node node; /* must be first */

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This requirement can easily be removed by using the `offsetof'
function macro...

It's a strange way to implement a list.
The nodes of the list are of type (struct Foo),
and the list doesn't contain any pointers to that type.

Ah, but that's the magic! You can have several different node types but
the code the manages the linked list only sees Nodes and is thus
generic; you don't need to duplicate the code for each new type. You do
have to cast the structs back and forth a bit, but that is guaranteed to
be safe (for exactly this reason) as long as the Node is the first
element in the various other struct types.

S

 

[Chris M. Thomasson]

how do we implement a generic linklist?

Sorry for the length. Here's a quick example of a doubly-linked list.
It's circular to eliminate special-cases.

#include <assert.h>
#include <stdio.h>

/* Circular doubly-linked list */

typedef struct Node Node;

struct Node
{
Node* next;
Node* prev;
};

[...]

/* Example using list */
typedef struct Foo Foo;

struct Foo
{
Node node; /* must be first */
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This requirement can easily be removed by using the `offsetof' function
macro...

Without cluttering user code up with even more complex casts?

You can wrap it up in a macro...




#define CONTAINS(mp_this, mp_struct, mp_member) ((mp_struct*)( \
((size_t)(mp_this)) - offsetof(mp_struct, mp_member) \
))


struct Foo {
/* [whatever] */

struct Node node;

/* [whatever] */
};


#define FOO_NODE(mp_this) CONTAINS(mp_this, struct Foo, node)


void foo(void) {
struct Foo f;
struct Node* const n = &f.node;
assert(FOO_NODE(n) == &f);
}




IMHO, its not all "that" bad...

;^)