1 /*
2 *
3 * Copyright (c) 2011, Jue Ruan <ruanjue@gmail.com>
4 *
5 *
6 * This program is free software: you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation, either version 3 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 #ifndef __HEAP_RJ_H
21 #define __HEAP_RJ_H
22
23 #include "list.h"
24
25 define_list(rjheapv, void*);
26
27 typedef int (*heap_comp_func)(const void *e1, const void *e2, void *ref);
28
29 typedef struct {
30 rjheapv *ptrs;
31 void *ref;
32 heap_comp_func cmp;
33 } Heap;
34
init_heap(heap_comp_func cmp,void * ref)35 static inline Heap* init_heap(heap_comp_func cmp, void *ref){
36 Heap *heap;
37 heap = malloc(sizeof(Heap));
38 heap->ptrs = init_rjheapv(8);
39 heap->cmp = cmp;
40 heap->ref = ref;
41 return heap;
42 }
43
free_heap(Heap * heap)44 static inline void free_heap(Heap *heap){ free_rjheapv(heap->ptrs); free(heap); }
45
clear_heap(Heap * heap)46 static inline void clear_heap(Heap *heap){ clear_rjheapv(heap->ptrs); }
47
push_heap(Heap * heap,void * p)48 static inline void push_heap(Heap *heap, void *p){
49 void *pp;
50 size_t i;
51 i = count_rjheapv(heap->ptrs);
52 push_rjheapv(heap->ptrs, p);
53 while(i && heap->cmp(get_rjheapv(heap->ptrs, i), get_rjheapv(heap->ptrs, (i - 1) >> 1), heap->ref) < 0){
54 pp = get_rjheapv(heap->ptrs, i);
55 set_rjheapv(heap->ptrs, i, get_rjheapv(heap->ptrs, (i - 1) >> 1));
56 set_rjheapv(heap->ptrs, (i - 1) >> 1, pp);
57 i = (i - 1) >> 1;
58 }
59 }
60
count_heap(Heap * heap)61 static inline size_t count_heap(Heap *heap){ return count_rjheapv(heap->ptrs); }
62
peer_heap(Heap * heap)63 static inline void* peer_heap(Heap *heap){ return (count_rjheapv(heap->ptrs)? get_rjheapv(heap->ptrs, 0) : NULL );}
64
remove_heap(Heap * heap,size_t idx)65 static inline void remove_heap(Heap *heap, size_t idx){
66 void *pp;
67 size_t swap;
68 set_rjheapv(heap->ptrs, idx, get_rjheapv(heap->ptrs, count_rjheapv(heap->ptrs) - 1));
69 trunc_rjheapv(heap->ptrs, 1);
70 while((idx << 1) + 1 < count_rjheapv(heap->ptrs)){
71 swap = idx;
72 if(heap->cmp((const void*)get_rjheapv(heap->ptrs, swap), (const void*)get_rjheapv(heap->ptrs, (idx << 1) + 1), heap->ref) > 0){
73 swap = (idx << 1) + 1;
74 }
75 if((idx << 1) + 2 < count_rjheapv(heap->ptrs) && heap->cmp((const void*)get_rjheapv(heap->ptrs, swap), (const void*)get_rjheapv(heap->ptrs, (idx << 1) + 2), heap->ref) > 0){
76 swap = (idx << 1) + 2;
77 }
78 if(swap == idx) break;
79 pp = get_rjheapv(heap->ptrs, idx);
80 set_rjheapv(heap->ptrs, idx, get_rjheapv(heap->ptrs, swap));
81 set_rjheapv(heap->ptrs, swap, pp);
82 idx = swap;
83 }
84 }
85
pop_heap(Heap * heap)86 static inline void* pop_heap(Heap *heap){
87 void *p;
88 if(count_rjheapv(heap->ptrs)){
89 p = get_rjheapv(heap->ptrs, 0);
90 remove_heap(heap, 0);
91 return p;
92 } else return NULL;
93 }
94
95 #endif
96