Line data    Source code

       1             : #include <stdlib.h>
       2             : #include <string.h>
       3             : #include <inttypes.h>
       4             : #include <limits.h>
       5             : 
       6             : #include <crater/heap.h>
       7             : 
       8             : CR8R_ATTR_NO_SAN("unsigned-integer-overflow")
       9       20114 : void cr8r_heap_ify(cr8r_vec *self, cr8r_vec_ft *ft, int ord){
      10     9256907 :     for(uint64_t i = self->len ? (ULLONG_MAX >> 1) >> __builtin_clzll(self->len) : 0; i--;){
      11     9216679 :         cr8r_heap_sift_down(self, ft, self->buf + i*ft->base.size, ord);//void pointer arithmetic works like char pointer arithmetic
      12             :     }
      13       20114 : }
      14             : 
      15      265055 : void *cr8r_heap_top(cr8r_vec *self, cr8r_vec_ft *ft){
      16      265055 :     return self->len ? self->buf : NULL;
      17             : }
      18             : 
      19      109000 : void cr8r_heap_sift_up(cr8r_vec *self, cr8r_vec_ft *ft, void *e, int ord){
      20      220609 :     for(uint64_t i = (e - self->buf)/ft->base.size, j; i; i = j){
      21      216431 :         j = (i - 1) >> 1;
      22      216431 :         if(ord*ft->cmp(&ft->base, self->buf + i*ft->base.size, self->buf + j*ft->base.size) <= 0){
      23             :             break;
      24             :         }
      25      111609 :         ft->swap(&ft->base, self->buf + i*ft->base.size, self->buf + j*ft->base.size);
      26             :     }
      27      109000 : }
      28             : 
      29    21249103 : void cr8r_heap_sift_down(cr8r_vec *self, cr8r_vec_ft *ft, void *e, int ord){
      30    21249103 :     uint64_t i = (e - self->buf)/ft->base.size;
      31    21249103 :     uint64_t l = (i << 1) + 1, r = l + 1, j;
      32   148069052 :     while(r < self->len){
      33   131162190 :         j = ord*ft->cmp(&ft->base, self->buf + l*ft->base.size, self->buf + r*ft->base.size) >= 0 ? l : r;
      34   131162190 :         if(ord*ft->cmp(&ft->base, self->buf + i*ft->base.size, self->buf + j*ft->base.size) >= 0){
      35             :             return;
      36             :         }
      37   126819949 :         ft->swap(&ft->base, self->buf + i*ft->base.size, self->buf + j*ft->base.size);
      38   126819949 :         i = j;
      39   126819949 :         l = (i << 1) + 1, r = l + 1;
      40             :     }
      41    16906862 :     if(l < self->len && ord*ft->cmp(&ft->base, self->buf + i*ft->base.size, self->buf + l*ft->base.size) < 0){
      42       52599 :         ft->swap(&ft->base, self->buf + i*ft->base.size, self->buf + l*ft->base.size);
      43             :     }
      44             : }
      45             : 
      46       10000 : bool cr8r_heap_push(cr8r_vec *self, cr8r_vec_ft *ft, const void *e, int ord){
      47       10000 :     if(!cr8r_vec_pushr(self, ft, e)){
      48             :         return 0;
      49             :     }
      50       10000 :     cr8r_heap_sift_up(self, ft, self->buf + (self->len - 1)*ft->base.size, ord);
      51       10000 :     return 1;
      52             : }
      53             : 
      54    11777370 : bool cr8r_heap_pop(cr8r_vec *self, cr8r_vec_ft *ft, void *o, int ord){
      55    11777370 :     if(self->len > 1){
      56    11777370 :         ft->swap(&ft->base, self->buf, self->buf + (self->len - 1)*ft->base.size);
      57             :     }
      58    11777370 :     if(!cr8r_vec_popr(self, ft, o)){
      59             :         return 0;
      60             :     }
      61    11777370 :     if(self->len){
      62    11777370 :         cr8r_heap_sift_down(self, ft, self->buf, ord);
      63             :     }
      64             :     return 1;
      65             : }
      66             :