1 /*************************************************************************/
2 /*  self_list.h                                                          */
3 /*************************************************************************/
4 /*                       This file is part of:                           */
5 /*                           GODOT ENGINE                                */
6 /*                      https://godotengine.org                          */
7 /*************************************************************************/
8 /* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur.                 */
9 /* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md).   */
10 /*                                                                       */
11 /* Permission is hereby granted, free of charge, to any person obtaining */
12 /* a copy of this software and associated documentation files (the       */
13 /* "Software"), to deal in the Software without restriction, including   */
14 /* without limitation the rights to use, copy, modify, merge, publish,   */
15 /* distribute, sublicense, and/or sell copies of the Software, and to    */
16 /* permit persons to whom the Software is furnished to do so, subject to */
17 /* the following conditions:                                             */
18 /*                                                                       */
19 /* The above copyright notice and this permission notice shall be        */
20 /* included in all copies or substantial portions of the Software.       */
21 /*                                                                       */
22 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,       */
23 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF    */
24 /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
25 /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY  */
26 /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,  */
27 /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE     */
28 /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                */
29 /*************************************************************************/
30 
31 #ifndef SELF_LIST_H
32 #define SELF_LIST_H
33 
34 #include "core/error_macros.h"
35 #include "core/typedefs.h"
36 
37 template <class T>
38 class SelfList {
39 public:
40 	class List {
41 
42 		SelfList<T> *_first;
43 		SelfList<T> *_last;
44 
45 	public:
add(SelfList<T> * p_elem)46 		void add(SelfList<T> *p_elem) {
47 
48 			ERR_FAIL_COND(p_elem->_root);
49 
50 			p_elem->_root = this;
51 			p_elem->_next = _first;
52 			p_elem->_prev = NULL;
53 
54 			if (_first) {
55 				_first->_prev = p_elem;
56 
57 			} else {
58 				_last = p_elem;
59 			}
60 
61 			_first = p_elem;
62 		}
63 
add_last(SelfList<T> * p_elem)64 		void add_last(SelfList<T> *p_elem) {
65 
66 			ERR_FAIL_COND(p_elem->_root);
67 
68 			p_elem->_root = this;
69 			p_elem->_next = NULL;
70 			p_elem->_prev = _last;
71 
72 			if (_last) {
73 				_last->_next = p_elem;
74 
75 			} else {
76 				_first = p_elem;
77 			}
78 
79 			_last = p_elem;
80 		}
81 
remove(SelfList<T> * p_elem)82 		void remove(SelfList<T> *p_elem) {
83 
84 			ERR_FAIL_COND(p_elem->_root != this);
85 			if (p_elem->_next) {
86 				p_elem->_next->_prev = p_elem->_prev;
87 			}
88 
89 			if (p_elem->_prev) {
90 				p_elem->_prev->_next = p_elem->_next;
91 			}
92 
93 			if (_first == p_elem) {
94 				_first = p_elem->_next;
95 			}
96 
97 			if (_last == p_elem) {
98 				_last = p_elem->_prev;
99 			}
100 
101 			p_elem->_next = NULL;
102 			p_elem->_prev = NULL;
103 			p_elem->_root = NULL;
104 		}
105 
first()106 		_FORCE_INLINE_ SelfList<T> *first() { return _first; }
first()107 		_FORCE_INLINE_ const SelfList<T> *first() const { return _first; }
List()108 		_FORCE_INLINE_ List() {
109 			_first = NULL;
110 			_last = NULL;
111 		}
~List()112 		_FORCE_INLINE_ ~List() { ERR_FAIL_COND(_first != NULL); }
113 	};
114 
115 private:
116 	List *_root;
117 	T *_self;
118 	SelfList<T> *_next;
119 	SelfList<T> *_prev;
120 
121 public:
in_list()122 	_FORCE_INLINE_ bool in_list() const { return _root; }
remove_from_list()123 	_FORCE_INLINE_ void remove_from_list() {
124 		if (_root) _root->remove(this);
125 	}
next()126 	_FORCE_INLINE_ SelfList<T> *next() { return _next; }
prev()127 	_FORCE_INLINE_ SelfList<T> *prev() { return _prev; }
next()128 	_FORCE_INLINE_ const SelfList<T> *next() const { return _next; }
prev()129 	_FORCE_INLINE_ const SelfList<T> *prev() const { return _prev; }
self()130 	_FORCE_INLINE_ T *self() const { return _self; }
131 
SelfList(T * p_self)132 	_FORCE_INLINE_ SelfList(T *p_self) {
133 
134 		_self = p_self;
135 		_next = NULL;
136 		_prev = NULL;
137 		_root = NULL;
138 	}
139 
~SelfList()140 	_FORCE_INLINE_ ~SelfList() {
141 
142 		if (_root)
143 			_root->remove(this);
144 	}
145 };
146 
147 #endif // SELF_LIST_H
148