]>
Commit | Line | Data |
---|---|---|
431205b7 | 1 | /* A type-safe hash set. |
f1717362 | 2 | Copyright (C) 2014-2016 Free Software Foundation, Inc. |
431205b7 | 3 | |
4 | This file is part of GCC. | |
5 | ||
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. | |
10 | ||
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. | |
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 | ||
21 | #ifndef hash_set_h | |
22 | #define hash_set_h | |
23 | ||
28544f39 | 24 | template<typename KeyId, typename Traits = default_hash_traits<KeyId> > |
431205b7 | 25 | class hash_set |
26 | { | |
431205b7 | 27 | public: |
28544f39 | 28 | typedef typename Traits::value_type Key; |
0ff42de5 | 29 | explicit hash_set (size_t n = 13, bool ggc = false CXX_MEM_STAT_INFO) |
e3343fd6 | 30 | : m_table (n, ggc, GATHER_STATISTICS, HASH_SET_ORIGIN PASS_MEM_STAT) {} |
8f359205 | 31 | |
32 | /* Create a hash_set in gc memory with space for at least n elements. */ | |
33 | ||
34 | static hash_set * | |
35 | create_ggc (size_t n) | |
36 | { | |
37 | hash_set *set = ggc_alloc<hash_set> (); | |
38 | new (set) hash_set (n, true); | |
39 | return set; | |
40 | } | |
431205b7 | 41 | |
42 | /* If key k isn't already in the map add it to the map, and | |
43 | return false. Otherwise return true. */ | |
44 | ||
45 | bool add (const Key &k) | |
46 | { | |
f581cceb | 47 | Key *e = m_table.find_slot_with_hash (k, Traits::hash (k), INSERT); |
48 | bool existed = !Traits::is_empty (*e); | |
431205b7 | 49 | if (!existed) |
f581cceb | 50 | *e = k; |
431205b7 | 51 | |
52 | return existed; | |
53 | } | |
54 | ||
55 | /* if the passed in key is in the map return its value otherwise NULL. */ | |
56 | ||
57 | bool contains (const Key &k) | |
58 | { | |
f581cceb | 59 | Key &e = m_table.find_with_hash (k, Traits::hash (k)); |
60 | return !Traits::is_empty (e); | |
431205b7 | 61 | } |
62 | ||
a3c990e4 | 63 | void remove (const Key &k) |
64 | { | |
65 | m_table.remove_elt_with_hash (k, Traits::hash (k)); | |
66 | } | |
67 | ||
431205b7 | 68 | /* Call the call back on each pair of key and value with the passed in |
69 | arg. */ | |
70 | ||
2479ea68 | 71 | template<typename Arg, bool (*f)(const typename Traits::value_type &, Arg)> |
431205b7 | 72 | void traverse (Arg a) const |
73 | { | |
f581cceb | 74 | for (typename hash_table<Traits>::iterator iter = m_table.begin (); |
431205b7 | 75 | iter != m_table.end (); ++iter) |
f581cceb | 76 | f (*iter, a); |
431205b7 | 77 | } |
78 | ||
8f359205 | 79 | /* Return the number of elements in the set. */ |
80 | ||
81 | size_t elements () const { return m_table.elements (); } | |
82 | ||
a3c990e4 | 83 | class iterator |
84 | { | |
85 | public: | |
86 | explicit iterator (const typename hash_table<Traits>::iterator &iter) : | |
87 | m_iter (iter) {} | |
88 | ||
89 | iterator &operator++ () | |
90 | { | |
91 | ++m_iter; | |
92 | return *this; | |
93 | } | |
94 | ||
95 | Key | |
96 | operator* () | |
97 | { | |
98 | return *m_iter; | |
99 | } | |
100 | ||
101 | bool | |
102 | operator != (const iterator &other) const | |
103 | { | |
104 | return m_iter != other.m_iter; | |
105 | } | |
106 | ||
107 | private: | |
108 | typename hash_table<Traits>::iterator m_iter; | |
109 | }; | |
110 | ||
111 | /* Standard iterator retrieval methods. */ | |
112 | ||
113 | iterator begin () const { return iterator (m_table.begin ()); } | |
114 | iterator end () const { return iterator (m_table.end ()); } | |
115 | ||
116 | ||
431205b7 | 117 | private: |
8f359205 | 118 | |
119 | template<typename T, typename U> friend void gt_ggc_mx (hash_set<T, U> *); | |
120 | template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *); | |
121 | template<typename T, typename U> friend void gt_pch_nx (hash_set<T, U> *, gt_pointer_operator, void *); | |
122 | ||
f581cceb | 123 | hash_table<Traits> m_table; |
431205b7 | 124 | }; |
125 | ||
8f359205 | 126 | /* ggc marking routines. */ |
127 | ||
128 | template<typename K, typename H> | |
129 | static inline void | |
130 | gt_ggc_mx (hash_set<K, H> *h) | |
131 | { | |
132 | gt_ggc_mx (&h->m_table); | |
133 | } | |
134 | ||
135 | template<typename K, typename H> | |
136 | static inline void | |
137 | gt_pch_nx (hash_set<K, H> *h) | |
138 | { | |
139 | gt_pch_nx (&h->m_table); | |
140 | } | |
141 | ||
142 | template<typename K, typename H> | |
143 | static inline void | |
144 | gt_pch_nx (hash_set<K, H> *h, gt_pointer_operator op, void *cookie) | |
145 | { | |
146 | op (&h->m_table.m_entries, cookie); | |
147 | } | |
148 | ||
431205b7 | 149 | #endif |