1 /*
2 * This file is part of the MicroPython project, http://micropython.org/
3 *
4 * The MIT License (MIT)
5 *
6 * Copyright (c) 2020 Damien P. George
7 *
8 * Permission is hereby granted, free of charge, to any person obtaining a copy
9 * of this software and associated documentation files (the "Software"), to deal
10 * in the Software without restriction, including without limitation the rights
11 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12 * copies of the Software, and to permit persons to whom the Software is
13 * furnished to do so, subject to the following conditions:
14 *
15 * The above copyright notice and this permission notice shall be included in
16 * all copies or substantial portions of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
24 * THE SOFTWARE.
25 */
26
27 #include "py/pairheap.h"
28
29 // The mp_pairheap_t.next pointer can take one of the following values:
30 // - NULL: the node is the top of the heap
31 // - LSB set: the node is the last of the children and points to its parent node
32 // - other: the node is a child and not the last child
33 // The macros below help manage this pointer.
34 #define NEXT_MAKE_RIGHTMOST_PARENT(parent) ((void *)((uintptr_t)(parent) | 1))
35 #define NEXT_IS_RIGHTMOST_PARENT(next) ((uintptr_t)(next) & 1)
36 #define NEXT_GET_RIGHTMOST_PARENT(next) ((void *)((uintptr_t)(next) & ~1))
37
38 // O(1), stable
mp_pairheap_meld(mp_pairheap_lt_t lt,mp_pairheap_t * heap1,mp_pairheap_t * heap2)39 mp_pairheap_t *mp_pairheap_meld(mp_pairheap_lt_t lt, mp_pairheap_t *heap1, mp_pairheap_t *heap2) {
40 if (heap1 == NULL) {
41 return heap2;
42 }
43 if (heap2 == NULL) {
44 return heap1;
45 }
46 if (lt(heap1, heap2)) {
47 if (heap1->child == NULL) {
48 heap1->child = heap2;
49 } else {
50 heap1->child_last->next = heap2;
51 }
52 heap1->child_last = heap2;
53 heap2->next = NEXT_MAKE_RIGHTMOST_PARENT(heap1);
54 return heap1;
55 } else {
56 heap1->next = heap2->child;
57 heap2->child = heap1;
58 if (heap1->next == NULL) {
59 heap2->child_last = heap1;
60 heap1->next = NEXT_MAKE_RIGHTMOST_PARENT(heap2);
61 }
62 return heap2;
63 }
64 }
65
66 // amortised O(log N), stable
mp_pairheap_pairing(mp_pairheap_lt_t lt,mp_pairheap_t * child)67 mp_pairheap_t *mp_pairheap_pairing(mp_pairheap_lt_t lt, mp_pairheap_t *child) {
68 if (child == NULL) {
69 return NULL;
70 }
71 mp_pairheap_t *heap = NULL;
72 while (!NEXT_IS_RIGHTMOST_PARENT(child)) {
73 mp_pairheap_t *n1 = child;
74 child = child->next;
75 n1->next = NULL;
76 if (!NEXT_IS_RIGHTMOST_PARENT(child)) {
77 mp_pairheap_t *n2 = child;
78 child = child->next;
79 n2->next = NULL;
80 n1 = mp_pairheap_meld(lt, n1, n2);
81 }
82 heap = mp_pairheap_meld(lt, heap, n1);
83 }
84 heap->next = NULL;
85 return heap;
86 }
87
88 // amortised O(log N), stable
mp_pairheap_delete(mp_pairheap_lt_t lt,mp_pairheap_t * heap,mp_pairheap_t * node)89 mp_pairheap_t *mp_pairheap_delete(mp_pairheap_lt_t lt, mp_pairheap_t *heap, mp_pairheap_t *node) {
90 // Simple case of the top being the node to delete
91 if (node == heap) {
92 mp_pairheap_t *child = heap->child;
93 node->child = NULL;
94 return mp_pairheap_pairing(lt, child);
95 }
96
97 // Case where node is not in the heap
98 if (node->next == NULL) {
99 return heap;
100 }
101
102 // Find parent of node
103 mp_pairheap_t *parent = node;
104 while (!NEXT_IS_RIGHTMOST_PARENT(parent->next)) {
105 parent = parent->next;
106 }
107 parent = NEXT_GET_RIGHTMOST_PARENT(parent->next);
108
109 // Replace node with pairing of its children
110 mp_pairheap_t *next;
111 if (node == parent->child && node->child == NULL) {
112 if (NEXT_IS_RIGHTMOST_PARENT(node->next)) {
113 parent->child = NULL;
114 } else {
115 parent->child = node->next;
116 }
117 node->next = NULL;
118 return heap;
119 } else if (node == parent->child) {
120 mp_pairheap_t *child = node->child;
121 next = node->next;
122 node->child = NULL;
123 node->next = NULL;
124 node = mp_pairheap_pairing(lt, child);
125 parent->child = node;
126 } else {
127 mp_pairheap_t *n = parent->child;
128 while (node != n->next) {
129 n = n->next;
130 }
131 mp_pairheap_t *child = node->child;
132 next = node->next;
133 node->child = NULL;
134 node->next = NULL;
135 node = mp_pairheap_pairing(lt, child);
136 if (node == NULL) {
137 node = n;
138 } else {
139 n->next = node;
140 }
141 }
142 node->next = next;
143 if (NEXT_IS_RIGHTMOST_PARENT(next)) {
144 parent->child_last = node;
145 }
146 return heap;
147 }
148