65 lines · cpp
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-exception6//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 the21 // 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_DECL65