libcsdbg  1.28
C++ exception (and generic) stack trace debug library
chain.hpp
Go to the documentation of this file.
1 #ifndef _CSDBG_CHAIN
2 #define _CSDBG_CHAIN 1
3 
10 #include "./node.hpp"
11 #include "./exception.hpp"
12 
13 namespace csdbg {
14 
32 template <class T>
33 class chain: virtual public object
34 {
35 protected:
36 
37  /* Protected variables */
38 
46  /* Protected generic methods */
47 
48  virtual node<T>* node_at(u32) const;
49 
50  virtual node<T>* node_with(const T*) const;
51 
52  virtual node<T>* detach_node(u32);
53 
54 public:
55 
56  /* Constructors, copy constructors and destructor */
57 
58  chain();
59 
60  chain(const chain&);
61 
62  virtual ~chain();
63 
64  virtual chain* clone() const;
65 
66 
67  /* Accessor methods */
68 
69  virtual u32 size() const;
70 
71 
72  /* Operator overloading methods */
73 
74  virtual chain& operator=(const chain&);
75 
76  virtual T* operator[](u32) const;
77 
78 
79  /* Generic methods */
80 
81  virtual chain& add(T*);
82 
83  virtual chain& remove(u32);
84 
85  virtual chain& clear();
86 
87  virtual T* at(u32) const;
88 
89  virtual T* detach(u32);
90 
91  virtual chain& foreach(void (*)(u32, T*)) const;
92 };
93 
94 
104 template <class T>
106 {
107  if ( unlikely(i >= m_size) )
108  throw exception("offset out of chain bounds (%d >= %d)", i, m_size);
109 
110  /* Select traversal direction */
111  node<T> *cur = m_head;
112  i32 j = i, mid = m_size / 2;
113  if (j >= mid) {
114  j = m_size - i - 1;
115  cur = m_tail;
116  }
117 
118  node<T> *prev = NULL, *next;
119  while ( likely(j-- > 0) ) {
120  next = cur->link(prev);
121  prev = cur;
122  cur = next;
123  }
124 
125  return cur;
126 }
127 
128 
136 template <class T>
137 node<T>* chain<T>::node_with(const T *d) const
138 {
139  __D_ASSERT(d != NULL);
140  if ( unlikely(d == NULL) )
141  return NULL;
142 
143  node<T> *cur = m_head, *prev = NULL, *next;
144  while ( likely(cur != NULL) ) {
145  if ( unlikely(cur->m_data == d) )
146  return cur;
147 
148  next = cur->link(prev);
149  prev = cur;
150  cur = next;
151  }
152 
153  return NULL;
154 }
155 
156 
166 template <class T>
168 {
169  if ( unlikely(i >= m_size) )
170  throw exception("offset out of chain bounds (%d >= %d)", i, m_size);
171 
172  node<T> *cur = m_head, *prev = NULL, *next;
173  while ( likely(i-- > 0) ) {
174  next = cur->link(prev);
175  prev = cur;
176  cur = next;
177  }
178 
179  next = cur->link(prev);
180 
181  /* If it's the first in the chain */
182  if ( unlikely(cur == m_head) ) {
183  m_head = next;
184 
185  /* If the chain is left empty */
186  if ( unlikely(m_head == NULL) )
187  m_tail = NULL;
188  else
189  m_head->unlink_from(cur);
190  }
191 
192  /* If it's the last in the chain */
193  else if ( unlikely(cur == m_tail) ) {
194  m_tail = prev;
195  m_tail->unlink_from(cur);
196  }
197 
198  /* Relink previous and next nodes */
199  else {
200  prev->unlink_from(cur);
201  prev->link_to(next);
202 
203  next->unlink_from(cur);
204  next->link_to(prev);
205  }
206 
207  m_size--;
208  return cur;
209 }
210 
211 
215 template <class T>
217 m_head(NULL),
218 m_tail(NULL),
219 m_size(0)
220 {
221 }
222 
223 
231 template <class T>
232 inline chain<T>::chain(const chain &src)
233 try:
234 m_head(NULL),
235 m_tail(NULL),
236 m_size(0)
237 {
238  *this = src;
239 }
240 
241 catch (...) {
242  clear();
243 }
244 
245 
249 template <class T>
251 {
252  clear();
253 }
254 
255 
263 template <class T>
264 inline chain<T>* chain<T>::clone() const
265 {
266  return new chain(*this);
267 }
268 
269 
275 template <class T>
276 inline u32 chain<T>::size() const
277 {
278  return m_size;
279 }
280 
281 
295 template <class T>
297 {
298  if ( unlikely(this == &rval) )
299  return *this;
300 
301  /* Check if the chains overlap and detach shared data pointers */
302  node<T> *cur = m_head, *prev = NULL, *next;
303  while ( likely(cur != NULL) ) {
304  if ( unlikely(rval.node_with(cur->m_data) != NULL) )
305  cur->detach();
306 
307  next = cur->link(prev);
308  prev = cur;
309  cur = next;
310  }
311 
312  clear();
313  cur = rval.m_head;
314  prev = NULL;
315  while ( likely(cur != NULL) ) {
316  T *copy = NULL;
317  try {
318  copy = new T(*cur->m_data);
319  add(copy);
320  }
321 
322  catch (...) {
323  delete copy;
324  throw;
325  }
326 
327  next = cur->link(prev);
328  prev = cur;
329  cur = next;
330  }
331 
332  return *this;
333 }
334 
335 
345 template <class T>
346 inline T* chain<T>::operator[](u32 i) const
347 {
348  return at(i);
349 }
350 
351 
362 template <class T>
364 {
365  if ( unlikely(d == NULL) )
366  throw exception("invalid argument: d (=%p)", d);
367 
368  /* If the data pointer already exists in the chain */
369  if ( unlikely(node_with(d) != NULL) )
370  throw exception("chain @ %p already has a node with data @ %p", this, d);
371 
372  node<T> *n = new node<T>(d);
373 
374  /* Add the node to the chain tail */
375  if ( likely(m_head != NULL) ) {
376  n->m_link = m_tail;
377  m_tail->link_to(n);
378  m_tail = n;
379  }
380 
381  /* If it is the first node */
382  else
383  m_head = m_tail = n;
384 
385  m_size++;
386  return *this;
387 }
388 
389 
399 template <class T>
401 {
402  delete detach_node(i);
403  return *this;
404 }
405 
406 
412 template <class T>
414 {
415  node<T> *cur = m_head, *prev = NULL, *next;
416  while ( likely(cur != NULL) ) {
417  next = cur->link(prev);
418  prev = cur;
419 
420  delete cur;
421  cur = next;
422  }
423 
424  m_head = m_tail = NULL;
425  m_size = 0;
426  return *this;
427 }
428 
429 
439 template <class T>
440 inline T* chain<T>::at(u32 i) const
441 {
442  return node_at(i)->m_data;
443 }
444 
445 
455 template <class T>
456 inline T* chain<T>::detach(u32 i)
457 {
458  node<T> *n = detach_node(i);
459  T *d = n->detach();
460  delete n;
461  return d;
462 }
463 
464 
472 template <class T>
473 chain<T>& chain<T>::foreach(void (*pfunc)(u32, T*)) const
474 {
475  __D_ASSERT(pfunc != NULL);
476  if ( unlikely(pfunc == NULL) )
477  return const_cast<chain<T>&> (*this);
478 
479  u32 i = 0;
480  node<T> *cur = m_head, *prev = NULL, *next;
481  while ( likely(cur != NULL) ) {
482  pfunc(i++, cur->m_data);
483 
484  next = cur->link(prev);
485  prev = cur;
486  cur = next;
487  }
488 
489  return const_cast<chain<T>&> (*this);
490 }
491 
492 }
493 
494 #endif
495 
This abstract class serves as the root of the class hierarchy tree.
Definition: object.hpp:17
virtual T * at(u32) const
Get the node data pointer at a chain offset.
Definition: chain.hpp:440
virtual node< T > * detach_node(u32)
Detach the node at a chain offset.
Definition: chain.hpp:167
u32 m_size
Node count.
Definition: chain.hpp:43
T * m_data
Node data.
Definition: node.hpp:44
virtual chain & clear()
Empty the chain.
Definition: chain.hpp:413
virtual u32 size() const
Get the chain size (node count)
Definition: chain.hpp:276
Lightweight, templated, doubly-linked list (using XOR linking)
Definition: chain.hpp:33
virtual T * detach(u32)
Detach the node at a chain offset.
Definition: chain.hpp:456
virtual node * link(const node *=NULL) const
Get the next node (using direct or XOR linking)
Definition: node.hpp:156
chain()
Object default constructor.
Definition: chain.hpp:216
#define likely(expr)
Offer a hint (positive) to the pipeline branch predictor.
Definition: config.hpp:344
virtual ~chain()
Object destructor.
Definition: chain.hpp:250
node< T > * m_tail
Chain tail.
Definition: chain.hpp:41
node< T > * m_head
Chain head.
Definition: chain.hpp:39
virtual chain & remove(u32)
Dispose the node (and its data) at a chain offset.
Definition: chain.hpp:400
virtual node< T > * node_at(u32) const
Get the node at a chain offset.
Definition: chain.hpp:105
A node in a templated chain (doubly-linked list) or stack (singly-linked LIFO queue) ...
Definition: node.hpp:36
virtual node & unlink_from(const node *)
Unlink from a node (for XOR linking)
Definition: node.hpp:187
virtual T * detach()
Detach the data pointer from the node.
Definition: node.hpp:200
virtual chain & add(T *)
Add a node to the chain.
Definition: chain.hpp:363
virtual node & link_to(const node *)
Link with a node (for XOR linking)
Definition: node.hpp:172
Class csdbg::exception definition.
unsigned int u32
32-bit unsigned integer
Definition: config.hpp:102
virtual chain & operator=(const chain &)
Assignment operator.
Definition: chain.hpp:296
virtual T * operator[](u32) const
Subscript operator.
Definition: chain.hpp:346
int i32
32-bit signed integer
Definition: config.hpp:82
Class csdbg::node definition and method implementation.
virtual chain & foreach(void(*)(u32, T *)) const
Traverse the chain with a callback for each node.
Definition: chain.hpp:473
This class is a throwable with a textual description of an error.
Definition: exception.hpp:26
#define unlikely(expr)
Offer a hint (negative) to the pipeline branch predictor.
Definition: config.hpp:349
node * m_link
Next node link (direct or XOR link)
Definition: node.hpp:42
virtual node< T > * node_with(const T *) const
Get the node with m_data == d.
Definition: chain.hpp:137
virtual chain * clone() const
Object virtual copy constructor.
Definition: chain.hpp:264
#define __D_ASSERT(x)
Assertion macro.
Definition: config.hpp:268