Cleanup: use '_len' instead of '_size' w/ BLI API
[blender.git] / source / blender / blenkernel / intern / outliner_treehash.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Blender Foundation 2013
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file outliner_treehash.c
24  *  \ingroup bke
25  *
26  * Tree hash for the outliner space.
27  */
28
29 #include <stdlib.h>
30
31 #include "BLI_utildefines.h"
32 #include "BLI_ghash.h"
33 #include "BLI_mempool.h"
34
35 #include "DNA_outliner_types.h"
36
37 #include "BKE_outliner_treehash.h"
38
39 #include "MEM_guardedalloc.h"
40
41 typedef struct TseGroup {
42         TreeStoreElem **elems;
43         int size;
44         int allocated;
45 } TseGroup;
46
47 /* Allocate structure for TreeStoreElements;
48  * Most of elements in treestore have no duplicates,
49  * so there is no need to preallocate memory for more than one pointer */
50 static TseGroup *tse_group_create(void)
51 {
52         TseGroup *tse_group = MEM_mallocN(sizeof(TseGroup), "TseGroup");
53         tse_group->elems = MEM_mallocN(sizeof(TreeStoreElem *), "TseGroupElems");
54         tse_group->size = 0;
55         tse_group->allocated = 1;
56         return tse_group;
57 }
58
59 static void tse_group_add(TseGroup *tse_group, TreeStoreElem *elem)
60 {
61         if (UNLIKELY(tse_group->size == tse_group->allocated)) {
62                 tse_group->allocated *= 2;
63                 tse_group->elems = MEM_reallocN(tse_group->elems, sizeof(TreeStoreElem *) * tse_group->allocated);
64         }
65         tse_group->elems[tse_group->size] = elem;
66         tse_group->size++;
67 }
68
69 static void tse_group_free(TseGroup *tse_group)
70 {
71         MEM_freeN(tse_group->elems);
72         MEM_freeN(tse_group);
73 }
74
75 static unsigned int tse_hash(const void *ptr)
76 {
77         const TreeStoreElem *tse = ptr;
78         union {
79                 short        h_pair[2];
80                 unsigned int u_int;
81         } hash;
82
83         BLI_assert(tse->type || !tse->nr);
84
85         hash.h_pair[0] = tse->type;
86         hash.h_pair[1] = tse->nr;
87
88         hash.u_int ^= BLI_ghashutil_ptrhash(tse->id);
89
90         return hash.u_int;
91 }
92
93 static bool tse_cmp(const void *a, const void *b)
94 {
95         const TreeStoreElem *tse_a = a;
96         const TreeStoreElem *tse_b = b;
97         return tse_a->type != tse_b->type || tse_a->nr != tse_b->nr || tse_a->id != tse_b->id;
98 }
99
100 static void fill_treehash(void *treehash, BLI_mempool *treestore)
101 {
102         TreeStoreElem *tselem;
103         BLI_mempool_iter iter;
104         BLI_mempool_iternew(treestore, &iter);
105
106         BLI_assert(treehash);
107
108         while ((tselem = BLI_mempool_iterstep(&iter))) {
109                 BKE_outliner_treehash_add_element(treehash, tselem);
110         }
111 }
112
113 void *BKE_outliner_treehash_create_from_treestore(BLI_mempool *treestore)
114 {
115         GHash *treehash = BLI_ghash_new_ex(tse_hash, tse_cmp, "treehash", BLI_mempool_len(treestore));
116         fill_treehash(treehash, treestore);
117         return treehash;
118 }
119
120 static void free_treehash_group(void *key)
121 {
122         tse_group_free(key);
123 }
124
125 void *BKE_outliner_treehash_rebuild_from_treestore(void *treehash, BLI_mempool *treestore)
126 {
127         BLI_assert(treehash);
128
129         BLI_ghash_clear_ex(treehash, NULL, free_treehash_group, BLI_mempool_len(treestore));
130         fill_treehash(treehash, treestore);
131         return treehash;
132 }
133
134 void BKE_outliner_treehash_add_element(void *treehash, TreeStoreElem *elem)
135 {
136         TseGroup *group;
137         void **val_p;
138
139         if (!BLI_ghash_ensure_p(treehash, elem, &val_p)) {
140                 *val_p = tse_group_create();
141         }
142         group = *val_p;
143         tse_group_add(group, elem);
144 }
145
146 static TseGroup *BKE_outliner_treehash_lookup_group(GHash *th, short type, short nr, struct ID *id)
147 {
148         TreeStoreElem tse_template;
149         tse_template.type = type;
150         tse_template.nr = type ? nr : 0;  // we're picky! :)
151         tse_template.id = id;
152
153         BLI_assert(th);
154
155         return BLI_ghash_lookup(th, &tse_template);
156 }
157
158 TreeStoreElem *BKE_outliner_treehash_lookup_unused(void *treehash, short type, short nr, struct ID *id)
159 {
160         TseGroup *group;
161
162         BLI_assert(treehash);
163
164         group = BKE_outliner_treehash_lookup_group(treehash, type, nr, id);
165         if (group) {
166                 int i;
167                 for (i = 0; i < group->size; i++) {
168                         if (!group->elems[i]->used) {
169                                 return group->elems[i];
170                         }
171                 }
172         }
173         return NULL;
174 }
175
176 TreeStoreElem *BKE_outliner_treehash_lookup_any(void *treehash, short type, short nr, struct ID *id)
177 {
178         TseGroup *group;
179
180         BLI_assert(treehash);
181
182         group = BKE_outliner_treehash_lookup_group(treehash, type, nr, id);
183         return group ? group->elems[0] : NULL;
184 }
185
186 void BKE_outliner_treehash_free(void *treehash)
187 {
188         BLI_assert(treehash);
189
190         BLI_ghash_free(treehash, NULL, free_treehash_group);
191 }