#include <algorithm>
#include <atomic>
#include <chrono>
#include <functional>
#include <iostream>
#include <iterator>
#include <string>
#include <thread>
#include <vector>
 
template <typename TaskType>
struct task_list {
 
	struct node {
		node(std::function<TaskType> task)
			: task(task), next(nullptr) { }
 
		std::function<void()> task;
		std::atomic<node*> next;
	};
 
	std::atomic<node*> tail{ nullptr };
 
	void push_task(std::function<TaskType> task) {
		node* new_node = new node(task);
		node* old_tail = tail.exchange(new_node, std::memory_order_relaxed);
 
		if(old_tail == nullptr || old_tail->next.exchange(new_node, std::memory_order_consume) == old_tail) {
			delete old_tail;
 
			node* current = new_node;
			for(;;) {
				current->task();
				node* expected = current->next.exchange(current, std::memory_order_release);
				if(expected == nullptr) return;
				else {
					delete current;
					current = expected;
				}
			}
		}
	}
 
	~task_list() {
		delete tail.load();
	}
};
 
int main() {
	task_list<void()> list;
 
	std::vector<std::thread> threads;
	std::string hello = "Hello, World!\n";
 
	auto task = [&list, &hello] {
		std::transform(std::begin(hello), std::end(hello), std::ostream_iterator<char>(std::cout), [](auto c) {
			std::this_thread::yield();
			std::this_thread::yield();
			return c;
		});
	};
 
	std::cout << "Ugly:\n";
	for(int i = 0; i < 10; ++i) {
		threads.emplace_back([&list, task] {
			task();
		});
	}
 
	for(auto& thread : threads)
		if(thread.joinable()) thread.join();
	threads.clear();
 
	std::cout << "\nNice:\n";
	for(int i = 0; i < 10; ++i) {
		threads.emplace_back([&list, task] {
			list.push_task(task);
		});
	}
 
	for(auto& thread : threads)
		if(thread.joinable()) thread.join();
}
 

I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGF0b21pYz4KI2luY2x1ZGUgPGNocm9ubz4KI2luY2x1ZGUgPGZ1bmN0aW9uYWw+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGl0ZXJhdG9yPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dGhyZWFkPgojaW5jbHVkZSA8dmVjdG9yPgoKdGVtcGxhdGUgPHR5cGVuYW1lIFRhc2tUeXBlPgpzdHJ1Y3QgdGFza19saXN0IHsKCglzdHJ1Y3Qgbm9kZSB7CgkJbm9kZShzdGQ6OmZ1bmN0aW9uPFRhc2tUeXBlPiB0YXNrKQoJCQk6IHRhc2sodGFzayksIG5leHQobnVsbHB0cikgeyB9CgoJCXN0ZDo6ZnVuY3Rpb248dm9pZCgpPiB0YXNrOwoJCXN0ZDo6YXRvbWljPG5vZGUqPiBuZXh0OwoJfTsKCglzdGQ6OmF0b21pYzxub2RlKj4gdGFpbHsgbnVsbHB0ciB9OwoKCXZvaWQgcHVzaF90YXNrKHN0ZDo6ZnVuY3Rpb248VGFza1R5cGU+IHRhc2spIHsKCQlub2RlKiBuZXdfbm9kZSA9IG5ldyBub2RlKHRhc2spOwoJCW5vZGUqIG9sZF90YWlsID0gdGFpbC5leGNoYW5nZShuZXdfbm9kZSwgc3RkOjptZW1vcnlfb3JkZXJfcmVsYXhlZCk7CgoJCWlmKG9sZF90YWlsID09IG51bGxwdHIgfHwgb2xkX3RhaWwtPm5leHQuZXhjaGFuZ2UobmV3X25vZGUsIHN0ZDo6bWVtb3J5X29yZGVyX2NvbnN1bWUpID09IG9sZF90YWlsKSB7CgkJCWRlbGV0ZSBvbGRfdGFpbDsKCgkJCW5vZGUqIGN1cnJlbnQgPSBuZXdfbm9kZTsKCQkJZm9yKDs7KSB7CgkJCQljdXJyZW50LT50YXNrKCk7CgkJCQlub2RlKiBleHBlY3RlZCA9IGN1cnJlbnQtPm5leHQuZXhjaGFuZ2UoY3VycmVudCwgc3RkOjptZW1vcnlfb3JkZXJfcmVsZWFzZSk7CgkJCQlpZihleHBlY3RlZCA9PSBudWxscHRyKSByZXR1cm47CgkJCQllbHNlIHsKCQkJCQlkZWxldGUgY3VycmVudDsKCQkJCQljdXJyZW50ID0gZXhwZWN0ZWQ7CgkJCQl9CgkJCX0KCQl9Cgl9CgoJfnRhc2tfbGlzdCgpIHsKCQlkZWxldGUgdGFpbC5sb2FkKCk7Cgl9Cn07CgppbnQgbWFpbigpIHsKCXRhc2tfbGlzdDx2b2lkKCk+IGxpc3Q7CgoJc3RkOjp2ZWN0b3I8c3RkOjp0aHJlYWQ+IHRocmVhZHM7CglzdGQ6OnN0cmluZyBoZWxsbyA9ICJIZWxsbywgV29ybGQhXG4iOwoKCWF1dG8gdGFzayA9IFsmbGlzdCwgJmhlbGxvXSB7CgkJc3RkOjp0cmFuc2Zvcm0oc3RkOjpiZWdpbihoZWxsbyksIHN0ZDo6ZW5kKGhlbGxvKSwgc3RkOjpvc3RyZWFtX2l0ZXJhdG9yPGNoYXI+KHN0ZDo6Y291dCksIFtdKGF1dG8gYykgewoJCQlzdGQ6OnRoaXNfdGhyZWFkOjp5aWVsZCgpOwoJCQlzdGQ6OnRoaXNfdGhyZWFkOjp5aWVsZCgpOwoJCQlyZXR1cm4gYzsKCQl9KTsKCX07CgoJc3RkOjpjb3V0IDw8ICJVZ2x5OlxuIjsKCWZvcihpbnQgaSA9IDA7IGkgPCAxMDsgKytpKSB7CgkJdGhyZWFkcy5lbXBsYWNlX2JhY2soWyZsaXN0LCB0YXNrXSB7CgkJCXRhc2soKTsKCQl9KTsKCX0KCQoJZm9yKGF1dG8mIHRocmVhZCA6IHRocmVhZHMpCgkJaWYodGhyZWFkLmpvaW5hYmxlKCkpIHRocmVhZC5qb2luKCk7Cgl0aHJlYWRzLmNsZWFyKCk7CgoJc3RkOjpjb3V0IDw8ICJcbk5pY2U6XG4iOwoJZm9yKGludCBpID0gMDsgaSA8IDEwOyArK2kpIHsKCQl0aHJlYWRzLmVtcGxhY2VfYmFjayhbJmxpc3QsIHRhc2tdIHsKCQkJbGlzdC5wdXNoX3Rhc2sodGFzayk7CgkJfSk7Cgl9CgoJZm9yKGF1dG8mIHRocmVhZCA6IHRocmVhZHMpCgkJaWYodGhyZWFkLmpvaW5hYmxlKCkpIHRocmVhZC5qb2luKCk7Cn0K