commit 1e83ca9427fbb138580bd7ff72bf3f6165df46a8
parent c42a7ded56a2f00b885aac12da425b52f4b4927c
Author: Louis Burda <quent.burda@gmail.com>
Date: Fri, 26 May 2023 03:25:12 +0200
Add more utility macros and upcast internally for sort funcs
Diffstat:
5 files changed, 74 insertions(+), 25 deletions(-)
diff --git a/include/list.h b/include/list.h
@@ -1,7 +1,7 @@
#pragma once
-#include <stdbool.h>
#include <sys/types.h>
+#include <stdbool.h>
#include <stddef.h>
#define LIST_LINK_INIT ((struct list_link) { 0 })
@@ -18,13 +18,39 @@
#define LIST_ITER_BWD(list, iter) (iter) = (list)->tail.prev; \
(iter) != &(list)->head; (iter) = (iter)->prev
+#define LIST_ITER_ITEMS(list, iter, item, type, member) \
+ (iter) = (list)->head.next; \
+ (iter) != &(list)->tail \
+ && ((item) = LIST_UPCAST(iter, type, member)); \
+ (iter) = (iter)->next
+#define LIST_ITER_ITEMS_BWD(list, iter, item, type, member) \
+ (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_link_free_func)(void *p);
+typedef void (*list_item_free_fn)(void *p);
+typedef bool (*list_sort_order_fn)(const void *p1, const void *p2);
struct list_link {
struct list_link *prev;
@@ -39,7 +65,7 @@ struct list {
void list_init(struct list *list);
void list_clear(struct list *list);
void list_free_items(struct list *list,
- list_link_free_func free_item, size_t offset);
+ 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);
@@ -51,10 +77,12 @@ 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,
- bool (*in_order)(const struct list_link *a, const struct list_link *b));
-void list_insertion_sort(struct list *list, bool reverse,
- bool (*in_order)(const struct list_link *a, const struct list_link *b));
+void list_insert_sorted(struct list *list, struct list_link *link,
+ bool reverse, list_sort_order_fn in_order, size_t offset);
+void list_insert_sorted_bwd(struct list *list, struct list_link *link,
+ bool reverse, list_sort_order_fn in_order, size_t offset);
+void list_insertion_sort(struct list *list,
+ bool reverse, list_sort_order_fn in_order, size_t offset);
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);
diff --git a/liblist.api b/liblist.api
@@ -6,6 +6,7 @@ list_len
list_index
list_insert_sorted
+list_insert_sorted_bwd
list_insertion_sort
list_at
diff --git a/liblist.lds b/liblist.lds
@@ -1,4 +1,4 @@
-LIBLIST_1.1 {
+LIBLIST_1.2 {
list_init;
list_clear;
list_free_items;
@@ -7,6 +7,7 @@ LIBLIST_1.1 {
list_index;
list_insert_sorted;
+ list_insert_sorted_bwd;
list_insertion_sort;
list_at;
diff --git a/src/list.c b/src/list.c
@@ -21,8 +21,7 @@ list_clear(struct list *list)
}
void
-list_free_items(struct list *list,
- list_link_free_func free_item, size_t offset)
+list_free_items(struct list *list, list_item_free_fn free_item, size_t offset)
{
struct list_link *item;
@@ -92,8 +91,8 @@ list_at_back(struct list *list, size_t n)
}
void
-list_insert_sorted(struct list *list, struct list_link *insert, bool reverse,
- bool (*in_order)(const struct list_link *a, const struct list_link *b))
+list_insert_sorted(struct list *list, struct list_link *insert,
+ bool reverse, list_sort_order_fn in_order, size_t offset)
{
struct list_link *link;
@@ -110,10 +109,32 @@ list_insert_sorted(struct list *list, struct list_link *insert, bool reverse,
}
void
-list_insertion_sort(struct list *list, bool reverse,
- bool (*in_order)(const struct list_link *a, const struct list_link *b))
+list_insert_sorted_bwd(struct list *list, struct list_link *insert,
+ bool reverse, list_sort_order_fn in_order, size_t offset)
+{
+ 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, insert) == !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)
{
struct list_link *link, *cmp, *next;
+ void *link_item, *cmp_item;
LIST_ABORT_ON_ARGS(!list || !in_order);
@@ -121,8 +142,10 @@ list_insertion_sort(struct list *list, bool reverse,
while (LIST_INNER(link)) {
next = link->next;
cmp = link->prev;
+ link_item = ((void *) link) - offset;
while (LIST_INNER(cmp)) {
- if (in_order(cmp, link) == !reverse)
+ cmp_item = ((void *) cmp) - offset;
+ if (in_order(cmp_item, link_item) == !reverse)
break;
cmp = cmp->prev;
}
diff --git a/src/test.c b/src/test.c
@@ -11,14 +11,11 @@ struct arg {
};
bool
-test_sort(const struct list_link *link1, const struct list_link *link2)
+test_sort(const void *p1, const void *p2)
{
- const struct arg *arg1, *arg2;
+ const struct arg *a1 = p1, *a2 = p2;
- arg1 = LIST_UPCAST(link1, struct arg, link);
- arg2 = LIST_UPCAST(link2, struct arg, link);
-
- return strcmp(arg1->str, arg2->str) <= 0;
+ return strcmp(a1->str, a2->str) <= 0;
}
int
@@ -44,12 +41,11 @@ main(int argc, const char **argv)
list_insert_back(&list, &item->link);
}
- list_insertion_sort(&list, atoi(argv[1]), test_sort);
+ list_insertion_sort(&list, atoi(argv[1]), test_sort,
+ LIST_OFFSET(struct arg, link));
- for (LIST_ITER(&list, iter)) {
- item = LIST_UPCAST(iter, struct arg, link);
+ for (LIST_ITER_ITEMS(&list, iter, item, struct arg, link))
printf("%s\n", item->str);
- }
list_free_items(&list, free, LIST_OFFSET(struct arg, link));
}