tests/unit/nonconcurrent_iterator_sequence.h

   1 //$$CDS-header$$
   2
   3 #ifndef __UNIT_NONCONCURRENT_ITERATOR_SEQUENCE_H
   4 #define __UNIT_NONCONCURRENT_ITERATOR_SEQUENCE_H
   5
   6 #include <cds/details/bounded_array.h>
   7 #include <cds/atomic.h>
   8 #include <algorithm>    // std::sort
   9
  10 namespace map { namespace nonconcurrent_iterator {
  11
  12     class Sequence
  13     {
  14     public:
  15         typedef int        TKey;
  16         struct TValue {
  17             TKey        keyControl    ;    // èñïîëüçóåòñÿ äëÿ êîíòðîëÿ, ÷òî äàííûå îòíîñÿòñÿ ê êëþ÷ó
  18             int            nShuffle    ;    // ñëó÷àéíîå çíà÷åíèå, èñïîëüçóåìîå äëÿ ñîðòèðîâêè
  19             TValue *    pOrigItem    ;    // óêàçàòåëü íà ýëåìåíò â ìàññèâå; òàê êàê ñïèñîê õðàíèò êîïèè,
  20                                         // òî ñ ïîìîùüþ ýòîãî ïîëÿ îðãàíèçóåòñÿ äîñòóï ê èñõîäíîìó ýëåìåíòó
  21
  22             cds::atomics::item_counter<cds::membar_release>   nAccess        ;    // ñ÷åò÷èê äîñòóïà ïðè îáõîäå ñïèñêà ïî èòåðàòîðàì
  23                                                 // (Atomic, òàê êàê âîçìîæåí ïàðàëëåüíûé äîñòóï)
  24
  25             TValue()
  26             {
  27                 ++nConstructCount;
  28             }
  29             TValue( const TValue& v )
  30             {
  31                 memcpy( this, &v, sizeof(*this) );
  32                 ++nConstructCount;
  33             }
  34             ~TValue()
  35             {
  36                 ++nDestructCount;
  37             }
  38         };
  39
  40         struct Data {
  41             TKey    key;
  42             TValue    value;
  43         };
  44
  45     protected:
  46         static size_t nConstructCount;
  47         static size_t nDestructCount;
  48
  49     public:
  50         typedef cds::details::BoundedArray<Data>        TDataArray;
  51         typedef TDataArray::const_iterator              const_iterator;
  52
  53         TDataArray                                        arrData;
  54
  55         const_iterator begin() const    { return arrData.begin(); }
  56         const_iterator end() const      { return arrData.end(); }
  57
  58     public:
  59         Sequence( size_t nSize )
  60             : arrData( nSize )
  61         {}
  62
  63         static unsigned int Rand( unsigned int nMax )
  64         {
  65             double rnd = double( rand() ) / double( RAND_MAX );
  66             unsigned int n = (unsigned int) (rnd * nMax);
  67             return n < nMax ? n : (n-1);
  68         }
  69
  70         void generateSequence()
  71         {
  72             // Ãåíåðèðóåì òåñòîâûé ìàññèâ äàííûõ. Ìàññèâ äîëæåí áûòü ïåðåìåøàí ñëó÷àéíûì îáðàçîì, ïîýòîìó
  73             // â êà÷åñòâå çíà÷åíèÿ ïîëÿ value.nShuffle èñïîëüçóåì ñëó÷àéíîå, è ñîðòèðóåì ìàññèâ
  74             // ïî ýòîìó ñëó÷àéíîìó çíà÷åíèþ
  75
  76             size_t nMax = arrData.capacity();
  77             for ( size_t i = 0; i < nMax; ++i ) {
  78                 arrData[i].key = (unsigned int) i;
  79                 arrData[i].value.keyControl = (unsigned int) i;
  80                 arrData[i].value.nShuffle = Rand( (unsigned int) nMax );
  81                 arrData[i].value.pOrigItem = &(arrData[i].value);
  82                 arrData[i].value.nAccess.reset( cds::membar_relaxed::order );
  83             }
  84         }
  85
  86         void restoreLinks()
  87         {
  88             size_t nMax = arrData.capacity();
  89             for ( size_t i = 0; i < nMax; ++i )
  90                 arrData[i].value.pOrigItem = &(arrData[i].value);
  91         }
  92
  93         static bool sortValue( const Data& p1, const Data&p2 )
  94         {
  95             return p1.value.nShuffle < p2.value.nShuffle;
  96         }
  97
  98         void makeRandomSortedSequence()
  99         {
 100             std::sort( arrData.begin(), arrData.end(), sortValue );
 101             restoreLinks();
 102         }
 103
 104         static bool sortAsc( const Data& p1, const Data&p2 )
 105         {
 106             return p1.key < p2.key;
 107         }
 108
 109         void makeAscSortedSequence()
 110         {
 111             // Ñîðòèðóåò ìàññèâ â ïîðÿäêå âîçðàñòàíèÿ êëþ÷åé
 112             std::sort( arrData.begin(), arrData.end(), sortAsc );
 113             restoreLinks();
 114         }
 115
 116         static bool sortDesc( const Data& p1, const Data&p2 )
 117         {
 118             return p2.key < p1.key;
 119         }
 120
 121         void makeDescSortedSequence()
 122         {
 123             // Ñîðòèðóåò ìàññèâ â ïîðÿäêå óáûâàíèÿ êëþ÷åé
 124             std::sort( arrData.begin(), arrData.end(), sortDesc );
 125             restoreLinks();
 126         }
 127
 128         void clearAccess()
 129         {
 130             size_t nMax = arrData.capacity();
 131             for ( size_t i = 0; i < nMax; ++i )
 132                 arrData[i].value.nAccess.reset( cds::membar_relaxed::order );
 133         }
 134     };
 135
 136 } } // namespace map::nonconcurrent_iterator
 137
 138 #endif    // #ifndef __UNIT_NONCONCURRENT_ITERATOR_SEQUENCE_H