ClangFormat: apply to source, most of intern
[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,
73                                                         short id_type)
74 {
75   for (int i = 0; i < MAX_LIBARRAY; i++) {
76     if (id_map->type_maps[i].id_type == id_type) {
77       return &id_map->type_maps[i];
78     }
79   }
80   return NULL;
81 }
82
83 /**
84  * Generate mapping from ID type/name to ID pointer for given \a bmain.
85  *
86  * \note When used during undo/redo, there is no guaranty that ID pointers from UI area
87  *       are not pointing to freed memory (when some IDs have been deleted). To avoid crashes
88  *       in those cases, one can provide the 'old' (aka current) Main databse as reference.
89  *       #BKE_main_idmap_lookup_id will then check that given ID does exist in \a old_bmain
90  *       before trying to use it.
91  *
92  * \param create_valid_ids_set: If \a true, generate a reference to prevent freed memory accesses.
93  * \param old_bmain: If not NULL, its IDs will be added the valid references set.
94  */
95 struct IDNameLib_Map *BKE_main_idmap_create(struct Main *bmain,
96                                             const bool create_valid_ids_set,
97                                             struct Main *old_bmain)
98 {
99   struct IDNameLib_Map *id_map = MEM_mallocN(sizeof(*id_map), __func__);
100
101   int index = 0;
102   while (index < MAX_LIBARRAY) {
103     struct IDNameLib_TypeMap *type_map = &id_map->type_maps[index];
104     type_map->map = NULL;
105     type_map->id_type = BKE_idcode_iter_step(&index);
106     BLI_assert(type_map->id_type != 0);
107   }
108   BLI_assert(index == MAX_LIBARRAY);
109
110   id_map->bmain = bmain;
111
112   if (create_valid_ids_set) {
113     id_map->valid_id_pointers = BKE_main_gset_create(bmain, NULL);
114     if (old_bmain != NULL) {
115       id_map->valid_id_pointers = BKE_main_gset_create(old_bmain, id_map->valid_id_pointers);
116     }
117   }
118   else {
119     id_map->valid_id_pointers = NULL;
120   }
121
122   return id_map;
123 }
124
125 struct Main *BKE_main_idmap_main_get(struct IDNameLib_Map *id_map)
126 {
127   return id_map->bmain;
128 }
129
130 static unsigned int idkey_hash(const void *ptr)
131 {
132   const struct IDNameLib_Key *idkey = ptr;
133   unsigned int key = BLI_ghashutil_strhash(idkey->name);
134   if (idkey->lib) {
135     key ^= BLI_ghashutil_ptrhash(idkey->lib);
136   }
137   return key;
138 }
139
140 static bool idkey_cmp(const void *a, const void *b)
141 {
142   const struct IDNameLib_Key *idkey_a = a;
143   const struct IDNameLib_Key *idkey_b = b;
144   return strcmp(idkey_a->name, idkey_b->name) || (idkey_a->lib != idkey_b->lib);
145 }
146
147 ID *BKE_main_idmap_lookup(struct IDNameLib_Map *id_map,
148                           short id_type,
149                           const char *name,
150                           const Library *lib)
151 {
152   struct IDNameLib_TypeMap *type_map = main_idmap_from_idcode(id_map, id_type);
153
154   if (UNLIKELY(type_map == NULL)) {
155     return NULL;
156   }
157
158   /* lazy init */
159   if (type_map->map == NULL) {
160     ListBase *lb = which_libbase(id_map->bmain, id_type);
161     const int lb_len = BLI_listbase_count(lb);
162     if (lb_len == 0) {
163       return NULL;
164     }
165     type_map->map = BLI_ghash_new_ex(idkey_hash, idkey_cmp, __func__, lb_len);
166     type_map->keys = MEM_mallocN(sizeof(struct IDNameLib_Key) * lb_len, __func__);
167
168     GHash *map = type_map->map;
169     struct IDNameLib_Key *key = type_map->keys;
170
171     for (ID *id = lb->first; id; id = id->next, key++) {
172       key->name = id->name + 2;
173       key->lib = id->lib;
174       BLI_ghash_insert(map, key, id);
175     }
176   }
177
178   const struct IDNameLib_Key key_lookup = {name, lib};
179   return BLI_ghash_lookup(type_map->map, &key_lookup);
180 }
181
182 ID *BKE_main_idmap_lookup_id(struct IDNameLib_Map *id_map, const ID *id)
183 {
184   /* When used during undo/redo, this function cannot assume that given id points to valid memory
185    * (i.e. has not been freed), so it has to check that it does exist in 'old' (aka current) Main database.
186    * Otherwise, we cannot provide new ID pointer that way (would crash accessing freed memory
187    * when trying to get ID name).
188    */
189   if (id_map->valid_id_pointers == NULL || BLI_gset_haskey(id_map->valid_id_pointers, id)) {
190     return BKE_main_idmap_lookup(id_map, GS(id->name), id->name + 2, id->lib);
191   }
192   return NULL;
193 }
194
195 void BKE_main_idmap_destroy(struct IDNameLib_Map *id_map)
196 {
197   struct IDNameLib_TypeMap *type_map = id_map->type_maps;
198   for (int i = 0; i < MAX_LIBARRAY; i++, type_map++) {
199     if (type_map->map) {
200       BLI_ghash_free(type_map->map, NULL, NULL);
201       type_map->map = NULL;
202       MEM_freeN(type_map->keys);
203     }
204   }
205
206   if (id_map->valid_id_pointers != NULL) {
207     BLI_gset_free(id_map->valid_id_pointers, NULL);
208   }
209
210   MEM_freeN(id_map);
211 }
212
213 /** \} */