Squashed 'third_party/immer/' content from commit ad3e3556d

git-subtree-dir: third_party/immer
git-subtree-split: ad3e3556d38bb75966dd24c61a774970a7c7957e

4 files changed, 223 insertions, 0 deletions

diff --git a/immer/refcount/enable_intrusive_ptr.hpp b/immer/refcount/enable_intrusive_ptr.hpp
new file mode 100644
index 000000000000..1185a219fd9b
--- /dev/null
+++ b/immer/refcount/enable_intrusive_ptr.hpp
@@ -0,0 +1,37 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#pragma once
+
+#include <immer/refcount/no_refcount_policy.hpp>
+
+namespace immer {
+
+template <typename Deriv, typename RefcountPolicy>
+class enable_intrusive_ptr
+{
+    mutable RefcountPolicy refcount_data_;
+
+public:
+    enable_intrusive_ptr()
+        : refcount_data_{disowned{}}
+    {}
+
+    friend void intrusive_ptr_add_ref(const Deriv* x)
+    {
+        x->refcount_data_.inc();
+    }
+
+    friend void intrusive_ptr_release(const Deriv* x)
+    {
+        if (x->refcount_data_.dec())
+            delete x;
+    }
+};
+
+} // namespace immer
diff --git a/immer/refcount/no_refcount_policy.hpp b/immer/refcount/no_refcount_policy.hpp
new file mode 100644
index 000000000000..24f9d489f54d
--- /dev/null
+++ b/immer/refcount/no_refcount_policy.hpp
@@ -0,0 +1,45 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#pragma once
+
+namespace immer {
+
+struct disowned
+{};
+
+struct no_spinlock
+{
+    bool try_lock() { return true; }
+    void lock() {}
+    void unlock() {}
+
+    struct scoped_lock
+    {
+        scoped_lock(no_spinlock&) {}
+    };
+};
+
+/*!
+ * Disables reference counting, to be used with an alternative garbage
+ * collection strategy like a `gc_heap`.
+ */
+struct no_refcount_policy
+{
+    using spinlock_type = no_spinlock;
+
+    no_refcount_policy(){};
+    no_refcount_policy(disowned) {}
+
+    void inc() {}
+    bool dec() { return false; }
+    void dec_unsafe() {}
+    bool unique() { return false; }
+};
+
+} // namespace immer
diff --git a/immer/refcount/refcount_policy.hpp b/immer/refcount/refcount_policy.hpp
new file mode 100644
index 000000000000..a7a282cd13a7
--- /dev/null
+++ b/immer/refcount/refcount_policy.hpp
@@ -0,0 +1,101 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#pragma once
+
+#include <immer/refcount/no_refcount_policy.hpp>
+
+#include <atomic>
+#include <cassert>
+#include <thread>
+#include <utility>
+
+// This has been shamelessly copied from boost...
+#if defined(_MSC_VER) && _MSC_VER >= 1310 &&                                   \
+    (defined(_M_IX86) || defined(_M_X64)) && !defined(__c2__)
+extern "C" void _mm_pause();
+#define IMMER_SMT_PAUSE _mm_pause()
+#elif defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))
+#define IMMER_SMT_PAUSE __asm__ __volatile__("rep; nop" : : : "memory")
+#endif
+
+namespace immer {
+
+// This is an atomic spinlock similar to the one used by boost to provide
+// "atomic" shared_ptr operations.  It also does not differ much from the one
+// from libc++ or libstdc++...
+struct spinlock
+{
+    std::atomic_flag v_{};
+
+    bool try_lock() { return !v_.test_and_set(std::memory_order_acquire); }
+
+    void lock()
+    {
+        for (auto k = 0u; !try_lock(); ++k) {
+            if (k < 4)
+                continue;
+#ifdef IMMER_SMT_PAUSE
+            else if (k < 16)
+                IMMER_SMT_PAUSE;
+#endif
+            else
+                std::this_thread::yield();
+        }
+    }
+
+    void unlock() { v_.clear(std::memory_order_release); }
+
+    struct scoped_lock
+    {
+        scoped_lock(const scoped_lock&) = delete;
+        scoped_lock& operator=(const scoped_lock&) = delete;
+
+        explicit scoped_lock(spinlock& sp)
+            : sp_{sp}
+        {
+            sp.lock();
+        }
+
+        ~scoped_lock() { sp_.unlock(); }
+
+    private:
+        spinlock& sp_;
+    };
+};
+
+/*!
+ * A reference counting policy implemented using an *atomic* `int`
+ * count.  It is **thread-safe**.
+ */
+struct refcount_policy
+{
+    using spinlock_type = spinlock;
+
+    mutable std::atomic<int> refcount;
+
+    refcount_policy()
+        : refcount{1} {};
+    refcount_policy(disowned)
+        : refcount{0}
+    {}
+
+    void inc() { refcount.fetch_add(1, std::memory_order_relaxed); }
+
+    bool dec() { return 1 == refcount.fetch_sub(1, std::memory_order_acq_rel); }
+
+    void dec_unsafe()
+    {
+        assert(refcount.load() > 1);
+        refcount.fetch_sub(1, std::memory_order_relaxed);
+    }
+
+    bool unique() { return refcount == 1; }
+};
+
+} // namespace immer
diff --git a/immer/refcount/unsafe_refcount_policy.hpp b/immer/refcount/unsafe_refcount_policy.hpp
new file mode 100644
index 000000000000..bcf24578de27
--- /dev/null
+++ b/immer/refcount/unsafe_refcount_policy.hpp
@@ -0,0 +1,40 @@
+//
+// immer: immutable data structures for C++
+// Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente
+//
+// This software is distributed under the Boost Software License, Version 1.0.
+// See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt
+//
+
+#pragma once
+
+#include <immer/refcount/no_refcount_policy.hpp>
+
+#include <atomic>
+#include <utility>
+
+namespace immer {
+
+/*!
+ * A reference counting policy implemented using a raw `int` count.
+ * It is **not thread-safe**.
+ */
+struct unsafe_refcount_policy
+{
+    using spinlock_type = no_spinlock;
+
+    mutable int refcount;
+
+    unsafe_refcount_policy()
+        : refcount{1} {};
+    unsafe_refcount_policy(disowned)
+        : refcount{0}
+    {}
+
+    void inc() { ++refcount; }
+    bool dec() { return --refcount == 0; }
+    void dec_unsafe() { --refcount; }
+    bool unique() { return refcount == 1; }
+};
+
+} // namespace immer