libc/src/__support/freelist.cpp

   1 //===-- Implementation for freelist ---------------------------------------===//
   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 "freelist.h"
  10
  11 namespace LIBC_NAMESPACE_DECL {
  12
  13 void FreeList::push(Node *node) {
  14   if (begin_) {
  15     LIBC_ASSERT(Block<>::from_usable_space(node)->outer_size() ==
  16                     begin_->block()->outer_size() &&
  17                 "freelist entries must have the same size");
  18     // Since the list is circular, insert the node immediately before begin_.
  19     node->prev = begin_->prev;
  20     node->next = begin_;
  21     begin_->prev->next = node;
  22     begin_->prev = node;
  23   } else {
  24     begin_ = node->prev = node->next = node;
  25   }
  26 }
  27
  28 void FreeList::remove(Node *node) {
  29   LIBC_ASSERT(begin_ && "cannot remove from empty list");
  30   if (node == node->next) {
  31     LIBC_ASSERT(node == begin_ &&
  32                 "a self-referential node must be the only element");
  33     begin_ = nullptr;
  34   } else {
  35     node->prev->next = node->next;
  36     node->next->prev = node->prev;
  37     if (begin_ == node)
  38       begin_ = node->next;
  39   }
  40 }
  41
  42 } // namespace LIBC_NAMESPACE_DECL