Line data Source code
1 : #include <stdlib.h>
2 : #include <string.h>
3 :
4 : #include <crater/pheap.h>
5 :
6 10001 : cr8r_pheap_node *cr8r_pheap_new(void *key, cr8r_pheap_ft *ft, cr8r_pheap_node *first_child, cr8r_pheap_node *sibling, cr8r_pheap_node *parent){
7 10001 : void *res = ft->alloc ? ft->alloc(&ft->base) : NULL;
8 10001 : if(res){
9 10001 : memcpy(res, key, ft->base.size);
10 10001 : memcpy(res + ft->base.size, &(cr8r_pheap_node){.first_child = first_child, .sibling = sibling, .parent = parent}, sizeof(cr8r_pheap_node));
11 : }
12 10001 : return res + ft->base.size;
13 : }
14 :
15 265055 : void *cr8r_pheap_top(cr8r_pheap_node *r, cr8r_pheap_ft *ft){
16 265055 : return r ? CR8R_OUTER_S(r, ft) : NULL;
17 : }
18 :
19 130 : cr8r_pheap_node *cr8r_pheap_root(cr8r_pheap_node *n){
20 130 : if(!n){
21 : return NULL;
22 : }
23 357 : while(n->parent){
24 228 : n = n->parent;
25 : }
26 : return n;
27 : }
28 :
29 2291404 : cr8r_pheap_node *cr8r_pheap_meld(cr8r_pheap_node *a, cr8r_pheap_node *b, cr8r_pheap_ft *ft){
30 2291404 : if(!a){
31 : return b;
32 2291402 : }else if(!b){
33 : return a;
34 1964740 : }else if(ft->cmp(&ft->base, CR8R_OUTER_S(a, ft), CR8R_OUTER_S(b, ft)) > 0){
35 685320 : a->sibling = b->first_child;
36 685320 : b->first_child = a;
37 685320 : a->parent = b;
38 685320 : return b;
39 : }
40 1279420 : b->sibling = a->first_child;
41 1279420 : a->first_child = b;
42 1279420 : b->parent = a;
43 1279420 : return a;
44 : }
45 :
46 10000 : cr8r_pheap_node *cr8r_pheap_push(cr8r_pheap_node *r, void *key, cr8r_pheap_ft *ft){
47 10000 : cr8r_pheap_node *n = cr8r_pheap_new(key, ft, NULL, NULL, NULL);
48 10000 : return n ? cr8r_pheap_meld(r, n, ft) : NULL;
49 : }
50 :
51 : /// helper function for cr8r_pheap_pop. Uses mergesort to combine a cr8r_pheap_node's children
52 : /// linked list into one pairing heap. Since the length of the list of children is
53 : /// not stored, this function accepts a recursion depth and is called by another helper
54 : /// function (cr8r_pheap_merge_exponential) with depth 0, 0, 1, 2, 3, 4, 5, 6, ... until all
55 : /// children are merged. If the list is empty, nothing is done. If the depth is 0,
56 : /// the first child in the remaining part of the list is removed and returned (1 node is sorted).
57 3466501 : static cr8r_pheap_node *cr8r_pheap_merge_binary(cr8r_pheap_node **n, size_t depth, cr8r_pheap_ft *ft){
58 3466501 : cr8r_pheap_node *a, *b;
59 3466501 : if(!*n){
60 : return NULL;
61 3139836 : }else if(!depth){
62 1954610 : a = *n;
63 1954610 : *n = (*n)->sibling;
64 1954610 : a->sibling = NULL;
65 1954610 : a->parent = NULL;
66 1954610 : return a;
67 : }
68 1185226 : a = cr8r_pheap_merge_binary(n, depth - 1, ft);
69 1185226 : b = cr8r_pheap_merge_binary(n, depth - 1, ft);
70 1185226 : return cr8r_pheap_meld(a, b, ft);
71 : }
72 :
73 : /// helper function for pheap_pop. Uses mergesort to combine a pheap_node's children
74 : /// linked list into one pairing heap.
75 263744 : static cr8r_pheap_node *cr8r_pheap_merge_exponential(cr8r_pheap_node **n, cr8r_pheap_ft *ft){
76 263744 : cr8r_pheap_node *a = cr8r_pheap_merge_binary(n, 0, ft);
77 1096049 : for(size_t depth = 0; *n; ++depth){
78 832305 : a = cr8r_pheap_meld(a, cr8r_pheap_merge_binary(n, depth, ft), ft);
79 : }
80 263744 : return a;
81 : }
82 :
83 263745 : cr8r_pheap_node *cr8r_pheap_pop(cr8r_pheap_node **r, cr8r_pheap_ft *ft){
84 263745 : if(!*r){
85 : return NULL;
86 : }
87 263744 : cr8r_pheap_node *ret = *r;
88 263744 : *r = cr8r_pheap_merge_exponential(&(*r)->first_child, ft);
89 263744 : return ret;
90 : }
91 :
92 130 : cr8r_pheap_node *cr8r_pheap_decreased_key(cr8r_pheap_node *n, cr8r_pheap_ft *ft){
93 130 : if(!n){
94 : return NULL;
95 : }
96 130 : cr8r_pheap_node *p = n->parent;
97 130 : if(!p || ft->cmp(&ft->base, CR8R_OUTER_S(p, ft), CR8R_OUTER_S(n, ft)) <= 0){
98 98 : return cr8r_pheap_root(p);
99 32 : }else if(p->first_child == n){
100 18 : p->first_child = n->sibling;
101 22 : }else for(cr8r_pheap_node *s = p->first_child;; s = s->sibling){
102 22 : if(s->sibling == n){
103 14 : s->sibling = n->sibling;
104 14 : break;
105 : }
106 : }
107 32 : n->sibling = NULL;
108 32 : n->parent = NULL;
109 32 : return cr8r_pheap_meld(cr8r_pheap_root(p), n, ft);
110 : }
111 :
112 6739 : void cr8r_pheap_delete(cr8r_pheap_node *r, cr8r_pheap_ft *ft){
113 6739 : if(!ft->free){
114 : return;
115 : }
116 10002 : for(cr8r_pheap_node *t; r;){
117 10001 : while(r->sibling){
118 6738 : cr8r_pheap_delete(r->sibling->first_child, ft);
119 6738 : t = r->sibling;
120 6738 : r->sibling = t->sibling;
121 6738 : ft->free(&ft->base, t);
122 : }
123 3263 : t = r;
124 3263 : r = r->first_child;
125 3263 : ft->free(&ft->base, t);
126 : }
127 : }
128 :
|
