text: ﻿/**
   * @brief 静态无锁队列(数组)
   * @note 固定最大长度
   * @note 使用了 c++11的atomic
   *       不支持的编译器就自求多福吧
   *
   * @version 1.0
   * @author OWenT
   * @date 2015-01-09
   *
   */
  #pragma once
  
  #include <array>
  #include <atomic>
  
  #include "config/compiler_features.h"
  #include "std/explicit_declare.h"
  
  #include <config/atframe_utils_build_feature.h>
  
  namespace util {
      namespace ds {
  
          template <typename T, size_t SIZE, typename TContainer = std::array<T, SIZE + 1> >
          class LIBATFRAME_UTILS_API_HEAD_ONLY lock_free_array {
          public:
              typedef T           value_type;
              typedef value_type *pointer_type;
              typedef value_type &reference_type;
              typedef TContainer  container_type;
  
          private:
              lock_free_array(const lock_free_array &) UTIL_CONFIG_DELETED_FUNCTION;
              lock_free_array &operator=(const lock_free_array &) UTIL_CONFIG_DELETED_FUNCTION;
  
          public:
              typedef pointer_type   iterator;
              typedef const iterator const_iterator;
  
          public:
              lock_free_array() {
                  start_.store(0);
                  end_.store(0);
              }
  
              iterator begin() { return &data_[start_.load()]; }
  
              iterator begin() const { return &data_[start_.load()]; }
  
              iterator end() { return &data_[end_.load()]; }
  
              iterator end() const { return &data_[end_.load()]; }
  
              /**
               * @brief 获取原始数据
               */
              iterator at(size_t index) { return &data_[index]; }
  
              /**
               * @brief 获取原始数据
               */
              iterator at(size_t index) const { return &data_[index]; }
  
              iterator push_back() {
                  while (true) {
                      size_t end_pos   = end_.load();
                      size_t start_pos = start_.load();
  
                      if ((end_pos + 1) % data_.size() == start_pos) {
                          return nullptr;
                      }
  
                      size_t new_end_pos = (end_pos + 1) % data_.size();
                      if (end_.compare_exchange_weak(end_pos, new_end_pos)) {
                          return at(end_pos);
                      }
                  }
  
                  return nullptr;
              }
  
              iterator pop_back() {
                  while (true) {
                      size_t end_pos   = end_.load();
                      size_t start_pos = start_.load();
  
                      if (end_pos == start_pos) {
                          return nullptr;
                      }
  
                      size_t new_end_pos = (end_pos + data_.size() - 1) % data_.size();
                      if (end_.compare_exchange_weak(end_pos, new_end_pos)) {
                          return at(new_end_pos);
                      }
                  }
  
                  return nullptr;
              }
  
              iterator push_front() {
                  while (true) {
                      size_t end_pos   = end_.load();
                      size_t start_pos = start_.load();
  
                      if ((end_pos + 1) % data_.size() == start_pos) {
                          return nullptr;
                      }
  
                      size_t new_start_pos = (start_pos + data_.size() - 1) % data_.size();
                      if (start_.compare_exchange_weak(start_pos, new_start_pos)) {
                          return at(new_start_pos);
                      }
                  }
  
                  return nullptr;
              }
  
              iterator pop_front() {
                  while (true) {
                      size_t end_pos   = end_.load();
                      size_t start_pos = start_.load();
  
                      if (end_pos == start_pos) {
                          return nullptr;
                      }
  
                      size_t new_start_pos = (start_pos + 1) % data_.size();
                      if (start_.compare_exchange_weak(start_pos, new_start_pos)) {
                          return at(start_pos);
                      }
                  }
  
                  return nullptr;
              }
  
              bool empty() const { return start_ != end_; }
  
              size_t size() const { return (data_.size() + end_ - start_) % data_.size(); }
  
  
              size_t capacity() const { return data_.capacity(); }
  
          private:
              std::atomic<size_t> start_;
              std::atomic<size_t> end_;
              container_type      data_;
          };
      } // namespace ds
  } // namespace util
  