1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 */
16
17 /** \file
18 * \ingroup bke
19 *
20 * Tree hash for the outliner space.
21 */
22
23 #include <stdlib.h>
24 #include <string.h>
25
26 #include "BLI_ghash.h"
27 #include "BLI_mempool.h"
28 #include "BLI_utildefines.h"
29
30 #include "DNA_outliner_types.h"
31
32 #include "BKE_outliner_treehash.h"
33
34 #include "MEM_guardedalloc.h"
35
36 typedef struct TseGroup {
37 TreeStoreElem **elems;
38 int lastused;
39 int size;
40 int allocated;
41 } TseGroup;
42
43 /* Allocate structure for TreeStoreElements;
44 * Most of elements in treestore have no duplicates,
45 * so there is no need to preallocate memory for more than one pointer */
tse_group_create(void)46 static TseGroup *tse_group_create(void)
47 {
48 TseGroup *tse_group = MEM_mallocN(sizeof(TseGroup), "TseGroup");
49 tse_group->elems = MEM_mallocN(sizeof(TreeStoreElem *), "TseGroupElems");
50 tse_group->size = 0;
51 tse_group->allocated = 1;
52 tse_group->lastused = 0;
53 return tse_group;
54 }
55
tse_group_add_element(TseGroup * tse_group,TreeStoreElem * elem)56 static void tse_group_add_element(TseGroup *tse_group, TreeStoreElem *elem)
57 {
58 if (UNLIKELY(tse_group->size == tse_group->allocated)) {
59 tse_group->allocated *= 2;
60 tse_group->elems = MEM_reallocN(tse_group->elems,
61 sizeof(TreeStoreElem *) * tse_group->allocated);
62 }
63 tse_group->elems[tse_group->size] = elem;
64 tse_group->size++;
65 }
66
tse_group_remove_element(TseGroup * tse_group,TreeStoreElem * elem)67 static void tse_group_remove_element(TseGroup *tse_group, TreeStoreElem *elem)
68 {
69 int min_allocated = MAX2(1, tse_group->allocated / 2);
70 BLI_assert(tse_group->allocated == 1 || (tse_group->allocated % 2) == 0);
71
72 tse_group->size--;
73 BLI_assert(tse_group->size >= 0);
74 for (int i = 0; i < tse_group->size; i++) {
75 if (tse_group->elems[i] == elem) {
76 memcpy(tse_group->elems[i],
77 tse_group->elems[i + 1],
78 (tse_group->size - (i + 1)) * sizeof(TreeStoreElem *));
79 break;
80 }
81 }
82
83 if (UNLIKELY(tse_group->size > 0 && tse_group->size <= min_allocated)) {
84 tse_group->allocated = min_allocated;
85 tse_group->elems = MEM_reallocN(tse_group->elems,
86 sizeof(TreeStoreElem *) * tse_group->allocated);
87 }
88 }
89
tse_group_free(TseGroup * tse_group)90 static void tse_group_free(TseGroup *tse_group)
91 {
92 MEM_freeN(tse_group->elems);
93 MEM_freeN(tse_group);
94 }
95
tse_hash(const void * ptr)96 static unsigned int tse_hash(const void *ptr)
97 {
98 const TreeStoreElem *tse = ptr;
99 union {
100 short h_pair[2];
101 unsigned int u_int;
102 } hash;
103
104 BLI_assert(tse->type || !tse->nr);
105
106 hash.h_pair[0] = tse->type;
107 hash.h_pair[1] = tse->nr;
108
109 hash.u_int ^= BLI_ghashutil_ptrhash(tse->id);
110
111 return hash.u_int;
112 }
113
tse_cmp(const void * a,const void * b)114 static bool tse_cmp(const void *a, const void *b)
115 {
116 const TreeStoreElem *tse_a = a;
117 const TreeStoreElem *tse_b = b;
118 return tse_a->type != tse_b->type || tse_a->nr != tse_b->nr || tse_a->id != tse_b->id;
119 }
120
fill_treehash(void * treehash,BLI_mempool * treestore)121 static void fill_treehash(void *treehash, BLI_mempool *treestore)
122 {
123 TreeStoreElem *tselem;
124 BLI_mempool_iter iter;
125 BLI_mempool_iternew(treestore, &iter);
126
127 BLI_assert(treehash);
128
129 while ((tselem = BLI_mempool_iterstep(&iter))) {
130 BKE_outliner_treehash_add_element(treehash, tselem);
131 }
132 }
133
BKE_outliner_treehash_create_from_treestore(BLI_mempool * treestore)134 void *BKE_outliner_treehash_create_from_treestore(BLI_mempool *treestore)
135 {
136 GHash *treehash = BLI_ghash_new_ex(tse_hash, tse_cmp, "treehash", BLI_mempool_len(treestore));
137 fill_treehash(treehash, treestore);
138 return treehash;
139 }
140
free_treehash_group(void * key)141 static void free_treehash_group(void *key)
142 {
143 tse_group_free(key);
144 }
145
BKE_outliner_treehash_clear_used(void * treehash)146 void BKE_outliner_treehash_clear_used(void *treehash)
147 {
148 GHashIterator gh_iter;
149
150 GHASH_ITER (gh_iter, treehash) {
151 TseGroup *group = BLI_ghashIterator_getValue(&gh_iter);
152 group->lastused = 0;
153 }
154 }
155
BKE_outliner_treehash_rebuild_from_treestore(void * treehash,BLI_mempool * treestore)156 void *BKE_outliner_treehash_rebuild_from_treestore(void *treehash, BLI_mempool *treestore)
157 {
158 BLI_assert(treehash);
159
160 BLI_ghash_clear_ex(treehash, NULL, free_treehash_group, BLI_mempool_len(treestore));
161 fill_treehash(treehash, treestore);
162 return treehash;
163 }
164
BKE_outliner_treehash_add_element(void * treehash,TreeStoreElem * elem)165 void BKE_outliner_treehash_add_element(void *treehash, TreeStoreElem *elem)
166 {
167 TseGroup *group;
168 void **val_p;
169
170 if (!BLI_ghash_ensure_p(treehash, elem, &val_p)) {
171 *val_p = tse_group_create();
172 }
173 group = *val_p;
174 group->lastused = 0;
175 tse_group_add_element(group, elem);
176 }
177
BKE_outliner_treehash_remove_element(void * treehash,TreeStoreElem * elem)178 void BKE_outliner_treehash_remove_element(void *treehash, TreeStoreElem *elem)
179 {
180 TseGroup *group = BLI_ghash_lookup(treehash, elem);
181
182 BLI_assert(group != NULL);
183 if (group->size <= 1) {
184 /* one element -> remove group completely */
185 BLI_ghash_remove(treehash, elem, NULL, free_treehash_group);
186 }
187 else {
188 tse_group_remove_element(group, elem);
189 }
190 }
191
BKE_outliner_treehash_lookup_group(GHash * th,short type,short nr,struct ID * id)192 static TseGroup *BKE_outliner_treehash_lookup_group(GHash *th, short type, short nr, struct ID *id)
193 {
194 TreeStoreElem tse_template;
195 tse_template.type = type;
196 tse_template.nr = type ? nr : 0; /* we're picky! :) */
197 tse_template.id = id;
198
199 BLI_assert(th);
200
201 return BLI_ghash_lookup(th, &tse_template);
202 }
203
BKE_outliner_treehash_lookup_unused(void * treehash,short type,short nr,struct ID * id)204 TreeStoreElem *BKE_outliner_treehash_lookup_unused(void *treehash,
205 short type,
206 short nr,
207 struct ID *id)
208 {
209 TseGroup *group;
210
211 BLI_assert(treehash);
212
213 group = BKE_outliner_treehash_lookup_group(treehash, type, nr, id);
214 if (group) {
215 /* Find unused element, with optimization to start from previously
216 * found element assuming we do repeated lookups. */
217 int size = group->size;
218 int offset = group->lastused;
219
220 for (int i = 0; i < size; i++, offset++) {
221 if (offset >= size) {
222 offset = 0;
223 }
224
225 if (!group->elems[offset]->used) {
226 group->lastused = offset;
227 return group->elems[offset];
228 }
229 }
230 }
231 return NULL;
232 }
233
BKE_outliner_treehash_lookup_any(void * treehash,short type,short nr,struct ID * id)234 TreeStoreElem *BKE_outliner_treehash_lookup_any(void *treehash,
235 short type,
236 short nr,
237 struct ID *id)
238 {
239 TseGroup *group;
240
241 BLI_assert(treehash);
242
243 group = BKE_outliner_treehash_lookup_group(treehash, type, nr, id);
244 return group ? group->elems[0] : NULL;
245 }
246
BKE_outliner_treehash_free(void * treehash)247 void BKE_outliner_treehash_free(void *treehash)
248 {
249 BLI_assert(treehash);
250
251 BLI_ghash_free(treehash, NULL, free_treehash_group);
252 }
253