liblist-c

commit e7393433f3699126f4453d973129305300333581
Author: Louis Burda <quent.burda@gmail.com>
Date:   Sat, 12 Feb 2022 14:25:25 +0100

Core functionality

Diffstat:
A
.gitignore
 | 
5
+++++
A
Makefile
 | 
42
++++++++++++++++++++++++++++++++++++++++++
A
include/list.h
 | 
52
++++++++++++++++++++++++++++++++++++++++++++++++++++
A
liblist.abi
 | 
13
+++++++++++++
A
src/list.c
 | 
196
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
src/test.c
 | 
34
++++++++++++++++++++++++++++++++++

6 files changed, 342 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,5 @@
+compile_commands.json
+build
+.cache
+vgcore*
+test
diff --git a/Makefile b/Makefile
@@ -0,0 +1,42 @@
+CFLAGS = -I src -I include
+LDLIBS =
+DEPFLAGS = -MT $@ -MMD -MP -MF build/$*.d
+
+_SRCS = list.c
+SRCS = $(_SRCS:%=src/%)
+OBJS = $(_SRCS:%.c=build/%.o)
+DEPS = $(_SRCS:%.c=build/%.d)
+PI_OBJS = $(_SRCS:%.c=build/%.pi.o)
+
+.PHONY: all clean
+
+all: build/liblist.so build/liblist.a build/test
+
+clean:
+	rm -rf build
+
+build:
+	mkdir build
+
+build/%.o: src/%.c build/%.d | build
+	$(CC) -c -o $@ $< $(DEPFLAGS) $(CFLAGS)
+
+build/%.pi.o: src/%.c build/%.d | build
+	$(CC) -c -o $@ $< $(DEPFLAGS) $(CFLAGS) -fPIC
+
+build/%.d: | build;
+
+include $(DEPS)
+
+build/liblist.a: $(OBJS) | build
+	$(CC) -o build/tmp.o $(OBJS) $(CFLAGS) -r
+	objcopy --keep-global-symbols=liblist.abi build/tmp.o build/fixed.o
+	ar rcs $@ build/fixed.o
+
+build/liblist.so: $(PI_OBJS) | build
+	$(CC) -o build/tmp.so $(PI_OBJS) $(CFLAGS) -shared
+	objcopy --keep-global-symbols=liblist.abi build/tmp.so $@
+
+build/test: src/test.c build/liblist.a | build
+	$(CC) -o $@ $^ -I include
+
diff --git a/include/list.h b/include/list.h
@@ -0,0 +1,52 @@
+#pragma once
+
+#include <stdlib.h>
+
+#define LINK_OFFSET(type) ((size_t) &((type *)0)->link)
+#define UPCAST(ptr, type) ({ \
+	const typeof( ((type *)0)->link ) *__mptr = (ptr); \
+	(type *)( (char *)__mptr - LINK_OFFSET(type) ); })
+
+#define LINK_EMPTY ((struct link) { 0 })
+
+#define LINK(p) (&(p)->link)
+
+#define LIST_INNER(list, link) \
+	(((link) != &(list)->head) && ((link) != &(list)->tail))
+
+#define LIST_ITER(list, iter) (iter) = (list)->head.next; \
+	(iter) != &(list)->tail; (iter) = (iter)->next
+
+typedef void (*link_free_func)(void *p);
+
+struct link {
+	struct link *prev;
+	struct link *next;
+};
+
+struct list {
+	struct link head;
+	struct link tail;
+};
+
+void list_init(struct list *list);
+void list_free(struct list *list, void (*free_item)(void *), int offset);
+
+int list_empty(struct list *list);
+int list_len(struct list *list);
+
+struct link *list_at(struct list *list, int n);
+struct link *list_front(struct list *list);
+struct link *list_back(struct list *list);
+
+void list_push_front(struct list *list, struct link *link);
+void list_push_back(struct list *list, struct link *link);
+struct link *list_pop_front(struct list *list);
+struct link *list_pop_back(struct list *list);
+
+struct link *link_iter(struct link *link, int n);
+struct link *link_pop(struct link *link);
+
+void link_prepend(struct link *list, struct link *link);
+void link_append(struct link *list, struct link *link);
+
diff --git a/liblist.abi b/liblist.abi
@@ -0,0 +1,13 @@
+list_init
+list_free
+list_empty
+list_len
+list_at
+list_push_front
+list_push_back
+list_pop_front
+list_pop_back
+link_iter
+link_pop
+link_prepend
+link_append
diff --git a/src/list.c b/src/list.c
@@ -0,0 +1,196 @@
+#include "list.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+
+#define ASSERT(x) assert((x), __FILE__, __LINE__, #x)
+
+static void assert(int cond, const char *file, int line, const char *condstr);
+static struct link *link_iter_fwd(struct link *link, size_t n);
+static struct link *link_iter_bwd(struct link *link, size_t n);
+
+void
+assert(int cond, const char *file, int line, const char *condstr)
+{
+	if (cond) return;
+
+	fprintf(stderr, "CLIST: Assertion failed at %s:%i (%s)\n",
+		file, line, condstr);
+	exit(1);
+}
+
+struct link *
+link_iter_fwd(struct link *link, size_t n)
+{
+	int i;
+
+	for (i = 0; i < n; i++) {
+		if (!link) return NULL;
+		link = link->next;
+	}
+
+	return link;
+}
+
+struct link *
+link_iter_bwd(struct link *link, size_t n)
+{
+	int i;
+
+	for (i = 0; i < n; i++) {
+		if (!link) return NULL;
+		link = link->prev;
+	}
+
+	return link;
+}
+
+
+void
+list_init(struct list *list)
+{
+	list->head.prev = NULL;
+	list->head.next = &list->tail;
+	list->tail.prev = &list->head;
+	list->tail.next = NULL;
+}
+
+void
+list_free(struct list *list, void (*free_item)(void *), int offset)
+{
+	struct link *item;
+
+	ASSERT(list != NULL);
+
+	while (!list_empty(list)) {
+		item = link_pop(list->head.next);
+		free_item(((void *) item) - offset);
+	}
+}
+
+int
+list_empty(struct list *list)
+{
+	ASSERT(list != NULL);
+
+	return list->head.next == &list->tail;
+}
+
+int
+list_len(struct list *list)
+{
+	struct link *iter;
+	int len;
+
+	ASSERT(list != NULL);
+
+	len = 0;
+	for (LIST_ITER(list, iter))
+		len += 1;
+
+	return len;
+}
+
+struct link *
+list_at(struct list *list, int n)
+{
+	ASSERT(list != NULL);
+
+	return link_iter(list->head.next, n);
+}
+
+struct link *
+list_front(struct list *list)
+{
+	return list_at(list, 1);
+}
+
+struct link *
+list_back(struct list *list)
+{
+	return list_at(list, -1);
+}
+
+void
+list_push_front(struct list *list, struct link *link)
+{
+	link_append(&list->head, link);
+}
+
+void
+list_push_back(struct list *list, struct link *link)
+{
+	link_prepend(&list->tail, link);
+}
+
+struct link *
+list_pop_front(struct list *list)
+{
+	ASSERT(list != NULL);
+
+	if (list_empty(list))
+		return NULL;
+
+	return link_pop(list->head.next);
+}
+
+struct link *
+list_pop_back(struct list *list)
+{
+	ASSERT(list != NULL);
+
+	if (list_empty(list))
+		return NULL;
+
+	return link_pop(list->tail.prev);
+}
+
+void
+link_prepend(struct link *cur, struct link *link)
+{
+	ASSERT(cur != NULL && link != NULL);
+
+	link->prev = cur->prev;
+	link->next = cur;
+
+	if (link->prev)
+		link->prev->next = link;
+	if (link->next)
+		link->next->prev = link;
+}
+
+void
+link_append(struct link *cur, struct link *link)
+{
+	ASSERT(cur != NULL && link != NULL);
+
+	link->prev = cur;
+	link->next = cur->next;
+
+	if (link->prev)
+		link->prev->next = link;
+	if (link->next)
+		link->next->prev = link;
+}
+
+struct link *
+link_iter(struct link *link, int n)
+{
+	if (n >= 0)
+		return link_iter_fwd(link, n);
+	else
+		return link_iter_bwd(link, -n);
+}
+
+struct link *
+link_pop(struct link *link)
+{
+	ASSERT(link != NULL);
+
+	if (link->prev)
+		link->prev->next = link->next;
+	if (link->next)
+		link->next->prev = link->prev;
+
+	return link;
+}
diff --git a/src/test.c b/src/test.c
@@ -0,0 +1,34 @@
+#include "list.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+
+struct arg {
+	const char *str;
+
+	struct link link;
+};
+
+int
+main(int argc, const char **argv)
+{
+	struct link *iter;
+	struct list list;
+	struct arg *item;
+	const char **arg;
+
+	list_init(&list);
+
+	for (arg = argv; *arg; arg++) {
+		item = malloc(sizeof(struct arg));
+		if (!item) return 0;
+		item->str = *arg;
+		item->link = LINK_EMPTY;
+		list_push_back(&list, LINK(item));
+	}
+
+	for (LIST_ITER(&list, iter)) {
+		item = UPCAST(iter, struct arg);
+		printf("%s\n", item->str);
+	}
+}