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.

8 files changed, 73 insertions, 61 deletions

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 <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;
 }
 
 /*
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;