sorted.h

// Copyright 2024 The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.
#pragma once
 
#include <cstddef>
 
#include "pw_allocator/bucket/base.h"
#include "pw_containers/intrusive_forward_list.h"
 
namespace pw::allocator {
 
 
class SortedItem : public IntrusiveForwardList<SortedItem>::Item {};
 
// Forward declarations.
 
template <typename BlockType>
class ForwardSortedBucket;
 
template <typename BlockType>
class ReverseSortedBucket;
 
namespace internal {
 
template <typename Derived, typename BlockType>
class SortedBucketBase : public BucketBase<Derived, BlockType, SortedItem> {
 public:
  ~SortedBucketBase() { Base::Clear(); }
 
 protected:
  using Base = BucketBase<Derived, BlockType, SortedItem>;
  friend Base;
 
  constexpr SortedBucketBase() = default;
 
  const IntrusiveForwardList<SortedItem>& items() const { return items_; }
 
  void DoAdd(BlockType& block) {
    auto* item_to_add = new (block.UsableSpace()) SortedItem();
    auto prev = Base::FindPrevIf(items_.before_begin(),
                                 items_.end(),
                                 Derived::MakeAddPredicate(block.InnerSize()));
    items_.insert_after(prev, *item_to_add);
  }
 
  BlockType* DoRemoveAny() {
    SortedItem& item = items_.front();
    items_.pop_front();
    return BlockType::FromUsableSpace(&item);
  }
 
  bool DoRemove(BlockType& block) {
    return items_.remove(Base::GetItemFrom(block));
  }
 
  BlockType* DoRemoveCompatible(Layout layout) {
    auto prev = Base::FindPrevIf(items_.before_begin(),
                                 items_.end(),
                                 Base::MakeCanAllocPredicate(layout));
    auto* block = Base::GetBlockFromPrev(prev, items_.end());
    if (block != nullptr) {
      items_.erase_after(prev);
    }
    return block;
  }
 
 private:
  IntrusiveForwardList<SortedItem> items_;
};
 
}  // namespace internal
 
template <typename BlockType>
class ForwardSortedBucket
    : public internal::SortedBucketBase<ForwardSortedBucket<BlockType>,
                                        BlockType> {
 private:
  using Base =
      internal::SortedBucketBase<ForwardSortedBucket<BlockType>, BlockType>;
 
  friend Base;
  friend typename Base::Base;
 
  static constexpr auto MakeAddPredicate(size_t inner_size) {
    return [inner_size](SortedItem& item) {
      auto* block = BlockType::FromUsableSpace(&item);
      return inner_size < block->InnerSize();
    };
  }
 
  const BlockType* DoFindLargest() const {
    const auto& items = Base::items();
    if (items.empty()) {
      return nullptr;
    }
    auto iter = items.before_begin();
    auto prev = iter;
    do {
      prev = iter++;
    } while (iter != items.end());
    return BlockType::FromUsableSpace(&(*prev));
  }
};
 
template <typename BlockType>
class ReverseSortedBucket
    : public internal::SortedBucketBase<ReverseSortedBucket<BlockType>,
                                        BlockType> {
 private:
  using Base =
      internal::SortedBucketBase<ReverseSortedBucket<BlockType>, BlockType>;
 
  friend Base;
  friend typename Base::Base;
 
  static constexpr auto MakeAddPredicate(size_t inner_size) {
    return [inner_size](SortedItem& item) {
      auto* block = BlockType::FromUsableSpace(&item);
      return block->InnerSize() < inner_size;
    };
  }
 
  const BlockType* DoFindLargest() const {
    const auto& items = Base::items();
    auto iter = items.begin();
    return BlockType::FromUsableSpace(&(*iter));
  }
};
 
 
}  // namespace pw::allocator