Lumiera  0.pre.03
»edit your freedom«
linked-elements.hpp
Go to the documentation of this file.
1 /*
2  LINKED-ELEMENTS.hpp - configurable intrusive single linked list template
3 
4  Copyright (C) Lumiera.org
5  2012, Hermann Vosseler <Ichthyostega@web.de>
6 
7  This program is free software; you can redistribute it and/or
8  modify it under the terms of the GNU General Public License as
9  published by the Free Software Foundation; either version 2 of
10  the License, or (at your option) any later version.
11 
12  This program is distributed in the hope that it will be useful,
13  but WITHOUT ANY WARRANTY; without even the implied warranty of
14  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  GNU General Public License for more details.
16 
17  You should have received a copy of the GNU General Public License
18  along with this program; if not, write to the Free Software
19  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
20 
21 */
22 
59 #ifndef LIB_LINKED_ELEMENTS_H
60 #define LIB_LINKED_ELEMENTS_H
61 
62 
63 #include "lib/error.hpp"
64 #include "lib/nocopy.hpp"
65 #include "lib/iter-adapter.hpp"
66 #include "lib/util.hpp"
67 
68 #include <utility>
69 
70 
71 namespace lib {
72 
73  namespace error = lumiera::error;
74  using error::LERR_(INDEX_BOUNDS);
75  using util::unConst;
76 
77 
78  namespace linked_elements {
79 
88  {
89  typedef void* CustomAllocator;
90 
94  template<class X>
95  void
96  destroy (X* elm)
97  {
98  delete elm;
99  }
100 
101 
104  template<class TY, typename...ARGS>
105  TY&
106  create (ARGS&& ...args)
107  {
108  return *new TY (std::forward<ARGS> (args)...);
109  }
110  };
111 
112 
113 
114 
115 
116 
126  struct NoOwnership
127  {
128  typedef void* CustomAllocator;
129 
133  void
134  destroy (void*)
135  {
136  /* does nothing */
137  }
138 
139  template<class TY, typename...ARGS>
140  TY&
141  create (ARGS&&...)
142  {
143  static_assert ("NoOwnership allocation strategy can not allocate elements");
144  } // ... you'll have to do that yourself (that's the whole point of using this strategy)
145  };
146 
147 
148 
149 
150 
151 #ifdef LIB_ALLOCATION_CLUSTER_H
152 
162  struct UseAllocationCluster
163  {
164  typedef AllocationCluster& CustomAllocator;
165 
166  CustomAllocator cluster_;
167 
168 
169  explicit
170  UseAllocationCluster (CustomAllocator clu)
171  : cluster_(clu)
172  { }
173 
174 
181  void
182  destroy (void*)
183  {
184  /* does nothing */
185  }
186 
187 
188  template<class TY, typename...ARGS>
189  TY&
190  create (ARGS&& ...args)
191  {
192  return cluster_.create<TY> (std::forward<ARGS> (args)...);
193  }
194  };
195 
196 #endif //(End)if lib/allocation-cluster.hpp was included
197 
198  }//(END)namespace linked_elements
199 
200 
201 
202 
203 
204 
205 
206 
207 
208 
220  template
221  < class N
223  >
225  : ALO
226  {
227  N* head_;
228 
229 
230  public:
231 
232  ~LinkedElements()
233  {
234  clear();
235  }
236 
238  : head_{nullptr}
239  { }
240 
241  LinkedElements (LinkedElements const&) = default;
243  : head_{rr.head_}
244  { // possibly transfer ownership
245  rr.head_ = nullptr;
246  }
247 
252  explicit
253  LinkedElements (typename ALO::CustomAllocator allo)
254  : ALO{allo}
255  , head_{nullptr}
256  { }
257 
264  template<class IT>
266  : head_{nullptr}
267  {
268  try {
269  pushAll (std::forward<IT> (elements));
270  }
271  catch(...)
272  {
273  WARN (progress, "Failure while populating LinkedElements list. "
274  "All elements will be discarded");
275  clear();
276  throw;
277  } }
278 
279 
280 
282  void
284  {
285  while (head_)
286  {
287  N* elm = head_;
288  head_ = head_->next;
289  try {
290  ALO::destroy(elm);
291  }
292  ERROR_LOG_AND_IGNORE (progress, "Clean-up of element in LinkedElements list")
293  }
294  }
295 
296 
301  template<class IT>
302  void
304  {
305  for ( ; elements; ++elements )
306  push (*elements);
307  }
308 
309 
310 
311 
316  template<typename TY>
317  TY&
318  push (TY& elm)
319  {
320  elm.next = head_;
321  head_ = &elm;
322  return elm;
323  }
324 
325 
326 // template< class TY =N>
327 // TY& //_________________________________________
328 // emplace () ///< add object of type TY, using 0-arg ctor
329 // {
330 // return push (ALO::template create<TY>());
331 // }
332 
334  template<class TY =N, typename...ARGS>
335  TY&
336  emplace (ARGS&& ...args)
337  {
338  return push (ALO::template create<TY> (std::forward<ARGS> (args)...));
339  }
340 
341 
342 
351  {
352  if (not empty())
353  {
354  N* p = head_->next;
355  head_->next = nullptr;
356  while (p)
357  {
358  N& n = *p;
359  p = p->next;
360  push (n);
361  } }
362  return *this;
363  }
364 
365 
366 
367 
368  /* === Element access and iteration === */
369 
370  N&
371  operator[] (size_t index) const
372  {
373  N* p = head_;
374  while (p and index)
375  {
376  p = p->next;
377  --index;
378  }
379 
380  if (!p or index)
381  throw error::Logic ("Attempt to access element beyond the end of LinkedElements list"
382  , LERR_(INDEX_BOUNDS));
383  else
384  return *p;
385  }
386 
387 
389  N&
390  top() const
391  {
392  REQUIRE (head_, "NIL");
393  return *(unConst(this)->head_);
394  }
395 
396 
398  size_t
399  size() const
400  {
401  uint count=0;
402  N* p = head_;
403  while (p)
404  {
405  p = p->next;
406  ++count;
407  }
408  return count;
409  }
410 
411 
412  bool
413  empty() const
414  {
415  return !head_;
416  }
417 
418  private:
426  {
427  N* node;
428 
429  IterationState (N* p =nullptr)
430  : node{p}
431  { }
432 
433  /* ==== internal callback API for the iterator ==== */
434 
440  void
442  {
443  node = node->next;
444  }
445 
447  bool
448  checkPoint() const
449  {
450  return bool(node);
451  }
452 
453  N&
454  yield() const
455  {
456  REQUIRE (node);
457  return * unConst(this)->node;
458  }
459 
460  friend bool
461  operator== (IterationState const& il, IterationState const& ir)
462  {
463  return il.node == ir.node;
464  }
465  };
466 
467  public:
470 
471 
472  iterator begin() { return iterator (head_); }
473  const_iterator begin() const { return const_iterator (head_); }
474  iterator end () { return iterator(); }
475  const_iterator end () const { return const_iterator(); }
476 
477  };
478 
479 
480 
481 
482 } // namespace lib
483 #endif /*LIB_LINKED_ELEMENTS_H*/
LinkedElements & reverse()
Mutate the complete list to change the order of elements.
IterQueue< T > elements(T const &elm)
convenience free function to build an iterable sequence
Definition: iter-stack.hpp:301
TY & emplace(ARGS &&...args)
prepend object of type TY, forwarding ctor args
Iteration is just following the single linked list.
void pushAll(IT elements)
convenience shortcut to add all the elements yielded by the given Lumiera Forward Iterator ...
#define ERROR_LOG_AND_IGNORE(_FLAG_, _OP_DESCR_)
convenience shortcut for a sequence of catch blocks just logging and consuming an error...
Definition: error.hpp:272
Intrusive single linked list, possibly taking ownership of node elements.
Helper template(s) for creating Lumiera Forward Iterators.
Types marked with this mix-in may be moved but not copied.
Definition: nocopy.hpp:58
bool operator==(PtrDerefIter< I1 > const &il, PtrDerefIter< I2 > const &ir)
Supporting equality comparisons...
TY & create(ARGS &&...args)
this policy creates new elements simply by heap allocation
LinkedElements(IT &&elements)
creating a LinkedElements list in RAII-style:
Implementation namespace for support and library code.
Derived specific exceptions within Lumiera&#39;s exception hierarchy.
Definition: error.hpp:196
void iterNext()
Iteration-logic: switch to next position.
Mix-Ins to allow or prohibit various degrees of copying and cloning.
Another Lumiera Forward Iterator building block, based on incorporating a state type right into the i...
Tiny helper functions and shortcuts to be used everywhere Consider this header to be effectively incl...
TY & push(TY &elm)
accept the given element and prepend it to the list of elements; depending on the allocation policy...
< allocation policies for the LinkedElements list container
Lumiera error handling (C++ interface).
A pile of objects sharing common allocation and lifecycle.
bool checkPoint() const
Iteration-logic: detect iteration end.
void destroy(void *)
this policy doesn&#39;t take ownership and thus never discards anything
LinkedElements(typename ALO::CustomAllocator allo)
void destroy(X *elm)
this policy discards elements by deallocating them from heap
Policy for LinkedElements: never create or destroy any elements, only allow to add already existing n...