test/unit/queue/intrusive_fcqueue.cpp

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #include <gtest/gtest.h>
  32 #include <cds/intrusive/fcqueue.h>
  33
  34 #include <vector>
  35 #include <boost/intrusive/slist.hpp>
  36
  37 namespace {
  38
  39     class IntrusiveFCQueue : public ::testing::Test
  40     {
  41     protected:
  42         template <typename Hook>
  43         struct base_hook_item : public Hook
  44         {
  45             int nVal;
  46             int nDisposeCount;
  47
  48             base_hook_item()
  49                 : nDisposeCount( 0 )
  50             {}
  51         };
  52
  53         template <typename Hook>
  54         struct member_hook_item
  55         {
  56             int nVal;
  57             int nDisposeCount;
  58             Hook hMember;
  59
  60             member_hook_item()
  61                 : nDisposeCount( 0 )
  62             {}
  63         };
  64
  65         struct disposer
  66         {
  67             template <typename T>
  68             void operator ()( T * p )
  69             {
  70                 ++p->nDisposeCount;
  71             }
  72         };
  73
  74         template <typename Queue>
  75         void test( Queue& q )
  76         {
  77             typedef typename Queue::value_type value_type;
  78
  79             size_t const nSize = 100;
  80             value_type * pv;
  81             std::vector<value_type> arr;
  82             arr.resize( nSize );
  83             for ( size_t i = 0; i < nSize; ++i )
  84                 arr[i].nVal = static_cast<int>(i);
  85
  86             ASSERT_TRUE( q.empty() );
  87             ASSERT_EQ( q.size(), 0 );
  88
  89             // pop from empty queue
  90             pv = q.pop();
  91             ASSERT_TRUE( pv == nullptr );
  92             ASSERT_TRUE( q.empty() );
  93             ASSERT_EQ( q.size(), 0 );
  94
  95             pv = q.dequeue();
  96             ASSERT_TRUE( pv == nullptr );
  97             ASSERT_TRUE( q.empty() );
  98             ASSERT_EQ( q.size(), 0 );
  99
 100             // push/pop test
 101             for ( size_t i = 0; i < nSize; ++i ) {
 102                 if ( i & 1 )
 103                     q.push( arr[i] );
 104                 else
 105                     q.enqueue( arr[i] );
 106                 ASSERT_FALSE( q.empty() );
 107                 ASSERT_EQ( q.size(), i + 1 );
 108             }
 109
 110             for ( size_t i = 0; i < nSize; ++i ) {
 111                 ASSERT_FALSE( q.empty() );
 112                 ASSERT_EQ( q.size(), nSize - i );
 113                 if ( i & 1 )
 114                     pv = q.pop();
 115                 else
 116                     pv = q.dequeue();
 117                 ASSERT_FALSE( pv == nullptr );
 118                 ASSERT_EQ( pv->nVal, static_cast<int>(i) );
 119             }
 120             ASSERT_TRUE( q.empty() );
 121             ASSERT_EQ( q.size(), 0 );
 122
 123             // pop() doesn't call disposer
 124             for ( size_t i = 0; i < nSize; ++i ) {
 125                 ASSERT_EQ( arr[i].nDisposeCount, 0 );
 126             }
 127
 128             // clear with disposer
 129             for ( size_t i = 0; i < nSize; ++i )
 130                 q.push( arr[i] );
 131
 132             ASSERT_FALSE( q.empty() );
 133             ASSERT_EQ( q.size(), nSize );
 134
 135             q.clear( true );
 136             ASSERT_TRUE( q.empty() );
 137             ASSERT_EQ( q.size(), 0 );
 138
 139             for ( size_t i = 0; i < nSize; ++i ) {
 140                 ASSERT_EQ( arr[i].nDisposeCount, 1 );
 141             }
 142
 143             // clear without disposer
 144             for ( size_t i = 0; i < nSize; ++i )
 145                 q.push( arr[i] );
 146
 147             q.clear();
 148             ASSERT_TRUE( q.empty() );
 149             ASSERT_EQ( q.size(), 0 );
 150
 151             for ( size_t i = 0; i < nSize; ++i ) {
 152                 ASSERT_EQ( arr[i].nDisposeCount, 1 );
 153             }
 154         }
 155     };
 156
 157     TEST_F( IntrusiveFCQueue, base )
 158     {
 159         typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
 160         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >,
 161             cds::intrusive::fcqueue::make_traits<
 162                 cds::intrusive::opt::disposer< disposer >
 163             >::type
 164         > queue_type;
 165
 166         queue_type q;
 167         test( q );
 168     }
 169
 170     TEST_F( IntrusiveFCQueue, base_mutex )
 171     {
 172         typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
 173         struct traits : public cds::intrusive::fcqueue::traits
 174         {
 175             typedef IntrusiveFCQueue::disposer disposer;
 176             typedef std::mutex lock_type;
 177             typedef cds::intrusive::fcqueue::stat<> stat;
 178         };
 179         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >, traits > queue_type;
 180
 181         queue_type q;
 182         test( q );
 183     }
 184
 185     TEST_F( IntrusiveFCQueue, base_elimination )
 186     {
 187         typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
 188         struct traits : public
 189             cds::intrusive::fcqueue::make_traits <
 190                 cds::intrusive::opt::disposer< disposer >
 191                 , cds::opt::enable_elimination < true >
 192             > ::type
 193         {};
 194         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >, traits > queue_type;
 195
 196         queue_type q;
 197         test( q );
 198     }
 199
 200     TEST_F( IntrusiveFCQueue, member )
 201     {
 202         typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
 203         typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
 204
 205         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >,
 206             cds::intrusive::fcqueue::make_traits<
 207                 cds::intrusive::opt::disposer< disposer >
 208             >::type
 209         > queue_type;
 210
 211         queue_type q;
 212         test( q );
 213     }
 214
 215     TEST_F( IntrusiveFCQueue, member_mutex )
 216     {
 217         typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
 218         typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
 219
 220         struct traits : public cds::intrusive::fcqueue::traits
 221         {
 222             typedef IntrusiveFCQueue::disposer disposer;
 223             typedef std::mutex lock_type;
 224             typedef cds::intrusive::fcqueue::stat<> stat;
 225         };
 226         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >, traits > queue_type;
 227
 228         queue_type q;
 229         test( q );
 230     }
 231
 232     TEST_F( IntrusiveFCQueue, member_elimination )
 233     {
 234         typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
 235         typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
 236
 237         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >,
 238             cds::intrusive::fcqueue::make_traits<
 239                 cds::intrusive::opt::disposer< disposer >
 240                 ,cds::opt::enable_elimination< true >
 241             >::type
 242         > queue_type;
 243
 244         queue_type q;
 245         test( q );
 246     }
 247
 248     TEST_F( IntrusiveFCQueue, slist_base )
 249     {
 250         typedef base_hook_item< boost::intrusive::slist_base_hook<>> value_type;
 251         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::slist< value_type, boost::intrusive::cache_last< true >>,
 252             cds::intrusive::fcqueue::make_traits<
 253                 cds::intrusive::opt::disposer< disposer >
 254             >::type
 255         > queue_type;
 256
 257         queue_type q;
 258         test( q );
 259     }
 260
 261     TEST_F( IntrusiveFCQueue, slist_base_elimination )
 262     {
 263         typedef base_hook_item< boost::intrusive::slist_base_hook<> > value_type;
 264         struct traits : public
 265             cds::intrusive::fcqueue::make_traits <
 266                 cds::intrusive::opt::disposer< disposer >
 267                 , cds::opt::enable_elimination < true >
 268                 , cds::opt::lock_type< std::mutex >
 269             > ::type
 270         {};
 271         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::slist< value_type, boost::intrusive::cache_last< true >>, traits > queue_type;
 272
 273         queue_type q;
 274         test( q );
 275     }
 276
 277     TEST_F( IntrusiveFCQueue, slist_member )
 278     {
 279         typedef member_hook_item< boost::intrusive::slist_member_hook<> > value_type;
 280         typedef boost::intrusive::member_hook<value_type, boost::intrusive::slist_member_hook<>, &value_type::hMember> member_option;
 281
 282         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::slist< value_type, member_option, boost::intrusive::cache_last< true >>,
 283             cds::intrusive::fcqueue::make_traits<
 284                 cds::intrusive::opt::disposer< disposer >
 285             >::type
 286         > queue_type;
 287
 288         queue_type q;
 289         test( q );
 290     }
 291
 292     TEST_F( IntrusiveFCQueue, slist_member_elimination )
 293     {
 294         typedef member_hook_item< boost::intrusive::slist_member_hook<> > value_type;
 295         typedef boost::intrusive::member_hook<value_type, boost::intrusive::slist_member_hook<>, &value_type::hMember> member_option;
 296
 297         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::slist< value_type, member_option, boost::intrusive::cache_last< true >>,
 298             cds::intrusive::fcqueue::make_traits<
 299                 cds::intrusive::opt::disposer< disposer >
 300                 ,cds::opt::enable_elimination< true >
 301             >::type
 302         > queue_type;
 303
 304         queue_type q;
 305         test( q );
 306     }
 307
 308 } // namepace