foobar2000 SDK  2015-08-03
chain_list_v2.h
Go to the documentation of this file.
1 namespace pfc {
2 
3  template<typename t_item>
4  class __chain_list_elem : public _list_node<t_item> {
5  public:
8 
10 
11  t_self * m_prev, * m_next;
12 
13  t_node * prev() throw() {return m_prev;}
14  t_node * next() throw() {return m_next;}
15 
16  //helper wrappers
17  void add_ref() throw() {this->refcount_add_ref();}
18  void release() throw() {this->refcount_release();}
19  //workaround for cross-list-relinking case - never actually deletes p_elem
21  };
22 
25  template<typename _t_item>
27  public:
28  typedef _t_item t_item;
30  typedef ::pfc::iterator<t_item> iterator;
31  typedef ::pfc::const_iterator<t_item> const_iterator;
33 
34  chain_list_v2_t() : m_first(), m_last(), m_count() {}
35  chain_list_v2_t(const t_self & p_source) : m_first(), m_last(), m_count() {
36  try {
37  *this = p_source;
38  } catch(...) {
39  remove_all();
40  throw;
41  }
42  }
43  template<typename t_in> void _set(const t_in & in) {
44  remove_all(); _add(in);
45  }
46  template<typename t_in> void _add(const t_in & in) {
47  for(typename t_in::const_iterator iter = in.first(); iter.is_valid(); ++in) add_item(*iter);
48  }
49  template<typename t_in> t_self & operator=(const t_in & in) {_set(in); return *this;}
50 
51  t_self & operator=(const t_self & p_other) {
52  remove_all();
53  for(t_elem * walk = p_other.m_first; walk != NULL; walk = walk->m_next) {
54  add_item(walk->m_content);
55  }
56  return *this;
57  }
58  // templated constructors = spawn of satan
59  // template<typename t_other> chain_list_v2_t(const t_other & in) { try {_add(in);} catch(...) {remove_all(); throw;} }
60 
61  t_size get_count() const {return m_count;}
62 
63  iterator first() {return iterator(m_first);}
64  iterator last() {return iterator(m_last);}
65  const_iterator first() const {return const_iterator(m_first);}
66  const_iterator last() const {return const_iterator(m_last);}
67 
68  void remove_single(const_iterator const & p_iter) {
69  PFC_ASSERT(p_iter.is_valid());
70  __unlink(_elem(p_iter));
71  }
72 
73  void remove(const_iterator const & p_iter) {
74  PFC_ASSERT(p_iter.is_valid());
75  __unlink(_elem(p_iter));
76  }
77 
78  void remove_all() throw() {
79  while(m_first != NULL) __unlink(m_first);
80  PFC_ASSERT(m_count == 0);
81  }
82  void remove_range(const_iterator const & p_from,const_iterator const & p_to) {
83  for(t_elem * walk = _elem(p_from);;) {
84  if (walk == NULL) {PFC_ASSERT(!"Should not get here"); break;}//should not happen unless there is a bug in calling code
85  t_elem * next = walk->m_next;
86  __unlink(walk);
87  if (walk == _elem(p_to)) break;
88  walk = next;
89  }
90  }
91 
92  template<typename t_callback> void enumerate(t_callback & p_callback) const {__enumerate_chain<const t_elem>(m_first,p_callback);}
93  template<typename t_callback> void enumerate(t_callback & p_callback) {__enumerate_chain<t_elem>(m_first,p_callback);}
94 
95  template<typename t_source> bool remove_item(const t_source & p_item) {
96  t_elem * elem;
97  if (__find(elem,p_item)) {
98  __unlink(elem);
99  return true;
100  } else {
101  return false;
102  }
103  }
104 
105  ~chain_list_v2_t() {remove_all();}
106 
107  template<typename t_source>
108  inline void add_item(const t_source & p_source) {
109  __link_last(new t_elem(p_source));
110  }
111  template<typename t_source>
112  inline t_self & operator+=(const t_source & p_source) {
113  add_item(p_source); return *this;
114  }
115  iterator insert_last() {return __link_last(new t_elem);}
116  iterator insert_first() {return __link_first(new t_elem);}
117  iterator insert_after(const_iterator const & p_iter) {return __link_next(_elem(p_iter),new t_elem);}
118  iterator insert_before(const_iterator const & p_iter) {return __link_prev(_elem(p_iter),new t_elem);}
119  template<typename t_source> iterator insert_last(const t_source & p_source) {return __link_last(new t_elem(p_source));}
120  template<typename t_source> iterator insert_first(const t_source & p_source) {return __link_first(new t_elem(p_source));}
121  template<typename t_source> iterator insert_after(const_iterator const & p_iter,const t_source & p_source) {return __link_next(_elem(p_iter),new t_elem(p_source));}
122  template<typename t_source> iterator insert_before(const_iterator const & p_iter,const t_source & p_source) {return __link_prev(_elem(p_iter),new t_elem(p_source));}
123 
124  template<typename t_source> const_iterator find_item(const t_source & p_item) const {
125  t_elem * elem;
126  if (!__find(elem,p_item)) return const_iterator();
127  return const_iterator(elem);
128  }
129 
130  template<typename t_source> iterator find_item(const t_source & p_item) {
131  t_elem * elem;
132  if (!__find(elem,p_item)) return iterator();
133  return iterator(elem);
134  }
135 
136  template<typename t_source> bool have_item(const t_source & p_item) const {
137  t_elem * dummy;
138  return __find(dummy,p_item);
139  }
140  template<typename t_source> void set_single(const t_source & p_item) {
141  remove_all(); add_item(p_item);
142  }
143 
145  const_iterator by_index(t_size p_index) const {return __by_index(p_index);}
147  iterator by_index(t_size p_index) {return __by_index(p_index);}
148 
149  t_self & operator<<(t_self & p_other) {
150  while(p_other.m_first != NULL) {
151  __link_last( p_other.__unlink_temporary(p_other.m_first) );
152  }
153  return *this;
154  }
155  t_self & operator>>(t_self & p_other) {
156  while(m_last != NULL) {
157  p_other.__link_first(__unlink_temporary(m_last));
158  }
159  return p_other;
160  }
162  void _link_last(const_iterator const& iter) {
163  PFC_ASSERT(iter.is_valid());
164  PFC_ASSERT( _elem(iter)->m_prev == NULL && _elem(iter)->m_next == NULL );
165  __link_last(_elem(iter));
166  }
168  void _link_first(const_iterator const& iter) {
169  PFC_ASSERT(iter.is_valid());
170  PFC_ASSERT( _elem(iter)->m_prev == NULL && _elem(iter)->m_next == NULL );
171  __link_first(_elem(iter));
172  }
173  private:
174  static t_elem * _elem(const_iterator const & iter) {
175  return static_cast<t_elem*>(iter._node());
176  }
177  t_elem * __by_index(t_size p_index) const {
178  t_elem * walk = m_first;
179  while(p_index > 0 && walk != NULL) {
180  p_index--;
181  walk = walk->m_next;
182  }
183  return walk;
184  }
185  template<typename t_elemwalk,typename t_callback>
186  static void __enumerate_chain(t_elemwalk * p_elem,t_callback & p_callback) {
187  t_elemwalk * walk = p_elem;
188  while(walk != NULL) {
189  p_callback(walk->m_content);
190  walk = walk->m_next;
191  }
192  }
193 
194  template<typename t_source> bool __find(t_elem * & p_elem,const t_source & p_item) const {
195  for(t_elem * walk = m_first; walk != NULL; walk = walk->m_next) {
196  if (walk->m_content == p_item) {
197  p_elem = walk; return true;
198  }
199  }
200  return false;
201  }
202 
203  void __unlink_helper(t_elem * p_elem) throw() {
204  (p_elem->m_prev == NULL ? m_first : p_elem->m_prev->m_next) = p_elem->m_next;
205  (p_elem->m_next == NULL ? m_last : p_elem->m_next->m_prev) = p_elem->m_prev;
206  p_elem->m_next = p_elem->m_prev = NULL;
207  }
208 
209  //workaround for cross-list-relinking case - never actually deletes p_elem
210  t_elem * __unlink_temporary(t_elem * p_elem) throw() {
211  __unlink_helper(p_elem);
212  --m_count; p_elem->__release_temporary();
213  return p_elem;
214  }
215 
216  t_elem * __unlink(t_elem * p_elem) throw() {
217  __unlink_helper(p_elem);
218  --m_count; p_elem->release();
219  return p_elem;
220  }
221  void __on_link(t_elem * p_elem) throw() {
222  p_elem->add_ref(); ++m_count;
223  }
224  t_elem * __link_first(t_elem * p_elem) throw() {
225  __on_link(p_elem);
226  p_elem->m_next = m_first;
227  p_elem->m_prev = NULL;
228  (m_first == NULL ? m_last : m_first->m_prev) = p_elem;
229  m_first = p_elem;
230  return p_elem;
231  }
232  t_elem * __link_last(t_elem * p_elem) throw() {
233  __on_link(p_elem);
234  p_elem->m_prev = m_last;
235  p_elem->m_next = NULL;
236  (m_last == NULL ? m_first : m_last->m_next) = p_elem;
237  m_last = p_elem;
238  return p_elem;
239  }
240  t_elem * __link_next(t_elem * p_prev,t_elem * p_elem) throw() {
241  __on_link(p_elem);
242  p_elem->m_prev = p_prev;
243  p_elem->m_next = p_prev->m_next;
244  (p_prev->m_next != NULL ? p_prev->m_next->m_prev : m_last) = p_elem;
245  p_prev->m_next = p_elem;
246  return p_elem;
247  }
248  t_elem * __link_prev(t_elem * p_next,t_elem * p_elem) throw() {
249  __on_link(p_elem);
250  p_elem->m_next = p_next;
251  p_elem->m_prev = p_next->m_prev;
252  (p_next->m_prev != NULL ? p_next->m_prev->m_next : m_first) = p_elem;
253  p_next->m_prev = p_elem;
254  return p_elem;
255  }
256  t_elem * m_first, * m_last;
258  };
259 
260 
261  template<typename t_item> class traits_t<chain_list_v2_t<t_item> > : public traits_default_movable {};
262 
264  public:
265  enum {
266  constructor_may_fail = false
267  };
268  };
269 
270  template<typename t_item> class traits_t<const_iterator<t_item> > : public traits_t<refcounted_object_ptr_t<_list_node<t_item> > > {};
271 
272  template<typename t_item> class traits_t<iterator<t_item> > : public traits_t<const_iterator<t_item> > {};
273 
274 }//namespace pfc
chain_list_v2_t(const t_self &p_source)
Definition: chain_list_v2.h:35
Base class for list nodes. Implemented by list implementers.
Definition: iterators.h:3
static void __enumerate_chain(t_elemwalk *p_elem, t_callback &p_callback)
::pfc::const_iterator< t_item > const_iterator
Definition: chain_list_v2.h:31
void add_item(const t_source &p_source)
t_elem * __link_prev(t_elem *p_next, t_elem *p_elem)
void set_single(const t_source &p_item)
::pfc::iterator< t_item > iterator
Definition: chain_list_v2.h:30
iterator insert_before(const_iterator const &p_iter)
t_elem * __unlink(t_elem *p_elem)
const_iterator first() const
Definition: chain_list_v2.h:65
t_elem * __link_last(t_elem *p_elem)
t_elem * __link_next(t_elem *p_prev, t_elem *p_elem)
t_elem * __unlink_temporary(t_elem *p_elem)
Differences between chain_list_v2_t<> and old chain_list_t<>: Iterators pointing to removed items as...
Definition: chain_list_v2.h:26
iterator by_index(t_size p_index)
Slow!
iterator insert_after(const_iterator const &p_iter, const t_source &p_source)
iterator insert_before(const_iterator const &p_iter, const t_source &p_source)
iterator find_item(const t_source &p_item)
t_self & operator=(const t_self &p_other)
Definition: chain_list_v2.h:51
t_self * walk(bool forward)
Definition: iterators.h:14
bool is_valid() const
Definition: iterators.h:24
iterator insert_first(const t_source &p_source)
const_iterator find_item(const t_source &p_item) const
t_self & operator>>(t_self &p_other)
bool remove_item(const t_source &p_item)
Definition: chain_list_v2.h:95
void remove_single(const_iterator const &p_iter)
Definition: chain_list_v2.h:68
t_node * _node() const
For internal use / list implementations only! Do not call!
Definition: iterators.h:32
t_size get_count() const
Definition: chain_list_v2.h:61
__chain_list_elem< t_item > t_elem
Definition: chain_list_v2.h:32
iterator insert_last(const t_source &p_source)
size_t t_size
Definition: int_types.h:48
void _link_first(const_iterator const &iter)
Links an object that has been unlinked from another list. Unsafe.
__chain_list_elem< t_item > t_self
Definition: chain_list_v2.h:9
void _set(const t_in &in)
Definition: chain_list_v2.h:43
void enumerate(t_callback &p_callback) const
Definition: chain_list_v2.h:92
const_iterator last() const
Definition: chain_list_v2.h:66
t_self & operator+=(const t_source &p_source)
bool have_item(const t_source &p_item) const
void enumerate(t_callback &p_callback)
Definition: chain_list_v2.h:93
void __on_link(t_elem *p_elem)
_list_node< t_item > t_node
Definition: chain_list_v2.h:6
t_self & operator=(const t_in &in)
Definition: chain_list_v2.h:49
void _link_last(const_iterator const &iter)
Links an object that has been unlinked from another list. Unsafe.
const_iterator by_index(t_size p_index) const
Slow!
static t_elem * _elem(const_iterator const &iter)
t_elem * __link_first(t_elem *p_elem)
bool __find(t_elem *&p_elem, const t_source &p_item) const
void remove_range(const_iterator const &p_from, const_iterator const &p_to)
Definition: chain_list_v2.h:82
t_elem * __by_index(t_size p_index) const
t_self & operator<<(t_self &p_other)
chain_list_v2_t< t_item > t_self
Definition: chain_list_v2.h:29
iterator insert_after(const_iterator const &p_iter)
TEMPLATE_CONSTRUCTOR_FORWARD_FLOOD_WITH_INITIALIZER(__chain_list_elem, t_node,{m_prev=m_next=NULL;})
void _add(const t_in &in)
Definition: chain_list_v2.h:46
void __unlink_helper(t_elem *p_elem)