gcc/objc/objc-map.h

   1 /* objc-map.h -- Implementation of map data structures for ObjC compiler
   2    Copyright (C) 2011-2013 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 */