1/*
2 * Copyright 2013 Haiku, Inc. All rights reserved.
3 * Distributed under the terms of the MIT License.
4 *
5 * Authors:
6 *		Pawe�� Dziepak, pdziepak@quarnos.org
7 */
8#ifndef KERNEL_UTIL_HEAP_H
9#define KERNEL_UTIL_HEAP_H
10
11
12#include <debug.h>
13
14#include <SupportDefs.h>
15
16
17template<typename Element, typename Key>
18struct HeapLink {
19						HeapLink();
20
21			int			fIndex;
22			Key			fKey;
23};
24
25template<typename Element, typename Key>
26class HeapLinkImpl {
27private:
28	typedef HeapLink<Element, Key> Link;
29
30public:
31	inline	Link*		GetHeapLink();
32
33private:
34			Link		fHeapLink;
35};
36
37template<typename Element, typename Key>
38class HeapStandardGetLink {
39private:
40	typedef HeapLink<Element, Key> Link;
41
42public:
43	inline	Link*		operator()(Element* element) const;
44};
45
46template<typename Element, typename Key,
47	HeapLink<Element, Key> Element::*LinkMember>
48class HeapMemberGetLink {
49private:
50	typedef HeapLink<Element, Key> Link;
51
52public:
53	inline	Link*		operator()(Element* element) const;
54};
55
56template<typename Key>
57class HeapLesserCompare {
58public:
59	inline	bool		operator()(Key a, Key b);
60};
61
62template<typename Key>
63class HeapGreaterCompare {
64public:
65	inline	bool		operator()(Key a, Key b);
66};
67
68#define HEAP_TEMPLATE_LIST	\
69	template<typename Element, typename Key, typename Compare, typename GetLink>
70#define HEAP_CLASS_NAME	Heap<Element, Key, Compare, GetLink>
71
72template<typename Element, typename Key,
73	typename Compare = HeapLesserCompare<Key>,
74	typename GetLink = HeapStandardGetLink<Element, Key> >
75class Heap {
76public:
77						Heap();
78						Heap(int initialSize);
79						~Heap();
80
81	inline	Element*	PeekRoot() const;
82
83	static	const Key&	GetKey(Element* element);
84
85	inline	void		ModifyKey(Element* element, Key newKey);
86
87	inline	void		RemoveRoot();
88	inline	status_t	Insert(Element* element, Key key);
89
90private:
91			status_t	_GrowHeap(int minimalSize = 0);
92
93			void		_MoveUp(HeapLink<Element, Key>* link);
94			void		_MoveDown(HeapLink<Element, Key>* link);
95
96			Element**	fElements;
97			int			fLastElement;
98			int			fSize;
99
100	static	Compare		sCompare;
101	static	GetLink		sGetLink;
102};
103
104
105#if KDEBUG
106template<typename Element, typename Key>
107HeapLink<Element, Key>::HeapLink()
108	:
109	fIndex(-1)
110{
111}
112#else
113template<typename Element, typename Key>
114HeapLink<Element, Key>::HeapLink()
115{
116}
117#endif
118
119
120template<typename Element, typename Key>
121HeapLink<Element, Key>*
122HeapLinkImpl<Element, Key>::GetHeapLink()
123{
124	return &fHeapLink;
125}
126
127
128template<typename Element, typename Key>
129HeapLink<Element, Key>*
130HeapStandardGetLink<Element, Key>::operator()(Element* element) const
131{
132	return element->GetHeapLink();
133}
134
135
136template<typename Element, typename Key,
137	HeapLink<Element, Key> Element::*LinkMember>
138HeapLink<Element, Key>*
139HeapMemberGetLink<Element, Key, LinkMember>::operator()(Element* element) const
140{
141	return &(element->*LinkMember);
142}
143
144
145template<typename Key>
146bool
147HeapLesserCompare<Key>::operator()(Key a, Key b)
148{
149	return a < b;
150}
151
152
153template<typename Key>
154bool
155HeapGreaterCompare<Key>::operator()(Key a, Key b)
156{
157	return a > b;
158}
159
160
161HEAP_TEMPLATE_LIST
162HEAP_CLASS_NAME::Heap()
163	:
164	fElements(NULL),
165	fLastElement(0),
166	fSize(0)
167{
168}
169
170
171HEAP_TEMPLATE_LIST
172HEAP_CLASS_NAME::Heap(int initialSize)
173	:
174	fElements(NULL),
175	fLastElement(0),
176	fSize(0)
177{
178	_GrowHeap(initialSize);
179}
180
181
182HEAP_TEMPLATE_LIST
183HEAP_CLASS_NAME::~Heap()
184{
185	free(fElements);
186}
187
188
189HEAP_TEMPLATE_LIST
190Element*
191HEAP_CLASS_NAME::PeekRoot() const
192{
193	if (fLastElement > 0)
194		return fElements[0];
195	return NULL;
196}
197
198
199HEAP_TEMPLATE_LIST
200const Key&
201HEAP_CLASS_NAME::GetKey(Element* element)
202{
203	return sGetLink(element)->fKey;
204}
205
206
207HEAP_TEMPLATE_LIST
208void
209HEAP_CLASS_NAME::ModifyKey(Element* element, Key newKey)
210{
211	HeapLink<Element, Key>* link = sGetLink(element);
212
213	ASSERT(link->fIndex >= 0 && link->fIndex < fLastElement);
214	Key oldKey = link->fKey;
215	link->fKey = newKey;
216
217	if (sCompare(newKey, oldKey))
218		_MoveUp(link);
219	else if (sCompare(oldKey, newKey))
220		_MoveDown(link);
221}
222
223
224HEAP_TEMPLATE_LIST
225void
226HEAP_CLASS_NAME::RemoveRoot()
227{
228	ASSERT(fLastElement > 0);
229
230#if KDEBUG
231	Element* element = PeekRoot();
232	HeapLink<Element, Key>* link = sGetLink(element);
233	ASSERT(link->fIndex != -1);
234	link->fIndex = -1;
235#endif
236
237	fLastElement--;
238	if (fLastElement > 0) {
239		Element* lastElement = fElements[fLastElement];
240		fElements[0] = lastElement;
241		sGetLink(lastElement)->fIndex = 0;
242		_MoveDown(sGetLink(lastElement));
243	}
244}
245
246
247HEAP_TEMPLATE_LIST
248status_t
249HEAP_CLASS_NAME::Insert(Element* element, Key key)
250{
251	if (fLastElement == fSize) {
252		status_t result = _GrowHeap();
253		if (result != B_OK)
254			return result;
255	}
256
257	ASSERT(fLastElement != fSize);
258
259	HeapLink<Element, Key>* link = sGetLink(element);
260
261	ASSERT(link->fIndex == -1);
262
263	fElements[fLastElement] = element;
264	link->fIndex = fLastElement++;
265	link->fKey = key;
266	_MoveUp(link);
267
268	return B_OK;
269}
270
271
272HEAP_TEMPLATE_LIST
273status_t
274HEAP_CLASS_NAME::_GrowHeap(int minimalSize)
275{
276	int newSize = max_c(max_c(fSize * 2, 4), minimalSize);
277
278	size_t arraySize = newSize * sizeof(Element*);
279	Element** newBuffer
280		= reinterpret_cast<Element**>(realloc(fElements, arraySize));
281	if (newBuffer == NULL)
282		return B_NO_MEMORY;
283
284	fElements = newBuffer;
285	fSize = newSize;
286
287	return B_OK;
288}
289
290
291HEAP_TEMPLATE_LIST
292void
293HEAP_CLASS_NAME::_MoveUp(HeapLink<Element, Key>* link)
294{
295	while (true) {
296		int parent = (link->fIndex - 1) / 2;
297		if (link->fIndex > 0
298			&& sCompare(link->fKey, sGetLink(fElements[parent])->fKey)) {
299
300			sGetLink(fElements[parent])->fIndex = link->fIndex;
301
302			Element* element = fElements[link->fIndex];
303			fElements[link->fIndex] = fElements[parent];
304			fElements[parent] = element;
305
306			link->fIndex = parent;
307		} else
308			break;
309	}
310}
311
312
313HEAP_TEMPLATE_LIST
314void
315HEAP_CLASS_NAME::_MoveDown(HeapLink<Element, Key>* link)
316{
317	int current;
318
319	while (true) {
320		current = link->fIndex;
321
322		int child = 2 * link->fIndex + 1;
323		if (child < fLastElement
324			&& sCompare(sGetLink(fElements[child])->fKey, link->fKey)) {
325			current = child;
326		}
327
328		child = 2 * link->fIndex + 2;
329		if (child < fLastElement
330			&& sCompare(sGetLink(fElements[child])->fKey,
331				sGetLink(fElements[current])->fKey)) {
332			current = child;
333		}
334
335		if (link->fIndex == current)
336			break;
337
338		sGetLink(fElements[current])->fIndex = link->fIndex;
339
340		Element* element = fElements[link->fIndex];
341		fElements[link->fIndex] = fElements[current];
342		fElements[current] = element;
343
344		link->fIndex = current;
345	}
346}
347
348
349HEAP_TEMPLATE_LIST
350Compare HEAP_CLASS_NAME::sCompare;
351
352HEAP_TEMPLATE_LIST
353GetLink HEAP_CLASS_NAME::sGetLink;
354
355
356#endif	// KERNEL_UTIL_HEAP_H
357
358