== utils ==
authorMartin Poirier <theeth@yahoo.com>
Thu, 1 Nov 2007 21:44:41 +0000 (21:44 +0000)
committerMartin Poirier <theeth@yahoo.com>
Thu, 1 Nov 2007 21:44:41 +0000 (21:44 +0000)
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
source/blender/blenlib/intern/util.c

index 3306be76c47c31125b081ba6522259d3439852a3..57248fb1d68e8a2f28fcc9cb7b662afe41847830 100644 (file)
@@ -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);
index f5ba3c34b18aa5eeef68a536d7990d9269ac2ec3..8e396eec09da667bcfece543852daf6d9cd985d1 100644 (file)
@@ -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;