Groovy hepcat JS was jivin' on Tue, 19 Apr 2005 12:15:25 +0200 in
comp.lang.c.
Add pointer to a double linked-list?'s a cool scene! Dig it!
I have a file called test.c. There I create a pointer to a pcb struct:
struct pcb {
void *(*start_routine) (void *);
void *arg;
jmp_buf state;
int stack[STACK_SIZE];
};
struct pcb *pcb_pointer;
pcb_pointer = (struct pcb *) malloc(sizeof(struct pcb));
if(pcb_pointer == NULL) {
exit(-1);
}
OK, so far so good.
add(pcb_pointer);
Now I would like to add "pcb_pointer" to a double linked-list. I have made
this double linked-list in another file called list.c where I am trying to
make the "add" function:
For a start, I wouldn't call it add(). That name is confusing. It
brings to mind the addition of two arithmetic terms. You can still use
the word "add" in your function name, but I'd clarify it by providing
more information in the function name. For example, LinkListAddNode()
or just AddNode() or something similar might be better. But that's
entirely up to you.
I would call this struct node, rather than struct list, because it
represents a single node, not a whole list.
I know someone already mentioned this, but why is this a void * when
you only want to store a struct pcb? Perhaps you want to modify the
code later to store any type of data in the node? Well, you can do
that later, when you've got the rest of the code working. For now just
stick with struct pcb *.
struct pcb *thread;
struct list *previous;
struct list *next;
};
struct list *f,*c,*n,*p,*l;
/ *f = first element, c = current element, n = next element, p = previous
element, l = last element. */
Why are all these variables defined here? Why not inside the
function? And what do you need all these for anyhow?
You should think about what you really need. Even before you create
a node to put in the list, you need the list itself. Most people
naively create a single struct node * at file scope. This is the head
node. This is not the best, in my opinion. You're locked into using
just one list. Suppose your program (or some future program that
reuses code taken from this one) needs more than one linked list: you
want to keep multiple head nodes and pass them to your linked list
handling functions. I find the best way to do this is to create
another struct type to hold the head node pointer along with any other
information that might be relevant (such as a tail node pointer, the
number of nodes currently stored in the list, etc.). For example:
struct linkedlist
{
struct node *head;
struct node *tail;
size_t numnodes;
/* Any other members you deem relevant or desirable can go here. */
};
Now that we have this type, we can create an instance of it anywhere
we like, preferably in main() or some other function where we need it.
We then need to pass to this to AddNode() (or whatever you want to
call that function). But how do we create it? Well, we could just
define it, like so:
struct linkedlist mylist = {NULL, NULL, 0};
Then we would pass it to AddNode() like so:
AddNode(&mylist ...);
That's doable. It's simple and straightforward. However, you're
probably better off making a function that dynamically allocates the
struct and initialises its members for you. So, you'd do something
like this:
struct linkedlist *mylist;
/* Create new list. */
mylist = NewList();
if(NULL == mylist)
{
/* Error: handle it somehow. */
}
....
/* Finished using the list - so free the associated memory. */
FreeList(mylist);
And, of course, you then need functions NewList() and FreeList(). They
might go something like this:
struct linkedlist *NewList(void)
{
struct linkedlist *list;
list = malloc(sizeof *list);
if(list)
{
list->head = list->tail = NULL;
list->numnodes = 0;
}
return list;
}
void FreeList(struct linkedlist *list)
{
struct node *next;
/* First, if there are any nodes left in the list, remove and free
them. */
while(list->head)
{
next = list->head->next;
FreeNode(list->head);
list->head = next;
}
/* Now free the list structure. */
free(list);
}
You'll notice that I've used a function here that we haven't defined
yet. We will in a minute. But before then we have to decide just how
we're going to store the node payloads (data) in the nodes.
We should ask ourselves several questions. First, when we pass data
to AddNode(), do we store that actual data, or do we make a
(dynamically allocated) copy of it and store *that* in our list
instead? For example, suppose we have a struct pcb object named mypcb;
do we do something like this:
node->thread = &mypcb;
(or its equivalent) or do we do it like this?
node->thread = malloc(sizeof *node->thread)
if(NULL == node->thread)
{
/* Error: handle it somehow. */
}
memcpy(node->thread, mypcb, sizeof mypcb);
For the purpose of this discussion, let's keep it simple and store the
object itself, not a copy.
I know someone already mentioned this, but another thing we need to
ask ourselves is where in the list we want to store the node: at the
start, at the end or in some kind of order. Storing a node at the
start is easiest. Storing it at the end is just as easy if we have a
tail pointer, and probably makes the most sense if the order doesn't
matter. So let's store new nodes at the end.
OK, now, armed with this information, we can make a start on the
AddNode() function. We should return a value to the caller to indicate
success/failure. Since success/failure depends on dynamic memory
allocation we could return a pointer to the object created. This will
be a null pointer in the case of failure. And of course we need to
pass (pointers to) the struct linkedlist we want to add the node to
and the data we want to store in the node. AddNode() is really quite
trivial to implement. But, as with any function, you need to bear in
mind what it actually has to do. There are four steps:
1) create (dynamically allocate) a new node,
2) store the data in it,
3) attach the new node to the list, and
4) update the count (numnodes).
struct node *AddNode(struct linkedlist *list, struct pcb *data)
{
struct node *node;
/* Step 1: create new node. */
node = malloc(sizeof *node)
if(node)
{
/* Step 2: store data in node. */
node->thread = data;
/* Step 3: attatch node to list. */
/* Is the list empty? */
if(NULL == head)
{
/* List is empty. */
/* Step 3ai: point the new node's links to NULL. */
node->next = node->prev = NULL;
/* Step 3aii: point head & tail pointers to new node. New node
is both first and last node in list, so both head and tail pointers
must point to it. */
list->head = list->tail = node;
}
else
{
/* List is not empty. */
/* Step 3bi: point new node's "next" link to NULL. */
node->next = NULL;
/* Step 3bii: point new node's "prev" link to list's last node.
*/
node->prev = list->tail;
/* Step 3biii: point last node's "next" link to new node. */
list->tail->next = node;
/* Step 3biv: point tail pointer to new node. */
list->tail = node;
}
/* Step 4: Add 1 to number of nodes. */
list->numnodes++;
}
return node;
}
And now we can define FreeNode() too. Since we stored the actual
data in the node, not a dynamically allocated copy, we don't have to
free that. All we have to free is the node itself. So FreeNode()
becomes a simple wrapper around free().
void FreeNode(struct node *node)
{
free(node);
}
Freeing a single node (but not the whole list), copying nodes,
sorting a list and other operations are left as an exercise for the
OP.
--
Dig the even newer still, yet more improved, sig!
http://alphalink.com.au/~phaywood/
"Ain't I'm a dog?" - Ronny Self, Ain't I'm a Dog, written by G. Sherry & W. Walker.
I know it's not "technically correct" English; but since when was rock & roll "technically correct"?
