ring_buffer.h

Go to the documentation of this file.

/*
The MIT License (MIT)

Copyright (c) 2015 University of Central Florida's Computer Software Engineering
Scalable & Secure Systems (CSE - S3) Lab

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/


#ifndef TERVEL_CONTAINERS_WF_RINGBUFFER_RINGBUFFER_H_
#define TERVEL_CONTAINERS_WF_RINGBUFFER_RINGBUFFER_H_

#include <atomic>
#include <assert.h>
#include <cstddef>
#include <memory>
#include <thread>
#include <string>

#include <tervel/util/info.h>
#include <tervel/util/util.h>
#include <tervel/util/progress_assurance.h>
#include <tervel/util/memory/hp/hazard_pointer.h>

namespace tervel {
namespace containers {
namespace wf {

template<typename T>
class RingBuffer {
  static const uintptr_t num_lsb = 3;
  static const uintptr_t delayMark_lsb = 0x1;
  static const uintptr_t emptytype_lsb = 0x2;
  static const uintptr_t oprec_lsb = 0x4;
  static const uintptr_t clear_lsb = 7;

  static_assert(sizeof(T) == sizeof(uintptr_t) &&
    sizeof(uintptr_t) == sizeof(uint64_t), " Pointers muse be 64 bits");

 public:
  class Value {
   public:
    Value() {};
    friend RingBuffer;
   private:
    int64_t func_seqid() {
      return seqid_;
    }

    void func_seqid(int64_t s) {
      seqid_ = s;
    }

    void atomic_change_seqid(int64_t e, int64_t n) {
      std::atomic<int64_t> *a;
      a = reinterpret_cast<std::atomic<int64_t> *>(&seqid_);
      bool res = a->compare_exchange_strong(e, n);
      assert( (res || e ==n) && " Seqid changed to an unexpected value in the"
        " progress assurance scheme");
    }
    int64_t seqid_{-1};
  };

  RingBuffer(size_t capacity);

  bool isFull();

  bool isFull(int64_t tail, int64_t head);


  bool isEmpty();

  bool isEmpty(int64_t tail, int64_t head);

  bool enqueue(T value);

  bool dequeue(T &value);

  std::string debug_string();

 private:

  bool readValue(int64_t pos, uintptr_t &val);

  static inline uintptr_t EmptyType(int64_t seqid);

  static inline int64_t getEmptyTypeSeqId(uintptr_t val);

  static inline uintptr_t ValueType(T value, int64_t seqid);

  static inline T getValueType(uintptr_t val);

  static inline int64_t getValueTypeSeqId(uintptr_t val);

  static inline uintptr_t DelayMarkValue(uintptr_t val);

  void getInfo(uintptr_t val, int64_t &val_seqid,
    bool &val_isValueType, bool &val_isMarked);

  static inline bool isEmptyType(uintptr_t p);

  static inline bool isValueType(uintptr_t p);

  static inline bool isDelayedMarked(uintptr_t p);

  int64_t nextHead();

  int64_t getHead();

  int64_t casHead(int64_t &expected, int64_t new_val);

  int64_t nextTail();

  int64_t getTail();

  int64_t casTail(int64_t &expected, int64_t new_val);

  static inline int64_t counterAction(std::atomic<int64_t> &counter, int64_t val);

  int64_t nextSeqId(int64_t seqid);

  int64_t getPos(int64_t seqid);

  bool backoff(int64_t pos, uintptr_t val);

  void atomic_delay_mark(int64_t pos);

  std::string debug_string(uintptr_t val);


  class BufferOp;
  class EnqueueOp;
  class DequeueOp;
  class Helper;

  const int64_t capacity_;
  std::atomic<int64_t> head_ {0};
  std::atomic<int64_t> tail_ {0};
  std::unique_ptr<std::atomic<uintptr_t>[]> array_;

};  // class RingBuffer<Value>



}  // namespace wf
}  // namespace containers
}  // namespace tervel

#include <tervel/containers/wf/ring-buffer/ring_buffer_op.h>
#include <tervel/containers/wf/ring-buffer/helper.h>
#include <tervel/containers/wf/ring-buffer/enqueue_op.h>
#include <tervel/containers/wf/ring-buffer/dequeue_op.h>

#include <tervel/containers/wf/ring-buffer/helper_imp.h>
#include <tervel/containers/wf/ring-buffer/enqueue_op_imp.h>
#include <tervel/containers/wf/ring-buffer/dequeue_op_imp.h>

#include <tervel/containers/wf/ring-buffer/ring_buffer_imp.h>


#endif  // TERVEL_CONTAINERS_WF_RINGBUFFER_RINGBUFFER_H_