From c3cc13e71b1d833ba40af4b290e995893c0163d4 Mon Sep 17 00:00:00 2001
From: Martin Poirier <theeth@yahoo.com>
Date: Thu, 1 Nov 2007 21:44:41 +0000
Subject: == utils ==

New listbase functions:
	void BLI_insertlinkafter(struct ListBase *listbase, void *vprevlink, void *vnewlink);
		- corrolary to insertlinkbefore

	BLI_sortlist(struct ListBase *listbase, int (*cmp)(void *, void *));
		- simple in place sorting method. NOT optimized, so use for small lists only. Uses a variant of insertion sort (I was lazy, people should feel free to rewrite).
---
 source/blender/blenlib/BLI_blenlib.h |  2 ++
 source/blender/blenlib/intern/util.c | 70 ++++++++++++++++++++++++++++++++++++
 2 files changed, 72 insertions(+)

(limited to 'source/blender/blenlib')

diff --git a/source/blender/blenlib/BLI_blenlib.h b/source/blender/blenlib/BLI_blenlib.h
index 3306be76c47..57248fb1d68 100644
--- a/source/blender/blenlib/BLI_blenlib.h
+++ b/source/blender/blenlib/BLI_blenlib.h
@@ -112,6 +112,8 @@ int BLI_stringdec(char *string, char *kop, char *start, unsigned short *numlen);
 void BLI_stringenc(char *string, char *kop, char *start, unsigned short numlen, int pic);
 void BLI_addhead(struct ListBase *listbase, void *vlink);
 void BLI_insertlinkbefore(struct ListBase *listbase, void *vnextlink, void *vnewlink);
+void BLI_insertlinkafter(struct ListBase *listbase, void *vprevlink, void *vnewlink);
+void BLI_sortlist(struct ListBase *listbase, int (*cmp)(void *, void *));
 void BLI_freelist(struct ListBase *listbase);
 int BLI_countlist(struct ListBase *listbase);
 void BLI_freelinkN(ListBase *listbase, void *vlink);
diff --git a/source/blender/blenlib/intern/util.c b/source/blender/blenlib/intern/util.c
index f5ba3c34b18..8e396eec09d 100644
--- a/source/blender/blenlib/intern/util.c
+++ b/source/blender/blenlib/intern/util.c
@@ -312,6 +312,76 @@ void BLI_insertlink(ListBase *listbase, void *vprevlink, void *vnewlink)
 	newlink->prev= prevlink;
 }
 
+/* This uses insertion sort, so NOT ok for large list */
+void BLI_sortlist(ListBase *listbase, int (*cmp)(void *, void *))
+{
+	Link *current = NULL;
+	Link *previous = NULL;
+	Link *next = NULL;
+	
+	if (cmp == NULL) return;
+	if (listbase == NULL) return;
+
+	if (listbase->first != listbase->last)
+	{
+		for( previous = listbase->first, current = previous->next; current; previous = current, current = next )
+		{
+			next = current->next;
+			
+			BLI_remlink(listbase, current);
+			
+			while(previous && cmp(previous, current) == 1)
+			{
+				previous = previous->prev;
+			}
+			
+			if (previous == NULL)
+			{
+				BLI_addhead(listbase, current);
+			}
+			else
+			{
+				BLI_insertlinkafter(listbase, previous, current);
+			}
+		}
+	}
+}
+
+void BLI_insertlinkafter(ListBase *listbase, void *vprevlink, void *vnewlink)
+{
+	Link *prevlink= vprevlink;
+	Link *newlink= vnewlink;
+
+	/* newlink before nextlink */
+	if (newlink == NULL) return;
+	if (listbase == NULL) return;
+
+	/* empty list */
+	if (listbase->first == NULL) { 
+		listbase->first= newlink;
+		listbase->last= newlink;
+		return;
+	}
+	
+	/* insert at head of list */
+	if (prevlink == NULL) {	
+		newlink->prev = NULL;
+		newlink->next = listbase->first;
+		((Link *)listbase->first)->prev = newlink;
+		listbase->first = newlink;
+		return;
+	}
+
+	/* at end of list */
+	if (listbase->last == prevlink) 
+		listbase->last = newlink;
+
+	newlink->next = prevlink->next;
+	newlink->prev = prevlink;
+	prevlink->next = newlink;
+	if (newlink->next) newlink->next->prev = newlink;
+}
+
 void BLI_insertlinkbefore(ListBase *listbase, void *vnextlink, void *vnewlink)
 {
 	Link *nextlink= vnextlink;
-- 
cgit v1.2.3