unordered.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 UnorderedItem : public IntrusiveForwardList<UnorderedItem>::Item {};
 
template <typename BlockType>
class UnorderedBucket : public internal::BucketBase<UnorderedBucket<BlockType>,
                                                    BlockType,
                                                    UnorderedItem> {
 private:
  using Base = internal::
      BucketBase<UnorderedBucket<BlockType>, BlockType, UnorderedItem>;
  friend Base;
 
 public:
  ~UnorderedBucket() { Base::Clear(); }
 
 private:
  void DoAdd(BlockType& block) {
    auto* item = new (block.UsableSpace()) UnorderedItem();
    items_.push_front(*item);
  }
 
  BlockType* DoRemoveAny() {
    UnorderedItem& item = items_.front();
    items_.pop_front();
    return BlockType::FromUsableSpace(&item);
  }
 
  const BlockType* DoFindLargest() const {
    auto iter = std::max_element(items_.begin(), items_.end(), Base::Compare);
    return BlockType::FromUsableSpace(&(*iter));
  }
 
  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;
  }
 
  IntrusiveForwardList<UnorderedItem> items_;
};
 
 
}  // namespace pw::allocator