libc/src/__support/freestore.h

   1 //===-- Interface for freestore ------------------------------------------===//
   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 #ifndef LLVM_LIBC_SRC___SUPPORT_FREESTORE_H
  10 #define LLVM_LIBC_SRC___SUPPORT_FREESTORE_H
  11
  12 #include "freetrie.h"
  13
  14 namespace LIBC_NAMESPACE_DECL {
  15
  16 /// A best-fit store of variously-sized free blocks. Blocks can be inserted and
  17 /// removed in logarithmic time.
  18 class FreeStore {
  19 public:
  20   FreeStore() = default;
  21   FreeStore(const FreeStore &other) = delete;
  22   FreeStore &operator=(const FreeStore &other) = delete;
  23
  24   /// Sets the range of possible block sizes. This can only be called when the
  25   /// trie is empty.
  26   LIBC_INLINE void set_range(FreeTrie::SizeRange range) {
  27     large_trie.set_range(range);
  28   }
  29
  30   /// Insert a free block. If the block is too small to be tracked, nothing
  31   /// happens.
  32   void insert(Block<> *block);
  33
  34   /// Remove a free block. If the block is too small to be tracked, nothing
  35   /// happens.
  36   void remove(Block<> *block);
  37
  38   /// Remove a best-fit free block that can contain the given size when
  39   /// allocated. Returns nullptr if there is no such block.
  40   Block<> *remove_best_fit(size_t size);
  41
  42 private:
  43   static constexpr size_t ALIGNMENT = alignof(max_align_t);
  44   static constexpr size_t MIN_OUTER_SIZE =
  45       align_up(Block<>::BLOCK_OVERHEAD + sizeof(FreeList::Node), ALIGNMENT);
  46   static constexpr size_t MIN_LARGE_OUTER_SIZE =
  47       align_up(Block<>::BLOCK_OVERHEAD + sizeof(FreeTrie::Node), ALIGNMENT);
  48   static constexpr size_t NUM_SMALL_SIZES =
  49       (MIN_LARGE_OUTER_SIZE - MIN_OUTER_SIZE) / ALIGNMENT;
  50
  51   LIBC_INLINE static bool too_small(Block<> *block) {
  52     return block->outer_size() < MIN_OUTER_SIZE;
  53   }
  54   LIBC_INLINE static bool is_small(Block<> *block) {
  55     return block->outer_size() < MIN_LARGE_OUTER_SIZE;
  56   }
  57
  58   FreeList &small_list(Block<> *block);
  59   FreeList *find_best_small_fit(size_t size);
  60
  61   cpp::array<FreeList, NUM_SMALL_SIZES> small_lists;
  62   FreeTrie large_trie;
  63 };
  64
  65 LIBC_INLINE void FreeStore::insert(Block<> *block) {
  66   if (too_small(block))
  67     return;
  68   if (is_small(block))
  69     small_list(block).push(block);
  70   else
  71     large_trie.push(block);
  72 }
  73
  74 LIBC_INLINE void FreeStore::remove(Block<> *block) {
  75   if (too_small(block))
  76     return;
  77   if (is_small(block)) {
  78     small_list(block).remove(
  79         reinterpret_cast<FreeList::Node *>(block->usable_space()));
  80   } else {
  81     large_trie.remove(
  82         reinterpret_cast<FreeTrie::Node *>(block->usable_space()));
  83   }
  84 }
  85
  86 LIBC_INLINE Block<> *FreeStore::remove_best_fit(size_t size) {
  87   if (FreeList *list = find_best_small_fit(size)) {
  88     Block<> *block = list->front();
  89     list->pop();
  90     return block;
  91   }
  92   if (FreeTrie::Node *best_fit = large_trie.find_best_fit(size)) {
  93     Block<> *block = best_fit->block();
  94     large_trie.remove(best_fit);
  95     return block;
  96   }
  97   return nullptr;
  98 }
  99
 100 LIBC_INLINE FreeList &FreeStore::small_list(Block<> *block) {
 101   LIBC_ASSERT(is_small(block) && "only legal for small blocks");
 102   return small_lists[(block->outer_size() - MIN_OUTER_SIZE) / ALIGNMENT];
 103 }
 104
 105 LIBC_INLINE FreeList *FreeStore::find_best_small_fit(size_t size) {
 106   for (FreeList &list : small_lists)
 107     if (!list.empty() && list.size() >= size)
 108       return &list;
 109   return nullptr;
 110 }
 111
 112 } // namespace LIBC_NAMESPACE_DECL
 113
 114 #endif // LLVM_LIBC_SRC___SUPPORT_FREESTORE_H