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 11 namespace LIBC_NAMESPACE_DECL { 12 remove(Node * node)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 replace_node(Node * node,Node * new_node)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