commit d7590f411fed9f98cae458162c28568761b8fb95
parent f92b7a2e1ac819ed3291b834dbf1b6a008c2873d
Author: Louis Burda <quent.burda@gmail.com>
Date: Wed, 2 Mar 2022 19:42:17 +0100
Simplified sorting interface
Diffstat:
4 files changed, 22 insertions(+), 20 deletions(-)
diff --git a/include/list.h b/include/list.h
@@ -37,10 +37,10 @@ void list_clear(struct list *list);
bool list_empty(struct list *list);
size_t list_len(struct list *list);
-void list_insert_sorted(struct list *list, struct link *link,
- int (*compare)(struct link *a, struct link *b));
-void list_sort(struct list *list,
- int (*compare)(struct link *a, struct link *b));
+void list_insert_sorted(struct list *list, struct link *link, bool ascending,
+ bool (*in_order)(struct link *a, struct link *b));
+void list_sort(struct list *list, bool ascending,
+ bool (*in_order)(struct link *a, struct link *b));
int list_index(struct list *list, struct link *link);
diff --git a/include/test.h b/include/test.h
diff --git a/src/list.c b/src/list.c
@@ -111,18 +111,18 @@ list_len(struct list *list)
}
void
-list_insert_sorted(struct list *list, struct link *insert,
- int (*compare)(struct link *a, struct link *b))
+list_insert_sorted(struct list *list, struct link *insert, bool ascending,
+ bool (*in_order)(struct link *a, struct link *b))
{
struct link *link;
- ASSERT(list != NULL && insert != NULL && compare != NULL);
+ ASSERT(list != NULL && insert != NULL && in_order != NULL);
/* Simple Insertion Sort */
/* cmp(a,b) -> (a-b) */
for (LIST_ITER(list, link)) {
- if (compare(link, insert) >= 0) {
+ if (ascending == in_order(insert, link)) {
link_prepend(link, insert);
return;
}
@@ -132,26 +132,25 @@ list_insert_sorted(struct list *list, struct link *insert,
}
void
-list_sort(struct list *list, int (*compare)(struct link *a, struct link *b))
+list_sort(struct list *list, bool ascending,
+ bool (*in_order)(struct link *a, struct link *b))
{
struct link *link, *cmp, *next;
- ASSERT(list != NULL && compare != NULL);
-
- /* Simple Insertion Sort */
- /* cmp(a,b) -> (a-b) */
+ ASSERT(list != NULL && in_order != NULL);
+ /* Insertion Sort */
link = list->head.next;
while (LIST_INNER(link)) {
next = link->next;
cmp = link->prev;
while (LIST_INNER(cmp)) {
- if (compare(cmp, link) < 0) {
- link_append(cmp, link_pop(link));
+ if (ascending == in_order(cmp, link))
break;
- }
cmp = cmp->prev;
}
+ if (cmp != link->prev)
+ link_append(cmp, link_pop(link));
link = next;
}
}
diff --git a/src/test.c b/src/test.c
@@ -10,7 +10,7 @@ struct arg {
struct link link;
};
-int
+bool
test_sort(struct link *link1, struct link *link2)
{
struct arg *arg1, *arg2;
@@ -18,7 +18,7 @@ test_sort(struct link *link1, struct link *link2)
arg1 = LINK_UPCAST(link1, struct arg, link);
arg2 = LINK_UPCAST(link2, struct arg, link);
- return strcmp(arg1->str, arg2->str);
+ return strcmp(arg1->str, arg2->str) <= 0;
}
int
@@ -31,7 +31,10 @@ main(int argc, const char **argv)
list_init(&list);
- for (arg = argv; *arg; arg++) {
+ if (argc < 3)
+ return 1;
+
+ for (arg = &argv[2]; *arg; arg++) {
item = malloc(sizeof(struct arg));
if (!item) return 0;
item->str = *arg;
@@ -39,7 +42,7 @@ main(int argc, const char **argv)
list_push_back(&list, &item->link);
}
- list_sort(&list, test_sort);
+ list_sort(&list, atoi(argv[1]), test_sort);
for (LIST_ITER(&list, iter)) {
item = LINK_UPCAST(iter, struct arg, link);