3 #ifndef __UNIT_NONCONCURRENT_ITERATOR_SEQUENCE_H
4 #define __UNIT_NONCONCURRENT_ITERATOR_SEQUENCE_H
6 #include <cds/details/bounded_array.h>
7 #include <cds/atomic.h>
8 #include <algorithm> // std::sort
10 namespace map { namespace nonconcurrent_iterator {
17 TKey keyControl ; // èñïîëüçóåòñÿ äëÿ êîíòðîëÿ, ÷òî äàííûå îòíîñÿòñÿ ê êëþ÷ó
18 int nShuffle ; // ñëó÷àéíîå çíà÷åíèå, èñïîëüçóåìîå äëÿ ñîðòèðîâêè
19 TValue * pOrigItem ; // óêàçàòåëü íà ýëåìåíò â ìàññèâå; òàê êàê ñïèñîê õðàíèò êîïèè,
20 // òî ñ ïîìîùüþ ýòîãî ïîëÿ îðãàíèçóåòñÿ äîñòóï ê èñõîäíîìó ýëåìåíòó
22 cds::atomics::item_counter<cds::membar_release> nAccess ; // ñ÷åò÷èê äîñòóïà ïðè îáõîäå ñïèñêà ïî èòåðàòîðàì
23 // (Atomic, òàê êàê âîçìîæåí ïàðàëëåüíûé äîñòóï)
29 TValue( const TValue& v )
31 memcpy( this, &v, sizeof(*this) );
46 static size_t nConstructCount;
47 static size_t nDestructCount;
50 typedef cds::details::BoundedArray<Data> TDataArray;
51 typedef TDataArray::const_iterator const_iterator;
55 const_iterator begin() const { return arrData.begin(); }
56 const_iterator end() const { return arrData.end(); }
59 Sequence( size_t nSize )
63 static unsigned int Rand( unsigned int nMax )
65 double rnd = double( rand() ) / double( RAND_MAX );
66 unsigned int n = (unsigned int) (rnd * nMax);
67 return n < nMax ? n : (n-1);
70 void generateSequence()
72 // Ãåíåðèðóåì òåñòîâûé ìàññèâ äàííûõ. Ìàññèâ äîëæåí áûòü ïåðåìåøàí ñëó÷àéíûì îáðàçîì, ïîýòîìó
73 // â êà÷åñòâå çíà÷åíèÿ ïîëÿ value.nShuffle èñïîëüçóåì ñëó÷àéíîå, è ñîðòèðóåì ìàññèâ
74 // ïî ýòîìó ñëó÷àéíîìó çíà÷åíèþ
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 );
88 size_t nMax = arrData.capacity();
89 for ( size_t i = 0; i < nMax; ++i )
90 arrData[i].value.pOrigItem = &(arrData[i].value);
93 static bool sortValue( const Data& p1, const Data&p2 )
95 return p1.value.nShuffle < p2.value.nShuffle;
98 void makeRandomSortedSequence()
100 std::sort( arrData.begin(), arrData.end(), sortValue );
104 static bool sortAsc( const Data& p1, const Data&p2 )
106 return p1.key < p2.key;
109 void makeAscSortedSequence()
111 // Ñîðòèðóåò ìàññèâ â ïîðÿäêå âîçðàñòàíèÿ êëþ÷åé
112 std::sort( arrData.begin(), arrData.end(), sortAsc );
116 static bool sortDesc( const Data& p1, const Data&p2 )
118 return p2.key < p1.key;
121 void makeDescSortedSequence()
123 // Ñîðòèðóåò ìàññèâ â ïîðÿäêå óáûâàíèÿ êëþ÷åé
124 std::sort( arrData.begin(), arrData.end(), sortDesc );
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 );
136 } } // namespace map::nonconcurrent_iterator
138 #endif // #ifndef __UNIT_NONCONCURRENT_ITERATOR_SEQUENCE_H