commit ff57ed0d47a21614c0fd3f7f3be9d7a0233958e7
parent bddda5d756abc662f8ef124afef86b851249418d
Author: Louis Burda <quent.burda@gmail.com>
Date: Tue, 28 Mar 2023 00:05:34 +0200
Inline some functions, add -O2 optimization, make naming less collision prone
Diffstat:
M | Makefile | | | 16 | ++++++++++++---- |
M | include/list.h | | | 135 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------------------- |
M | liblist.api | | | 25 | +++++++++---------------- |
M | liblist.lds | | | 43 | +++++++++++++++++-------------------------- |
M | src/list.c | | | 272 | ++++++++++++++++++++++++++++++------------------------------------------------- |
M | src/test.c | | | 18 | ++++++++++-------- |
6 files changed, 251 insertions(+), 258 deletions(-)
diff --git a/Makefile b/Makefile
@@ -2,10 +2,18 @@ PREFIX ?= /usr/local
LIBDIR ?= /lib
INCLDIR ?= /include
-CFLAGS = -I src -I include
+CFLAGS = -I include
+CFLAGS += -Wunused-function -Wunused-variable -Wno-prototype
+CFLAGS += -Wconversion -Wsign-compare -Werror
ifeq "$(DEBUG)" "1"
-CFLAGS += -g -DLIBLIST_CHECK_ENABLE=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
@@ -16,12 +24,12 @@ clean:
build:
mkdir build
-build/liblist.a: src/list.c include/list.h | 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 | build
+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
diff --git a/include/list.h b/include/list.h
@@ -3,61 +3,126 @@
#include <stdbool.h>
#include <stdlib.h>
-#define LINK_OFFSET(type, member) ((size_t) &((type *)0)->member)
-#define LINK_UPCAST(ptr, type, member) ({ \
- const typeof( ((type *)0)->member ) *__mptr = (ptr); \
- (type *)( (char *)__mptr - LINK_OFFSET(type, member) ); })
+#define LIST_LINK_INIT ((struct list_link) { 0 })
-#define LINK_EMPTY ((struct link) { 0 })
+#define LIST_OFFSET(type, member) ((size_t) &((type *)0)->member)
+#define LIST_UPCAST(ptr, type, member) ({ \
+ const typeof( ((type *)0)->member ) *__mptr = (ptr); \
+ (type *)( (char *)__mptr - LIST_OFFSET(type, member) ); })
-#define LIST_INNER(link) \
- ((link) != NULL && (link)->prev != NULL && (link)->next != NULL)
+#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
+
+#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 (*link_free_func)(void *p);
+typedef void (*list_link_free_func)(void *p);
-struct link {
- struct link *prev;
- struct link *next;
+struct list_link {
+ struct list_link *prev;
+ struct list_link *next;
};
struct list {
- struct link head;
- struct link tail;
+ struct list_link head;
+ struct list_link tail;
};
void list_init(struct list *list);
-void list_free(struct list *list,
- void (*free_item)(void *), int offset);
-
void list_clear(struct list *list);
+void list_free_items(struct list *list,
+ list_link_free_func 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);
+
+void list_insert_sorted(struct list *list, struct list_link *link, bool reverse,
+ bool (*in_order)(struct list_link *a, struct list_link *b));
+void list_insertion_sort(struct list *list, bool reverse,
+ bool (*in_order)(struct list_link *a, struct list_link *b));
+
+struct list_link *list_at(struct list *list, size_t n);
+struct list_link *list_at_back(struct list *list, size_t n);
+
+static inline void list_push_front(struct list *list, struct list_link *link);
+static inline void list_push_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);
+
+void list_link_prepend(struct list_link *list, struct list_link *link);
+void list_link_append(struct list_link *list, 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;
+}
-bool list_empty(struct list *list);
-size_t list_len(struct list *list);
+static inline bool
+list_empty(const struct list *list)
+{
+ LIST_ABORT_ON_ARGS(!list);
-void list_insert_sorted(struct list *list, struct link *link, bool reverse,
- bool (*in_order)(struct link *a, struct link *b));
-void list_sort(struct list *list, bool reverse,
- bool (*in_order)(struct link *a, struct link *b));
+ return list->head.next == &list->tail;
+}
-int list_index(struct list *list, struct link *link);
+static inline bool
+list_link_inuse(const struct list_link *link)
+{
+ LIST_ABORT_ON_ARGS(!link);
-struct link *list_at(struct list *list, int n);
-struct link *list_front(struct list *list);
-struct link *list_back(struct list *list);
+ return link->prev && link->next;
+}
-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);
+static inline void
+list_push_front(struct list *list, struct list_link *link)
+{
+ LIST_ABORT_ON_ARGS(!list);
-struct link *link_iter(struct link *link, int n);
-struct link *link_pop(struct link *link);
+ list_link_append(&list->head, link);
+}
-bool link_inuse(struct link *link);
+static inline void
+list_push_back(struct list *list, struct list_link *link)
+{
+ LIST_ABORT_ON_ARGS(!list);
-void link_prepend(struct link *list, struct link *link);
-void link_append(struct link *list, struct link *link);
+ list_link_prepend(&list->tail, link);
+}
diff --git a/liblist.api b/liblist.api
@@ -1,29 +1,22 @@
list_init
-list_free
-
list_clear
+list_free_items
-list_empty
list_len
+list_index
list_insert_sorted
-list_sort
-
-list_index
+list_insertion_sort
list_at
-list_front
-list_back
+list_at_back
-list_push_front
-list_push_back
list_pop_front
list_pop_back
-link_inuse
-
-link_iter
-link_pop
+list_link_iter_fwd
+list_link_iter_bwd
+list_link_pop
-link_prepend
-link_append
+list_link_prepend
+list_link_append
diff --git a/liblist.lds b/liblist.lds
@@ -1,33 +1,24 @@
-LIBLIST_1.0 {
- global:
- list_init;
- list_free;
+LIBLIST_1.1 {
+ list_init;
+ list_clear;
+ list_free_items;
- list_clear;
+ list_len;
+ list_index;
- list_empty;
- list_len;
+ list_insert_sorted;
+ list_insertion_sort;
- list_insert_sorted;
- list_sort;
+ list_at;
+ list_at_back;
- list_index;
+ list_pop_front;
+ list_pop_back;
- list_at;
- list_front;
- list_back;
+ list_link_iter_fwd;
+ list_link_iter_bwd;
+ list_link_pop;
- list_push_front;
- list_push_back;
- list_pop_front;
- list_pop_back;
-
- link_inuse;
-
- link_iter;
- link_pop;
-
- link_prepend;
- link_append;
- local: *;
+ list_link_prepend;
+ list_link_append;
};
diff --git a/src/list.c b/src/list.c
@@ -1,62 +1,9 @@
#include "list.h"
-#include <stdbool.h>
-#include <stdlib.h>
-#include <stdio.h>
-
-#ifdef LIBLIST_CHECK_ENABLE
-#define LIBLIST_CHECK(x) liblist_assert((x), __FILE__, __LINE__, #x)
-#else
-#define LIBLIST_CHECK(x)
-#endif
-
-static struct link *link_iter_fwd(struct link *link, size_t n);
-static struct link *link_iter_bwd(struct link *link, size_t n);
-
-static inline void
-liblist_assert(int cond, const char *file, int line, const char *condstr)
-{
- if (cond) return;
-
- fprintf(stderr, "liblist: Assertion failed at %s:%i (%s)\n",
- file, line, condstr);
- abort();
-}
-
-struct link *
-link_iter_fwd(struct link *link, size_t n)
-{
- size_t i;
-
- LIBLIST_CHECK(link != NULL);
-
- 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)
-{
- size_t i;
-
- LIBLIST_CHECK(link != NULL);
-
- for (i = 0; i < n; i++) {
- if (!link) return NULL;
- link = link->prev;
- }
-
- return link;
-}
-
void
list_init(struct list *list)
{
- LIBLIST_CHECK(list != NULL);
+ LIST_ABORT_ON_ARGS(!list);
list->head.prev = NULL;
list->head.next = &list->tail;
@@ -65,42 +12,35 @@ list_init(struct list *list)
}
void
-list_free(struct list *list, void (*free_item)(void *), int offset)
-{
- struct link *item;
-
- LIBLIST_CHECK(list != NULL && free_item != NULL);
-
- while (!list_empty(list)) {
- item = link_pop(list->head.next);
- free_item(((void *) item) - offset);
- }
-}
-
-void
list_clear(struct list *list)
{
- LIBLIST_CHECK(list != NULL);
+ LIST_ABORT_ON_ARGS(!list);
while (!list_empty(list))
list_pop_back(list);
}
-bool
-list_empty(struct list *list)
+void
+list_free_items(struct list *list,
+ list_link_free_func free_item, size_t offset)
{
- LIBLIST_CHECK(list != NULL);
+ struct list_link *item;
+
+ LIST_ABORT_ON_ARGS(!list || !free_item);
- return list->head.next == &list->tail;
+ while (!list_empty(list)) {
+ item = list_link_pop(list->head.next);
+ free_item(((void *) item) - offset);
+ }
}
size_t
-list_len(struct list *list)
+list_len(const struct list *list)
{
- struct link *link;
+ const struct list_link *link;
size_t len;
- LIBLIST_CHECK(list != NULL);
+ LIST_ABORT_ON_ARGS(!list);
len = 0;
for (LIST_ITER(list, link))
@@ -109,20 +49,35 @@ list_len(struct list *list)
return len;
}
-void
-list_insert_sorted(struct list *list, struct link *insert, bool reverse,
- bool (*in_order)(struct link *a, struct link *b))
+ssize_t
+list_index(const struct list *list, const struct list_link *target)
{
- struct link *link;
+ 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++;
+ }
- LIBLIST_CHECK(list != NULL && insert != NULL && in_order != NULL);
+ return -1;
+}
+
+void
+list_insert_sorted(struct list *list, struct list_link *insert, bool reverse,
+ bool (*in_order)(struct list_link *a, struct list_link *b))
+{
+ struct list_link *link;
- /* Simple Insertion Sort */
- /* cmp(a,b) -> (a-b) */
+ LIST_ABORT_ON_ARGS(!list || !insert || !in_order);
for (LIST_ITER(list, link)) {
if (in_order(insert, link) == !reverse) {
- link_prepend(link, insert);
+ list_link_prepend(link, insert);
return;
}
}
@@ -131,14 +86,13 @@ list_insert_sorted(struct list *list, struct link *insert, bool reverse,
}
void
-list_sort(struct list *list, bool reverse,
- bool (*in_order)(struct link *a, struct link *b))
+list_insertion_sort(struct list *list, bool reverse,
+ bool (*in_order)(struct list_link *a, struct list_link *b))
{
- struct link *link, *cmp, *next;
+ struct list_link *link, *cmp, *next;
- LIBLIST_CHECK(list != NULL && in_order != NULL);
+ LIST_ABORT_ON_ARGS(!list || !in_order);
- /* Insertion Sort */
link = list->head.next;
while (LIST_INNER(link)) {
next = link->next;
@@ -149,92 +103,103 @@ list_sort(struct list *list, bool reverse,
cmp = cmp->prev;
}
if (cmp != link->prev)
- link_append(cmp, link_pop(link));
+ list_link_append(cmp, list_link_pop(link));
link = next;
}
}
-int
-list_index(struct list *list, struct link *target)
+struct list_link *
+list_at(struct list *list, size_t n)
{
- struct link *link;
- int index;
+ struct list_link *link;
- index = 0;
- for (LIST_ITER(list, link)) {
- if (link == target)
- return index;
- index++;
- }
+ LIST_ABORT_ON_ARGS(!list);
- return -1;
+ link = list_iter_fwd(list->head.next, n);
+
+ return LIST_INNER(link) ? link : NULL;
}
-struct link *
-list_at(struct list *list, int n)
+struct list_link *
+list_at_back(struct list *list, size_t n)
{
- struct link * link;
+ struct list_link *link;
- LIBLIST_CHECK(list != NULL);
+ LIST_ABORT_ON_ARGS(!list);
- if (n >= 0)
- link = link_iter_fwd(list->head.next, n);
- else
- link = link_iter_bwd(&list->tail, -n);
+ link = list_iter_bwd(&list->tail, n);
return LIST_INNER(link) ? link : NULL;
}
-struct link *
-list_front(struct list *list)
+struct list_link *
+list_pop_front(struct list *list)
{
- return list_at(list, 0);
-}
+ LIST_ABORT_ON_ARGS(!list);
-struct link *
-list_back(struct list *list)
-{
- return list_at(list, -1);
+ if (list_empty(list)) return NULL;
+
+ return list_link_pop(list->head.next);
}
-void
-list_push_front(struct list *list, struct link *link)
+struct list_link *
+list_pop_back(struct list *list)
{
- link_append(&list->head, link);
+ LIST_ABORT_ON_ARGS(!list);
+
+ if (list_empty(list)) return NULL;
+
+ return list_link_pop(list->tail.prev);
}
-void
-list_push_back(struct list *list, struct link *link)
+struct list_link *
+list_link_pop(struct list_link *link)
{
- link_prepend(&list->tail, 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 link *
-list_pop_front(struct list *list)
+struct list_link *
+list_iter_fwd(struct list_link *link, size_t n)
{
- LIBLIST_CHECK(list != NULL);
+ size_t i;
+
+ LIST_ABORT_ON_ARGS(!link);
- if (list_empty(list))
- return NULL;
+ for (i = 0; i < n; i++) {
+ if (!link) return NULL;
+ link = link->next;
+ }
- return link_pop(list->head.next);
+ return link;
}
-struct link *
-list_pop_back(struct list *list)
+struct list_link *
+list_iter_bwd(struct list_link *link, size_t n)
{
- LIBLIST_CHECK(list != NULL);
+ size_t i;
- if (list_empty(list))
- return NULL;
+ LIST_ABORT_ON_ARGS(!link);
- return link_pop(list->tail.prev);
+ for (i = 0; i < n; i++) {
+ if (!link) return NULL;
+ link = link->prev;
+ }
+
+ return link;
}
void
-link_prepend(struct link *cur, struct link *link)
+list_link_prepend(struct list_link *cur, struct list_link *link)
{
- LIBLIST_CHECK(cur != NULL && link != NULL);
+ LIST_ABORT_ON_ARGS(!cur || !link);
link->prev = cur->prev;
link->next = cur;
@@ -246,9 +211,9 @@ link_prepend(struct link *cur, struct link *link)
}
void
-link_append(struct link *cur, struct link *link)
+list_link_append(struct list_link *cur, struct list_link *link)
{
- LIBLIST_CHECK(cur != NULL && link != NULL);
+ LIST_ABORT_ON_ARGS(!cur || !link);
link->prev = cur;
link->next = cur->next;
@@ -258,34 +223,3 @@ link_append(struct link *cur, struct link *link)
if (link->next)
link->next->prev = link;
}
-
-bool
-link_inuse(struct link *link)
-{
- LIBLIST_CHECK(link != NULL);
-
- return link->prev != NULL && link->next != NULL;
-}
-
-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)
-{
- LIBLIST_CHECK(link != NULL);
-
- if (link->prev)
- link->prev->next = link->next;
- if (link->next)
- link->next->prev = link->prev;
- *link = LINK_EMPTY;
-
- return link;
-}
diff --git a/src/test.c b/src/test.c
@@ -7,16 +7,16 @@
struct arg {
const char *str;
- struct link link;
+ struct list_link link;
};
bool
-test_sort(struct link *link1, struct link *link2)
+test_sort(struct list_link *link1, struct list_link *link2)
{
struct arg *arg1, *arg2;
- arg1 = LINK_UPCAST(link1, struct arg, link);
- arg2 = LINK_UPCAST(link2, struct arg, link);
+ arg1 = LIST_UPCAST(link1, struct arg, link);
+ arg2 = LIST_UPCAST(link2, struct arg, link);
return strcmp(arg1->str, arg2->str) <= 0;
}
@@ -24,7 +24,7 @@ test_sort(struct link *link1, struct link *link2)
int
main(int argc, const char **argv)
{
- struct link *iter;
+ struct list_link *iter;
struct list list;
struct arg *item;
const char **arg;
@@ -40,14 +40,16 @@ main(int argc, const char **argv)
item = malloc(sizeof(struct arg));
if (!item) return 0;
item->str = *arg;
- item->link = LINK_EMPTY;
+ item->link = LIST_LINK_INIT;
list_push_back(&list, &item->link);
}
- list_sort(&list, atoi(argv[1]), test_sort);
+ list_insertion_sort(&list, atoi(argv[1]), test_sort);
for (LIST_ITER(&list, iter)) {
- item = LINK_UPCAST(iter, struct arg, link);
+ item = LIST_UPCAST(iter, struct arg, link);
printf("%s\n", item->str);
}
+
+ list_free_items(&list, free, LIST_OFFSET(struct arg, link));
}