xref: /f-stack/app/micro_thread/heap.h (revision a9643ea8) 
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 ������ɾ���Ķ�,  �����û�����ɾ������, ������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 ��С�ѵĶ�Ԫ�ض���, ���ڹ���ͨ�õĶ�, �̳и�Ԫ�ؼ�����չ
44  */
45 class HeapEntry
46 {
47 private:
48     int  _index;          ///<  ��Ԫ���±�, ���ڿ�������ɾ������
49 
50 public:
51 	friend class HeapList;
52 
53     /**
54      *  @brief ����������������
55      */
56 	HeapEntry():_index(0){};
57 	virtual ~HeapEntry(){};
58 
59     /**
60      *  @brief ��Ԫ��ȡֵ����, ���ڷ���ֵ�Ƚ�, ���Ӻ���ʵ��, ����Ĭ������
61      *  @return ��Ԫ��ӳ���ֵ
62      */
63     virtual unsigned long long HeapValue() = 0;
64 
65 
66     /**
67      *  @brief �ѱ����ӿ�, ���ڵ���, �ڱ���ÿ��Ԫ��ʱ������, ��ѡʵ��
68      */
69     virtual void HeapIterate() {
70         return;
71     };
72 
73     /**
74      *  @brief ��Ԫ�ز������
75      *  @param list ��ָ��
76      *  @return 0 �ɹ�; ����ʧ��  -1 ����; -2 �ظ�����
77      */
78     inline int InsertIntoHeap(HeapList* list);
79 
80     /**
81      *  @brief ��Ԫ�شӶ���ɾ��
82      *  @param list ��ָ��
83      *  @return 0 �ɹ�; ����ʧ��  -1 �ѿ�; -2 �ظ�ɾ����������
84      */
85     inline int DeleteFromHeap(HeapList* list);
86 
87 
88     /**
89      *  @brief ��Ԫ���±���Ϣ��ȡ, �ڲ�����ʹ��
90      *  @return ��Ԫ���ڶ����±���Ϣ
91      */
92 	inline int GetIndex() {
93 		return _index;
94 	};
95 
96 private:
97 
98     inline int HeapValueCmp(HeapEntry* rhs) {
99         if (this->HeapValue() == rhs->HeapValue()) {
100             return 0;
101         } else if (this->HeapValue() > rhs->HeapValue()) {
102             return 1;
103         } else {
104             return -1;
105         }
106     };
107 
108 	inline void SetIndex(int index) {
109 		_index = index;
110 	};
111 
112 
113 };
114 
115 
116 /**
117  *  @brief ��С�Ѷ�����, ͨ����
118  */
119 class HeapList
120 {
121 private:
122 	HeapEntry**  _list;         // ��Ԫ�ص�ָ������, Ŀǰ����
123 	int          _max;          // �ѿɹ������Ԫ�ظ���
124 	int          _count;        // ���Ѿ������Ԫ�ظ���
125 
126 public:
127 
128     /**
129      *  @brief ���캯������������
130      */
131 	explicit HeapList(int max = 100000) {
132         _max = (max > 0) ? max : 100000;
133 		_list = (HeapEntry**)malloc (sizeof(HeapEntry*) * (_max+1));
134 		heap_assert(_list);
135 		memset(_list, 0, sizeof(HeapEntry*) * (_max+1));
136 		_count = 0;
137 	};
138 	virtual ~HeapList()  {
139 		if (_list) {
140 		    free(_list);
141 			_list = NULL;
142 		}
143         _max = 0;
144         _count = 0;
145 	};
146 
147     /**
148      *  @brief ��չheap�Ĵ�С, ��С�����
149      *  @param size �µĶ�Ԫ�ظ���
150      *  @return 0 �ɹ�; -1 ʧ��
151      */
152     int HeapResize(int size) {
153         if (_max >= size) {
154             return 0;
155         }
156 
157         HeapEntry** new_list = (HeapEntry**)malloc(sizeof(HeapEntry*) * (size+1));
158         if (NULL == new_list) {
159             return -1;
160         }
161         memset(new_list, 0, sizeof(HeapEntry*) * (size+1));
162         memcpy(new_list, _list, sizeof(HeapEntry*) * (_max+1));
163         free(_list);
164         _list = new_list;
165         _max = size;
166 
167         return 0;
168     };
169 
170 
171     /**
172      *  @brief �����Ԫ��
173      *  @param entry ��Ԫ��ָ��
174      *  @return 0 �ɹ�; ����ʧ��  -1 ����; -2 �ظ�����
175      */
176 	int HeapPush(HeapEntry* entry);
177 
178     /**
179      *  @brief ȡ�Ѷ�Ԫ��, ���Ƴ���Ԫ��
180      *  @return �Ѷ�Ԫ��ָ��, NULL ��ʾ��Ϊ��
181      */
182 	HeapEntry* HeapPop();
183 
184     /**
185      *  @brief �Ƴ������Ԫ��
186      *  @param entry ��Ԫ��ָ��
187      *  @return 0 �ɹ�; ����ʧ��  -1 �ѿ�; -2 �ظ�ɾ����������
188      */
189 	int HeapDelete(HeapEntry* entry);
190 
191     /**
192      *  @brief ���Խӿ�, ��2��ѷ�ʽ��ӡԪ��, ͬʱ����ÿԪ�صĵ����ӿ�
193      */
194 	void HeapForeach();
195 
196     /**
197      *  @brief ��ȡ�ѵ�Ԫ�ظ���
198      *  @return ��Ԫ��ʵ����Ŀ
199      */
200     int HeapSize() {
201         return _count;
202     };
203 
204     /**
205      *  @brief ȡ�Ѷ�Ԫ��, ���Ƴ���Ԫ��
206      *  @return �Ѷ�Ԫ��ָ��, NULL ��ʾ��Ϊ��
207      */
208     HeapEntry* HeapTop() {
209         return (_count > 0) ? _list[1] : NULL;
210     };
211 
212 private:
213 
214     /**
215      *  @brief �ж����Ƿ���
216      *  @return true ��
217      */
218 	bool HeapFull() {
219 		return (_count >= _max);
220 	};
221 
222     /**
223      *  @brief �ж����Ƿ��
224      *  @return true ��
225      */
226 	bool HeapEmpty() {
227 		return (_count == 0);
228 	};
229 
230     /**
231      *  @brief ���ȽϺ���, �������Ŷ�Ԫ��
232      */
233 	void HeapUp();
234 
235     /**
236      *  @brief ���ȽϺ���, �������Ŷ�Ԫ��
237      */
238 	void HeapDown(int index);
239 
240 };
241 
242 /**
243  *  @brief ���ȽϺ���, �������Ŷ�Ԫ��
244  */
245 inline void HeapList::HeapUp()
246 {
247 	for (int pos = _count; pos > 0; pos = pos/2)
248 	{
249 		if (pos/2 < 1)   // pos == 1 �Ѿ�����, 0 ���ڱ���
250 		{
251 			break;
252 		}
253 
254         if (_list[pos]->HeapValueCmp(_list[pos/2]) < 0)
255 		{
256 			HeapEntry* tmp = _list[pos/2];
257 			_list[pos/2] = _list[pos];
258 			_list[pos] = tmp;
259 
260 			_list[pos]->SetIndex(pos);
261 			_list[pos/2]->SetIndex(pos/2);
262 		}
263 		else
264 		{
265 			break;
266 		}
267 	}
268 }
269 
270 
271 /**
272  *  @brief ���ȽϺ���, �������Ŷ�Ԫ��
273  *  @param index �Ӹ�λ�ÿ�ʼ����
274  */
275 inline void HeapList::HeapDown(int index)
276 {
277 	int  min_son;
278 	for (int pos = index; pos <= _count;  pos = min_son)
279 	{
280 		if  (pos*2 > _count)  // pos��Ҷ�ӽڵ���
281 		{
282 			break;
283 		}
284 		else if (pos*2 == _count)
285 		{
286 			min_son = pos*2;
287 		}
288 		else
289 		{
290             if (_list[pos*2+1]->HeapValueCmp(_list[pos*2]) < 0)
291 			{
292 				min_son = pos*2+1;
293 			}
294 			else
295 			{
296 				min_son = pos*2;
297 			}
298 		}
299 
300 		if  (_list[pos]->HeapValueCmp(_list[min_son]) > 0)
301 		{
302 			HeapEntry* tmp = _list[min_son];
303 			_list[min_son] = _list[pos];
304 			_list[pos] = tmp;
305 
306 			_list[pos]->SetIndex(pos);
307 			_list[min_son]->SetIndex(min_son);
308 		}
309 		else
310 		{
311 			break;
312 		}
313 	}
314 }
315 
316 
317 /**
318  *  @brief �����Ԫ��
319  *  @param entry ��Ԫ��ָ��
320  *  @return 0 �ɹ�; ����ʧ��  -1 ����; -2 �ظ�����
321  */
322 inline int HeapList::HeapPush(HeapEntry*  item)
323 {
324 	if (HeapFull()) {
325         heap_assert(0); // ��, �������ǿ��ܵ�, ʵ�����в�̫���ܹ�10W
326 		return -1;
327 	}
328 
329     if (item->GetIndex() != 0) {
330         heap_assert(0); // �ظ�����
331         return -2;
332     }
333 
334 	_count++;
335 	_list[_count] = item;
336     item->SetIndex(_count);
337 
338 	HeapUp();
339 
340 	return 0;
341 }
342 
343 
344 /**
345  *  @brief ȡ�Ѷ�Ԫ��, ���Ƴ���Ԫ��
346  *  @return �Ѷ�Ԫ��ָ��, NULL ��ʾ��Ϊ��
347  */
348 inline HeapEntry* HeapList::HeapPop()
349 {
350 	if  (HeapEmpty()) {
351 		return NULL;
352 	}
353 
354 	HeapEntry* top = _list[1];	// 0 ����
355 
356 	_list[1] = _list[_count];
357     _list[1]->SetIndex(1);
358     _list[_count] = 0;
359 
360 	_count--;
361 	HeapDown(1);
362 
363     heap_assert(top->GetIndex() == 1);
364 	top->SetIndex(0);
365 	return top;
366 }
367 
368 /**
369  *  @brief �Ƴ������Ԫ��
370  *  @param entry ��Ԫ��ָ��
371  *  @return 0 �ɹ�; ����ʧ��  -1 �ѿ�; -2 �ظ�ɾ����������
372  */
373 inline int  HeapList::HeapDelete(HeapEntry* item)
374 {
375 	if  (HeapEmpty()) {
376 		return -1;
377 	}
378 
379 	int pos = item->GetIndex() ;
380 	if  ((pos > _count)  ||(pos <= 0))
381 	{
382         heap_assert(0); // �Ƿ����ݻ��ظ�ɾ��
383 		return -2;
384 	}
385 
386 	HeapEntry* del = _list[pos];
387 	_list[pos] = _list[_count];
388     _list[pos]->SetIndex(pos);
389 
390     _list[_count] = 0;
391 	_count--;
392 
393 	HeapDown(pos);
394     heap_assert(pos == del->GetIndex());
395 	del->SetIndex(0);
396 	return 0;
397 }
398 
399 
400 /**
401  *  @brief ���Խӿ�, ��2��ѷ�ʽ��ӡԪ��, ͬʱ����ÿԪ�صĵ����ӿ�
402  */
403 inline void HeapList::HeapForeach()
404 {
405     int per = 1;
406 	for (int i = 1; i <= _count; i++)
407 	{
408 	    if (i >= per*2)
409 	    {
410 	        printf("\n");
411 	        per *=2;
412 	    }
413 		printf("%llu ", _list[i]->HeapValue());
414 
415         _list[i]->HeapIterate();
416 	}
417 }
418 
419 /**
420  *  @brief ��Ԫ�ز������
421  *  @param list ��ָ��
422  *  @return 0 �ɹ�; ����ʧ��  -1 ����; -2 �ظ�����
423  */
424 inline int HeapEntry::InsertIntoHeap(HeapList* list) {
425     return list->HeapPush(this);
426 };
427 
428 /**
429  *  @brief ��Ԫ�شӶ���ɾ��
430  *  @param list ��ָ��
431  *  @return 0 �ɹ�; ����ʧ��  -1 �ѿ�; -2 �ظ�ɾ����������
432  */
433 inline int HeapEntry::DeleteFromHeap(HeapList* list) {
434     return list->HeapDelete(this);
435 };
436 
437 } // namespace end
438 
439 #endif
440 
441 
442