| 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 |
} |