From 1c6c13564704c6defc003f727782cef984e43039 Mon Sep 17 00:00:00 2001 From: cloudwalk Date: Mon, 7 Sep 2020 23:57:34 +0000 Subject: [PATCH] Implement Linux kernel-inspired generic cyclic doubly linked list interface It's incomplete, leaving out several helpers. These will be added later if the need arises. git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@12910 d7cf8633-e32d-0410-b094-e92efae38249 --- com_list.c | 210 +++++++++++++++++++++++++++++++++ com_list.h | 55 +++++++++ common.h | 2 + darkplaces-sdl2-vs2017.vcxproj | 2 + darkplaces-sdl2-vs2019.vcxproj | 2 + makefile.inc | 1 + quakedef.h | 1 + 7 files changed, 273 insertions(+) create mode 100644 com_list.c create mode 100644 com_list.h diff --git a/com_list.c b/com_list.c new file mode 100644 index 00000000..cb001480 --- /dev/null +++ b/com_list.c @@ -0,0 +1,210 @@ +/* +Copyright (C) 2020 David "Cloudwalk" Knapp + +This program is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License +as published by the Free Software Foundation; either version 2 +of the License, or (at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + +See the GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software +Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + +*/ + +// com_list.c - generic doubly linked list interface, inspired by Linux list.h + +#include "qtypes.h" +#include "com_list.h" + +/* + * Insert a node between two known nodes. + * + * Only use when prev and next are known. + */ +static void __List_Add(llist_t *node, llist_t *prev, llist_t *next) +{ + next->prev = node; + node->next = next; + node->prev = prev; + prev->next = node; +} + +/* + * Insert a node immediately after head. + */ +void List_Add(llist_t *node, llist_t *head) +{ + __List_Add(node, head, head->next); +} + +/* + * Insert a node immediately before head. + */ +void List_Add_Tail(llist_t *node, llist_t *head) +{ + __List_Add(node, head->prev, head); +} + +/* + * Bridge prev and next together, when removing the parent of them. + */ +static void __List_Delete(llist_t *prev, llist_t *next) +{ + next->prev = prev; + prev->next = next; +} + +/* + * Redundant? + */ +static void __List_Delete_Node(llist_t *node) +{ + __List_Delete(node->prev, node->next); +} + +/* + * Removes a node from its list. + */ +void List_Delete(llist_t *node) +{ + __List_Delete_Node(node); + node->next = node->prev = node; +} + +/* + * Replace old with new. Old is overwritten if empty. + */ +void List_Replace(llist_t *old, llist_t *_new) +{ + _new->next = old->next; + _new->next->prev = _new; + _new->prev = old->prev; + _new->prev->next = _new; + old->next = old->prev = old; +} + +/* + * Swap node1 with node2 in place. + */ +void List_Swap(llist_t *node1, llist_t *node2) +{ + llist_t *pos = node2->prev; + List_Delete(node2); + List_Replace(node1, node2); + if(pos == node1) + pos = node2; + List_Add(node1, pos); +} + +/* + * Delete list from its... list, then insert after head. + */ +void List_Move(llist_t *list, llist_t *head) +{ + __List_Delete_Node(list); + List_Add(list, head); +} + +/* + * Delete list from its... list, then insert before head. + */ +void List_Move_Tail(llist_t *list, llist_t *head) +{ + __List_Delete_Node(list); + List_Add_Tail(list, head); +} + +/* + * Move the first node of a range of nodes immediately after head. + * All three parameters must belong to the same list. + */ + +void List_Bulk_Move_Tail(llist_t *head, llist_t *first, llist_t *last) +{ + first->prev->next = last->next; + last->next->prev = first->prev; + + head->prev->next = first; + first->prev = head->prev; + + last->next = head; + head->prev = last; +} + +/* + * Shift the head to the right (like rotating a wheel counterclockwise). + * The node immediately to the right becomes the new head. + */ +void List_Rotate_Left(llist_t *head) +{ + llist_t *first; + + if (!List_IsEmpty(head)) + { + first = head->next; + List_Move_Tail(first, head); + } +} + +/* + * Make list the new head. + */ +void List_Rotate_To_Front(llist_t *list, llist_t *head) +{ + List_Move_Tail(head, list); +} + +/* + * Concatenate two lists. The head of list will be discarded. + */ +static void __List_Splice(const llist_t *list, llist_t *prev, llist_t *next) +{ + llist_t *first = list->next; + llist_t *last = list->prev; + + first->prev = prev; + prev->next = first; + + last->next = next; + next->prev = last; +} + +/* + * Concatenate two lists. The first node of list will be inserted after head. + */ +void List_Splice(const llist_t *list, llist_t *head) +{ + if(!List_IsEmpty(list)) + __List_Splice(list, head, head->next); +} + +/* + * Concatenate two lists. The tail of list will be inserted before head. + */ +void List_Splice_Tail(const llist_t *list, llist_t *head) +{ + if (!List_IsEmpty(list)) + __List_Splice(list, head->prev, head); +} + +qboolean List_IsFirst(llist_t *list, llist_t *start) +{ + return list->prev == start; +} + +qboolean List_IsLast(llist_t *list, llist_t *start) +{ + return list->next == start; +} + +qboolean List_IsEmpty(const llist_t *list) +{ + return list->next == list; +} \ No newline at end of file diff --git a/com_list.h b/com_list.h new file mode 100644 index 00000000..eac28823 --- /dev/null +++ b/com_list.h @@ -0,0 +1,55 @@ +/* +Copyright (C) 2020 David "Cloudwalk" Knapp + +This program is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License +as published by the Free Software Foundation; either version 2 +of the License, or (at your option) any later version. + +This program is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + +See the GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with this program; if not, write to the Free Software +Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + +*/ + +// com_list.c - generic doubly linked list interface, inspired by Linux list.h + +#include + +typedef struct llist_s +{ + struct llist_s *prev; + struct llist_s *next; +} llist_t; + +#define List_Head_Reset(name) { &(name), &(name) } + +#define List_Container(ptr, type, member) ContainerOf(ptr, type, member) + +#define List_ForEach(pos, head) \ + for (pos = (head)->next; pos != (head); pos = pos->next) + +#define List_ForEach_Prev(pos, head) \ + for (pos = (head)->prev; pos != (head); pos = pos->prev) + +void List_Add(llist_t *node, llist_t *start); +void List_Add_Tail(llist_t *node, llist_t *start); +void List_Delete(llist_t *node); +void List_Replace(llist_t *old, llist_t *_new); +void List_Swap(llist_t *node1, llist_t *node2); +void List_Move(llist_t *list, llist_t *start); +void List_Move_Tail(llist_t *list, llist_t *start); +void List_Bulk_Move_Tail(llist_t *start, llist_t *first, llist_t *last); +void List_Rotate_Left(llist_t *head); +void List_Rotate_To_Front(llist_t *list, llist_t *head); +void List_Splice(const llist_t *list, llist_t *head); +void List_Splice_Tail(const llist_t *list, llist_t *head); +qboolean List_IsFirst(llist_t *list, llist_t *start); +qboolean List_IsLast(llist_t *list, llist_t *start); +qboolean List_IsEmpty(const llist_t *list); \ No newline at end of file diff --git a/common.h b/common.h index 15ca90d0..b92ca9aa 100644 --- a/common.h +++ b/common.h @@ -38,6 +38,8 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. //============================================================================ +#define ContainerOf(ptr, type, member) (type *)((void *)&(ptr) - offsetof(type, member)) + typedef struct sizebuf_s { qboolean allowoverflow; ///< if false, do a Sys_Error diff --git a/darkplaces-sdl2-vs2017.vcxproj b/darkplaces-sdl2-vs2017.vcxproj index 5eb99060..2b23d8e8 100644 --- a/darkplaces-sdl2-vs2017.vcxproj +++ b/darkplaces-sdl2-vs2017.vcxproj @@ -220,6 +220,7 @@ + @@ -327,6 +328,7 @@ + diff --git a/darkplaces-sdl2-vs2019.vcxproj b/darkplaces-sdl2-vs2019.vcxproj index 138b58a9..0eea6d48 100644 --- a/darkplaces-sdl2-vs2019.vcxproj +++ b/darkplaces-sdl2-vs2019.vcxproj @@ -221,6 +221,7 @@ + @@ -328,6 +329,7 @@ + diff --git a/makefile.inc b/makefile.inc index b2255ab9..51b64d15 100644 --- a/makefile.inc +++ b/makefile.inc @@ -101,6 +101,7 @@ OBJ_COMMON= \ com_ents.o \ com_ents4.o \ com_game.o \ + com_list.o \ com_msg.o \ common.o \ console.o \ diff --git a/quakedef.h b/quakedef.h index 41c91c96..ff6a3943 100644 --- a/quakedef.h +++ b/quakedef.h @@ -371,6 +371,7 @@ extern char engineversion[128]; #include "zone.h" #include "fs.h" #include "common.h" +#include "com_list.h" #include "cvar.h" #include "bspfile.h" #include "sys.h" -- 2.39.2