Gecko [ c.stage.kornherr.net ]

Name	Size	Permission	Date
backward	[ DIR ]	drwxr-xr-x	2026-04-26 19:49
bits	[ DIR ]	drwxr-xr-x	2026-04-26 19:49
debug	[ DIR ]	drwxr-xr-x	2026-04-26 19:49
decimal	[ DIR ]	drwxr-xr-x	2026-04-26 19:49
experimental	[ DIR ]	drwxr-xr-x	2026-04-26 19:49
ext	[ DIR ]	drwxr-xr-x	2026-04-26 19:49
parallel	[ DIR ]	drwxr-xr-x	2026-04-26 19:49
pstl	[ DIR ]	drwxr-xr-x	2026-04-26 19:49
tr1	[ DIR ]	drwxr-xr-x	2026-04-26 19:49
tr2	[ DIR ]	drwxr-xr-x	2026-04-26 19:49
algorithm	2.97 KB	-rw-r--r--	2025-12-18 20:59
any	18.38 KB	-rw-r--r--	2025-12-18 20:59
array	15.21 KB	-rw-r--r--	2025-12-18 20:59
atomic	50.36 KB	-rw-r--r--	2025-12-18 20:59
barrier	7.89 KB	-rw-r--r--	2025-12-18 20:59
bit	14.04 KB	-rw-r--r--	2025-12-18 20:59
bitset	49.14 KB	-rw-r--r--	2025-12-18 20:59
cassert	1.61 KB	-rw-r--r--	2025-12-18 20:59
ccomplex	1.3 KB	-rw-r--r--	2025-12-18 20:59
cctype	2.35 KB	-rw-r--r--	2025-12-18 20:59
cerrno	1.73 KB	-rw-r--r--	2025-12-18 20:59
cfenv	2 KB	-rw-r--r--	2025-12-18 20:59
cfloat	1.84 KB	-rw-r--r--	2025-12-18 20:59
charconv	29.52 KB	-rw-r--r--	2025-12-18 20:59
chrono	94.76 KB	-rw-r--r--	2025-12-18 20:59
cinttypes	2.11 KB	-rw-r--r--	2025-12-18 20:59
ciso646	1.43 KB	-rw-r--r--	2025-12-18 20:59
climits	1.87 KB	-rw-r--r--	2025-12-18 20:59
clocale	1.86 KB	-rw-r--r--	2025-12-18 20:59
cmath	91.77 KB	-rw-r--r--	2025-12-18 20:59
codecvt	5.15 KB	-rw-r--r--	2025-12-18 20:59
compare	36.91 KB	-rw-r--r--	2025-12-18 20:59
complex	74.66 KB	-rw-r--r--	2025-12-18 20:59
complex.h	1.56 KB	-rw-r--r--	2025-12-18 20:59
concepts	12.51 KB	-rw-r--r--	2025-12-18 20:59
condition_variable	12.59 KB	-rw-r--r--	2025-12-18 20:59
coroutine	9.44 KB	-rw-r--r--	2025-12-18 20:59
csetjmp	1.9 KB	-rw-r--r--	2025-12-18 20:59
csignal	1.81 KB	-rw-r--r--	2025-12-18 20:59
cstdalign	1.37 KB	-rw-r--r--	2025-12-18 20:59
cstdarg	1.82 KB	-rw-r--r--	2025-12-18 20:59
cstdbool	1.37 KB	-rw-r--r--	2025-12-18 20:59
cstddef	6.5 KB	-rw-r--r--	2025-12-18 20:59
cstdint	3.76 KB	-rw-r--r--	2025-12-18 20:59
cstdio	4.33 KB	-rw-r--r--	2025-12-18 20:59
cstdlib	6.38 KB	-rw-r--r--	2025-12-18 20:59
cstring	3.08 KB	-rw-r--r--	2025-12-18 20:59
ctgmath	1.33 KB	-rw-r--r--	2025-12-18 20:59
ctime	2.24 KB	-rw-r--r--	2025-12-18 20:59
cuchar	2.84 KB	-rw-r--r--	2025-12-18 20:59
cwchar	6.39 KB	-rw-r--r--	2025-12-18 20:59
cwctype	2.73 KB	-rw-r--r--	2025-12-18 20:59
cxxabi.h	21.76 KB	-rw-r--r--	2025-12-18 20:59
deque	4.39 KB	-rw-r--r--	2025-12-18 20:59
exception	5.28 KB	-rw-r--r--	2025-12-18 20:59
execution	1.83 KB	-rw-r--r--	2025-12-18 20:59
expected	49.72 KB	-rw-r--r--	2025-12-18 20:59
fenv.h	1.97 KB	-rw-r--r--	2025-12-18 20:59
filesystem	1.66 KB	-rw-r--r--	2025-12-18 20:59
format	113.64 KB	-rw-r--r--	2025-12-18 20:59
forward_list	2.65 KB	-rw-r--r--	2025-12-18 20:59
fstream	39.77 KB	-rw-r--r--	2025-12-18 20:59
functional	45.45 KB	-rw-r--r--	2025-12-18 20:59
future	51.89 KB	-rw-r--r--	2025-12-18 20:59
initializer_list	2.93 KB	-rw-r--r--	2025-12-18 20:59
iomanip	16.22 KB	-rw-r--r--	2025-12-18 20:59
ios	1.61 KB	-rw-r--r--	2025-12-18 20:59
iosfwd	8.21 KB	-rw-r--r--	2025-12-18 20:59
iostream	3 KB	-rw-r--r--	2025-12-18 20:59
istream	35.47 KB	-rw-r--r--	2025-12-18 20:59
iterator	2.76 KB	-rw-r--r--	2025-12-18 20:59
latch	2.72 KB	-rw-r--r--	2025-12-18 20:59
limits	76.4 KB	-rw-r--r--	2025-12-18 20:59
list	3.6 KB	-rw-r--r--	2025-12-18 20:59
locale	1.5 KB	-rw-r--r--	2025-12-18 20:59
map	4.05 KB	-rw-r--r--	2025-12-18 20:59
math.h	4.47 KB	-rw-r--r--	2025-12-18 20:59
memory	4.82 KB	-rw-r--r--	2025-12-18 20:59
memory_resource	14.14 KB	-rw-r--r--	2025-12-18 20:59
mutex	26.63 KB	-rw-r--r--	2025-12-18 20:59
new	8.45 KB	-rw-r--r--	2025-12-18 20:59
numbers	6.87 KB	-rw-r--r--	2025-12-18 20:59
numeric	25.38 KB	-rw-r--r--	2025-12-18 20:59
optional	44.1 KB	-rw-r--r--	2025-12-18 20:59
ostream	26.56 KB	-rw-r--r--	2025-12-18 20:59
queue	2.46 KB	-rw-r--r--	2025-12-18 20:59
random	1.71 KB	-rw-r--r--	2025-12-18 20:59
ranges	253.81 KB	-rw-r--r--	2025-12-18 20:59
ratio	20.97 KB	-rw-r--r--	2025-12-18 20:59
regex	3.08 KB	-rw-r--r--	2025-12-18 20:59
scoped_allocator	17.33 KB	-rw-r--r--	2025-12-18 20:59
semaphore	2.98 KB	-rw-r--r--	2025-12-18 20:59
set	3.91 KB	-rw-r--r--	2025-12-18 20:59
shared_mutex	24.52 KB	-rw-r--r--	2025-12-18 20:59
source_location	2.68 KB	-rw-r--r--	2025-12-18 20:59
span	13.82 KB	-rw-r--r--	2025-12-18 20:59
spanstream	12.17 KB	-rw-r--r--	2025-12-18 20:59
sstream	38.83 KB	-rw-r--r--	2025-12-18 20:59
stack	2.38 KB	-rw-r--r--	2025-12-18 20:59
stacktrace	21.37 KB	-rw-r--r--	2025-12-18 20:59
stdatomic.h	3.97 KB	-rw-r--r--	2025-12-18 20:59
stdexcept	9.65 KB	-rw-r--r--	2025-12-18 20:59
stdfloat	1.72 KB	-rw-r--r--	2025-12-18 20:59
stdlib.h	2.25 KB	-rw-r--r--	2025-12-18 20:59
stop_token	15.7 KB	-rw-r--r--	2025-12-18 20:59
streambuf	29.24 KB	-rw-r--r--	2025-12-18 20:59
string	3.87 KB	-rw-r--r--	2025-12-18 20:59
string_view	27.33 KB	-rw-r--r--	2025-12-18 20:59
syncstream	8.17 KB	-rw-r--r--	2025-12-18 20:59
system_error	17.96 KB	-rw-r--r--	2025-12-18 20:59
tgmath.h	1.33 KB	-rw-r--r--	2025-12-18 20:59
thread	7.33 KB	-rw-r--r--	2025-12-18 20:59
tuple	76.49 KB	-rw-r--r--	2025-12-18 20:59
type_traits	112.36 KB	-rw-r--r--	2025-12-18 20:59
typeindex	3.43 KB	-rw-r--r--	2025-12-18 20:59
typeinfo	8.11 KB	-rw-r--r--	2025-12-18 20:59
unordered_map	3.37 KB	-rw-r--r--	2025-12-18 20:59
unordered_set	3.23 KB	-rw-r--r--	2025-12-18 20:59
utility	6.98 KB	-rw-r--r--	2025-12-18 20:59
valarray	40.2 KB	-rw-r--r--	2025-12-18 20:59
variant	64.72 KB	-rw-r--r--	2025-12-18 20:59
vector	4.72 KB	-rw-r--r--	2025-12-18 20:59
version	12.32 KB	-rw-r--r--	2025-12-18 20:59

