1 /*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef CHRE_UTIL_HEAP_IMPL_H_
18 #define CHRE_UTIL_HEAP_IMPL_H_
19
20 // IWYU pragma: private
21 #include <utility>
22
23 #include "chre/util/container_support.h"
24 #include "chre/util/dynamic_vector.h"
25 #include "chre/util/fixed_size_vector.h"
26
27 namespace chre {
28
29 namespace {
30
31 template <typename ContainerType, typename CompareFunction>
siftUp(ContainerType & container,size_t index,const CompareFunction & compare)32 void siftUp(ContainerType &container, size_t index,
33 const CompareFunction &compare) {
34 CHRE_ASSERT(index < container.size());
35 size_t current = index;
36 while (current > 0) {
37 size_t parent = (current - 1) / 2;
38 if (compare(container[parent], container[current])) {
39 container.swap(parent, current);
40 current = parent;
41 } else {
42 break;
43 }
44 }
45 }
46
47 template <typename ContainerType, typename CompareFunction>
siftDown(ContainerType & container,size_t index,const CompareFunction & compare)48 void siftDown(ContainerType &container, size_t index,
49 const CompareFunction &compare) {
50 CHRE_ASSERT(index < container.size());
51 size_t current = index;
52
53 // The last element is to be removed. If that's the element being indexed,
54 // it's a no-op.
55 while (index < container.size() - 1) {
56 size_t child = 2 * current + 1; // left child
57
58 // If there are two children, pick the dominant one.
59 if (child + 1 < container.size() - 1 &&
60 compare(container[child], container[child + 1])) {
61 child++;
62 }
63
64 // If the current element is not childless and the dominant child dominates
65 // over it, swap and continue.
66 if (child < container.size() - 1 &&
67 compare(container[current], container[child])) {
68 container.swap(current, child);
69 current = child;
70 } else {
71 break;
72 }
73 }
74 }
75
76 } // namespace
77
78 template <typename ContainerType, typename CompareFunction>
push_heap(ContainerType & container,const CompareFunction & compare)79 void push_heap(ContainerType &container, const CompareFunction &compare) {
80 CHRE_ASSERT(container.size() > 0);
81 if (container.size() > 0) {
82 siftUp(container, container.size() - 1, compare);
83 }
84 }
85
86 template <typename ContainerType, typename CompareFunction>
pop_heap(ContainerType & container,const CompareFunction & compare)87 void pop_heap(ContainerType &container, const CompareFunction &compare) {
88 CHRE_ASSERT(container.size() > 0);
89 if (container.size() > 0) {
90 container.swap(0, container.size() - 1);
91 siftDown(container, 0, compare);
92 }
93 }
94
95 template <typename ContainerType, typename CompareFunction>
remove_heap(ContainerType & container,size_t index,const CompareFunction & compare)96 void remove_heap(ContainerType &container, size_t index,
97 const CompareFunction &compare) {
98 CHRE_ASSERT(index < container.size());
99 container.swap(index, container.size() - 1);
100
101 size_t parent = (index - 1) / 2;
102 // When index = 0, it has no parent and can only sift down.
103 if (index > 0 && compare(container[parent], container[index])) {
104 siftUp(container, index, compare);
105 } else {
106 siftDown(container, index, compare);
107 }
108 }
109
110 } // namespace chre
111
112 #endif // CHRE_UTIL_PRIORITY_QUEUE_IMPL_H_
113