• Advertisement
Sign in to follow this  

Linked list adventure

This topic is 438 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

After fiddling around with making macros for a non-generic linked list, i decided to use the same style used in the linux kernel list.h.
This works and seems to be fast as well - even though i have to use ListNextEntry to iterate over items (Small price to pay for a bit genericness):

Warning: This code should never be used in any way - except you release your application under GPL!
 
#define WriteOnce(x, val) x=(val)
#define WriteOnce(x, val) x=(val)
#define ReadOnce(x) (x)

#define ContainerOf(address, type, field) ((type *)( \
		(char *)(address) - \
		(unsigned long long)(&((type *)0)->field)) \
	)

struct ListHead {
	struct ListHead *next;
	struct ListHead *prev;
};

static inline void __ListAdd(struct ListHead *now, struct ListHead *prev, struct ListHead *next) {
	next->prev = now;
	now->next = next;
	now->prev = prev;
	WriteOnce(prev->next, now);
}
static inline void __ListRemove(struct ListHead *prev, struct ListHead * next) {
	next->prev = prev;
	WriteOnce(prev->next, next);
}
static inline void InitListHead(struct ListHead *list) {
	WriteOnce(list->next, list);
	list->prev = list;
}
static inline void ListPushFront(struct ListHead *now, struct ListHead *head) {
	__ListAdd(now, head, head->next);
}
static inline void ListPushBack(struct ListHead *now, struct ListHead *head) {
	__ListAdd(now, head->prev, head);
}
static inline int IsItemLast(const struct ListHead *item, const struct ListHead *head) {
	return item->next == head;
}
static inline int IsListEmpty(const struct ListHead *head) {
	return ReadOnce(head->next) == head;
}

static inline void ListRemove(struct ListHead *entry) {
	__ListRemove(entry->prev, entry->next);
}
static inline ListHead *__ListPopFront(struct ListHead *head) {
	ListHead *result = ReadOnce(head->next);
	ListRemove(result);
	return(result);
}
static inline ListHead *__ListPopBack(struct ListHead *head) {
	ListHead *result = ReadOnce(head->prev);
	ListRemove(result);
	return(result);
}

#define ListEntry(ptr, type, member) \
	ContainerOf(ptr, type, member)

#define ListFirstEntry(ptr, type, member) \
	ListEntry((ptr)->next, type, member)

#define ListLastEntry(ptr, type, member) \
	ListEntry((ptr)->prev, type, member)

#define ListNextEntry(pos, type, member) \
	ListEntry((pos)->member.next, type, member)

#define ListPrevEntry(pos, type, member) \
	ListEntry((pos)->member.prev, type, member)

#define ListPopFront(head, type, member) \
	ListEntry(__ListPopFront(head), type, member)

#define ListPopBack(head, type, member) \
	ListEntry(__ListPopBack(head), type, member)

#include <malloc.h>
#include <stdio.h>
#include <Windows.h>

int main() {

	struct MyItem {
		struct ListHead list;
		int data;
	};

	MyItem mylist = {};
	InitListHead(&mylist.list);

	int listCapacity = 10;
	MyItem *listBase = (MyItem *)malloc(sizeof(MyItem) * listCapacity);

	for (int i = 0; i < listCapacity; ++i) {
		MyItem *item = listBase + i;
		*item = {};
		item->data = i + 1;
		ListPushBack(&item->list, &mylist.list);
	}

	MyItem *firstItem = ListPopFront(&mylist.list, MyItem, list);
	MyItem *lastItem = ListPopBack(&mylist.list, MyItem, list);

	char buffer[255];
	for (MyItem *item = ListFirstEntry(&mylist.list, MyItem, list); item != &mylist; item = ListNextEntry(item, MyItem, list)) {
		sprintf_s(buffer, "%d\n", item->data);
		OutputDebugString(buffer);
	}

	free(listBase);

	return 0;
}
Also circular lists seems to be much easier to implement and are more robust. Back is just head->prev and front head->next.

The only thing i dont like is the LIST_POISON thingy, i rather set the next and prev pointer to zero.
In addition i included a pop front and back function as well.

If you are interested how the linux linked list are defined, here is the full version of it: https://github.com/torvalds/linux/blob/master/include/linux/list.h