Rename

// <barrier> -*- C++ -*-

// Copyright (C) 2020-2023 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

// This implementation is based on libcxx/include/barrier
//===-- barrier.h --------------------------------------------------===//
//
// 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
//
//===---------------------------------------------------------------===//

/** @file include/barrier
 *  This is a Standard C++ Library header.
 */

#ifndef _GLIBCXX_BARRIER
#define _GLIBCXX_BARRIER 1

#pragma GCC system_header

#include <bits/requires_hosted.h> // threading primitive

#if __cplusplus > 201703L
#include <bits/atomic_base.h>
#if __cpp_lib_atomic_wait && __cpp_aligned_new
#include <bits/std_thread.h>
#include <bits/unique_ptr.h>

#include <array>

#define __cpp_lib_barrier 201907L

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

struct __empty_completion
  {
    _GLIBCXX_ALWAYS_INLINE void
    operator()() noexcept
    { }
  };

The default implementation of __tree_barrier is a classic tree barrier.

It looks different from literature pseudocode for two main reasons:
 1. Threads that call into std::barrier functions do not provide indices,
    so a numbering step is added before the actual barrier algorithm,
    appearing as an N+1 round to the N rounds of the tree barrier.
 2. A great deal of attention has been paid to avoid cache line thrashing
    by flattening the tree structure into cache-line sized arrays, that
    are indexed in an efficient way.

