3 #ifndef CDSLIB_INTRUSIVE_SKIP_LIST_NOGC_H
4 #define CDSLIB_INTRUSIVE_SKIP_LIST_NOGC_H
8 #include <cds/gc/nogc.h>
9 #include <cds/intrusive/details/skip_list_base.h>
10 #include <cds/opt/compare.h>
11 #include <cds/details/binary_functor_wrapper.h>
13 namespace cds { namespace intrusive {
17 template <typename Tag>
18 class node< cds::gc::nogc, Tag >
21 typedef cds::gc::nogc gc; ///< Garbage collector
22 typedef Tag tag; ///< tag
24 typedef atomics::atomic<node * > atomic_ptr;
25 typedef atomic_ptr tower_item_type;
28 atomic_ptr m_pNext; ///< Next item in bottom-list (list at level 0)
29 unsigned int m_nHeight; ///< Node height (size of m_arrNext array). For node at level 0 the height is 1.
30 atomic_ptr * m_arrNext; ///< Array of next items for levels 1 .. m_nHeight - 1. For node at level 0 \p m_arrNext is \p nullptr
33 /// Constructs a node of height 1 (a bottom-list node)
37 , m_arrNext( nullptr )
40 /// Constructs a node of height \p nHeight
41 void make_tower( unsigned int nHeight, atomic_ptr * nextTower )
43 assert( nHeight > 0 );
44 assert( (nHeight == 1 && nextTower == nullptr) // bottom-list node
45 || (nHeight > 1 && nextTower != nullptr) // node at level of more than 0
48 m_arrNext = nextTower;
52 atomic_ptr * release_tower()
54 atomic_ptr * pTower = m_arrNext;
60 atomic_ptr * get_tower() const
65 /// Access to element of next pointer array
66 atomic_ptr& next( unsigned int nLevel )
68 assert( nLevel < height() );
69 assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr) );
71 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
74 /// Access to element of next pointer array (const version)
75 atomic_ptr const& next( unsigned int nLevel ) const
77 assert( nLevel < height() );
78 assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr );
80 return nLevel ? m_arrNext[ nLevel - 1] : m_pNext;
83 /// Access to element of next pointer array (same as \ref next function)
84 atomic_ptr& operator[]( unsigned int nLevel )
86 return next( nLevel );
89 /// Access to element of next pointer array (same as \ref next function)
90 atomic_ptr const& operator[]( unsigned int nLevel ) const
92 return next( nLevel );
95 /// Height of the node
96 unsigned int height() const
101 /// Clears internal links
104 assert( m_arrNext == nullptr );
105 m_pNext.store( nullptr, atomics::memory_order_release );
108 bool is_cleared() const
110 return m_pNext.load( atomics::memory_order_relaxed ) == nullptr
111 && m_arrNext == nullptr
116 } // namespace skip_list
118 namespace skip_list { namespace details {
120 template <typename NodeTraits, typename BackOff, bool IsConst>
121 class iterator< cds::gc::nogc, NodeTraits, BackOff, IsConst>
124 typedef cds::gc::nogc gc;
125 typedef NodeTraits node_traits;
126 typedef BackOff back_off;
127 typedef typename node_traits::node_type node_type;
128 typedef typename node_traits::value_type value_type;
129 static CDS_CONSTEXPR bool const c_isConst = IsConst;
131 typedef typename std::conditional< c_isConst, value_type const &, value_type &>::type value_ref;
132 friend class iterator< gc, node_traits, back_off, !c_isConst >;
135 typedef typename node_type::atomic_ptr atomic_ptr;
138 public: // for internal use only!!!
139 iterator( node_type& refHead )
140 : m_pNode( refHead[0].load( atomics::memory_order_relaxed ) )
143 static iterator from_node( node_type * pNode )
155 iterator( iterator const& s)
156 : m_pNode( s.m_pNode )
159 value_type * operator ->() const
161 assert( m_pNode != nullptr );
162 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
164 return node_traits::to_value_ptr( m_pNode );
167 value_ref operator *() const
169 assert( m_pNode != nullptr );
170 assert( node_traits::to_value_ptr( m_pNode ) != nullptr );
172 return *node_traits::to_value_ptr( m_pNode );
176 iterator& operator ++()
179 m_pNode = m_pNode->next(0).load( atomics::memory_order_relaxed );
183 iterator& operator =(const iterator& src)
185 m_pNode = src.m_pNode;
189 template <typename Bkoff, bool C>
190 bool operator ==(iterator<gc, node_traits, Bkoff, C> const& i ) const
192 return m_pNode == i.m_pNode;
194 template <typename Bkoff, bool C>
195 bool operator !=(iterator<gc, node_traits, Bkoff, C> const& i ) const
197 return !( *this == i );
200 }} // namespace skip_list::details
203 /// Lock-free skip-list set (template specialization for gc::nogc)
204 /** @ingroup cds_intrusive_map
205 @anchor cds_intrusive_SkipListSet_nogc
207 This specialization is so-called append-only when no item
208 reclamation may be performed. The class does not support deleting of list item.
210 See \ref cds_intrusive_SkipListSet_hp "SkipListSet" for description of skip-list.
212 <b>Template arguments</b> :
213 - \p T - type to be stored in the set. The type must be based on \p skip_list::node (for \p skip_list::base_hook)
214 or it must have a member of type \p skip_list::node (for \p skip_list::member_hook).
215 - \p Traits - type traits, default is \p skip_list::traits.
216 It is possible to declare option-based list with \p cds::intrusive::skip_list::make_traits metafunction
217 istead of \p Traits template argument.
221 The class supports a forward iterator (\ref iterator and \ref const_iterator).
222 The iteration is ordered.
224 The iterator class supports the following minimalistic interface:
231 iterator( iterator const& s);
233 value_type * operator ->() const;
234 value_type& operator *() const;
237 iterator& operator ++();
240 iterator& operator = (const iterator& src);
242 bool operator ==(iterator const& i ) const;
243 bool operator !=(iterator const& i ) const;
246 Note, the iterator object returned by \ref end, \p cend member functions points to \p nullptr and should not be dereferenced.
250 You should incorporate \p skip_list::node into your struct \p T and provide
251 appropriate \p skip_list::traits::hook in your \p Traits template parameters. Usually, for \p Traits you
252 define a struct based on \p skip_list::traits.
254 Example for base hook:
256 #include <cds/intrusive/skip_list_nogc.h>
258 // Data stored in skip list
259 struct my_data: public cds::intrusive::skip_list::node< cds::gc::nogc >
268 // my_data compare functor
270 int operator()( const my_data& d1, const my_data& d2 )
272 return d1.strKey.compare( d2.strKey );
275 int operator()( const my_data& d, const std::string& s )
277 return d.strKey.compare(s);
280 int operator()( const std::string& s, const my_data& d )
282 return s.compare( d.strKey );
288 struct my_traits: public cds::intrusive::skip_list::traits
290 typedef cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::nogc > > hook;
291 typedef my_data_cmp compare;
294 // Declare skip-list set type
295 typedef cds::intrusive::SkipListSet< cds::gc::nogc, my_data, my_traits > traits_based_set;
298 Equivalent option-based code:
300 // GC-related specialization
301 #include <cds/intrusive/skip_list_nogc.h>
310 // Declare option-based skip-list set
311 typedef cds::intrusive::SkipListSet< cds::gc::nogc
313 , typename cds::intrusive::skip_list::make_traits<
314 cds::intrusive::opt::hook< cds::intrusive::skip_list::base_hook< cds::opt::gc< cds::gc::nogc > > >
315 ,cds::intrusive::opt::compare< my_data_cmp >
322 #ifdef CDS_DOXYGEN_INVOKED
323 ,typename Traits = skip_list::traits
328 class SkipListSet< cds::gc::nogc, T, Traits >
331 typedef cds::gc::nogc gc; ///< No garbage collector is used
332 typedef T value_type; ///< type of value stored in the skip-list
333 typedef Traits traits; ///< Traits template parameter
335 typedef typename traits::hook hook; ///< hook type
336 typedef typename hook::node_type node_type; ///< node type
338 # ifdef CDS_DOXYGEN_INVOKED
339 typedef implementation_defined key_comparator; ///< key comparison functor based on \p Traits::compare and \p Traits::less
341 typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator;
343 typedef typename get_node_traits< value_type, node_type, hook>::type node_traits; ///< node traits
345 typedef typename traits::item_counter item_counter; ///< Item counting policy
346 typedef typename traits::memory_model memory_model; ///< Memory ordering. See \p cds::opt::memory_model option
347 typedef typename traits::random_level_generator random_level_generator ; ///< random level generator
348 typedef typename traits::allocator allocator_type; ///< allocator for maintaining array of next pointers of the node
349 typedef typename traits::back_off back_off; ///< Back-off strategy
350 typedef typename traits::stat stat; ///< internal statistics type
351 typedef typename traits::disposer disposer; ///< disposer
353 /// Max node height. The actual node height should be in range <tt>[0 .. c_nMaxHeight)</tt>
355 The max height is specified by \ref skip_list::random_level_generator "random level generator" constant \p m_nUpperBound
356 but it should be no more than 32 (\p skip_list::c_nHeightLimit).
358 static unsigned int const c_nMaxHeight = std::conditional<
359 (random_level_generator::c_nUpperBound <= skip_list::c_nHeightLimit),
360 std::integral_constant< unsigned int, random_level_generator::c_nUpperBound >,
361 std::integral_constant< unsigned int, skip_list::c_nHeightLimit >
365 static unsigned int const c_nMinHeight = 3;
366 typedef cds::intrusive::skip_list::implementation_tag implementation_tag;
370 typedef typename node_type::atomic_ptr atomic_node_ptr; ///< Atomic node pointer
374 typedef skip_list::details::intrusive_node_builder< node_type, atomic_node_ptr, allocator_type > intrusive_node_builder;
376 typedef typename std::conditional<
377 std::is_same< typename traits::internal_node_builder, cds::opt::none >::value
378 ,intrusive_node_builder
379 ,typename traits::internal_node_builder
380 >::type node_builder;
382 typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr;
385 node_type * pPrev[ c_nMaxHeight ];
386 node_type * pSucc[ c_nMaxHeight ];
391 class head_node: public node_type
393 typename node_type::atomic_ptr m_Tower[c_nMaxHeight];
396 head_node( unsigned int nHeight )
398 for ( size_t i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
399 m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
401 node_type::make_tower( nHeight, m_Tower );
404 node_type * head() const
406 return const_cast<node_type *>( static_cast<node_type const *>(this));
411 for (unsigned int i = 0; i < sizeof(m_Tower) / sizeof(m_Tower[0]); ++i )
412 m_Tower[i].store( nullptr, atomics::memory_order_relaxed );
413 node_type::m_pNext.store( nullptr, atomics::memory_order_relaxed );
419 head_node m_Head; ///< head tower (max height)
421 item_counter m_ItemCounter; ///< item counter
422 random_level_generator m_RandomLevelGen; ///< random level generator instance
423 atomics::atomic<unsigned int> m_nHeight; ///< estimated high level
424 mutable stat m_Stat; ///< internal statistics
428 unsigned int random_level()
430 // Random generator produces a number from range [0..31]
431 // We need a number from range [1..32]
432 return m_RandomLevelGen() + 1;
435 template <typename Q>
436 node_type * build_node( Q v )
438 return node_builder::make_tower( v, m_RandomLevelGen );
441 static void dispose_node( node_type * pNode )
443 assert( pNode != nullptr );
444 typename node_builder::node_disposer()( pNode );
445 disposer()( node_traits::to_value_ptr( pNode ));
448 template <typename Q, typename Compare >
449 bool find_position( Q const& val, position& pos, Compare cmp, bool bStopIfFound, bool bStrictSearch ) const
453 node_type * pCur = nullptr;
457 unsigned int nHeight = c_nMaxHeight;
459 if ( !bStrictSearch )
460 nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
461 pPred = m_Head.head();
463 for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
465 pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
468 // end of the list at level nLevel - goto next level
472 pSucc = pCur->next( nLevel ).load( memory_model::memory_order_relaxed );
474 if ( pPred->next( nLevel ).load( memory_model::memory_order_acquire ) != pCur
475 || pCur->next( nLevel ).load( memory_model::memory_order_acquire ) != pSucc )
480 nCmp = cmp( *node_traits::to_value_ptr( pCur ), val );
483 else if ( nCmp == 0 && bStopIfFound )
489 pos.pPrev[ nLevel ] = pPred;
490 pos.pSucc[ nLevel ] = pCur;
498 return pCur && nCmp == 0;
501 template <typename Func>
502 bool insert_at_position( value_type& val, node_type * pNode, position& pos, Func f )
504 unsigned int nHeight = pNode->height();
506 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel )
507 pNode->next( nLevel ).store( nullptr, memory_model::memory_order_relaxed );
510 node_type * p = pos.pSucc[0];
511 pNode->next( 0 ).store( pos.pSucc[ 0 ], memory_model::memory_order_release );
512 if ( !pos.pPrev[0]->next(0).compare_exchange_strong( p, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) ) {
518 for ( unsigned int nLevel = 1; nLevel < nHeight; ++nLevel ) {
519 node_type * p = nullptr;
521 node_type * q = pos.pSucc[ nLevel ];
523 if ( pNode->next( nLevel ).compare_exchange_strong( p, q, memory_model::memory_order_release, memory_model::memory_order_relaxed )) {
525 if ( pos.pPrev[nLevel]->next(nLevel).compare_exchange_strong( q, pNode, memory_model::memory_order_release, memory_model::memory_order_relaxed ) )
529 // Renew insert position
530 find_position( val, pos, key_comparator(), false, true );
536 template <typename Q, typename Compare, typename Func>
537 node_type * find_with_( Q& val, Compare cmp, Func f ) const
540 if ( find_position( val, pos, cmp, true, false )) {
541 assert( cmp( *node_traits::to_value_ptr( pos.pCur ), val ) == 0 );
543 f( *node_traits::to_value_ptr( pos.pCur ), val );
545 m_Stat.onFindFastSuccess();
549 m_Stat.onFindFastFailed();
554 void increase_height( unsigned int nHeight )
556 unsigned int nCur = m_nHeight.load( memory_model::memory_order_relaxed );
557 while ( nCur < nHeight && !m_nHeight.compare_exchange_weak( nCur, nHeight, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) );
562 /// Default constructor
564 The constructor checks whether the count of guards is enough
565 for skip-list and may raise an exception if not.
568 : m_Head( c_nMaxHeight )
569 , m_nHeight( c_nMinHeight )
571 static_assert( (std::is_same< gc, typename node_type::gc >::value), "GC and node_type::gc must be the same type" );
573 // Barrier for head node
574 atomics::atomic_thread_fence( memory_model::memory_order_release );
577 /// Clears and destructs the skip-list
585 typedef skip_list::details::iterator< gc, node_traits, back_off, false > iterator;
587 /// Const iterator type
588 typedef skip_list::details::iterator< gc, node_traits, back_off, true > const_iterator;
590 /// Returns a forward iterator addressing the first element in a set
593 return iterator( *m_Head.head() );
596 /// Returns a forward const iterator addressing the first element in a set
597 const_iterator begin() const
599 return const_iterator( *m_Head.head() );
601 /// Returns a forward const iterator addressing the first element in a set
602 const_iterator cbegin() const
604 return const_iterator( *m_Head.head() );
607 /// Returns a forward iterator that addresses the location succeeding the last element in a set.
613 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
614 const_iterator end() const
616 return const_iterator();
618 /// Returns a forward const iterator that addresses the location succeeding the last element in a set.
619 const_iterator cend() const
621 return const_iterator();
626 iterator nonconst_end() const
635 The function inserts \p val in the set if it does not contain
636 an item with key equal to \p val.
638 Returns \p true if \p val is placed into the set, \p false otherwise.
640 bool insert( value_type& val )
642 node_type * pNode = node_traits::to_node_ptr( val );
643 scoped_node_ptr scp( pNode );
644 unsigned int nHeight = pNode->height();
645 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
646 bool bTowerMade = false;
651 bool bFound = find_position( val, pos, key_comparator(), true, true );
653 // scoped_node_ptr deletes the node tower if we create it
657 m_Stat.onInsertFailed();
663 nHeight = pNode->height();
668 if ( !insert_at_position( val, pNode, pos, []( value_type& ) {} )) {
669 m_Stat.onInsertRetry();
673 increase_height( nHeight );
675 m_Stat.onAddNode( nHeight );
676 m_Stat.onInsertSuccess();
684 The operation performs inserting or changing data with lock-free manner.
686 If the item \p val is not found in the set, then \p val is inserted into the set
687 iff \p bInsert is \p true.
688 Otherwise, the functor \p func is called with item found.
689 The functor signature is:
691 void func( bool bNew, value_type& item, value_type& val );
694 - \p bNew - \p true if the item has been inserted, \p false otherwise
695 - \p item - item of the set
696 - \p val - argument \p val passed into the \p %update() function
697 If new item has been inserted (i.e. \p bNew is \p true) then \p item and \p val arguments
698 refer to the same thing.
700 The functor can change non-key fields of the \p item; however, \p func must guarantee
701 that during changing no any other modifications could be made on this item by concurrent threads.
703 Returns std::pair<bool, bool> where \p first is \p true if operation is successfull,
704 \p second is \p true if new item has been added or \p false if the item with \p key
705 already is in the set.
707 @warning See \ref cds_intrusive_item_creating "insert item troubleshooting"
709 template <typename Func>
710 std::pair<bool, bool> update( value_type& val, Func func, bool bInsert = true )
712 node_type * pNode = node_traits::to_node_ptr( val );
713 scoped_node_ptr scp( pNode );
714 unsigned int nHeight = pNode->height();
715 bool bTowerOk = nHeight > 1 && pNode->get_tower() != nullptr;
716 bool bTowerMade = false;
721 bool bFound = find_position( val, pos, key_comparator(), true, true );
723 // scoped_node_ptr deletes the node tower if we create it before
727 func( false, *node_traits::to_value_ptr(pos.pCur), val );
728 m_Stat.onUpdateExist();
729 return std::make_pair( true, false );
734 return std::make_pair( false, false );
739 nHeight = pNode->height();
744 if ( !insert_at_position( val, pNode, pos, [&func]( value_type& item ) { func( true, item, item ); })) {
745 m_Stat.onInsertRetry();
749 increase_height( nHeight );
752 m_Stat.onAddNode( nHeight );
753 m_Stat.onUpdateNew();
754 return std::make_pair( true, true );
759 // Deprecated, use update() instead
760 template <typename Func>
761 std::pair<bool, bool> ensure( value_type& val, Func func )
763 return update( val, func, true );
768 /** \anchor cds_intrusive_SkipListSet_nogc_find_func
769 The function searches the item with key equal to \p key and calls the functor \p f for item found.
770 The interface of \p Func functor is:
773 void operator()( value_type& item, Q& key );
776 where \p item is the item found, \p key is the <tt>find</tt> function argument.
778 The functor can change non-key fields of \p item. Note that the functor is only guarantee
779 that \p item cannot be disposed during functor is executing.
780 The functor does not serialize simultaneous access to the set \p item. If such access is
781 possible you must provide your own synchronization schema on item level to exclude unsafe item modifications.
783 The \p key argument is non-const since it can be used as \p f functor destination i.e., the functor
784 can modify both arguments.
786 Note the hash functor specified for class \p Traits template parameter
787 should accept a parameter of type \p Q that can be not the same as \p value_type.
789 The function returns \p true if \p key is found, \p false otherwise.
791 template <typename Q, typename Func>
792 bool find( Q& key, Func f ) const
794 return find_with_( key, key_comparator(), f ) != nullptr;
797 template <typename Q, typename Func>
798 bool find( Q const& key, Func f ) const
800 return find_with_( key, key_comparator(), f ) != nullptr;
804 /// Finds the key \p key using \p pred predicate for comparing
806 The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_func "find(Q&, Func)"
807 but \p pred predicate is used for key compare.
808 \p Less has the interface like \p std::less.
809 \p pred must imply the same element order as the comparator used for building the set.
811 template <typename Q, typename Less, typename Func>
812 bool find_with( Q& key, Less pred, Func f ) const
815 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
818 template <typename Q, typename Less, typename Func>
819 bool find_with( Q const& key, Less pred, Func f ) const
822 return find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), f ) != nullptr;
827 /** \anchor cds_intrusive_SkipListSet_nogc_find_val
828 The function searches the item with key equal to \p key
829 and returns \p true if it is found, and \p false otherwise.
831 Note the hash functor specified for class \p Traits template parameter
832 should accept a parameter of type \p Q that can be not the same as \p value_type.
834 template <typename Q>
835 value_type * find( Q const& key ) const
837 node_type * pNode = find_with_( key, key_comparator(), [](value_type& , Q const& ) {} );
839 return node_traits::to_value_ptr( pNode );
843 /// Finds \p key using \p pred predicate for comparing
845 The function is an analog of \ref cds_intrusive_SkipListSet_nogc_find_val "find(Q const&)"
846 but \p pred predicate is used for key compare.
847 \p Less has the interface like \p std::less.
848 \p pred must imply the same element order as the comparator used for building the set.
850 template <typename Q, typename Less>
851 value_type * find_with( Q const& key, Less pred ) const
854 node_type * pNode = find_with_( key, cds::opt::details::make_comparator_from_less<Less>(), [](value_type& , Q const& ) {} );
856 return node_traits::to_value_ptr( pNode );
860 /// Gets minimum key from the set
862 If the set is empty the function returns \p nullptr
864 value_type * get_min() const
866 return node_traits::to_value_ptr( m_Head.head()->next( 0 ));
869 /// Gets maximum key from the set
871 The function returns \p nullptr if the set is empty
873 value_type * get_max() const
877 unsigned int nHeight = m_nHeight.load( memory_model::memory_order_relaxed );
878 pPred = m_Head.head();
880 for ( int nLevel = (int) nHeight - 1; nLevel >= 0; --nLevel ) {
882 node_type * pCur = pPred->next( nLevel ).load( memory_model::memory_order_relaxed );
885 // end of the list at level nLevel - goto next level
891 return pPred && pPred != m_Head.head() ? node_traits::to_value_ptr( pPred ) : nullptr;
894 /// Clears the set (non-atomic)
896 The function is not atomic.
897 Finding and/or inserting is prohibited while clearing.
898 Otherwise an unpredictable result may be encountered.
899 Thus, \p clear() may be used only for debugging purposes.
903 node_type * pNode = m_Head.head()->next(0).load( memory_model::memory_order_relaxed );
905 m_ItemCounter.reset();
906 m_nHeight.store( c_nMinHeight, memory_model::memory_order_release );
909 node_type * pNext = pNode->next(0).load( memory_model::memory_order_relaxed );
910 dispose_node( pNode );
915 /// Returns item count in the set
917 The value returned depends on item counter type provided by \p Traits template parameter.
918 For \p atomicity::empty_item_counter the function always returns 0.
919 The function is not suitable for checking the set emptiness, use \p empty().
923 return m_ItemCounter;
926 /// Checks if the set is empty
929 return m_Head.head()->next( 0 ).load( memory_model::memory_order_relaxed ) == nullptr;
932 /// Returns maximum height of skip-list. The max height is a constant for each object and does not exceed 32.
933 static CDS_CONSTEXPR unsigned int max_height() CDS_NOEXCEPT
938 /// Returns const reference to internal statistics
939 stat const& statistics() const
945 }} // namespace cds::intrusive
948 #endif // #ifndef CDSLIB_INTRUSIVE_SKIP_LIST_IMPL_H