3 /*-------------------------------------------------------------------------
4 * drawElements Memory Pool Library
5 * --------------------------------
7 * Copyright 2014 The Android Open Source Project
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
13 * http://www.apache.org/licenses/LICENSE-2.0
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.
23 * \brief Memory pool heap class.
24 *//*--------------------------------------------------------------------*/
27 #include "deMemPool.h"
28 #include "dePoolArray.h"
32 void dePoolHeap_selfTest (void);
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).
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.
46 * The functions for operating the heap are:
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);
56 *//*--------------------------------------------------------------------*/
57 #define DE_DECLARE_POOL_HEAP(TYPENAME, VALUETYPE, CMPFUNC) \
59 DE_DECLARE_POOL_ARRAY(TYPENAME##Array, VALUETYPE); \
61 typedef struct TYPENAME##_s \
63 TYPENAME##Array* array; \
64 } TYPENAME; /* NOLINT(TYPENAME) */ \
66 DE_INLINE TYPENAME* TYPENAME##_create (deMemPool* pool); \
67 DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* heap) DE_UNUSED_FUNCTION; \
68 DE_INLINE deBool TYPENAME##_reserve (DE_PTR_TYPE(TYPENAME) heap, int capacity) DE_UNUSED_FUNCTION; \
69 DE_INLINE void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) heap) DE_UNUSED_FUNCTION; \
70 DE_INLINE void TYPENAME##_moveDown (DE_PTR_TYPE(TYPENAME) heap, int ndx) DE_UNUSED_FUNCTION; \
71 DE_INLINE void TYPENAME##_moveUp (DE_PTR_TYPE(TYPENAME) heap, int ndx) DE_UNUSED_FUNCTION; \
72 DE_INLINE deBool TYPENAME##_push (DE_PTR_TYPE(TYPENAME) heap, VALUETYPE elem) DE_UNUSED_FUNCTION; \
73 DE_INLINE VALUETYPE TYPENAME##_popMin (DE_PTR_TYPE(TYPENAME) heap) DE_UNUSED_FUNCTION; \
75 DE_INLINE TYPENAME* TYPENAME##_create (deMemPool* pool) \
77 DE_PTR_TYPE(TYPENAME) heap = DE_POOL_NEW(pool, TYPENAME); \
80 heap->array = TYPENAME##Array_create(pool); \
86 DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* heap) \
88 return TYPENAME##Array_getNumElements(heap->array); \
91 DE_INLINE deBool TYPENAME##_reserve (DE_PTR_TYPE(TYPENAME) heap, int capacity) \
93 return TYPENAME##Array_reserve(heap->array, capacity); \
96 DE_INLINE void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) heap) \
98 TYPENAME##Array_setSize(heap->array, 0); \
101 DE_INLINE void TYPENAME##_moveDown (DE_PTR_TYPE(TYPENAME) heap, int ndx) \
103 TYPENAME##Array* array = heap->array; \
104 int numElements = TYPENAME##Array_getNumElements(array); \
107 int childNdx0 = 2*ndx + 1; \
108 if (childNdx0 < numElements) \
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)); \
116 TYPENAME##Array_swap(array, ndx, minChildNdx); \
127 DE_INLINE void TYPENAME##_moveUp (DE_PTR_TYPE(TYPENAME) heap, int ndx) \
129 TYPENAME##Array* array = heap->array; \
132 int parentNdx = (ndx-1) >> 1; \
133 int cmpRes = CMPFUNC(TYPENAME##Array_get(array, ndx), TYPENAME##Array_get(array, parentNdx)); \
136 TYPENAME##Array_swap(array, ndx, parentNdx); \
144 DE_INLINE deBool TYPENAME##_push (DE_PTR_TYPE(TYPENAME) heap, VALUETYPE elem) \
146 TYPENAME##Array* array = heap->array; \
147 int numElements = TYPENAME##Array_getNumElements(array); \
148 if (!TYPENAME##Array_setSize(array, numElements + 1)) \
150 TYPENAME##Array_set(array, numElements, elem); \
151 TYPENAME##_moveUp(heap, numElements); \
155 DE_INLINE VALUETYPE TYPENAME##_popMin (DE_PTR_TYPE(TYPENAME) heap) \
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); \
166 struct TYPENAME##Dummy_s { int dummy; }
168 #endif /* _DEPOOLHEAP_H */