diff options
Diffstat (limited to 'source/blender/blenlib/intern/BLI_linklist.c')
-rw-r--r-- | source/blender/blenlib/intern/BLI_linklist.c | 152 |
1 files changed, 132 insertions, 20 deletions
diff --git a/source/blender/blenlib/intern/BLI_linklist.c b/source/blender/blenlib/intern/BLI_linklist.c index a0b61e7945c..1da39967945 100644 --- a/source/blender/blenlib/intern/BLI_linklist.c +++ b/source/blender/blenlib/intern/BLI_linklist.c @@ -30,13 +30,18 @@ * \ingroup bli */ +#include <stdlib.h> #include "MEM_guardedalloc.h" + +#include "BLI_utildefines.h" #include "BLI_linklist.h" #include "BLI_memarena.h" #include "BLI_mempool.h" -int BLI_linklist_length(LinkNode *list) +#include "BLI_strict_flags.h" + +int BLI_linklist_count(LinkNode *list) { int len; @@ -85,6 +90,77 @@ void BLI_linklist_reverse(LinkNode **listp) } /** + * Move an item from its current position to a new one inside a single-linked list. + * Note *listp may be modified. + */ +void BLI_linklist_move_item(LinkNode **listp, int curr_index, int new_index) +{ + LinkNode *lnk, *lnk_psrc = NULL, *lnk_pdst = NULL; + int i; + + if (new_index == curr_index) { + return; + } + + if (new_index < curr_index) { + for (lnk = *listp, i = 0; lnk; lnk = lnk->next, i++) { + if (i == new_index - 1) { + lnk_pdst = lnk; + } + else if (i == curr_index - 1) { + lnk_psrc = lnk; + break; + } + } + + if (!(lnk_psrc && lnk_psrc->next && (!lnk_pdst || lnk_pdst->next))) { + /* Invalid indices, abort. */ + return; + } + + lnk = lnk_psrc->next; + lnk_psrc->next = lnk->next; + if (lnk_pdst) { + lnk->next = lnk_pdst->next; + lnk_pdst->next = lnk; + } + else { + /* destination is first element of the list... */ + lnk->next = *listp; + *listp = lnk; + } + } + else { + for (lnk = *listp, i = 0; lnk; lnk = lnk->next, i++) { + if (i == new_index) { + lnk_pdst = lnk; + break; + } + else if (i == curr_index - 1) { + lnk_psrc = lnk; + } + } + + if (!(lnk_pdst && (!lnk_psrc || lnk_psrc->next))) { + /* Invalid indices, abort. */ + return; + } + + if (lnk_psrc) { + lnk = lnk_psrc->next; + lnk_psrc->next = lnk->next; + } + else { + /* source is first element of the list... */ + lnk = *listp; + *listp = lnk->next; + } + lnk->next = lnk_pdst->next; + lnk_pdst->next = lnk; + } +} + +/** * A version of prepend that takes the allocated link. */ void BLI_linklist_prepend_nlink(LinkNode **listp, void *ptr, LinkNode *nlink) @@ -96,7 +172,7 @@ void BLI_linklist_prepend_nlink(LinkNode **listp, void *ptr, LinkNode *nlink) void BLI_linklist_prepend(LinkNode **listp, void *ptr) { - LinkNode *nlink = MEM_mallocN(sizeof(*nlink), "nlink"); + LinkNode *nlink = MEM_mallocN(sizeof(*nlink), __func__); BLI_linklist_prepend_nlink(listp, ptr, nlink); } @@ -115,40 +191,39 @@ void BLI_linklist_prepend_pool(LinkNode **listp, void *ptr, BLI_mempool *mempool /** * A version of append that takes the allocated link. */ -void BLI_linklist_append_nlink(LinkNode **listp, void *ptr, LinkNode *nlink) +void BLI_linklist_append_nlink(LinkNodePair *list_pair, void *ptr, LinkNode *nlink) { - LinkNode *node = *listp; - nlink->link = ptr; nlink->next = NULL; - if (node == NULL) { - *listp = nlink; + if (list_pair->list) { + BLI_assert((list_pair->last_node != NULL) && (list_pair->last_node->next == NULL)); + list_pair->last_node->next = nlink; } else { - while (node->next != NULL) { - node = node->next; - } - node->next = nlink; + BLI_assert(list_pair->last_node == NULL); + list_pair->list = nlink; } + + list_pair->last_node = nlink; } -void BLI_linklist_append(LinkNode **listp, void *ptr) +void BLI_linklist_append(LinkNodePair *list_pair, void *ptr) { - LinkNode *nlink = MEM_mallocN(sizeof(*nlink), "nlink"); - BLI_linklist_append_nlink(listp, ptr, nlink); + LinkNode *nlink = MEM_mallocN(sizeof(*nlink), __func__); + BLI_linklist_append_nlink(list_pair, ptr, nlink); } -void BLI_linklist_append_arena(LinkNode **listp, void *ptr, MemArena *ma) +void BLI_linklist_append_arena(LinkNodePair *list_pair, void *ptr, MemArena *ma) { LinkNode *nlink = BLI_memarena_alloc(ma, sizeof(*nlink)); - BLI_linklist_append_nlink(listp, ptr, nlink); + BLI_linklist_append_nlink(list_pair, ptr, nlink); } -void BLI_linklist_append_pool(LinkNode **listp, void *ptr, BLI_mempool *mempool) +void BLI_linklist_append_pool(LinkNodePair *list_pair, void *ptr, BLI_mempool *mempool) { LinkNode *nlink = BLI_mempool_alloc(mempool); - BLI_linklist_append_nlink(listp, ptr, nlink); + BLI_linklist_append_nlink(list_pair, ptr, nlink); } void *BLI_linklist_pop(struct LinkNode **listp) @@ -157,7 +232,7 @@ void *BLI_linklist_pop(struct LinkNode **listp) void *link = (*listp)->link; void *next = (*listp)->next; - MEM_freeN((*listp)); + MEM_freeN(*listp); *listp = next; return link; @@ -177,7 +252,7 @@ void *BLI_linklist_pop_pool(struct LinkNode **listp, struct BLI_mempool *mempool void BLI_linklist_insert_after(LinkNode **listp, void *ptr) { - LinkNode *nlink = MEM_mallocN(sizeof(*nlink), "nlink"); + LinkNode *nlink = MEM_mallocN(sizeof(*nlink), __func__); LinkNode *node = *listp; nlink->link = ptr; @@ -235,3 +310,40 @@ void BLI_linklist_apply(LinkNode *list, LinkNodeApplyFP applyfunc, void *userdat for (; list; list = list->next) applyfunc(list->link, userdata); } + +/* -------------------------------------------------------------------- */ +/* Sort */ +#define SORT_IMPL_LINKTYPE LinkNode +#define SORT_IMPL_LINKTYPE_DATA link + +/* regular call */ +#define SORT_IMPL_FUNC linklist_sort_fn +#include "list_sort_impl.h" +#undef SORT_IMPL_FUNC + +/* reentrant call */ +#define SORT_IMPL_USE_THUNK +#define SORT_IMPL_FUNC linklist_sort_fn_r +#include "list_sort_impl.h" +#undef SORT_IMPL_FUNC +#undef SORT_IMPL_USE_THUNK + +#undef SORT_IMPL_LINKTYPE +#undef SORT_IMPL_LINKTYPE_DATA + + +LinkNode *BLI_linklist_sort(LinkNode *list, int (*cmp)(const void *, const void *)) +{ + if (list && list->next) { + list = linklist_sort_fn(list, cmp); + } + return list; +} + +LinkNode *BLI_linklist_sort_r(LinkNode *list, int (*cmp)(void *, const void *, const void *), void *thunk) +{ + if (list && list->next) { + list = linklist_sort_fn_r(list, cmp, thunk); + } + return list; +} |