source: arduino-1-6-7/trunk/fuentes/arduino-ide-amd64/hardware/tools/avr/lib/gcc/avr/4.9.2/plugin/include/pointer-set.h @ 4837

Last change on this file since 4837 was 4837, checked in by daduve, 3 years ago

Adding new version

File size: 4.9 KB
Line 
1/* Set operations on pointers
2   Copyright (C) 2004-2014 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3.  If not see
18<http://www.gnu.org/licenses/>.  */
19
20#ifndef POINTER_SET_H
21#define POINTER_SET_H
22
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
31struct 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  const void **slots;
37};
38
39struct pointer_set_t *pointer_set_create (void);
40void pointer_set_destroy (struct pointer_set_t *pset);
41int pointer_set_contains (const struct pointer_set_t *pset, const void *p);
42int pointer_set_insert (struct pointer_set_t *pset, const void *p);
43void pointer_set_traverse (const struct pointer_set_t *,
44                           bool (*) (const void *, void *),
45                           void *);
46bool pointer_set_lookup (const pointer_set_t *, const void *, size_t *);
47
48/* A pointer map is represented the same way as a pointer_set, so
49   the hash code is based on the address of the key, rather than
50   its contents.  Null keys are a reserved value.  Deletion is not
51   supported (yet).  There is no mechanism for user control of hash
52   function, equality comparison, initial size, or resizing policy.  */
53
54template <typename T>
55class pointer_map : protected pointer_set_t
56{
57  T *values;
58
59public:
60  pointer_map ();
61  ~pointer_map ();
62  T *contains (const void *p);
63  T *insert (const void *p, bool *existed_p = NULL);
64  void traverse (bool (*fn) (const void *, T *, void *), void *data);
65};
66
67/* Allocate an empty pointer map.  */
68template <typename T>
69pointer_map<T>::pointer_map (void)
70{
71  n_elements = 0;
72  log_slots = 8;
73  n_slots = (size_t) 1 << log_slots;
74
75  slots = XCNEWVEC (const void *, n_slots);
76  values = XNEWVEC (T, n_slots);
77}
78
79/* Reclaims all memory associated with PMAP.  */
80template <typename T>
81pointer_map<T>::~pointer_map (void)
82{
83  XDELETEVEC (slots);
84  XDELETEVEC (values);
85}
86
87/* Returns a pointer to the value to which P maps, if PMAP contains P.  P
88   must be nonnull.  Return NULL if PMAP does not contain P.
89
90   Collisions are resolved by linear probing.  */
91template <typename T>
92T *
93pointer_map<T>::contains (const void *p)
94{
95  size_t n;
96  if (!pointer_set_lookup (this, p, &n))
97    return NULL;
98  return &values[n];
99}
100
101/* Inserts P into PMAP if it wasn't already there.  Returns a pointer
102   to the value.  P must be nonnull.  */
103template <typename T>
104T *
105pointer_map<T>::insert (const void *p, bool *existed_p)
106{
107  size_t n;
108
109  /* For simplicity, expand the map even if P is already there.  This can be
110     superfluous but can happen at most once.  */
111  /* ???  Fugly that we have to inline that here.  */
112  if (n_elements > n_slots / 4)
113    {
114      size_t old_n_slots = n_slots;
115      const void **old_keys = slots;
116      T *old_values = values;
117      log_slots = log_slots + 1;
118      n_slots = n_slots * 2;
119      slots = XCNEWVEC (const void *, n_slots);
120      values = XNEWVEC (T, n_slots);
121      for (size_t i = 0; i < old_n_slots; ++i)
122        if (old_keys[i])
123          {
124            const void *key = old_keys[i];
125            pointer_set_lookup (this, key, &n);
126            slots[n] = key;
127            values[n] = old_values[i];
128          }
129      XDELETEVEC (old_keys);
130      XDELETEVEC (old_values);
131    }
132
133  if (!pointer_set_lookup (this, p, &n))
134    {
135      ++n_elements;
136      slots[n] = p;
137      if (existed_p)
138        *existed_p = false;
139    }
140  else if (existed_p)
141    *existed_p = true;
142
143  return &values[n];
144}
145
146/* Pass each pointer in PMAP to the function in FN, together with the pointer
147   to the value and the fixed parameter DATA.  If FN returns false, the
148   iteration stops.  */
149
150template <class T>
151void
152pointer_map<T>::traverse (bool (*fn) (const void *, T *, void *), void *data)
153{
154  for (size_t i = 0; i < n_slots; ++i)
155    if (slots[i] && !fn (slots[i], &values[i], data))
156      break;
157}
158
159
160struct pointer_map_t;
161pointer_map_t *pointer_map_create (void);
162void pointer_map_destroy (pointer_map_t *pmap);
163
164void **pointer_map_contains (const pointer_map_t *pmap, const void *p);
165void **pointer_map_insert (pointer_map_t *pmap, const void *p);
166void pointer_map_traverse (const pointer_map_t *,
167                           bool (*) (const void *, void **, void *), void *);
168
169
170#endif  /* POINTER_SET_H  */
Note: See TracBrowser for help on using the repository browser.