blob: e76efe717f2154f5222af1d81c935ec5b3a5e49f (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
//===-- Implementation for freetrie ---------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "freetrie.h"
namespace LIBC_NAMESPACE_DECL {
void FreeTrie::remove(Node *node) {
LIBC_ASSERT(!empty() && "cannot remove from empty trie");
FreeList list = node;
list.pop();
Node *new_node = static_cast<Node *>(list.begin());
if (!new_node) {
// The freelist is empty. Replace the subtrie root with an arbitrary leaf.
// This is legal because there is no relationship between the size of the
// root and its children.
Node *leaf = node;
while (leaf->lower || leaf->upper)
leaf = leaf->lower ? leaf->lower : leaf->upper;
if (leaf == node) {
// If the root is a leaf, then removing it empties the subtrie.
replace_node(node, nullptr);
return;
}
replace_node(leaf, nullptr);
new_node = leaf;
}
if (!is_head(node))
return;
// Copy the trie links to the new head.
new_node->lower = node->lower;
new_node->upper = node->upper;
new_node->parent = node->parent;
replace_node(node, new_node);
}
void FreeTrie::replace_node(Node *node, Node *new_node) {
LIBC_ASSERT(is_head(node) && "only head nodes contain trie links");
if (node->parent) {
Node *&parent_child =
node->parent->lower == node ? node->parent->lower : node->parent->upper;
LIBC_ASSERT(parent_child == node &&
"no reference to child node found in parent");
parent_child = new_node;
} else {
LIBC_ASSERT(root == node && "non-root node had no parent");
root = new_node;
}
if (node->lower)
node->lower->parent = new_node;
if (node->upper)
node->upper->parent = new_node;
}
} // namespace LIBC_NAMESPACE_DECL
|
