1#ifndef _DEPOOLHEAP_H
2#define _DEPOOLHEAP_H
3/*-------------------------------------------------------------------------
4 * drawElements Memory Pool Library
5 * --------------------------------
6 *
7 * Copyright 2014 The Android Open Source Project
8 *
9 * Licensed under the Apache License, Version 2.0 (the "License");
10 * you may not use this file except in compliance with the License.
11 * You may obtain a copy of the License at
12 *
13 *      http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing, software
16 * distributed under the License is distributed on an "AS IS" BASIS,
17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
18 * See the License for the specific language governing permissions and
19 * limitations under the License.
20 *
21 *//*!
22 * \file
23 * \brief Memory pool heap class.
24 *//*--------------------------------------------------------------------*/
25
26#include "deDefs.h"
27#include "deMemPool.h"
28#include "dePoolArray.h"
29
30DE_BEGIN_EXTERN_C
31
32void			dePoolHeap_selfTest			(void);
33
34DE_END_EXTERN_C
35
36/*--------------------------------------------------------------------*//*!
37 * \brief Declare a template pool heap class.
38 * \param TYPENAME	Type name of the declared heap.
39 * \param VALUETYPE	Type of the value contained in the heap.
40 * \param CMPFUNC	Comparison function of two elements returning (-1, 0, +1).
41 *
42 * This macro declares a pool heap with all the necessary functions for
43 * operating with it. All allocated memory is taken from the memory pool
44 * given to the constructor.
45 *
46 * The functions for operating the heap are:
47 *
48 * \code
49 * Heap*    Heap_create            (deMemPool* pool);
50 * int      Heap_getNumElements    (const Heap* heap);
51 * deBool   Heap_reserve           (Heap* heap, int size);
52 * void		Heap_reset             (Heap* heap);
53 * deBool   Heap_push              (Heap* heap, Element elem);
54 * Element  Heap_popMin            (Heap* heap);
55 * \endcode
56*//*--------------------------------------------------------------------*/
57#define DE_DECLARE_POOL_HEAP(TYPENAME, VALUETYPE, CMPFUNC)		\
58    \
59DE_DECLARE_POOL_ARRAY(TYPENAME##Array, VALUETYPE);		\
60\
61typedef struct TYPENAME##_s    \
62{    \
63	TYPENAME##Array*	array;		\
64} TYPENAME;    \
65\
66DE_INLINE TYPENAME*	TYPENAME##_create			(deMemPool* pool);										\
67DE_INLINE int		TYPENAME##_getNumElements	(const TYPENAME* heap)				DE_UNUSED_FUNCTION;	\
68DE_INLINE deBool	TYPENAME##_reserve			(TYPENAME* heap, int capacity)		DE_UNUSED_FUNCTION;	\
69DE_INLINE void		TYPENAME##_reset			(TYPENAME* heap)					DE_UNUSED_FUNCTION;	\
70DE_INLINE void		TYPENAME##_moveDown			(TYPENAME* heap, int ndx)			DE_UNUSED_FUNCTION;	\
71DE_INLINE void		TYPENAME##_moveUp			(TYPENAME* heap, int ndx)			DE_UNUSED_FUNCTION;	\
72DE_INLINE deBool	TYPENAME##_push				(TYPENAME* heap, VALUETYPE elem)	DE_UNUSED_FUNCTION;	\
73DE_INLINE VALUETYPE	TYPENAME##_popMin			(TYPENAME* heap)					DE_UNUSED_FUNCTION;	\
74\
75DE_INLINE TYPENAME* TYPENAME##_create (deMemPool* pool)    \
76{    \
77	TYPENAME* heap = DE_POOL_NEW(pool, TYPENAME);	\
78	if (!heap)				\
79		return DE_NULL;		\
80	heap->array = TYPENAME##Array_create(pool);	\
81	if (!heap->array)		\
82		return DE_NULL;		\
83	return heap;			\
84}    \
85\
86DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* heap)    \
87{    \
88	return TYPENAME##Array_getNumElements(heap->array);    \
89}    \
90\
91DE_INLINE deBool TYPENAME##_reserve (TYPENAME* heap, int capacity)    \
92{    \
93	return TYPENAME##Array_reserve(heap->array, capacity);    \
94}    \
95\
96DE_INLINE void TYPENAME##_reset (TYPENAME* heap)    \
97{    \
98	TYPENAME##Array_setSize(heap->array, 0);    \
99}    \
100\
101DE_INLINE void TYPENAME##_moveDown (TYPENAME* heap, int ndx)    \
102{   \
103	TYPENAME##Array*	array 		= heap->array;	\
104	int					numElements	= TYPENAME##Array_getNumElements(array);	\
105	for (;;)	\
106	{	\
107		int childNdx0	= 2*ndx + 1;								\
108		if (childNdx0 < numElements)	\
109		{	\
110			int childNdx1	= deMin32(childNdx0 + 1, numElements - 1);	\
111			int childCmpRes	= CMPFUNC(TYPENAME##Array_get(array, childNdx0), TYPENAME##Array_get(array, childNdx1)); \
112			int minChildNdx	= (childCmpRes == 1) ? childNdx1 : childNdx0;	\
113			int cmpRes		= CMPFUNC(TYPENAME##Array_get(array, ndx), TYPENAME##Array_get(array, minChildNdx)); \
114			if (cmpRes == 1)	\
115			{	\
116				TYPENAME##Array_swap(array, ndx, minChildNdx);	\
117				ndx = minChildNdx;	\
118			}	\
119			else	\
120				break;	\
121		}	\
122		else	\
123			break;	\
124	}	\
125}    \
126\
127DE_INLINE void TYPENAME##_moveUp (TYPENAME* heap, int ndx)    \
128{    \
129	TYPENAME##Array* array = heap->array;	\
130	while (ndx > 0)	\
131	{	\
132		int parentNdx	= (ndx-1) >> 1;								\
133		int cmpRes		= CMPFUNC(TYPENAME##Array_get(array, ndx), TYPENAME##Array_get(array, parentNdx)); \
134		if (cmpRes == -1)	\
135		{	\
136			TYPENAME##Array_swap(array, ndx, parentNdx);	\
137			ndx = parentNdx;	\
138		}	\
139		else	\
140			break;	\
141	}	\
142}    \
143\
144DE_INLINE deBool TYPENAME##_push (TYPENAME* heap, VALUETYPE elem)    \
145{    \
146	TYPENAME##Array* array = heap->array;	\
147	int numElements = TYPENAME##Array_getNumElements(array);	\
148	if (!TYPENAME##Array_setSize(array, numElements + 1)) \
149		return DE_FALSE; \
150	TYPENAME##Array_set(array, numElements, elem); \
151	TYPENAME##_moveUp(heap, numElements);	\
152	return DE_TRUE;    \
153}    \
154\
155DE_INLINE VALUETYPE TYPENAME##_popMin (TYPENAME* heap)    \
156{    \
157	TYPENAME##Array* array = heap->array;	\
158	VALUETYPE 	tmp			= TYPENAME##Array_get(array, 0);	\
159	int			numElements	= TYPENAME##Array_getNumElements(array);	\
160	TYPENAME##Array_set(array, 0, TYPENAME##Array_get(array, numElements-1));	\
161	TYPENAME##Array_setSize(array, numElements-1);	\
162	TYPENAME##_moveDown(heap, 0);	\
163	return tmp;	\
164}    \
165\
166struct TYPENAME##Dummy_s { int dummy; }
167
168#endif /* _DEPOOLHEAP_H */
169