Mercurial > hg > CbC > CbC_gcc
comparison gcc/hash-set.h @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
1 /* A type-safe hash set. | |
2 Copyright (C) 2014-2017 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 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 | |
24 template<typename KeyId, typename Traits = default_hash_traits<KeyId> > | |
25 class hash_set | |
26 { | |
27 public: | |
28 typedef typename Traits::value_type Key; | |
29 explicit hash_set (size_t n = 13, bool ggc = false CXX_MEM_STAT_INFO) | |
30 : m_table (n, ggc, GATHER_STATISTICS, HASH_SET_ORIGIN PASS_MEM_STAT) {} | |
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 } | |
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 { | |
47 Key *e = m_table.find_slot_with_hash (k, Traits::hash (k), INSERT); | |
48 bool existed = !Traits::is_empty (*e); | |
49 if (!existed) | |
50 *e = k; | |
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 { | |
59 Key &e = m_table.find_with_hash (k, Traits::hash (k)); | |
60 return !Traits::is_empty (e); | |
61 } | |
62 | |
63 void remove (const Key &k) | |
64 { | |
65 m_table.remove_elt_with_hash (k, Traits::hash (k)); | |
66 } | |
67 | |
68 /* Call the call back on each pair of key and value with the passed in | |
69 arg. */ | |
70 | |
71 template<typename Arg, bool (*f)(const typename Traits::value_type &, Arg)> | |
72 void traverse (Arg a) const | |
73 { | |
74 for (typename hash_table<Traits>::iterator iter = m_table.begin (); | |
75 iter != m_table.end (); ++iter) | |
76 f (*iter, a); | |
77 } | |
78 | |
79 /* Return the number of elements in the set. */ | |
80 | |
81 size_t elements () const { return m_table.elements (); } | |
82 | |
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 | |
117 private: | |
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 | |
123 hash_table<Traits> m_table; | |
124 }; | |
125 | |
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 | |
149 #endif |