doxygen: add newline after \file
[blender.git] / source / blender / blenkernel / intern / library_idmap.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 #include <string.h>
18 #include <stdlib.h>
19
20 #include "MEM_guardedalloc.h"
21
22 #include "BLI_utildefines.h"
23 #include "BLI_ghash.h"
24 #include "BLI_listbase.h"
25
26 #include "DNA_ID.h"
27
28 #include "BKE_idcode.h"
29 #include "BKE_library_idmap.h"  /* own include */
30 #include "BKE_main.h"
31
32 /** \file
33  * \ingroup bke
34  *
35  * Utility functions for faster ID lookups.
36  */
37
38 /** \name BKE_main_idmap API
39  *
40  * Cache ID (name, library lookups).
41  * This doesn't account for adding/removing data-blocks,
42  * and should only be used when performing many lookups.
43  *
44  * \note GHash's are initialized on demand,
45  * since its likely some types will never have lookups run on them,
46  * so its a waste to create and never use.
47  * \{ */
48
49 struct IDNameLib_Key {
50         /** ``ID.name + 2``: without the ID type prefix, since each id type gets it's own 'map' */
51         const char *name;
52         /** ``ID.lib``: */
53         const Library *lib;
54 };
55
56 struct IDNameLib_TypeMap {
57         GHash *map;
58         short id_type;
59         /* only for storage of keys in the ghash, avoid many single allocs */
60         struct IDNameLib_Key *keys;
61 };
62
63 /**
64  * Opaque structure, external API users only see this.
65  */
66 struct IDNameLib_Map {
67         struct IDNameLib_TypeMap type_maps[MAX_LIBARRAY];
68         struct Main *bmain;
69         struct GSet *valid_id_pointers;
70 };
71
72 static struct IDNameLib_TypeMap *main_idmap_from_idcode(struct IDNameLib_Map *id_map, short id_type)
73 {
74         for (int i = 0; i < MAX_LIBARRAY; i++) {
75                 if (id_map->type_maps[i].id_type == id_type) {
76                         return &id_map->type_maps[i];
77                 }
78         }
79         return NULL;
80 }
81
82 /**
83  * Generate mapping from ID type/name to ID pointer for given \a bmain.
84  *
85  * \note When used during undo/redo, there is no guaranty that ID pointers from UI area
86  *       are not pointing to freed memory (when some IDs have been deleted). To avoid crashes
87  *       in those cases, one can provide the 'old' (aka current) Main databse as reference.
88  *       #BKE_main_idmap_lookup_id will then check that given ID does exist in \a old_bmain
89  *       before trying to use it.
90  *
91  * \param create_valid_ids_set: If \a true, generate a reference to prevent freed memory accesses.
92  * \param old_bmain: If not NULL, its IDs will be added the valid references set.
93  */
94 struct IDNameLib_Map *BKE_main_idmap_create(
95         struct Main *bmain, const bool create_valid_ids_set, struct Main *old_bmain)
96 {
97         struct IDNameLib_Map *id_map = MEM_mallocN(sizeof(*id_map), __func__);
98
99         int index = 0;
100         while (index < MAX_LIBARRAY) {
101                 struct IDNameLib_TypeMap *type_map = &id_map->type_maps[index];
102                 type_map->map = NULL;
103                 type_map->id_type = BKE_idcode_iter_step(&index);
104                 BLI_assert(type_map->id_type != 0);
105         }
106         BLI_assert(index == MAX_LIBARRAY);
107
108         id_map->bmain = bmain;
109
110         if (create_valid_ids_set) {
111                 id_map->valid_id_pointers = BKE_main_gset_create(bmain, NULL);
112                 if (old_bmain != NULL) {
113                         id_map->valid_id_pointers = BKE_main_gset_create(old_bmain, id_map->valid_id_pointers);
114                 }
115         }
116         else {
117                 id_map->valid_id_pointers = NULL;
118         }
119
120         return id_map;
121 }
122
123 struct Main *BKE_main_idmap_main_get(struct IDNameLib_Map *id_map)
124 {
125         return id_map->bmain;
126 }
127
128 static unsigned int idkey_hash(const void *ptr)
129 {
130         const struct IDNameLib_Key *idkey = ptr;
131         unsigned int key = BLI_ghashutil_strhash(idkey->name);
132         if (idkey->lib) {
133                 key ^= BLI_ghashutil_ptrhash(idkey->lib);
134         }
135         return key;
136 }
137
138 static bool idkey_cmp(const void *a, const void *b)
139 {
140         const struct IDNameLib_Key *idkey_a = a;
141         const struct IDNameLib_Key *idkey_b = b;
142         return strcmp(idkey_a->name, idkey_b->name) || (idkey_a->lib != idkey_b->lib);
143 }
144
145 ID *BKE_main_idmap_lookup(struct IDNameLib_Map *id_map, short id_type, const char *name, const Library *lib)
146 {
147         struct IDNameLib_TypeMap *type_map = main_idmap_from_idcode(id_map, id_type);
148
149         if (UNLIKELY(type_map == NULL)) {
150                 return NULL;
151         }
152
153         /* lazy init */
154         if (type_map->map == NULL) {
155                 ListBase *lb = which_libbase(id_map->bmain, id_type);
156                 const int lb_len = BLI_listbase_count(lb);
157                 if (lb_len == 0) {
158                         return NULL;
159                 }
160                 type_map->map = BLI_ghash_new_ex(idkey_hash, idkey_cmp, __func__, lb_len);
161                 type_map->keys = MEM_mallocN(sizeof(struct IDNameLib_Key) * lb_len, __func__);
162
163                 GHash *map = type_map->map;
164                 struct IDNameLib_Key *key = type_map->keys;
165
166                 for (ID *id = lb->first; id; id = id->next, key++) {
167                         key->name = id->name + 2;
168                         key->lib = id->lib;
169                         BLI_ghash_insert(map, key, id);
170                 }
171         }
172
173         const struct IDNameLib_Key key_lookup = {name, lib};
174         return BLI_ghash_lookup(type_map->map, &key_lookup);
175 }
176
177 ID *BKE_main_idmap_lookup_id(struct IDNameLib_Map *id_map, const ID *id)
178 {
179         /* When used during undo/redo, this function cannot assume that given id points to valid memory
180          * (i.e. has not been freed), so it has to check that it does exist in 'old' (aka current) Main database.
181          * Otherwise, we cannot provide new ID pointer that way (would crash accessing freed memory
182          * when trying to get ID name).
183          */
184         if (id_map->valid_id_pointers == NULL || BLI_gset_haskey(id_map->valid_id_pointers, id)) {
185                 return BKE_main_idmap_lookup(id_map, GS(id->name), id->name + 2, id->lib);
186         }
187         return NULL;
188 }
189
190 void BKE_main_idmap_destroy(struct IDNameLib_Map *id_map)
191 {
192         struct IDNameLib_TypeMap *type_map = id_map->type_maps;
193         for (int i = 0; i < MAX_LIBARRAY; i++, type_map++) {
194                 if (type_map->map) {
195                         BLI_ghash_free(type_map->map, NULL, NULL);
196                         type_map->map = NULL;
197                         MEM_freeN(type_map->keys);
198                 }
199         }
200
201         if (id_map->valid_id_pointers != NULL) {
202                 BLI_gset_free(id_map->valid_id_pointers, NULL);
203         }
204
205         MEM_freeN(id_map);
206 }
207
208 /** \} */