文档章节

Algorithm: atomic stack(simple)

SHIHUAMarryMe
 SHIHUAMarryMe
发布于 2017/03/16 17:43
字数 792
阅读 25
收藏 1
/*
author: SHIHUA
time: 17/3/10

原理:
该stack的实现包括两个引用计数.
外部引用计数: 每次读取结点的时候+1;
内部引用计数: 每次读取结点结束的时候-1; 且当一个线程结束对该结点的读取的时候也-1;
*/

#ifndef _ATOMIC_STACK_H
#define  _ATOMIC_STACK_H
#define  _ENABLE_ATOMIC_ALIGNMENT_FIX


#include <atomic>
#include <memory>
#include <type_traits>


namespace TT {

	template<typename T>
	class Node;

	template<typename Ty>
	class ExternalCounter { //stack node
	public:
		int counter{ 0 }; //外部引用计数.
		Node<Ty>* ptr{nullptr};



		~ExternalCounter() = default; //这里并不对它含的指针进行内存管理.
		ExternalCounter() = default;
		ExternalCounter(Node<Ty>* next_ , const int& count = 0)
			:ptr{ next_ },
			counter{ count } {}

		/*ExternalCounter(const ExternalCounter<Ty>& other)
			:counter{ other.counter },
			ptr{ other.ptr } {}

		ExternalCounter(ExternalCounter<Ty>&& other)
			:counter{ std::move(other.counter) },
			ptr{ other.ptr }
		{
			other.ptr = nullptr;
		}

		ExternalCounter<Ty>& operator=(const ExternalCounter<Ty>& other)
		{
			this->counter = other.counter;
			this->ptr = other.ptr;

			return *this;
		}

		ExternalCounter<Ty>& operator=(ExternalCounter<Ty>&& other)
		{
			this->counter = std::move(other.counter);
			this->ptr = other.ptr;
			other.ptr = nullptr;

			return *this;
		}*/


		void setPtrNext(const ExternalCounter<Ty>& other) && noexcept = delete;
		void setPtrNext(const ExternalCounter<Ty>& other)& noexcept
		{
			(this->ptr)->next = other;
		}

		void setPtrNext(ExternalCounter<Ty>&& other) && noexcept = delete;
		inline void setPtrNext(ExternalCounter<Ty>&& other)& noexcept
		{
			(this->ptr)->next = std::move(other);
		}


		ExternalCounter<Ty>& getPtrNext() && noexcept = delete;
		inline ExternalCounter<Ty>& getPtrNext()& noexcept
		{
			return ((this->ptr)->next);
		}

		bool operator==(const ExternalCounter<Ty>& other)
		{
			if ((this->counter == other.counter) && (this->ptr == other.ptr)) {
				return true;
			}

			return false;
		}
	};


	template<typename Ty>
	class Node { //for internal counter
	public:
		ExternalCounter<Ty> next{}; //指向当前结点的下一个结点.并含有外部引用计数.
		std::shared_ptr<Ty> data{ nullptr }; //存放数据.
		std::atomic<int> internal_counter{ 0 }; //内部引用计数

		template<typename T, typename = 
			                                  typename std::enable_if<std::is_same<Ty, std::remove_reference<std::remove_cv<T>::type>::type>::value
			                                                                        || std::is_convertible<Ty, std::remove_reference<std::remove_cv<T>::type>::type>::value, void>::type>
		Node(T&& value, Node<Ty>* next_ = nullptr)
			:next{ next_ },
			data{ std::make_shared<Ty>(std::forward<T>(value)) },
			internal_counter{0}
		{
			//constructor!
		}

		~Node() = default;
		Node() = default;
		Node(const Node<Ty>& other) = delete;
		Node(Node<Ty>&& other) = delete;
		Node<Ty>& operator=(const Node<Ty>& other) = delete;
		Node<Ty>& operator=(Node<Ty>&& other) = delete;
	};


	template<typename Ty, typename =
		typename std::enable_if<!std::is_const<Ty>::value, void>::type>
		class Stack {
		private:
			std::atomic<ExternalCounter<Ty>> head;

			void increaseOldHeadCounter(ExternalCounter<Ty>& old_head)noexcept
			{
				ExternalCounter<Ty> new_head;

				do {
					new_head = old_head;
					++(new_head.counter);


					//保证new_head和old_head总是一致的.
				} while ((this->head).compare_exchange_strong(old_head, new_head)); //std::memory_order_seq_cst

				old_head.counter = new_head.counter;
			}

		public:

			Stack() = default;

			~Stack()
			{
				while (this->pop());
			}

			template<typename T>
			void push(T&& val)noexcept
			{
				ExternalCounter<Ty> new_node{ new Node<Ty>{ std::forward<T>(val) }, 1 }; //创建新结点的时候新结点的外部引用计数设置为1
				new_node.setPtrNext((this->head).load());  //std::memory_order_seq_cst

				while (!(head.compare_exchange_strong(new_node.getPtrNext(), new_node))); //std::memory_order_seq_cst
			}

