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 Streaming 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"
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 //! Does not perform allocations.
27 //! Provides O(1) size check, membership check, insertion, and removal.
28 //!
29 //! @tparam T defines object type, it should inherit ListNode.
30 //!
31 //! @tparam OwnershipPolicy defines ownership policy which is used to acquire an
32 //! element ownership when it's added to the list and release ownership when it's
33 //! removed from the list.
34 template <class T, template <class TT> class OwnershipPolicy = RefCountedOwnership>
35 class List : public NonCopyable<> {
36 public:
37  //! Pointer type.
38  //! @remarks
39  //! either raw or smart pointer depending on the ownership policy.
40  typedef typename OwnershipPolicy<T>::Pointer Pointer;
41 
42  //! Initialize empty list.
43  List()
44  : size_(0) {
45  head_.prev = &head_;
46  head_.next = &head_;
47  head_.list = this;
48  }
49 
50  //! Release ownership of containing objects.
51  ~List() {
52  ListNode::ListNodeData* next_data;
53 
54  for (ListNode::ListNodeData* data = head_.next; data != &head_;
55  data = next_data) {
56  roc_panic_if(data == NULL);
57  check_is_member_(data, this);
58 
59  next_data = data->next;
60  data->list = NULL;
61 
62  OwnershipPolicy<T>::release(*container_of_(data));
63  }
64 
65  head_.list = NULL;
66  }
67 
68  //! Get number of elements in list.
69  size_t size() const {
70  return size_;
71  }
72 
73  //! Check if size is zero.
74  bool is_empty() const {
75  return size_ == 0;
76  }
77 
78  //! Check if element belongs to list.
79  bool contains(const T& element) {
80  const ListNode::ListNodeData* data = element.list_node_data();
81  return (data->list == this);
82  }
83 
84  //! Get first list element.
85  //! @returns
86  //! first element or NULL if list is empty.
87  Pointer front() const {
88  if (size_ == 0) {
89  return NULL;
90  }
91  return container_of_(head_.next);
92  }
93 
94  //! Get last list element.
95  //! @returns
96  //! last element or NULL if list is empty.
97  Pointer back() const {
98  if (size_ == 0) {
99  return NULL;
100  }
101  return container_of_(head_.prev);
102  }
103 
104  //! Get list element next to given one.
105  //!
106  //! @returns
107  //! list element following @p element if @p element is not
108  //! last, or NULL otherwise.
109  //!
110  //! @pre
111  //! @p element should be member of this list.
112  Pointer nextof(T& element) const {
113  ListNode::ListNodeData* data = element.list_node_data();
114  check_is_member_(data, this);
115 
116  if (data->next == &head_) {
117  return NULL;
118  }
119  return container_of_(data->next);
120  }
121 
122  //! Prepend element to list.
123  //!
124  //! @remarks
125  //! - prepends @p element to list
126  //! - acquires ownership of @p element
127  //!
128  //! @pre
129  //! @p element should not be member of any list.
130  void push_front(T& element) {
131  if (size_ == 0) {
132  insert_(element, NULL);
133  } else {
134  insert_(element, container_of_(head_.next));
135  }
136  }
137 
138  //! Append element to list.
139  //!
140  //! @remarks
141  //! - appends @p element to list
142  //! - acquires ownership of @p element
143  //!
144  //! @pre
145  //! @p element should not be member of any list.
146  void push_back(T& element) {
147  insert_(element, NULL);
148  }
149 
150  //! Insert element into list.
151  //!
152  //! @remarks
153  //! - inserts @p element before @p before
154  //! - acquires ownership of @p element
155  //!
156  //! @pre
157  //! @p element should not be member of any list.
158  //! @p before should be member of this list or NULL.
159  void insert_before(T& element, T& before) {
160  insert_(element, &before);
161  }
162 
163  //! Remove element from list.
164  //!
165  //! @remarks
166  //! - removes @p element from list
167  //! - releases ownership of @p element
168  //!
169  //! @pre
170  //! @p element should be member of this list.
171  void remove(T& element) {
172  ListNode::ListNodeData* data = element.list_node_data();
173  check_is_member_(data, this);
174 
175  data->prev->next = data->next;
176  data->next->prev = data->prev;
177 
178  data->list = NULL;
179 
180  size_--;
181 
182  OwnershipPolicy<T>::release(element);
183  }
184 
185 private:
186  static T* container_of_(ListNode::ListNodeData* data) {
187  return static_cast<T*>(data->container_of());
188  }
189 
190  static void check_is_member_(const ListNode::ListNodeData* data, const List* list) {
191  if (data->list != list) {
192  roc_panic("list: element is member of wrong list: expected %p, got %p",
193  (const void*)list, (const void*)data->list);
194  }
195  }
196 
197  void insert_(T& element, T* before) {
198  ListNode::ListNodeData* data_new = element.list_node_data();
199  check_is_member_(data_new, NULL);
200 
201  ListNode::ListNodeData* data_before;
202  if (before != NULL) {
203  data_before = before->list_node_data();
204  check_is_member_(data_before, this);
205  } else {
206  data_before = &head_;
207  }
208 
209  data_new->next = data_before;
210  data_new->prev = data_before->prev;
211 
212  data_before->prev->next = data_new;
213  data_before->prev = data_new;
214 
215  data_new->list = this;
216 
217  size_++;
218 
219  OwnershipPolicy<T>::acquire(element);
220  }
221 
222  ListNode::ListNodeData head_;
223  size_t size_;
224 };
225 
226 } // namespace core
227 } // namespace roc
228 
229 #endif // ROC_CORE_LIST_H_
Intrusive doubly-linked list.
Definition: list.h:35
void insert_before(T &element, T &before)
Insert element into list.
Definition: list.h:159
void remove(T &element)
Remove element from list.
Definition: list.h:171
List()
Initialize empty list.
Definition: list.h:43
size_t size() const
Get number of elements in list.
Definition: list.h:69
OwnershipPolicy< T >::Pointer Pointer
Pointer type.
Definition: list.h:40
Pointer nextof(T &element) const
Get list element next to given one.
Definition: list.h:112
Pointer back() const
Get last list element.
Definition: list.h:97
Pointer front() const
Get first list element.
Definition: list.h:87
~List()
Release ownership of containing objects.
Definition: list.h:51
void push_front(T &element)
Prepend element to list.
Definition: list.h:130
bool is_empty() const
Check if size is zero.
Definition: list.h:74
void push_back(T &element)
Append element to list.
Definition: list.h:146
bool contains(const T &element)
Check if element belongs to list.
Definition: list.h:79
Base class for non-copyable objects.
Definition: noncopyable.h:23
Linked list node.
Root namespace.
Non-copyable object.
Ownership policies.
Panic.
#define roc_panic_if(x)
Panic if condition is true.
Definition: panic.h:26
#define roc_panic(...)
Print error message and terminate program gracefully.
Definition: panic.h:50
Commonly used types and functions.
ListNodeData * next
Next list element.
Definition: list_node.h:34
ListNodeData * prev
Previous list element.
Definition: list_node.h:31
void * list
The list this node is member of.
Definition: list_node.h:39
ListNode * container_of()
Get ListNode object that contains this ListData object.
Definition: list_node.h:48