intrusive_list.h
Go to the documentation of this file.
/*
Copyright (c) 2005-2020 Intel Corporation
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
#ifndef _TBB_intrusive_list_H
#define _TBB_intrusive_list_H
#include "tbb/tbb_stddef.h"
#include "tbb/internal/_template_helpers.h"
namespace tbb {
namespace internal {
struct intrusive_list_node {
intrusive_list_node *my_prev_node,
*my_next_node;
#if TBB_USE_ASSERT
intrusive_list_node () { my_prev_node = my_next_node = this; }
#endif /* TBB_USE_ASSERT */
};
template <class List, class T>
class intrusive_list_base {
intrusive_list_node my_head;
size_t my_size;
static intrusive_list_node& node ( T& item ) { return List::node(item); }
static T& item ( intrusive_list_node* node ) { return List::item(node); }
static const T& item( const intrusive_list_node* node ) { return List::item(node); }
template <typename DereferenceType>
class iterator_impl {
__TBB_STATIC_ASSERT((tbb::internal::is_same_type<DereferenceType, T>::value ||
tbb::internal::is_same_type<DereferenceType, const T>::value),
"Incorrect DereferenceType in iterator_impl");
typedef typename tbb::internal::conditional<tbb::internal::is_same_type<DereferenceType, T>::value,
intrusive_list_node*,
const intrusive_list_node*>::type pointer_type;
public:
iterator_impl() : my_pos(NULL) {}
iterator_impl( pointer_type pos ) : my_pos(pos) {}
iterator_impl& operator=( const iterator_impl& other ) {
if (this != &other) {
my_pos = other.my_pos;
}
return *this;
}
iterator_impl& operator=( const T& val ) {
my_pos = &node(val);
return *this;
}
iterator_impl& operator++() {
my_pos = my_pos->my_next_node;
return *this;
}
iterator_impl operator++( int ) {
iterator_impl it(*this);
++*this;
return it;
}
iterator_impl& operator--() {
my_pos = my_pos->my_prev_node;
return *this;
}
iterator_impl operator--( int ) {
iterator_impl it(*this);
--*this;
return it;
}
bool operator==( const iterator_impl& rhs ) const {
return my_pos == rhs.my_pos;
}
bool operator!=( const iterator_impl& rhs ) const {
return my_pos != rhs.my_pos;
}
DereferenceType& operator*() const {
return intrusive_list_base::item(my_pos);
}
DereferenceType* operator->() const {
return &intrusive_list_base::item(my_pos);
}
private:
// Node the iterator points to at the moment
pointer_type my_pos;
}; // class iterator_impl
void assert_ok () const {
__TBB_ASSERT( (my_head.my_prev_node == &my_head && !my_size) ||
(my_head.my_next_node != &my_head && my_size >0), "intrusive_list_base corrupted" );
#if TBB_USE_ASSERT >= 2
size_t i = 0;
for ( intrusive_list_node *n = my_head.my_next_node; n != &my_head; n = n->my_next_node )
++i;
__TBB_ASSERT( my_size == i, "Wrong size" );
#endif /* TBB_USE_ASSERT >= 2 */
}
public:
typedef iterator_impl<T> iterator;
typedef iterator_impl<const T> const_iterator;
intrusive_list_base () : my_size(0) {
my_head.my_prev_node = &my_head;
my_head.my_next_node = &my_head;
}
bool empty () const { return my_head.my_next_node == &my_head; }
size_t size () const { return my_size; }
iterator begin () { return iterator(my_head.my_next_node); }
iterator end () { return iterator(&my_head); }
const_iterator begin () const { return const_iterator(my_head.my_next_node); }
const_iterator end () const { return const_iterator(&my_head); }
void push_front ( T& val ) {
__TBB_ASSERT( node(val).my_prev_node == &node(val) && node(val).my_next_node == &node(val),
"Object with intrusive list node can be part of only one intrusive list simultaneously" );
// An object can be part of only one intrusive list at the given moment via the given node member
node(val).my_prev_node = &my_head;
node(val).my_next_node = my_head.my_next_node;
my_head.my_next_node->my_prev_node = &node(val);
my_head.my_next_node = &node(val);
++my_size;
assert_ok();
}
void remove( T& val ) {
__TBB_ASSERT( node(val).my_prev_node != &node(val) && node(val).my_next_node != &node(val), "Element to remove is not in the list" );
__TBB_ASSERT( node(val).my_prev_node->my_next_node == &node(val) && node(val).my_next_node->my_prev_node == &node(val), "Element to remove is not in the list" );
--my_size;
node(val).my_next_node->my_prev_node = node(val).my_prev_node;
node(val).my_prev_node->my_next_node = node(val).my_next_node;
#if TBB_USE_ASSERT
node(val).my_prev_node = node(val).my_next_node = &node(val);
#endif
assert_ok();
}
iterator erase ( iterator it ) {
T& val = *it;
++it;
remove( val );
return it;
}
}; // intrusive_list_base
template <class T, class U, intrusive_list_node U::*NodePtr>
class memptr_intrusive_list : public intrusive_list_base<memptr_intrusive_list<T, U, NodePtr>, T>
{
friend class intrusive_list_base<memptr_intrusive_list<T, U, NodePtr>, T>;
static intrusive_list_node& node ( T& val ) { return val.*NodePtr; }
static T& item ( intrusive_list_node* node ) {
// Cannot use __TBB_offsetof (and consequently __TBB_get_object_ref) macro
// with *NodePtr argument because gcc refuses to interpret pasted "->" and "*"
// as member pointer dereferencing operator, and explicit usage of ## in
// __TBB_offsetof implementation breaks operations with normal member names.
return *reinterpret_cast<T*>((char*)node - ((ptrdiff_t)&(reinterpret_cast<T*>(0x1000)->*NodePtr) - 0x1000));
}
static const T& item( const intrusive_list_node* node ) {
return item(const_cast<intrusive_list_node*>(node));
}
}; // intrusive_list<T, U, NodePtr>
template <class T>
class intrusive_list : public intrusive_list_base<intrusive_list<T>, T>
{
friend class intrusive_list_base<intrusive_list<T>, T>;
static intrusive_list_node& node ( T& val ) { return val; }
static T& item ( intrusive_list_node* node ) { return *static_cast<T*>(node); }
static const T& item( const intrusive_list_node* node ) { return *static_cast<const T*>(node); }
}; // intrusive_list<T>
} // namespace internal
} // namespace tbb
#endif /* _TBB_intrusive_list_H */
_template_helpers.h
tbb_stddef.h
__TBB_ASSERT
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
type
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type type
Definition: ittnotify_static.h:198
tbb
The graph class.
Definition: serial/tbb/parallel_for.h:46
internal
Definition: _flow_graph_async_msg_impl.h:24
tbb::internal::is_same_type
Detects whether two given types are the same.
Definition: _template_helpers.h:61
tbb::internal::conditional
Definition: _template_helpers.h:299
tbb::internal::intrusive_list_node
Data structure to be inherited by the types that can form intrusive lists.
Definition: intrusive_list.h:31
tbb::internal::intrusive_list_node::my_prev_node
intrusive_list_node * my_prev_node
Definition: intrusive_list.h:32
tbb::internal::intrusive_list_node::my_next_node
intrusive_list_node * my_next_node
Definition: intrusive_list.h:33
tbb::internal::intrusive_list_base
List of element of type T, where T is derived from intrusive_list_node.
Definition: intrusive_list.h:42
tbb::internal::intrusive_list_base::my_head
intrusive_list_node my_head
Pointer to the head node.
Definition: intrusive_list.h:44
tbb::internal::intrusive_list_base::begin
const_iterator begin() const
Definition: intrusive_list.h:151
tbb::internal::intrusive_list_base::item
static const T & item(const intrusive_list_node *node)
Definition: intrusive_list.h:53
tbb::internal::intrusive_list_base::begin
iterator begin()
Definition: intrusive_list.h:147
tbb::internal::intrusive_list_base::iterator
iterator_impl< T > iterator
Definition: intrusive_list.h:135
tbb::internal::intrusive_list_base::my_size
size_t my_size
Number of list elements.
Definition: intrusive_list.h:47
tbb::internal::intrusive_list_base::end
const_iterator end() const
Definition: intrusive_list.h:153
tbb::internal::intrusive_list_base::const_iterator
iterator_impl< const T > const_iterator
Definition: intrusive_list.h:136
tbb::internal::intrusive_list_base::remove
void remove(T &val)
Definition: intrusive_list.h:167
tbb::internal::intrusive_list_base::end
iterator end()
Definition: intrusive_list.h:149
tbb::internal::intrusive_list_base::node
static intrusive_list_node & node(T &item)
Definition: intrusive_list.h:49
tbb::internal::intrusive_list_base::empty
bool empty() const
Definition: intrusive_list.h:143
tbb::internal::intrusive_list_base::item
static T & item(intrusive_list_node *node)
Definition: intrusive_list.h:51
tbb::internal::intrusive_list_base::intrusive_list_base
intrusive_list_base()
Definition: intrusive_list.h:138
tbb::internal::intrusive_list_base::size
size_t size() const
Definition: intrusive_list.h:145
tbb::internal::intrusive_list_base::erase
iterator erase(iterator it)
Definition: intrusive_list.h:179
tbb::internal::intrusive_list_base::push_front
void push_front(T &val)
Definition: intrusive_list.h:155
tbb::internal::intrusive_list_base::assert_ok
void assert_ok() const
Definition: intrusive_list.h:123
tbb::internal::intrusive_list_base::iterator_impl
Definition: intrusive_list.h:56
tbb::internal::intrusive_list_base::iterator_impl::operator++
iterator_impl & operator++()
Definition: intrusive_list.h:80
tbb::internal::intrusive_list_base::iterator_impl::iterator_impl
iterator_impl(pointer_type pos)
Definition: intrusive_list.h:66
tbb::internal::intrusive_list_base::iterator_impl::operator->
DereferenceType * operator->() const
Definition: intrusive_list.h:114
tbb::internal::intrusive_list_base::iterator_impl::operator--
iterator_impl & operator--()
Definition: intrusive_list.h:91
tbb::internal::intrusive_list_base::iterator_impl::operator!=
bool operator!=(const iterator_impl &rhs) const
Definition: intrusive_list.h:106
tbb::internal::intrusive_list_base::iterator_impl::operator++
iterator_impl operator++(int)
Definition: intrusive_list.h:85
tbb::internal::intrusive_list_base::iterator_impl::operator==
bool operator==(const iterator_impl &rhs) const
Definition: intrusive_list.h:102
tbb::internal::intrusive_list_base::iterator_impl::pointer_type
tbb::internal::conditional< tbb::internal::is_same_type< DereferenceType, T >::value, intrusive_list_node *, const intrusive_list_node * >::type pointer_type
Definition: intrusive_list.h:62
tbb::internal::intrusive_list_base::iterator_impl::__TBB_STATIC_ASSERT
__TBB_STATIC_ASSERT((tbb::internal::is_same_type< DereferenceType, T >::value||tbb::internal::is_same_type< DereferenceType, const T >::value), "Incorrect DereferenceType in iterator_impl")
tbb::internal::intrusive_list_base::iterator_impl::iterator_impl
iterator_impl()
Definition: intrusive_list.h:64
tbb::internal::intrusive_list_base::iterator_impl::operator=
iterator_impl & operator=(const iterator_impl &other)
Definition: intrusive_list.h:68
tbb::internal::intrusive_list_base::iterator_impl::my_pos
pointer_type my_pos
Definition: intrusive_list.h:120
tbb::internal::intrusive_list_base::iterator_impl::operator=
iterator_impl & operator=(const T &val)
Definition: intrusive_list.h:75
tbb::internal::intrusive_list_base::iterator_impl::operator*
DereferenceType & operator*() const
Definition: intrusive_list.h:110
tbb::internal::intrusive_list_base::iterator_impl::operator--
iterator_impl operator--(int)
Definition: intrusive_list.h:96
tbb::internal::memptr_intrusive_list
Double linked list of items of type T containing a member of type intrusive_list_node.
Definition: intrusive_list.h:200
tbb::internal::memptr_intrusive_list::item
static T & item(intrusive_list_node *node)
Definition: intrusive_list.h:205
tbb::internal::memptr_intrusive_list::node
static intrusive_list_node & node(T &val)
Definition: intrusive_list.h:203
tbb::internal::intrusive_list
Double linked list of items of type T that is derived from intrusive_list_node class.
Definition: intrusive_list.h:225
tbb::internal::intrusive_list::item
static const T & item(const intrusive_list_node *node)
Definition: intrusive_list.h:231
tbb::internal::intrusive_list::item
static T & item(intrusive_list_node *node)
Definition: intrusive_list.h:230
tbb::internal::intrusive_list::node
static intrusive_list_node & node(T &val)
Definition: intrusive_list.h:228

Copyright © 2005-2020 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.