commit 57a44cbf548e67798425dd96367c9f5f53101bad
Author: Louis Burda <quent.burda@gmail.com>
Date: Fri, 15 Mar 2024 22:54:09 +0100
Squashed 'src/lib/liblist/' content from commit fbebd71
git-subtree-dir: src/lib/liblist
git-subtree-split: fbebd71c0ee05f98a54ae7df7065985f58f3ebf6
Diffstat:
| A | .gitignore | | | 6 | ++++++ |
| A | LICENSE | | | 21 | +++++++++++++++++++++ |
| A | Makefile | | | 50 | ++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | build.jst.tmpl | | | 64 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | configure | | | 3 | +++ |
| A | include/list.h | | | 219 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | liblist.api | | | 23 | +++++++++++++++++++++++ |
| A | liblist.lds | | | 25 | +++++++++++++++++++++++++ |
| A | src/list.c | | | 224 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | src/test.c | | | 50 | ++++++++++++++++++++++++++++++++++++++++++++++++++ |
10 files changed, 685 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,6 @@
+compile_commands.json
+build
+build.jst
+.cache
+vgcore*
+test
diff --git a/LICENSE b/LICENSE
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) 2023 Louis Burda
+
+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.
diff --git a/Makefile b/Makefile
@@ -0,0 +1,50 @@
+PREFIX ?= /usr/local
+LIBDIR ?= /lib
+INCLDIR ?= /include
+
+CFLAGS = -I include -std=c99
+CFLAGS += -Wunused-function -Wunused-variable -Wno-prototype
+CFLAGS += -Wconversion -Wsign-compare -Werror
+
+ifeq "$(DEBUG)" "1"
+CFLAGS += -Og -g
+else
+CFLAGS += -O2
+endif
+
+ifeq "$(ASSERT_ARGS)" "1"
+CFLAGS += -DLIBLIST_ASSERT_ARGS=1
+endif
+
+all: build/liblist.so build/liblist.a build/test
+
+clean:
+ rm -rf build
+
+cleanall: clean
+
+build:
+ mkdir build
+
+build/liblist.a: src/list.c include/list.h liblist.api | build
+ $(CC) -o build/tmp.o src/list.c $(CFLAGS) -r
+ objcopy --keep-global-symbols=liblist.api build/tmp.o build/fixed.o
+ ar rcs $@ build/fixed.o
+
+build/liblist.so: src/list.c include/list.h liblist.lds | build
+ $(CC) -o $@ src/list.c $(CFLAGS) -shared -Wl,-version-script liblist.lds
+
+build/test: src/test.c build/liblist.a | build
+ $(CC) -o $@ $^ -I include
+
+install:
+ install -m644 include/list.h -t "$(DESTDIR)$(PREFIX)$(INCLDIR)"
+ install -m755 build/liblist.a -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
+ install -m755 build/liblist.so -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
+
+uninstall:
+ rm -f "$(DESTDIR)$(PREFIX)$(INCLDIR)/list.h"
+ rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/liblist.a"
+ rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/liblist.so"
+
+.PHONY: all clean cleanall install uninstall
diff --git a/build.jst.tmpl b/build.jst.tmpl
@@ -0,0 +1,64 @@
+#default PREFIX /usr/local
+#default INCLDIR /include
+#default LIBDIR /lib
+#default CC gcc
+
+#ifdef LIBLIST_DEBUG
+#define DEBUG 1
+#endif
+
+#ifdef DEBUG
+#define OPT_CFLAGS -Og -g
+#else
+#define OPT_CFLAGS -O2
+#endif
+
+cflags = -Wunused-function -Wunused-variable -Wconversion
+ -I include #{OPT_CFLAGS} #{EXTRA_CFLAGS} #{LIBLIST_EXTRA_CFLAGS}
+
+rule liba
+ #{CC} -o $out.tmp.o $in $cflags -r
+ objcopy --keep-global-symbols=liblist.api $out.tmp.o $out.fixed.o
+ ar rcs $out $out.fixed.o
+ rm $out.tmp.o $out.fixed.o
+
+rule libso
+ #{CC} -o $out $in $cflags -shared -Wl,-version-script liblist.lds
+
+rule cc
+ #{CC} -o $out $in $cflags
+
+rule mkdir
+ mkdir $out
+
+target build
+ mkdir
+
+target build/liblist.a
+ liba src/list.c | include/list.h build
+
+target build/liblist.so
+ libso src/list.c | include/list.h build
+
+target build/test
+ cc src/test.c build/liblist.a | build
+
+command clean
+ rm -rf build
+
+command cleanall
+ just clean
+
+command install
+ install -m755 build/liblist.a -t "#{DESTDIR}#{PREFIX}#{LIBDIR}"
+ install -m755 build/liblist.so -t "#{DESTDIR}#{PREFIX}#{LIBDIR}"
+ install -m644 include/list.h -t "#{DESTDIR}#{PREFIX}#{INCLDIR}"
+
+command uninstall
+ rm -f "#{DESTDIR}#{PREFIX}#{LIBDIR}/liblist.a"
+ rm -f "#{DESTDIR}#{PREFIX}#{LIBDIR}/liblist.so"
+ rm -f "#{DESTDIR}#{PREFIX}#{INCLDIR}/list.h"
+
+command all
+ just build/liblist.a build/liblist.so build/test
+
diff --git a/configure b/configure
@@ -0,0 +1,3 @@
+#!/bin/sh
+
+tmpl "$@" build.jst.tmpl > build.jst
diff --git a/include/list.h b/include/list.h
@@ -0,0 +1,219 @@
+#pragma once
+
+#include <sys/types.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+#define LIST_LINK_INIT ((struct list_link) { 0 })
+
+#define LIST_OFFSET(type, member) ((size_t) &((type *)0)->member)
+#define LIST_UPCAST(ptr, type, member) \
+ ((type *)((char *)ptr - LIST_OFFSET(type, member)))
+
+#define LIST_INNER(link) ((link) != NULL && \
+ (link)->prev != NULL && (link)->next != NULL)
+
+#define LIST_ITER(list, iter) (iter) = (list)->head.next; \
+ (iter) != &(list)->tail; (iter) = (iter)->next
+#define LIST_ITER_BWD(list, iter) (iter) = (list)->tail.prev; \
+ (iter) != &(list)->head; (iter) = (iter)->prev
+
+#define LIST_ITER_ITEMS(list, item, type, member) \
+ struct list_link *_iter = (list)->head.next; \
+ _iter != &(list)->tail \
+ && ((item) = LIST_UPCAST(_iter, type, member)); \
+ _iter = _iter->next
+#define LIST_ITER_ITEMS_BWD(list, item, type, member) \
+ struct link_link *_iter = (list)->tail.prev; \
+ _iter != &(list)->head \
+ && ((item) = LIST_UPCAST(_iter, type, member)); \
+ _iter = _iter->prev
+
+#define LIST_FRONT_ITEM(list, type, member) \
+ ((type *) ({ void *p = list_front(list); \
+ p ? LIST_UPCAST(p, type, member) : p; }))
+#define LIST_BACK_ITEM(list, type, member) \
+ ((type *) ({ void *p = list_back(list); \
+ p ? LIST_UPCAST(p, type, member) : p; }))
+
+#define LIST_ITEM_AT(list, idx, type, member) \
+ ((type *) ({ void *p = list_at(list, idx); \
+ p ? LIST_UPCAST(p, type, member) : p; }))
+#define LIST_ITEM_AT_BACK(list, idx, type, member) \
+ ((type *) ({ void *p = list_at_back(list, idx); \
+ p ? LIST_UPCAST(p, type, member) : p; }))
+
+#ifdef LIBLIST_ASSERT_ARGS
+#define LIST_ABORT_ON_ARGS(cond) do { if (cond) abort(); } while (0)
+#else
+#define LIST_ABORT_ON_ARGS(cond)
+#endif
+
+typedef void (*list_item_free_fn)(void *p);
+typedef bool (*list_sort_order_fn)(const void *p1, const void *p2, void *u);
+
+struct list_link {
+ struct list_link *prev;
+ struct list_link *next;
+};
+
+struct list {
+ struct list_link head;
+ struct list_link tail;
+};
+
+void list_init(struct list *list);
+void list_clear(struct list *list);
+void list_free_items(struct list *list,
+ list_item_free_fn free_item, size_t offset);
+
+static inline struct list_link *list_front(const struct list *list);
+static inline struct list_link *list_back(const struct list *list);
+
+static inline bool list_empty(const struct list *list);
+size_t list_len(const struct list *list);
+ssize_t list_index(const struct list *list, const struct list_link *link);
+
+struct list_link *list_at(struct list *list, size_t n);
+struct list_link *list_at_back(struct list *list, size_t n);
+
+void list_insert_sorted(struct list *list, struct list_link *link,
+ bool reverse, list_sort_order_fn in_order, size_t offset, void *user);
+void list_insert_sorted_bwd(struct list *list, struct list_link *link,
+ bool reverse, list_sort_order_fn in_order, size_t offset, void *user);
+void list_insertion_sort(struct list *list,
+ bool reverse, list_sort_order_fn in_order, size_t offset, void *user);
+static inline void list_insert_front(struct list *list, struct list_link *link);
+static inline void list_insert_back(struct list *list, struct list_link *link);
+
+struct list_link *list_pop_front(struct list *list);
+struct list_link *list_pop_back(struct list *list);
+
+static inline bool list_link_inuse(const struct list_link *link);
+struct list_link *list_link_pop(struct list_link *link);
+
+struct list_link *list_iter_fwd(struct list_link *link, size_t n);
+struct list_link *list_iter_bwd(struct list_link *link, size_t n);
+
+static inline void list_link_prepend(struct list_link *a, struct list_link *b);
+static inline void list_link_append(struct list_link *a, struct list_link *b);
+
+static inline void list_link_attach_next(struct list_link *a, struct list_link *b);
+static inline void list_link_attach_prev(struct list_link *a, struct list_link *b);
+
+static inline void list_link_detach_next(struct list_link *link);
+static inline void list_link_detach_prev(struct list_link *link);
+
+static inline struct list_link *
+list_front(const struct list *list)
+{
+ struct list_link *link;
+
+ LIST_ABORT_ON_ARGS(!list);
+
+ link = list->head.next;
+
+ return link != &list->tail ? link : NULL;
+}
+
+static inline struct list_link *
+list_back(const struct list *list)
+{
+ struct list_link *link;
+
+ LIST_ABORT_ON_ARGS(!list);
+
+ link = list->tail.prev;
+
+ return link != &list->head ? link : NULL;
+}
+
+static inline bool
+list_empty(const struct list *list)
+{
+ LIST_ABORT_ON_ARGS(!list);
+
+ return list->head.next == &list->tail;
+}
+
+static inline bool
+list_link_inuse(const struct list_link *link)
+{
+ LIST_ABORT_ON_ARGS(!link);
+
+ return link->prev && link->next;
+}
+
+static inline void
+list_insert_front(struct list *list, struct list_link *link)
+{
+ LIST_ABORT_ON_ARGS(!list);
+
+ list_link_append(&list->head, link);
+}
+
+static inline void
+list_insert_back(struct list *list, struct list_link *link)
+{
+ LIST_ABORT_ON_ARGS(!list);
+
+ list_link_prepend(&list->tail, link);
+}
+
+/* attach b before a: b -> a */
+static inline void
+list_link_prepend(struct list_link *a, struct list_link *b)
+{
+ list_link_attach_prev(a, b);
+}
+
+/* attach b after a: a -> b */
+static inline void
+list_link_append(struct list_link *a, struct list_link *b)
+{
+ list_link_attach_next(a, b);
+}
+
+/* attach b before a: b -> a */
+static inline void
+list_link_attach_prev(struct list_link *a, struct list_link *b)
+{
+ LIST_ABORT_ON_ARGS(!a || !b);
+
+ b->prev = a->prev;
+ b->next = a;
+
+ if (b->prev) b->prev->next = b;
+ a->prev = b;
+}
+
+/* attach b after a: a -> b */
+static inline void
+list_link_attach_next(struct list_link *a, struct list_link *b)
+{
+ LIST_ABORT_ON_ARGS(!a || !b);
+
+ b->next = a->next;
+ b->prev = a;
+
+ if (b->next) b->next->prev = b;
+ a->next = b;
+}
+
+static inline void
+list_link_detach_next(struct list_link *link)
+{
+ LIST_ABORT_ON_ARGS(!link);
+
+ if (link->next) link->next->prev = NULL;
+ link->next = NULL;
+}
+
+static inline void
+list_link_detach_prev(struct list_link *link)
+{
+ LIST_ABORT_ON_ARGS(!link);
+
+ if (link->prev) link->prev->next = NULL;
+ link->prev = NULL;
+}
diff --git a/liblist.api b/liblist.api
@@ -0,0 +1,23 @@
+list_init
+list_clear
+list_free_items
+
+list_len
+list_index
+
+list_insert_sorted
+list_insert_sorted_bwd
+list_insertion_sort
+
+list_at
+list_at_back
+
+list_pop_front
+list_pop_back
+
+list_link_iter_fwd
+list_link_iter_bwd
+list_link_pop
+
+list_link_prepend
+list_link_append
diff --git a/liblist.lds b/liblist.lds
@@ -0,0 +1,25 @@
+LIBLIST_1.2 {
+ list_init;
+ list_clear;
+ list_free_items;
+
+ list_len;
+ list_index;
+
+ list_insert_sorted;
+ list_insert_sorted_bwd;
+ list_insertion_sort;
+
+ list_at;
+ list_at_back;
+
+ list_pop_front;
+ list_pop_back;
+
+ list_link_iter_fwd;
+ list_link_iter_bwd;
+ list_link_pop;
+
+ list_link_prepend;
+ list_link_append;
+};
diff --git a/src/list.c b/src/list.c
@@ -0,0 +1,224 @@
+#include "list.h"
+
+void
+list_init(struct list *list)
+{
+ LIST_ABORT_ON_ARGS(!list);
+
+ list->head.prev = NULL;
+ list->head.next = &list->tail;
+ list->tail.prev = &list->head;
+ list->tail.next = NULL;
+}
+
+void
+list_clear(struct list *list)
+{
+ LIST_ABORT_ON_ARGS(!list);
+
+ while (!list_empty(list))
+ list_pop_back(list);
+}
+
+void
+list_free_items(struct list *list, list_item_free_fn free_item, size_t offset)
+{
+ struct list_link *item;
+
+ LIST_ABORT_ON_ARGS(!list || !free_item);
+
+ while (!list_empty(list)) {
+ item = list_link_pop(list->head.next);
+ free_item(((void *) item) - offset);
+ }
+}
+
+size_t
+list_len(const struct list *list)
+{
+ const struct list_link *link;
+ size_t len;
+
+ LIST_ABORT_ON_ARGS(!list);
+
+ len = 0;
+ for (LIST_ITER(list, link))
+ len += 1;
+
+ return len;
+}
+
+ssize_t
+list_index(const struct list *list, const struct list_link *target)
+{
+ struct list_link *link;
+ ssize_t index;
+
+ LIST_ABORT_ON_ARGS(!list || !target);
+
+ index = 0;
+ for (LIST_ITER(list, link)) {
+ if (link == target)
+ return index;
+ index++;
+ }
+
+ return -1;
+}
+
+struct list_link *
+list_at(struct list *list, size_t n)
+{
+ struct list_link *link;
+
+ LIST_ABORT_ON_ARGS(!list);
+
+ link = list_iter_fwd(list->head.next, n);
+
+ return LIST_INNER(link) ? link : NULL;
+}
+
+struct list_link *
+list_at_back(struct list *list, size_t n)
+{
+ struct list_link *link;
+
+ LIST_ABORT_ON_ARGS(!list);
+
+ link = list_iter_bwd(&list->tail, n);
+
+ return LIST_INNER(link) ? link : NULL;
+}
+
+void
+list_insert_sorted(struct list *list, struct list_link *insert,
+ bool reverse, list_sort_order_fn in_order, size_t offset, void *user)
+{
+ struct list_link *link;
+ void *link_item, *insert_item;
+
+ LIST_ABORT_ON_ARGS(!list || !insert || !in_order);
+
+ insert_item = ((void *) insert) - offset;
+ for (LIST_ITER(list, link)) {
+ link_item = ((void *) link) - offset;
+ if (in_order(insert_item, link_item, user) == !reverse) {
+ list_link_prepend(link, insert);
+ return;
+ }
+ }
+
+ list_insert_back(list, insert);
+}
+
+void
+list_insert_sorted_bwd(struct list *list, struct list_link *insert,
+ bool reverse, list_sort_order_fn in_order, size_t offset, void *user)
+{
+ struct list_link *link;
+ void *link_item, *insert_item;
+
+ LIST_ABORT_ON_ARGS(!list || !insert || !in_order);
+
+ insert_item = ((void *) insert) - offset;
+ for (LIST_ITER_BWD(list, link)) {
+ link_item = ((void *) link) - offset;
+ if (in_order(link_item, insert_item, user) == !reverse) {
+ list_link_append(link, insert);
+ return;
+ }
+ }
+
+ list_insert_front(list, insert);
+}
+
+void
+list_insertion_sort(struct list *list, bool reverse,
+ list_sort_order_fn in_order, size_t offset, void *user)
+{
+ struct list_link *link, *cmp, *next;
+ void *link_item, *cmp_item;
+
+ LIST_ABORT_ON_ARGS(!list || !in_order);
+
+ link = list->head.next;
+ while (LIST_INNER(link)) {
+ next = link->next;
+ cmp = link->prev;
+ link_item = ((void *) link) - offset;
+ while (LIST_INNER(cmp)) {
+ cmp_item = ((void *) cmp) - offset;
+ if (in_order(cmp_item, link_item, user) == !reverse)
+ break;
+ cmp = cmp->prev;
+ }
+ if (cmp != link->prev)
+ list_link_append(cmp, list_link_pop(link));
+ link = next;
+ }
+}
+
+struct list_link *
+list_pop_front(struct list *list)
+{
+ LIST_ABORT_ON_ARGS(!list);
+
+ if (list_empty(list)) return NULL;
+
+ return list_link_pop(list->head.next);
+}
+
+struct list_link *
+list_pop_back(struct list *list)
+{
+ LIST_ABORT_ON_ARGS(!list);
+
+ if (list_empty(list)) return NULL;
+
+ return list_link_pop(list->tail.prev);
+}
+
+struct list_link *
+list_link_pop(struct list_link *link)
+{
+ LIST_ABORT_ON_ARGS(!link);
+
+ if (link->prev)
+ link->prev->next = link->next;
+ if (link->next)
+ link->next->prev = link->prev;
+ *link = LIST_LINK_INIT;
+
+ return link;
+}
+
+struct list_link *
+list_iter_fwd(struct list_link *link, size_t n)
+{
+ size_t i;
+
+ LIST_ABORT_ON_ARGS(!link);
+
+ for (i = 0; i < n; i++) {
+ if (!link) return NULL;
+ link = link->next;
+ }
+
+ return link;
+}
+
+struct list_link *
+list_iter_bwd(struct list_link *link, size_t n)
+{
+ size_t i;
+
+ LIST_ABORT_ON_ARGS(!link);
+
+ for (i = 0; i < n; i++) {
+ if (!link) return NULL;
+ link = link->prev;
+ }
+
+ return link;
+}
+
diff --git a/src/test.c b/src/test.c
@@ -0,0 +1,50 @@
+#include "list.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+struct arg {
+ const char *str;
+
+ struct list_link link;
+};
+
+bool
+test_sort(const void *p1, const void *p2, void *u)
+{
+ const struct arg *a1 = p1, *a2 = p2;
+
+ return strcmp(a1->str, a2->str) <= 0;
+}
+
+int
+main(int argc, const char **argv)
+{
+ struct list list;
+ struct arg *item;
+ const char **arg;
+
+ list_init(&list);
+
+ if (argc < 3) {
+ fprintf(stderr, "Usage: test REVERSE [STR]..\n");
+ return 1;
+ }
+
+ for (arg = argv + 2; *arg; arg++) {
+ item = malloc(sizeof(struct arg));
+ if (!item) return 0;
+ item->str = *arg;
+ item->link = LIST_LINK_INIT;
+ list_insert_back(&list, &item->link);
+ }
+
+ list_insertion_sort(&list, atoi(argv[1]), test_sort,
+ LIST_OFFSET(struct arg, link), NULL);
+
+ for (LIST_ITER_ITEMS(&list, item, struct arg, link))
+ printf("%s\n", item->str);
+
+ list_free_items(&list, free, LIST_OFFSET(struct arg, link));
+}
