Path: utzoo!utgpu!water!watmath!clyde!att!ucbvax!husc6!bloom-beacon!athena.mit.edu!scs
From: scs@athena.mit.edu (Steve Summit)
Newsgroups: comp.lang.c
Subject: Re: static list initialization
Message-ID: <7612@bloom-beacon.MIT.EDU>
Date: 22 Oct 88 22:05:36 GMT
References: <196@donk.UUCP>
Sender: daemon@bloom-beacon.MIT.EDU
Reply-To: scs@adam.pika.mit.edu (Steve Summit)
Distribution: na
Lines: 40

In article <196@donk.UUCP> ajw@donk.UUCP (ajw) writes:
>Here's a fragment of code I find myself staring at glumly from
>time to time.  It sets up the nucleus of a 2-way list, into
>which extra malloc'd nodes will be inserted.

In general, I try not to have statically- and dynamically-
allocated elements in the same list, because of the possibility
of trying to free one of the statically-allocated ones.
Preventing this can require ugly special cases.

I usually use something like

	static struct whatever *head = NULL;
	static struct whatever *tail = NULL;

	insert_at_head(stuff)
	int stuff;
	{
	struct whatever *new;

	new = (struct whatever *)alloc(sizeof(struct whatever));

	new->eresting_stuff = stuff;
	new->next = head;
	head = new;
	new->prev = NULL;
	if(tail == NULL)
		tail = new;
	}

Note that head and tail are now pointers, not structures.  This
still requires one special case, to set tail initially, which is
one reason I don't like doubly-linked lists.  Complexity seems to
be O(n**2) with the number of links, so that doubly-linked lists
are four times as hard to get right as singly-linked ones.  (You
can insert at either the head or tail of a singly-linked list
without special casing the initial case, if you're clever.)

                                            Steve Summit
                                            scs@adam.pika.mit.edu