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 } 123
