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 <Locker.h>
32
33#include "AutoLocker.h"
34#include "OpenHashTable.h"
35
36
37namespace BPrivate {
38
39// HashSetElement
40template<typename Key>
41class HashSetElement : public OpenHashElement {
42private:
43	typedef HashSetElement<Key> Element;
44public:
45
46	HashSetElement() : OpenHashElement(), fKey()
47	{
48		fNext = -1;
49	}
50
51	inline uint32 Hash() const
52	{
53		return fKey.GetHashCode();
54	}
55
56	inline bool operator==(const OpenHashElement &_element) const
57	{
58		const Element &element = static_cast<const Element&>(_element);
59		return (fKey == element.fKey);
60	}
61
62	inline void Adopt(Element &element)
63	{
64		fKey = element.fKey;
65	}
66
67	Key		fKey;
68};
69
70// HashSet
71template<typename Key>
72class HashSet {
73public:
74	class Iterator {
75	private:
76		typedef HashSetElement<Key>	Element;
77	public:
78		Iterator(const Iterator& other)
79			: fSet(other.fSet),
80			  fIndex(other.fIndex),
81			  fElement(other.fElement),
82			  fLastElement(other.fElement)
83		{
84		}
85
86		bool HasNext() const
87		{
88			return fElement;
89		}
90
91		Key Next()
92		{
93			if (!fElement)
94				return Key();
95			Key result(fElement->fKey);
96			_FindNext();
97			return result;
98		}
99
100		bool Remove()
101		{
102			if (!fLastElement)
103				return false;
104			fSet->fTable.Remove(fLastElement);
105			fLastElement = NULL;
106			return true;
107		}
108
109		Iterator& operator=(const Iterator& other)
110		{
111			fSet = other.fSet;
112			fIndex = other.fIndex;
113			fElement = other.fElement;
114			fLastElement = other.fLastElement;
115			return *this;
116		}
117
118	private:
119		Iterator(HashSet<Key>* map)
120			: fSet(map),
121			  fIndex(0),
122			  fElement(NULL),
123			  fLastElement(NULL)
124		{
125			// find first
126			_FindNext();
127		}
128
129		void _FindNext()
130		{
131			fLastElement = fElement;
132			if (fElement && fElement->fNext >= 0) {
133				fElement = fSet->fTable.ElementAt(fElement->fNext);
134				return;
135			}
136			fElement = NULL;
137			int32 arraySize = fSet->fTable.ArraySize();
138			for (; !fElement && fIndex < arraySize; fIndex++)
139				fElement = fSet->fTable.FindFirst(fIndex);
140		}
141
142	private:
143		friend class HashSet<Key>;
144
145		HashSet<Key>*	fSet;
146		int32			fIndex;
147		Element*		fElement;
148		Element*		fLastElement;
149	};
150
151	HashSet();
152	~HashSet();
153
154	status_t InitCheck() const;
155
156	status_t Add(const Key& key);
157	bool Remove(const Key& key);
158	void Clear();
159	bool Contains(const Key& key) const;
160
161	int32 Size() const;
162	bool IsEmpty() const	{ return Size() == 0; }
163
164	Iterator GetIterator();
165
166protected:
167	typedef HashSetElement<Key>	Element;
168	friend class Iterator;
169
170private:
171	Element *_FindElement(const Key& key) const;
172
173protected:
174	OpenHashElementArray<Element>							fElementArray;
175	OpenHashTable<Element, OpenHashElementArray<Element> >	fTable;
176};
177
178// SynchronizedHashSet
179template<typename Key>
180class SynchronizedHashSet : public BLocker {
181public:
182	typedef struct HashSet<Key>::Iterator Iterator;
183
184	SynchronizedHashSet() : BLocker("synchronized hash set")	{}
185	~SynchronizedHashSet()	{ Lock(); }
186
187	status_t InitCheck() const
188	{
189		return fSet.InitCheck();
190	}
191
192	status_t Add(const Key& key)
193	{
194		MapLocker locker(this);
195		if (!locker.IsLocked())
196			return B_ERROR;
197		return fSet.Add(key);
198	}
199
200	bool Remove(const Key& key)
201	{
202		MapLocker locker(this);
203		if (!locker.IsLocked())
204			return false;
205		return fSet.Remove(key);
206	}
207
208	bool Contains(const Key& key) const
209	{
210		const BLocker* lock = this;
211		MapLocker locker(const_cast<BLocker*>(lock));
212		if (!locker.IsLocked())
213			return false;
214		return fSet.Contains(key);
215	}
216
217	int32 Size() const
218	{
219		const BLocker* lock = this;
220		MapLocker locker(const_cast<BLocker*>(lock));
221		return fSet.Size();
222	}
223
224	Iterator GetIterator()
225	{
226		return fSet.GetIterator();
227	}
228
229	// for debugging only
230	const HashSet<Key>& GetUnsynchronizedSet() const	{ return fSet; }
231	HashSet<Key>& GetUnsynchronizedSet()				{ return fSet; }
232
233protected:
234	typedef AutoLocker<BLocker> MapLocker;
235
236	HashSet<Key>	fSet;
237};
238
239// HashSet
240
241// constructor
242template<typename Key>
243HashSet<Key>::HashSet()
244	: fElementArray(1000),
245	  fTable(1000, &fElementArray)
246{
247}
248
249// destructor
250template<typename Key>
251HashSet<Key>::~HashSet()
252{
253}
254
255// InitCheck
256template<typename Key>
257status_t
258HashSet<Key>::InitCheck() const
259{
260	return (fTable.InitCheck() && fElementArray.InitCheck()
261			? B_OK : B_NO_MEMORY);
262}
263
264// Add
265template<typename Key>
266status_t
267HashSet<Key>::Add(const Key& key)
268{
269	if (Contains(key))
270		return B_OK;
271	Element* element = fTable.Add(key.GetHashCode());
272	if (!element)
273		return B_NO_MEMORY;
274	element->fKey = key;
275	return B_OK;
276}
277
278// Remove
279template<typename Key>
280bool
281HashSet<Key>::Remove(const Key& key)
282{
283	if (Element* element = _FindElement(key)) {
284		fTable.Remove(element);
285		return true;
286	}
287	return false;
288}
289
290// Clear
291template<typename Key>
292void
293HashSet<Key>::Clear()
294{
295	fTable.RemoveAll();
296}
297
298// Contains
299template<typename Key>
300bool
301HashSet<Key>::Contains(const Key& key) const
302{
303	return _FindElement(key);
304}
305
306// Size
307template<typename Key>
308int32
309HashSet<Key>::Size() const
310{
311	return fTable.CountElements();
312}
313
314// GetIterator
315template<typename Key>
316struct HashSet<Key>::Iterator
317HashSet<Key>::GetIterator()
318{
319	return Iterator(this);
320}
321
322// _FindElement
323template<typename Key>
324struct HashSet<Key>::Element *
325HashSet<Key>::_FindElement(const Key& key) const
326{
327	Element* element = fTable.FindFirst(key.GetHashCode());
328	while (element && element->fKey != key) {
329		if (element->fNext >= 0)
330			element = fTable.ElementAt(element->fNext);
331		else
332			element = NULL;
333	}
334	return element;
335}
336
337}	// namespace BPrivate
338
339using BPrivate::HashSet;
340using BPrivate::SynchronizedHashSet;
341
342#endif	// HASH_SET_H
343