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
30typedef struct HeapItem_s
31{
32	int		priority;
33	int		value;
34} HeapItem;
35
36DE_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
44DE_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
53DE_DECLARE_POOL_HEAP(TestHeap, HeapItem, HeapItem_cmp);
54
55/*--------------------------------------------------------------------*//*!
56 * \internal
57 * \brief Test heap functionality.
58 *//*--------------------------------------------------------------------*/
59void 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}
123