1// HashSet.h
2//
3// Copyright (c) 2004, Ingo Weinhold (bonefish@cs.tu-berlin.de)
4//
5// Permission is hereby granted, free of charge, to any person obtaining a
6// copy of this software and associated documentation files (the "Software"),
7// to deal in the Software without restriction, including without limitation
8// the rights to use, copy, modify, merge, publish, distribute, sublicense,
9// and/or sell copies of the Software, and to permit persons to whom the
10// Software is furnished to do so, subject to the following conditions:
11//
12// The above copyright notice and this permission notice shall be included in
13// all copies or substantial portions of the Software.
14//
15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
18// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21// DEALINGS IN THE SOFTWARE.
22//
23// Except as contained in this notice, the name of a copyright holder shall
24// not be used in advertising or otherwise to promote the sale, use or other
25// dealings in this Software without prior written authorization of the
26// copyright holder.
27
28#ifndef HASH_SET_H
29#define HASH_SET_H
30
31#include "AutoLocker.h"
32#include "Locker.h"
33#include "OpenHashTable.h"
34
35// HashSetElement
36template<typename Key>
37class HashSetElement : public OpenHashElement {
38private:
39	typedef HashSetElement<Key> Element;
40public:
41
42	HashSetElement() : OpenHashElement(), fKey()
43	{
44		fNext = -1;
45	}
46
47	inline uint32 Hash() const
48	{
49		return fKey.GetHashCode();
50	}
51
52	inline bool operator==(const OpenHashElement &_element) const
53	{
54		const Element &element = static_cast<const Element&>(_element);
55		return (fKey == element.fKey);
56	}
57
58	inline void Adopt(Element &element)
59	{
60		fKey = element.fKey;
61	}
62
63	Key		fKey;
64};
65
66// HashSet
67template<typename Key>
68class HashSet {
69public:
70	class Iterator {
71	private:
72		typedef HashSetElement<Key>	Element;
73	public:
74		Iterator(const Iterator& other)
75			: fSet(other.fSet),
76			  fIndex(other.fIndex),
77			  fElement(other.fElement),
78			  fLastElement(other.fElement)
79		{
80		}
81
82		bool HasNext() const
83		{
84			return fElement;
85		}
86
87		Key Next()
88		{
89			if (!fElement)
90				return Key();
91			Key result(fElement->fKey);
92			_FindNext();
93			return result;
94		}
95
96		bool Remove()
97		{
98			if (!fLastElement)
99				return false;
100			fSet->fTable.Remove(fLastElement);
101			fLastElement = NULL;
102			return true;
103		}
104
105		Iterator& operator=(const Iterator& other)
106		{
107			fSet = other.fSet;
108			fIndex = other.fIndex;
109			fElement = other.fElement;
110			fLastElement = other.fLastElement;
111			return *this;
112		}
113
114	private:
115		Iterator(HashSet<Key>* map)
116			: fSet(map),
117			  fIndex(0),
118			  fElement(NULL),
119			  fLastElement(NULL)
120		{
121			// find first
122			_FindNext();
123		}
124
125		void _FindNext()
126		{
127			fLastElement = fElement;
128			if (fElement && fElement->fNext >= 0) {
129				fElement = fSet->fTable.ElementAt(fElement->fNext);
130				return;
131			}
132			fElement = NULL;
133			int32 arraySize = fSet->fTable.ArraySize();
134			for (; !fElement && fIndex < arraySize; fIndex++)
135				fElement = fSet->fTable.FindFirst(fIndex);
136		}
137
138	private:
139		friend class HashSet<Key>;
140
141		HashSet<Key>*	fSet;
142		int32			fIndex;
143		Element*		fElement;
144		Element*		fLastElement;
145	};
146
147	HashSet();
148	~HashSet();
149
150	status_t InitCheck() const;
151
152	status_t Add(const Key& key);
153	bool Remove(const Key& key);
154	bool Contains(const Key& key) const;
155
156	int32 Size() const;
157
158	Iterator GetIterator();
159
160protected:
161	typedef HashSetElement<Key>	Element;
162	friend class Iterator;
163
164private:
165	Element *_FindElement(const Key& key) const;
166
167protected:
168	OpenHashElementArray<Element>							fElementArray;
169	OpenHashTable<Element, OpenHashElementArray<Element> >	fTable;
170};
171
172// SynchronizedHashSet
173template<typename Key>
174class SynchronizedHashSet : public Locker {
175public:
176	typedef HashSet<Key>::Iterator Iterator;
177
178	SynchronizedHashSet() : Locker("synchronized hash map")	{}
179	~SynchronizedHashSet()	{ Lock(); }
180
181	status_t InitCheck() const
182	{
183		return fSet.InitCheck();
184	}
185
186	status_t Add(const Key& key)
187	{
188		MapLocker locker(this);
189		if (!locker.IsLocked())
190			return B_ERROR;
191		return fSet.Add(key);
192	}
193
194	bool Remove(const Key& key)
195	{
196		MapLocker locker(this);
197		if (!locker.IsLocked())
198			return false;
199		return fSet.Remove(key);
200	}
201
202	bool Contains(const Key& key) const
203	{
204		const Locker* lock = this;
205		MapLocker locker(const_cast<Locker*>(lock));
206		if (!locker.IsLocked())
207			return false;
208		return fSet.Contains(key);
209	}
210
211	int32 Size() const
212	{
213		const Locker* lock = this;
214		MapLocker locker(const_cast<Locker*>(lock));
215		return fSet.Size();
216	}
217
218	Iterator GetIterator()
219	{
220		return fSet.GetIterator();
221	}
222
223	// for debugging only
224	const HashSet<Key>& GetUnsynchronizedSet() const	{ return fSet; }
225	HashSet<Key>& GetUnsynchronizedSet()				{ return fSet; }
226
227protected:
228	typedef AutoLocker<Locker> MapLocker;
229
230	HashSet<Key>	fSet;
231};
232
233// HashSet
234
235// constructor
236template<typename Key>
237HashSet<Key>::HashSet()
238	: fElementArray(1000),
239	  fTable(1000, &fElementArray)
240{
241}
242
243// destructor
244template<typename Key>
245HashSet<Key>::~HashSet()
246{
247}
248
249// InitCheck
250template<typename Key>
251status_t
252HashSet<Key>::InitCheck() const
253{
254	return (fTable.InitCheck() && fElementArray.InitCheck()
255			? B_OK : B_NO_MEMORY);
256}
257
258// Add
259template<typename Key>
260status_t
261HashSet<Key>::Add(const Key& key)
262{
263	if (Contains(key))
264		return B_OK;
265	Element* element = fTable.Add(key.GetHashCode());
266	if (!element)
267		return B_NO_MEMORY;
268	element->fKey = key;
269	return B_OK;
270}
271
272// Remove
273template<typename Key>
274bool
275HashSet<Key>::Remove(const Key& key)
276{
277	if (Element* element = _FindElement(key)) {
278		fTable.Remove(element);
279		return true;
280	}
281	return false;
282}
283
284// Contains
285template<typename Key>
286bool
287HashSet<Key>::Contains(const Key& key) const
288{
289	return _FindElement(key);
290}
291
292// Size
293template<typename Key>
294int32
295HashSet<Key>::Size() const
296{
297	return fTable.CountElements();
298}
299
300// GetIterator
301template<typename Key>
302HashSet<Key>::Iterator
303HashSet<Key>::GetIterator()
304{
305	return Iterator(this);
306}
307
308// _FindElement
309template<typename Key>
310HashSet<Key>::Element *
311HashSet<Key>::_FindElement(const Key& key) const
312{
313	Element* element = fTable.FindFirst(key.GetHashCode());
314	while (element && element->fKey != key) {
315		if (element->fNext >= 0)
316			element = fTable.ElementAt(element->fNext);
317		else
318			element = NULL;
319	}
320	return element;
321}
322
323#endif	// HASH_SET_H
324