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

source code of libc/src/__support/freetrie.cpp