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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [pointer-set.c] - Blame information for rev 280

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Set operations on pointers
2
   Copyright (C) 2004, 2006, 2007 Free Software Foundation, Inc.
3
 
4
This file is part of GCC.
5
 
6
GCC is free software; you can redistribute it and/or modify
7
it under the terms of the GNU General Public License as published by
8
the Free Software Foundation; either version 3, or (at your option)
9
any later version.
10
 
11
GCC is distributed in the hope that it will be useful,
12
but WITHOUT ANY WARRANTY; without even the implied warranty of
13
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14
GNU General Public License for more details.
15
 
16
You should have received a copy of the GNU General Public License
17
along with GCC; see the file COPYING3.  If not see
18
<http://www.gnu.org/licenses/>.  */
19
 
20
#include "config.h"
21
#include "system.h"
22
#include "pointer-set.h"
23
 
24
/* A pointer set is represented as a simple open-addressing hash
25
   table.  Simplifications: The hash code is based on the value of the
26
   pointer, not what it points to.  The number of buckets is always a
27
   power of 2.  Null pointers are a reserved value.  Deletion is not
28
   supported (yet).  There is no mechanism for user control of hash
29
   function, equality comparison, initial size, or resizing policy.  */
30
 
31
struct pointer_set_t
32
{
33
  size_t log_slots;
34
  size_t n_slots;               /* n_slots = 2^log_slots */
35
  size_t n_elements;
36
 
37
  const void **slots;
38
};
39
 
40
/* Use the multiplicative method, as described in Knuth 6.4, to obtain
41
   a hash code for P in the range [0, MAX).  MAX == 2^LOGMAX.
42
 
43
   Summary of this method: Multiply p by some number A that's
44
   relatively prime to 2^sizeof(size_t).  The result is two words.
45
   Discard the most significant word, and return the most significant
46
   N bits of the least significant word.  As suggested by Knuth, our
47
   choice for A is the integer part of (ULONG_MAX + 1.0) / phi, where phi
48
   is the golden ratio.
49
 
50
   We don't need to do anything special for full-width multiplication
51
   because we're only interested in the least significant word of the
52
   product, and unsigned arithmetic in C is modulo the word size.  */
53
 
54
static inline size_t
55
hash1 (const void *p, unsigned long max, unsigned long logmax)
56
{
57
#if HOST_BITS_PER_LONG == 32
58
  const unsigned long A = 0x9e3779b9u;
59
#elif HOST_BITS_PER_LONG == 64
60
  const unsigned long A = 0x9e3779b97f4a7c16ul;
61
#else
62
  const unsigned long A
63
    = (ULONG_MAX + 1.0L) * 0.6180339887498948482045868343656381177203L;
64
#endif
65
  const unsigned long shift = HOST_BITS_PER_LONG - logmax;
66
 
67
  return ((A * (unsigned long) p) >> shift) & (max - 1);
68
}
69
 
70
/* Allocate an empty pointer set.  */
71
struct pointer_set_t *
72
pointer_set_create (void)
73
{
74
  struct pointer_set_t *result = XNEW (struct pointer_set_t);
75
 
76
  result->n_elements = 0;
77
  result->log_slots = 8;
78
  result->n_slots = (size_t) 1 << result->log_slots;
79
 
80
  result->slots = XCNEWVEC (const void *, result->n_slots);
81
  return result;
82
}
83
 
84
/* Reclaims all memory associated with PSET.  */
85
void
86
pointer_set_destroy (struct pointer_set_t *pset)
87
{
88
  XDELETEVEC (pset->slots);
89
  XDELETE (pset);
90
}
91
 
92
/* Returns nonzero if PSET contains P.  P must be nonnull.
93
 
94
   Collisions are resolved by linear probing.  */
95
int
96
pointer_set_contains (const struct pointer_set_t *pset, const void *p)
97
{
98
  size_t n = hash1 (p, pset->n_slots, pset->log_slots);
99
 
100
  while (true)
101
    {
102
      if (pset->slots[n] == p)
103
       return 1;
104
      else if (pset->slots[n] == 0)
105
       return 0;
106
      else
107
       {
108
         ++n;
109
         if (n == pset->n_slots)
110
           n = 0;
111
       }
112
    }
113
}
114
 
115
/* Subroutine of pointer_set_insert.  Return the insertion slot for P into
116
   an empty element of SLOTS, an array of length N_SLOTS.  */
117
static inline size_t
118
insert_aux (const void *p, const void **slots, size_t n_slots, size_t log_slots)
119
{
120
  size_t n = hash1 (p, n_slots, log_slots);
121
  while (true)
122
    {
123
      if (slots[n] == p || slots[n] == 0)
124
        return n;
125
      else
126
        {
127
          ++n;
128
          if (n == n_slots)
129
            n = 0;
130
        }
131
    }
132
}
133
 
134
/* Inserts P into PSET if it wasn't already there.  Returns nonzero
135
   if it was already there. P must be nonnull.  */
