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 30 DE_BEGIN_EXTERN_C 31 32 void dePoolHeap_selfTest(void); 33 34 DE_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 * bool Heap_reserve (Heap* heap, int size); 52 * void Heap_reset (Heap* heap); 53 * bool 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 \ 59 DE_DECLARE_POOL_ARRAY(TYPENAME##Array, VALUETYPE); \ 60 \ 61 typedef struct TYPENAME##_s \ 62 { \ 63 TYPENAME##Array *array; \ 64 } TYPENAME; /* NOLINT(TYPENAME) */ \ 65 \ 66 DE_INLINE TYPENAME *TYPENAME##_create(deMemPool *pool); \ 67 DE_INLINE int TYPENAME##_getNumElements(const TYPENAME *heap) DE_UNUSED_FUNCTION; \ 68 DE_INLINE bool 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 bool 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; \ 74 \ 75 DE_INLINE TYPENAME *TYPENAME##_create(deMemPool *pool) \ 76 { \ 77 DE_PTR_TYPE(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 \ 86 DE_INLINE int TYPENAME##_getNumElements(const TYPENAME *heap) \ 87 { \ 88 return TYPENAME##Array_getNumElements(heap->array); \ 89 } \ 90 \ 91 DE_INLINE bool TYPENAME##_reserve(DE_PTR_TYPE(TYPENAME) heap, int capacity) \ 92 { \ 93 return TYPENAME##Array_reserve(heap->array, capacity); \ 94 } \ 95 \ 96 DE_INLINE void TYPENAME##_reset(DE_PTR_TYPE(TYPENAME) heap) \ 97 { \ 98 TYPENAME##Array_setSize(heap->array, 0); \ 99 } \ 100 \ 101 DE_INLINE void TYPENAME##_moveDown(DE_PTR_TYPE(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 = \ 112 CMPFUNC(TYPENAME##Array_get(array, childNdx0), TYPENAME##Array_get(array, childNdx1)); \ 113 int minChildNdx = (childCmpRes == 1) ? childNdx1 : childNdx0; \ 114 int cmpRes = CMPFUNC(TYPENAME##Array_get(array, ndx), TYPENAME##Array_get(array, minChildNdx)); \ 115 if (cmpRes == 1) \ 116 { \ 117 TYPENAME##Array_swap(array, ndx, minChildNdx); \ 118 ndx = minChildNdx; \ 119 } \ 120 else \ 121 break; \ 122 } \ 123 else \ 124 break; \ 125 } \ 126 } \ 127 \ 128 DE_INLINE void TYPENAME##_moveUp(DE_PTR_TYPE(TYPENAME) heap, int ndx) \ 129 { \ 130 TYPENAME##Array *array = heap->array; \ 131 while (ndx > 0) \ 132 { \ 133 int parentNdx = (ndx - 1) >> 1; \ 134 int cmpRes = CMPFUNC(TYPENAME##Array_get(array, ndx), TYPENAME##Array_get(array, parentNdx)); \ 135 if (cmpRes == -1) \ 136 { \ 137 TYPENAME##Array_swap(array, ndx, parentNdx); \ 138 ndx = parentNdx; \ 139 } \ 140 else \ 141 break; \ 142 } \ 143 } \ 144 \ 145 DE_INLINE bool TYPENAME##_push(DE_PTR_TYPE(TYPENAME) heap, VALUETYPE elem) \ 146 { \ 147 TYPENAME##Array *array = heap->array; \ 148 int numElements = TYPENAME##Array_getNumElements(array); \ 149 if (!TYPENAME##Array_setSize(array, numElements + 1)) \ 150 return false; \ 151 TYPENAME##Array_set(array, numElements, elem); \ 152 TYPENAME##_moveUp(heap, numElements); \ 153 return true; \ 154 } \ 155 \ 156 DE_INLINE VALUETYPE TYPENAME##_popMin(DE_PTR_TYPE(TYPENAME) heap) \ 157 { \ 158 TYPENAME##Array *array = heap->array; \ 159 VALUETYPE tmp = TYPENAME##Array_get(array, 0); \ 160 int numElements = TYPENAME##Array_getNumElements(array); \ 161 TYPENAME##Array_set(array, 0, TYPENAME##Array_get(array, numElements - 1)); \ 162 TYPENAME##Array_setSize(array, numElements - 1); \ 163 TYPENAME##_moveDown(heap, 0); \ 164 return tmp; \ 165 } \ 166 \ 167 struct TYPENAME##Unused_s \ 168 { \ 169 int unused; \ 170 } 171 172 #endif /* _DEPOOLHEAP_H */ 173