Roc Toolkit internal modules
Roc Toolkit: real-time audio streaming
list.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2015 Roc authors
3  *
4  * This Source Code Form is subject to the terms of the Mozilla Public
5  * License, v. 2.0. If a copy of the MPL was not distributed with this
6  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7  */
8 
9 //! @file roc_core/list.h
10 //! @brief Intrusive doubly-linked list.
11 
12 #ifndef ROC_CORE_LIST_H_
13 #define ROC_CORE_LIST_H_
14 
15 #include "roc_core/list_node.h"
16 #include "roc_core/noncopyable.h"
17 #include "roc_core/ownership.h"
18 #include "roc_core/panic.h"
19 #include "roc_core/stddefs.h"
20 
21 namespace roc {
22 namespace core {
23 
24 //! Intrusive doubly-linked list.
25 //!
26 //! @tparam T defines object type, it should inherit ListNode.
27 //! @tparam Ownership defines ownership policy which is used to acquire an element
28 //! ownership
29 //! when it's added to the list and release ownership when it's removed from the list
30 template <class T, template <class TT> class Ownership = RefCntOwnership>
31 class List : public NonCopyable<> {
32 public:
33  //! Pointer type.
34  //! @remarks
35  //! either raw or smart pointer depending on the ownership policy.
36  typedef typename Ownership<T>::Pointer Pointer;
37 
38  //! Initialize empty list.
39  List()
40  : size_(0) {
41  head_.prev = &head_;
42  head_.next = &head_;
43  head_.list = this;
44  }
45 
46  //! Release ownership of containing objects.
47  ~List() {
48  ListNode::ListNodeData* next_data;
49 
50  for (ListNode::ListNodeData* data = head_.next; data != &head_;
51  data = next_data) {
52  roc_panic_if(data == NULL);
53  check_is_member_(data, this);
54 
55  next_data = data->next;
56  data->list = NULL;
57 
58  Ownership<T>::release(*container_of_(data));
59  }
60 
61  head_.list = NULL;
62  }
63 
64  //! Get number of elements in list.
65  size_t size() const {
66  return size_;
67  }
68 
69  //! Get first list element.
70  //! @returns
71  //! first element or NULL if list is empty.
72  Pointer front() const {
73  if (size_ == 0) {
74  return NULL;
75  }
76  return container_of_(head_.next);
77  }
78 
79  //! Get last list element.
80  //! @returns
81  //! last element or NULL if list is empty.
82  Pointer back() const {
83  if (size_ == 0) {
84  return NULL;
85  }
86  return container_of_(head_.prev);
87  }
88 
89  //! Get list element next to given one.
90  //!
91  //! @returns
92  //! list element following @p element if @p element is not
93  //! last, or NULL otherwise.
94  //!
95  //! @pre
96  //! @p element should be member of this list.
97  Pointer nextof(T& element) const {
98  ListNode::ListNodeData* data = element.list_node_data();
99  check_is_member_(data, this);
100 
101  if (data->next == &head_) {
102  return NULL;
103  }
104  return container_of_(data->next);
105  }
106 
107  //! Prepend element to list.
108  //!
109  //! @remarks
110  //! - prepends @p element to list
111  //! - acquires ownership of @p element
112  //!
113  //! @pre
114  //! @p element should not be member of any list.
115  void push_front(T& element) {
116  if (size_ == 0) {
117  insert_(element, NULL);
118  } else {
119  insert_(element, container_of_(head_.next));
120  }
121  }
122 
123  //! Append element to list.
124  //!
125  //! @remarks
126  //! - appends @p element to list
127  //! - acquires ownership of @p element
128  //!
129  //! @pre
130  //! @p element should not be member of any list.
131  void push_back(T& element) {
132  insert_(element, NULL);
133  }
134 
135  //! Insert element into list.
136  //!
137  //! @remarks
138  //! - inserts @p element before @p before
139  //! - acquires ownership of @p element
140  //!
141  //! @pre
142  //! @p element should not be member of any list.
143  //! @p before should be member of this list or NULL.
144  void insert_before(T& element, T& before) {
145  insert_(element, &before);
146  }
147 
148  //! Remove element from list.
149  //!
150  //! @remarks
151  //! - removes @p element from list
152  //! - releases ownership of @p element
153  //!
154  //! @pre
155  //! @p element should be member of this list.
156  void remove(T& element) {
157  ListNode::ListNodeData* data = element.list_node_data();
158  check_is_member_(data, this);
159 
160  data->prev->next = data->next;
161  data->next->prev = data->prev;
162 
163  data->list = NULL;
164 
165  size_--;
166 
167  Ownership<T>::release(element);
168  }
169 
170 private:
171  static inline T* container_of_(ListNode::ListNodeData* data) {
172  return static_cast<T*>(data->container_of());
173  }
174 
175  static void check_is_member_(const ListNode::ListNodeData* data, const List* list) {
176  if (data->list != list) {
177  roc_panic("list element is member of wrong list: expected %p, got %p",
178  (const void*)list, (const void*)data->list);
179  }
180  }
181 
182  void insert_(T& element, T* before) {
183  ListNode::ListNodeData* data_new = element.list_node_data();
184  check_is_member_(data_new, NULL);
185 
186  ListNode::ListNodeData* data_before;
187  if (before != NULL) {
188  data_before = before->list_node_data();
189  check_is_member_(data_before, this);
190  } else {
191  data_before = &head_;
192  }
193 
194  data_new->next = data_before;
195  data_new->prev = data_before->prev;
196 
197  data_before->prev->next = data_new;
198  data_before->prev = data_new;
199 
200  data_new->list = this;
201 
202  size_++;
203 
204  Ownership<T>::acquire(element);
205  }
206 
208  size_t size_;
209 };
210 
211 } // namespace core
212 } // namespace roc
213 
214 #endif // ROC_CORE_LIST_H_
List()
Initialize empty list.
Definition: list.h:39
Pointer front() const
Get first list element.
Definition: list.h:72
void * list
The list this node is member of.
Definition: list_node.h:39
ListNodeData * prev
Previous list element.
Definition: list_node.h:31
#define roc_panic_if(x)
Panic if condition is true.
Definition: panic.h:26
ListNode * container_of()
Get ListNode object that contains this ListData object.
Definition: list_node.h:48
Ownership policies.
Root namespace.
Intrusive doubly-linked list.
Definition: list.h:31
Linked list node.
~List()
Release ownership of containing objects.
Definition: list.h:47
ListNodeData * next
Next list element.
Definition: list_node.h:34
size_t size() const
Get number of elements in list.
Definition: list.h:65
Commonly used types and functions.
Ownership< T >::Pointer Pointer
Pointer type.
Definition: list.h:36
#define roc_panic(...)
Print error message and terminate program gracefully.
Definition: panic.h:42
Pointer back() const
Get last list element.
Definition: list.h:82
Base class for non-copyable objects.
Definition: noncopyable.h:23
Panic function.
void insert_before(T &element, T &before)
Insert element into list.
Definition: list.h:144
Pointer nextof(T &element) const
Get list element next to given one.
Definition: list.h:97
Non-copyable object.
void push_front(T &element)
Prepend element to list.
Definition: list.h:115
void push_back(T &element)
Append element to list.
Definition: list.h:131