1 /* objc-map.h -- Implementation of map data structures for ObjC compiler 2 Copyright 2011 Free Software Foundation, Inc. 3 Written by Nicola Pero <nicola.pero@meta-innovation.com> 4 5 This program is free software; you can redistribute it and/or modify it 6 under the terms of the GNU Lesser Public License as published by the 7 Free Software Foundation; either version 3, or (at your option) any 8 later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU Lesser Public License for more details. 14 15 You should have received a copy of the GNU Lesser Public License 16 along with this program; if not, write to the Free Software 17 Foundation, 51 Franklin Street - Fifth Floor, 18 Boston, MA 02110-1301, USA. */ 19 20 #ifndef OBJC_MAP_H 21 #define OBJC_MAP_H 22 23 /* A map is a data structure that maps a key to a value. In this file 24 we currently have maps that can map a GCC identifier (a tree) to 25 some other GCC tree. This is what the ObjC frontend mostly needs: 26 being able to look up an identifier into an ObjC data structure. A 27 typical usage is mapping ObjC class names (as identifiers) to a 28 tree representing the class. 29 30 This implementation is fast. :-) */ 31 32 /** 33 ** Private definitions. 34 **/ 35 36 /* We include private declaration and definitions that are required to 37 provide the implementation of inline functions. You should ignore 38 these definitions (and the implementation of the inline functions) 39 as they are not part of the public API and may change. */ 40 typedef unsigned int objc_map_private_hash_t; 41 42 /* This is used as sentinel. */ 43 #define OBJC_MAP_PRIVATE_EMPTY_SLOT (tree)0 44 45 struct GTY(()) objc_map_private { 46 /* Total number of slots. This is the maximum number of elements 47 that can be currently stored in the map before resizing. This is 48 the number of slots in the C array. Important: this is 49 guaranteed to be a power of 2. When we create (or resize) the 50 map, we round up the size to the next power of 2. This allows us 51 to convert a hash to a position in the hashtable by simply doing 52 "position = hash & mask", where mask is number_of_slots - 1 53 instead of using a modulo (which requires a division). */ 54 size_t number_of_slots; 55 56 /* This is number_of_slots - 1, precomputed. */ 57 size_t mask; 58 59 /* Number of slots that are not empty (ie, that are active). We 60 keep counts using this variable which can easily be checked 61 against max_number_of_non_empty_slots. */ 62 size_t number_of_non_empty_slots; 63 64 /* This is the load factor limit. When the number of non empty 65 slots equals this number, we need to resize the array. This is 66 calculated once, when the slots are resized, and then kept cached 67 so it can be compared quickly when elements are added. */ 68 size_t max_number_of_non_empty_slots; 69 70 /* The maximum load factor. */ 71 int maximum_load_factor; 72 73 /* These are the keys. */ 74 tree * GTY ((length ("%h.number_of_slots"))) slots; 75 76 /* These are the values. values[i] is the the value corresponding 77 to slots[i]. */ 78 tree * GTY ((length ("%h.number_of_slots"))) values; 79 }; 80 81 /* Private functions used to resize the map. They may be called by 82 the inline functions when adding elements. */ 83 extern void 84 objc_map_private_grow (struct objc_map_private *map); 85 86 87 /** 88 ** The definition of a map. 89 **/ 90 typedef struct objc_map_private *objc_map_t; 91 92 93 /** 94 ** Creating a map. 95 **/ 96 97 /* objc_map_alloc_ggc() creates a new map which is under GGC. The initial 98 capacity must be specified as an argument; this is used to size the map 99 when it is created. */ 100 objc_map_t objc_map_alloc_ggc (size_t initial_capacity); 101 102 /** 103 ** Performance tuning. 104 **/ 105 106 /* Set a maximum load factor for the data structure. This is the main 107 tuning parameter to improve performance (at the expense of 108 memory). */ 109 void objc_map_set_maximum_load_factor (objc_map_t map, int number_between_zero_and_one_hundred); 110 111 /* Read the maximum load factor. */ 112 int objc_map_maximum_load_factor (objc_map_t map); 113 114 115 /** 116 ** Getting the value corresponding to a key. 117 **/ 118 119 /* This is the value returned by objc_map_get() when the value 120 corresponding to a key is not found. */ 121 #define OBJC_MAP_NOT_FOUND (tree)1 122 123 /* objc_map_get() returns the value associated with a certain key, 124 or OBJC_MAP_NOT_FOUND if there is no value associated with that key. 125 Note that you can also use it to simply check if the map contains a 126 pair with a certain key; just compare the result of calling 127 objc_map_get() to OBJC_MAP_NOT_FOUND. 128 129 It is essential to always check the results of the call to make 130 sure it is not OBJC_MAP_NOT_FOUND. 131 132 NULL is a valid value, so a key can be inserted into a map with 133 value NULL, and objc_map_get() will return NULL in that case. 134 So a result of NULL means that they key *was* found, and the value 135 associated with it was NULL. */ 136 static inline tree 137 objc_map_get (objc_map_t map, /* struct tree_identifier * */tree key) 138 { 139 /* The inline implementation is private and may change without notice. */ 140 objc_map_private_hash_t hash = IDENTIFIER_HASH_VALUE (key); 141 size_t i = hash & map->mask; 142 size_t j = 1; 143 144 if (map->slots[i] == OBJC_MAP_PRIVATE_EMPTY_SLOT) 145 return OBJC_MAP_NOT_FOUND; 146 147 if (map->slots[i] == key) 148 return map->values[i]; 149 150 while (1) 151 { 152 i = (i + j) & map->mask; 153 154 if (map->slots[i] == OBJC_MAP_PRIVATE_EMPTY_SLOT) 155 return OBJC_MAP_NOT_FOUND; 156 157 if (map->slots[i] == key) 158 return map->values[i]; 159 160 j++; 161 } 162 } 163 164 /* objc_map_put() puts a key/value pair into the map. If the map does 165 not contain the key, it is added to it with the specified value. 166 If the map already contains the key, the previous value is replaced 167 with the new one. 168 169 You can use any identifier as key, with the exception of NULL. 170 171 You can use any tree as value, including NULL. */ 172 static inline 173 void objc_map_put (objc_map_t map, /*struct tree_identifier * */tree key, tree value) 174 { 175 /* The inline implementation is private and may change without notice. */ 176 objc_map_private_hash_t hash = IDENTIFIER_HASH_VALUE (key); 177 size_t i, j = 0; 178 179 if (map->number_of_non_empty_slots == map->max_number_of_non_empty_slots) 180 objc_map_private_grow (map); 181 182 i = hash & map->mask; 183 184 while (1) 185 { 186 if (map->slots[i] == OBJC_MAP_PRIVATE_EMPTY_SLOT) 187 { 188 map->number_of_non_empty_slots++; 189 map->slots[i] = key; 190 map->values[i] = value; 191 return; 192 } 193 if (map->slots[i] == key) 194 { 195 map->values[i] = value; 196 return; 197 } 198 199 j++; 200 i = (i + j) & map->mask; 201 } 202 } 203 204 /** 205 ** Iterating over a map using an iterator. 206 **/ 207 208 /* When using iterators you can iterate directly on the elements in 209 the map, and take an action over each one. 210 211 Here is how you iterate over a hmap_pointer using iterators: 212 213 objc_map_iterator_t i; 214 215 objc_map_iterator_initialize (map, &i); 216 217 while (objc_map_iterator_move_to_next (map, &i)) 218 { 219 tree p = objc_map_iterator_current_key (map, i); 220 tree q = objc_map_iterator_current_value (map, i); 221 222 ... do something with p and q ... 223 } 224 225 You'll notice that the functions that modify the iterator (to 226 initialize it, or move it to the next element) take a pointer to it 227 as argument (as in "&i"), while the functions that only read its 228 state (to read the current key/value, or remove the current 229 key/value from the map) take it as a direct argument (as in "i"). 230 231 Note that all the objc_map_iterator_*() functions are inline and if 232 you follow the pattern above, the compiler should be able to inline 233 everything into a very efficient loop, roughly equivalent to 234 hand-writing a C loop that iterates directly onto the hmap_pointer 235 internal data structures. */ 236 237 /* A objc_map_iterator_t variable encapsulates the state of an 238 iteration. The fact that this is actually a size_t (pointing to 239 the index of the slot that we return next) is an internal, private 240 detail of the implementation and may change without notice. */ 241 typedef size_t objc_map_iterator_t; 242 243 /* Initialize an iterator to iterate over the specified objc_map. You 244 must use this before starting the iteration, to get a working 245 iterator. */ 246 static inline 247 void 248 objc_map_iterator_initialize (objc_map_t map ATTRIBUTE_UNUSED, objc_map_iterator_t *i) 249 { 250 /* The inline implementation is private and may change without notice. */ 251 /* This is trivial, but the same API would work to initialize more 252 complicated iterators. */ 253 *i = 0; 254 } 255 256 #define OBJC_MAP_FAILURE 0 257 #define OBJC_MAP_SUCCESS 1 258 259 /* Move the iterator to the next key/value pair, and return 260 OBJC_MAP_SUCCESS if there is such a key/value pair, and 261 OBJC_MAP_FAILURE if there are no more ones. The iterator must have 262 been initialized using objc_map_iterator_initialize(). Note that 263 because this function is modifying the iterator, you need to pass a 264 pointer to it. */ 265 static inline 266 int 267 objc_map_iterator_move_to_next (objc_map_t map, objc_map_iterator_t *i) 268 { 269 /* The inline implementation is private and may change without notice. */ 270 while (1) 271 { 272 void *slot; 273 if (*i == map->number_of_slots) 274 return OBJC_MAP_FAILURE; 275 276 slot = map->slots[*i]; 277 *i = *i + 1; 278 if (slot != OBJC_MAP_PRIVATE_EMPTY_SLOT) 279 return OBJC_MAP_SUCCESS; 280 } 281 } 282 283 /* Return the current key. You can only call it after you have called 284 objc_map_iterator_move_to_next() at least once (to move to the 285 first element), and only if the last call returned 286 OBJC_MAP_SUCCESS. The behaviour is otherwise undefined, probably a 287 segmentation fault. */ 288 static inline 289 tree 290 objc_map_iterator_current_key (objc_map_t map, objc_map_iterator_t i) 291 { 292 /* The inline implementation is private and may change without notice. */ 293 return map->slots[i - 1]; 294 } 295 296 /* Return the current value. You can only call it after you have 297 called objc_map_iterator_move_to_next() at least once (to move to 298 the first element), and only if the last call returned 299 OBJC_MAP_SUCCESS. The behaviour is otherwise undefined, probably a 300 segmentation fault. */ 301 static inline 302 tree 303 objc_map_iterator_current_value (objc_map_t map, objc_map_iterator_t i) 304 { 305 /* The inline implementation is private and may change without notice. */ 306 return map->values[i - 1]; 307 } 308 309 #endif /* OBJC_MAP_H */ 310