diff options
| -rw-r--r-- | llist.h | 103 |
1 files changed, 103 insertions, 0 deletions
@@ -0,0 +1,103 @@ +/** + * llist.h + * Copyright (c) 2022 Jon Santmyer <jon@jonsantmyer.com> + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + * + */ + +#ifndef LINKED_LIST_H +#define LINKED_LIST_H 1 + +#include <stddef.h> + +/*List member structs must begin with this struct as the first member*/ +struct llist_header +{ + struct llist_header *prev, *next; +}; + +/*Marks an unknown-state llist header as a single member circular list*/ +static inline void __llist_setup(struct llist_header *head) +{ + head->prev = head->next = head; +} +#define llist_setup(head) __llist_setup((struct llist_header*)(head)) + +/*Fits a new node between prev and next*/ +static inline void __llist_add(struct llist_header *new, struct llist_header *prev, struct llist_header *next) +{ + new->prev = prev; + new->next = next; + prev->next = new; + next->prev = new; +} + +#define llist_append(head, new) __llist_add(\ + (struct llist_header*)(new), \ + (struct llist_header*)(head), \ + (struct llist_header*)(head->next)) +#define llist_prepend(head, new) __llist_add(\ + (struct llist_header*)(new), \ + (struct llist_header*)(head->prev), \ + (struct llist_header*)(head)) + +/*Seperates a node from prev and next, marking the removed as memberless*/ +static inline void __llist_del(struct llist_header *node, struct llist_header *prev, struct llist_header *next) +{ + prev->next = node->next; + next->prev = node->prev; + node->prev = node->next = NULL; +} +#define llist_del(node) __llist_del(\ + (struct llist_header*)(node), \ + (struct llist_header*)(node->prev), \ + (struct llist_header*)(node->next)) + +/*Returns the list header i elements ahead of head*/ +static inline struct llist_header *__llist_traverse(struct llist_header *head, size_t i) +{ + if(head == NULL) return NULL; + for(; i != 0 && head != NULL; head = head->next, i--); + return head; +} +#define llist_traverse(head, i) __list_traverse((struct llist_header*)(head), i) + +/*Returns how many jumps forwards it takes to reach find*/ +static inline int __llist_at(struct llist_header *head, struct llist_header *find) +{ + if(head == NULL) return -1; + int r = 1; + for( + struct llist_header *node = head->next; + node != head; + node = node->next, r++) { + if(node == find) return ++r; + } + return -1; +} +#define llist_at(head, find) __llist_at(\ + (struct llist_header*)(head), \ + (struct llist_header*)(find)) + +/*Define for easily looping through a llist*/ +#define llist_foreach(node, head) \ + for(struct llist_header *node = head->next; node != head; node = node->next) + +#endif |