diff options
author | Campbell Barton <ideasman42@gmail.com> | 2015-06-12 09:57:15 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2015-06-12 10:13:34 +0300 |
commit | 4ab47a767067a88cfc82ae2e2214178b90e0f544 (patch) | |
tree | 6082569575478f91345a21a9b0b17878909fef7e /source/blender/blenlib | |
parent | 5893a3445e8227689c2f10b958a79f5f6ec18d20 (diff) |
BLI_linklist, avoid full list search for append
For areas that require append, store the last node,
Previous behavior would too easily hide poorly performing code.
Also avoid (prepend, reverse) where possible.
Diffstat (limited to 'source/blender/blenlib')
-rw-r--r-- | source/blender/blenlib/BLI_linklist.h | 58 | ||||
-rw-r--r-- | source/blender/blenlib/intern/BLI_linklist.c | 32 | ||||
-rw-r--r-- | source/blender/blenlib/intern/storage.c | 8 |
3 files changed, 54 insertions, 44 deletions
diff --git a/source/blender/blenlib/BLI_linklist.h b/source/blender/blenlib/BLI_linklist.h index d0dc7fc7b2f..67cb30e8d17 100644 --- a/source/blender/blenlib/BLI_linklist.h +++ b/source/blender/blenlib/BLI_linklist.h @@ -35,47 +35,59 @@ * */ +#include "BLI_compiler_attrs.h" + struct MemArena; struct BLI_mempool; typedef void (*LinkNodeFreeFP)(void *link); typedef void (*LinkNodeApplyFP)(void *link, void *userdata); -struct LinkNode; typedef struct LinkNode { struct LinkNode *next; void *link; } LinkNode; -int BLI_linklist_length(struct LinkNode *list); -int BLI_linklist_index(struct LinkNode *list, void *ptr); +/** + * Use for append (single linked list, storing the last element). + * + * \note list manipulation functions don't operate on this struct. + * This is only to be used while appending. + */ +typedef struct LinkNodePair { + LinkNode *list, *last_node; +} LinkNodePair; + +int BLI_linklist_count(LinkNode *list) ATTR_WARN_UNUSED_RESULT; +int BLI_linklist_index(LinkNode *list, void *ptr) ATTR_WARN_UNUSED_RESULT; -struct LinkNode *BLI_linklist_find(struct LinkNode *list, int index); +LinkNode *BLI_linklist_find(LinkNode *list, int index) ATTR_WARN_UNUSED_RESULT; -void BLI_linklist_reverse(struct LinkNode **listp); +void BLI_linklist_reverse(LinkNode **listp) ATTR_NONNULL(1); -void BLI_linklist_move_item(struct LinkNode **listp, int curr_index, int new_index); +void BLI_linklist_move_item(LinkNode **listp, int curr_index, int new_index) ATTR_NONNULL(1); -void BLI_linklist_prepend_nlink(struct LinkNode **listp, void *ptr, struct LinkNode *nlink); -void BLI_linklist_prepend(struct LinkNode **listp, void *ptr); -void BLI_linklist_prepend_arena(struct LinkNode **listp, void *ptr, struct MemArena *ma); -void BLI_linklist_prepend_pool(struct LinkNode **listp, void *ptr, struct BLI_mempool *mempool); +void BLI_linklist_prepend_nlink(LinkNode **listp, void *ptr, LinkNode *nlink) ATTR_NONNULL(1, 3); +void BLI_linklist_prepend(LinkNode **listp, void *ptr) ATTR_NONNULL(1); +void BLI_linklist_prepend_arena(LinkNode **listp, void *ptr, struct MemArena *ma) ATTR_NONNULL(1, 3); +void BLI_linklist_prepend_pool(LinkNode **listp, void *ptr, struct BLI_mempool *mempool) ATTR_NONNULL(1, 3); -void BLI_linklist_append_nlink(LinkNode **listp, void *ptr, LinkNode *nlink); -void BLI_linklist_append(struct LinkNode **listp, void *ptr); -void BLI_linklist_append_arena(LinkNode **listp, void *ptr, struct MemArena *ma); -void BLI_linklist_append_pool(LinkNode **listp, void *ptr, struct BLI_mempool *mempool); +/* use LinkNodePair to avoid full search */ +void BLI_linklist_append_nlink(LinkNodePair *list_pair, void *ptr, LinkNode *nlink) ATTR_NONNULL(1, 3); +void BLI_linklist_append(LinkNodePair *list_pair, void *ptr) ATTR_NONNULL(1); +void BLI_linklist_append_arena(LinkNodePair *list_pair, void *ptr, struct MemArena *ma) ATTR_NONNULL(1, 3); +void BLI_linklist_append_pool(LinkNodePair *list_pair, void *ptr, struct BLI_mempool *mempool) ATTR_NONNULL(1, 3); -void *BLI_linklist_pop(struct LinkNode **listp); -void *BLI_linklist_pop_pool(struct LinkNode **listp, struct BLI_mempool *mempool); -void BLI_linklist_insert_after(struct LinkNode **listp, void *ptr); +void *BLI_linklist_pop(LinkNode **listp) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); +void *BLI_linklist_pop_pool(LinkNode **listp, struct BLI_mempool *mempool) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2); +void BLI_linklist_insert_after(LinkNode **listp, void *ptr) ATTR_NONNULL(1); -void BLI_linklist_free(struct LinkNode *list, LinkNodeFreeFP freefunc); -void BLI_linklist_freeN(struct LinkNode *list); -void BLI_linklist_free_pool(LinkNode *list, LinkNodeFreeFP freefunc, struct BLI_mempool *mempool); -void BLI_linklist_apply(struct LinkNode *list, LinkNodeApplyFP applyfunc, void *userdata); -struct LinkNode *BLI_linklist_sort(LinkNode *list, int (*cmp)(const void *, const void *)); -struct LinkNode *BLI_linklist_sort_r(LinkNode *list, int (*cmp)(void *, const void *, const void *), void *thunk); +void BLI_linklist_free(LinkNode *list, LinkNodeFreeFP freefunc); +void BLI_linklist_freeN(LinkNode *list); +void BLI_linklist_free_pool(LinkNode *list, LinkNodeFreeFP freefunc, struct BLI_mempool *mempool); +void BLI_linklist_apply(LinkNode *list, LinkNodeApplyFP applyfunc, void *userdata); +LinkNode *BLI_linklist_sort(LinkNode *list, int (*cmp)(const void *, const void *)) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(2); +LinkNode *BLI_linklist_sort_r(LinkNode *list, int (*cmp)(void *, const void *, const void *), void *thunk) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(2); #define BLI_linklist_prepend_alloca(listp, ptr) \ BLI_linklist_prepend_nlink(listp, ptr, alloca(sizeof(LinkNode))) diff --git a/source/blender/blenlib/intern/BLI_linklist.c b/source/blender/blenlib/intern/BLI_linklist.c index 394f6e3db8a..1da39967945 100644 --- a/source/blender/blenlib/intern/BLI_linklist.c +++ b/source/blender/blenlib/intern/BLI_linklist.c @@ -30,6 +30,7 @@ * \ingroup bli */ +#include <stdlib.h> #include "MEM_guardedalloc.h" @@ -40,7 +41,7 @@ #include "BLI_strict_flags.h" -int BLI_linklist_length(LinkNode *list) +int BLI_linklist_count(LinkNode *list) { int len; @@ -190,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), __func__); - BLI_linklist_append_nlink(listp, ptr, nlink); + 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) diff --git a/source/blender/blenlib/intern/storage.c b/source/blender/blenlib/intern/storage.c index 6394187d40a..7b7733dea37 100644 --- a/source/blender/blenlib/intern/storage.c +++ b/source/blender/blenlib/intern/storage.c @@ -286,7 +286,7 @@ bool BLI_is_file(const char *path) LinkNode *BLI_file_read_as_lines(const char *name) { FILE *fp = BLI_fopen(name, "r"); - LinkNode *lines = NULL; + LinkNodePair lines = {NULL, NULL}; char *buf; size_t size; @@ -315,7 +315,7 @@ LinkNode *BLI_file_read_as_lines(const char *name) if (i == size || buf[i] == '\n') { char *line = BLI_strdupn(&buf[last], i - last); - BLI_linklist_prepend(&lines, line); + BLI_linklist_append(&lines, line); /* faster to build singly-linked list in reverse order */ /* alternatively, could process buffer in reverse order so * list ends up right way round to start with */ @@ -328,9 +328,7 @@ LinkNode *BLI_file_read_as_lines(const char *name) fclose(fp); - /* get them the right way round */ - BLI_linklist_reverse(&lines); - return lines; + return lines.list; } /* |