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.
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.
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.
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.
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.
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.
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
183 }
184
185private:
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
Shared ownership intrusive pointer.
Definition shared_ptr.h:32
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