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
HeapItem_create(int priority,int value)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
HeapItem_cmp(HeapItem a,HeapItem b)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 *//*--------------------------------------------------------------------*/
dePoolHeap_selfTest(void)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 /* Unused 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 }
123