1 /*-------------------------------------------------------------------------
2 * drawElements Memory Pool Library
3 * --------------------------------
5 * Copyright 2014 The Android Open Source Project
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
11 * http://www.apache.org/licenses/LICENSE-2.0
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.
21 * \brief Memory pool heap class.
22 *//*--------------------------------------------------------------------*/
24 #include "dePoolHeap.h"
30 typedef struct HeapItem_s
36 DE_INLINE HeapItem HeapItem_create (int priority, int value)
39 h.priority = priority;
44 DE_INLINE int HeapItem_cmp (HeapItem a, HeapItem b)
46 if (a.priority < b.priority)
48 if (a.priority > b.priority)
53 DE_DECLARE_POOL_HEAP(TestHeap, HeapItem, HeapItem_cmp);
55 /*--------------------------------------------------------------------*//*!
57 * \brief Test heap functionality.
58 *//*--------------------------------------------------------------------*/
59 void dePoolHeap_selfTest (void)
61 deMemPool* pool = deMemPool_createRoot(DE_NULL, 0);
62 TestHeap* heap = TestHeap_create(pool);
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);
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);
75 /* Push items -1000..1000 into heap. */
76 for (i = -1000; i < 1000; i++)
78 /* Dummy alloc to try to break alignments. */
79 deMemPool_alloc(pool, 1);
80 TestHeap_push(heap, HeapItem_create(i, -i));
82 DE_TEST_ASSERT(TestHeap_getNumElements(heap) == 2000);
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);
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);
94 /* Pop -3000..-2500 from heap. */
95 for (i = -3000; i < -2500; i++)
97 HeapItem h = TestHeap_popMin(heap);
98 DE_TEST_ASSERT(h.priority == i);
99 DE_TEST_ASSERT(h.value == -h.priority);
101 DE_TEST_ASSERT(TestHeap_getNumElements(heap) == 3500);
103 /* Pop -1000..1000 from heap. */
104 for (i = -1000; i < 1000; i++)
106 HeapItem h = TestHeap_popMin(heap);
107 DE_TEST_ASSERT(h.priority == i);
108 DE_TEST_ASSERT(h.value == -h.priority);
110 DE_TEST_ASSERT(TestHeap_getNumElements(heap) == 1500);
112 /* Pop 6000..7500 from heap. */
113 for (i = 6000; i < 7500; i++)
115 HeapItem h = TestHeap_popMin(heap);
116 DE_TEST_ASSERT(h.priority == i);
117 DE_TEST_ASSERT(h.value == -h.priority);
119 DE_TEST_ASSERT(TestHeap_getNumElements(heap) == 0);
121 deMemPool_destroy(pool);