framework/delibs/depool/dePoolHeap.c

   1 /*-------------------------------------------------------------------------
   2  * drawElements Memory Pool Library
   3  * --------------------------------
   4  *
   5  * Copyright 2014 The Android Open Source Project
   6  *
   7  * Licensed under the Apache License, Version 2.0 (the "License");
   8  * you may not use this file except in compliance with the License.
   9  * You may obtain a copy of the License at
  10  *
  11  *      http://www.apache.org/licenses/LICENSE-2.0
  12  *
  13  * Unless required by applicable law or agreed to in writing, software
  14  * distributed under the License is distributed on an "AS IS" BASIS,
  15  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  16  * See the License for the specific language governing permissions and
  17  * limitations under the License.
  18  *
  19  *//*!
  20  * \file
  21  * \brief Memory pool heap class.
  22  *//*--------------------------------------------------------------------*/
  23
  24 #include "dePoolHeap.h"
  25 #include "deInt32.h"
  26
  27 #include <stdlib.h>
  28 #include <string.h>
  29
  30 typedef struct HeapItem_s
  31 {
  32         int             priority;
  33         int             value;
  34 } HeapItem;
  35
  36 DE_INLINE HeapItem HeapItem_create (int priority, int value)
  37 {
  38         HeapItem h;
  39         h.priority      = priority;
  40         h.value         = value;
  41         return h;
  42 }
  43
  44 DE_INLINE int HeapItem_cmp (HeapItem a, HeapItem b)
  45 {
  46         if (a.priority < b.priority)
  47                 return -1;
  48         if (a.priority > b.priority)
  49                 return +1;
  50         return 0;
  51 }
  52
  53 DE_DECLARE_POOL_HEAP(TestHeap, HeapItem, HeapItem_cmp);
  54
  55 /*--------------------------------------------------------------------*//*!
  56  * \internal
  57  * \brief Test heap functionality.
  58  *//*--------------------------------------------------------------------*/
  59 void dePoolHeap_selfTest (void)
  60 {
  61         deMemPool*              pool    = deMemPool_createRoot(DE_NULL, 0);
  62         TestHeap*               heap    = TestHeap_create(pool);
  63         int                             i;
  64
  65         TestHeap_push(heap, HeapItem_create(10, 10));
  66         TestHeap_push(heap, HeapItem_create(0, 10));
  67         TestHeap_push(heap, HeapItem_create(20, 10));
  68         DE_TEST_ASSERT(TestHeap_getNumElements(heap) == 3);
  69
  70         DE_TEST_ASSERT(TestHeap_popMin(heap).priority == 0);
  71         DE_TEST_ASSERT(TestHeap_popMin(heap).priority == 10);
  72         DE_TEST_ASSERT(TestHeap_popMin(heap).priority == 20);
  73         DE_TEST_ASSERT(TestHeap_getNumElements(heap) == 0);
  74
  75         /* Push items -1000..1000 into heap. */
  76         for (i = -1000; i < 1000; i++)
  77         {
  78                 /* Dummy alloc to try to break alignments. */
  79                 deMemPool_alloc(pool, 1);
  80                 TestHeap_push(heap, HeapItem_create(i, -i));
  81         }
  82         DE_TEST_ASSERT(TestHeap_getNumElements(heap) == 2000);
  83
  84         /* Push items -2500..-3000 into heap. */
  85         for (i = -2501; i >= -3000; i--)
  86                 TestHeap_push(heap, HeapItem_create(i, -i));
  87         DE_TEST_ASSERT(TestHeap_getNumElements(heap) == 2500);
  88
  89         /* Push items 6000..7500 into heap. */
  90         for (i = 6000; i < 7500; i++)
  91                 TestHeap_push(heap, HeapItem_create(i, -i));
  92         DE_TEST_ASSERT(TestHeap_getNumElements(heap) == 4000);
  93
  94         /* Pop -3000..-2500 from heap. */
  95         for (i = -3000; i < -2500; i++)
  96         {
  97                 HeapItem h = TestHeap_popMin(heap);
  98                 DE_TEST_ASSERT(h.priority == i);
  99                 DE_TEST_ASSERT(h.value == -h.priority);
 100         }
 101         DE_TEST_ASSERT(TestHeap_getNumElements(heap) == 3500);
 102
 103         /* Pop -1000..1000 from heap. */
 104         for (i = -1000; i < 1000; i++)
 105         {
 106                 HeapItem h = TestHeap_popMin(heap);
 107                 DE_TEST_ASSERT(h.priority == i);
 108                 DE_TEST_ASSERT(h.value == -h.priority);
 109         }
 110         DE_TEST_ASSERT(TestHeap_getNumElements(heap) == 1500);
 111
 112         /* Pop 6000..7500 from heap. */
 113         for (i = 6000; i < 7500; i++)
 114         {
 115                 HeapItem h = TestHeap_popMin(heap);
 116                 DE_TEST_ASSERT(h.priority == i);
 117                 DE_TEST_ASSERT(h.value == -h.priority);
 118         }
 119         DE_TEST_ASSERT(TestHeap_getNumElements(heap) == 0);
 120
 121         deMemPool_destroy(pool);
 122 }