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

## 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 ContainerOf(address, type, field) ((type *)( \
(unsigned long long)(&((type *)0)->field)) \
)

};

next->prev = now;
now->next = next;
now->prev = prev;
WriteOnce(prev->next, now);
}
next->prev = prev;
WriteOnce(prev->next, next);
}
WriteOnce(list->next, list);
list->prev = list;
}
}
}
}
}

static inline void ListRemove(struct ListHead *entry) {
__ListRemove(entry->prev, entry->next);
}
ListRemove(result);
return(result);
}
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)

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

int main() {

struct MyItem {
int data;
};

MyItem mylist = {};

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 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...

##### 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) {
}
void PushFront(T *item) {
}
...
};

struct MyAwesomeItem : GenericListItem<MyAwesomeItem>
{
int data;
};

Btw: This nullyfies my thread post entirely. Edited by Finalspace

##### 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 on other sites
The OP uses C, is my guess :)

##### 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 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

1. 1
Rutin
32
2. 2
3. 3
4. 4
5. 5

• 11
• 13
• 87
• 11
• 10
• ### Forum Statistics

• Total Topics
632973
• Total Posts
3009617
• ### Who's Online (See full list)

There are no registered users currently online

×