115 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIBC_SRC___SUPPORT_FREESTORE_H10#define LLVM_LIBC_SRC___SUPPORT_FREESTORE_H11 12#include "freetrie.h"13 14namespace LIBC_NAMESPACE_DECL {15 16/// A best-fit store of variously-sized free blocks. Blocks can be inserted and17/// removed in logarithmic time.18class FreeStore {19public: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 the25 /// 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, nothing31 /// happens.32 void insert(Block *block);33 34 /// Remove a free block. If the block is too small to be tracked, nothing35 /// happens.36 void remove(Block *block);37 38 /// Remove a best-fit free block that can contain the given size when39 /// allocated. Returns nullptr if there is no such block.40 Block *remove_best_fit(size_t size);41 42private:43 static constexpr size_t MIN_OUTER_SIZE =44 align_up(sizeof(Block) + sizeof(FreeList::Node), alignof(max_align_t));45 static constexpr size_t MIN_LARGE_OUTER_SIZE =46 align_up(sizeof(Block) + sizeof(FreeTrie::Node), alignof(max_align_t));47 static constexpr size_t NUM_SMALL_SIZES =48 (MIN_LARGE_OUTER_SIZE - MIN_OUTER_SIZE) / alignof(max_align_t);49 50 LIBC_INLINE static bool too_small(Block *block) {51 return block->outer_size() < MIN_OUTER_SIZE;52 }53 LIBC_INLINE static bool is_small(Block *block) {54 return block->outer_size() < MIN_LARGE_OUTER_SIZE;55 }56 57 FreeList &small_list(Block *block);58 FreeList *find_best_small_fit(size_t size);59 60 cpp::array<FreeList, NUM_SMALL_SIZES> small_lists;61 FreeTrie large_trie;62};63 64LIBC_INLINE void FreeStore::insert(Block *block) {65 if (too_small(block))66 return;67 if (is_small(block))68 small_list(block).push(block);69 else70 large_trie.push(block);71}72 73LIBC_INLINE void FreeStore::remove(Block *block) {74 if (too_small(block))75 return;76 if (is_small(block)) {77 small_list(block).remove(78 reinterpret_cast<FreeList::Node *>(block->usable_space()));79 } else {80 large_trie.remove(81 reinterpret_cast<FreeTrie::Node *>(block->usable_space()));82 }83}84 85LIBC_INLINE Block *FreeStore::remove_best_fit(size_t size) {86 if (FreeList *list = find_best_small_fit(size)) {87 Block *block = list->front();88 list->pop();89 return block;90 }91 if (FreeTrie::Node *best_fit = large_trie.find_best_fit(size)) {92 Block *block = best_fit->block();93 large_trie.remove(best_fit);94 return block;95 }96 return nullptr;97}98 99LIBC_INLINE FreeList &FreeStore::small_list(Block *block) {100 LIBC_ASSERT(is_small(block) && "only legal for small blocks");101 return small_lists[(block->outer_size() - MIN_OUTER_SIZE) /102 alignof(max_align_t)];103}104 105LIBC_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_DECL113 114#endif // LLVM_LIBC_SRC___SUPPORT_FREESTORE_H115