OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [objc/] [objc-map.h] - Blame information for rev 717

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 717 jeremybenn
/* 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 */

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.