fork download
copy 
  1. //////////////////////////////////////////////////////////////////////
  2. // linked_list.h
  3.  
  4. #pragma once
  5.  
  6. //////////////////////////////////////////////////////////////////////
  7.  
  8. #include <cstddef>
  9. #include <functional>
  10.  
  11. //////////////////////////////////////////////////////////////////////
  12.  
  13. struct list_node
  14. {
  15. 	list_node *next;
  16. 	list_node *prev;
  17. };
  18.  
  19. //////////////////////////////////////////////////////////////////////
  20.  
  21. template<typename T, size_t off> struct linked_list
  22. {
  23. 	//////////////////////////////////////////////////////////////////////
  24.  
  25. 	static list_node const *get_node(T const *o)
  26. 	{
  27. 		return reinterpret_cast<list_node const *>(reinterpret_cast<char const *>(o) + off);
  28. 	}
  29.  
  30. 	//////////////////////////////////////////////////////////////////////
  31.  
  32. 	static list_node *get_node(T *o)
  33. 	{
  34. 		return reinterpret_cast<list_node *>(reinterpret_cast<char *>(o) + off);
  35. 	}
  36.  
  37. 	//////////////////////////////////////////////////////////////////////
  38.  
  39. 	static T const *get_object(list_node const *node)
  40. 	{
  41. 		return reinterpret_cast<T const *>(reinterpret_cast<char const *>(node) - off);
  42. 	}
  43.  
  44. 	//////////////////////////////////////////////////////////////////////
  45.  
  46. 	static T *get_object(list_node *node)
  47. 	{
  48. 		return reinterpret_cast<T *>(reinterpret_cast<char *>(node) - off);
  49. 	}
  50.  
  51. 	//////////////////////////////////////////////////////////////////////
  52.  
  53. 	list_node root;
  54.  
  55. 	//////////////////////////////////////////////////////////////////////
  56.  
  57. 	linked_list()
  58. 	{
  59. 		root.next = &root;
  60. 		root.prev = &root;
  61. 	}
  62.  
  63. 	//////////////////////////////////////////////////////////////////////
  64.  
  65. 	void push_front(T *obj)
  66. 	{
  67. 		list_node *node = get_node(obj);
  68. 		root.next->prev = node;
  69. 		node->next = root.next;
  70. 		node->prev = &root;
  71. 		root.next = node;
  72. 	}
  73.  
  74. 	//////////////////////////////////////////////////////////////////////
  75.  
  76. 	void push_front(T &obj)
  77. 	{
  78. 		list_node *node = get_node(&obj);
  79. 		root.next->prev = node;
  80. 		node->next = root.next;
  81. 		node->prev = &root;
  82. 		root.next = node;
  83. 	}
  84.  
  85. 	//////////////////////////////////////////////////////////////////////
  86.  
  87. 	void push_back(T *obj)
  88. 	{
  89. 		list_node *node = get_node(obj);
  90. 		node->prev = root.prev;
  91. 		node->next = &root;
  92. 		root.prev->next = node;
  93. 		root.prev = node;
  94. 	}
  95.  
  96. 	//////////////////////////////////////////////////////////////////////
  97.  
  98. 	void push_back(T &obj)
  99. 	{
  100. 		list_node *node = get_node(&obj);
  101. 		node->prev = root.prev;
  102. 		node->next = &root;
  103. 		root.prev->next = node;
  104. 		root.prev = node;
  105. 	}
  106.  
  107. 	//////////////////////////////////////////////////////////////////////
  108.  
  109. 	void insert_before(T *pos, T *obj)
  110. 	{
  111. 		list_node *node = get_node(obj);
  112. 		list_node *n = get_node(pos);
  113. 		n->prev->next = node;
  114. 		node->prev = n->prev;
  115. 		n->prev = node;
  116. 		node->next = n;
  117. 	}
  118.  
  119. 	//////////////////////////////////////////////////////////////////////
  120.  
  121. 	void insert_before(T &pos, T &obj)
  122. 	{
  123. 		list_node *node = get_node(&obj);
  124. 		list_node *n = get_node(&pos);
  125. 		n->prev->next = node;
  126. 		node->prev = n->prev;
  127. 		n->prev = node;
  128. 		node->next = n;
  129. 	}
  130.  
  131. 	//////////////////////////////////////////////////////////////////////
  132.  
  133. 	void insert_after(T *pos, T *obj)
  134. 	{
  135. 		list_node *node = get_node(obj);
  136. 		list_node *n = get_node(pos);
  137. 		n->next->prev = node;
  138. 		node->next = n->next;
  139. 		n->next = node;
  140. 		node->prev = n;
  141. 	}
  142.  
  143. 	//////////////////////////////////////////////////////////////////////
  144.  
  145. 	void insert_after(T &pos, T &obj)
  146. 	{
  147. 		list_node *node = get_node(&obj);
  148. 		list_node *n = get_node(&pos);
  149. 		n->next->prev = node;
  150. 		node->next = n->next;
  151. 		n->next = node;
  152. 		node->prev = n;
  153. 	}
  154.  
  155. 	//////////////////////////////////////////////////////////////////////
  156.  
  157. 	void remove(T *obj)
  158. 	{
  159. 		list_node *node = get_node(obj);
  160. 		node->prev->next = node->next;
  161. 		node->next->prev = node->prev;
  162. 	}
  163.  
  164. 	//////////////////////////////////////////////////////////////////////
  165.  
  166. 	void remove(T &obj)
  167. 	{
  168. 		list_node *node = get_node(&obj);
  169. 		node->prev->next = node->next;
  170. 		node->next->prev = node->prev;
  171. 	}
  172.  
  173. 	//////////////////////////////////////////////////////////////////////
  174.  
  175. 	T *pop_back()
  176. 	{
  177. 		list_node *node = root.prev;
  178. 		node->prev->next = node->next;
  179. 		node->next->prev = node->prev;
  180. 		return get_object(node);
  181. 	}
  182.  
  183. 	//////////////////////////////////////////////////////////////////////
  184.  
  185. 	T *pop_front()
  186. 	{
  187. 		list_node *node = root.next;
  188. 		node->next->prev = node->prev;
  189. 		node->prev->next = node->next;
  190. 		return get_object(node);
  191. 	}
  192.  
  193. 	//////////////////////////////////////////////////////////////////////
  194.  
  195. 	bool empty() const
  196. 	{
  197. 		return root.next == &root;
  198. 	}
  199.  
  200. 	//////////////////////////////////////////////////////////////////////
  201.  
  202. 	void clear()
  203. 	{
  204. 		root.next = root.prev = &root;
  205. 	}
  206.  
  207. 	//////////////////////////////////////////////////////////////////////
  208.  
  209. 	T *head() const
  210. 	{
  211. 		return get_object(root.next);
  212. 	}
  213.  
  214. 	//////////////////////////////////////////////////////////////////////
  215.  
  216. 	T *tail() const
  217. 	{
  218. 		return get_object(root.prev);
  219. 	}
  220.  
  221. 	//////////////////////////////////////////////////////////////////////
  222.  
  223. 	T const *end()
  224. 	{
  225. 		return get_object(&root);
  226. 	}
  227.  
  228. 	//////////////////////////////////////////////////////////////////////
  229.  
  230. 	T *next(T *i) const
  231. 	{
  232. 		return get_object(get_node(i)->next);
  233. 	}
  234.  
  235. 	//////////////////////////////////////////////////////////////////////
  236.  
  237. 	T *prev(T *i) const
  238. 	{
  239. 		return get_object(get_node(i)->prev);
  240. 	}
  241.  
  242. 	//////////////////////////////////////////////////////////////////////
  243.  
  244. 	bool for_each(std::function<bool (T *)> func)
  245. 	{
  246. 		for(T *i = head(); i != end(); i = next(i))
  247. 		{
  248. 			if(!func(i))
  249. 			{
  250. 				return false;
  251. 			}
  252. 		}
  253. 		return true;
  254. 	}
  255.  
  256. 	//////////////////////////////////////////////////////////////////////
  257.  
  258. 	T *find(std::function<bool (T *)> func)
  259. 	{
  260. 		for(T *i = head(); i != end(); i = next(i))
  261. 		{
  262. 			if(func(i))
  263. 			{
  264. 				return i;
  265. 			}
  266. 		}
  267. 		return nullptr;
  268. 	}
  269.  
  270. 	//////////////////////////////////////////////////////////////////////
  271.  
  272. };
  273.  
  274. //////////////////////////////////////////////////////////////////////
  275.  
  276. // Yuck:
  277.  
  278. #define declare_linked_list(type_name, node_name) \
  279. 	linked_list<type_name, offsetof(type_name, node_name)>
  280.  
  281. #define typedef_linked_list(type_name, node_name) \
  282. 	typedef declare_linked_list(type_name, node_name)
  283.  
  284. //////////////////////////////////////////////////////////////////////
  285. // main.cpp
  286.  
  287. #include <stdio.h>
  288. #include <random>
  289. //#include "linked_list.h"
  290.  
  291. struct foo
  292. {
  293. 	foo() : i(rand() % 10) { }
  294.  
  295. 	int i;
  296.  
  297. 	list_node node1;	// would like it if these could be made private
  298. 	list_node node2;	// but the nasty macros need to see inside...
  299. 	list_node node3;	// getting rid of the macros would be even better
  300. };
  301.  
  302. // None of these 3 options are very nice:
  303.  
  304. // 1. declare a list with the macro
  305. declare_linked_list(foo, node1) list1;
  306.  
  307. // 2. or via a typedef
  308. typedef_linked_list(foo, node2) list2_t;
  309. list2_t list2;
  310.  
  311. // 3. or very wordy non-macro declaration
  312. linked_list<foo, offsetof(foo, node3)> list3;
  313.  
  314. int main(int, char **)
  315. {
  316. 	printf("Begin\n");
  317.  
  318. 	foo foos[10];
  319.  
  320. 	for(int i=0; i<10; ++i)
  321. 	{
  322. 		list1.push_back(foos[i]);
  323. 		list2.push_back(foos[i]);
  324. 		list3.push_back(foos[i]);
  325. 	}
  326.  
  327. 	int sum = 0;
  328. 	int n = 0;
  329. 	// but this for loop is clear and readable and has very low overhead
  330. 	for(foo *i = list1.head(); i != list1.end(); i = list1.next(i))
  331. 	{
  332. 		sum += i->i;
  333. 	}
  334. 	printf("Total: %d\n", sum);
  335.  
  336. 	list2.remove(foos[2]);
  337.  
  338. 	n = 0;
  339. 	sum = 0;
  340. 	for(foo *i = list2.head(); i != list2.end(); i = list2.next(i))
  341. 	{
  342. 		sum += i->i;
  343. 	}
  344. 	printf("Total2: %d\n", sum);
  345.  
  346. 	getchar();
  347. 	return 0;
  348. }
  349.  
Success #stdin #stdout 0s 3344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Begin
Total: 47
Total2: 40
https://ideone.com/ul2PiS
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!