fix for [#36260] 2,300 Objects Makes Blender Unresponsive
authorSv. Lockal <lockalsash@gmail.com>
Sat, 3 Aug 2013 11:35:09 +0000 (11:35 +0000)
committerSv. Lockal <lockalsash@gmail.com>
Sat, 3 Aug 2013 11:35:09 +0000 (11:35 +0000)
- performance of outliner was low because of unoptimal data structures.
- now it uses BLI_mempool instead of custom mempool and GHash to make searches for duplicates faster.
- also fix undesired behaviour of BLI_mempool_as_arrayN

thanks to Campbell Barton and Lukas Tönne for helping me get a better fix put together.

13 files changed:
source/blender/blenkernel/intern/object.c
source/blender/blenlib/intern/BLI_mempool.c
source/blender/blenloader/intern/readfile.c
source/blender/blenloader/intern/writefile.c
source/blender/editors/space_outliner/outliner_draw.c
source/blender/editors/space_outliner/outliner_edit.c
source/blender/editors/space_outliner/outliner_intern.h
source/blender/editors/space_outliner/outliner_select.c
source/blender/editors/space_outliner/outliner_tools.c
source/blender/editors/space_outliner/outliner_tree.c
source/blender/editors/space_outliner/space_outliner.c
source/blender/makesdna/DNA_outliner_types.h
source/blender/makesdna/DNA_space_types.h

index 8ac067c03160e6861eb5f889edc75cb9f2e82308..7aa23dc6c2b8c096446eb3812a44ba3f2fc7683c 100644 (file)
@@ -678,9 +678,10 @@ void BKE_object_unlink(Object *ob)
                                        SpaceOops *so = (SpaceOops *)sl;
 
                                        if (so->treestore) {
-                                               TreeStoreElem *tselem = so->treestore->data;
-                                               int i;
-                                               for (i = 0; i < so->treestore->usedelem; i++, tselem++) {
+                                               TreeStoreElem *tselem;
+                                               BLI_mempool_iter iter;
+                                               BLI_mempool_iternew(so->treestore, &iter);
+                                               while ((tselem = BLI_mempool_iterstep(&iter))) {
                                                        if (tselem->id == (ID *)ob) tselem->id = NULL;
                                                }
                                        }
index 217a4b9d266a3616cbecc117296ac670f4762848..f370f32c31df1cd37a5fa4d9d0797d9ba5351162 100644 (file)
@@ -354,8 +354,18 @@ void BLI_mempool_as_array(BLI_mempool *pool, void **data)
  */
 void *BLI_mempool_as_arrayN(BLI_mempool *pool, const char *allocstr)
 {
-       void *data = MEM_mallocN((size_t)(BLI_mempool_count(pool) * pool->esize), allocstr);
-       BLI_mempool_as_array(pool, data);
+       char *data = MEM_mallocN((size_t)(pool->totused * pool->esize), allocstr);
+       BLI_assert(pool->flag & BLI_MEMPOOL_ALLOW_ITER);
+       if (data) {
+               BLI_mempool_iter iter;
+               char *elem, *p = data;
+               BLI_mempool_iternew(pool, &iter);
+               for (elem = BLI_mempool_iterstep(&iter); elem; elem = BLI_mempool_iterstep(&iter)) {
+                       memcpy(p, elem, (size_t)pool->esize);
+                       p += pool->esize;
+               }
+               BLI_assert((p - data) == pool->totused * pool->esize);
+       }
        return data;
 }
 
index 0ff3392ad005ffc72895dc0961bad8e4bb022544..72b426a155a7618621e605ce1409ed5666ea7b81 100644 (file)
 #include "BLI_math.h"
 #include "BLI_edgehash.h"
 #include "BLI_threads.h"
+#include "BLI_mempool.h"
 
 #include "BLF_translation.h"
 
@@ -5684,16 +5685,24 @@ static void lib_link_screen(FileData *fd, Main *main)
                                        }
                                        else if (sl->spacetype == SPACE_OUTLINER) {
                                                SpaceOops *so= (SpaceOops *)sl;
-                                               TreeStoreElem *tselem;
-                                               int a;
-                                               
                                                so->search_tse.id = newlibadr(fd, NULL, so->search_tse.id);
                                                
                                                if (so->treestore) {
-                                                       tselem = so->treestore->data;
-                                                       for (a=0; a < so->treestore->usedelem; a++, tselem++) {
+                                                       TreeStoreElem *tselem;
+                                                       BLI_mempool_iter iter;
+
+                                                       BLI_mempool_iternew(so->treestore, &iter);
+                                                       while ((tselem = BLI_mempool_iterstep(&iter))) {
                                                                tselem->id = newlibadr(fd, NULL, tselem->id);
                                                        }
+                                                       if (so->treehash) {
+                                                               /* update hash table, because it depends on ids too */
+                                                               BLI_ghash_clear(so->treehash, NULL, NULL);
+                                                               BLI_mempool_iternew(so->treestore, &iter);
+                                                               while ((tselem = BLI_mempool_iterstep(&iter))) {
+                                                                       BLI_ghash_insert(so->treehash, tselem, tselem);
+                                                               }
+                                                       }
                                                }
                                        }
                                        else if (sl->spacetype == SPACE_NODE) {
@@ -6016,16 +6025,25 @@ void blo_lib_link_screen_restore(Main *newmain, bScreen *curscreen, Scene *cursc
                                }
                                else if (sl->spacetype == SPACE_OUTLINER) {
                                        SpaceOops *so= (SpaceOops *)sl;
-                                       int a;
                                        
                                        so->search_tse.id = restore_pointer_by_name(newmain, so->search_tse.id, 0);
                                        
                                        if (so->treestore) {
-                                               TreeStore *ts = so->treestore;
-                                               TreeStoreElem *tselem = ts->data;
-                                               for (a = 0; a < ts->usedelem; a++, tselem++) {
+                                               TreeStoreElem *tselem;
+                                               BLI_mempool_iter iter;
+
+                                               BLI_mempool_iternew(so->treestore, &iter);
+                                               while ((tselem = BLI_mempool_iterstep(&iter))) {
                                                        tselem->id = restore_pointer_by_name(newmain, tselem->id, 0);
                                                }
+                                               if (so->treehash) {
+                                                       /* update hash table, because it depends on ids too */
+                                                       BLI_ghash_clear(so->treehash, NULL, NULL);
+                                                       BLI_mempool_iternew(so->treestore, &iter);
+                                                       while ((tselem = BLI_mempool_iterstep(&iter))) {
+                                                               BLI_ghash_insert(so->treehash, tselem, tselem);
+                                                       }
+                                               }
                                        }
                                }
                                else if (sl->spacetype == SPACE_NODE) {
@@ -6283,13 +6301,27 @@ static bool direct_link_screen(FileData *fd, bScreen *sc)
                        else if (sl->spacetype == SPACE_OUTLINER) {
                                SpaceOops *soops = (SpaceOops *) sl;
                                
-                               soops->treestore = newdataadr(fd, soops->treestore);
-                               if (soops->treestore) {
-                                       soops->treestore->data = newdataadr(fd, soops->treestore->data);
+                               TreeStore *ts = newdataadr(fd, soops->treestore);
+                               soops->treestore = NULL;
+                               if (ts) {
+                                       TreeStoreElem *elems = newdataadr(fd, ts->data);
+                                       
+                                       soops->treestore = BLI_mempool_create(sizeof(TreeStoreElem), ts->usedelem,
+                                                                             512, BLI_MEMPOOL_ALLOW_ITER);
+                                       if (ts->usedelem && elems) {
+                                               int i;
+                                               for (i = 0; i < ts->usedelem; i++) {
+                                                       TreeStoreElem *new_elem = BLI_mempool_alloc(soops->treestore);
+                                                       *new_elem = elems[i];
+                                               }
+                                               MEM_freeN(elems);
+                                       }
                                        /* we only saved what was used */
-                                       soops->treestore->totelem = soops->treestore->usedelem;
                                        soops->storeflag |= SO_TREESTORE_CLEANUP;       // at first draw
+                                       
+                                       MEM_freeN(ts);
                                }
+                               soops->treehash = NULL;
                                soops->tree.first = soops->tree.last= NULL;
                        }
                        else if (sl->spacetype == SPACE_IMAGE) {
index e170107713c7836f964fd1ec4f6a4a5f08fef573..12804e8042d241fbf19352d36103d3d6d2c96984 100644 (file)
 #include "BLI_bitmap.h"
 #include "BLI_blenlib.h"
 #include "BLI_linklist.h"
-#include "BKE_bpath.h"
 #include "BLI_math.h"
 #include "BLI_utildefines.h"
+#include "BLI_mempool.h"
 
 #include "BKE_action.h"
 #include "BKE_blender.h"
+#include "BKE_bpath.h"
 #include "BKE_curve.h"
 #include "BKE_constraint.h"
 #include "BKE_global.h" // for G
@@ -2393,6 +2394,31 @@ static void write_region(WriteData *wd, ARegion *ar, int spacetype)
        }
 }
 
+static void write_soops(WriteData *wd, SpaceOops *so)
+{
+       BLI_mempool *ts = so->treestore;
+       
+       if (ts) {
+               int elems = BLI_mempool_count(ts);
+               /* linearize mempool to array */
+               TreeStoreElem *data = elems ? BLI_mempool_as_arrayN(ts, "TreeStoreElem") : NULL;
+               TreeStore ts_flat = {elems, elems, data};
+               
+               /* temporarily replace mempool-treestore by flat-treestore */
+               so->treestore = (BLI_mempool *)&ts_flat;
+               writestruct(wd, DATA, "SpaceOops", 1, so);
+               /* restore old treestore */
+               so->treestore = ts;
+               writestruct(wd, DATA, "TreeStore", 1, &ts_flat);
+               if (data) {
+                       writestruct(wd, DATA, "TreeStoreElem", elems, data);
+                       MEM_freeN(data);
+               }
+       } else {
+               writestruct(wd, DATA, "SpaceOops", 1, so);
+       }
+}
+
 static void write_screens(WriteData *wd, ListBase *scrbase)
 {
        bScreen *sc;
@@ -2475,15 +2501,7 @@ static void write_screens(WriteData *wd, ListBase *scrbase)
                                }
                                else if (sl->spacetype==SPACE_OUTLINER) {
                                        SpaceOops *so= (SpaceOops *)sl;
-                                       
-                                       writestruct(wd, DATA, "SpaceOops", 1, so);
-
-                                       /* outliner */
-                                       if (so->treestore) {
-                                               writestruct(wd, DATA, "TreeStore", 1, so->treestore);
-                                               if (so->treestore->data)
-                                                       writestruct(wd, DATA, "TreeStoreElem", so->treestore->usedelem, so->treestore->data);
-                                       }
+                                       write_soops(wd, so);
                                }
                                else if (sl->spacetype==SPACE_IMAGE) {
                                        SpaceImage *sima= (SpaceImage *)sl;
index b308bd09026f68fd63a09c0d08520adcc44cfae0..44d5672e7da5b45814d9a8f1b485e062704a3b89 100644 (file)
@@ -40,6 +40,7 @@
 #include "BLI_blenlib.h"
 #include "BLI_utildefines.h"
 #include "BLI_ghash.h"
+#include "BLI_mempool.h"
 
 #include "BLF_translation.h"
 
@@ -407,7 +408,7 @@ static void namebutton_cb(bContext *C, void *tsep, char *oldname)
        SpaceOops *soops = CTX_wm_space_outliner(C);
        Scene *scene = CTX_data_scene(C);
        Object *obedit = CTX_data_edit_object(C);
-       TreeStore *ts = soops->treestore;
+       BLI_mempool *ts = soops->treestore;
        TreeStoreElem *tselem = tsep;
        
        if (ts && tselem) {
index cef5fe53407efe52d95d9a9927dbcaa6bbf26194..a014724af4a0d5aa37abb5ffec18f7ed029b04a1 100644 (file)
@@ -984,7 +984,7 @@ static int ed_operator_outliner_datablocks_active(bContext *C)
  * NOTE: the caller must zero-out all values of the pointers that it passes here first, as
  * this function does not do that yet 
  */
-static void tree_element_to_path(SpaceOops *soops, TreeElement *te, TreeStoreElem *tselem, 
+static void tree_element_to_path(TreeElement *te, TreeStoreElem *tselem,
                                  ID **id, char **path, int *array_index, short *flag, short *UNUSED(groupmode))
 {
        ListBase hierarchy = {NULL, NULL};
@@ -1152,7 +1152,7 @@ static void do_outliner_drivers_editop(SpaceOops *soops, ListBase *tree, ReportL
                            RNA_property_animateable(&te->rnaptr, te->directdata))
                        {
                                /* get id + path + index info from the selected element */
-                               tree_element_to_path(soops, te, tselem, 
+                               tree_element_to_path(te, tselem,
                                                     &id, &path, &array_index, &flag, &groupmode);
                        }
                        
@@ -1333,7 +1333,7 @@ static void do_outliner_keyingset_editop(SpaceOops *soops, KeyingSet *ks, ListBa
                            RNA_property_animateable(&te->rnaptr, te->directdata))
                        {
                                /* get id + path + index info from the selected element */
-                               tree_element_to_path(soops, te, tselem, 
+                               tree_element_to_path(te, tselem,
                                                     &id, &path, &array_index, &flag, &groupmode);
                        }
                        
index 2310ca9b4b5cb90cd6a09d417d27aa6c180a9265..5aaf8b5430b9228823a4fff76611725892ec5203 100644 (file)
@@ -48,15 +48,15 @@ struct Object;
 typedef struct TreeElement {
        struct TreeElement *next, *prev, *parent;
        ListBase subtree;
-       int xs, ys;         // do selection
-       int store_index;    // offset in tree store
-       short flag;         // flag for non-saved stuff
-       short index;        // index for data arrays
-       short idcode;       // from TreeStore id
-       short xend;         // width of item display, for select
+       int xs, ys;                // do selection
+       TreeStoreElem *store_elem; // element in tree store
+       short flag;                // flag for non-saved stuff
+       short index;               // index for data arrays
+       short idcode;              // from TreeStore id
+       short xend;                // width of item display, for select
        const char *name;
-       void *directdata;   // Armature Bones, Base, Sequence, Strip...
-       PointerRNA rnaptr;  // RNA Pointer
+       void *directdata;          // Armature Bones, Base, Sequence, Strip...
+       PointerRNA rnaptr;         // RNA Pointer
 }  TreeElement;
 
 /* TreeElement->flag */
@@ -111,7 +111,7 @@ typedef struct TreeElement {
 /* get TreeStoreElem associated with a TreeElement 
  * < a: (TreeElement) tree element to find stored element for
  */
-#define TREESTORE(a) (soops->treestore->data + (a)->store_index)
+#define TREESTORE(a) ((a)->store_elem)
 
 /* size constants */
 #define OL_Y_OFFSET 2
@@ -150,6 +150,7 @@ typedef struct TreeElement {
 
 /* outliner_tree.c ----------------------------------------------- */
 
+void outliner_rebuild_treehash(struct SpaceOops *soops);
 void outliner_free_tree(ListBase *lb);
 void outliner_cleanup_tree(struct SpaceOops *soops);
 
index 9720d981e85e1a465aec551ebda6759cedf7827a..41ad75bb14fbaebd16e750af4be8a0996be5d722 100644 (file)
@@ -282,7 +282,7 @@ static int tree_element_active_material(bContext *C, Scene *scene, SpaceOops *so
        return 0;
 }
 
-static int tree_element_active_texture(bContext *C, Scene *scene, SpaceOops *soops, TreeElement *te, int set)
+static int tree_element_active_texture(bContext *C, Scene *scene, SpaceOops *UNUSED(soops), TreeElement *te, int set)
 {
        TreeElement *tep;
        TreeStoreElem /* *tselem,*/ *tselemp;
@@ -384,7 +384,7 @@ static int tree_element_active_camera(bContext *UNUSED(C), Scene *scene, SpaceOo
        return scene->camera == ob;
 }
 
-static int tree_element_active_world(bContext *C, Scene *scene, SpaceOops *soops, TreeElement *te, int set)
+static int tree_element_active_world(bContext *C, Scene *scene, SpaceOops *UNUSED(soops), TreeElement *te, int set)
 {
        TreeElement *tep;
        TreeStoreElem *tselem = NULL;
index 1e4af4304f0ec1ebf65be403883364096408ffc2..c1950e62817f345be420ce3fcf483750fe29484c 100644 (file)
@@ -45,6 +45,7 @@
 
 #include "BLI_blenlib.h"
 #include "BLI_utildefines.h"
+#include "BLI_ghash.h"
 
 #include "BKE_animsys.h"
 #include "BKE_context.h"
@@ -298,13 +299,17 @@ static void object_delete_cb(bContext *C, Scene *scene, TreeElement *te,
        if (base == NULL)
                base = BKE_scene_base_find(scene, (Object *)tselem->id);
        if (base) {
+               SpaceOops *soops = CTX_wm_space_outliner(C);
+
                // check also library later
                if (scene->obedit == base->object)
                        ED_object_editmode_exit(C, EM_FREEDATA | EM_FREEUNDO | EM_WAITCURSOR | EM_DO_UNDO);
                
                ED_base_object_free_and_unlink(CTX_data_main(C), scene, base);
                te->directdata = NULL;
+               BLI_ghash_remove(soops->treehash, tselem, NULL, NULL);
                tselem->id = NULL;
+               BLI_ghash_insert(soops->treehash, tselem, tselem);
        }
 }
 
index 17734f00997b3c6a4e19d0c7cf0ae13853031bd8..2295af93166cbff818f68c4259e01a55f61f135c 100644 (file)
@@ -63,6 +63,8 @@
 #include "BLI_blenlib.h"
 #include "BLI_utildefines.h"
 #include "BLI_math.h"
+#include "BLI_ghash.h"
+#include "BLI_mempool.h"
 
 #include "BLF_translation.h"
 
 
 static void outliner_storage_cleanup(SpaceOops *soops)
 {
-       TreeStore *ts = soops->treestore;
+       BLI_mempool *ts = soops->treestore;
        
        if (ts) {
                TreeStoreElem *tselem;
-               int a, unused = 0;
+               int unused = 0;
                
                /* each element used once, for ID blocks with more users to have each a treestore */
-               for (a = 0, tselem = ts->data; a < ts->usedelem; a++, tselem++) tselem->used = 0;
+               BLI_mempool_iter iter;
+
+               BLI_mempool_iternew(ts, &iter);
+               while ((tselem = BLI_mempool_iterstep(&iter))) {
+                       tselem->used = 0;
+               }
                
                /* cleanup only after reading file or undo step, and always for
                 * RNA datablocks view in order to save memory */
                if (soops->storeflag & SO_TREESTORE_CLEANUP) {
-                       
-                       for (a = 0, tselem = ts->data; a < ts->usedelem; a++, tselem++) {
+                       BLI_mempool_iternew(ts, &iter);
+                       while ((tselem = BLI_mempool_iterstep(&iter))) {
                                if (tselem->id == NULL) unused++;
                        }
                        
                        if (unused) {
-                               if (ts->usedelem == unused) {
-                                       MEM_freeN(ts->data);
-                                       ts->data = NULL;
-                                       ts->usedelem = ts->totelem = 0;
+                               if (BLI_mempool_count(ts) == unused) {
+                                       BLI_mempool_destroy(ts);
+                                       soops->treestore = NULL;
+
+                                       if (soops->treehash) {
+                                               BLI_ghash_free(soops->treehash, NULL, NULL);
+                                               soops->treehash = NULL;
+                                       }
                                }
                                else {
-                                       TreeStoreElem *tsnewar, *tsnew;
-                                       
-                                       tsnew = tsnewar = MEM_mallocN((ts->usedelem - unused) * sizeof(TreeStoreElem), "new tselem");
-                                       for (a = 0, tselem = ts->data; a < ts->usedelem; a++, tselem++) {
+                                       TreeStoreElem *tsenew;
+                                       BLI_mempool *new_ts = BLI_mempool_create(sizeof(TreeStoreElem), BLI_mempool_count(ts) - unused,
+                                                                                512, BLI_MEMPOOL_ALLOW_ITER);
+                                       BLI_mempool_iternew(ts, &iter);
+                                       while ((tselem = BLI_mempool_iterstep(&iter))) {
                                                if (tselem->id) {
-                                                       *tsnew = *tselem;
-                                                       tsnew++;
+                                                       tsenew = BLI_mempool_alloc(new_ts);
+                                                       *tsenew = *tselem;
+                                               }
+                                       }
+                                       BLI_mempool_destroy(ts);
+                                       soops->treestore = new_ts;
+
+                                       if (soops->treehash) {
+                                               /* update hash table to fix broken pointers */
+                                               BLI_ghash_clear(soops->treehash, NULL, NULL);
+                                               BLI_mempool_iternew(soops->treestore, &iter);
+                                               while ((tselem = BLI_mempool_iterstep(&iter))) {
+                                                       BLI_ghash_insert(soops->treehash, tselem, tselem);
                                                }
                                        }
-                                       MEM_freeN(ts->data);
-                                       ts->data = tsnewar;
-                                       ts->usedelem -= unused;
-                                       ts->totelem = ts->usedelem;
                                }
                        }
                }
        }
 }
 
-/* XXX - THIS FUNCTION IS INCREDIBLY SLOW
- * ... it can bring blenders tools and viewport to a grinding halt because of searching
- * for duplicate items every times they are added.
- *
- * TODO (possible speedups)
- * - use a hash for duplicate (could even store a hash per type)
- * - use mempool for TreeElements
- * */
+static unsigned int tse_hash(const void *ptr)
+{
+       const TreeStoreElem *tse = (const TreeStoreElem *)ptr;
+       unsigned int hash;
+       BLI_assert(tse->type || !tse->nr);
+       hash = BLI_ghashutil_inthash(SET_INT_IN_POINTER((tse->nr << 16) + tse->type));
+       hash ^= BLI_ghashutil_inthash(tse->id);
+       return hash;
+}
+
+static int tse_cmp(const void *a, const void *b)
+{
+       const TreeStoreElem *tse_a = (const TreeStoreElem *)a;
+       const TreeStoreElem *tse_b = (const TreeStoreElem *)b;
+       return tse_a->type != tse_b->type || tse_a->nr != tse_b->nr || tse_a->id != tse_b->id;
+}
+
 static void check_persistent(SpaceOops *soops, TreeElement *te, ID *id, short type, short nr)
 {
-       TreeStore *ts;
-       TreeStoreElem *tselem;
-       int a;
+       /* When treestore comes directly from readfile.c, treehash is empty;
+        * In this case we don't want to get TSE_CLOSED while adding elements one by one,
+     * that is why this function restores treehash */
+       bool restore_treehash = (soops->treestore && !soops->treehash);
+       TreeStoreElem *tselem, elem_template;
        
-       /* case 1; no TreeStore */
        if (soops->treestore == NULL) {
-               soops->treestore = MEM_callocN(sizeof(TreeStore), "treestore");
+               /* if treestore was not created in readfile.c, create it here */
+               soops->treestore = BLI_mempool_create(sizeof(TreeStoreElem), 1, 512, BLI_MEMPOOL_ALLOW_ITER);
        }
-       ts = soops->treestore;
-       
-       /* check if 'te' is in treestore */
-       tselem = ts->data;
-       for (a = 0; a < ts->usedelem; a++, tselem++) {
-               if ((tselem->used == 0) && (tselem->type == type) && (tselem->id == id)) {
-                       if ((type == 0) || (tselem->nr == nr)) {
-                               te->store_index = a;
-                               tselem->used = 1;
-                               return;
-                       }
-               }
+       if (soops->treehash == NULL) {
+               soops->treehash = BLI_ghash_new(tse_hash, tse_cmp, "treehash");
        }
        
-       /* add 1 element to treestore */
-       if (ts->usedelem == ts->totelem) {
-               TreeStoreElem *tsnew;
-               
-               tsnew = MEM_mallocN((ts->totelem + TS_CHUNK) * sizeof(TreeStoreElem), "treestore data");
-               if (ts->data) {
-                       memcpy(tsnew, ts->data, ts->totelem * sizeof(TreeStoreElem));
-                       MEM_freeN(ts->data);
+       if (restore_treehash) {
+               BLI_mempool_iter iter;
+               BLI_mempool_iternew(soops->treestore, &iter);
+               while ((tselem = BLI_mempool_iterstep(&iter))) {
+                       BLI_ghash_insert(soops->treehash, tselem, tselem);
                }
-               ts->data = tsnew;
-               ts->totelem += TS_CHUNK;
        }
-       
-       tselem = ts->data + ts->usedelem;
-       
+
+       /* check if 'te' is in treestore */
+       elem_template.type = type;
+       elem_template.nr = type ? nr : 0;  // we're picky! :)
+       elem_template.id = id;
+       tselem = BLI_ghash_lookup(soops->treehash, &elem_template);
+       if (tselem && !tselem->used) {
+               te->store_elem = tselem;
+               tselem->used = 1;
+               return;
+       }
+
+       /* add 1 element to treestore */
+       tselem = BLI_mempool_alloc(soops->treestore);
        tselem->type = type;
-       if (type) tselem->nr = nr;  // we're picky! :)
-       else tselem->nr = 0;
+       tselem->nr = type ? nr : 0;
        tselem->id = id;
        tselem->used = 0;
        tselem->flag = TSE_CLOSED;
-       te->store_index = ts->usedelem;
-       
-       ts->usedelem++;
+       te->store_elem = tselem;
+       BLI_ghash_insert(soops->treehash, tselem, tselem);
 }
 
 /* ********************************************************* */
@@ -216,15 +240,14 @@ void outliner_cleanup_tree(SpaceOops *soops)
        outliner_storage_cleanup(soops);
 }
 
-/* Find ith item from the treestore */
-static TreeElement *outliner_find_tree_element(ListBase *lb, int store_index)
+/* Find specific item from the treestore */
+static TreeElement *outliner_find_tree_element(ListBase *lb, TreeStoreElem *store_elem)
 {
-       TreeElement *te = lb->first, *tes;
-       while (te) {
-               if (te->store_index == store_index) return te;
-               tes = outliner_find_tree_element(&te->subtree, store_index);
+       TreeElement *te, *tes;
+       for (te = lb->first; te; te = te->next) {
+               if (te->store_elem == store_elem) return te;
+               tes = outliner_find_tree_element(&te->subtree, store_elem);
                if (tes) return tes;
-               te = te->next;
        }
        return NULL;
 }
@@ -232,23 +255,18 @@ static TreeElement *outliner_find_tree_element(ListBase *lb, int store_index)
 /* tse is not in the treestore, we use its contents to find a match */
 TreeElement *outliner_find_tse(SpaceOops *soops, TreeStoreElem *tse)
 {
-       TreeStore *ts = soops->treestore;
-       TreeStoreElem *tselem;
-       int a;
-       
+       GHash *th = soops->treehash;
+       TreeStoreElem *tselem, tselem_template;
+
        if (tse->id == NULL) return NULL;
        
        /* check if 'tse' is in treestore */
-       tselem = ts->data;
-       for (a = 0; a < ts->usedelem; a++, tselem++) {
-               if ((tse->type == 0 && tselem->type == 0) || (tselem->type == tse->type && tselem->nr == tse->nr)) {
-                       if (tselem->id == tse->id) {
-                               break;
-                       }
-               }
-       }
+       tselem_template.id = tse->id;
+       tselem_template.type = tse->type;
+       tselem_template.nr = tse->type ? tse->nr : 0;
+       tselem = BLI_ghash_lookup(th, &tselem_template);
        if (tselem) 
-               return outliner_find_tree_element(&soops->tree, a);
+               return outliner_find_tree_element(&soops->tree, tselem);
        
        return NULL;
 }
@@ -274,7 +292,7 @@ TreeElement *outliner_find_id(SpaceOops *soops, ListBase *lb, ID *id)
 }
 
 
-ID *outliner_search_back(SpaceOops *soops, TreeElement *te, short idcode)
+ID *outliner_search_back(SpaceOops *UNUSED(soops), TreeElement *te, short idcode)
 {
        TreeStoreElem *tselem;
        te = te->parent;
@@ -1187,7 +1205,7 @@ static void outliner_add_seq_dup(SpaceOops *soops, Sequence *seq, TreeElement *t
 /* Hierarchy --------------------------------------------- */
 
 /* make sure elements are correctly nested */
-static void outliner_make_hierarchy(SpaceOops *soops, ListBase *lb)
+static void outliner_make_hierarchy(ListBase *lb)
 {
        TreeElement *te, *ten, *tep;
        TreeStoreElem *tselem;
@@ -1489,7 +1507,7 @@ void outliner_build_tree(Main *mainvar, Scene *scene, SpaceOops *soops)
        Object *ob;
        TreeElement *te = NULL, *ten;
        TreeStoreElem *tselem;
-       int show_opened = (soops->treestore == NULL); /* on first view, we open scenes */
+       int show_opened = !soops->treestore || !BLI_mempool_count(soops->treestore); /* on first view, we open scenes */
 
        /* Are we looking for something - we want to tag parents to filter child matches
         * - NOT in datablocks view - searching all datablocks takes way too long to be useful
@@ -1561,7 +1579,7 @@ void outliner_build_tree(Main *mainvar, Scene *scene, SpaceOops *soops)
                                ten = outliner_add_element(soops, &te->subtree, base->object, te, 0, 0);
                                ten->directdata = base;
                        }
-                       outliner_make_hierarchy(soops, &te->subtree);
+                       outliner_make_hierarchy(&te->subtree);
                        /* clear id.newid, to prevent objects be inserted in wrong scenes (parent in other scene) */
                        for (base = sce->base.first; base; base = base->next) base->object->id.newid = NULL;
                }
@@ -1574,14 +1592,14 @@ void outliner_build_tree(Main *mainvar, Scene *scene, SpaceOops *soops)
                        ten = outliner_add_element(soops, &soops->tree, base->object, NULL, 0, 0);
                        ten->directdata = base;
                }
-               outliner_make_hierarchy(soops, &soops->tree);
+               outliner_make_hierarchy(&soops->tree);
        }
        else if (soops->outlinevis == SO_VISIBLE) {
                for (base = scene->base.first; base; base = base->next) {
                        if (base->lay & scene->lay)
                                outliner_add_element(soops, &soops->tree, base->object, NULL, 0, 0);
                }
-               outliner_make_hierarchy(soops, &soops->tree);
+               outliner_make_hierarchy(&soops->tree);
        }
        else if (soops->outlinevis == SO_GROUPS) {
                Group *group;
@@ -1595,7 +1613,7 @@ void outliner_build_tree(Main *mainvar, Scene *scene, SpaceOops *soops)
                                        ten = outliner_add_element(soops, &te->subtree, go->ob, te, 0, 0);
                                        ten->directdata = NULL; /* eh, why? */
                                }
-                               outliner_make_hierarchy(soops, &te->subtree);
+                               outliner_make_hierarchy(&te->subtree);
                                /* clear id.newid, to prevent objects be inserted in wrong scenes (parent in other scene) */
                                for (go = group->gobject.first; go; go = go->next) go->ob->id.newid = NULL;
                        }
@@ -1610,7 +1628,7 @@ void outliner_build_tree(Main *mainvar, Scene *scene, SpaceOops *soops)
                                        ten->directdata = base;
                                }
                        }
-                       outliner_make_hierarchy(soops, &soops->tree);
+                       outliner_make_hierarchy(&soops->tree);
                }
        }
        else if (soops->outlinevis == SO_SELECTED) {
@@ -1622,7 +1640,7 @@ void outliner_build_tree(Main *mainvar, Scene *scene, SpaceOops *soops)
                                }
                        }
                }
-               outliner_make_hierarchy(soops, &soops->tree);
+               outliner_make_hierarchy(&soops->tree);
        }
        else if (soops->outlinevis == SO_SEQUENCE) {
                Sequence *seq;
index 8da244b1db15dab108fd14bb1406d560c8295764..9c51265f917e42a7265e5ac8a8e6cf1e709fd7e8 100644 (file)
@@ -37,6 +37,8 @@
 #include "BLI_blenlib.h"
 #include "BLI_math.h"
 #include "BLI_utildefines.h"
+#include "BLI_mempool.h"
+#include "BLI_ghash.h"
 
 #include "BKE_context.h"
 #include "BKE_screen.h"
@@ -426,10 +428,11 @@ static void outliner_free(SpaceLink *sl)
        
        outliner_free_tree(&soutliner->tree);
        if (soutliner->treestore) {
-               if (soutliner->treestore->data) MEM_freeN(soutliner->treestore->data);
-               MEM_freeN(soutliner->treestore);
+               BLI_mempool_destroy(soutliner->treestore);
+       }
+       if (soutliner->treehash) {
+               BLI_ghash_free(soutliner->treehash, NULL, NULL);
        }
-       
 }
 
 /* spacetype; init callback */
index 5f9c90f09f740c906238f3d06c351c7bb82e26d0..53061b55e2db9f0e5197ec4146a857dec0be2169 100644 (file)
@@ -32,6 +32,8 @@
 #ifndef __DNA_OUTLINER_TYPES_H__
 #define __DNA_OUTLINER_TYPES_H__
 
+#include "DNA_defs.h"
+
 struct ID;
 
 typedef struct TreeStoreElem {
@@ -39,9 +41,12 @@ typedef struct TreeStoreElem {
        struct ID *id;
 } TreeStoreElem;
 
+/* used only to store data in in blend files */
 typedef struct TreeStore {
-       int totelem, usedelem;
-       TreeStoreElem *data;
+       int totelem  DNA_DEPRECATED; /* was previously used for memory preallocation */
+       int usedelem;                /* number of elements in data array */
+       TreeStoreElem *data;         /* elements to be packed from mempool in writefile.c
+                                     * or extracted to mempool in readfile.c */
 } TreeStore;
 
 /* TreeStoreElem->flag */
index 2d87cb1d8900e984b14b8b277884b819454abdc9..c562a1fefae6b56251935617a086aa31825d3def 100644 (file)
@@ -72,6 +72,8 @@ struct wmTimer;
 struct MovieClip;
 struct MovieClipScopes;
 struct Mask;
+struct GHash;
+struct BLI_mempool;
 
 
 /* SpaceLink (Base) ==================================== */
@@ -244,13 +246,14 @@ typedef struct SpaceOops {
        View2D v2d DNA_DEPRECATED;  /* deprecated, copied to region */
        
        ListBase tree;
-       struct TreeStore *treestore;
+       struct BLI_mempool *treestore;
        
        /* search stuff */
        char search_string[32];
        struct TreeStoreElem search_tse;
 
        short flag, outlinevis, storeflag, search_flags;
+       struct GHash *treehash;
 } SpaceOops;