Subversion Repository Public Repository

Divide-Framework

This repository has no backups
This repository's network speed is throttled to 100KB/sec

Diff Revisions 1011 vs 1012 for /trunk/Source Code/Libs/ConcurrentQueue/concurrentqueue.h

Diff revisions: vs.
  @@ -5,7 +5,7 @@
5 5 // http://moodycamel.com/blog/2014/detailed-design-of-a-lock-free-queue
6 6
7 7 // Simplified BSD license:
8 - // Copyright (c) 2013-2015, Cameron Desrochers.
8 + // Copyright (c) 2013-2016, Cameron Desrochers.
9 9 // All rights reserved.
10 10 //
11 11 // Redistribution and use in source and binary forms, with or without modification,
  @@ -59,6 +59,7 @@
59 59 #include <atomic> // Requires C++11. Sorry VS2010.
60 60 #include <cassert>
61 61 #endif
62 + #include <cstddef> // for max_align_t
62 63 #include <cstdint>
63 64 #include <cstdlib>
64 65 #include <type_traits>
  @@ -95,7 +96,7 @@
95 96 static const thread_id_t invalid_thread_id2 = 0xFFFFFFFFU; // Not technically guaranteed to be invalid, but is never used in practice. Note that all Win32 thread IDs are presently multiples of 4.
96 97 static inline thread_id_t thread_id() { return static_cast<thread_id_t>(::GetCurrentThreadId()); }
97 98 } }
98 - #elif defined(__APPLE__) && TARGET_OS_IPHONE
99 + #elif defined(__arm__) || defined(_M_ARM) || defined(__aarch64__) || (defined(__APPLE__) && TARGET_OS_IPHONE)
99 100 namespace moodycamel { namespace details {
100 101 static_assert(sizeof(std::thread::id) == 4 || sizeof(std::thread::id) == 8, "std::thread::id is expected to be either 4 or 8 bytes");
101 102
  @@ -153,6 +154,9 @@
153 154 #ifndef MOODYCAMEL_EXCEPTIONS_ENABLED
154 155 #if (defined(_MSC_VER) && defined(_CPPUNWIND)) || (defined(__GNUC__) && defined(__EXCEPTIONS)) || (!defined(_MSC_VER) && !defined(__GNUC__))
155 156 #define MOODYCAMEL_EXCEPTIONS_ENABLED
157 + #endif
158 + #endif
159 + #ifdef MOODYCAMEL_EXCEPTIONS_ENABLED
156 160 #define MOODYCAMEL_TRY try
157 161 #define MOODYCAMEL_CATCH(...) catch(__VA_ARGS__)
158 162 #define MOODYCAMEL_RETHROW throw
  @@ -163,7 +167,6 @@
163 167 #define MOODYCAMEL_RETHROW
164 168 #define MOODYCAMEL_THROW(expr)
165 169 #endif
166 - #endif
167 170
168 171 #ifndef MOODYCAMEL_NOEXCEPT
169 172 #if !defined(MOODYCAMEL_EXCEPTIONS_ENABLED)
  @@ -191,13 +194,13 @@
191 194 #ifdef MCDBGQ_USE_RELACY
192 195 #define MOODYCAMEL_CPP11_THREAD_LOCAL_SUPPORTED
193 196 #else
194 - //// VS2013 doesn't support `thread_local`, and MinGW-w64 w/ POSIX threading has a crippling bug: http://sourceforge.net/p/mingw-w64/bugs/445
195 - //// g++ <=4.7 doesn't support thread_local either.
196 - //// Finally, iOS/ARM doesn't have support for it either.
197 - //#if (!defined(_MSC_VER) || _MSC_VER >= 1900) && (!defined(__MINGW32__) && !defined(__MINGW64__) || !defined(__WINPTHREADS_VERSION)) && (!defined(__GNUC__) || __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8)) && (!defined(__APPLE__) || !TARGET_OS_IPHONE)
198 - //// Assume `thread_local` is fully supported in all other C++11 compilers/runtimes
199 - //#define MOODYCAMEL_CPP11_THREAD_LOCAL_SUPPORTED
200 - //#endif
197 + // VS2013 doesn't support `thread_local`, and MinGW-w64 w/ POSIX threading has a crippling bug: http://sourceforge.net/p/mingw-w64/bugs/445
198 + // g++ <=4.7 doesn't support thread_local either.
199 + // Finally, iOS/ARM doesn't have support for it either, and g++/ARM allows it to compile but it's unconfirmed to actually work
200 + #if (!defined(_MSC_VER) || _MSC_VER >= 1900) && (!defined(__MINGW32__) && !defined(__MINGW64__) || !defined(__WINPTHREADS_VERSION)) && (!defined(__GNUC__) || __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 8)) && (!defined(__APPLE__) || !TARGET_OS_IPHONE) && !defined(__arm__) && !defined(_M_ARM) && !defined(__aarch64__)
201 + // Assume `thread_local` is fully supported in all other C++11 compilers/platforms
202 + //#define MOODYCAMEL_CPP11_THREAD_LOCAL_SUPPORTED // always disabled for now since several users report having problems with it on
203 + #endif
201 204 #endif
202 205 #endif
203 206
  @@ -235,12 +238,20 @@
235 238 ? (static_cast<T>(1) << (sizeof(T) * CHAR_BIT - 1)) - static_cast<T>(1)
236 239 : static_cast<T>(-1);
237 240 };
238 -
239 - #ifdef __GNUC__
240 - typedef ::max_align_t max_align_t; // GCC forgot to add it to std:: for a while
241 +
242 + #if defined(__GLIBCXX__)
243 + typedef ::max_align_t std_max_align_t; // libstdc++ forgot to add it to std:: for a while
241 244 #else
242 - typedef std::max_align_t max_align_t; // Others (e.g. MSVC) insist it can *only* be accessed via std::
245 + typedef std::max_align_t std_max_align_t; // Others (e.g. MSVC) insist it can *only* be accessed via std::
243 246 #endif
247 +
248 + // Some platforms have incorrectly set max_align_t to a type with <8 bytes alignment even while supporting
249 + // 8-byte aligned scalar values (*cough* 32-bit iOS). Work around this with our own union. See issue #64.
250 + typedef union {
251 + std_max_align_t x;
252 + long long y;
253 + void* z;
254 + } max_align_t;
244 255 }
245 256
246 257 // Default traits for the ConcurrentQueue. To change some of the
  @@ -748,7 +759,7 @@
