framework/delibs/depool/dePoolHeap.h

   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##Unused_s { int unused; }
 167
 168 #endif /* _DEPOOLHEAP_H */