/*
- * Copyright 2015 Facebook, Inc.
+ * Copyright 2015-present Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
#pragma once
#include <atomic>
-#include <boost/noncopyable.hpp>
-#include <iostream>
#include <cmath>
+#include <cstring>
#include <memory>
-#include <string.h>
#include <type_traits>
-#include <unistd.h>
-#include <folly/detail/TurnSequencer.h>
+#include <boost/noncopyable.hpp>
+
#include <folly/Portability.h>
+#include <folly/detail/TurnSequencer.h>
+#include <folly/portability/TypeTraits.h>
+#include <folly/portability/Unistd.h>
namespace folly {
namespace detail {
-template<typename T,
- template<typename> class Atom>
+template <typename T, template <typename> class Atom>
class RingBufferSlot;
} // namespace detail
/// "future" can optionally block but reads from the "past" will always fail.
///
-template<typename T, template<typename> class Atom = std::atomic>
+template <typename T, template <typename> class Atom = std::atomic>
class LockFreeRingBuffer: boost::noncopyable {
+ static_assert(
+ std::is_nothrow_default_constructible<T>::value,
+ "Element type must be nothrow default constructible");
- static_assert(std::is_nothrow_default_constructible<T>::value,
- "Element type must be nothrow default constructible");
-
- static_assert(FOLLY_IS_TRIVIALLY_COPYABLE(T),
- "Element type must be trivially copyable");
+ static_assert(
+ FOLLY_IS_TRIVIALLY_COPYABLE(T),
+ "Element type must be trivially copyable");
-public:
+ public:
/// Opaque pointer to a past or future write.
/// Can be moved relative to its current location but not in absolute terms.
struct Cursor {
explicit Cursor(uint64_t initialTicket) noexcept : ticket(initialTicket) {}
- void moveForward(uint64_t steps = 1) noexcept {
+ /// Returns true if this cursor now points to a different
+ /// write, false otherwise.
+ bool moveForward(uint64_t steps = 1) noexcept {
+ uint64_t prevTicket = ticket;
ticket += steps;
+ return prevTicket != ticket;
}
- void moveBackward(uint64_t steps = 1) noexcept {
+ /// Returns true if this cursor now points to a previous
+ /// write, false otherwise.
+ bool moveBackward(uint64_t steps = 1) noexcept {
+ uint64_t prevTicket = ticket;
if (steps > ticket) {
ticket = 0;
} else {
ticket -= steps;
}
+ return prevTicket != ticket;
}
- protected: // for test visibility reasons
+ protected: // for test visibility reasons
uint64_t ticket;
friend class LockFreeRingBuffer;
};
- explicit LockFreeRingBuffer(size_t capacity) noexcept
+ explicit LockFreeRingBuffer(uint32_t capacity) noexcept
: capacity_(capacity)
, slots_(new detail::RingBufferSlot<T,Atom>[capacity])
, ticket_(0)
slots_[idx(ticket)].write(turn(ticket), value);
}
+ /// Perform a single write of an object of type T.
+ /// Writes can block iff a previous writer has not yet completed a write
+ /// for the same slot (before the most recent wrap-around).
+ /// Returns a Cursor pointing to the just-written T.
+ Cursor writeAndGetCursor(T& value) noexcept {
+ uint64_t ticket = ticket_.fetch_add(1);
+ slots_[idx(ticket)].write(turn(ticket), value);
+ return Cursor(ticket);
+ }
+
/// Read the value at the cursor.
/// Returns true if the read succeeded, false otherwise. If the return
/// value is false, dest is to be considered partially read and in an
~LockFreeRingBuffer() {
}
-private:
- const size_t capacity_;
+ private:
+ const uint32_t capacity_;
const std::unique_ptr<detail::RingBufferSlot<T,Atom>[]> slots_;
}
uint32_t turn(uint64_t ticket) noexcept {
- return (ticket / capacity_);
+ return (uint32_t)(ticket / capacity_);
}
}; // LockFreeRingBuffer
namespace detail {
-template<typename T, template<typename> class Atom>
+template <typename T, template <typename> class Atom>
class RingBufferSlot {
-public:
+ public:
explicit RingBufferSlot() noexcept
: sequencer_()
, data()
bool waitAndTryRead(T& dest, uint32_t turn) noexcept {
uint32_t desired_turn = (turn + 1) * 2;
Atom<uint32_t> cutoff(0);
- if(!sequencer_.tryWaitForTurn(desired_turn, cutoff, false)) {
+ if (sequencer_.tryWaitForTurn(desired_turn, cutoff, false) !=
+ TurnSequencer<Atom>::TryWaitResult::SUCCESS) {
return false;
}
memcpy(&dest, &data, sizeof(T));
return sequencer_.isTurn((turn + 1) * 2);
}
-
-private:
+ private:
TurnSequencer<Atom> sequencer_;
T data;
}; // RingBufferSlot