enum class __barrier_phase_t : unsigned char { };

template<typename _CompletionF>
    class __tree_barrier
    {
      using __atomic_phase_ref_t = std::__atomic_ref<__barrier_phase_t>;
      using __atomic_phase_const_ref_t = std::__atomic_ref<const __barrier_phase_t>;
      static constexpr auto __phase_alignment =
		      __atomic_phase_ref_t::required_alignment;

using __tickets_t = std::array<__barrier_phase_t, 64>;
      struct alignas(64) /* naturally-align the heap state */ __state_t
      {
	alignas(__phase_alignment) __tickets_t __tickets;
      };

ptrdiff_t _M_expected;
      unique_ptr<__state_t[]> _M_state;
      __atomic_base<ptrdiff_t> _M_expected_adjustment;
      _CompletionF _M_completion;

alignas(__phase_alignment) __barrier_phase_t  _M_phase;

bool
      _M_arrive(__barrier_phase_t __old_phase, size_t __current)
      {
	const auto __old_phase_val = static_cast<unsigned char>(__old_phase);
	const auto __half_step =
			   static_cast<__barrier_phase_t>(__old_phase_val + 1);
	const auto __full_step =
			   static_cast<__barrier_phase_t>(__old_phase_val + 2);

size_t __current_expected = _M_expected;
	__current %= ((_M_expected + 1) >> 1);

for (int __round = 0; ; ++__round)
	  {
	    if (__current_expected <= 1)
		return true;
	    size_t const __end_node = ((__current_expected + 1) >> 1),
			 __last_node = __end_node - 1;
	    for ( ; ; ++__current)
	      {
		if (__current == __end_node)
		  __current = 0;
		auto __expect = __old_phase;
		__atomic_phase_ref_t __phase(_M_state[__current]
						.__tickets[__round]);
		if (__current == __last_node && (__current_expected & 1))
		  {
		    if (__phase.compare_exchange_strong(__expect, __full_step,
						        memory_order_acq_rel))
		      break;     // I'm 1 in 1, go to next __round
		  }
		else if (__phase.compare_exchange_strong(__expect, __half_step,
						         memory_order_acq_rel))
		  {
		    return false; // I'm 1 in 2, done with arrival
		  }
		else if (__expect == __half_step)
		  {
		    if (__phase.compare_exchange_strong(__expect, __full_step,
						        memory_order_acq_rel))
		      break;    // I'm 2 in 2, go to next __round
		  }
	      }
	    __current_expected = __last_node + 1;
	    __current >>= 1;
	  }
      }

public:
      using arrival_token = __barrier_phase_t;

static constexpr ptrdiff_t
      max() noexcept
      { return __PTRDIFF_MAX__; }

__tree_barrier(ptrdiff_t __expected, _CompletionF __completion)
	  : _M_expected(__expected), _M_expected_adjustment(0),
	    _M_completion(move(__completion)),
	    _M_phase(static_cast<__barrier_phase_t>(0))
      {
	size_t const __count = (_M_expected + 1) >> 1;

_M_state = std::make_unique<__state_t[]>(__count);
      }

[[nodiscard]] arrival_token
      arrive(ptrdiff_t __update)
      {
	std::hash<std::thread::id> __hasher;
	size_t __current = __hasher(std::this_thread::get_id());
	__atomic_phase_ref_t __phase(_M_phase);
	const auto __old_phase = __phase.load(memory_order_relaxed);
	const auto __cur = static_cast<unsigned char>(__old_phase);
	for(; __update; --__update)
	  {
	    if(_M_arrive(__old_phase, __current))
	      {
		_M_completion();
		_M_expected += _M_expected_adjustment.load(memory_order_relaxed);
		_M_expected_adjustment.store(0, memory_order_relaxed);
		auto __new_phase = static_cast<__barrier_phase_t>(__cur + 2);
		__phase.store(__new_phase, memory_order_release);
		__phase.notify_all();
	      }
	  }
	return __old_phase;
      }

void
      wait(arrival_token&& __old_phase) const
      {
	__atomic_phase_const_ref_t __phase(_M_phase);
	auto const __test_fn = [=]
	  {
	    return __phase.load(memory_order_acquire) != __old_phase;
	  };
	std::__atomic_wait_address(&_M_phase, __test_fn);
      }

void
      arrive_and_drop()
      {
	_M_expected_adjustment.fetch_sub(1, memory_order_relaxed);
	(void)arrive(1);
      }
    };

