[Bf-blender-cvs] [4ab47a7] master: BLI_linklist, avoid full list search for append
Campbell Barton
noreply at git.blender.org
Fri Jun 12 09:14:41 CEST 2015
Commit: 4ab47a767067a88cfc82ae2e2214178b90e0f544
Author: Campbell Barton
Date: Fri Jun 12 16:57:15 2015 +1000
Branches: master
https://developer.blender.org/rB4ab47a767067a88cfc82ae2e2214178b90e0f544
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.
===================================================================
M source/blender/blenkernel/intern/cloth.c
M source/blender/blenlib/BLI_linklist.h
M source/blender/blenlib/intern/BLI_linklist.c
M source/blender/blenlib/intern/storage.c
M source/blender/bmesh/tools/bmesh_region_match.c
M source/blender/collada/collada.cpp
M source/blender/editors/sculpt_paint/paint_image_proj.c
M source/blender/editors/space_file/filelist.c
===================================================================
diff --git a/source/blender/blenkernel/intern/cloth.c b/source/blender/blenkernel/intern/cloth.c
index 3b3fe32..e3ff968 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 d0dc7fc..67cb30e 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 394f6e3..1da3996 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 **l
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list