1
2 /**
3 * Tencent is pleased to support the open source community by making MSEC available.
4 *
5 * Copyright (C) 2016 THL A29 Limited, a Tencent company. All rights reserved.
6 *
7 * Licensed under the GNU General Public License, Version 2.0 (the "License");
8 * you may not use this file except in compliance with the License. You may
9 * obtain a copy of the License at
10 *
11 * https://opensource.org/licenses/GPL-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software distributed under the
14 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND,
15 * either express or implied. See the License for the specific language governing permissions
16 * and limitations under the License.
17 */
18
19
20 /**
21 * @filename heap.h
22 * @info flexible insert and delete heap, if no random deletion, use std::make_heap
23 * @time 2013-06-11
24 */
25
26 #ifndef __HEAP_ENTRY_FILE__
27 #define __HEAP_ENTRY_FILE__
28
29 #include <stdlib.h>
30 #include <stdio.h>
31 #include <string.h>
32 #include <assert.h>
33
34 #define heap_assert(statement)
35 //#define heap_assert(statement) assert(statement)
36
37 namespace NS_MICRO_THREAD {
38
39 class HeapEntry;
40 class HeapList;
41
42 /**
43 * @brief definition of heap elements for minimum heap
44 */
45 class HeapEntry
46 {
47 private:
48 int _index;
49
50 public:
51 friend class HeapList;
52
HeapEntry()53 HeapEntry():_index(0){};
~HeapEntry()54 virtual ~HeapEntry(){};
55
56 virtual unsigned long long HeapValue() = 0;
57
HeapIterate()58 virtual void HeapIterate() {
59 return;
60 };
61
62 inline int InsertIntoHeap(HeapList* list);
63
64 inline int DeleteFromHeap(HeapList* list);
65
GetIndex()66 inline int GetIndex() {
67 return _index;
68 };
69
70 private:
71
HeapValueCmp(HeapEntry * rhs)72 inline int HeapValueCmp(HeapEntry* rhs) {
73 if (this->HeapValue() == rhs->HeapValue()) {
74 return 0;
75 } else if (this->HeapValue() > rhs->HeapValue()) {
76 return 1;
77 } else {
78 return -1;
79 }
80 };
81
SetIndex(int index)82 inline void SetIndex(int index) {
83 _index = index;
84 };
85
86
87 };
88
89
90 /**
91 * @brief minimum heap queue.
92 */
93 class HeapList
94 {
95 private:
96 HeapEntry** _list;
97 int _max;
98 int _count;
99
100 public:
101
102 explicit HeapList(int max = 100000) {
103 _max = (max > 0) ? max : 100000;
104 _list = (HeapEntry**)malloc (sizeof(HeapEntry*) * (_max+1));
105 heap_assert(_list);
106 memset(_list, 0, sizeof(HeapEntry*) * (_max+1));
107 _count = 0;
108 };
~HeapList()109 virtual ~HeapList() {
110 if (_list) {
111 free(_list);
112 _list = NULL;
113 }
114 _max = 0;
115 _count = 0;
116 };
117
HeapResize(int size)118 int HeapResize(int size) {
119 if (_max >= size) {
120 return 0;
121 }
122
123 HeapEntry** new_list = (HeapEntry**)malloc(sizeof(HeapEntry*) * (size+1));
124 if (NULL == new_list) {
125 return -1;
126 }
127 memset(new_list, 0, sizeof(HeapEntry*) * (size+1));
128 memcpy(new_list, _list, sizeof(HeapEntry*) * (_max+1));
129 free(_list);
130 _list = new_list;
131 _max = size;
132
133 return 0;
134 };
135
136
137 int HeapPush(HeapEntry* entry);
138
139 HeapEntry* HeapPop();
140
141 int HeapDelete(HeapEntry* entry);
142
143 void HeapForeach();
144
HeapSize()145 int HeapSize() {
146 return _count;
147 };
148
HeapTop()149 HeapEntry* HeapTop() {
150 return (_count > 0) ? _list[1] : NULL;
151 };
152
153 private:
154
HeapFull()155 bool HeapFull() {
156 return (_count >= _max);
157 };
158
159
HeapEmpty()160 bool HeapEmpty() {
161 return (_count == 0);
162 };
163
164 void HeapUp();
165
166 void HeapDown(int index);
167
168 };
169
170
HeapUp()171 inline void HeapList::HeapUp()
172 {
173 for (int pos = _count; pos > 0; pos = pos/2)
174 {
175 if (pos/2 < 1) // pos == 1 peaked, 0 reserved.
176 {
177 break;
178 }
179
180 if (_list[pos]->HeapValueCmp(_list[pos/2]) < 0)
181 {
182 HeapEntry* tmp = _list[pos/2];
183 _list[pos/2] = _list[pos];
184 _list[pos] = tmp;
185
186 _list[pos]->SetIndex(pos);
187 _list[pos/2]->SetIndex(pos/2);
188 }
189 else
190 {
191 break;
192 }
193 }
194 }
195
196
HeapDown(int index)197 inline void HeapList::HeapDown(int index)
198 {
199 int min_son;
200 for (int pos = index; pos <= _count; pos = min_son)
201 {
202 if (pos*2 > _count) // pos is a leaf node.
203 {
204 break;
205 }
206 else if (pos*2 == _count)
207 {
208 min_son = pos*2;
209 }
210 else
211 {
212 if (_list[pos*2+1]->HeapValueCmp(_list[pos*2]) < 0)
213 {
214 min_son = pos*2+1;
215 }
216 else
217 {
218 min_son = pos*2;
219 }
220 }
221
222 if (_list[pos]->HeapValueCmp(_list[min_son]) > 0)
223 {
224 HeapEntry* tmp = _list[min_son];
225 _list[min_son] = _list[pos];
226 _list[pos] = tmp;
227
228 _list[pos]->SetIndex(pos);
229 _list[min_son]->SetIndex(min_son);
230 }
231 else
232 {
233 break;
234 }
235 }
236 }
237
238
HeapPush(HeapEntry * item)239 inline int HeapList::HeapPush(HeapEntry* item)
240 {
241 if (HeapFull()) {
242 heap_assert(0); // it's possible in theory but not in fact.
243 return -1;
244 }
245
246 if (item->GetIndex() != 0) {
247 heap_assert(0); // duplicated insertion.
248 return -2;
249 }
250
251 _count++;
252 _list[_count] = item;
253 item->SetIndex(_count);
254
255 HeapUp();
256
257 return 0;
258 }
259
260
HeapPop()261 inline HeapEntry* HeapList::HeapPop()
262 {
263 if (HeapEmpty()) {
264 return NULL;
265 }
266
267 HeapEntry* top = _list[1]; // 0 reserved.
268
269 _list[1] = _list[_count];
270 _list[1]->SetIndex(1);
271 _list[_count] = 0;
272
273 _count--;
274 HeapDown(1);
275
276 heap_assert(top->GetIndex() == 1);
277 top->SetIndex(0);
278 return top;
279 }
280
HeapDelete(HeapEntry * item)281 inline int HeapList::HeapDelete(HeapEntry* item)
282 {
283 if (HeapEmpty()) {
284 return -1;
285 }
286
287 int pos = item->GetIndex() ;
288 if ((pos > _count) ||(pos <= 0))
289 {
290 heap_assert(0); // duplicated deletion or illegal data.
291 return -2;
292 }
293
294 HeapEntry* del = _list[pos];
295 _list[pos] = _list[_count];
296 _list[pos]->SetIndex(pos);
297
298 _list[_count] = 0;
299 _count--;
300
301 HeapDown(pos);
302 heap_assert(pos == del->GetIndex());
303 del->SetIndex(0);
304 return 0;
305 }
306
307
HeapForeach()308 inline void HeapList::HeapForeach()
309 {
310 int per = 1;
311 for (int i = 1; i <= _count; i++)
312 {
313 if (i >= per*2)
314 {
315 printf("\n");
316 per *=2;
317 }
318 printf("%llu ", _list[i]->HeapValue());
319
320 _list[i]->HeapIterate();
321 }
322 }
323
InsertIntoHeap(HeapList * list)324 inline int HeapEntry::InsertIntoHeap(HeapList* list) {
325 return list->HeapPush(this);
326 };
327
DeleteFromHeap(HeapList * list)328 inline int HeapEntry::DeleteFromHeap(HeapList* list) {
329 return list->HeapDelete(this);
330 };
331
332 } // namespace end
333
334 #endif
335
336
337