Debian Codegraph @

libdrgn/splay_tree.c

raw
1 // Copyright (c) Meta Platforms, Inc. and affiliates.
2 // SPDX-License-Identifier: LGPL-2.1-or-later
3
4 #include "binary_search_tree.h" // IWYU pragma: associated
5
6 /*
7 * Binary search tree splay operation based on the original paper [1]. Rotations
8 * are inlined to avoid redundant pointer assignments. We still do redundant
9 * assignments to great_grandparent->{left,right} and node->{left,right}; this
10 * was faster in microbenchmarks than doing the extra tracking to avoid the
11 * reassignments.
12 *
13 * This assumes that the node is not already the root.
14 *
15 * 1: "Self-Adjusting Binary Search Trees" (Sleator & Tarjan, 1985):
16 * http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf
17 */
18 void drgn_splay_tree_splay(struct binary_tree_node **root,
19 struct binary_tree_node *node,
20 struct binary_tree_node *parent)
21 {
22 for (;;) {
23 struct binary_tree_node *grandparent, *great_grandparent;
24
25 grandparent = parent->parent;
26 if (node == parent->left) {
27 if (!grandparent) {
28 /*
29 * Zig step: rotate_right(parent). The node
30 * takes the place of its parent, which is the
31 * root.
32 */
33 parent->left = node->right;
34 node->right = parent;
35
36 if (parent->left)
37 parent->left->parent = parent;
38 parent->parent = node;
39 break;
40 } else {
41 great_grandparent = grandparent->parent;
42 if (parent == grandparent->left) {
43 /*
44 * Zig-zig step:
45 * rotate_right(grandparent),
46 * rotate_right(parent).
47 */
48 grandparent->left = parent->right;
49 parent->left = node->right;
50 parent->right = grandparent;
51 node->right = parent;
52
53 if (grandparent->left)
54 grandparent->left->parent = grandparent;
55 grandparent->parent = parent;
56 if (parent->left)
57 parent->left->parent = parent;
58 parent->parent = node;
59 } else {
60 /*
61 * Zig-zag step: rotate_right(parent),
62 * rotate_left(grandparent).
63 */
64 grandparent->right = node->left;
65 parent->left = node->right;
66 node->left = grandparent;
67 node->right = parent;
68
69 if (grandparent->right)
70 grandparent->right->parent = grandparent;
71 if (parent->left)
72 parent->left->parent = parent;
73 grandparent->parent = node;
74 parent->parent = node;
75 }
76 }
77 } else {
78 if (!grandparent) {
79 /*
80 * Zig step: rotate_left(parent). The node
81 * takes the place of its parent, which is the
82 * root.
83 */
84 parent->right = node->left;
85 node->left = parent;
86
87 if (parent->right)
88 parent->right->parent = parent;
89 parent->parent = node;
90 break;
91 } else {
92 great_grandparent = grandparent->parent;
93 if (parent == grandparent->right) {
94 /*
95 * Zig-zig step:
96 * rotate_left(grandparent),
97 * rotate_left(parent).
98 */
99 grandparent->right = parent->left;
100 parent->right = node->left;
101 parent->left = grandparent;
102 node->left = parent;
103
104 if (grandparent->right)
105 grandparent->right->parent = grandparent;
106 grandparent->parent = parent;
107 if (parent->right)
108 parent->right->parent = parent;
109 parent->parent = node;
110 } else {
111 /*
112 * Zig-zag step: rotate_left(parent),
113 * rotate_right(grandparent).
114 */
115 grandparent->left = node->right;
116 parent->right = node->left;
117 node->right = grandparent;
118 node->left = parent;
119
120 if (grandparent->left)
121 grandparent->left->parent = grandparent;
122 if (parent->right)
123 parent->right->parent = parent;
124 grandparent->parent = node;
125 parent->parent = node;
126 }
127 }
128 }
129 /*
130 * Common code for zig-zig and zig-zag steps, both left and
131 * right. The node took the place of its grandparent, which may
132 * have been the root. We don't need to update the node's parent
133 * pointer because it is always NULL in the end.
134 */
135 if (!great_grandparent)
136 break;
137 if (grandparent == great_grandparent->left)
138 great_grandparent->left = node;
139 else
140 great_grandparent->right = node;
141 parent = great_grandparent;
142 }
143
144 /* The node reached the root. */
145 *root = node;
146 node->parent = NULL;
147 }
148
149 static inline void drgn_splay_tree_transplant(struct binary_tree_node **root,
150 struct binary_tree_node *old,
151 struct binary_tree_node *new)
152 {
153 if (!old->parent)
154 *root = new;
155 else if (old == old->parent->left)
156 old->parent->left = new;
157 else
158 old->parent->right = new;
159 if (new)
160 new->parent = old->parent;
161 }
162
163 void drgn_splay_tree_delete(struct binary_tree_node **root,
164 struct binary_tree_node *node)
165 {
166 if (node->left == NULL) {
167 drgn_splay_tree_transplant(root, node, node->right);
168 } else if (node->right == NULL) {
169 drgn_splay_tree_transplant(root, node, node->left);
170 } else {
171 struct binary_tree_node *successor;
172
173 successor = node->right;
174 if (successor->left) {
175 do {
176 successor = successor->left;
177 } while (successor->left);
178 drgn_splay_tree_transplant(root, successor, successor->right);
179 successor->right = node->right;
180 successor->right->parent = successor;
181 }
182 drgn_splay_tree_transplant(root, node, successor);
183 successor->left = node->left;
184 successor->left->parent = successor;
185 }
186 if (node->parent && node->parent->parent)
187 drgn_splay_tree_splay(root, node->parent, node->parent->parent);
188 }