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     public:
  66         struct disposer
  67         {
  68             template <typename T>
  69             void operator ()( T * p )
  70             {
  71                 ++p->nDisposeCount;
  72             }
  73         };
  74
  75     protected:
  76         template <typename Queue>
  77         void test( Queue& q )
  78         {
  79             typedef typename Queue::value_type value_type;
  80
  81             size_t const nSize = 100;
  82             value_type * pv;
  83             std::vector<value_type> arr;
  84             arr.resize( nSize );
  85             for ( size_t i = 0; i < nSize; ++i )
  86                 arr[i].nVal = static_cast<int>(i);
  87
  88             ASSERT_TRUE( q.empty() );
  89             ASSERT_EQ( q.size(), 0 );
  90
  91             // pop from empty queue
  92             pv = q.pop();
  93             ASSERT_TRUE( pv == nullptr );
  94             ASSERT_TRUE( q.empty() );
  95             ASSERT_EQ( q.size(), 0 );
  96
  97             pv = q.dequeue();
  98             ASSERT_TRUE( pv == nullptr );
  99             ASSERT_TRUE( q.empty() );
 100             ASSERT_EQ( q.size(), 0 );
 101
 102             // push/pop test
 103             for ( size_t i = 0; i < nSize; ++i ) {
 104                 if ( i & 1 )
 105                     q.push( arr[i] );
 106                 else
 107                     q.enqueue( arr[i] );
 108                 ASSERT_FALSE( q.empty() );
 109                 ASSERT_EQ( q.size(), i + 1 );
 110             }
 111
 112             for ( size_t i = 0; i < nSize; ++i ) {
 113                 ASSERT_FALSE( q.empty() );
 114                 ASSERT_EQ( q.size(), nSize - i );
 115                 if ( i & 1 )
 116                     pv = q.pop();
 117                 else
 118                     pv = q.dequeue();
 119                 ASSERT_FALSE( pv == nullptr );
 120                 ASSERT_EQ( pv->nVal, static_cast<int>(i) );
 121             }
 122             ASSERT_TRUE( q.empty() );
 123             ASSERT_EQ( q.size(), 0 );
 124
 125             // pop() doesn't call disposer
 126             for ( size_t i = 0; i < nSize; ++i ) {
 127                 ASSERT_EQ( arr[i].nDisposeCount, 0 );
 128             }
 129
 130             // clear with disposer
 131             for ( size_t i = 0; i < nSize; ++i )
 132                 q.push( arr[i] );
 133
 134             ASSERT_FALSE( q.empty() );
 135             ASSERT_EQ( q.size(), nSize );
 136
 137             q.clear( true );
 138             ASSERT_TRUE( q.empty() );
 139             ASSERT_EQ( q.size(), 0 );
 140
 141             for ( size_t i = 0; i < nSize; ++i ) {
 142                 ASSERT_EQ( arr[i].nDisposeCount, 1 );
 143             }
 144
 145             // clear without disposer
 146             for ( size_t i = 0; i < nSize; ++i )
 147                 q.push( arr[i] );
 148
 149             q.clear();
 150             ASSERT_TRUE( q.empty() );
 151             ASSERT_EQ( q.size(), 0 );
 152
 153             for ( size_t i = 0; i < nSize; ++i ) {
 154                 ASSERT_EQ( arr[i].nDisposeCount, 1 );
 155             }
 156         }
 157     };
 158
 159     TEST_F( IntrusiveFCQueue, base )
 160     {
 161         typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
 162         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >,
 163             cds::intrusive::fcqueue::make_traits<
 164                 cds::intrusive::opt::disposer< disposer >
 165             >::type
 166         > queue_type;
 167
 168         queue_type q;
 169         test( q );
 170     }
 171
 172     TEST_F( IntrusiveFCQueue, base_mutex )
 173     {
 174         typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
 175         struct traits : public cds::intrusive::fcqueue::traits
 176         {
 177             typedef IntrusiveFCQueue::disposer disposer;
 178             typedef std::mutex lock_type;
 179             typedef cds::intrusive::fcqueue::stat<> stat;
 180         };
 181         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >, traits > queue_type;
 182
 183         queue_type q;
 184         test( q );
 185     }
 186
 187     TEST_F( IntrusiveFCQueue, base_elimination )
 188     {
 189         typedef base_hook_item< boost::intrusive::list_base_hook<> > value_type;
 190         struct traits : public
 191             cds::intrusive::fcqueue::make_traits <
 192                 cds::intrusive::opt::disposer< disposer >
 193                 , cds::opt::enable_elimination < true >
 194             > ::type
 195         {};
 196         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type >, traits > queue_type;
 197
 198         queue_type q;
 199         test( q );
 200     }
 201
 202     TEST_F( IntrusiveFCQueue, member )
 203     {
 204         typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
 205         typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
 206
 207         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >,
 208             cds::intrusive::fcqueue::make_traits<
 209                 cds::intrusive::opt::disposer< disposer >
 210             >::type
 211         > queue_type;
 212
 213         queue_type q;
 214         test( q );
 215     }
 216
 217     TEST_F( IntrusiveFCQueue, member_mutex )
 218     {
 219         typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
 220         typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
 221
 222         struct traits : public cds::intrusive::fcqueue::traits
 223         {
 224             typedef IntrusiveFCQueue::disposer disposer;
 225             typedef std::mutex lock_type;
 226             typedef cds::intrusive::fcqueue::stat<> stat;
 227         };
 228         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >, traits > queue_type;
 229
 230         queue_type q;
 231         test( q );
 232     }
 233
 234     TEST_F( IntrusiveFCQueue, member_elimination )
 235     {
 236         typedef member_hook_item< boost::intrusive::list_member_hook<> > value_type;
 237         typedef boost::intrusive::member_hook<value_type, boost::intrusive::list_member_hook<>, &value_type::hMember> member_option;
 238
 239         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::list< value_type, member_option >,
 240             cds::intrusive::fcqueue::make_traits<
 241                 cds::intrusive::opt::disposer< disposer >
 242                 ,cds::opt::enable_elimination< true >
 243             >::type
 244         > queue_type;
 245
 246         queue_type q;
 247         test( q );
 248     }
 249
 250     TEST_F( IntrusiveFCQueue, slist_base )
 251     {
 252         typedef base_hook_item< boost::intrusive::slist_base_hook<>> value_type;
 253         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::slist< value_type, boost::intrusive::cache_last< true >>,
 254             cds::intrusive::fcqueue::make_traits<
 255                 cds::intrusive::opt::disposer< disposer >
 256             >::type
 257         > queue_type;
 258
 259         queue_type q;
 260         test( q );
 261     }
 262
 263     TEST_F( IntrusiveFCQueue, slist_base_elimination )
 264     {
 265         typedef base_hook_item< boost::intrusive::slist_base_hook<> > value_type;
 266         struct traits : public
 267             cds::intrusive::fcqueue::make_traits <
 268                 cds::intrusive::opt::disposer< disposer >
 269                 , cds::opt::enable_elimination < true >
 270                 , cds::opt::lock_type< std::mutex >
 271             > ::type
 272         {};
 273         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::slist< value_type, boost::intrusive::cache_last< true >>, traits > queue_type;
 274
 275         queue_type q;
 276         test( q );
 277     }
 278
 279     TEST_F( IntrusiveFCQueue, slist_member )
 280     {
 281         typedef member_hook_item< boost::intrusive::slist_member_hook<> > value_type;
 282         typedef boost::intrusive::member_hook<value_type, boost::intrusive::slist_member_hook<>, &value_type::hMember> member_option;
 283
 284         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::slist< value_type, member_option, boost::intrusive::cache_last< true >>,
 285             cds::intrusive::fcqueue::make_traits<
 286                 cds::intrusive::opt::disposer< disposer >
 287             >::type
 288         > queue_type;
 289
 290         queue_type q;
 291         test( q );
 292     }
 293
 294     TEST_F( IntrusiveFCQueue, slist_member_elimination )
 295     {
 296         typedef member_hook_item< boost::intrusive::slist_member_hook<> > value_type;
 297         typedef boost::intrusive::member_hook<value_type, boost::intrusive::slist_member_hook<>, &value_type::hMember> member_option;
 298
 299         typedef cds::intrusive::FCQueue< value_type, boost::intrusive::slist< value_type, member_option, boost::intrusive::cache_last< true >>,
 300             cds::intrusive::fcqueue::make_traits<
 301                 cds::intrusive::opt::disposer< disposer >
 302                 ,cds::opt::enable_elimination< true >
 303             >::type
 304         > queue_type;
 305
 306         queue_type q;
 307         test( q );
 308     }
 309
 310 } // namepace