748 759 {
749 760 implicitProducerHashResizeInProgress.clear(std::memory_order_relaxed);
750 761 populate_initial_implicit_producer_hash();
751 - size_t blocks = ((((minCapacity + BLOCK_SIZE - 1) / BLOCK_SIZE) - 1) * (maxExplicitProducers + 1) + 2 * (maxExplicitProducers + maxImplicitProducers)) * BLOCK_SIZE;
762 + size_t blocks = (((minCapacity + BLOCK_SIZE - 1) / BLOCK_SIZE) - 1) * (maxExplicitProducers + 1) + 2 * (maxExplicitProducers + maxImplicitProducers);
752 763 populate_initial_block_list(blocks);
753 764
754 765 #ifdef MOODYCAMEL_QUEUE_INTERNAL_DEBUG
  @@ -942,7 +953,7 @@
942 953 bool enqueue_bulk(It itemFirst, size_t count)
943 954 {
944 955 if (INITIAL_IMPLICIT_PRODUCER_HASH_SIZE == 0) return false;
945 - return inner_enqueue_bulk<CanAlloc>(std::forward<It>(itemFirst), count);
956 + return inner_enqueue_bulk<CanAlloc>(itemFirst, count);
946 957 }
947 958
948 959 // Enqueues several items using an explicit producer token.
  @@ -954,7 +965,7 @@
954 965 template<typename It>
955 966 bool enqueue_bulk(producer_token_t const& token, It itemFirst, size_t count)
956 967 {
957 - return inner_enqueue_bulk<CanAlloc>(token, std::forward<It>(itemFirst), count);
968 + return inner_enqueue_bulk<CanAlloc>(token, itemFirst, count);
958 969 }
959 970
960 971 // Enqueues a single item (by copying it).
  @@ -1006,7 +1017,7 @@
1006 1017 bool try_enqueue_bulk(It itemFirst, size_t count)
1007 1018 {
1008 1019 if (INITIAL_IMPLICIT_PRODUCER_HASH_SIZE == 0) return false;
1009 - return inner_enqueue_bulk<CannotAlloc>(std::forward<It>(itemFirst), count);
1020 + return inner_enqueue_bulk<CannotAlloc>(itemFirst, count);
1010 1021 }
1011 1022
1012 1023 // Enqueues several items using an explicit producer token.
  @@ -1017,7 +1028,7 @@
1017 1028 template<typename It>
1018 1029 bool try_enqueue_bulk(producer_token_t const& token, It itemFirst, size_t count)
1019 1030 {
1020 - return inner_enqueue_bulk<CannotAlloc>(token, std::forward<It>(itemFirst), count);
1031 + return inner_enqueue_bulk<CannotAlloc>(token, itemFirst, count);
1021 1032 }
1022 1033
1023 1034
  @@ -1281,14 +1292,14 @@
1281 1292 template<AllocationMode canAlloc, typename It>
1282 1293 inline bool inner_enqueue_bulk(producer_token_t const& token, It itemFirst, size_t count)
1283 1294 {
1284 - return static_cast<ExplicitProducer*>(token.producer)->ConcurrentQueue::ExplicitProducer::template enqueue_bulk<canAlloc>(std::forward<It>(itemFirst), count);
1295 + return static_cast<ExplicitProducer*>(token.producer)->ConcurrentQueue::ExplicitProducer::template enqueue_bulk<canAlloc>(itemFirst, count);
1285 1296 }
1286 1297
1287 1298 template<AllocationMode canAlloc, typename It>
1288 1299 inline bool inner_enqueue_bulk(It itemFirst, size_t count)
1289 1300 {
1290 1301 auto producer = get_or_add_implicit_producer();
1291 - return producer == nullptr ? false : producer->ConcurrentQueue::ImplicitProducer::template enqueue_bulk<canAlloc>(std::forward<It>(itemFirst), count);
1302 + return producer == nullptr ? false : producer->ConcurrentQueue::ImplicitProducer::template enqueue_bulk<canAlloc>(itemFirst, count);
1292 1303 }
1293 1304
1294 1305 inline bool update_current_producer_after_rotation(consumer_token_t& token)
  @@ -1565,8 +1576,8 @@
1565 1576 }
1566 1577 }
1567 1578
1568 - inline T* operator[](index_t idx) MOODYCAMEL_NOEXCEPT { return reinterpret_cast<T*>(elements) + static_cast<size_t>(idx & static_cast<index_t>(BLOCK_SIZE - 1)); }
1569 - inline T const* operator[](index_t idx) const MOODYCAMEL_NOEXCEPT { return reinterpret_cast<T const*>(elements) + static_cast<size_t>(idx & static_cast<index_t>(BLOCK_SIZE - 1)); }
1579 + inline T* operator[](index_t idx) MOODYCAMEL_NOEXCEPT { return static_cast<T*>(static_cast<void*>(elements)) + static_cast<size_t>(idx & static_cast<index_t>(BLOCK_SIZE - 1)); }
1580 + inline T const* operator[](index_t idx) const MOODYCAMEL_NOEXCEPT { return static_cast<T const*>(static_cast<void const*>(elements)) + static_cast<size_t>(idx & static_cast<index_t>(BLOCK_SIZE - 1)); }
1570 1581
1571 1582 private:
1572 1583 // IMPORTANT: This must be the first member in Block, so that if T depends on the alignment of
  @@ -1597,7 +1608,7 @@
