sequenced.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 <algorithm>
#include <cstddef>
#include <iterator>
 
#include "pw_allocator/bucket/base.h"
#include "pw_containers/intrusive_list.h"
 
namespace pw::allocator {
 
 
class SequencedItem
    : public containers::future::IntrusiveList<SequencedItem>::Item {};
 
template <typename BlockType>
class SequencedBucket : public internal::BucketBase<SequencedBucket<BlockType>,
                                                    BlockType,
                                                    SequencedItem> {
 private:
  using Base = internal::
      BucketBase<SequencedBucket<BlockType>, BlockType, SequencedItem>;
  friend Base;
 
 public:
  ~SequencedBucket() { Base::Clear(); }
 
  constexpr size_t threshold() const { return threshold_; }
 
  void set_threshold(size_t threshold) { threshold_ = threshold; }
 
 private:
  void DoAdd(BlockType& block) {
    auto* item_to_add = new (block.UsableSpace()) SequencedItem();
    containers::future::IntrusiveList<SequencedItem>::iterator iter;
    if (block.InnerSize() < threshold_) {
      // Search from back.
      auto r_iter = std::find_if(
          items_.rbegin(), items_.rend(), [item_to_add](SequencedItem& item) {
            return &item < item_to_add;
          });
 
      // If r_iter dereferences to the last address that is before than the
      // item to add, then the corresponding forward iterator points to the
      // first address that is after the item to add.
      iter = r_iter.base();
 
    } else {
      // Search from front.
      iter = std::find_if(
          items_.begin(), items_.end(), [item_to_add](SequencedItem& item) {
            return item_to_add < &item;
          });
    }
    items_.insert(iter, *item_to_add);
  }
 
  const BlockType* DoFindLargest() const {
    auto iter = std::max_element(items_.begin(), items_.end(), Base::Compare);
    return BlockType::FromUsableSpace(&(*iter));
  }
 
  BlockType* DoRemoveAny() {
    SequencedItem& item = items_.front();
    items_.pop_front();
    return BlockType::FromUsableSpace(&item);
  }
 
  bool DoRemove(BlockType& block) {
    SequencedItem& item_to_remove = Base::GetItemFrom(block);
    if (block.InnerSize() >= threshold_) {
      // Search from front and remove.
      return items_.remove(item_to_remove);
    }
    // Search from back and remove.
    auto iter = std::find_if(
        items_.rbegin(), items_.rend(), [&item_to_remove](SequencedItem& item) {
          return &item_to_remove == &item;
        });
    if (iter == items_.rend()) {
      return false;
    }
    items_.erase(*iter);
    return true;
  }
 
  BlockType* DoRemoveCompatible(Layout layout) {
    auto predicate = Base::MakeCanAllocPredicate(layout);
    SequencedItem* item = nullptr;
    if (layout.size() < threshold_) {
      // Search from back.
      auto iter = std::find_if(items_.rbegin(), items_.rend(), predicate);
      item = iter != items_.rend() ? &(*iter) : nullptr;
    } else {
      // Search from front.
      auto iter = std::find_if(items_.begin(), items_.end(), predicate);
      item = iter != items_.end() ? &(*iter) : nullptr;
    }
    if (item == nullptr) {
      return nullptr;
    }
    auto* block = BlockType::FromUsableSpace(item);
    items_.erase(*item);
    return block;
  }
 
  containers::future::IntrusiveList<SequencedItem> items_;
  size_t threshold_ = 0;
};
 
 
}  // namespace pw::allocator