libc/src/__support/freetrie.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "freetrie.h"
  10
  11 namespace LIBC_NAMESPACE_DECL {
  12
  13 void 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
  45 void 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