diff options
author | Martin Poirier <theeth@yahoo.com> | 2007-11-02 00:44:41 +0300 |
---|---|---|
committer | Martin Poirier <theeth@yahoo.com> | 2007-11-02 00:44:41 +0300 |
commit | c3cc13e71b1d833ba40af4b290e995893c0163d4 (patch) | |
tree | 6bb6a8cb16717d03559df9ac6e937206a0efae79 | |
parent | 0ca5c98f2383b38bb3aa49e37be3f76074b0ca34 (diff) |
== 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).
-rw-r--r-- | source/blender/blenlib/BLI_blenlib.h | 2 | ||||
-rw-r--r-- | source/blender/blenlib/intern/util.c | 70 |
2 files changed, 72 insertions, 0 deletions
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; |