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 * 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 \ 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 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; \ 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 deBool 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 = 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 \ 127 DE_INLINE void TYPENAME##_moveUp (DE_PTR_TYPE(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 \ 144 DE_INLINE deBool TYPENAME##_push (DE_PTR_TYPE(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 \ 155 DE_INLINE VALUETYPE TYPENAME##_popMin (DE_PTR_TYPE(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 \ 166 struct TYPENAME##Dummy_s { int dummy; } 167 168 #endif /* _DEPOOLHEAP_H */ 169
