+++ /dev/null
-/*
- This file is a part of libcds - Concurrent Data Structures library
-
- (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
-
- Source code repo: http://github.com/khizmax/libcds/
- Download: http://sourceforge.net/projects/libcds/files/
-
- Redistribution and use in source and binary forms, with or without
- modification, are permitted provided that the following conditions are met:
-
- * Redistributions of source code must retain the above copyright notice, this
- list of conditions and the following disclaimer.
-
- * Redistributions in binary form must reproduce the above copyright notice,
- this list of conditions and the following disclaimer in the documentation
- and/or other materials provided with the distribution.
-
- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
- AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
- FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
- SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
- CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
- OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-*/
-
-#ifndef CDSUNIT_NONCONCURRENT_ITERATOR_SEQUENCE_H
-#define CDSUNIT_NONCONCURRENT_ITERATOR_SEQUENCE_H
-
-#include <cds/details/bounded_array.h>
-#include <cds/atomic.h>
-#include <algorithm> // std::sort
-
-namespace map { namespace nonconcurrent_iterator {
-
- class Sequence
- {
- public:
- typedef int TKey;
- struct TValue {
- TKey keyControl ; // èñïîëüçóåòñÿ äëÿ êîíòðîëÿ, ÷òî äàííûå îòíîñÿòñÿ ê êëþ÷ó
- int nShuffle ; // ñëó÷àéíîå çíà÷åíèå, èñïîëüçóåìîå äëÿ ñîðòèðîâêè
- TValue * pOrigItem ; // óêàçàòåëü íà ýëåìåíò â ìàññèâå; òàê êàê ñïèñîê õðàíèò êîïèè,
- // òî ñ ïîìîùüþ ýòîãî ïîëÿ îðãàíèçóåòñÿ äîñòóï ê èñõîäíîìó ýëåìåíòó
-
- cds::atomics::item_counter<cds::membar_release> nAccess ; // ñ÷åò÷èê äîñòóïà ïðè îáõîäå ñïèñêà ïî èòåðàòîðàì
- // (Atomic, òàê êàê âîçìîæåí ïàðàëëåüíûé äîñòóï)
-
- TValue()
- {
- ++nConstructCount;
- }
- TValue( const TValue& v )
- {
- memcpy( this, &v, sizeof(*this) );
- ++nConstructCount;
- }
- ~TValue()
- {
- ++nDestructCount;
- }
- };
-
- struct Data {
- TKey key;
- TValue value;
- };
-
- protected:
- static size_t nConstructCount;
- static size_t nDestructCount;
-
- public:
- typedef cds::details::BoundedArray<Data> TDataArray;
- typedef TDataArray::const_iterator const_iterator;
-
- TDataArray arrData;
-
- const_iterator begin() const { return arrData.begin(); }
- const_iterator end() const { return arrData.end(); }
-
- public:
- Sequence( size_t nSize )
- : arrData( nSize )
- {}
-
- static unsigned int Rand( unsigned int nMax )
- {
- double rnd = double( rand() ) / double( RAND_MAX );
- unsigned int n = (unsigned int) (rnd * nMax);
- return n < nMax ? n : (n-1);
- }
-
- void generateSequence()
- {
- // Ãåíåðèðóåì òåñòîâûé ìàññèâ äàííûõ. Ìàññèâ äîëæåí áûòü ïåðåìåøàí ñëó÷àéíûì îáðàçîì, ïîýòîìó
- // â êà÷åñòâå çíà÷åíèÿ ïîëÿ value.nShuffle èñïîëüçóåì ñëó÷àéíîå, è ñîðòèðóåì ìàññèâ
- // ïî ýòîìó ñëó÷àéíîìó çíà÷åíèþ
-
- size_t nMax = arrData.capacity();
- for ( size_t i = 0; i < nMax; ++i ) {
- arrData[i].key = (unsigned int) i;
- arrData[i].value.keyControl = (unsigned int) i;
- arrData[i].value.nShuffle = Rand( (unsigned int) nMax );
- arrData[i].value.pOrigItem = &(arrData[i].value);
- arrData[i].value.nAccess.reset( cds::membar_relaxed::order );
- }
- }
-
- void restoreLinks()
- {
- size_t nMax = arrData.capacity();
- for ( size_t i = 0; i < nMax; ++i )
- arrData[i].value.pOrigItem = &(arrData[i].value);
- }
-
- static bool sortValue( const Data& p1, const Data&p2 )
- {
- return p1.value.nShuffle < p2.value.nShuffle;
- }
-
- void makeRandomSortedSequence()
- {
- std::sort( arrData.begin(), arrData.end(), sortValue );
- restoreLinks();
- }
-
- static bool sortAsc( const Data& p1, const Data&p2 )
- {
- return p1.key < p2.key;
- }
-
- void makeAscSortedSequence()
- {
- // Ñîðòèðóåò ìàññèâ â ïîðÿäêå âîçðàñòàíèÿ êëþ÷åé
- std::sort( arrData.begin(), arrData.end(), sortAsc );
- restoreLinks();
- }
-
- static bool sortDesc( const Data& p1, const Data&p2 )
- {
- return p2.key < p1.key;
- }
-
- void makeDescSortedSequence()
- {
- // Ñîðòèðóåò ìàññèâ â ïîðÿäêå óáûâàíèÿ êëþ÷åé
- std::sort( arrData.begin(), arrData.end(), sortDesc );
- restoreLinks();
- }
-
- void clearAccess()
- {
- size_t nMax = arrData.capacity();
- for ( size_t i = 0; i < nMax; ++i )
- arrData[i].value.nAccess.reset( cds::membar_relaxed::order );
- }
- };
-
-} } // namespace map::nonconcurrent_iterator
-
-#endif // #ifndef CDSUNIT_NONCONCURRENT_ITERATOR_SEQUENCE_H
projects / libcds.git / blobdiff