Well, another day another cheap trick. It's about linked lists, again, but this time probably more practical. Consider the following, you want to write a container for your list that also provides convinient functions to work with the list's content, the functions are going to be well tested and debugged so you can be sure that it works without any flaws and don't have to copy and paste all over the place and keep track of them in case you have to fix something.

But, oh noes, how would a node/bucket in the linked list look like? It must be generic as well, so you will probably end up with something like this:
Code:
typedef struct bucket_s
{
    void *data;
    
    struct bucket_s *next;
    struct bucket_s *prev;
} bucket_t;


But this is rather inelegant, because what exactly are you going to pass around when working with the linked list? The data pointer or the bucket/node (which requires you to keep track of the content and the bucket when working with the data). But if you use just the data, you have too lookup the node the data belongs to every time you want to operate with the list. Deleting a known node, which should be an O(1) operation in a linked list suddenly becomes an O(n) operation! All advantages of a linked list gone, and let's not even talk about walking down the list.

So let's go and toss the generic bucket around, let's do two allocations instead of one and let's alway go an indirect route when working with our data, all for the sake of performance and freedom of bugs.
No wait, actually, let's do something else. You can tell the list WHERE your next and previous pointers are in the linked list and have it work with this data. So you are free to design your own bucket and still have the advantage of a fast and generic linked list implementation.

It's easy to say the least, so I'm just going to leave you with the code which implements the two functions add and delete. Afterwards follows a short example with a custom bucket.


Code:
// offsetof Makro
#define offsetof(type, member) ((unsigned int)&(((type *)0)->member))

typedef struct
{
	size_t oPrev;
	size_t oNext;
	
	void *head;
	void *tail;
} list_t;


list_t *list_create(size_t oPrev, size_t oNext)
{
	list_t *list = malloc(sizeof(list_t));
	if(list)
	{
		list->oPrev = oPrev;
		list->oNext = oNext;
		
		list->head = list->tail = NULL;
	}
	
	return list;
}

// Access primitives
#define list_t_accessPrev(list, entry) *((void **)&((char *)entry)[list->oPrev])
#define list_t_accessNext(list, entry) *((void **)&((char *)entry)[list->oNext])

void list_addBack(list_t *list, void *entry)
{
	if(list->tail)
	{
		list_t_accessPrev(list, entry) = list->tail;
		list_t_accessNext(list, entry) = NULL;
		
		list_t_accessNext(list, list->tail) = entry;
	}
	else
	{
		list_t_accessPrev(list, entry) = NULL;
		list_t_accessNext(list, entry) = NULL;
		
		list->head = entry;
	}
	
	list->tail = entry;
}

void list_delete(list_t *list, void *entry)
{
	void *prev = list_t_accessPrev(list, entry);
	void *next = list_t_accessNext(list, entry);
	
	if(prev)
		list_t_accessNext(list, prev) = next;
	
	if(next)
		list_t_accessPrev(list, next) = prev;
    
	if(list->head == entry)
		list->head = next;
    
	if(list->tail == entry)
		list->tail = prev;
}


Example:
Code:
typedef struct myBucket
{
	int i;
	
	struct myBucket *prev;
	struct myBucket *next;
} myBucket;

myBucket *bucket_create(int i)
{
	myBucket *bucket = malloc(sizeof(myBucket));
	
	bucket->i = i;
	
	return bucket;
}

void main()
{
	list_t *list = list_create(offsetof(myBucket, prev), offsetof(myBucket, next));
	
	// Insert ten entries
	for(int i=0; i<10; i++)
	{
		myBucket *bucket = bucket_create(i);
		list_addBack(list, bucket);
		
		if((i % 2) == 0) // No, actually, I hate even numbers. Fuck them!
		{
			list_delete(list, bucket);
			free(bucket);
		}
	}
	
	// Iterate over the entries
	myBucket *bucket = list->head;
	while(bucket)
	{
		printf("i: %i\n", bucket->i);
		bucket = bucket->next;
	}
}

Shitlord by trade and passion. Graphics programmer at Laminar Research.
I write blog posts at feresignum.com