commit b1809aacf142d2acc9b95dad4d7611afab300fbd
parent 2e59d4b247f144e26bc3577776dba3c40f7fbf70
Author: Louis Burda <quent.burda@gmail.com>
Date: Mon, 21 Feb 2022 19:00:54 +0100
Added simple insertion sort and index functions
Diffstat:
5 files changed, 73 insertions(+), 4 deletions(-)
diff --git a/include/list.h b/include/list.h
@@ -29,11 +29,17 @@ struct list {
};
void list_init(struct list *list);
-void list_free(struct list *list, void (*free_item)(void *), int offset);
+void list_free(struct list *list,
+ void (*free_item)(void *), int offset);
bool list_empty(struct list *list);
size_t list_len(struct list *list);
+void list_sort(struct list *list,
+ int (*compare)(struct link *a, struct link *b));
+
+int list_index(struct list *list, struct link *link);
+
struct link *list_at(struct list *list, int n);
struct link *list_front(struct list *list);
struct link *list_back(struct list *list);
diff --git a/liblist.api b/liblist.api
@@ -4,6 +4,10 @@ list_free
list_empty
list_len
+list_sort
+
+list_index
+
list_at
list_front
list_back
diff --git a/liblist.lds b/liblist.lds
@@ -6,6 +6,10 @@ LIBLIST_1.0 {
list_empty;
list_len;
+ list_sort;
+
+ list_index;
+
list_at;
list_front;
list_back;
diff --git a/src/list.c b/src/list.c
@@ -87,18 +87,59 @@ list_empty(struct list *list)
size_t
list_len(struct list *list)
{
- struct link *iter;
- size_t len;
+ struct link *link;
+ int len;
ASSERT(list != NULL);
len = 0;
- for (LIST_ITER(list, iter))
+ for (LIST_ITER(list, link))
len += 1;
return len;
}
+void
+list_sort(struct list *list, int (*compare)(struct link *a, struct link *b))
+{
+ struct link *link, *cmp, *next;
+
+ ASSERT(list != NULL && cmp != NULL);
+
+ /* Simple Insertion Sort */
+ /* cmp(a,b) -> (a-b) */
+
+ 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));
+ break;
+ }
+ cmp = cmp->prev;
+ }
+ link = next;
+ }
+}
+
+int
+list_index(struct list *list, struct link *target)
+{
+ struct link *link;
+ int index;
+
+ index = 0;
+ for (LIST_ITER(list, link)) {
+ if (link == target)
+ return index;
+ index++;
+ }
+
+ return -1;
+}
+
struct link *
list_at(struct list *list, int n)
{
diff --git a/src/test.c b/src/test.c
@@ -2,6 +2,7 @@
#include <stdlib.h>
#include <stdio.h>
+#include <string.h>
struct arg {
const char *str;
@@ -10,6 +11,17 @@ struct arg {
};
int
+test_sort(struct link *link1, struct link *link2)
+{
+ struct arg *arg1, *arg2;
+
+ arg1 = LINK_UPCAST(link1, struct arg, link);
+ arg2 = LINK_UPCAST(link2, struct arg, link);
+
+ return strcmp(arg1->str, arg2->str);
+}
+
+int
main(int argc, const char **argv)
{
struct link *iter;
@@ -27,6 +39,8 @@ main(int argc, const char **argv)
list_push_back(&list, &item->link);
}
+ list_sort(&list, test_sort);
+
for (LIST_ITER(&list, iter)) {
item = LINK_UPCAST(iter, struct arg, link);
printf("%s\n", item->str);