1//
2// immer: immutable data structures for C++
3// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
4//
5// This software is distributed under the Boost Software License, Version 1.0.
6// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
7//
8
9#pragma once
10
11#include <immer/refcount/no_refcount_policy.hpp>
12
13#include <atomic>
14#include <utility>
15#include <cassert>
16#include <thread>
17
18// This has been shamelessly copied from boost...
19#if defined(_MSC_VER) && _MSC_VER >= 1310 && (defined(_M_IX86) || defined(_M_X64)) && !defined(__c2__)
20extern "C" void _mm_pause();
21# define IMMER_SMT_PAUSE _mm_pause()
22#elif defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))
23# define IMMER_SMT_PAUSE __asm__ __volatile__( "rep; nop" : : : "memory" )
24#endif
25
26namespace immer {
27
28// This is an atomic spinlock similar to the one used by boost to provide
29// "atomic" shared_ptr operations. It also does not differ much from the one
30// from libc++ or libstdc++...
31struct spinlock
32{
33 std::atomic_flag v_{};
34
35 bool try_lock()
36 {
37 return !v_.test_and_set(std::memory_order_acquire);
38 }
39
40 void lock()
41 {
42 for (auto k = 0u; !try_lock(); ++k) {
43 if (k < 4)
44 continue;
45#ifdef IMMER_SMT_PAUSE
46 else if (k < 16)
47 IMMER_SMT_PAUSE;
48#endif
49 else
50 std::this_thread::yield();
51 }
52 }
53
54 void unlock()
55 {
56 v_.clear(std::memory_order_release);
57 }
58
59 struct scoped_lock
60 {
61 scoped_lock(const scoped_lock&) = delete;
62 scoped_lock& operator=(const scoped_lock& ) = delete;
63
64 explicit scoped_lock(spinlock& sp)
65 : sp_{sp}
66 { sp.lock(); }
67
68 ~scoped_lock()
69 { sp_.unlock();}
70
71 private:
72 spinlock& sp_;
73 };
74};
75
76/*!
77 * A reference counting policy implemented using an *atomic* `int`
78 * count. It is **thread-safe**.
79 */
80struct refcount_policy
81{
82 using spinlock_type = spinlock;
83
84 mutable std::atomic<int> refcount;
85
86 refcount_policy() : refcount{1} {};
87 refcount_policy(disowned) : refcount{0} {}
88
89 void inc()
90 {
91 refcount.fetch_add(1, std::memory_order_relaxed);
92 }
93
94 bool dec()
95 {
96 return 1 == refcount.fetch_sub(1, std::memory_order_acq_rel);
97 }
98
99 void dec_unsafe()
100 {
101 assert(refcount.load() > 1);
102 refcount.fetch_sub(1, std::memory_order_relaxed);
103 }
104
105 bool unique()
106 {
107 return refcount == 1;
108 }
109};
110
111} // namespace immer
112