			std::shared_ptr<Ty> pop()noexcept
			{
				ExternalCounter<Ty> old_head{ (this->head).load() }; //std::memory_order_seq_cst

				for (;;) 
				{
					this->increaseOldHeadCounter(old_head);
					Node<Ty>* const ptr{ old_head.ptr };

					if (!ptr) {
						return nullptr;
					}

					if ((this->head).compare_exchange_strong(old_head, ptr->next)) { //std::memory_order_seq_cst
						std::shared_ptr<Ty> data{ nullptr };
						data.swap(ptr->data);

						int counter = old_head.counter - 2; //这里之所以-2;
						                                                                   //每次结束对ptr内容的读取internal_counter - 1;
						                                                                  //且我们假设这是最后一个正在使用该结点的线程而且该线程即将结束因此internl_counter - 1;
						                                                                 //因此我们假设: external_counter-2  =  -internal_counter;

						if ((ptr->internal_counter).fetch_add(counter) == -counter) { //std::memory_order_seq_cst
							delete ptr;
						}

						return data;

						//当上面一步的比较交换操作失败的时候说明:
						//其他线程添加了新的结点或者其他线程删除了当前结点,也就是说当前线程结束了对该结点的读取.
						//因此我们需要对内部引用计数-1;
						//如果内部引用计数-1后的值为0说明只有一个线程正在使用该结点那么我们就可以安全的删除.
					} else if ((ptr->internal_counter).fetch_sub(1) == 1) { //std::memory_order_seq_cst
						delete ptr;
					}

				}
			}
	};

}

template<typename Ty>
bool operator==(const TT::ExternalCounter<Ty>& lh, const TT::ExternalCounter<Ty>& rh)noexcept
{
	return (lh.operator==(rh));
}

#endif //_ATOMIC_STACK_H

 

© 著作权归作者所有

SHIHUAMarryMe
粉丝 13
博文 162
码字总数 138435
作品 0
武汉
程序员
私信 提问
国外同学让帮忙的一个C++机器人程序

一朋友在英国读书,老师安排了一个C++的作业,想让我帮下忙,可是我已经不做C++好久了。所以很多都记不起来了。 感觉这个题目还挺有意思,不知道有没有人能帮忙试一下。下面我发一下需求: ...

一条大河波浪宽
2013/12/28
1K
10
Google PerfTools 1.9 发布

这个工具可让开发创建更强大的应用程序,特别是那些用C++模版开发的多线程应用程序,包括TCMalloc, heap-checker, heap-profiler 和cpu-profiler。 Google PerfTools 1.9发布.2011-12-22 上一...

fei
2011/12/23
2.3K
1
My Little Learner

Introduction This tip is a very simple implementation of k-Nearest Neighbor classifier in Machine Learning. Background I am currently watching YouTube playlist by Google Develop......

2017/12/18
0
0
Percona Server 5.6.15-63.0/5.5.35-33.0 发布

Percona Server全面更新。5.6.15-63.0/5.5.35-33.0/5.1.73-14.11 发布 .2013-12-20. 同步基于 MySQL 5.6.15/5.5.34/5.1.73.此版本增强了线程池在高并发下的性能,增强mysqlbinlog支持SSL和压...

fei
2013/12/20
490
0
kmap_atomic的细节以及改进

kmap_atomic用于高端内存映射,用于紧急的,短时间的映射,它没有使用任何锁,完全靠一个数学公式来避免混乱,它空间有限且虚拟地址固定,这意味着它映射的内存不能长期被占用而不被unmap,k...

晨曦之光
2012/04/10
177
0

没有更多内容

加载失败,请刷新页面

加载更多

HashSet和HashMap有什么区别?

HashSet 底层是采用 HashMap 实现,HashSet 的实现比较简单,HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现 调用 HashSet 的 add 方法时,实际上是向 HashSet 对象内部持有的 Ha...

ConstXiong
29分钟前
6
0
击穿JVM虚拟机

什么是JVM虚拟机 首先我们需要了解什么是虚拟机,为什么虚拟机可以实现夸平台,虚拟机在计算机中扮演一个什么样的角色。 (从下向上看) 看上图的操作系统与虚拟机层,可以看到,JVM是在操作...

兜兜毛毛
37分钟前
5
0
OpenNMS 利用 Sentinel处理Netflow(流量流向分析)

准备环境 CentOS-7-x86_64 Java8 OpenNMS 23.0.4 minion-23.0.4 sentinel-23.0.4 elasticsearch-6.7.1.tar.gz OpenNMS 配置 1 配置ActiveMQ vi $OPENNMS_HOME/etc/opennms-activemq.xml 取消......

qoswork
41分钟前
5
0
PHP Socket初探---先从一个简单的socket服务器开始

socket的中文名字叫做套接字,这种东西就是对TCP/IP的“封装”。现实中的网络实际上只有四层而已,从上至下分别是应用层、传输层、网络层、数据链路层。最常用的http协议则是属于应用层的协议...

bengozhong
48分钟前
5
0
Git

指令 git init :创建版本库,生成.git文件夹 git add XX:上传代码到暂存区 git state:查看目前本地工作起、暂存区、分支,三者之间的文件状态 git diff demo.html:查看工作区和暂存区的代码...

Hui先生
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部