From 4ab47a767067a88cfc82ae2e2214178b90e0f544 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Fri, 12 Jun 2015 16:57:15 +1000 Subject: 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. --- source/blender/blenkernel/intern/cloth.c | 22 ++++---- source/blender/blenlib/BLI_linklist.h | 58 +++++++++++++--------- source/blender/blenlib/intern/BLI_linklist.c | 32 ++++++------ source/blender/blenlib/intern/storage.c | 8 ++- source/blender/bmesh/tools/bmesh_region_match.c | 2 +- source/blender/collada/collada.cpp | 2 +- .../editors/sculpt_paint/paint_image_proj.c | 8 +-- source/blender/editors/space_file/filelist.c | 2 +- 8 files changed, 73 insertions(+), 61 deletions(-) (limited to 'source') diff --git a/source/blender/blenkernel/intern/cloth.c b/source/blender/blenkernel/intern/cloth.c index 3b3fe323f2b..e3ff96853b3 100644 --- a/source/blender/blenkernel/intern/cloth.c +++ b/source/blender/blenkernel/intern/cloth.c @@ -997,19 +997,19 @@ int cloth_add_spring(ClothModifierData *clmd, unsigned int indexA, unsigned int return 0; } -static void cloth_free_edgelist(LinkNode **edgelist, unsigned int numverts) +static void cloth_free_edgelist(LinkNodePair *edgelist, unsigned int numverts) { if (edgelist) { unsigned int i; for (i = 0; i < numverts; i++) { - BLI_linklist_free(edgelist[i], NULL); + BLI_linklist_free(edgelist[i].list, NULL); } MEM_freeN(edgelist); } } -static void cloth_free_errorsprings(Cloth *cloth, LinkNode **edgelist) +static void cloth_free_errorsprings(Cloth *cloth, LinkNodePair *edgelist) { if ( cloth->springs != NULL ) { LinkNode *search = cloth->springs; @@ -1260,7 +1260,7 @@ static int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm ) MEdge *medge = dm->getEdgeArray (dm); MFace *mface = dm->getTessFaceArray (dm); int index2 = 0; // our second vertex index - LinkNode **edgelist = NULL; + LinkNodePair *edgelist; EdgeSet *edgeset = NULL; LinkNode *search = NULL, *search2 = NULL; @@ -1276,7 +1276,7 @@ static int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm ) cloth->springs = NULL; cloth->edgeset = NULL; - edgelist = MEM_callocN ( sizeof (LinkNode *) * numverts, "cloth_edgelist_alloc" ); + edgelist = MEM_callocN(sizeof(*edgelist) * numverts, "cloth_edgelist_alloc" ); if (!edgelist) return 0; @@ -1347,8 +1347,9 @@ static int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm ) spring->type = CLOTH_SPRING_TYPE_SHEAR; spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0f; - BLI_linklist_append ( &edgelist[spring->ij], spring ); - BLI_linklist_append ( &edgelist[spring->kl], spring ); + BLI_linklist_append(&edgelist[spring->ij], spring); + BLI_linklist_append(&edgelist[spring->kl], spring); + shear_springs++; BLI_linklist_prepend ( &cloth->springs, spring ); @@ -1371,8 +1372,9 @@ static int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm ) spring->type = CLOTH_SPRING_TYPE_SHEAR; spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0f; - BLI_linklist_append ( &edgelist[spring->ij], spring ); - BLI_linklist_append ( &edgelist[spring->kl], spring ); + BLI_linklist_append(&edgelist[spring->ij], spring); + BLI_linklist_append(&edgelist[spring->kl], spring); + shear_springs++; BLI_linklist_prepend ( &cloth->springs, spring ); @@ -1389,7 +1391,7 @@ static int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm ) break; tspring2 = search2->link; - search = edgelist[tspring2->kl]; + search = edgelist[tspring2->kl].list; while ( search ) { tspring = search->link; index2 = ( ( tspring->ij==tspring2->kl ) ? ( tspring->kl ) : ( tspring->ij ) ); 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 #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; } /* diff --git a/source/blender/bmesh/tools/bmesh_region_match.c b/source/blender/bmesh/tools/bmesh_region_match.c index 72c3bc90599..a6860a6614a 100644 --- a/source/blender/bmesh/tools/bmesh_region_match.c +++ b/source/blender/bmesh/tools/bmesh_region_match.c @@ -511,7 +511,7 @@ static void bm_uuidwalk_pass_add( UUIDFaceStep *fstep; - BLI_assert(faces_pass_len == (unsigned int)BLI_linklist_length(faces_pass)); + BLI_assert(faces_pass_len == (unsigned int)BLI_linklist_count(faces_pass)); /* rehash faces now all their verts have been added */ bm_uuidwalk_rehash_facelinks(uuidwalk, faces_pass, faces_pass_len, true); diff --git a/source/blender/collada/collada.cpp b/source/blender/collada/collada.cpp index f1d5f1a208a..4ca21869ec2 100644 --- a/source/blender/collada/collada.cpp +++ b/source/blender/collada/collada.cpp @@ -116,7 +116,7 @@ int collada_export(Scene *sce, eObjectSet objectSet = (export_settings.selected) ? OB_SET_SELECTED : OB_SET_ALL; export_settings.export_set = BKE_object_relational_superset(sce, objectSet, (eObRelationTypes)includeFilter); - int export_count = BLI_linklist_length(export_settings.export_set); + int export_count = BLI_linklist_count(export_settings.export_set); if (export_count==0) { diff --git a/source/blender/editors/sculpt_paint/paint_image_proj.c b/source/blender/editors/sculpt_paint/paint_image_proj.c index 46e294de956..6d2f3d5587d 100644 --- a/source/blender/editors/sculpt_paint/paint_image_proj.c +++ b/source/blender/editors/sculpt_paint/paint_image_proj.c @@ -3768,7 +3768,7 @@ static void project_paint_prepare_all_faces( const bool is_multi_view) { /* Image Vars - keep track of images we have used */ - LinkNode *image_LinkList = NULL; + LinkNodePair image_LinkList = {NULL, NULL}; Image *tpage_last = NULL, *tpage; TexPaintSlot *slot_last = NULL; @@ -3843,7 +3843,7 @@ static void project_paint_prepare_all_faces( if (tpage_last != tpage) { - image_index = BLI_linklist_index(image_LinkList, tpage); + image_index = BLI_linklist_index(image_LinkList.list, tpage); if (image_index == -1 && BKE_image_has_ibuf(tpage, NULL)) { /* MemArena dosnt have an append func */ BLI_linklist_append(&image_LinkList, tpage); @@ -3864,11 +3864,11 @@ static void project_paint_prepare_all_faces( /* build an array of images we use*/ if (ps->is_shared_user == false) { - project_paint_build_proj_ima(ps, arena, image_LinkList); + project_paint_build_proj_ima(ps, arena, image_LinkList.list); } /* we have built the array, discard the linked list */ - BLI_linklist_free(image_LinkList, NULL); + BLI_linklist_free(image_LinkList.list, NULL); } /* run once per stroke before projection painting */ diff --git a/source/blender/editors/space_file/filelist.c b/source/blender/editors/space_file/filelist.c index af65149ff9c..4048c9fc1a1 100644 --- a/source/blender/editors/space_file/filelist.c +++ b/source/blender/editors/space_file/filelist.c @@ -1104,7 +1104,7 @@ static void filelist_from_library(struct FileList *filelist) previews = NULL; nprevs = 0; names = BLO_blendhandle_get_linkable_groups(filelist->libfiledata); - nnames = BLI_linklist_length(names); + nnames = BLI_linklist_count(names); } filelist->numfiles = nnames + 1; -- cgit v1.2.3