doxygen: add newline after \file
[blender.git] / source / blender / blenkernel / intern / outliner_treehash.c
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_utildefines.h"
27 #include "BLI_ghash.h"
28 #include "BLI_mempool.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 */
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
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, sizeof(TreeStoreElem *) * tse_group->allocated);
61         }
62         tse_group->elems[tse_group->size] = elem;
63         tse_group->size++;
64 }
65
66 static void tse_group_remove_element(TseGroup *tse_group, TreeStoreElem *elem)
67 {
68         int min_allocated = MAX2(1, tse_group->allocated / 2);
69         BLI_assert(tse_group->allocated == 1 || (tse_group->allocated % 2) == 0);
70
71         tse_group->size--;
72         BLI_assert(tse_group->size >= 0);
73         for (int i = 0; i < tse_group->size; i++) {
74                 if (tse_group->elems[i] == elem) {
75                         memcpy(tse_group->elems[i], tse_group->elems[i + 1], (tse_group->size - (i + 1)) * sizeof(TreeStoreElem *));
76                         break;
77                 }
78         }
79
80         if (UNLIKELY(tse_group->size > 0 && tse_group->size <= min_allocated)) {
81                 tse_group->allocated = min_allocated;
82                 tse_group->elems = MEM_reallocN(tse_group->elems, sizeof(TreeStoreElem *) * tse_group->allocated);
83         }
84 }
85
86 static void tse_group_free(TseGroup *tse_group)
87 {
88         MEM_freeN(tse_group->elems);
89         MEM_freeN(tse_group);
90 }
91
92 static unsigned int tse_hash(const void *ptr)
93 {
94         const TreeStoreElem *tse = ptr;
95         union {
96                 short        h_pair[2];
97                 unsigned int u_int;
98         } hash;
99
100         BLI_assert(tse->type || !tse->nr);
101
102         hash.h_pair[0] = tse->type;
103         hash.h_pair[1] = tse->nr;
104
105         hash.u_int ^= BLI_ghashutil_ptrhash(tse->id);
106
107         return hash.u_int;
108 }
109
110 static bool tse_cmp(const void *a, const void *b)
111 {
112         const TreeStoreElem *tse_a = a;
113         const TreeStoreElem *tse_b = b;
114         return tse_a->type != tse_b->type || tse_a->nr != tse_b->nr || tse_a->id != tse_b->id;
115 }
116
117 static void fill_treehash(void *treehash, BLI_mempool *treestore)
118 {
119         TreeStoreElem *tselem;
120         BLI_mempool_iter iter;
121         BLI_mempool_iternew(treestore, &iter);
122
123         BLI_assert(treehash);
124
125         while ((tselem = BLI_mempool_iterstep(&iter))) {
126                 BKE_outliner_treehash_add_element(treehash, tselem);
127         }
128 }
129
130 void *BKE_outliner_treehash_create_from_treestore(BLI_mempool *treestore)
131 {
132         GHash *treehash = BLI_ghash_new_ex(tse_hash, tse_cmp, "treehash", BLI_mempool_len(treestore));
133         fill_treehash(treehash, treestore);
134         return treehash;
135 }
136
137 static void free_treehash_group(void *key)
138 {
139         tse_group_free(key);
140 }
141
142 void BKE_outliner_treehash_clear_used(void *treehash)
143 {
144         GHashIterator gh_iter;
145
146         GHASH_ITER(gh_iter, treehash) {
147                 TseGroup *group = BLI_ghashIterator_getValue(&gh_iter);
148                 group->lastused = 0;
149         }
150 }
151
152 void *BKE_outliner_treehash_rebuild_from_treestore(void *treehash, BLI_mempool *treestore)
153 {
154         BLI_assert(treehash);
155
156         BLI_ghash_clear_ex(treehash, NULL, free_treehash_group, BLI_mempool_len(treestore));
157         fill_treehash(treehash, treestore);
158         return treehash;
159 }
160
161 void BKE_outliner_treehash_add_element(void *treehash, TreeStoreElem *elem)
162 {
163         TseGroup *group;
164         void **val_p;
165
166         if (!BLI_ghash_ensure_p(treehash, elem, &val_p)) {
167                 *val_p = tse_group_create();
168         }
169         group = *val_p;
170         group->lastused = 0;
171         tse_group_add_element(group, elem);
172 }
173
174 void BKE_outliner_treehash_remove_element(void *treehash, TreeStoreElem *elem)
175 {
176         TseGroup *group = BLI_ghash_lookup(treehash, elem);
177
178         BLI_assert(group != NULL);
179         if (group->size <= 1) {
180                 /* one element -> remove group completely */
181                 BLI_ghash_remove(treehash, elem, NULL, free_treehash_group);
182         }
183         else {
184                 tse_group_remove_element(group, elem);
185         }
186 }
187
188 static TseGroup *BKE_outliner_treehash_lookup_group(GHash *th, short type, short nr, struct ID *id)
189 {
190         TreeStoreElem tse_template;
191         tse_template.type = type;
192         tse_template.nr = type ? nr : 0;  // we're picky! :)
193         tse_template.id = id;
194
195         BLI_assert(th);
196
197         return BLI_ghash_lookup(th, &tse_template);
198 }
199
200 TreeStoreElem *BKE_outliner_treehash_lookup_unused(void *treehash, short type, short nr, struct ID *id)
201 {
202         TseGroup *group;
203
204         BLI_assert(treehash);
205
206         group = BKE_outliner_treehash_lookup_group(treehash, type, nr, id);
207         if (group) {
208                 /* Find unused element, with optimization to start from previously
209                  * found element assuming we do repeated lookups. */
210                 int size = group->size;
211                 int offset = group->lastused;
212
213                 for (int i = 0; i < size; i++, offset++) {
214                         if (offset >= size) {
215                                 offset = 0;
216                         }
217
218                         if (!group->elems[offset]->used) {
219                                 group->lastused = offset;
220                                 return group->elems[offset];
221                         }
222                 }
223         }
224         return NULL;
225 }
226
227 TreeStoreElem *BKE_outliner_treehash_lookup_any(void *treehash, short type, short nr, struct ID *id)
228 {
229         TseGroup *group;
230
231         BLI_assert(treehash);
232
233         group = BKE_outliner_treehash_lookup_group(treehash, type, nr, id);
234         return group ? group->elems[0] : NULL;
235 }
236
237 void BKE_outliner_treehash_free(void *treehash)
238 {
239         BLI_assert(treehash);
240
241         BLI_ghash_free(treehash, NULL, free_treehash_group);
242 }