* config/i386/i386.c (ix86_adjust_stack_and_probe_stack_clash): New.
[official-gcc.git] / gcc / hash-map.h
blob73f1c5427a0b9be426fbc4d2247d8f88ab753825
1 /* A type-safe hash map.
2 Copyright (C) 2014-2017 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
9 version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 for more details.
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/>. */
21 #ifndef hash_map_h
22 #define hash_map_h
24 template<typename KeyId, typename Value,
25 typename Traits>
26 class GTY((user)) hash_map
28 typedef typename Traits::key_type Key;
29 struct hash_entry
31 Key m_key;
32 Value m_value;
34 typedef hash_entry value_type;
35 typedef Key compare_type;
37 static hashval_t hash (const hash_entry &e)
39 return Traits::hash (e.m_key);
42 static bool equal (const hash_entry &a, const Key &b)
44 return Traits::equal_keys (a.m_key, b);
47 static void remove (hash_entry &e) { Traits::remove (e); }
49 static void mark_deleted (hash_entry &e) { Traits::mark_deleted (e); }
51 static bool is_deleted (const hash_entry &e)
53 return Traits::is_deleted (e);
56 static void mark_empty (hash_entry &e) { Traits::mark_empty (e); }
57 static bool is_empty (const hash_entry &e) { return Traits::is_empty (e); }
59 static void ggc_mx (hash_entry &e)
61 gt_ggc_mx (e.m_key);
62 gt_ggc_mx (e.m_value);
65 static void pch_nx (hash_entry &e)
67 gt_pch_nx (e.m_key);
68 gt_pch_nx (e.m_value);
71 static void pch_nx (hash_entry &e, gt_pointer_operator op, void *c)
73 pch_nx_helper (e.m_key, op, c);
74 pch_nx_helper (e.m_value, op, c);
77 private:
78 template<typename T>
79 static void
80 pch_nx_helper (T &x, gt_pointer_operator op, void *cookie)
82 gt_pch_nx (&x, op, cookie);
85 static void
86 pch_nx_helper (int, gt_pointer_operator, void *)
90 static void
91 pch_nx_helper (unsigned int, gt_pointer_operator, void *)
95 static void
96 pch_nx_helper (bool, gt_pointer_operator, void *)
100 template<typename T>
101 static void
102 pch_nx_helper (T *&x, gt_pointer_operator op, void *cookie)
104 op (&x, cookie);
108 public:
109 explicit hash_map (size_t n = 13, bool ggc = false,
110 bool gather_mem_stats = GATHER_STATISTICS
111 CXX_MEM_STAT_INFO)
112 : m_table (n, ggc, gather_mem_stats, HASH_MAP_ORIGIN PASS_MEM_STAT) {}
114 explicit hash_map (const hash_map &h, bool ggc = false,
115 bool gather_mem_stats = GATHER_STATISTICS
116 CXX_MEM_STAT_INFO)
117 : m_table (h.m_table, ggc, gather_mem_stats,
118 HASH_MAP_ORIGIN PASS_MEM_STAT) {}
120 /* Create a hash_map in ggc memory. */
121 static hash_map *create_ggc (size_t size,
122 bool gather_mem_stats = GATHER_STATISTICS
123 CXX_MEM_STAT_INFO)
125 hash_map *map = ggc_alloc<hash_map> ();
126 new (map) hash_map (size, true, gather_mem_stats PASS_MEM_STAT);
127 return map;
130 /* If key k isn't already in the map add key k with value v to the map, and
131 return false. Otherwise set the value of the entry for key k to be v and
132 return true. */
134 bool put (const Key &k, const Value &v)
136 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
137 INSERT);
138 bool existed = !hash_entry::is_empty (*e);
139 if (!existed)
140 e->m_key = k;
142 e->m_value = v;
143 return existed;
146 /* if the passed in key is in the map return its value otherwise NULL. */
148 Value *get (const Key &k)
150 hash_entry &e = m_table.find_with_hash (k, Traits::hash (k));
151 return Traits::is_empty (e) ? NULL : &e.m_value;
154 /* Return a reference to the value for the passed in key, creating the entry
155 if it doesn't already exist. If existed is not NULL then it is set to false
156 if the key was not previously in the map, and true otherwise. */
158 Value &get_or_insert (const Key &k, bool *existed = NULL)
160 hash_entry *e = m_table.find_slot_with_hash (k, Traits::hash (k),
161 INSERT);
162 bool ins = Traits::is_empty (*e);
163 if (ins)
164 e->m_key = k;
166 if (existed != NULL)
167 *existed = !ins;
169 return e->m_value;
172 void remove (const Key &k)
174 m_table.remove_elt_with_hash (k, Traits::hash (k));
177 /* Call the call back on each pair of key and value with the passed in
178 arg. */
180 template<typename Arg, bool (*f)(const typename Traits::key_type &,
181 const Value &, Arg)>
182 void traverse (Arg a) const
184 for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
185 iter != m_table.end (); ++iter)
186 f ((*iter).m_key, (*iter).m_value, a);
189 template<typename Arg, bool (*f)(const typename Traits::key_type &,
190 Value *, Arg)>
191 void traverse (Arg a) const
193 for (typename hash_table<hash_entry>::iterator iter = m_table.begin ();
194 iter != m_table.end (); ++iter)
195 if (!f ((*iter).m_key, &(*iter).m_value, a))
196 break;
199 size_t elements () const { return m_table.elements (); }
201 void empty () { m_table.empty(); }
203 class iterator
205 public:
206 explicit iterator (const typename hash_table<hash_entry>::iterator &iter) :
207 m_iter (iter) {}
209 iterator &operator++ ()
211 ++m_iter;
212 return *this;
215 std::pair<Key, Value> operator* ()
217 hash_entry &e = *m_iter;
218 return std::pair<Key, Value> (e.m_key, e.m_value);
221 bool
222 operator != (const iterator &other) const
224 return m_iter != other.m_iter;
227 private:
228 typename hash_table<hash_entry>::iterator m_iter;
231 /* Standard iterator retrieval methods. */
233 iterator begin () const { return iterator (m_table.begin ()); }
234 iterator end () const { return iterator (m_table.end ()); }
236 private:
238 template<typename T, typename U, typename V> friend void gt_ggc_mx (hash_map<T, U, V> *);
239 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *);
240 template<typename T, typename U, typename V> friend void gt_pch_nx (hash_map<T, U, V> *, gt_pointer_operator, void *);
242 hash_table<hash_entry> m_table;
245 /* ggc marking routines. */
247 template<typename K, typename V, typename H>
248 static inline void
249 gt_ggc_mx (hash_map<K, V, H> *h)
251 gt_ggc_mx (&h->m_table);
254 template<typename K, typename V, typename H>
255 static inline void
256 gt_pch_nx (hash_map<K, V, H> *h)
258 gt_pch_nx (&h->m_table);
261 template<typename K, typename V, typename H>
262 static inline void
263 gt_pch_nx (hash_map<K, V, H> *h, gt_pointer_operator op, void *cookie)
265 op (&h->m_table.m_entries, cookie);
268 #endif