diff options
Diffstat (limited to 'common')
-rw-r--r-- | common/list.c | 90 | ||||
-rw-r--r-- | common/list.h | 4 |
2 files changed, 94 insertions, 0 deletions
diff --git a/common/list.c b/common/list.c index 579d9574..65d83295 100644 --- a/common/list.c +++ b/common/list.c @@ -100,6 +100,48 @@ struct slist *slist_insert_before(struct slist *list, struct slist *sibling, voi return list; } +struct slist *slist_insert_sorted(struct slist *list, void *data, cmp_func_t cmp_func) +{ + struct slist *tmp, *prev, *entry; + int cmp; + + entry = malloc(sizeof(struct slist)); + if (!entry) + return list; + + entry->data = data; + entry->next = NULL; + + if (!list) + return entry; + + prev = NULL; + tmp = list; + + cmp = cmp_func(data, tmp->data); + + while (tmp->next && cmp > 0) { + prev = tmp; + tmp = tmp->next; + + cmp = cmp_func(data, tmp->data); + } + + if (!tmp->next && cmp > 0) { + tmp->next = entry; + return list; + } + + if (prev) { + prev->next = entry; + entry->next = tmp; + return list; + } else { + entry->next = list; + return entry; + } +} + struct slist *slist_remove(struct slist *list, void *data) { struct slist *l, *next, *prev = NULL, *match = NULL; @@ -144,6 +186,54 @@ struct slist *slist_find(struct slist *list, const void *data, return NULL; } +static struct slist *slist_sort_merge(struct slist *l1, struct slist *l2, + cmp_func_t cmp_func) +{ + struct slist list, *l; + int cmp; + + l = &list; + + while (l1 && l2) { + cmp = cmp_func(l1->data, l2->data); + + if (cmp <= 0) { + l = l->next = l1; + l1 = l1->next; + } else { + l = l->next = l2; + l2 = l2->next; + } + } + + l->next = l1 ? l1 : l2; + + return list.next; +} + +struct slist *slist_sort(struct slist *list, cmp_func_t cmp_func) +{ + struct slist *l1, *l2; + + if (!list || !list->next) + return list; + + l1 = list; + l2 = list->next; + + while ((l2 = l2->next) != NULL) { + if ((l2 = l2->next) == NULL) + break; + l1 = l1->next; + } + + l2 = l1->next; + l1->next = NULL; + + return slist_sort_merge(slist_sort(list, cmp_func), + slist_sort(l2, cmp_func), cmp_func); +} + int slist_length(struct slist *list) { int len; diff --git a/common/list.h b/common/list.h index f6576429..9868a79a 100644 --- a/common/list.h +++ b/common/list.h @@ -39,11 +39,15 @@ struct slist *slist_prepend(struct slist *list, void *data); struct slist *slist_insert_before(struct slist *list, struct slist *sibling, void *data); +struct slist *slist_insert_sorted(struct slist *list, void *data, cmp_func_t cmp_func); + struct slist *slist_remove(struct slist *list, void *data); struct slist *slist_find(struct slist *list, const void *data, cmp_func_t cmp_func); +struct slist *slist_sort(struct slist *list, cmp_func_t cmp_func); + int slist_length(struct slist *list); void slist_foreach(struct slist *list, slist_func_t func, void *user_data); |