1597 1608 void* owner;
1598 1609 #endif
1599 1610 };
1600 - static_assert(std::alignment_of<Block>::value >= std::alignment_of<details::max_align_t>::value, "Internal error: Blocks must be at least as aligned as the type they are wrapping");
1611 + static_assert(std::alignment_of<Block>::value >= std::alignment_of<details::max_align_t>::value, "Internal error: Blocks must be at least as aligned as the type they are wrapping");
1601 1612
1602 1613
1603 1614 #if MCDBGQ_TRACKMEM
  @@ -1612,14 +1623,14 @@
1612 1623
1613 1624 struct ProducerBase : public details::ConcurrentQueueProducerTypelessBase
1614 1625 {
1615 - ProducerBase(ConcurrentQueue* parent, bool isExplicit) :
1626 + ProducerBase(ConcurrentQueue* parent_, bool isExplicit_) :
1616 1627 tailIndex(0),
1617 1628 headIndex(0),
1618 1629 dequeueOptimisticCount(0),
1619 1630 dequeueOvercommit(0),
1620 1631 tailBlock(nullptr),
1621 - isExplicit(isExplicit),
1622 - parent(parent)
1632 + isExplicit(isExplicit_),
1633 + parent(parent_)
1623 1634 {
1624 1635 }
1625 1636
  @@ -2120,7 +2131,7 @@
2120 2131 }
2121 2132 currentTailIndex = startTailIndex;
2122 2133 while (true) {
2123 - auto stopIndex = (currentTailIndex & ~static_cast<index_t>(BLOCK_SIZE - 1)) + static_cast<index_t>(BLOCK_SIZE);
2134 + stopIndex = (currentTailIndex & ~static_cast<index_t>(BLOCK_SIZE - 1)) + static_cast<index_t>(BLOCK_SIZE);
2124 2135 if (details::circular_less_than<index_t>(constructedStopIndex, stopIndex)) {
2125 2136 stopIndex = constructedStopIndex;
2126 2137 }
  @@ -2557,7 +2568,7 @@
2557 2568 currentTailIndex += static_cast<index_t>(BLOCK_SIZE);
2558 2569
2559 2570 // Find out where we'll be inserting this block in the block index
2560 - BlockIndexEntry* idxEntry;
2571 + BlockIndexEntry* idxEntry = nullptr; // initialization here unnecessary but compiler can't always tell
2561 2572 Block* newBlock;
2562 2573 bool indexInserted = false;
2563 2574 auto head = this->headIndex.load(std::memory_order_relaxed);
  @@ -2641,7 +2652,7 @@
2641 2652 }
2642 2653 currentTailIndex = startTailIndex;
2643 2654 while (true) {
2644 - auto stopIndex = (currentTailIndex & ~static_cast<index_t>(BLOCK_SIZE - 1)) + static_cast<index_t>(BLOCK_SIZE);
2655 + stopIndex = (currentTailIndex & ~static_cast<index_t>(BLOCK_SIZE - 1)) + static_cast<index_t>(BLOCK_SIZE);
2645 2656 if (details::circular_less_than<index_t>(constructedStopIndex, stopIndex)) {
2646 2657 stopIndex = constructedStopIndex;
2647 2658 }
  @@ -2804,6 +2815,9 @@
2804 2815 inline bool insert_block_index_entry(BlockIndexEntry*& idxEntry, index_t blockStartIndex)
2805 2816 {
2806 2817 auto localBlockIndex = blockIndex.load(std::memory_order_relaxed); // We're the only writer thread, relaxed is OK
2818 + if (localBlockIndex == nullptr) {
2819 + return false; // this can happen if new_block_index failed in the constructor
2820 + }
2807 2821 auto newTail = (localBlockIndex->tail.load(std::memory_order_relaxed) + 1) & (localBlockIndex->capacity - 1);
2808 2822 idxEntry = localBlockIndex->index[newTail];
2809 2823 if (idxEntry->key.load(std::memory_order_relaxed) == INVALID_BLOCK_BASE ||
  @@ -3318,10 +3332,10 @@
3318 3332 auto empty = details::invalid_thread_id;
3319 3333 #ifdef MOODYCAMEL_CPP11_THREAD_LOCAL_SUPPORTED
3320 3334 auto reusable = details::invalid_thread_id2;
3321 - if ((probedKey == empty && mainHash->entries[index].key.compare_exchange_strong(empty, id, std::memory_order_relaxed)) ||
3322 - (probedKey == reusable && mainHash->entries[index].key.compare_exchange_strong(reusable, id, std::memory_order_acquire))) {
3335 + if ((probedKey == empty && mainHash->entries[index].key.compare_exchange_strong(empty, id, std::memory_order_relaxed, std::memory_order_relaxed)) ||
3336 + (probedKey == reusable && mainHash->entries[index].key.compare_exchange_strong(reusable, id, std::memory_order_acquire, std::memory_order_acquire))) {
3323 3337 #else
3324 - if ((probedKey == empty && mainHash->entries[index].key.compare_exchange_strong(empty, id, std::memory_order_relaxed))) {
3338 + if ((probedKey == empty && mainHash->entries[index].key.compare_exchange_strong(empty, id, std::memory_order_relaxed, std::memory_order_relaxed))) {
3325 3339 #endif
3326 3340 mainHash->entries[index].value = value;
3327 3341 break;
  @@ -3406,10 +3420,10 @@
3406 3420 auto empty = details::invalid_thread_id;
3407 3421 #ifdef MOODYCAMEL_CPP11_THREAD_LOCAL_SUPPORTED
3408 3422 auto reusable = details::invalid_thread_id2;
3409 - if ((probedKey == empty && mainHash->entries[index].key.compare_exchange_strong(empty, id, std::memory_order_relaxed)) ||
3410 - (probedKey == reusable && mainHash->entries[index].key.compare_exchange_strong(reusable, id, std::memory_order_acquire))) {
3423 + if ((probedKey == empty && mainHash->entries[index].key.compare_exchange_strong(empty, id, std::memory_order_relaxed, std::memory_order_relaxed)) ||
3424 + (probedKey == reusable && mainHash->entries[index].key.compare_exchange_strong(reusable, id, std::memory_order_acquire, std::memory_order_acquire))) {
3411 3425 #else
3412 - if ((probedKey == empty && mainHash->entries[index].key.compare_exchange_strong(empty, id, std::memory_order_relaxed))) {
3426 + if ((probedKey == empty && mainHash->entries[index].key.compare_exchange_strong(empty, id, std::memory_order_relaxed, std::memory_order_relaxed))) {
3413 3427 #endif
3414 3428 mainHash->entries[index].value = producer;
3415 3429 break;