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