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/intern | |
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/intern')
-rw-r--r-- | source/blender/blenlib/intern/BLI_linklist.c | 32 | ||||
-rw-r--r-- | source/blender/blenlib/intern/storage.c | 8 |
2 files changed, 19 insertions, 21 deletions
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; } /* |