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		Iterator& operator=(const Iterator& other)
92		{
93			fSet = other.fSet;
94			fIterator = other.fIterator;
95			fElement = other.fElement;
96			return *this;
97		}
98
99	private:
100		Iterator(const HashSet<Key>* set)
101			:
102			fSet(set),
103			fIterator(set->fTable.GetIterator()),
104			fElement(NULL)
105		{
106		}
107
108	private:
109		typedef BOpenHashTable<HashSetTableDefinition<Key> > ElementTable;
110
111		const HashSet<Key>*				fSet;
112		typename ElementTable::Iterator fIterator;
113		Element*						fElement;
114
115	private:
116		friend class HashSet<Key>;
117	};
118
119	HashSet();
120	~HashSet();
121
122	status_t InitCheck() const;
123
124	status_t Add(const Key& key);
125	bool Remove(const Key& key);
126	bool Remove(Iterator& it);
127	void Clear();
128	bool Contains(const Key& key) const;
129
130	int32 Size() const;
131
132	Iterator GetIterator() const;
133
134protected:
135	typedef BOpenHashTable<HashSetTableDefinition<Key> > ElementTable;
136	typedef HashSetElement<Key>	Element;
137	friend class Iterator;
138
139protected:
140	ElementTable	fTable;
141};
142
143
144// SynchronizedHashSet
145template<typename Key, typename Locker = BLocker>
146class SynchronizedHashSet : public Locker {
147public:
148	typedef typename HashSet<Key>::Iterator Iterator;
149
150	SynchronizedHashSet() : Locker("synchronized hash set")	{}
151	~SynchronizedHashSet()	{ Locker::Lock(); }
152
153	status_t InitCheck() const
154	{
155		return fSet.InitCheck();
156	}
157
158	status_t Add(const Key& key)
159	{
160		MapLocker locker(this);
161		if (!locker.IsLocked())
162			return B_ERROR;
163		return fSet.Add(key);
164	}
165
166	bool Remove(const Key& key)
167	{
168		MapLocker locker(this);
169		if (!locker.IsLocked())
170			return false;
171		return fSet.Remove(key);
172	}
173
174	void Clear()
175	{
176		MapLocker locker(this);
177		fSet.Clear();
178	}
179
180	bool Contains(const Key& key) const
181	{
182		const Locker* lock = this;
183		MapLocker locker(const_cast<Locker*>(lock));
184		if (!locker.IsLocked())
185			return false;
186		return fSet.Contains(key);
187	}
188
189	int32 Size() const
190	{
191		const Locker* lock = this;
192		MapLocker locker(const_cast<Locker*>(lock));
193		return fSet.Size();
194	}
195
196	Iterator GetIterator() const
197	{
198		return fSet.GetIterator();
199	}
200
201	// for debugging only
202	const HashSet<Key>& GetUnsynchronizedSet() const	{ return fSet; }
203	HashSet<Key>& GetUnsynchronizedSet()				{ return fSet; }
204
205protected:
206	typedef AutoLocker<Locker> MapLocker;
207
208	HashSet<Key>	fSet;
209};
210
211
212// HashSet
213
214// constructor
215template<typename Key>
216HashSet<Key>::HashSet()
217	:
218	fTable()
219{
220	fTable.Init();
221}
222
223
224// destructor
225template<typename Key>
226HashSet<Key>::~HashSet()
227{
228	Clear();
229}
230
231
232// InitCheck
233template<typename Key>
234status_t
235HashSet<Key>::InitCheck() const
236{
237	return (fTable.TableSize() > 0 ? B_OK : B_NO_MEMORY);
238}
239
240
241// Add
242template<typename Key>
243status_t
244HashSet<Key>::Add(const Key& key)
245{
246	Element* element = fTable.Lookup(key);
247	if (element) {
248		// already contains the value
249		return B_OK;
250	}
251
252	// does not contain the key yet: create an element and add it
253	element = new(std::nothrow) Element(key);
254	if (!element)
255		return B_NO_MEMORY;
256
257	status_t error = fTable.Insert(element);
258	if (error != B_OK)
259		delete element;
260
261	return error;
262}
263
264
265// Remove
266template<typename Key>
267bool
268HashSet<Key>::Remove(const Key& key)
269{
270	Element* element = fTable.Lookup(key);
271	if (element == NULL)
272		return false;
273
274	fTable.Remove(element);
275	delete element;
276
277	return true;
278}
279
280
281// Remove
282template<typename Key>
283bool
284HashSet<Key>::Remove(Iterator& it)
285{
286	Element* element = it.fElement;
287	if (element == NULL)
288		return false;
289
290	fTable.RemoveUnchecked(element);
291	delete element;
292	it.fElement = NULL;
293
294	return true;
295}
296
297
298// Clear
299template<typename Key>
300void
301HashSet<Key>::Clear()
302{
303	// clear the table and delete the elements
304	Element* element = fTable.Clear(true);
305	while (element != NULL) {
306		Element* next = element->fNext;
307		delete element;
308		element = next;
309	}
310}
311
312
313// Contains
314template<typename Key>
315bool
316HashSet<Key>::Contains(const Key& key) const
317{
318	return fTable.Lookup(key) != NULL;
319}
320
321
322// Size
323template<typename Key>
324int32
325HashSet<Key>::Size() const
326{
327	return fTable.CountElements();
328}
329
330
331// GetIterator
332template<typename Key>
333typename HashSet<Key>::Iterator
334HashSet<Key>::GetIterator() const
335{
336	return Iterator(this);
337}
338
339} // namespace BPrivate
340
341using BPrivate::HashSet;
342
343#endif	// HASH_SET_H
344