summaryrefslogtreecommitdiffstats
path: root/src/list.c
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2023-03-28 14:18:08 -0400
committerTavian Barnes <tavianator@tavianator.com>2023-03-29 12:26:43 -0400
commit135b98c26456adbfbc72fb12e4753ee0716b1f92 (patch)
tree992541d0f4b215dd44a6648db0f796a7a05da2dc /src/list.c
parente40855d3b98aa3f65c19608b3d8c70f54b714063 (diff)
downloadbfs-135b98c26456adbfbc72fb12e4753ee0716b1f92.tar.xz
list: New generic linked list API
Diffstat (limited to 'src/list.c')
-rw-r--r--src/list.c169
1 files changed, 169 insertions, 0 deletions
diff --git a/src/list.c b/src/list.c
new file mode 100644
index 0000000..dffee19
--- /dev/null
+++ b/src/list.c
@@ -0,0 +1,169 @@
+// Copyright © Tavian Barnes <tavianator@tavianator.com>
+// SPDX-License-Identifier: 0BSD
+
+#include "list.h"
+#include <assert.h>
+#include <stddef.h>
+
+void slink_init(struct slink *link) {
+ link->next = NULL;
+}
+
+void slist_init(struct slist *list) {
+ list->head = NULL;
+ list->tail = &list->head;
+}
+
+bool slist_is_empty(const struct slist *list) {
+ return !list->head;
+}
+
+void slist_append(struct slist *list, struct slink *link) {
+ assert(!link->next);
+ *list->tail = link;
+ list->tail = &link->next;
+}
+
+void slist_prepend(struct slist *list, struct slink *link) {
+ assert(!link->next);
+ if (!list->head) {
+ list->tail = &link->next;
+ }
+ link->next = list->head;
+ list->head = link;
+}
+
+void slist_extend(struct slist *dest, struct slist *src) {
+ if (src->head) {
+ *dest->tail = src->head;
+ dest->tail = src->tail;
+ slist_init(src);
+ }
+}
+
+struct slink *slist_pop(struct slist *list) {
+ struct slink *head = list->head;
+ if (!head) {
+ return NULL;
+ }
+
+ list->head = head->next;
+ if (!list->head) {
+ list->tail = &list->head;
+ }
+
+ head->next = NULL;
+ return head;
+}
+
+void slist_sort(struct slist *list, slist_cmp_fn *cmp_fn, const void *ptr) {
+ if (!list->head || !list->head->next) {
+ return;
+ }
+
+ struct slist left, right;
+ slist_init(&left);
+ slist_init(&right);
+
+ // Split
+ for (struct slink *hare = list->head; hare && (hare = hare->next); hare = hare->next) {
+ slist_append(&left, slist_pop(list));
+ }
+ slist_extend(&right, list);
+
+ // Recurse
+ slist_sort(&left, cmp_fn, ptr);
+ slist_sort(&right, cmp_fn, ptr);
+
+ // Merge
+ while (left.head && right.head) {
+ if (cmp_fn(left.head, right.head, ptr)) {
+ slist_append(list, slist_pop(&left));
+ } else {
+ slist_append(list, slist_pop(&right));
+ }
+ }
+ slist_extend(list, &left);
+ slist_extend(list, &right);
+}
+
+void link_init(struct link *link) {
+ link->prev = NULL;
+ link->next = NULL;
+}
+
+void list_init(struct list *list) {
+ list->head = NULL;
+ list->tail = NULL;
+}
+
+bool list_is_empty(const struct list *list) {
+ return !list->head;
+}
+
+void list_append(struct list *list, struct link *link) {
+ list_insert_after(list, list->tail, link);
+}
+
+void list_prepend(struct list *list, struct link *link) {
+ list_insert_after(list, NULL, link);
+}
+
+void list_insert_after(struct list *list, struct link *target, struct link *link) {
+ assert(!list_attached(list, link));
+
+ if (target) {
+ link->prev = target;
+ link->next = target->next;
+ } else {
+ link->next = list->head;
+ }
+
+ if (link->prev) {
+ link->prev->next = link;
+ } else {
+ list->head = link;
+ }
+
+ if (link->next) {
+ link->next->prev = link;
+ } else {
+ list->tail = link;
+ }
+}
+
+void list_remove(struct list *list, struct link *link) {
+ if (link->prev) {
+ assert(list->head != link);
+ link->prev->next = link->next;
+ } else {
+ assert(list->head == link);
+ list->head = link->next;
+ }
+
+ if (link->next) {
+ assert(list->tail != link);
+ link->next->prev = link->prev;
+ } else {
+ assert(list->tail == link);
+ list->tail = link->prev;
+ }
+
+ link->prev = NULL;
+ link->next = NULL;
+}
+
+struct link *list_pop(struct list *list) {
+ struct link *head = list->head;
+ if (!head) {
+ return NULL;
+ }
+
+ list_remove(list, head);
+ return head;
+}
+
+bool list_attached(const struct list *list, const struct link *link) {
+ return link->prev || list->head == link
+ || link->next || list->tail == link;
+}