Implement slist_insert_sorted and slist_find functions

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);