BLI_linklist, avoid full list search for append
authorCampbell Barton <ideasman42@gmail.com>
Fri, 12 Jun 2015 06:57:15 +0000 (16:57 +1000)
committerCampbell Barton <ideasman42@gmail.com>
Fri, 12 Jun 2015 07:13:34 +0000 (17:13 +1000)
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
source/blender/blenlib/BLI_linklist.h
source/blender/blenlib/intern/BLI_linklist.c
source/blender/blenlib/intern/storage.c
source/blender/bmesh/tools/bmesh_region_match.c
source/blender/collada/collada.cpp
source/blender/editors/sculpt_paint/paint_image_proj.c
source/blender/editors/space_file/filelist.c

index 3b3fe323f2b39298df0c128a6ad770533e6a9b22..e3ff96853b362917c11276ace10b0e77866828ca 100644 (file)
@@ -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 ) );
index d0dc7fc7b2f422faa2051c8a74254e913b316705..67cb30e8d17fe22ba7e48af5cc89c61b05d699a2 100644 (file)
  * 
  */
 
+#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)))
index 394f6e3db8a09d96149591f704cd20cb9fef1e1d..1da39967945feda1d336b263da8e70abaa71f5f1 100644 (file)
@@ -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)
index 6394187d40a2573a7323d3db2ddf948809f83bfc..7b7733dea373eafa65b535489cf89779e031e41c 100644 (file)
@@ -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;
 }
 
 /*
index 72c3bc905996eb2371df954939c1b6ca4c844259..a6860a6614af681417e6abd0c0b01b909afa25ca 100644 (file)
@@ -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);
index f1d5f1a208a584d58c019efe5c8f9094c12c7d62..4ca21869ec2734e369cba0d634fcd635113cc32f 100644 (file)
@@ -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)
        {
index 46e294de9566b37b623b0a6e3f88b9456be30e61..6d2f3d5587de156de99e61aa7681a833cea7e632 100644 (file)
@@ -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 */
index af65149ff9c12e414025819ba2b91da159a6355e..4048c9fc1a1b305ed2ec85aca96e0b05a6cde5fe 100644 (file)
@@ -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;