136
int
137
pointer_set_insert (struct pointer_set_t *pset, const void *p)
138
{
139
  size_t n;
140
 
141
  /* For simplicity, expand the set even if P is already there.  This can be
142
     superfluous but can happen at most once.  */
143
  if (pset->n_elements > pset->n_slots / 4)
144
    {
145
      size_t new_log_slots = pset->log_slots + 1;
146
      size_t new_n_slots = pset->n_slots * 2;
147
      const void **new_slots = XCNEWVEC (const void *, new_n_slots);
148
      size_t i;
149
 
150
      for (i = 0; i < pset->n_slots; ++i)
151
        {
152
          const void *value = pset->slots[i];
153
          n = insert_aux (value, new_slots, new_n_slots, new_log_slots);
154
          new_slots[n] = value;
155
        }
156
 
157
      XDELETEVEC (pset->slots);
158
      pset->n_slots = new_n_slots;
159
      pset->log_slots = new_log_slots;
160
      pset->slots = new_slots;
161
    }
162
 
163
  n = insert_aux (p, pset->slots, pset->n_slots, pset->log_slots);
164
  if (pset->slots[n])
165
    return 1;
166
 
167
  pset->slots[n] = p;
168
  ++pset->n_elements;
169
  return 0;
170
}
171
 
172
/* Pass each pointer in PSET to the function in FN, together with the fixed
173
   parameter DATA.  If FN returns false, the iteration stops.  */
174
 
175
void pointer_set_traverse (const struct pointer_set_t *pset,
176
                           bool (*fn) (const void *, void *), void *data)
177
{
178
  size_t i;
179
  for (i = 0; i < pset->n_slots; ++i)
180
    if (pset->slots[i] && !fn (pset->slots[i], data))
181
      break;
182
}
183
 
184
 
185
/* A pointer map is represented the same way as a pointer_set, so
186
   the hash code is based on the address of the key, rather than
187
   its contents.  Null keys are a reserved value.  Deletion is not
188
   supported (yet).  There is no mechanism for user control of hash
189
   function, equality comparison, initial size, or resizing policy.  */
190
 
191
struct pointer_map_t
192
{
193
  size_t log_slots;
194
  size_t n_slots;               /* n_slots = 2^log_slots */
195
  size_t n_elements;
196
 
197
  const void **keys;
198
  void **values;
199
};
200
 
201
/* Allocate an empty pointer map.  */
202
struct pointer_map_t *
203
pointer_map_create (void)
204
{
205
  struct pointer_map_t *result = XNEW (struct pointer_map_t);
206
 
207
  result->n_elements = 0;
208
  result->log_slots = 8;
209
  result->n_slots = (size_t) 1 << result->log_slots;
210
 
211
  result->keys = XCNEWVEC (const void *, result->n_slots);
212
  result->values = XCNEWVEC (void *, result->n_slots);
213
  return result;
214
}
215
 
216
/* Reclaims all memory associated with PMAP.  */
217
void pointer_map_destroy (struct pointer_map_t *pmap)
218
{
219
  XDELETEVEC (pmap->keys);
220
  XDELETEVEC (pmap->values);
221
  XDELETE (pmap);
222
}
223
 
224
/* Returns a pointer to the value to which P maps, if PMAP contains P.  P
225
   must be nonnull.  Return NULL if PMAP does not contain P.
226
 
227
   Collisions are resolved by linear probing.  */
228
void **
229
pointer_map_contains (const struct pointer_map_t *pmap, const void *p)
230
{
231
  size_t n = hash1 (p, pmap->n_slots, pmap->log_slots);
232
 
233
  while (true)
234
    {
235
      if (pmap->keys[n] == p)
236
        return &pmap->values[n];
237
      else if (pmap->keys[n] == 0)
238
        return NULL;
239
      else
240
       {
241
         ++n;
242
         if (n == pmap->n_slots)
243
           n = 0;
244
       }
245
    }
246
}
247
 
248
/* Inserts P into PMAP if it wasn't already there.  Returns a pointer
249
   to the value.  P must be nonnull.  */
250
void **
251
pointer_map_insert (struct pointer_map_t *pmap, const void *p)
252
{
253
  size_t n;
254
 
255
  /* For simplicity, expand the map even if P is already there.  This can be
256
     superfluous but can happen at most once.  */
257
  if (pmap->n_elements > pmap->n_slots / 4)
258
    {
259
      size_t new_log_slots = pmap->log_slots + 1;
260
      size_t new_n_slots = pmap->n_slots * 2;
261
      const void **new_keys = XCNEWVEC (const void *, new_n_slots);
262
      void **new_values = XCNEWVEC (void *, new_n_slots);
263
      size_t i;
264
 
265
      for (i = 0; i < pmap->n_slots; ++i)
266
        if (pmap->keys[i])
267
          {
268
            const void *key = pmap->keys[i];
269
            n = insert_aux (key, new_keys, new_n_slots, new_log_slots);
270
            new_keys[n] = key;
271
            new_values[n] = pmap->values[i];
272
          }
273
 
274
      XDELETEVEC (pmap->keys);
275
      XDELETEVEC (pmap->values);
276
      pmap->n_slots = new_n_slots;
277
      pmap->log_slots = new_log_slots;
278
      pmap->keys = new_keys;
279
      pmap->values = new_values;
280
    }
281
 
282
  n = insert_aux (p, pmap->keys, pmap->n_slots, pmap->log_slots);
283
  if (!pmap->keys[n])
284
    {
285
      ++pmap->n_elements;
286
      pmap->keys[n] = p;
287
    }
288
 
289
  return &pmap->values[n];
290
}
291
 
292
/* Pass each pointer in PMAP to the function in FN, together with the pointer
293
   to the value and the fixed parameter DATA.  If FN returns false, the
294
   iteration stops.  */
295
 
296
void pointer_map_traverse (const struct pointer_map_t *pmap,
297
                           bool (*fn) (const void *, void **, void *), void *data)
298
{
299
  size_t i;
300
  for (i = 0; i < pmap->n_slots; ++i)
301
    if (pmap->keys[i] && !fn (pmap->keys[i], &pmap->values[i], data))
302
      break;
303
}

powered by: WebSVN 2.1.0

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