HashSet.h revision 759d502e
1/*
2 * Copyright 2004-2009, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * Copyright 2019, Haiku, Inc. All rights reserved.
4 * Distributed under the terms of the MIT License.
5 */
6#ifndef HASH_SET_H
7#define HASH_SET_H
8
9#include <OpenHashTable.h>
10#include <Locker.h>
11
12#include "AutoLocker.h"
13
14
15namespace BPrivate {
16
17
18// HashSetElement
19template<typename Key>
20class HashSetElement {
21private:
22	typedef HashSetElement<Key> Element;
23
24public:
25	HashSetElement()
26		:
27		fKey(),
28		fNext(NULL)
29	{
30	}
31
32	HashSetElement(const Key& key)
33		:
34		fKey(key),
35		fNext(NULL)
36	{
37	}
38
39	Key				fKey;
40	HashSetElement*	fNext;
41};
42
43
44// HashSetTableDefinition
45template<typename Key>
46struct HashSetTableDefinition {
47	typedef Key					KeyType;
48	typedef	HashSetElement<Key>	ValueType;
49
50	size_t HashKey(const KeyType& key) const
51		{ return key.GetHashCode(); }
52	size_t Hash(const ValueType* value) const
53		{ return HashKey(value->fKey); }
54	bool Compare(const KeyType& key, const ValueType* value) const
55		{ return value->fKey == key; }
56	ValueType*& GetLink(ValueType* value) const
57		{ return value->fNext; }
58};
59
60
61// HashSet
62template<typename Key>
63class HashSet {
64public:
65	class Iterator {
66	private:
67		typedef HashSetElement<Key>	Element;
68	public:
69		Iterator(const Iterator& other)
70			:
71			fSet(other.fSet),
72			fIterator(other.fIterator),
73			fElement(other.fElement)
74		{
75		}
76
77		bool HasNext() const
78		{
79			return fIterator.HasNext();
80		}
81
82		Key Next()
83		{
84			fElement = fIterator.Next();
85			if (fElement == NULL)
86				return Key();
87
88			return fElement->fKey;
89		}
90
91		bool Remove()
92		{
93			if (fElement == NULL)
94				return false;
95
96			fSet->fTable.RemoveUnchecked(fElement);
97			delete fElement;
98			fElement = NULL;
99
100			return true;
101		}
102
103		Iterator& operator=(const Iterator& other)
104		{
105			fSet = other.fSet;
106			fIterator = other.fIterator;
107			fElement = other.fElement;
108			return *this;
109		}
110
111	private:
112		Iterator(HashSet<Key>* set)
113			:
114			fSet(set),
115			fIterator(set->fTable.GetIterator()),
116			fElement(NULL)
117		{
118		}
119
120	private:
121		typedef BOpenHashTable<HashSetTableDefinition<Key> > ElementTable;
122
123		HashSet<Key>*					fSet;
124		typename ElementTable::Iterator fIterator;
125		Element*						fElement;
126
127	private:
128		friend class HashSet<Key>;
129	};
130
131	HashSet();
132	~HashSet();
133
134	status_t InitCheck() const;
135
136	status_t Add(const Key& key);
137	bool Remove(const Key& key);
138	void Clear();
139	bool Contains(const Key& key) const;
140
141	int32 Size() const;
142
143	Iterator GetIterator();
144
145protected:
146	typedef BOpenHashTable<HashSetTableDefinition<Key> > ElementTable;
147	typedef HashSetElement<Key>	Element;
148	friend class Iterator;
149
150protected:
151	ElementTable	fTable;
152};
153
154
155// SynchronizedHashSet
156template<typename Key, typename Locker = BLocker>
157class SynchronizedHashSet : public Locker {
158public:
159	typedef typename HashSet<Key>::Iterator Iterator;
160
161	SynchronizedHashSet() : Locker("synchronized hash set")	{}
162	~SynchronizedHashSet()	{ Locker::Lock(); }
163
164	status_t InitCheck() const
165	{
166		return fSet.InitCheck();
167	}
168
169	status_t Add(const Key& key)
170	{
171		MapLocker locker(this);
172		if (!locker.IsLocked())
173			return B_ERROR;
174		return fSet.Add(key);
175	}
176
177	bool Remove(const Key& key)
178	{
179		MapLocker locker(this);
180		if (!locker.IsLocked())
181			return false;
182		return fSet.Remove(key);
183	}
184
185	void Clear()
186	{
187		MapLocker locker(this);
188		fSet.Clear();
189	}
190
191	bool Contains(const Key& key) const
192	{
193		const Locker* lock = this;
194		MapLocker locker(const_cast<Locker*>(lock));
195		if (!locker.IsLocked())
196			return false;
197		return fSet.Contains(key);
198	}
199
200	int32 Size() const
201	{
202		const Locker* lock = this;
203		MapLocker locker(const_cast<Locker*>(lock));
204		return fSet.Size();
205	}
206
207	Iterator GetIterator()
208	{
209		return fSet.GetIterator();
210	}
211
212	// for debugging only
213	const HashSet<Key>& GetUnsynchronizedSet() const	{ return fSet; }
214	HashSet<Key>& GetUnsynchronizedSet()				{ return fSet; }
215
216protected:
217	typedef AutoLocker<Locker> MapLocker;
218
219	HashSet<Key>	fSet;
220};
221
222
223// HashSet
224
225// constructor
226template<typename Key>
227HashSet<Key>::HashSet()
228	:
229	fTable()
230{
231	fTable.Init();
232}
233
234
235// destructor
236template<typename Key>
237HashSet<Key>::~HashSet()
238{
239	Clear();
240}
241
242
243// InitCheck
244template<typename Key>
245status_t
246HashSet<Key>::InitCheck() const
247{
248	return (fTable.TableSize() > 0 ? B_OK : B_NO_MEMORY);
249}
250
251
252// Add
253template<typename Key>
254status_t
255HashSet<Key>::Add(const Key& key)
256{
257	Element* element = fTable.Lookup(key);
258	if (element) {
259		// already contains the value
260		return B_OK;
261	}
262
263	// does not contain the key yet: create an element and add it
264	element = new(std::nothrow) Element(key);
265	if (!element)
266		return B_NO_MEMORY;
267
268	status_t error = fTable.Insert(element);
269	if (error != B_OK)
270		delete element;
271
272	return error;
273}
274
275
276// Remove
277template<typename Key>
278bool
279HashSet<Key>::Remove(const Key& key)
280{
281	Element* element = fTable.Lookup(key);
282	if (element == NULL)
283		return false;
284
285	fTable.Remove(element);
286	delete element;
287
288	return true;
289}
290
291
292// Clear
293template<typename Key>
294void
295HashSet<Key>::Clear()
296{
297	// clear the table and delete the elements
298	Element* element = fTable.Clear(true);
299	while (element != NULL) {
300		Element* next = element->fNext;
301		delete element;
302		element = next;
303	}
304}
305
306
307// Contains
308template<typename Key>
309bool
310HashSet<Key>::Contains(const Key& key) const
311{
312	return fTable.Lookup(key) != NULL;
313}
314
315
316// Size
317template<typename Key>
318int32
319HashSet<Key>::Size() const
320{
321	return fTable.CountElements();
322}
323
324
325// GetIterator
326template<typename Key>
327typename HashSet<Key>::Iterator
328HashSet<Key>::GetIterator()
329{
330	return Iterator(this);
331}
332
333} // namespace BPrivate
334
335using BPrivate::HashSet;
336
337#endif	// HASH_SET_H
338