NOTE: There was a previous post and title here, but somehow a reply to this post replaced the original one - so i had to change this entire post... sorry about that -.- Edited by Finalspace

Share this post


Link to post
Share on other sites
Advertisement

Just a quick note about this, if you've lifted the list macros from the linux kernel, doesnt this make your game's source code GPL, as the license is viral...

Share this post


Link to post
Share on other sites

Just a quick note about this, if you've lifted the list macros from the linux kernel, doesnt this make your game's source code GPL, as the license is viral...


Hmm, you are correct. Its the first time i found any interesting in the inux kernel ever and i assume just open source my list header file will not be enough: The entire application and source must be GPL!

But fortunatly the concept of circular linked lists are not patended in a way, so i can write and use ugly code like this - which does the same Thing, but requires C++ (https://en.wikipedia.org/wiki/Linked_list):
 
template <typename T>
struct GenericListItem {
  T *prev, *next;
  void Init() {
    prev = next = (T *)this;
  }
  void Add(T *item, T *prev, T *next) {
    next->prev = item;
    item->next = next;
    item->prev = prev;
  }
  void PushBack(T *item) {
    Add(item, (T *)this->prev, (T *)this);
  }
  void PushFront(T *item) {
    Add(item, (T *)this, (T *)this->next);
  }
  ...
};

struct MyAwesomeItem : GenericListItem<MyAwesomeItem>
{
  int data;
};
Btw: This nullyfies my thread post entirely. Edited by Finalspace

Share this post


Link to post
Share on other sites

In this day and age there is absolutely no reason to not use the c++ standard library containers.  If you are making linked list for education and learning, go for it.  But production code?  Standard library containers all the way.

Share this post


Link to post
Share on other sites

The OP uses C, is my guess :)


You are right sir - only C++ when needed.
 

In this day and age there is absolutely no reason to not use the c++ standard library containers.  If you are making linked list for education and learning, go for it.  But production code?  Standard library containers all the way.


Really? Are you serious?? Do you troll me or something???

Its the opposite: When you dont care about peformance or memory, you use std library however you like, like for example in some tools, debug stuff, business applications, you name it etc. but i would never use the std library in any realtime production code ever.

Most major game companies use custom memory systems, custom lists instead of the std library, just look at example at the EA library posted by "sirpalee".

Also there are few things which i really hate about the std library:

- I have no idea how the memory is allocated, how much it allocates, what it allocates, where it allocates the memory etc.
- I have no control over the allocated memory at all
- Debugging any std library errors is just horror
- Zero initialization totally breaks the containers:
 
std::vector<int> mylist = {};
mylist.push_back(42); // Crash

std::vector<int> mylist_autoctor;
mylist.push_back(42); // Works

std::vector<int> mylist_manctor = std::vector<int>();
mylist.push_back(42); // Works as well

std::vector<int> *mylist_ptr = new std::vector<int>();
mylist->push_back(42); // Whatever
This seems to be no problem for this simple case, but look at the following example:
 
struct Physics {
  std::vector<Body *> bodies;
};

struct GameState {
  Physics physics;
};

GameState gameState = {};
...
gameState.physics.bodies.push_back(mynewbody); // Crash, because zero initialization breaks the list
You have to use "new" for the entire GameState, so all default constructors will be called: The worst.
Or you have to make a pointer to the list, so only the list must be allocated with new: Also worst

Nothing more to say about that. Edited by Finalspace

Share this post


Link to post
Share on other sites

No, you don't. You do realize that the following does already call the default constructors, right?

GameState gameState;
You shouldn't be zero-initializing non-POD types the way you think you want to, anyway. I've encountered code that did the following and it was real bad: 
Thing::Thing() {
   memset(this, 0, sizeof(*this));
}
Please don't do that, or do anything that boils down to that.


This was just an example, i use VirtualAlloc to allocate my memory once and use my own allocation scheme, moving pointers around - without the use of new or malloc ever.
If this was a pointer it will have the same problem:
 
GameState *gameState = (GameState *)myGameMemoryAddress;
*gameState = {};
If this does not work, it cannot and i will never use it.
 

You can write custom allocators for the standard library containers. It's irritating, but you can do it.


Omg, i do not want to see any code for this... this must be "beutiful" like heaven.

Also about using std library in game dev, see this:
Edited by Finalspace

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement