Branch data     Line data    Source code

       1                 :             : // Copyright 2026 HPActor Contributors
       2                 :             : //
       3                 :             : // Licensed under the Apache License, Version 2.0 (the "License");
       4                 :             : // you may not use this file except in compliance with the License.
       5                 :             : // You may obtain a copy of the License at
       6                 :             : //
       7                 :             : //     http://www.apache.org/licenses/LICENSE-2.0
       8                 :             : //
       9                 :             : // Unless required by applicable law or agreed to in writing, software
      10                 :             : // distributed under the License is distributed on an "AS IS" BASIS,
      11                 :             : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12                 :             : // See the License for the specific language governing permissions and
      13                 :             : // limitations under the License.
      14                 :             : 
      15                 :             : #pragma once
      16                 :             : 
      17                 :             : #include <atomic>
      18                 :             : #include <cstddef>
      19                 :             : 
      20                 :             : namespace hpactor::mem {
      21                 :             : 
      22                 :             : // Lock-free LIFO freelist. Each node must have a `T* next` field.
      23                 :             : // Thread-safe for any number of concurrent push/pop operations.
      24                 :             : template <typename T> class FreeList {
      25                 :             :   public:
      26                 :         231 :     FreeList() : top_(nullptr) {}
      27                 :             : 
      28                 :     1165134 :     void push(T* node) noexcept {
      29                 :     1165134 :         node->next = top_.load(std::memory_order_acquire);
      30                 :     1184283 :         while (!top_.compare_exchange_weak(node->next, node,
      31                 :             :                                            std::memory_order_acq_rel,
      32                 :             :                                            std::memory_order_acquire)) {
      33                 :             :         }
      34                 :     1165134 :     }
      35                 :             : 
      36                 :     1268840 :     T* pop() noexcept {
      37                 :     1268840 :         T* node = top_.load(std::memory_order_acquire);
      38                 :     1283904 :         while (node != nullptr) {
      39                 :      125181 :             T* next = node->next;
      40                 :      125181 :             if (top_.compare_exchange_weak(node, next,
      41                 :             :                                            std::memory_order_acq_rel,
      42                 :             :                                            std::memory_order_acquire)) {
      43                 :      110117 :                 return node;
      44                 :             :             }
      45                 :             :         }
      46                 :     1158723 :         return nullptr;
      47                 :             :     }
      48                 :             : 
      49                 :           4 :     bool empty() const noexcept {
      50                 :           4 :         return top_.load(std::memory_order_acquire) == nullptr;
      51                 :             :     }
      52                 :             : 
      53                 :             :   private:
      54                 :             :     std::atomic<T*> top_;
      55                 :             : };
      56                 :             : 
      57                 :             : } // namespace hpactor::mem