circular_list_algorithms.hpp 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476
  1. /////////////////////////////////////////////////////////////////////////////
  2. //
  3. // (C) Copyright Olaf Krzikalla 2004-2006.
  4. // (C) Copyright Ion Gaztanaga 2006-2014
  5. //
  6. // Distributed under the Boost Software License, Version 1.0.
  7. // (See accompanying file LICENSE_1_0.txt or copy at
  8. // http://www.boost.org/LICENSE_1_0.txt)
  9. //
  10. // See http://www.boost.org/libs/intrusive for documentation.
  11. //
  12. /////////////////////////////////////////////////////////////////////////////
  13. #ifndef BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP
  14. #define BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP
  15. #include <boost/intrusive/detail/config_begin.hpp>
  16. #include <boost/intrusive/intrusive_fwd.hpp>
  17. #include <boost/intrusive/detail/workaround.hpp>
  18. #include <boost/intrusive/detail/algo_type.hpp>
  19. #include <cstddef>
  20. #if defined(BOOST_HAS_PRAGMA_ONCE)
  21. # pragma once
  22. #endif
  23. namespace boost {
  24. namespace intrusive {
  25. //! circular_list_algorithms provides basic algorithms to manipulate nodes
  26. //! forming a circular doubly linked list. An empty circular list is formed by a node
  27. //! whose pointers point to itself.
  28. //!
  29. //! circular_list_algorithms is configured with a NodeTraits class, which encapsulates the
  30. //! information about the node to be manipulated. NodeTraits must support the
  31. //! following interface:
  32. //!
  33. //! <b>Typedefs</b>:
  34. //!
  35. //! <tt>node</tt>: The type of the node that forms the circular list
  36. //!
  37. //! <tt>node_ptr</tt>: A pointer to a node
  38. //!
  39. //! <tt>const_node_ptr</tt>: A pointer to a const node
  40. //!
  41. //! <b>Static functions</b>:
  42. //!
  43. //! <tt>static node_ptr get_previous(const_node_ptr n);</tt>
  44. //!
  45. //! <tt>static void set_previous(node_ptr n, node_ptr prev);</tt>
  46. //!
  47. //! <tt>static node_ptr get_next(const_node_ptr n);</tt>
  48. //!
  49. //! <tt>static void set_next(node_ptr n, node_ptr next);</tt>
  50. template<class NodeTraits>
  51. class circular_list_algorithms
  52. {
  53. public:
  54. typedef typename NodeTraits::node node;
  55. typedef typename NodeTraits::node_ptr node_ptr;
  56. typedef typename NodeTraits::const_node_ptr const_node_ptr;
  57. typedef NodeTraits node_traits;
  58. //! <b>Effects</b>: Constructs an non-used list element, so that
  59. //! inited(this_node) == true
  60. //!
  61. //! <b>Complexity</b>: Constant
  62. //!
  63. //! <b>Throws</b>: Nothing.
  64. static void init(node_ptr this_node) BOOST_NOEXCEPT
  65. {
  66. const node_ptr null_node = node_ptr();
  67. NodeTraits::set_next(this_node, null_node);
  68. NodeTraits::set_previous(this_node, null_node);
  69. }
  70. //! <b>Effects</b>: Returns true is "this_node" is in a non-used state
  71. //! as if it was initialized by the "init" function.
  72. //!
  73. //! <b>Complexity</b>: Constant
  74. //!
  75. //! <b>Throws</b>: Nothing.
  76. inline static bool inited(const_node_ptr this_node) BOOST_NOEXCEPT
  77. { return !NodeTraits::get_next(this_node); }
  78. //! <b>Effects</b>: Constructs an empty list, making this_node the only
  79. //! node of the circular list:
  80. //! <tt>NodeTraits::get_next(this_node) == NodeTraits::get_previous(this_node)
  81. //! == this_node</tt>.
  82. //!
  83. //! <b>Complexity</b>: Constant
  84. //!
  85. //! <b>Throws</b>: Nothing.
  86. static void init_header(node_ptr this_node) BOOST_NOEXCEPT
  87. {
  88. NodeTraits::set_next(this_node, this_node);
  89. NodeTraits::set_previous(this_node, this_node);
  90. }
  91. //! <b>Effects</b>: Returns true if this_node_points to an empty list.
  92. //!
  93. //! <b>Complexity</b>: Constant
  94. //!
  95. //! <b>Throws</b>: Nothing.
  96. inline static bool is_empty(const_node_ptr this_node) BOOST_NOEXCEPT
  97. {
  98. return NodeTraits::get_next(this_node) == this_node;
  99. }
  100. //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
  101. //!
  102. //! <b>Effects</b>: Returns true is "this_node" is the only node of a circular list:
  103. //! <tt>return NodeTraits::get_next(this_node) == this_node</tt>
  104. //!
  105. //! <b>Complexity</b>: Constant
  106. //!
  107. //! <b>Throws</b>: Nothing.
  108. static bool unique(const_node_ptr this_node) BOOST_NOEXCEPT
  109. {
  110. node_ptr next = NodeTraits::get_next(this_node);
  111. return !next || next == this_node;
  112. }
  113. //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
  114. //!
  115. //! <b>Effects</b>: Returns the number of nodes in a circular list. If the circular list
  116. //! is empty, returns 1.
  117. //!
  118. //! <b>Complexity</b>: Linear
  119. //!
  120. //! <b>Throws</b>: Nothing.
  121. static std::size_t count(const_node_ptr this_node) BOOST_NOEXCEPT
  122. {
  123. std::size_t result = 0;
  124. const_node_ptr p = this_node;
  125. do{
  126. p = NodeTraits::get_next(p);
  127. ++result;
  128. }while (p != this_node);
  129. return result;
  130. }
  131. //! <b>Requires</b>: this_node must be in a circular list or be an empty circular list.
  132. //!
  133. //! <b>Effects</b>: Unlinks the node from the circular list.
  134. //!
  135. //! <b>Complexity</b>: Constant
  136. //!
  137. //! <b>Throws</b>: Nothing.
  138. static node_ptr unlink(node_ptr this_node) BOOST_NOEXCEPT
  139. {
  140. node_ptr next(NodeTraits::get_next(this_node));
  141. node_ptr prev(NodeTraits::get_previous(this_node));
  142. NodeTraits::set_next(prev, next);
  143. NodeTraits::set_previous(next, prev);
  144. return next;
  145. }
  146. //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.
  147. //!
  148. //! <b>Effects</b>: Unlinks the node [b, e) from the circular list.
  149. //!
  150. //! <b>Complexity</b>: Constant
  151. //!
  152. //! <b>Throws</b>: Nothing.
  153. static void unlink(node_ptr b, node_ptr e) BOOST_NOEXCEPT
  154. {
  155. if (b != e) {
  156. node_ptr prevb(NodeTraits::get_previous(b));
  157. NodeTraits::set_previous(e, prevb);
  158. NodeTraits::set_next(prevb, e);
  159. }
  160. }
  161. //! <b>Requires</b>: nxt_node must be a node of a circular list.
  162. //!
  163. //! <b>Effects</b>: Links this_node before nxt_node in the circular list.
  164. //!
  165. //! <b>Complexity</b>: Constant
  166. //!
  167. //! <b>Throws</b>: Nothing.
  168. static void link_before(node_ptr nxt_node, node_ptr this_node) BOOST_NOEXCEPT
  169. {
  170. node_ptr prev(NodeTraits::get_previous(nxt_node));
  171. NodeTraits::set_previous(this_node, prev);
  172. NodeTraits::set_next(this_node, nxt_node);
  173. //nxt_node might be an alias for prev->next_
  174. //so use it before NodeTraits::set_next(prev, ...)
  175. //is called and the reference changes its value
  176. NodeTraits::set_previous(nxt_node, this_node);
  177. NodeTraits::set_next(prev, this_node);
  178. }
  179. //! <b>Requires</b>: prev_node must be a node of a circular list.
  180. //!
  181. //! <b>Effects</b>: Links this_node after prev_node in the circular list.
  182. //!
  183. //! <b>Complexity</b>: Constant
  184. //!
  185. //! <b>Throws</b>: Nothing.
  186. static void link_after(node_ptr prev_node, node_ptr this_node) BOOST_NOEXCEPT
  187. {
  188. node_ptr next(NodeTraits::get_next(prev_node));
  189. NodeTraits::set_previous(this_node, prev_node);
  190. NodeTraits::set_next(this_node, next);
  191. //prev_node might be an alias for next->next_
  192. //so use it before update it before NodeTraits::set_previous(next, ...)
  193. //is called and the reference changes it's value
  194. NodeTraits::set_next(prev_node, this_node);
  195. NodeTraits::set_previous(next, this_node);
  196. }
  197. //! <b>Requires</b>: this_node and other_node must be nodes inserted
  198. //! in circular lists or be empty circular lists.
  199. //!
  200. //! <b>Effects</b>: Swaps the position of the nodes: this_node is inserted in
  201. //! other_nodes position in the second circular list and the other_node is inserted
  202. //! in this_node's position in the first circular list.
  203. //!
  204. //! <b>Complexity</b>: Constant
  205. //!
  206. //! <b>Throws</b>: Nothing.
  207. static void swap_nodes(node_ptr this_node, node_ptr other_node) BOOST_NOEXCEPT
  208. {
  209. if (other_node == this_node)
  210. return;
  211. bool this_inited = inited(this_node);
  212. bool other_inited = inited(other_node);
  213. if(this_inited){
  214. init_header(this_node);
  215. }
  216. if(other_inited){
  217. init_header(other_node);
  218. }
  219. node_ptr next_this(NodeTraits::get_next(this_node));
  220. node_ptr prev_this(NodeTraits::get_previous(this_node));
  221. node_ptr next_other(NodeTraits::get_next(other_node));
  222. node_ptr prev_other(NodeTraits::get_previous(other_node));
  223. //these first two swaps must happen before the other two
  224. swap_prev(next_this, next_other);
  225. swap_next(prev_this, prev_other);
  226. swap_next(this_node, other_node);
  227. swap_prev(this_node, other_node);
  228. if(this_inited){
  229. init(other_node);
  230. }
  231. if(other_inited){
  232. init(this_node);
  233. }
  234. }
  235. //! <b>Requires</b>: b and e must be nodes of the same circular list or an empty range.
  236. //! and p must be a node of a different circular list or may not be an iterator in
  237. // [b, e).
  238. //!
  239. //! <b>Effects</b>: Removes the nodes from [b, e) range from their circular list and inserts
  240. //! them before p in p's circular list.
  241. //!
  242. //! <b>Complexity</b>: Constant
  243. //!
  244. //! <b>Throws</b>: Nothing.
  245. static void transfer(node_ptr p, node_ptr b, node_ptr e) BOOST_NOEXCEPT
  246. {
  247. if (b != e && p != b && p != e) {
  248. node_ptr prev_p(NodeTraits::get_previous(p));
  249. node_ptr prev_b(NodeTraits::get_previous(b));
  250. node_ptr prev_e(NodeTraits::get_previous(e));
  251. NodeTraits::set_next(prev_e, p);
  252. NodeTraits::set_previous(p, prev_e);
  253. NodeTraits::set_next(prev_b, e);
  254. NodeTraits::set_previous(e, prev_b);
  255. NodeTraits::set_next(prev_p, b);
  256. NodeTraits::set_previous(b, prev_p);
  257. }
  258. }
  259. //! <b>Requires</b>: i must a node of a circular list
  260. //! and p must be a node of a different circular list.
  261. //!
  262. //! <b>Effects</b>: Removes the node i from its circular list and inserts
  263. //! it before p in p's circular list.
  264. //! If p == i or p == NodeTraits::get_next(i), this function is a null operation.
  265. //!
  266. //! <b>Complexity</b>: Constant
  267. //!
  268. //! <b>Throws</b>: Nothing.
  269. static void transfer(node_ptr p, node_ptr i) BOOST_NOEXCEPT
  270. {
  271. node_ptr n(NodeTraits::get_next(i));
  272. if(n != p && i != p){
  273. node_ptr prev_p(NodeTraits::get_previous(p));
  274. node_ptr prev_i(NodeTraits::get_previous(i));
  275. NodeTraits::set_next(prev_p, i);
  276. NodeTraits::set_previous(i, prev_p);
  277. NodeTraits::set_next(i, p);
  278. NodeTraits::set_previous(p, i);
  279. NodeTraits::set_previous(n, prev_i);
  280. NodeTraits::set_next(prev_i, n);
  281. }
  282. }
  283. //! <b>Effects</b>: Reverses the order of elements in the list.
  284. //!
  285. //! <b>Throws</b>: Nothing.
  286. //!
  287. //! <b>Complexity</b>: This function is linear time.
  288. static void reverse(node_ptr p) BOOST_NOEXCEPT
  289. {
  290. node_ptr f(NodeTraits::get_next(p));
  291. node_ptr i(NodeTraits::get_next(f)), e(p);
  292. while(i != e) {
  293. node_ptr n = i;
  294. i = NodeTraits::get_next(i);
  295. transfer(f, n, i);
  296. f = n;
  297. }
  298. }
  299. //! <b>Effects</b>: Moves the node p n positions towards the end of the list.
  300. //!
  301. //! <b>Throws</b>: Nothing.
  302. //!
  303. //! <b>Complexity</b>: Linear to the number of moved positions.
  304. static void move_backwards(node_ptr p, std::size_t n) BOOST_NOEXCEPT
  305. {
  306. //Null shift, nothing to do
  307. if(!n) return;
  308. node_ptr first = NodeTraits::get_next(p);
  309. //size() == 0 or 1, nothing to do
  310. if(first == NodeTraits::get_previous(p)) return;
  311. unlink(p);
  312. //Now get the new first node
  313. while(n--){
  314. first = NodeTraits::get_next(first);
  315. }
  316. link_before(first, p);
  317. }
  318. //! <b>Effects</b>: Moves the node p n positions towards the beginning of the list.
  319. //!
  320. //! <b>Throws</b>: Nothing.
  321. //!
  322. //! <b>Complexity</b>: Linear to the number of moved positions.
  323. static void move_forward(node_ptr p, std::size_t n) BOOST_NOEXCEPT
  324. {
  325. //Null shift, nothing to do
  326. if(!n) return;
  327. node_ptr last = NodeTraits::get_previous(p);
  328. //size() == 0 or 1, nothing to do
  329. if(last == NodeTraits::get_next(p)) return;
  330. unlink(p);
  331. //Now get the new last node
  332. while(n--){
  333. last = NodeTraits::get_previous(last);
  334. }
  335. link_after(last, p);
  336. }
  337. //! <b>Requires</b>: f and l must be in a circular list.
  338. //!
  339. //! <b>Effects</b>: Returns the number of nodes in the range [f, l).
  340. //!
  341. //! <b>Complexity</b>: Linear
  342. //!
  343. //! <b>Throws</b>: Nothing.
  344. static std::size_t distance(const_node_ptr f, const_node_ptr l) BOOST_NOEXCEPT
  345. {
  346. std::size_t result = 0;
  347. while(f != l){
  348. f = NodeTraits::get_next(f);
  349. ++result;
  350. }
  351. return result;
  352. }
  353. struct stable_partition_info
  354. {
  355. std::size_t num_1st_partition;
  356. std::size_t num_2nd_partition;
  357. node_ptr beg_2st_partition;
  358. };
  359. template<class Pred>
  360. static void stable_partition(node_ptr beg, node_ptr end, Pred pred, stable_partition_info &info)
  361. {
  362. node_ptr bcur = node_traits::get_previous(beg);
  363. node_ptr cur = beg;
  364. node_ptr new_f = end;
  365. std::size_t num1 = 0, num2 = 0;
  366. while(cur != end){
  367. if(pred(cur)){
  368. ++num1;
  369. bcur = cur;
  370. cur = node_traits::get_next(cur);
  371. }
  372. else{
  373. ++num2;
  374. node_ptr last_to_remove = bcur;
  375. new_f = cur;
  376. bcur = cur;
  377. cur = node_traits::get_next(cur);
  378. BOOST_INTRUSIVE_TRY{
  379. //Main loop
  380. while(cur != end){
  381. if(pred(cur)){ //Might throw
  382. ++num1;
  383. //Process current node
  384. node_traits::set_next (last_to_remove, cur);
  385. node_traits::set_previous(cur, last_to_remove);
  386. last_to_remove = cur;
  387. node_ptr nxt = node_traits::get_next(cur);
  388. node_traits::set_next (bcur, nxt);
  389. node_traits::set_previous(nxt, bcur);
  390. cur = nxt;
  391. }
  392. else{
  393. ++num2;
  394. bcur = cur;
  395. cur = node_traits::get_next(cur);
  396. }
  397. }
  398. }
  399. BOOST_INTRUSIVE_CATCH(...){
  400. node_traits::set_next (last_to_remove, new_f);
  401. node_traits::set_previous(new_f, last_to_remove);
  402. BOOST_INTRUSIVE_RETHROW;
  403. }
  404. BOOST_INTRUSIVE_CATCH_END
  405. node_traits::set_next(last_to_remove, new_f);
  406. node_traits::set_previous(new_f, last_to_remove);
  407. break;
  408. }
  409. }
  410. info.num_1st_partition = num1;
  411. info.num_2nd_partition = num2;
  412. info.beg_2st_partition = new_f;
  413. }
  414. private:
  415. static void swap_prev(node_ptr this_node, node_ptr other_node) BOOST_NOEXCEPT
  416. {
  417. node_ptr temp(NodeTraits::get_previous(this_node));
  418. NodeTraits::set_previous(this_node, NodeTraits::get_previous(other_node));
  419. NodeTraits::set_previous(other_node, temp);
  420. }
  421. static void swap_next(node_ptr this_node, node_ptr other_node) BOOST_NOEXCEPT
  422. {
  423. node_ptr temp(NodeTraits::get_next(this_node));
  424. NodeTraits::set_next(this_node, NodeTraits::get_next(other_node));
  425. NodeTraits::set_next(other_node, temp);
  426. }
  427. };
  428. /// @cond
  429. template<class NodeTraits>
  430. struct get_algo<CircularListAlgorithms, NodeTraits>
  431. {
  432. typedef circular_list_algorithms<NodeTraits> type;
  433. };
  434. /// @endcond
  435. } //namespace intrusive
  436. } //namespace boost
  437. #include <boost/intrusive/detail/config_end.hpp>
  438. #endif //BOOST_INTRUSIVE_CIRCULAR_LIST_ALGORITHMS_HPP