template<typename _CompletionF = __empty_completion>
    class barrier
    {
      // Note, we may introduce a "central" barrier algorithm at some point
      // for more space constrained targets
      using __algorithm_t = __tree_barrier<_CompletionF>;
      __algorithm_t _M_b;

public:
      class arrival_token final
      {
      public:
	arrival_token(arrival_token&&) = default;
	arrival_token& operator=(arrival_token&&) = default;
	~arrival_token() = default;

private:
	friend class barrier;
	using __token = typename __algorithm_t::arrival_token;
	explicit arrival_token(__token __tok) noexcept : _M_tok(__tok) { }
	__token _M_tok;
      };

static constexpr ptrdiff_t
      max() noexcept
      { return __algorithm_t::max(); }

explicit
      barrier(ptrdiff_t __count, _CompletionF __completion = _CompletionF())
      : _M_b(__count, std::move(__completion))
      { }

barrier(barrier const&) = delete;
      barrier& operator=(barrier const&) = delete;

[[nodiscard]] arrival_token
      arrive(ptrdiff_t __update = 1)
      { return arrival_token{_M_b.arrive(__update)}; }

void
      wait(arrival_token&& __phase) const
      { _M_b.wait(std::move(__phase._M_tok)); }

void
      arrive_and_wait()
      { wait(arrive()); }

void
      arrive_and_drop()
      { _M_b.arrive_and_drop(); }
    };

_GLIBCXX_END_NAMESPACE_VERSION
} // namespace
#endif // __cpp_lib_atomic_wait && __cpp_aligned_new
#endif // __cplusplus > 201703L
#endif // _GLIBCXX_BARRIER