Line data Source code
1 : #include <stdlib.h>
2 : #include <string.h>
3 : #include <inttypes.h>
4 : #include <limits.h>
5 :
6 : #include <crater/minmax_heap.h>
7 :
8 : CR8R_ATTR_NO_SAN("unsigned-integer-overflow")
9 1 : void cr8r_mmheap_ify(cr8r_vec *self, cr8r_vec_ft *ft){
10 512 : for(uint64_t i = (ULLONG_MAX >> 1) >> __builtin_clzll(self->len); i--;){
11 511 : cr8r_mmheap_sift_down(self, ft, self->buf + i*ft->base.size);//void pointer arithmetic works like char pointer arithmetic
12 : }
13 1 : }
14 :
15 2001 : void *cr8r_mmheap_peek_min(cr8r_vec *self, cr8r_vec_ft *ft){
16 2001 : return self->len ? self->buf : NULL;
17 : }
18 :
19 477002 : void *cr8r_mmheap_peek_max(cr8r_vec *self, cr8r_vec_ft *ft){
20 477002 : if(self->len < 3){
21 1 : return self->len ? self->buf + (self->len - 1)*ft->base.size : NULL;
22 : }
23 477001 : void *l = self->buf + 1*ft->base.size, *r = self->buf + 2*ft->base.size;
24 477001 : return ft->cmp(&ft->base, l, r) > 0 ? l : r;
25 : }
26 :
27 2500000 : void cr8r_mmheap_sift_up(cr8r_vec *self, cr8r_vec_ft *ft, void *e){
28 2500000 : if(e == self->buf){
29 : return;
30 : }
31 2497500 : uint64_t i = (e - self->buf)/ft->base.size;
32 : // the bit length of i + 1 gives a good way to compute the ceil of the
33 : // binary log of i + 2, which is the height of the shortest complete
34 : // heap containing an ith element. If there is an odd number of layers,
35 : // i is in a min layer, otherwise it is in a max layer. Finally,
36 : // note the parity of the bit length of i + 1 is the same as the parity of
37 : // the number of leading zeros of i + 1.
38 2497500 : bool is_min_layer = __builtin_clzll(i + 1)&1;
39 2497500 : uint64_t i1 = (i - 1) >> 1;
40 2497500 : void *e1 = self->buf + i1*ft->base.size;
41 2497500 : int ord = is_min_layer ? 1 : -1;
42 2497500 : if(ord*ft->cmp(&ft->base, e1, e) < 0){
43 837362 : ft->swap(&ft->base, e, e1);
44 837362 : i = i1;
45 837362 : e = e1;
46 837362 : ord = -ord;
47 : }
48 6798772 : while(i > 2){
49 5043231 : i1 = (i - 3) >> 2;
50 5043231 : e1 = self->buf + i1*ft->base.size;
51 5043231 : if(ord*ft->cmp(&ft->base, e, e1) < 0){
52 4301272 : ft->swap(&ft->base, e, e1);
53 4301272 : i = i1;
54 4301272 : e = e1;
55 : }else{
56 : break;
57 : }
58 : }
59 : }
60 :
61 2275511 : void cr8r_mmheap_sift_down(cr8r_vec *self, cr8r_vec_ft *ft, void *e){
62 2275511 : uint64_t i = (e - self->buf)/ft->base.size;
63 2275511 : bool is_min_layer = __builtin_clzll(i + 1)&1;
64 2275511 : int ord = is_min_layer ? 1 : -1;
65 6558243 : while(2*i + 1 < self->len){
66 : // Find m and em, the index of the extremal element and a pointer to the extremal element
67 : // respectively among the children and grandchildren of e. For min layers, extremal means
68 : // minimal, and for max layers it means maximal
69 6294867 : uint64_t m = 2*i + 1;
70 6294867 : void *em = self->buf + m*ft->base.size;
71 6294867 : const uint64_t idxs[] = {2*i + 2, 4*i + 3, 4*i + 4, 4*i + 5, 4*i + 6};
72 30925032 : for(uint64_t ii = 0; ii < sizeof(idxs)/sizeof(uint64_t) && idxs[ii] < self->len; ++ii){
73 24630165 : void *ei = self->buf + idxs[ii]*ft->base.size;
74 24630165 : if(ord*ft->cmp(&ft->base, ei, em) < 0){
75 12449233 : m = idxs[ii];
76 12449233 : em = ei;
77 : }
78 : }
79 : // If em is a grandchild of e (as should be the case most of the time)
80 : // we may have to sift down farther after fixing up here
81 6294867 : if(m > 2*i + 2){
82 5029008 : if(ord*ft->cmp(&ft->base, em, e) < 0){
83 4282732 : ft->swap(&ft->base, em, e);
84 4282732 : uint64_t p = (m - 1) >> 1;
85 4282732 : void *ep = self->buf + p*ft->base.size;
86 4282732 : if(ord*ft->cmp(&ft->base, ep, em) < 0){
87 199642 : ft->swap(&ft->base, em, ep);
88 : }
89 4282732 : i = m;
90 4282732 : e = em;
91 : }else{
92 : break;
93 : }
94 : }else{// otherwise em is a direct child so it must be a leaf or its invariant would be wrong
95 1265859 : if(ord*ft->cmp(&ft->base, em, e) < 0){
96 176063 : ft->swap(&ft->base, em, e);
97 : }
98 : break;
99 : }
100 : }
101 2275511 : }
102 :
103 2500001 : bool cr8r_mmheap_push(cr8r_vec *self, cr8r_vec_ft *ft, const void *e){
104 2500001 : if(!cr8r_vec_pushr(self, ft, e)){
105 : return 0;
106 : }
107 2500000 : cr8r_mmheap_sift_up(self, ft, cr8r_vec_getx(self, ft, -1));
108 2500000 : return 1;
109 : }
110 :
111 900000 : bool cr8r_mmheap_pop_min(cr8r_vec *self, cr8r_vec_ft *ft, void *o){
112 900000 : return cr8r_mmheap_pop_idx(self, ft, o, 0);
113 : }
114 :
115 1375001 : bool cr8r_mmheap_pop_max(cr8r_vec *self, cr8r_vec_ft *ft, void *o){
116 1375001 : if(self->len < 3){
117 1 : return self->len ? cr8r_mmheap_pop_idx(self, ft, o, self->len - 1) : false;
118 : }
119 1375000 : void *l = self->buf + 1*ft->base.size, *r = self->buf + 2*ft->base.size;
120 2548741 : return cr8r_mmheap_pop_idx(self, ft, o, ft->cmp(&ft->base, l, r) > 0 ? 1 : 2);
121 : }
122 :
123 2275000 : bool cr8r_mmheap_pop_idx(cr8r_vec *self, cr8r_vec_ft *ft, void *o, uint64_t i){
124 2275000 : if(i == self->len - 1){
125 0 : return cr8r_vec_popr(self, ft, o);
126 2275000 : }else if(!self->len){
127 : return 0;
128 : }
129 2275000 : void *e = self->buf + i*ft->base.size;
130 2275000 : memcpy(o, e, ft->base.size);
131 2275000 : cr8r_vec_popr(self, ft, e);
132 2275000 : cr8r_mmheap_sift_down(self, ft, e);
133 2275000 : return 1;
134 : }
135 :
136 900000 : bool cr8r_mmheap_pushpop_min(cr8r_vec *self, cr8r_vec_ft *ft, const void *e, void *o){
137 900000 : if(!cr8r_mmheap_push(self, ft, e)){
138 : return 0;
139 : }
140 900000 : return cr8r_mmheap_pop_min(self, ft, o);
141 : }
142 :
143 1375000 : bool cr8r_mmheap_pushpop_max(cr8r_vec *self, cr8r_vec_ft *ft, const void *e, void *o){
144 1375000 : if(!cr8r_mmheap_push(self, ft, e)){
145 : return 0;
146 : }
147 1375000 : return cr8r_mmheap_pop_max(self, ft, o);
148 : }
149 :
|
