llvm/libc/src/__support/freelist.h

//===-- Interface for freelist_malloc -------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_LIBC_SRC___SUPPORT_FREELIST_H
#define LLVM_LIBC_SRC___SUPPORT_FREELIST_H

#include "src/__support/CPP/array.h"
#include "src/__support/CPP/cstddef.h"
#include "src/__support/CPP/new.h"
#include "src/__support/CPP/span.h"
#include "src/__support/fixedvector.h"
#include "src/__support/macros/config.h"

namespace LIBC_NAMESPACE_DECL {

span;

/// Basic [freelist](https://en.wikipedia.org/wiki/Free_list) implementation
/// for an allocator. This implementation buckets by chunk size, with a list
/// of user-provided buckets. Each bucket is a linked list of storage chunks.
/// Because this freelist uses the added chunks themselves as list nodes, there
/// is a lower bound of `sizeof(FreeList.FreeListNode)` bytes for chunks which
/// can be added to this freelist. There is also an implicit bucket for
/// "everything else", for chunks which do not fit into a bucket.
///
/// Each added chunk will be added to the smallest bucket under which it fits.
/// If it does not fit into any user-provided bucket, it will be added to the
/// default bucket.
///
/// As an example, assume that the `FreeList` is configured with buckets of
/// sizes {64, 128, 256, and 512} bytes. The internal state may look like the
/// following:
///
/// @code{.unparsed}
/// bucket[0] (64B) --> chunk[12B] --> chunk[42B] --> chunk[64B] --> NULL
/// bucket[1] (128B) --> chunk[65B] --> chunk[72B] --> NULL
/// bucket[2] (256B) --> NULL
/// bucket[3] (512B) --> chunk[312B] --> chunk[512B] --> chunk[416B] --> NULL
/// bucket[4] (implicit) --> chunk[1024B] --> chunk[513B] --> NULL
/// @endcode
///
/// Note that added chunks should be aligned to a 4-byte boundary.
template <size_t NUM_BUCKETS = 6> class FreeList { … };

template <size_t NUM_BUCKETS>
constexpr void FreeList<NUM_BUCKETS>::set_freelist_node(FreeListNode &node,
                                                        span<cpp::byte> chunk) { … }

template <size_t NUM_BUCKETS>
bool FreeList<NUM_BUCKETS>::add_chunk(span<cpp::byte> chunk) { … }

template <size_t NUM_BUCKETS>
template <typename Cond>
span<cpp::byte> FreeList<NUM_BUCKETS>::find_chunk_if(Cond op) const { … }

template <size_t NUM_BUCKETS>
span<cpp::byte> FreeList<NUM_BUCKETS>::find_chunk(size_t size) const { … }

template <size_t NUM_BUCKETS>
bool FreeList<NUM_BUCKETS>::remove_chunk(span<cpp::byte> chunk) { … }

template <size_t NUM_BUCKETS>
constexpr size_t
FreeList<NUM_BUCKETS>::find_chunk_ptr_for_size(size_t size,
                                               bool non_null) const { … }

} // namespace LIBC_NAMESPACE_DECL

#endif // LLVM_LIBC_SRC___SUPPORT_FREELIST_H