Roc Toolkit internal modules
Roc Toolkit: real-time audio streaming
Loading...
Searching...
No Matches
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"
18#include "roc_core/panic.h"
19#include "roc_core/stddefs.h"
20
21namespace roc {
22namespace 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.
34template <class T, template <class TT> class OwnershipPolicy = RefCountedOwnership>
35class List : public NonCopyable<> {
36public:
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.
44 : size_(0) {
45 head_.prev = &head_;
46 head_.next = &head_;
47 head_.list = this;
48 }
49
50 //! Release ownership of containing objects.
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 element belongs to list.
74 bool contains(const T& element) {
75 const ListNode::ListNodeData* data = element.list_node_data();
76 return (data->list == this);
77 }
78
79 //! Get first list element.
80 //! @returns
81 //! first element or NULL if list is empty.
82 Pointer front() const {
83 if (size_ == 0) {
84 return NULL;
85 }
86 return container_of_(head_.next);
87 }
88
89 //! Get last list element.
90 //! @returns
91 //! last element or NULL if list is empty.
92 Pointer back() const {
93 if (size_ == 0) {
94 return NULL;
95 }
96 return container_of_(head_.prev);
97 }
98
99 //! Get list element next to given one.
100 //!
101 //! @returns
102 //! list element following @p element if @p element is not
103 //! last, or NULL otherwise.
104 //!
105 //! @pre
106 //! @p element should be member of this list.
107 Pointer nextof(T& element) const {
108 ListNode::ListNodeData* data = element.list_node_data();
109 check_is_member_(data, this);
110
111 if (data->next == &head_) {
112 return NULL;
113 }
114 return container_of_(data->next);
115 }
116
117 //! Prepend element to list.
118 //!
119 //! @remarks
120 //! - prepends @p element to list
121 //! - acquires ownership of @p element
122 //!
123 //! @pre
124 //! @p element should not be member of any list.
125 void push_front(T& element) {
126 if (size_ == 0) {
127 insert_(element, NULL);
128 } else {
129 insert_(element, container_of_(head_.next));
130 }
131 }
132
133 //! Append element to list.
134 //!
135 //! @remarks
136 //! - appends @p element to list
137 //! - acquires ownership of @p element
138 //!
139 //! @pre
140 //! @p element should not be member of any list.
141 void push_back(T& element) {
142 insert_(element, NULL);
143 }
144
145 //! Insert element into list.
146 //!
147 //! @remarks
148 //! - inserts @p element before @p before
149 //! - acquires ownership of @p element
150 //!
151 //! @pre
152 //! @p element should not be member of any list.
153 //! @p before should be member of this list or NULL.
154 void insert_before(T& element, T& before) {
155 insert_(element, &before);
156 }
157
158 //! Remove element from list.
159 //!
160 //! @remarks
161 //! - removes @p element from list
162 //! - releases ownership of @p element
163 //!
164 //! @pre
165 //! @p element should be member of this list.
166 void remove(T& element) {
167 ListNode::ListNodeData* data = element.list_node_data();
168 check_is_member_(data, this);
169
170 data->prev->next = data->next;
171 data->next->prev = data->prev;
172
173 data->list = NULL;
174
175 size_--;
176
177 OwnershipPolicy<T>::release(element);
178 }
179
180private:
181 static inline T* container_of_(ListNode::ListNodeData* data) {
182 return static_cast<T*>(data->container_of());
183 }
184
185 static void check_is_member_(const ListNode::ListNodeData* data, const List* list) {
186 if (data->list != list) {
187 roc_panic("list element is member of wrong list: expected %p, got %p",
188 (const void*)list, (const void*)data->list);
189 }
190 }
191
192 void insert_(T& element, T* before) {
193 ListNode::ListNodeData* data_new = element.list_node_data();
194 check_is_member_(data_new, NULL);
195
196 ListNode::ListNodeData* data_before;
197 if (before != NULL) {
198 data_before = before->list_node_data();
199 check_is_member_(data_before, this);
200 } else {
201 data_before = &head_;
202 }
203
204 data_new->next = data_before;
205 data_new->prev = data_before->prev;
206
207 data_before->prev->next = data_new;
208 data_before->prev = data_new;
209
210 data_new->list = this;
211
212 size_++;
213
214 OwnershipPolicy<T>::acquire(element);
215 }
216
217 ListNode::ListNodeData head_;
218 size_t size_;
219};
220
221} // namespace core
222} // namespace roc
223
224#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:154
void remove(T &element)
Remove element from list.
Definition list.h:166
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:107
Pointer back() const
Get last list element.
Definition list.h:92
Pointer front() const
Get first list element.
Definition list.h:82
~List()
Release ownership of containing objects.
Definition list.h:51
void push_front(T &element)
Prepend element to list.
Definition list.h:125
void push_back(T &element)
Append element to list.
Definition list.h:141
bool contains(const T &element)
Check if element belongs to list.
Definition list.h:74
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.
ListNode * container_of()
Get ListNode object that contains this ListData object.
Definition list_node.h:48
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