1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052305330543055305630573058305930603061306230633064306530663067306830693070307130723073307430753076307730783079308030813082308330843085308630873088308930903091309230933094309530963097309830993100310131023103310431053106310731083109311031113112311331143115311631173118311931203121312231233124312531263127312831293130313131323133313431353136313731383139314031413142314331443145314631473148314931503151315231533154315531563157315831593160316131623163316431653166316731683169317031713172317331743175317631773178317931803181318231833184318531863187318831893190319131923193319431953196319731983199320032013202320332043205320632073208320932103211321232133214321532163217321832193220322132223223322432253226322732283229323032313232323332343235323632373238323932403241324232433244324532463247324832493250325132523253325432553256325732583259326032613262326332643265326632673268326932703271327232733274327532763277327832793280328132823283328432853286328732883289329032913292329332943295329632973298329933003301330233033304330533063307330833093310331133123313331433153316331733183319332033213322332333243325332633273328332933303331333233333334333533363337333833393340334133423343334433453346334733483349335033513352335333543355335633573358335933603361336233633364336533663367336833693370337133723373337433753376337733783379338033813382338333843385338633873388338933903391339233933394339533963397339833993400340134023403340434053406340734083409341034113412341334143415341634173418341934203421342234233424342534263427342834293430343134323433343434353436343734383439344034413442344334443445344634473448344934503451345234533454345534563457345834593460346134623463346434653466346734683469347034713472347334743475347634773478347934803481348234833484348534863487348834893490349134923493349434953496349734983499350035013502350335043505350635073508350935103511351235133514351535163517351835193520352135223523352435253526352735283529353035313532353335343535353635373538353935403541354235433544354535463547354835493550355135523553355435553556355735583559356035613562356335643565356635673568356935703571357235733574357535763577357835793580358135823583358435853586358735883589359035913592359335943595359635973598359936003601360236033604360536063607360836093610361136123613361436153616361736183619362036213622362336243625362636273628362936303631363236333634363536363637363836393640364136423643364436453646364736483649365036513652365336543655365636573658365936603661366236633664366536663667366836693670367136723673367436753676367736783679368036813682368336843685368636873688368936903691369236933694369536963697369836993700370137023703370437053706370737083709371037113712371337143715371637173718371937203721372237233724372537263727372837293730373137323733373437353736373737383739374037413742374337443745374637473748374937503751375237533754375537563757375837593760376137623763376437653766376737683769377037713772377337743775377637773778377937803781378237833784378537863787378837893790379137923793379437953796379737983799380038013802380338043805380638073808380938103811381238133814381538163817381838193820382138223823382438253826382738283829383038313832383338343835383638373838383938403841384238433844384538463847384838493850385138523853385438553856385738583859386038613862386338643865386638673868386938703871387238733874387538763877387838793880388138823883388438853886388738883889389038913892389338943895389638973898389939003901390239033904390539063907390839093910391139123913391439153916391739183919392039213922392339243925392639273928392939303931393239333934393539363937393839393940394139423943394439453946394739483949395039513952395339543955395639573958395939603961396239633964396539663967396839693970397139723973397439753976397739783979398039813982398339843985398639873988398939903991399239933994399539963997399839994000400140024003400440054006400740084009401040114012401340144015401640174018401940204021402240234024402540264027402840294030403140324033403440354036403740384039404040414042404340444045404640474048404940504051405240534054405540564057405840594060406140624063406440654066406740684069407040714072407340744075407640774078407940804081408240834084408540864087408840894090409140924093409440954096409740984099410041014102410341044105410641074108410941104111411241134114411541164117411841194120412141224123412441254126412741284129413041314132413341344135413641374138413941404141414241434144414541464147414841494150415141524153415441554156415741584159416041614162416341644165416641674168416941704171417241734174417541764177417841794180418141824183418441854186418741884189419041914192419341944195419641974198419942004201420242034204420542064207420842094210421142124213421442154216421742184219422042214222422342244225422642274228422942304231423242334234423542364237423842394240424142424243424442454246424742484249425042514252425342544255425642574258425942604261426242634264426542664267426842694270427142724273427442754276427742784279428042814282428342844285428642874288428942904291429242934294429542964297429842994300430143024303430443054306430743084309431043114312431343144315431643174318431943204321432243234324432543264327432843294330433143324333433443354336433743384339434043414342434343444345434643474348434943504351435243534354435543564357435843594360436143624363 |
- #ifndef BOOST_INTRUSIVE_HASHTABLE_HPP
- #define BOOST_INTRUSIVE_HASHTABLE_HPP
- #include <boost/intrusive/detail/config_begin.hpp>
- #include <boost/intrusive/intrusive_fwd.hpp>
- #include <boost/intrusive/detail/hashtable_node.hpp>
- #include <boost/intrusive/detail/transform_iterator.hpp>
- #include <boost/intrusive/link_mode.hpp>
- #include <boost/intrusive/detail/ebo_functor_holder.hpp>
- #include <boost/intrusive/detail/is_stateful_value_traits.hpp>
- #include <boost/intrusive/detail/node_to_value.hpp>
- #include <boost/intrusive/detail/exception_disposer.hpp>
- #include <boost/intrusive/detail/node_cloner_disposer.hpp>
- #include <boost/intrusive/detail/simple_disposers.hpp>
- #include <boost/intrusive/detail/size_holder.hpp>
- #include <boost/intrusive/detail/iterator.hpp>
- #include <boost/intrusive/detail/get_value_traits.hpp>
- #include <boost/intrusive/detail/algorithm.hpp>
- #include <boost/intrusive/detail/value_functors.hpp>
- #include <boost/intrusive/unordered_set_hook.hpp>
- #include <boost/intrusive/detail/slist_iterator.hpp>
- #include <boost/intrusive/pointer_traits.hpp>
- #include <boost/intrusive/detail/mpl.hpp>
- #include <boost/intrusive/circular_slist_algorithms.hpp>
- #include <boost/intrusive/linear_slist_algorithms.hpp>
- #include <boost/container_hash/hash.hpp>
- #include <boost/intrusive/detail/assert.hpp>
- #include <boost/static_assert.hpp>
- #include <boost/move/utility_core.hpp>
- #include <boost/move/adl_move_swap.hpp>
- #include <boost/move/algo/detail/search.hpp>
- #include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair
- #include <cstddef> //std::size_t
- #include <boost/cstdint.hpp> //std::uint64_t
- #if defined(BOOST_HAS_PRAGMA_ONCE)
- # pragma once
- #endif
- #ifdef _MSC_VER
- #include <intrin.h>
- #endif
- namespace boost {
- namespace intrusive {
- #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
- #ifdef _WIN64
- # define BOOST_INTRUSIVE_SIZE_C(NUMBER) NUMBER##ULL
- # define BOOST_INTRUSIVE_64_BIT_SIZE_T 1
- #else
- # define BOOST_INTRUSIVE_SIZE_C(NUMBER) NUMBER##UL
- # define BOOST_INTRUSIVE_64_BIT_SIZE_T (((((ULONG_MAX>>16)>>16)>>16)>>15) != 0)
- #endif
- template<int Dummy = 0>
- struct prime_list_holder
- {
- private:
- template <class SizeType>
- static BOOST_INTRUSIVE_FORCEINLINE SizeType truncate_size_type(std::size_t n, detail::true_)
- { return n < std::size_t(SizeType(-1)) ? static_cast<SizeType>(n) : SizeType(-1); }
- template <class SizeType>
- static BOOST_INTRUSIVE_FORCEINLINE SizeType truncate_size_type(std::size_t n, detail::false_)
- { return static_cast<SizeType>(n); }
- static const std::size_t prime_list[];
- static const std::size_t prime_list_size;
- static const std::size_t *suggested_lower_bucket_count_ptr(std::size_t n)
- {
- const std::size_t *primes = &prime_list[0];
- const std::size_t *primes_end = primes + prime_list_size;
- std::size_t const* bound =
- boost::movelib::lower_bound(primes, primes_end, n, value_less<std::size_t>());
- bound -= std::size_t(bound == primes_end);
- return bound;
- }
- static const std::size_t *suggested_upper_bucket_count_ptr(std::size_t n)
- {
- const std::size_t *primes = &prime_list[0];
- const std::size_t *primes_end = primes + prime_list_size;
- std::size_t const* bound =
- boost::movelib::upper_bound(primes, primes_end, n, value_less<std::size_t>());
- bound -= std::size_t(bound == primes_end);
- return bound;
- }
- static std::size_t suggested_lower_bucket_count_impl(std::size_t n)
- { return *suggested_lower_bucket_count_ptr(n); }
- static std::size_t suggested_upper_bucket_count_impl(std::size_t n)
- { return *suggested_upper_bucket_count_ptr(n); }
- public:
- template <class SizeType>
- static BOOST_INTRUSIVE_FORCEINLINE SizeType suggested_upper_bucket_count(SizeType n)
- {
- std::size_t const c = suggested_upper_bucket_count_impl(static_cast<std::size_t>(n));
- return truncate_size_type<SizeType>(c, detail::bool_<(sizeof(SizeType) < sizeof(std::size_t))>());
- }
- template <class SizeType>
- static BOOST_INTRUSIVE_FORCEINLINE SizeType suggested_lower_bucket_count(SizeType n)
- {
- std::size_t const c = suggested_lower_bucket_count_impl(static_cast<std::size_t>(n));
- return truncate_size_type<SizeType>(c, detail::bool_<(sizeof(SizeType) < sizeof(std::size_t))>());
- }
- static BOOST_INTRUSIVE_FORCEINLINE std::size_t suggested_lower_bucket_count_idx(std::size_t n)
- { return static_cast<std::size_t>(suggested_lower_bucket_count_ptr(n) - &prime_list[0]); }
- static BOOST_INTRUSIVE_FORCEINLINE std::size_t suggested_upper_bucket_count_idx(std::size_t n)
- { return static_cast<std::size_t>(suggested_upper_bucket_count_ptr(n) - &prime_list[0]); }
- static BOOST_INTRUSIVE_FORCEINLINE std::size_t size_from_index(std::size_t n)
- { return prime_list[std::ptrdiff_t(n)]; }
- template<std::size_t SizeIndex>
- BOOST_INTRUSIVE_FORCEINLINE static std::size_t modfunc(std::size_t hash) { return hash % SizeIndex; }
- static std::size_t(*const positions[])(std::size_t);
- #if BOOST_INTRUSIVE_64_BIT_SIZE_T
- static const uint64_t inv_sizes32[];
- static const std::size_t inv_sizes32_size;
- #endif
- BOOST_INTRUSIVE_FORCEINLINE static std::size_t lower_size_index(std::size_t n)
- { return prime_list_holder<>::suggested_lower_bucket_count_idx(n); }
- BOOST_INTRUSIVE_FORCEINLINE static std::size_t upper_size_index(std::size_t n)
- { return prime_list_holder<>::suggested_upper_bucket_count_idx(n); }
- BOOST_INTRUSIVE_FORCEINLINE static std::size_t size(std::size_t size_index)
- { return prime_list_holder<>::size_from_index(size_index); }
- #if BOOST_INTRUSIVE_64_BIT_SIZE_T
-
- BOOST_INTRUSIVE_FORCEINLINE static uint64_t mul128_u32(uint64_t lowbits, uint32_t d)
- {
- #if defined(_MSC_VER)
- return __umulh(lowbits, d);
- #elif defined(BOOST_HAS_INT128)
- return static_cast<uint64_t>((uint128_type(lowbits) * d) >> 64);
- #else
- uint64_t r1 = (lowbits & UINT32_MAX) * d;
- uint64_t r2 = (lowbits >> 32) * d;
- r2 += r1 >> 32;
- return r2 >> 32;
- #endif
- }
- BOOST_INTRUSIVE_FORCEINLINE static uint32_t fastmod_u32(uint32_t a, uint64_t M, uint32_t d)
- {
- uint64_t lowbits = M * a;
- return (uint32_t)(mul128_u32(lowbits, d));
- }
- #endif
- BOOST_INTRUSIVE_FORCEINLINE static std::size_t position(std::size_t hash,std::size_t size_index)
- {
- #if BOOST_INTRUSIVE_64_BIT_SIZE_T
- BOOST_CONSTEXPR_OR_CONST std::size_t sizes_under_32bit = sizeof(inv_sizes32)/sizeof(inv_sizes32[0]);
- if(BOOST_LIKELY(size_index < sizes_under_32bit)){
- return fastmod_u32( uint32_t(hash)+uint32_t(hash>>32)
- , inv_sizes32[size_index]
- , uint32_t(prime_list[size_index]) );
- }
- else{
- return positions[size_index](hash);
- }
- #else
- return positions[size_index](hash);
- #endif
- }
- };
- template<int Dummy>
- std::size_t(* const prime_list_holder<Dummy>::positions[])(std::size_t) =
- {
- modfunc<BOOST_INTRUSIVE_SIZE_C(3)>, modfunc<BOOST_INTRUSIVE_SIZE_C(7)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(11)>, modfunc<BOOST_INTRUSIVE_SIZE_C(17)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(29)>, modfunc<BOOST_INTRUSIVE_SIZE_C(53)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(97)>, modfunc<BOOST_INTRUSIVE_SIZE_C(193)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(389)>, modfunc<BOOST_INTRUSIVE_SIZE_C(769)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(1543)>, modfunc<BOOST_INTRUSIVE_SIZE_C(3079)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(6151)>, modfunc<BOOST_INTRUSIVE_SIZE_C(12289)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(24593)>, modfunc<BOOST_INTRUSIVE_SIZE_C(49157)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(98317)>, modfunc<BOOST_INTRUSIVE_SIZE_C(196613)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(393241)>, modfunc<BOOST_INTRUSIVE_SIZE_C(786433)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(1572869)>, modfunc<BOOST_INTRUSIVE_SIZE_C(3145739)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(6291469)>, modfunc<BOOST_INTRUSIVE_SIZE_C(12582917)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(25165843)>, modfunc<BOOST_INTRUSIVE_SIZE_C(50331653)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(100663319)>, modfunc<BOOST_INTRUSIVE_SIZE_C(201326611)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(402653189)>, modfunc<BOOST_INTRUSIVE_SIZE_C(805306457)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(1610612741)>,
- #if BOOST_INTRUSIVE_64_BIT_SIZE_T
-
- modfunc<BOOST_INTRUSIVE_SIZE_C(3221225473)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(6442450939)>, modfunc<BOOST_INTRUSIVE_SIZE_C(12884901893)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(25769803751)>, modfunc<BOOST_INTRUSIVE_SIZE_C(51539607551)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(103079215111)>, modfunc<BOOST_INTRUSIVE_SIZE_C(206158430209)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(412316860441)>, modfunc<BOOST_INTRUSIVE_SIZE_C(824633720831)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(1649267441651)>, modfunc<BOOST_INTRUSIVE_SIZE_C(3298534883309)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(6597069766657)>, modfunc<BOOST_INTRUSIVE_SIZE_C(13194139533299)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(26388279066623)>, modfunc<BOOST_INTRUSIVE_SIZE_C(52776558133303)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(105553116266489)>, modfunc<BOOST_INTRUSIVE_SIZE_C(211106232532969)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(422212465066001)>, modfunc<BOOST_INTRUSIVE_SIZE_C(844424930131963)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(1688849860263953)>, modfunc<BOOST_INTRUSIVE_SIZE_C(3377699720527861)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(6755399441055731)>, modfunc<BOOST_INTRUSIVE_SIZE_C(13510798882111483)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(27021597764222939)>, modfunc<BOOST_INTRUSIVE_SIZE_C(54043195528445957)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(108086391056891903)>, modfunc<BOOST_INTRUSIVE_SIZE_C(216172782113783843)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(432345564227567621)>, modfunc<BOOST_INTRUSIVE_SIZE_C(864691128455135207)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(1729382256910270481)>, modfunc<BOOST_INTRUSIVE_SIZE_C(3458764513820540933)>,
- modfunc<BOOST_INTRUSIVE_SIZE_C(6917529027641081903)>, modfunc<BOOST_INTRUSIVE_SIZE_C(9223372036854775783)>
- #else
- modfunc<BOOST_INTRUSIVE_SIZE_C(2147483647)>
- #endif
- };
- template<int Dummy>
- const std::size_t prime_list_holder<Dummy>::prime_list[] = {
- BOOST_INTRUSIVE_SIZE_C(3), BOOST_INTRUSIVE_SIZE_C(7),
- BOOST_INTRUSIVE_SIZE_C(11), BOOST_INTRUSIVE_SIZE_C(17),
- BOOST_INTRUSIVE_SIZE_C(29), BOOST_INTRUSIVE_SIZE_C(53),
- BOOST_INTRUSIVE_SIZE_C(97), BOOST_INTRUSIVE_SIZE_C(193),
- BOOST_INTRUSIVE_SIZE_C(389), BOOST_INTRUSIVE_SIZE_C(769),
- BOOST_INTRUSIVE_SIZE_C(1543), BOOST_INTRUSIVE_SIZE_C(3079),
- BOOST_INTRUSIVE_SIZE_C(6151), BOOST_INTRUSIVE_SIZE_C(12289),
- BOOST_INTRUSIVE_SIZE_C(24593), BOOST_INTRUSIVE_SIZE_C(49157),
- BOOST_INTRUSIVE_SIZE_C(98317), BOOST_INTRUSIVE_SIZE_C(196613),
- BOOST_INTRUSIVE_SIZE_C(393241), BOOST_INTRUSIVE_SIZE_C(786433),
- BOOST_INTRUSIVE_SIZE_C(1572869), BOOST_INTRUSIVE_SIZE_C(3145739),
- BOOST_INTRUSIVE_SIZE_C(6291469), BOOST_INTRUSIVE_SIZE_C(12582917),
- BOOST_INTRUSIVE_SIZE_C(25165843), BOOST_INTRUSIVE_SIZE_C(50331653),
- BOOST_INTRUSIVE_SIZE_C(100663319), BOOST_INTRUSIVE_SIZE_C(201326611),
- BOOST_INTRUSIVE_SIZE_C(402653189), BOOST_INTRUSIVE_SIZE_C(805306457),
- BOOST_INTRUSIVE_SIZE_C(1610612741),
- #if BOOST_INTRUSIVE_64_BIT_SIZE_T
-
- BOOST_INTRUSIVE_SIZE_C(3221225473),
- BOOST_INTRUSIVE_SIZE_C(6442450939), BOOST_INTRUSIVE_SIZE_C(12884901893),
- BOOST_INTRUSIVE_SIZE_C(25769803751), BOOST_INTRUSIVE_SIZE_C(51539607551),
- BOOST_INTRUSIVE_SIZE_C(103079215111), BOOST_INTRUSIVE_SIZE_C(206158430209),
- BOOST_INTRUSIVE_SIZE_C(412316860441), BOOST_INTRUSIVE_SIZE_C(824633720831),
- BOOST_INTRUSIVE_SIZE_C(1649267441651), BOOST_INTRUSIVE_SIZE_C(3298534883309),
- BOOST_INTRUSIVE_SIZE_C(6597069766657), BOOST_INTRUSIVE_SIZE_C(13194139533299),
- BOOST_INTRUSIVE_SIZE_C(26388279066623), BOOST_INTRUSIVE_SIZE_C(52776558133303),
- BOOST_INTRUSIVE_SIZE_C(105553116266489), BOOST_INTRUSIVE_SIZE_C(211106232532969),
- BOOST_INTRUSIVE_SIZE_C(422212465066001), BOOST_INTRUSIVE_SIZE_C(844424930131963),
- BOOST_INTRUSIVE_SIZE_C(1688849860263953), BOOST_INTRUSIVE_SIZE_C(3377699720527861),
- BOOST_INTRUSIVE_SIZE_C(6755399441055731), BOOST_INTRUSIVE_SIZE_C(13510798882111483),
- BOOST_INTRUSIVE_SIZE_C(27021597764222939), BOOST_INTRUSIVE_SIZE_C(54043195528445957),
- BOOST_INTRUSIVE_SIZE_C(108086391056891903), BOOST_INTRUSIVE_SIZE_C(216172782113783843),
- BOOST_INTRUSIVE_SIZE_C(432345564227567621), BOOST_INTRUSIVE_SIZE_C(864691128455135207),
- BOOST_INTRUSIVE_SIZE_C(1729382256910270481), BOOST_INTRUSIVE_SIZE_C(3458764513820540933),
- BOOST_INTRUSIVE_SIZE_C(6917529027641081903), BOOST_INTRUSIVE_SIZE_C(9223372036854775783)
- #else
- BOOST_INTRUSIVE_SIZE_C(2147483647)
- #endif
- };
- template<int Dummy>
- const std::size_t prime_list_holder<Dummy>::prime_list_size
- = sizeof(prime_list) / sizeof(std::size_t);
- #if BOOST_INTRUSIVE_64_BIT_SIZE_T
- template<int Dummy>
- const uint64_t prime_list_holder<Dummy>::inv_sizes32[] = {
- BOOST_INTRUSIVE_SIZE_C(6148914691236517206),
- BOOST_INTRUSIVE_SIZE_C(2635249153387078803),
- BOOST_INTRUSIVE_SIZE_C(1676976733973595602),
- BOOST_INTRUSIVE_SIZE_C(1085102592571150096),
- BOOST_INTRUSIVE_SIZE_C(636094623231363849),
- BOOST_INTRUSIVE_SIZE_C(348051774975651918),
- BOOST_INTRUSIVE_SIZE_C(190172619316593316),
- BOOST_INTRUSIVE_SIZE_C(95578984837873325),
- BOOST_INTRUSIVE_SIZE_C(47420935922132524),
- BOOST_INTRUSIVE_SIZE_C(23987963684927896),
- BOOST_INTRUSIVE_SIZE_C(11955116055547344),
- BOOST_INTRUSIVE_SIZE_C(5991147799191151),
- BOOST_INTRUSIVE_SIZE_C(2998982941588287),
- BOOST_INTRUSIVE_SIZE_C(1501077717772769),
- BOOST_INTRUSIVE_SIZE_C(750081082979285),
- BOOST_INTRUSIVE_SIZE_C(375261795343686),
- BOOST_INTRUSIVE_SIZE_C(187625172388393),
- BOOST_INTRUSIVE_SIZE_C(93822606204624),
- BOOST_INTRUSIVE_SIZE_C(46909513691883),
- BOOST_INTRUSIVE_SIZE_C(23456218233098),
- BOOST_INTRUSIVE_SIZE_C(11728086747027),
- BOOST_INTRUSIVE_SIZE_C(5864041509391),
- BOOST_INTRUSIVE_SIZE_C(2932024948977),
- BOOST_INTRUSIVE_SIZE_C(1466014921160),
- BOOST_INTRUSIVE_SIZE_C(733007198436),
- BOOST_INTRUSIVE_SIZE_C(366503839517),
- BOOST_INTRUSIVE_SIZE_C(183251896093),
- BOOST_INTRUSIVE_SIZE_C(91625960335),
- BOOST_INTRUSIVE_SIZE_C(45812983922),
- BOOST_INTRUSIVE_SIZE_C(22906489714),
- BOOST_INTRUSIVE_SIZE_C(11453246088),
- BOOST_INTRUSIVE_SIZE_C(5726623060)
- };
- template<int Dummy>
- const std::size_t prime_list_holder<Dummy>::inv_sizes32_size
- = sizeof(inv_sizes32) / sizeof(uint64_t);
- #endif
- struct prime_fmod_size : prime_list_holder<>
- {
- };
- #undef BOOST_INTRUSIVE_SIZE_C
- #undef BOOST_INTRUSIVE_64_BIT_SIZE_T
- #endif
- template<class InputIt, class T>
- InputIt priv_algo_find(InputIt first, InputIt last, const T& value)
- {
- for (; first != last; ++first) {
- if (*first == value) {
- return first;
- }
- }
- return last;
- }
- template<class InputIt, class T>
- typename boost::intrusive::iterator_traits<InputIt>::difference_type
- priv_algo_count(InputIt first, InputIt last, const T& value)
- {
- typename boost::intrusive::iterator_traits<InputIt>::difference_type ret = 0;
- for (; first != last; ++first) {
- if (*first == value) {
- ret++;
- }
- }
- return ret;
- }
- template <class ForwardIterator1, class ForwardIterator2>
- bool priv_algo_is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)
- {
- typedef typename
- boost::intrusive::iterator_traits<ForwardIterator2>::difference_type
- distance_type;
-
-
- for ( ; first1 != last1; ++first1, ++first2){
- if (! (*first1 == *first2))
- break;
- }
- if (first1 == last1){
- return true;
- }
-
-
- ForwardIterator2 last2 = first2;
- boost::intrusive::iterator_advance(last2, boost::intrusive::iterator_distance(first1, last1));
- for(ForwardIterator1 scan = first1; scan != last1; ++scan){
- if (scan != (priv_algo_find)(first1, scan, *scan)){
- continue;
- }
- distance_type matches = (priv_algo_count)(first2, last2, *scan);
- if (0 == matches || (priv_algo_count)(scan, last1, *scan) != matches){
- return false;
- }
- }
- return true;
- }
- struct hash_bool_flags
- {
- static const std::size_t unique_keys_pos = 1u;
- static const std::size_t constant_time_size_pos = 2u;
- static const std::size_t power_2_buckets_pos = 4u;
- static const std::size_t cache_begin_pos = 8u;
- static const std::size_t compare_hash_pos = 16u;
- static const std::size_t incremental_pos = 32u;
- static const std::size_t linear_buckets_pos = 64u;
- static const std::size_t fastmod_buckets_pos = 128u;
- };
- template<class Bucket, class Algo, class Disposer, class SizeType>
- class exception_bucket_disposer
- {
- Bucket *cont_;
- Disposer &disp_;
- const SizeType &constructed_;
- exception_bucket_disposer(const exception_bucket_disposer&);
- exception_bucket_disposer &operator=(const exception_bucket_disposer&);
- public:
- exception_bucket_disposer
- (Bucket &cont, Disposer &disp, const SizeType &constructed)
- : cont_(&cont), disp_(disp), constructed_(constructed)
- {}
- BOOST_INTRUSIVE_FORCEINLINE void release()
- { cont_ = 0; }
- ~exception_bucket_disposer()
- {
- SizeType n = constructed_;
- if(cont_){
- while(n--){
- Algo::detach_and_dispose(cont_[n].get_node_ptr(), disp_);
- }
- }
- }
- };
- template<class SupposedValueTraits>
- struct unordered_bucket_impl
- {
- typedef typename detail::get_node_traits
- <SupposedValueTraits>::type node_traits;
- typedef typename reduced_slist_node_traits
- <node_traits>::type reduced_node_traits;
- typedef bucket_impl<reduced_node_traits> type;
- typedef typename pointer_traits
- <typename reduced_node_traits::node_ptr>
- ::template rebind_pointer<type>::type pointer;
- };
- template<class SupposedValueTraits>
- struct unordered_bucket_ptr_impl
- {
- typedef typename unordered_bucket_impl<SupposedValueTraits>::pointer type;
- };
- template <class BucketPtr, class SizeType>
- struct bucket_traits_impl
- {
- private:
- BOOST_COPYABLE_AND_MOVABLE(bucket_traits_impl)
- public:
-
- typedef BucketPtr bucket_ptr;
- typedef SizeType size_type;
-
- BOOST_INTRUSIVE_FORCEINLINE bucket_traits_impl(bucket_ptr buckets, size_type len)
- : buckets_(buckets), buckets_len_(len)
- {}
- BOOST_INTRUSIVE_FORCEINLINE bucket_traits_impl(const bucket_traits_impl& x)
- : buckets_(x.buckets_), buckets_len_(x.buckets_len_)
- {}
- BOOST_INTRUSIVE_FORCEINLINE bucket_traits_impl(BOOST_RV_REF(bucket_traits_impl) x)
- : buckets_(x.buckets_), buckets_len_(x.buckets_len_)
- {
- x.buckets_ = bucket_ptr(); x.buckets_len_ = 0u;
- }
- BOOST_INTRUSIVE_FORCEINLINE bucket_traits_impl& operator=(BOOST_RV_REF(bucket_traits_impl) x)
- {
- buckets_ = x.buckets_; buckets_len_ = x.buckets_len_;
- x.buckets_ = bucket_ptr(); x.buckets_len_ = 0u; return *this;
- }
- BOOST_INTRUSIVE_FORCEINLINE bucket_traits_impl& operator=(BOOST_COPY_ASSIGN_REF(bucket_traits_impl) x)
- {
- buckets_ = x.buckets_; buckets_len_ = x.buckets_len_; return *this;
- }
- BOOST_INTRUSIVE_FORCEINLINE bucket_ptr bucket_begin() const
- {
- return buckets_;
- }
- BOOST_INTRUSIVE_FORCEINLINE size_type bucket_count() const BOOST_NOEXCEPT
- {
- return buckets_len_;
- }
- private:
- bucket_ptr buckets_;
- size_type buckets_len_;
- };
- template <class T>
- struct store_hash_is_true
- {
- template<bool Add>
- struct two_or_three {detail::yes_type _[2u + (unsigned)Add];};
- template <class U> static detail::yes_type test(...);
- template <class U> static two_or_three<U::store_hash> test (int);
- static const bool value = sizeof(test<T>(0)) > sizeof(detail::yes_type)*2u;
- };
- template <class T>
- struct optimize_multikey_is_true
- {
- template<bool Add>
- struct two_or_three { detail::yes_type _[2u + (unsigned)Add];};
- template <class U> static detail::yes_type test(...);
- template <class U> static two_or_three<U::optimize_multikey> test (int);
- static const bool value = sizeof(test<T>(0)) > sizeof(detail::yes_type)*2u;
- };
- template<bool StoreHash>
- struct insert_commit_data_impl
- {
- std::size_t hash;
- std::size_t bucket_idx;
- BOOST_INTRUSIVE_FORCEINLINE std::size_t get_hash() const
- { return hash; }
- BOOST_INTRUSIVE_FORCEINLINE void set_hash(std::size_t h)
- { hash = h; }
- };
- template<>
- struct insert_commit_data_impl<false>
- {
- std::size_t bucket_idx;
- BOOST_INTRUSIVE_FORCEINLINE std::size_t get_hash() const
- { return 0U; }
- BOOST_INTRUSIVE_FORCEINLINE void set_hash(std::size_t)
- {}
- };
- template<class Node, class SlistNodePtr>
- BOOST_INTRUSIVE_FORCEINLINE typename pointer_traits<SlistNodePtr>::template rebind_pointer<Node>::type
- dcast_bucket_ptr(const SlistNodePtr &p)
- {
- typedef typename pointer_traits<SlistNodePtr>::template rebind_pointer<Node>::type node_ptr;
- return pointer_traits<node_ptr>::pointer_to(static_cast<Node&>(*p));
- }
- template<class NodeTraits>
- struct group_functions
- {
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- typedef NodeTraits node_traits;
- typedef unordered_group_adapter<node_traits> group_traits;
- typedef typename node_traits::node_ptr node_ptr;
- typedef typename node_traits::node node;
- typedef typename reduced_slist_node_traits
- <node_traits>::type reduced_node_traits;
- typedef typename reduced_node_traits::node_ptr slist_node_ptr;
- typedef typename reduced_node_traits::node slist_node;
- typedef circular_slist_algorithms<group_traits> group_algorithms;
- typedef circular_slist_algorithms<node_traits> node_algorithms;
- static slist_node_ptr get_bucket_before_begin
- (slist_node_ptr bucket_beg, slist_node_ptr bucket_last, slist_node_ptr sp, detail::true_)
- {
-
-
-
- node_ptr p = dcast_bucket_ptr<node>(sp);
- node_ptr prev_node = p;
- node_ptr nxt(node_traits::get_next(p));
- while(!(bucket_beg <= nxt && nxt <= bucket_last) &&
- (group_traits::get_next(nxt) == prev_node)){
- prev_node = nxt;
- nxt = node_traits::get_next(nxt);
- }
-
- if(bucket_beg <= nxt && nxt <= bucket_last){
- return nxt;
- }
-
- node_ptr first_node_of_group = nxt;
- node_ptr last_node_group = group_traits::get_next(first_node_of_group);
- slist_node_ptr possible_end = node_traits::get_next(last_node_group);
- while(!(bucket_beg <= possible_end && possible_end <= bucket_last)){
- first_node_of_group = dcast_bucket_ptr<node>(possible_end);
- last_node_group = group_traits::get_next(first_node_of_group);
- possible_end = node_traits::get_next(last_node_group);
- }
- return possible_end;
- }
- static slist_node_ptr get_bucket_before_begin
- (slist_node_ptr bucket_beg, slist_node_ptr bucket_last, slist_node_ptr sp, detail::false_)
- {
-
-
- while (!(bucket_beg <= sp && sp <= bucket_last)){
- sp = reduced_node_traits::get_next(sp);
- }
- return sp;
- }
- static node_ptr get_prev_to_first_in_group(slist_node_ptr bucket_node, node_ptr first_in_group)
- {
- node_ptr nb = dcast_bucket_ptr<node>(bucket_node);
- node_ptr n;
- while((n = node_traits::get_next(nb)) != first_in_group){
- nb = group_traits::get_next(n);
- }
- return nb;
- }
- static void erase_from_group(slist_node_ptr end_ptr, node_ptr to_erase_ptr, detail::true_)
- {
- node_ptr const nxt_ptr(node_traits::get_next(to_erase_ptr));
-
-
- if(nxt_ptr != end_ptr && to_erase_ptr == group_traits::get_next(nxt_ptr)){
- group_algorithms::unlink_after(nxt_ptr);
- }
- }
- BOOST_INTRUSIVE_FORCEINLINE static void erase_from_group(slist_node_ptr, node_ptr, detail::false_)
- {}
- BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_last_in_group(node_ptr first_in_group, detail::true_)
- { return group_traits::get_next(first_in_group); }
- BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_last_in_group(node_ptr n, detail::false_)
- { return n; }
- static node_ptr get_first_in_group(node_ptr n, detail::true_)
- {
- node_ptr ng;
- while(n == node_traits::get_next((ng = group_traits::get_next(n)))){
- n = ng;
- }
- return n;
- }
- BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_first_in_group(node_ptr n, detail::false_)
- { return n; }
- BOOST_INTRUSIVE_FORCEINLINE static bool is_first_in_group(node_ptr ptr)
- { return node_traits::get_next(group_traits::get_next(ptr)) != ptr; }
- BOOST_INTRUSIVE_FORCEINLINE static void insert_in_group(node_ptr first_in_group, node_ptr n, detail::true_)
- { group_algorithms::link_after(first_in_group, n); }
- BOOST_INTRUSIVE_FORCEINLINE static void insert_in_group(node_ptr, node_ptr, detail::false_)
- {}
-
-
- static node_ptr split_group(node_ptr const new_first)
- {
- node_ptr const old_first((get_first_in_group)(new_first, detail::true_()));
-
- if(old_first != new_first){
- node_ptr const last = group_traits::get_next(old_first);
- group_traits::set_next(old_first, group_traits::get_next(new_first));
- group_traits::set_next(new_first, last);
- }
- return old_first;
- }
- };
- template<class BucketType, class SplitTraits, class SlistNodeAlgorithms>
- class incremental_rehash_rollback
- {
- private:
- typedef BucketType bucket_type;
- typedef SplitTraits split_traits;
- incremental_rehash_rollback();
- incremental_rehash_rollback & operator=(const incremental_rehash_rollback &);
- incremental_rehash_rollback (const incremental_rehash_rollback &);
- public:
- incremental_rehash_rollback
- (bucket_type &source_bucket, bucket_type &destiny_bucket, split_traits &split_tr)
- : source_bucket_(source_bucket), destiny_bucket_(destiny_bucket)
- , split_traits_(split_tr), released_(false)
- {}
- BOOST_INTRUSIVE_FORCEINLINE void release()
- { released_ = true; }
- ~incremental_rehash_rollback()
- {
- if(!released_){
-
-
- SlistNodeAlgorithms::transfer_after(destiny_bucket_.get_node_ptr(), source_bucket_.get_node_ptr());
- split_traits_.decrement();
- }
- }
- private:
- bucket_type &source_bucket_;
- bucket_type &destiny_bucket_;
- split_traits &split_traits_;
- bool released_;
- };
- template<class NodeTraits>
- struct node_functions
- {
- BOOST_INTRUSIVE_FORCEINLINE static void store_hash(typename NodeTraits::node_ptr p, std::size_t h, detail::true_)
- { return NodeTraits::set_hash(p, h); }
- BOOST_INTRUSIVE_FORCEINLINE static void store_hash(typename NodeTraits::node_ptr, std::size_t, detail::false_)
- {}
- };
- BOOST_INTRUSIVE_FORCEINLINE std::size_t hash_to_bucket(std::size_t hash_value, std::size_t bucket_cnt, detail::false_)
- { return hash_value % bucket_cnt; }
- BOOST_INTRUSIVE_FORCEINLINE std::size_t hash_to_bucket(std::size_t hash_value, std::size_t bucket_cnt, detail::true_)
- { return hash_value & (bucket_cnt - 1); }
- template<bool Power2Buckets, bool Incremental>
- BOOST_INTRUSIVE_FORCEINLINE std::size_t hash_to_bucket_split(std::size_t hash_value, std::size_t bucket_cnt, std::size_t split, detail::false_)
- {
- std::size_t bucket_number = hash_to_bucket(hash_value, bucket_cnt, detail::bool_<Power2Buckets>());
- BOOST_IF_CONSTEXPR(Incremental)
- bucket_number -= static_cast<std::size_t>(bucket_number >= split)*(bucket_cnt/2);
- return bucket_number;
- }
- template<bool Power2Buckets, bool Incremental>
- BOOST_INTRUSIVE_FORCEINLINE std::size_t hash_to_bucket_split(std::size_t hash_value, std::size_t , std::size_t split, detail::true_)
- {
- return prime_fmod_size::position(hash_value, split);
- }
- template<class ValueTraitsOrHookOption>
- struct unordered_bucket
- : public unordered_bucket_impl
- < typename ValueTraitsOrHookOption::
- template pack<empty>::proto_value_traits>
- {};
- template<class ValueTraitsOrHookOption>
- struct unordered_bucket_ptr
- : public unordered_bucket_ptr_impl
- < typename ValueTraitsOrHookOption::
- template pack<empty>::proto_value_traits>
- {};
- template<class ValueTraitsOrHookOption>
- struct unordered_default_bucket_traits
- {
- typedef typename ValueTraitsOrHookOption::
- template pack<empty>::proto_value_traits supposed_value_traits;
-
- typedef bucket_traits_impl
- < typename unordered_bucket_ptr_impl
- <supposed_value_traits>::type
- , std::size_t> type;
- };
- struct default_bucket_traits;
- struct default_hashtable_hook_applier
- { template <class T> struct apply{ typedef typename T::default_hashtable_hook type; }; };
- template<>
- struct is_default_hook_tag<default_hashtable_hook_applier>
- { static const bool value = true; };
- struct hashtable_defaults
- {
- typedef default_hashtable_hook_applier proto_value_traits;
- typedef std::size_t size_type;
- typedef void key_of_value;
- typedef void equal;
- typedef void hash;
- typedef default_bucket_traits bucket_traits;
- static const bool constant_time_size = true;
- static const bool power_2_buckets = false;
- static const bool cache_begin = false;
- static const bool compare_hash = false;
- static const bool incremental = false;
- static const bool linear_buckets = false;
- static const bool fastmod_buckets = false;
- };
- template<class ValueTraits, bool IsConst>
- struct downcast_node_to_value_t
- : public detail::node_to_value<ValueTraits, IsConst>
- {
- typedef detail::node_to_value<ValueTraits, IsConst> base_t;
- typedef typename base_t::result_type result_type;
- typedef ValueTraits value_traits;
- typedef typename unordered_bucket_impl
- <value_traits>::type::node_traits::node node;
- typedef typename detail::add_const_if_c
- <node, IsConst>::type &first_argument_type;
- typedef typename detail::add_const_if_c
- < typename ValueTraits::node_traits::node
- , IsConst>::type &intermediate_argument_type;
- typedef typename pointer_traits
- <typename ValueTraits::pointer>::
- template rebind_pointer
- <const ValueTraits>::type const_value_traits_ptr;
- BOOST_INTRUSIVE_FORCEINLINE downcast_node_to_value_t(const_value_traits_ptr ptr)
- : base_t(ptr)
- {}
- BOOST_INTRUSIVE_FORCEINLINE result_type operator()(first_argument_type arg) const
- { return this->base_t::operator()(static_cast<intermediate_argument_type>(arg)); }
- };
- template<class F, class SlistNodePtr, class NodePtr>
- struct node_cast_adaptor
-
- : public detail::ebo_functor_holder<F>
- {
- typedef detail::ebo_functor_holder<F> base_t;
- typedef typename pointer_traits<SlistNodePtr>::element_type slist_node;
- typedef typename pointer_traits<NodePtr>::element_type node;
- template<class ConvertibleToF, class RealValuTraits>
- BOOST_INTRUSIVE_FORCEINLINE node_cast_adaptor(const ConvertibleToF &c2f, const RealValuTraits *traits)
- : base_t(base_t(c2f, traits))
- {}
- BOOST_INTRUSIVE_FORCEINLINE typename base_t::node_ptr operator()(const slist_node &to_clone)
- { return base_t::operator()(static_cast<const node &>(to_clone)); }
- BOOST_INTRUSIVE_FORCEINLINE void operator()(SlistNodePtr to_clone)
- {
- base_t::operator()(pointer_traits<NodePtr>::pointer_to(static_cast<node &>(*to_clone)));
- }
- };
- template<class ValueTraits, class BucketTraits, bool LinearBuckets>
- struct bucket_plus_vtraits
- {
- private:
- BOOST_MOVABLE_BUT_NOT_COPYABLE(bucket_plus_vtraits)
- struct data_type
- : public ValueTraits, BucketTraits
- {
- private:
- BOOST_MOVABLE_BUT_NOT_COPYABLE(data_type)
- public:
- BOOST_INTRUSIVE_FORCEINLINE data_type(const ValueTraits& val_traits, const BucketTraits& b_traits)
- : ValueTraits(val_traits), BucketTraits(b_traits)
- {}
- BOOST_INTRUSIVE_FORCEINLINE data_type(BOOST_RV_REF(data_type) other)
- : ValueTraits (BOOST_MOVE_BASE(ValueTraits, other))
- , BucketTraits(BOOST_MOVE_BASE(BucketTraits, other))
- {}
- } m_data;
- public:
- typedef BucketTraits bucket_traits;
- typedef ValueTraits value_traits;
- static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value;
- typedef typename unordered_bucket_impl
- <value_traits>::type bucket_type;
- typedef typename unordered_bucket_ptr_impl
- <value_traits>::type bucket_ptr;
- typedef typename value_traits::node_traits node_traits;
- typedef typename bucket_type::node_traits slist_node_traits;
- typedef unordered_group_adapter<node_traits> group_traits;
- typedef group_functions<node_traits> group_functions_t;
- typedef typename detail::if_c
- < LinearBuckets
- , linear_slist_algorithms<slist_node_traits>
- , circular_slist_algorithms<slist_node_traits>
- >::type slist_node_algorithms;
- typedef typename slist_node_traits::node_ptr slist_node_ptr;
- typedef trivial_value_traits
- <slist_node_traits, normal_link> slist_value_traits;
- typedef slist_iterator<slist_value_traits, false> siterator;
- typedef slist_iterator<slist_value_traits, true> const_siterator;
- typedef typename node_traits::node_ptr node_ptr;
- typedef typename node_traits::const_node_ptr const_node_ptr;
- typedef typename node_traits::node node;
- typedef typename value_traits::value_type value_type;
- typedef typename value_traits::pointer pointer;
- typedef typename value_traits::const_pointer const_pointer;
- typedef typename pointer_traits<pointer>::reference reference;
- typedef typename pointer_traits
- <const_pointer>::reference const_reference;
- typedef circular_slist_algorithms<group_traits> group_algorithms;
- typedef typename pointer_traits
- <typename value_traits::pointer>::
- template rebind_pointer
- <const value_traits>::type const_value_traits_ptr;
- typedef typename pointer_traits
- <typename value_traits::pointer>::
- template rebind_pointer
- <const bucket_plus_vtraits>::type const_bucket_value_traits_ptr;
- typedef detail::bool_<LinearBuckets> linear_buckets_t;
- typedef bucket_plus_vtraits& this_ref;
- static const std::size_t bucket_overhead = LinearBuckets ? 1u : 0u;
- BOOST_INTRUSIVE_FORCEINLINE bucket_plus_vtraits(const ValueTraits &val_traits, const bucket_traits &b_traits)
- : m_data(val_traits, b_traits)
- {}
- BOOST_INTRUSIVE_FORCEINLINE bucket_plus_vtraits(BOOST_RV_REF(bucket_plus_vtraits) other)
- : m_data(boost::move(((bucket_plus_vtraits&)other).m_data))
- {}
- BOOST_INTRUSIVE_FORCEINLINE const_value_traits_ptr priv_value_traits_ptr() const
- { return pointer_traits<const_value_traits_ptr>::pointer_to(this->priv_value_traits()); }
-
-
- BOOST_INTRUSIVE_FORCEINLINE const bucket_plus_vtraits &get_bucket_value_traits() const
- { return *this; }
- BOOST_INTRUSIVE_FORCEINLINE bucket_plus_vtraits &get_bucket_value_traits()
- { return *this; }
- BOOST_INTRUSIVE_FORCEINLINE const_bucket_value_traits_ptr bucket_value_traits_ptr() const
- { return pointer_traits<const_bucket_value_traits_ptr>::pointer_to(this->get_bucket_value_traits()); }
-
-
- BOOST_INTRUSIVE_FORCEINLINE const value_traits &priv_value_traits() const
- { return static_cast<const value_traits &>(this->m_data); }
- BOOST_INTRUSIVE_FORCEINLINE value_traits &priv_value_traits()
- { return static_cast<value_traits &>(this->m_data); }
-
-
- BOOST_INTRUSIVE_FORCEINLINE const bucket_traits &priv_bucket_traits() const
- { return static_cast<const bucket_traits &>(this->m_data); }
- BOOST_INTRUSIVE_FORCEINLINE bucket_traits& priv_bucket_traits()
- { return static_cast<bucket_traits&>(this->m_data); }
-
- BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_bucket_pointer() const BOOST_NOEXCEPT
- { return this->priv_bucket_traits().bucket_begin(); }
- BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_usable_bucket_count() const BOOST_NOEXCEPT
- {
- BOOST_IF_CONSTEXPR(bucket_overhead){
- const std::size_t n = this->priv_bucket_traits().bucket_count();
- return n - std::size_t(n != 0)*bucket_overhead;
- }
- else{
- return this->priv_bucket_traits().bucket_count();
- }
- }
- BOOST_INTRUSIVE_FORCEINLINE bucket_type &priv_bucket(std::size_t n) const BOOST_NOEXCEPT
- {
- BOOST_INTRUSIVE_INVARIANT_ASSERT(n < this->priv_usable_bucket_count());
- return this->priv_bucket_pointer()[std::ptrdiff_t(n)];
- }
- BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_bucket_ptr(std::size_t n) const BOOST_NOEXCEPT
- { return pointer_traits<bucket_ptr>::pointer_to(this->priv_bucket(n)); }
- BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_past_usable_bucket_ptr() const
- { return this->priv_bucket_pointer() + std::ptrdiff_t(priv_usable_bucket_count()); }
- BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_invalid_bucket_ptr() const
- {
- BOOST_IF_CONSTEXPR(LinearBuckets) {
- return bucket_ptr();
- }
- else{
- return this->priv_past_usable_bucket_ptr();
- }
- }
- BOOST_INTRUSIVE_FORCEINLINE void priv_set_sentinel_bucket() const
- {
- BOOST_IF_CONSTEXPR(LinearBuckets) {
- BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_bucket_traits().bucket_count() > 1);
- bucket_type &b = this->priv_bucket_pointer()[std::ptrdiff_t(this->priv_usable_bucket_count())];
- slist_node_algorithms::set_sentinel(b.get_node_ptr());
- }
- }
- BOOST_INTRUSIVE_FORCEINLINE void priv_unset_sentinel_bucket() const
- {
- BOOST_IF_CONSTEXPR(LinearBuckets) {
- BOOST_INTRUSIVE_INVARIANT_ASSERT(this->priv_bucket_traits().bucket_count() > 1);
- bucket_type& b = this->priv_bucket_pointer()[std::ptrdiff_t(this->priv_usable_bucket_count())];
- slist_node_algorithms::init_header(b.get_node_ptr());
- }
- }
- BOOST_INTRUSIVE_FORCEINLINE siterator priv_end_sit() const
- { return priv_end_sit(linear_buckets_t()); }
- BOOST_INTRUSIVE_FORCEINLINE siterator priv_end_sit(detail::true_) const
- { return siterator(this->priv_bucket_pointer() + std::ptrdiff_t(this->priv_bucket_traits().bucket_count() - bucket_overhead)); }
- BOOST_INTRUSIVE_FORCEINLINE siterator priv_end_sit(detail::false_) const
- { return siterator(this->priv_bucket_pointer()->get_node_ptr()); }
- BOOST_INTRUSIVE_FORCEINLINE siterator priv_bucket_lbegin(std::size_t n) const
- { siterator s(this->priv_bucket_lbbegin(n)); return ++s; }
- BOOST_INTRUSIVE_FORCEINLINE siterator priv_bucket_lbbegin(std::size_t n) const
- { return this->sit_bbegin(this->priv_bucket(n)); }
- BOOST_INTRUSIVE_FORCEINLINE siterator priv_bucket_lend(std::size_t n) const
- { return this->sit_end(this->priv_bucket(n)); }
- BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_bucket_size(std::size_t n) const
- { return slist_node_algorithms::count(this->priv_bucket(n).get_node_ptr())-1u; }
- BOOST_INTRUSIVE_FORCEINLINE bool priv_bucket_empty(std::size_t n) const
- { return slist_node_algorithms::is_empty(this->priv_bucket(n).get_node_ptr()); }
- BOOST_INTRUSIVE_FORCEINLINE bool priv_bucket_empty(bucket_ptr p) const
- { return slist_node_algorithms::is_empty(p->get_node_ptr()); }
- static BOOST_INTRUSIVE_FORCEINLINE siterator priv_bucket_lbegin(bucket_type &b)
- { return siterator(slist_node_traits::get_next(b.get_node_ptr())); }
- static BOOST_INTRUSIVE_FORCEINLINE siterator priv_bucket_lbbegin(bucket_type& b)
- { return siterator(b.get_node_ptr()); }
- static BOOST_INTRUSIVE_FORCEINLINE siterator priv_bucket_lend(bucket_type& b)
- { return siterator(slist_node_algorithms::end_node(b.get_node_ptr())); }
- static BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_bucket_size(const bucket_type& b)
- { return slist_node_algorithms::count(b.get_node_ptr())-1u; }
- static BOOST_INTRUSIVE_FORCEINLINE bool priv_bucket_empty(const bucket_type& b)
- { return slist_node_algorithms::is_empty(b.get_node_ptr()); }
- template<class NodeDisposer>
- static std::size_t priv_erase_from_single_bucket
- (bucket_type &b, siterator sbefore_first, siterator slast, NodeDisposer node_disposer, detail::true_)
- {
- std::size_t n = 0;
- siterator const sfirst(++siterator(sbefore_first));
- if(sfirst != slast){
- node_ptr const nf = dcast_bucket_ptr<node>(sfirst.pointed_node());
- node_ptr const nl = dcast_bucket_ptr<node>(slast.pointed_node());
- slist_node_ptr const ne = (priv_bucket_lend(b)).pointed_node();
- if(group_functions_t::is_first_in_group(nf)) {
-
- if(nl != ne){
- group_functions_t::split_group(nl);
- }
- }
- else {
- node_ptr const group1 = group_functions_t::split_group(nf);
- if(nl != ne) {
- node_ptr const group2 = group_functions_t::split_group(nl);
- if(nf == group2) {
-
- node_ptr const end1 = group_traits::get_next(group1);
- node_ptr const end2 = group_traits::get_next(group2);
- group_traits::set_next(group1, end2);
- group_traits::set_next(nl, end1);
- }
- }
- }
- n = slist_node_algorithms::unlink_after_and_dispose(sbefore_first.pointed_node(), slast.pointed_node(), node_disposer);
- }
- return n;
- }
- template<class NodeDisposer>
- static std::size_t priv_erase_from_single_bucket
- (bucket_type &, siterator sbefore_first, siterator slast, NodeDisposer node_disposer, detail::false_)
- {
- return slist_node_algorithms::unlink_after_and_dispose(sbefore_first.pointed_node(), slast.pointed_node(), node_disposer);
- }
- template<class NodeDisposer>
- static void priv_erase_node(bucket_type &b, siterator i, NodeDisposer node_disposer, detail::true_)
- {
- slist_node_ptr const ne(priv_bucket_lend(b).pointed_node());
- slist_node_ptr const nbb(priv_bucket_lbbegin(b).pointed_node());
- node_ptr n(dcast_bucket_ptr<node>(i.pointed_node()));
- node_ptr pos = node_traits::get_next(group_traits::get_next(n));
- node_ptr bn;
- node_ptr nn(node_traits::get_next(n));
-
- if(pos != n) {
-
- bn = group_functions_t::get_prev_to_first_in_group(nbb, n);
-
- if(nn != ne && group_traits::get_next(nn) == n){
- group_algorithms::unlink_after(nn);
- }
- }
- else if(nn != ne && group_traits::get_next(nn) == n){
-
- bn = group_traits::get_next(n);
- group_algorithms::unlink_after(nn);
- }
- else{
-
- bn = group_traits::get_next(n);
- node_ptr const x(group_algorithms::get_previous_node(n));
- group_algorithms::unlink_after(x);
- }
- slist_node_algorithms::unlink_after_and_dispose(bn, node_disposer);
- }
- template<class NodeDisposer>
- BOOST_INTRUSIVE_FORCEINLINE static void priv_erase_node(bucket_type &b, siterator i, NodeDisposer node_disposer, detail::false_)
- {
- slist_node_ptr bi = slist_node_algorithms::get_previous_node(b.get_node_ptr(), i.pointed_node());
- slist_node_algorithms::unlink_after_and_dispose(bi, node_disposer);
- }
- template<class NodeDisposer, bool OptimizeMultikey>
- std::size_t priv_erase_node_range( siterator const &before_first_it, std::size_t const first_bucket
- , siterator const &last_it, std::size_t const last_bucket
- , NodeDisposer node_disposer, detail::bool_<OptimizeMultikey> optimize_multikey_tag)
- {
- std::size_t num_erased(0);
- siterator last_step_before_it;
- if(first_bucket != last_bucket){
- bucket_type *b = &this->priv_bucket(0);
- num_erased += this->priv_erase_from_single_bucket
- (b[first_bucket], before_first_it, this->priv_bucket_lend(first_bucket), node_disposer, optimize_multikey_tag);
- for(std::size_t i = 0, n = (last_bucket - first_bucket - 1); i != n; ++i){
- num_erased += this->priv_erase_whole_bucket(b[first_bucket+i+1], node_disposer);
- }
- last_step_before_it = this->priv_bucket_lbbegin(last_bucket);
- }
- else{
- last_step_before_it = before_first_it;
- }
- num_erased += this->priv_erase_from_single_bucket
- (this->priv_bucket(last_bucket), last_step_before_it, last_it, node_disposer, optimize_multikey_tag);
- return num_erased;
- }
- static siterator priv_get_last(bucket_type &b, detail::true_)
- {
-
-
-
- slist_node_ptr end_ptr(sit_end(b).pointed_node());
- slist_node_ptr last_node_group(b.get_node_ptr());
- slist_node_ptr possible_end(slist_node_traits::get_next(last_node_group));
- while(end_ptr != possible_end){
- last_node_group = group_traits::get_next(dcast_bucket_ptr<node>(possible_end));
- possible_end = slist_node_traits::get_next(last_node_group);
- }
- return siterator(last_node_group);
- }
- BOOST_INTRUSIVE_FORCEINLINE static siterator priv_get_last(bucket_type &b, detail::false_)
- {
- slist_node_ptr p = b.get_node_ptr();
- return siterator(slist_node_algorithms::get_previous_node(p, slist_node_algorithms::end_node(p)));
- }
- template<class NodeDisposer>
- static BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_erase_whole_bucket(bucket_type &b, NodeDisposer node_disposer)
- { return slist_node_algorithms::detach_and_dispose(b.get_node_ptr(), node_disposer); }
- static siterator priv_get_previous(bucket_type &b, siterator i, detail::true_)
- {
- node_ptr const elem(dcast_bucket_ptr<node>(i.pointed_node()));
- node_ptr const prev_in_group(group_traits::get_next(elem));
- bool const first_in_group = node_traits::get_next(prev_in_group) != elem;
- slist_node_ptr n = first_in_group
- ? group_functions_t::get_prev_to_first_in_group(b.get_node_ptr(), elem)
- : group_traits::get_next(elem)
- ;
- return siterator(n);
- }
- BOOST_INTRUSIVE_FORCEINLINE static siterator priv_get_previous(bucket_type &b, siterator i, detail::false_)
- { return siterator(slist_node_algorithms::get_previous_node(b.get_node_ptr(), i.pointed_node())); }
- template<class Disposer>
- struct typeof_node_disposer
- {
- typedef node_cast_adaptor
- < detail::node_disposer< Disposer, value_traits, CommonSListAlgorithms>
- , slist_node_ptr, node_ptr > type;
- };
- template<class Disposer>
- BOOST_INTRUSIVE_FORCEINLINE typename typeof_node_disposer<Disposer>::type
- make_node_disposer(const Disposer &disposer) const
- {
- typedef typename typeof_node_disposer<Disposer>::type return_t;
- return return_t(disposer, &this->priv_value_traits());
- }
- static BOOST_INTRUSIVE_FORCEINLINE bucket_ptr to_ptr(bucket_type &b)
- { return pointer_traits<bucket_ptr>::pointer_to(b); }
- static BOOST_INTRUSIVE_FORCEINLINE siterator sit_bbegin(bucket_type& b)
- { return siterator(b.get_node_ptr()); }
- static BOOST_INTRUSIVE_FORCEINLINE siterator sit_begin(bucket_type& b)
- { return siterator(b.begin_ptr()); }
- static BOOST_INTRUSIVE_FORCEINLINE siterator sit_end(bucket_type& b)
- { return siterator(slist_node_algorithms::end_node(b.get_node_ptr())); }
- BOOST_INTRUSIVE_FORCEINLINE static std::size_t priv_stored_hash(siterator s, detail::true_)
- { return node_traits::get_hash(dcast_bucket_ptr<node>(s.pointed_node())); }
- BOOST_INTRUSIVE_FORCEINLINE static std::size_t priv_stored_hash(siterator, detail::false_)
- { return std::size_t(-1); }
- BOOST_INTRUSIVE_FORCEINLINE node &priv_value_to_node(reference v)
- { return *this->priv_value_traits().to_node_ptr(v); }
- BOOST_INTRUSIVE_FORCEINLINE const node &priv_value_to_node(const_reference v) const
- { return *this->priv_value_traits().to_node_ptr(v); }
- BOOST_INTRUSIVE_FORCEINLINE node_ptr priv_value_to_node_ptr(reference v)
- { return this->priv_value_traits().to_node_ptr(v); }
- BOOST_INTRUSIVE_FORCEINLINE const_node_ptr priv_value_to_node_ptr(const_reference v) const
- { return this->priv_value_traits().to_node_ptr(v); }
- BOOST_INTRUSIVE_FORCEINLINE reference priv_value_from_siterator(siterator s)
- { return *this->priv_value_traits().to_value_ptr(dcast_bucket_ptr<node>(s.pointed_node())); }
- BOOST_INTRUSIVE_FORCEINLINE const_reference priv_value_from_siterator(siterator s) const
- { return *this->priv_value_traits().to_value_ptr(dcast_bucket_ptr<node>(s.pointed_node())); }
- static void priv_init_buckets(const bucket_ptr buckets_ptr, const std::size_t bucket_cnt)
- {
- bucket_ptr buckets_it = buckets_ptr;
- for (std::size_t bucket_i = 0; bucket_i != bucket_cnt; ++buckets_it, ++bucket_i) {
- slist_node_algorithms::init_header(buckets_it->get_node_ptr());
- }
- }
- void priv_clear_buckets(const bucket_ptr buckets_ptr, const std::size_t bucket_cnt)
- {
- bucket_ptr buckets_it = buckets_ptr;
- for(std::size_t bucket_i = 0; bucket_i != bucket_cnt; ++buckets_it, ++bucket_i){
- bucket_type &b = *buckets_it;
- BOOST_IF_CONSTEXPR(safemode_or_autounlink){
- slist_node_algorithms::detach_and_dispose(b.get_node_ptr(), this->make_node_disposer(detail::null_disposer()));
- }
- else{
- slist_node_algorithms::init_header(b.get_node_ptr());
- }
- }
- }
- BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_stored_or_compute_hash(const value_type &v, detail::true_) const
- { return node_traits::get_hash(this->priv_value_traits().to_node_ptr(v)); }
- typedef hashtable_iterator<bucket_plus_vtraits, LinearBuckets, false> iterator;
- typedef hashtable_iterator<bucket_plus_vtraits, LinearBuckets, true> const_iterator;
- BOOST_INTRUSIVE_FORCEINLINE iterator end() BOOST_NOEXCEPT
- { return this->build_iterator(this->priv_end_sit(), bucket_ptr()); }
- BOOST_INTRUSIVE_FORCEINLINE const_iterator end() const BOOST_NOEXCEPT
- { return this->cend(); }
- BOOST_INTRUSIVE_FORCEINLINE const_iterator cend() const BOOST_NOEXCEPT
- { return this->build_const_iterator(this->priv_end_sit(), bucket_ptr()); }
- BOOST_INTRUSIVE_FORCEINLINE iterator build_iterator(siterator s, bucket_ptr p)
- { return this->build_iterator(s, p, linear_buckets_t()); }
- BOOST_INTRUSIVE_FORCEINLINE iterator build_iterator(siterator s, bucket_ptr p, detail::true_)
- { return iterator(s, p, this->priv_value_traits_ptr()); }
- BOOST_INTRUSIVE_FORCEINLINE iterator build_iterator(siterator s, bucket_ptr, detail::false_)
- { return iterator(s, &this->get_bucket_value_traits()); }
- BOOST_INTRUSIVE_FORCEINLINE const_iterator build_const_iterator(siterator s, bucket_ptr p) const
- { return this->build_const_iterator(s, p, linear_buckets_t()); }
- BOOST_INTRUSIVE_FORCEINLINE const_iterator build_const_iterator(siterator s, bucket_ptr p, detail::true_) const
- { return const_iterator(s, p, this->priv_value_traits_ptr()); }
- BOOST_INTRUSIVE_FORCEINLINE const_iterator build_const_iterator(siterator s, bucket_ptr, detail::false_) const
- { return const_iterator(s, &this->get_bucket_value_traits()); }
- };
- template<class Hash, class>
- struct get_hash
- {
- typedef Hash type;
- };
- template<class T>
- struct get_hash<void, T>
- {
- typedef ::boost::hash<T> type;
- };
- template<class EqualTo, class>
- struct get_equal_to
- {
- typedef EqualTo type;
- };
- template<class T>
- struct get_equal_to<void, T>
- {
- typedef value_equal<T> type;
- };
- template<class KeyOfValue, class T>
- struct get_hash_key_of_value
- {
- typedef KeyOfValue type;
- };
- template<class T>
- struct get_hash_key_of_value<void, T>
- {
- typedef ::boost::intrusive::detail::identity<T> type;
- };
- template<class T, class VoidOrKeyOfValue>
- struct hash_key_types_base
- {
- typedef typename get_hash_key_of_value
- < VoidOrKeyOfValue, T>::type key_of_value;
- typedef typename key_of_value::type key_type;
- };
- template<class T, class VoidOrKeyOfValue, class VoidOrKeyHash>
- struct hash_key_hash
- : get_hash
- < VoidOrKeyHash
- , typename hash_key_types_base<T, VoidOrKeyOfValue>::key_type
- >
- {};
- template<class T, class VoidOrKeyOfValue, class VoidOrKeyEqual>
- struct hash_key_equal
- : get_equal_to
- < VoidOrKeyEqual
- , typename hash_key_types_base<T, VoidOrKeyOfValue>::key_type
- >
- {};
- template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class BucketTraits, bool LinearBuckets>
- struct bucket_hash_t
-
- : public detail::ebo_functor_holder
- <typename hash_key_hash < typename bucket_plus_vtraits<ValueTraits,BucketTraits, LinearBuckets >::value_traits::value_type
- , VoidOrKeyOfValue
- , VoidOrKeyHash
- >::type
- >
- , bucket_plus_vtraits<ValueTraits, BucketTraits, LinearBuckets>
- {
- private:
- BOOST_MOVABLE_BUT_NOT_COPYABLE(bucket_hash_t)
- public:
- typedef typename bucket_plus_vtraits
- <ValueTraits,BucketTraits, LinearBuckets>::value_traits value_traits;
- typedef typename value_traits::value_type value_type;
- typedef typename value_traits::node_traits node_traits;
- typedef hash_key_hash
- < value_type, VoidOrKeyOfValue, VoidOrKeyHash> hash_key_hash_t;
- typedef typename hash_key_hash_t::type hasher;
- typedef typename hash_key_types_base<value_type, VoidOrKeyOfValue>::key_of_value key_of_value;
- typedef BucketTraits bucket_traits;
- typedef bucket_plus_vtraits<ValueTraits, BucketTraits, LinearBuckets> bucket_plus_vtraits_t;
- typedef detail::ebo_functor_holder<hasher> base_t;
- BOOST_INTRUSIVE_FORCEINLINE bucket_hash_t(const ValueTraits &val_traits, const bucket_traits &b_traits, const hasher & h)
- : base_t(h)
- , bucket_plus_vtraits_t(val_traits, b_traits)
- {}
- BOOST_INTRUSIVE_FORCEINLINE bucket_hash_t(BOOST_RV_REF(bucket_hash_t) other)
- : base_t(BOOST_MOVE_BASE(base_t, other))
- , bucket_plus_vtraits_t(BOOST_MOVE_BASE(bucket_plus_vtraits_t, other))
- {}
- template<class K>
- BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_hash(const K &k) const
- { return this->base_t::operator()(k); }
- BOOST_INTRUSIVE_FORCEINLINE const hasher &priv_hasher() const
- { return this->base_t::get(); }
- BOOST_INTRUSIVE_FORCEINLINE hasher &priv_hasher()
- { return this->base_t::get(); }
- using bucket_plus_vtraits_t::priv_stored_or_compute_hash;
- BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_stored_or_compute_hash(const value_type &v, detail::false_) const
- { return this->priv_hasher()(key_of_value()(v)); }
- };
- template<class ValueTraits, class BucketTraits, class VoidOrKeyOfValue, class VoidOrKeyEqual, bool LinearBuckets>
- struct hashtable_equal_holder
- {
- typedef detail::ebo_functor_holder
- < typename hash_key_equal < typename bucket_plus_vtraits
- <ValueTraits, BucketTraits, LinearBuckets>::value_traits::value_type
- , VoidOrKeyOfValue
- , VoidOrKeyEqual
- >::type
- > type;
- };
- template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits, bool LinearBuckets, bool>
- struct bucket_hash_equal_t
-
- : public bucket_hash_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, BucketTraits, LinearBuckets>
- , public hashtable_equal_holder<ValueTraits, BucketTraits, VoidOrKeyOfValue, VoidOrKeyEqual, LinearBuckets>::type
- {
- private:
- BOOST_MOVABLE_BUT_NOT_COPYABLE(bucket_hash_equal_t)
- public:
- typedef typename hashtable_equal_holder
- < ValueTraits, BucketTraits, VoidOrKeyOfValue
- , VoidOrKeyEqual, LinearBuckets>::type equal_holder_t;
- typedef bucket_hash_t< ValueTraits, VoidOrKeyOfValue
- , VoidOrKeyHash, BucketTraits
- , LinearBuckets> bucket_hash_type;
- typedef bucket_plus_vtraits
- <ValueTraits, BucketTraits, LinearBuckets> bucket_plus_vtraits_t;
- typedef ValueTraits value_traits;
- typedef typename equal_holder_t::functor_type key_equal;
- typedef typename bucket_hash_type::hasher hasher;
- typedef BucketTraits bucket_traits;
- typedef typename bucket_plus_vtraits_t::siterator siterator;
- typedef typename bucket_plus_vtraits_t::const_siterator const_siterator;
- typedef typename bucket_plus_vtraits_t::bucket_type bucket_type;
- typedef typename bucket_plus_vtraits_t::slist_node_algorithms slist_node_algorithms;
- typedef typename unordered_bucket_ptr_impl
- <value_traits>::type bucket_ptr;
- bucket_hash_equal_t(const ValueTraits &val_traits, const bucket_traits &b_traits, const hasher & h, const key_equal &e)
- : bucket_hash_type(val_traits, b_traits, h)
- , equal_holder_t(e)
- {}
- BOOST_INTRUSIVE_FORCEINLINE bucket_hash_equal_t(BOOST_RV_REF(bucket_hash_equal_t) other)
- : bucket_hash_type(BOOST_MOVE_BASE(bucket_hash_type, other))
- , equal_holder_t(BOOST_MOVE_BASE(equal_holder_t, other))
- {}
- BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_get_cache()
- { return this->priv_bucket_pointer(); }
- BOOST_INTRUSIVE_FORCEINLINE void priv_set_cache(bucket_ptr)
- {}
- BOOST_INTRUSIVE_FORCEINLINE void priv_set_cache_bucket_num(std::size_t)
- {}
- BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_get_cache_bucket_num()
- { return 0u; }
- BOOST_INTRUSIVE_FORCEINLINE void priv_init_cache()
- {}
- BOOST_INTRUSIVE_FORCEINLINE void priv_swap_cache(bucket_hash_equal_t &)
- {}
- siterator priv_begin(bucket_ptr &pbucketptr) const
- {
- std::size_t n = 0;
- std::size_t bucket_cnt = this->priv_usable_bucket_count();
- for (n = 0; n < bucket_cnt; ++n){
- bucket_type &b = this->priv_bucket(n);
- if(!slist_node_algorithms::is_empty(b.get_node_ptr())){
- pbucketptr = this->to_ptr(b);
- return siterator(b.begin_ptr());
- }
- }
- pbucketptr = this->priv_invalid_bucket_ptr();
- return this->priv_end_sit();
- }
- BOOST_INTRUSIVE_FORCEINLINE void priv_insertion_update_cache(std::size_t)
- {}
- BOOST_INTRUSIVE_FORCEINLINE void priv_erasure_update_cache_range(std::size_t, std::size_t)
- {}
- BOOST_INTRUSIVE_FORCEINLINE void priv_erasure_update_cache(bucket_ptr)
- {}
- BOOST_INTRUSIVE_FORCEINLINE void priv_erasure_update_cache()
- {}
- BOOST_INTRUSIVE_FORCEINLINE const key_equal &priv_equal() const
- { return this->equal_holder_t::get(); }
- BOOST_INTRUSIVE_FORCEINLINE key_equal &priv_equal()
- { return this->equal_holder_t::get(); }
- };
- template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits, bool LinearBuckets>
- struct bucket_hash_equal_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, LinearBuckets, true>
-
- : public bucket_hash_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, BucketTraits, LinearBuckets>
- , public hashtable_equal_holder<ValueTraits, BucketTraits, VoidOrKeyOfValue, VoidOrKeyEqual, LinearBuckets>::type
- {
- private:
- BOOST_MOVABLE_BUT_NOT_COPYABLE(bucket_hash_equal_t)
- public:
- typedef typename hashtable_equal_holder
- < ValueTraits, BucketTraits
- , VoidOrKeyOfValue, VoidOrKeyEqual, LinearBuckets>::type equal_holder_t;
- typedef bucket_plus_vtraits
- < ValueTraits, BucketTraits, LinearBuckets> bucket_plus_vtraits_t;
- typedef ValueTraits value_traits;
- typedef typename equal_holder_t::functor_type key_equal;
- typedef bucket_hash_t
- < ValueTraits, VoidOrKeyOfValue
- , VoidOrKeyHash, BucketTraits, LinearBuckets> bucket_hash_type;
- typedef typename bucket_hash_type::hasher hasher;
- typedef BucketTraits bucket_traits;
- typedef typename bucket_plus_vtraits_t::siterator siterator;
- typedef typename bucket_plus_vtraits_t::slist_node_algorithms slist_node_algorithms;
- bucket_hash_equal_t(const ValueTraits &val_traits, const bucket_traits &b_traits, const hasher & h, const key_equal &e)
- : bucket_hash_type(val_traits, b_traits, h)
- , equal_holder_t(e)
- {}
- BOOST_INTRUSIVE_FORCEINLINE bucket_hash_equal_t(BOOST_RV_REF(bucket_hash_equal_t) other)
- : bucket_hash_type(BOOST_MOVE_BASE(bucket_hash_type, other))
- , equal_holder_t(BOOST_MOVE_BASE(equal_holder_t, other))
- {}
- typedef typename unordered_bucket_ptr_impl
- <typename bucket_hash_type::value_traits>::type bucket_ptr;
- BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_get_cache() const
- { return cached_begin_; }
- BOOST_INTRUSIVE_FORCEINLINE void priv_set_cache(bucket_ptr p)
- { cached_begin_ = p; }
- BOOST_INTRUSIVE_FORCEINLINE void priv_set_cache_bucket_num(std::size_t insertion_bucket)
- {
- BOOST_INTRUSIVE_INVARIANT_ASSERT(insertion_bucket <= this->priv_usable_bucket_count());
- this->cached_begin_ = this->priv_bucket_pointer() + std::ptrdiff_t(insertion_bucket);
- }
- BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_get_cache_bucket_num()
- { return std::size_t(this->cached_begin_ - this->priv_bucket_pointer()); }
- BOOST_INTRUSIVE_FORCEINLINE void priv_init_cache()
- { this->cached_begin_ = this->priv_past_usable_bucket_ptr(); }
- BOOST_INTRUSIVE_FORCEINLINE void priv_swap_cache(bucket_hash_equal_t &other)
- { ::boost::adl_move_swap(this->cached_begin_, other.cached_begin_); }
- siterator priv_begin(bucket_ptr& pbucketptr) const
- {
- pbucketptr = this->cached_begin_;
- if(this->cached_begin_ == this->priv_past_usable_bucket_ptr()){
- return this->priv_end_sit();
- }
- else{
- return siterator(cached_begin_->begin_ptr());
- }
- }
- void priv_insertion_update_cache(std::size_t insertion_bucket)
- {
- BOOST_INTRUSIVE_INVARIANT_ASSERT(insertion_bucket < this->priv_usable_bucket_count());
- bucket_ptr p = this->priv_bucket_pointer() + std::ptrdiff_t(insertion_bucket);
- if(p < this->cached_begin_){
- this->cached_begin_ = p;
- }
- }
- BOOST_INTRUSIVE_FORCEINLINE const key_equal &priv_equal() const
- { return this->equal_holder_t::get(); }
- BOOST_INTRUSIVE_FORCEINLINE key_equal &priv_equal()
- { return this->equal_holder_t::get(); }
- void priv_erasure_update_cache_range(std::size_t first_bucket_num, std::size_t last_bucket_num)
- {
-
-
- if(this->priv_get_cache_bucket_num() == first_bucket_num &&
- this->priv_bucket_empty(first_bucket_num) ){
- this->priv_set_cache(this->priv_bucket_pointer() + std::ptrdiff_t(last_bucket_num));
- this->priv_erasure_update_cache();
- }
- }
- void priv_erasure_update_cache(bucket_ptr first_bucket)
- {
-
-
- if (this->priv_get_cache() == first_bucket &&
- this->priv_bucket_empty(first_bucket)) {
- this->priv_erasure_update_cache();
- }
- }
- void priv_erasure_update_cache()
- {
- const bucket_ptr cache_end = this->priv_past_usable_bucket_ptr();
- while( cached_begin_ != cache_end) {
- if (!slist_node_algorithms::is_empty(cached_begin_->get_node_ptr())) {
- return;
- }
- ++cached_begin_;
- }
- }
- bucket_ptr cached_begin_;
- };
- template<class DeriveFrom, class SizeType, bool>
- struct hashtable_size_wrapper
- : public DeriveFrom
- {
- private:
- BOOST_MOVABLE_BUT_NOT_COPYABLE(hashtable_size_wrapper)
- public:
- template<class Base, class Arg0, class Arg1, class Arg2>
- hashtable_size_wrapper( BOOST_FWD_REF(Base) base, BOOST_FWD_REF(Arg0) arg0
- , BOOST_FWD_REF(Arg1) arg1, BOOST_FWD_REF(Arg2) arg2)
- : DeriveFrom( ::boost::forward<Base>(base)
- , ::boost::forward<Arg0>(arg0)
- , ::boost::forward<Arg1>(arg1)
- , ::boost::forward<Arg2>(arg2))
- {}
- typedef detail::size_holder < true, SizeType> size_traits;
- BOOST_INTRUSIVE_FORCEINLINE hashtable_size_wrapper(BOOST_RV_REF(hashtable_size_wrapper) other)
- : DeriveFrom(BOOST_MOVE_BASE(DeriveFrom, other))
- {}
- size_traits size_traits_;
- typedef const size_traits & size_traits_const_t;
- typedef size_traits & size_traits_t;
- BOOST_INTRUSIVE_FORCEINLINE SizeType get_hashtable_size_wrapper_size() const
- { return size_traits_.get_size(); }
- BOOST_INTRUSIVE_FORCEINLINE void set_hashtable_size_wrapper_size(SizeType s)
- { size_traits_.set_size(s); }
- BOOST_INTRUSIVE_FORCEINLINE void inc_hashtable_size_wrapper_size()
- { size_traits_.increment(); }
- BOOST_INTRUSIVE_FORCEINLINE void dec_hashtable_size_wrapper_size()
- { size_traits_.decrement(); }
- BOOST_INTRUSIVE_FORCEINLINE size_traits_t priv_size_traits()
- { return size_traits_; }
- };
- template<class DeriveFrom, class SizeType>
- struct hashtable_size_wrapper<DeriveFrom, SizeType, false>
- : public DeriveFrom
- {
- private:
- BOOST_MOVABLE_BUT_NOT_COPYABLE(hashtable_size_wrapper)
- public:
- template<class Base, class Arg0, class Arg1, class Arg2>
- hashtable_size_wrapper( BOOST_FWD_REF(Base) base, BOOST_FWD_REF(Arg0) arg0
- , BOOST_FWD_REF(Arg1) arg1, BOOST_FWD_REF(Arg2) arg2)
- : DeriveFrom( ::boost::forward<Base>(base)
- , ::boost::forward<Arg0>(arg0)
- , ::boost::forward<Arg1>(arg1)
- , ::boost::forward<Arg2>(arg2))
- {}
- BOOST_INTRUSIVE_FORCEINLINE hashtable_size_wrapper(BOOST_RV_REF(hashtable_size_wrapper) other)
- : DeriveFrom(BOOST_MOVE_BASE(DeriveFrom, other))
- {}
- typedef detail::size_holder< false, SizeType> size_traits;
- typedef size_traits size_traits_const_t;
- typedef size_traits size_traits_t;
- BOOST_INTRUSIVE_FORCEINLINE SizeType get_hashtable_size_wrapper_size() const
- { return 0u; }
- BOOST_INTRUSIVE_FORCEINLINE void set_hashtable_size_wrapper_size(SizeType)
- {}
- BOOST_INTRUSIVE_FORCEINLINE void inc_hashtable_size_wrapper_size()
- {}
- BOOST_INTRUSIVE_FORCEINLINE void dec_hashtable_size_wrapper_size()
- {}
- BOOST_INTRUSIVE_FORCEINLINE size_traits priv_size_traits()
- { return size_traits(); }
- };
- template< class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash
- , class VoidOrKeyEqual, class BucketTraits, class SizeType
- , std::size_t BoolFlags>
- struct get_hashtable_size_wrapper_bucket
- {
- typedef hashtable_size_wrapper
- < bucket_hash_equal_t
- < ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual
- , BucketTraits
- , 0 != (BoolFlags & hash_bool_flags::linear_buckets_pos)
- , 0 != (BoolFlags & hash_bool_flags::cache_begin_pos)
- >
- , SizeType
- , (BoolFlags & hash_bool_flags::incremental_pos) != 0 ||
- (BoolFlags & hash_bool_flags::fastmod_buckets_pos) != 0
- > type;
- };
- template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits, class SizeType, std::size_t BoolFlags>
- struct hashdata_internal
- : public get_hashtable_size_wrapper_bucket
- <ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, SizeType, BoolFlags>::type
- {
- private:
- BOOST_MOVABLE_BUT_NOT_COPYABLE(hashdata_internal)
- public:
- static const bool linear_buckets = 0 != (BoolFlags & hash_bool_flags::linear_buckets_pos);
- typedef typename get_hashtable_size_wrapper_bucket
- <ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, SizeType, BoolFlags>::type split_bucket_hash_equal_t;
-
- typedef typename split_bucket_hash_equal_t::key_equal key_equal;
- typedef typename split_bucket_hash_equal_t::hasher hasher;
- typedef bucket_plus_vtraits
- <ValueTraits, BucketTraits, linear_buckets> bucket_plus_vtraits_t;
- typedef SizeType size_type;
- typedef typename split_bucket_hash_equal_t::size_traits split_traits;
- typedef typename bucket_plus_vtraits_t::bucket_ptr bucket_ptr;
- typedef typename bucket_plus_vtraits_t::const_value_traits_ptr const_value_traits_ptr;
- typedef typename bucket_plus_vtraits_t::siterator siterator;
- typedef typename bucket_plus_vtraits_t::bucket_traits bucket_traits;
- typedef typename bucket_plus_vtraits_t::value_traits value_traits;
- typedef typename bucket_plus_vtraits_t::bucket_type bucket_type;
- typedef typename value_traits::value_type value_type;
- typedef typename value_traits::pointer pointer;
- typedef typename value_traits::const_pointer const_pointer;
- typedef typename pointer_traits<pointer>::reference reference;
- typedef typename pointer_traits
- <const_pointer>::reference const_reference;
- typedef typename value_traits::node_traits node_traits;
- typedef typename node_traits::node node;
- typedef typename node_traits::node_ptr node_ptr;
- typedef typename node_traits::const_node_ptr const_node_ptr;
- typedef typename bucket_plus_vtraits_t::slist_node_algorithms slist_node_algorithms;
- typedef typename bucket_plus_vtraits_t::slist_node_ptr slist_node_ptr;
- typedef hash_key_types_base
- < typename ValueTraits::value_type
- , VoidOrKeyOfValue
- > hash_types_base;
- typedef typename hash_types_base::key_of_value key_of_value;
- static const bool store_hash = store_hash_is_true<node_traits>::value;
- static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value;
- static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value;
- typedef detail::bool_<store_hash> store_hash_t;
- typedef detail::transform_iterator
- < siterator
- , downcast_node_to_value_t<value_traits, false> > local_iterator;
- typedef detail::transform_iterator
- < siterator
- , downcast_node_to_value_t<value_traits, true> > const_local_iterator;
- typedef detail::bool_<linear_buckets> linear_buckets_t;
- hashdata_internal( const ValueTraits &val_traits, const bucket_traits &b_traits
- , const hasher & h, const key_equal &e)
- : split_bucket_hash_equal_t(val_traits, b_traits, h, e)
- {}
- BOOST_INTRUSIVE_FORCEINLINE hashdata_internal(BOOST_RV_REF(hashdata_internal) other)
- : split_bucket_hash_equal_t(BOOST_MOVE_BASE(split_bucket_hash_equal_t, other))
- {}
- BOOST_INTRUSIVE_FORCEINLINE typename split_bucket_hash_equal_t::size_traits_t priv_split_traits()
- { return this->priv_size_traits(); }
- ~hashdata_internal()
- { this->priv_clear_buckets(); }
- using split_bucket_hash_equal_t::priv_clear_buckets;
- void priv_clear_buckets()
- {
- const std::size_t cache_num = this->priv_get_cache_bucket_num();
- this->priv_clear_buckets(this->priv_get_cache(), this->priv_usable_bucket_count() - cache_num);
- }
- void priv_clear_buckets_and_cache()
- {
- this->priv_clear_buckets();
- this->priv_init_cache();
- }
- void priv_init_buckets_and_cache()
- {
- this->priv_init_buckets(this->priv_bucket_pointer(), this->priv_usable_bucket_count());
- this->priv_init_cache();
- }
-
- typedef typename bucket_plus_vtraits_t::iterator iterator;
- typedef typename bucket_plus_vtraits_t::const_iterator const_iterator;
-
- BOOST_INTRUSIVE_FORCEINLINE SizeType split_count() const BOOST_NOEXCEPT
- { return this->split_bucket_hash_equal_t::get_hashtable_size_wrapper_size(); }
- BOOST_INTRUSIVE_FORCEINLINE void split_count(SizeType s) BOOST_NOEXCEPT
- { this->split_bucket_hash_equal_t::set_hashtable_size_wrapper_size(s); }
-
- BOOST_INTRUSIVE_FORCEINLINE void inc_split_count() BOOST_NOEXCEPT
- { this->split_bucket_hash_equal_t::inc_hashtable_size_wrapper_size(); }
- BOOST_INTRUSIVE_FORCEINLINE void dec_split_count() BOOST_NOEXCEPT
- { this->split_bucket_hash_equal_t::dec_hashtable_size_wrapper_size(); }
- BOOST_INTRUSIVE_FORCEINLINE static SizeType initial_split_from_bucket_count(SizeType bc) BOOST_NOEXCEPT
- {
- BOOST_IF_CONSTEXPR(fastmod_buckets) {
- size_type split;
- split = static_cast<SizeType>(prime_fmod_size::lower_size_index(bc));
-
- BOOST_ASSERT(prime_fmod_size::size(split) == bc);
- return split;
- }
- else {
- BOOST_IF_CONSTEXPR(incremental) {
- BOOST_ASSERT(0 == (std::size_t(bc) & (std::size_t(bc) - 1u)));
- return size_type(bc >> 1u);
- }
- else{
- return bc;
- }
- }
- }
- BOOST_INTRUSIVE_FORCEINLINE static SizeType rehash_split_from_bucket_count(SizeType bc) BOOST_NOEXCEPT
- {
- BOOST_IF_CONSTEXPR(fastmod_buckets) {
- return (initial_split_from_bucket_count)(bc);
- }
- else {
- BOOST_IF_CONSTEXPR(incremental) {
- BOOST_ASSERT(0 == (std::size_t(bc) & (std::size_t(bc) - 1u)));
- return bc;
- }
- else{
- return bc;
- }
- }
- }
- BOOST_INTRUSIVE_FORCEINLINE iterator iterator_to(reference value) BOOST_NOEXCEPT_IF(!linear_buckets)
- { return iterator_to(value, linear_buckets_t()); }
- const_iterator iterator_to(const_reference value) const BOOST_NOEXCEPT_IF(!linear_buckets)
- { return iterator_to(value, linear_buckets_t()); }
- iterator iterator_to(reference value, detail::true_)
- {
- const std::size_t h = this->priv_stored_or_compute_hash(value, store_hash_t());
- siterator sit(this->priv_value_to_node_ptr(value));
- return this->build_iterator(sit, this->priv_hash_to_bucket_ptr(h));
- }
- const_iterator iterator_to(const_reference value, detail::true_) const
- {
- const std::size_t h = this->priv_stored_or_compute_hash(value, store_hash_t());
- siterator const sit = siterator
- ( pointer_traits<node_ptr>::const_cast_from(this->priv_value_to_node_ptr(value))
- );
- return this->build_const_iterator(sit, this->priv_hash_to_bucket_ptr(h));
- }
- static const bool incremental = 0 != (BoolFlags & hash_bool_flags::incremental_pos);
- static const bool power_2_buckets = incremental || (0 != (BoolFlags & hash_bool_flags::power_2_buckets_pos));
- static const bool fastmod_buckets = 0 != (BoolFlags & hash_bool_flags::fastmod_buckets_pos);
- typedef detail::bool_<fastmod_buckets> fastmod_buckets_t;
- BOOST_INTRUSIVE_FORCEINLINE bucket_type &priv_hash_to_bucket(std::size_t hash_value) const
- { return this->priv_bucket(this->priv_hash_to_nbucket(hash_value)); }
- BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_hash_to_bucket_ptr(std::size_t hash_value) const
- { return this->priv_bucket_ptr(this->priv_hash_to_nbucket(hash_value)); }
- BOOST_INTRUSIVE_FORCEINLINE size_type priv_hash_to_nbucket(std::size_t hash_value) const
- { return (priv_hash_to_nbucket)(hash_value, fastmod_buckets_t()); }
- BOOST_INTRUSIVE_FORCEINLINE size_type priv_hash_to_nbucket(std::size_t hash_value, detail::true_) const
- { return static_cast<size_type>(prime_fmod_size::position(hash_value, this->split_count())); }
- BOOST_INTRUSIVE_FORCEINLINE size_type priv_hash_to_nbucket(std::size_t hash_value, detail::false_) const
- {
- return static_cast<size_type>(hash_to_bucket_split<power_2_buckets, incremental>
- (hash_value, this->priv_usable_bucket_count(), this->split_count(), detail::false_()));
- }
- BOOST_INTRUSIVE_FORCEINLINE iterator iterator_to(reference value, detail::false_) BOOST_NOEXCEPT
- {
- return iterator( siterator(this->priv_value_to_node_ptr(value))
- , &this->get_bucket_value_traits());
- }
- const_iterator iterator_to(const_reference value, detail::false_) const BOOST_NOEXCEPT
- {
- siterator const sit = siterator
- ( pointer_traits<node_ptr>::const_cast_from(this->priv_value_to_node_ptr(value)) );
- return const_iterator(sit, &this->get_bucket_value_traits());
- }
- static local_iterator s_local_iterator_to(reference value) BOOST_NOEXCEPT
- {
- BOOST_STATIC_ASSERT((!stateful_value_traits));
- siterator sit(value_traits::to_node_ptr(value));
- return local_iterator(sit, const_value_traits_ptr());
- }
- static const_local_iterator s_local_iterator_to(const_reference value) BOOST_NOEXCEPT
- {
- BOOST_STATIC_ASSERT((!stateful_value_traits));
- siterator const sit = siterator
- ( pointer_traits<node_ptr>::const_cast_from
- (value_traits::to_node_ptr(value))
- );
- return const_local_iterator(sit, const_value_traits_ptr());
- }
- local_iterator local_iterator_to(reference value) BOOST_NOEXCEPT
- {
- siterator sit(this->priv_value_to_node_ptr(value));
- return local_iterator(sit, this->priv_value_traits_ptr());
- }
- const_local_iterator local_iterator_to(const_reference value) const BOOST_NOEXCEPT
- {
- siterator sit
- ( pointer_traits<node_ptr>::const_cast_from(this->priv_value_to_node_ptr(value)) );
- return const_local_iterator(sit, this->priv_value_traits_ptr());
- }
- BOOST_INTRUSIVE_FORCEINLINE size_type bucket_count() const BOOST_NOEXCEPT
- { return size_type(this->priv_usable_bucket_count()); }
- BOOST_INTRUSIVE_FORCEINLINE size_type bucket_size(size_type n) const BOOST_NOEXCEPT
- { return (size_type)this->priv_bucket_size(n); }
- BOOST_INTRUSIVE_FORCEINLINE bucket_ptr bucket_pointer() const BOOST_NOEXCEPT
- { return this->priv_bucket_pointer(); }
- BOOST_INTRUSIVE_FORCEINLINE local_iterator begin(size_type n) BOOST_NOEXCEPT
- { return local_iterator(this->priv_bucket_lbegin(n), this->priv_value_traits_ptr()); }
- BOOST_INTRUSIVE_FORCEINLINE const_local_iterator begin(size_type n) const BOOST_NOEXCEPT
- { return this->cbegin(n); }
- static BOOST_INTRUSIVE_FORCEINLINE size_type suggested_upper_bucket_count(size_type n) BOOST_NOEXCEPT
- {
- BOOST_IF_CONSTEXPR(fastmod_buckets){
- std::size_t s = prime_fmod_size::upper_size_index(n);
- return static_cast<SizeType>(prime_fmod_size::size(s));
- }
- else{
- return prime_list_holder<0>::suggested_upper_bucket_count(n);
- }
- }
- static BOOST_INTRUSIVE_FORCEINLINE size_type suggested_lower_bucket_count(size_type n) BOOST_NOEXCEPT
- {
- BOOST_IF_CONSTEXPR(fastmod_buckets){
- std::size_t s = prime_fmod_size::lower_size_index(n);
- return static_cast<SizeType>(prime_fmod_size::size(s));
- }
- else{
- return prime_list_holder<0>::suggested_lower_bucket_count(n);
- }
- }
- const_local_iterator cbegin(size_type n) const BOOST_NOEXCEPT
- {
- return const_local_iterator
- (this->priv_bucket_lbegin(n)
- , this->priv_value_traits_ptr());
- }
- using split_bucket_hash_equal_t::end;
- using split_bucket_hash_equal_t::cend;
- local_iterator end(size_type n) BOOST_NOEXCEPT
- { return local_iterator(this->priv_bucket_lend(n), this->priv_value_traits_ptr()); }
- BOOST_INTRUSIVE_FORCEINLINE const_local_iterator end(size_type n) const BOOST_NOEXCEPT
- { return this->cend(n); }
- const_local_iterator cend(size_type n) const BOOST_NOEXCEPT
- {
- return const_local_iterator
- ( this->priv_bucket_lend(n)
- , this->priv_value_traits_ptr());
- }
-
- BOOST_INTRUSIVE_FORCEINLINE iterator begin() BOOST_NOEXCEPT
- {
- bucket_ptr p;
- siterator s = this->priv_begin(p);
- return this->build_iterator(s, p);
- }
- BOOST_INTRUSIVE_FORCEINLINE const_iterator begin() const BOOST_NOEXCEPT
- { return this->cbegin(); }
- BOOST_INTRUSIVE_FORCEINLINE const_iterator cbegin() const BOOST_NOEXCEPT
- {
- bucket_ptr p;
- siterator s = this->priv_begin(p);
- return this->build_const_iterator(s, p);
- }
- BOOST_INTRUSIVE_FORCEINLINE hasher hash_function() const
- { return this->priv_hasher(); }
- BOOST_INTRUSIVE_FORCEINLINE key_equal key_eq() const
- { return this->priv_equal(); }
- };
- template< class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash
- , class VoidOrKeyEqual, class BucketTraits, class SizeType
- , std::size_t BoolFlags>
- struct get_hashtable_size_wrapper_internal
- {
- typedef hashtable_size_wrapper
- < hashdata_internal
- < ValueTraits
- , VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual
- , BucketTraits, SizeType
- , BoolFlags & ~(hash_bool_flags::constant_time_size_pos)
- >
- , SizeType
- , (BoolFlags& hash_bool_flags::constant_time_size_pos) != 0
- > type;
- };
- #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
- template<class T, class ...Options>
- #else
- template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits, class SizeType, std::size_t BoolFlags>
- #endif
- class hashtable_impl
- : private get_hashtable_size_wrapper_internal
- <ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, SizeType, BoolFlags>::type
- {
- static const bool linear_buckets_flag = (BoolFlags & hash_bool_flags::linear_buckets_pos) != 0;
- typedef typename get_hashtable_size_wrapper_internal
- <ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, SizeType, BoolFlags>::type
- internal_type;
- typedef typename internal_type::size_traits size_traits;
- typedef hash_key_types_base
- < typename ValueTraits::value_type
- , VoidOrKeyOfValue
- > hash_types_base;
- public:
- typedef ValueTraits value_traits;
-
- typedef BucketTraits bucket_traits;
- typedef bucket_plus_vtraits
- <ValueTraits, BucketTraits, linear_buckets_flag> bucket_plus_vtraits_t;
- typedef typename bucket_plus_vtraits_t::const_value_traits_ptr const_value_traits_ptr;
- typedef detail::bool_<linear_buckets_flag> linear_buckets_t;
- typedef typename internal_type::siterator siterator;
- typedef typename internal_type::const_siterator const_siterator;
- using internal_type::begin;
- using internal_type::cbegin;
- using internal_type::end;
- using internal_type::cend;
- using internal_type::hash_function;
- using internal_type::key_eq;
- using internal_type::bucket_size;
- using internal_type::bucket_count;
- using internal_type::local_iterator_to;
- using internal_type::s_local_iterator_to;
- using internal_type::iterator_to;
- using internal_type::bucket_pointer;
- using internal_type::suggested_upper_bucket_count;
- using internal_type::suggested_lower_bucket_count;
- using internal_type::split_count;
-
- typedef typename value_traits::pointer pointer;
- typedef typename value_traits::const_pointer const_pointer;
- typedef typename value_traits::value_type value_type;
- typedef typename hash_types_base::key_type key_type;
- typedef typename hash_types_base::key_of_value key_of_value;
- typedef typename pointer_traits<pointer>::reference reference;
- typedef typename pointer_traits<const_pointer>::reference const_reference;
- typedef typename pointer_traits<pointer>::difference_type difference_type;
- typedef SizeType size_type;
- typedef typename internal_type::key_equal key_equal;
- typedef typename internal_type::hasher hasher;
- typedef typename internal_type::bucket_type bucket_type;
- typedef typename internal_type::bucket_ptr bucket_ptr;
- typedef typename internal_type::iterator iterator;
- typedef typename internal_type::const_iterator const_iterator;
- typedef typename internal_type::local_iterator local_iterator;
- typedef typename internal_type::const_local_iterator const_local_iterator;
- typedef typename value_traits::node_traits node_traits;
- typedef typename node_traits::node node;
- typedef typename pointer_traits
- <pointer>::template rebind_pointer
- < node >::type node_ptr;
- typedef typename pointer_traits
- <pointer>::template rebind_pointer
- < const node >::type const_node_ptr;
- typedef typename pointer_traits
- <node_ptr>::reference node_reference;
- typedef typename pointer_traits
- <const_node_ptr>::reference const_node_reference;
- typedef typename internal_type::slist_node_algorithms slist_node_algorithms;
- static const bool stateful_value_traits = internal_type::stateful_value_traits;
- static const bool store_hash = internal_type::store_hash;
- static const bool unique_keys = 0 != (BoolFlags & hash_bool_flags::unique_keys_pos);
- static const bool constant_time_size = 0 != (BoolFlags & hash_bool_flags::constant_time_size_pos);
- static const bool cache_begin = 0 != (BoolFlags & hash_bool_flags::cache_begin_pos);
- static const bool compare_hash = 0 != (BoolFlags & hash_bool_flags::compare_hash_pos);
- static const bool incremental = 0 != (BoolFlags & hash_bool_flags::incremental_pos);
- static const bool power_2_buckets = incremental || (0 != (BoolFlags & hash_bool_flags::power_2_buckets_pos));
- static const bool optimize_multikey = optimize_multikey_is_true<node_traits>::value && !unique_keys;
- static const bool linear_buckets = linear_buckets_flag;
- static const bool fastmod_buckets = 0 != (BoolFlags & hash_bool_flags::fastmod_buckets_pos);
- static const std::size_t bucket_overhead = internal_type::bucket_overhead;
-
- static const bool is_multikey = !unique_keys;
- private:
-
-
- BOOST_STATIC_ASSERT((!compare_hash || store_hash));
-
-
- BOOST_STATIC_ASSERT(!(fastmod_buckets && power_2_buckets));
- typedef typename internal_type::slist_node_ptr slist_node_ptr;
- typedef typename pointer_traits
- <slist_node_ptr>::template rebind_pointer
- < void >::type void_pointer;
-
-
- typedef unordered_group_adapter<node_traits> group_traits;
- typedef circular_slist_algorithms<group_traits> group_algorithms;
- typedef typename internal_type::store_hash_t store_hash_t;
- typedef detail::bool_<optimize_multikey> optimize_multikey_t;
- typedef detail::bool_<cache_begin> cache_begin_t;
- typedef detail::bool_<power_2_buckets> power_2_buckets_t;
- typedef detail::bool_<fastmod_buckets> fastmod_buckets_t;
- typedef detail::bool_<compare_hash> compare_hash_t;
- typedef typename internal_type::split_traits split_traits;
- typedef group_functions<node_traits> group_functions_t;
- typedef node_functions<node_traits> node_functions_t;
- private:
-
- BOOST_MOVABLE_BUT_NOT_COPYABLE(hashtable_impl)
- static const bool safemode_or_autounlink = internal_type::safemode_or_autounlink;
-
- BOOST_STATIC_ASSERT(!(constant_time_size && ((int)value_traits::link_mode == (int)auto_unlink)));
-
- BOOST_STATIC_ASSERT(!(cache_begin && ((int)value_traits::link_mode == (int)auto_unlink)));
-
-
- public:
- typedef insert_commit_data_impl<store_hash> insert_commit_data;
- private:
- void default_init_actions()
- {
- this->priv_set_sentinel_bucket();
- this->priv_init_buckets_and_cache();
- this->priv_size_count(size_type(0));
- size_type bucket_sz = this->bucket_count();
- BOOST_INTRUSIVE_INVARIANT_ASSERT(bucket_sz != 0);
-
- BOOST_INTRUSIVE_INVARIANT_ASSERT
- (!power_2_buckets || (0 == (bucket_sz & (bucket_sz - 1))));
- this->split_count(this->initial_split_from_bucket_count(bucket_sz));
- }
- BOOST_INTRUSIVE_FORCEINLINE SizeType priv_size_count() const BOOST_NOEXCEPT
- { return this->internal_type::get_hashtable_size_wrapper_size(); }
- BOOST_INTRUSIVE_FORCEINLINE void priv_size_count(SizeType s) BOOST_NOEXCEPT
- { this->internal_type::set_hashtable_size_wrapper_size(s); }
- BOOST_INTRUSIVE_FORCEINLINE void priv_size_inc() BOOST_NOEXCEPT
- { this->internal_type::inc_hashtable_size_wrapper_size(); }
- BOOST_INTRUSIVE_FORCEINLINE void priv_size_dec() BOOST_NOEXCEPT
- { this->internal_type::dec_hashtable_size_wrapper_size(); }
- public:
-
-
-
-
-
-
-
-
-
-
-
-
-
- explicit hashtable_impl ( const bucket_traits &b_traits
- , const hasher & hash_func = hasher()
- , const key_equal &equal_func = key_equal()
- , const value_traits &v_traits = value_traits())
- : internal_type(v_traits, b_traits, hash_func, equal_func)
- { this->default_init_actions(); }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template<class Iterator>
- hashtable_impl ( bool unique, Iterator b, Iterator e
- , const bucket_traits &b_traits
- , const hasher & hash_func = hasher()
- , const key_equal &equal_func = key_equal()
- , const value_traits &v_traits = value_traits())
- : internal_type(v_traits, b_traits, hash_func, equal_func)
- {
- this->default_init_actions();
-
- if(unique)
- this->insert_unique(b, e);
- else
- this->insert_equal(b, e);
- }
-
-
-
-
-
-
-
-
-
- hashtable_impl(BOOST_RV_REF(hashtable_impl) x)
- : internal_type(BOOST_MOVE_BASE(internal_type, x))
- {
- this->priv_swap_cache(x);
- x.priv_init_cache();
- this->priv_size_count(x.priv_size_count());
- x.priv_size_count(size_type(0));
- this->split_count(x.split_count());
- x.split_count(size_type(0));
- }
-
-
- hashtable_impl& operator=(BOOST_RV_REF(hashtable_impl) x)
- { this->swap(x); return *this; }
-
-
-
-
-
-
-
- ~hashtable_impl()
- {}
- #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-
-
-
-
-
-
- iterator begin() BOOST_NOEXCEPT;
-
-
-
-
-
-
-
- const_iterator begin() const BOOST_NOEXCEPT;
-
-
-
-
-
-
-
- const_iterator cbegin() const BOOST_NOEXCEPT;
-
-
-
-
-
- iterator end() BOOST_NOEXCEPT;
-
-
-
-
-
- const_iterator end() const BOOST_NOEXCEPT;
-
-
-
-
-
- const_iterator cend() const BOOST_NOEXCEPT;
-
-
-
-
-
- hasher hash_function() const;
-
-
-
-
-
- key_equal key_eq() const;
- #endif
-
-
-
-
-
-
-
- bool empty() const BOOST_NOEXCEPT
- {
- BOOST_IF_CONSTEXPR(constant_time_size){
- return !this->size();
- }
- else if(cache_begin){
- return this->begin() == this->end();
- }
- else{
- size_type bucket_cnt = this->bucket_count();
- const bucket_type *b = boost::movelib::to_raw_pointer(this->priv_bucket_pointer());
- for (size_type n = 0; n < bucket_cnt; ++n, ++b){
- if(!slist_node_algorithms::is_empty(b->get_node_ptr())){
- return false;
- }
- }
- return true;
- }
- }
-
-
-
-
-
-
- size_type size() const BOOST_NOEXCEPT
- {
- BOOST_IF_CONSTEXPR(constant_time_size)
- return this->priv_size_count();
- else{
- std::size_t len = 0;
- std::size_t bucket_cnt = this->bucket_count();
- const bucket_type *b = boost::movelib::to_raw_pointer(this->priv_bucket_pointer());
- for (std::size_t n = 0; n < bucket_cnt; ++n, ++b){
- len += slist_node_algorithms::count(b->get_node_ptr()) - 1u;
- }
- BOOST_INTRUSIVE_INVARIANT_ASSERT((len <= SizeType(-1)));
- return size_type(len);
- }
- }
-
-
-
-
-
-
-
-
-
-
- void swap(hashtable_impl& other)
- {
-
- ::boost::adl_move_swap(this->priv_equal(), other.priv_equal());
- ::boost::adl_move_swap(this->priv_hasher(), other.priv_hasher());
-
- ::boost::adl_move_swap(this->priv_bucket_traits(), other.priv_bucket_traits());
- ::boost::adl_move_swap(this->priv_value_traits(), other.priv_value_traits());
- this->priv_swap_cache(other);
- this->priv_size_traits().swap(other.priv_size_traits());
- this->priv_split_traits().swap(other.priv_split_traits());
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template <class Cloner, class Disposer>
- BOOST_INTRUSIVE_FORCEINLINE void clone_from(const hashtable_impl &src, Cloner cloner, Disposer disposer)
- { this->priv_clone_from(src, cloner, disposer); }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template <class Cloner, class Disposer>
- BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(hashtable_impl) src, Cloner cloner, Disposer disposer)
- { this->priv_clone_from(static_cast<hashtable_impl&>(src), cloner, disposer); }
-
-
-
-
-
-
-
-
-
-
-
-
- iterator insert_equal(reference value)
- {
- size_type bucket_num;
- std::size_t hash_value;
- siterator prev;
- siterator const it = this->priv_find
- (key_of_value()(value), this->priv_hasher(), this->priv_equal(), bucket_num, hash_value, prev);
- bool const next_is_in_group = optimize_multikey && it != this->priv_end_sit();
- return this->priv_insert_equal_after_find(value, bucket_num, hash_value, prev, next_is_in_group);
- }
-
-
-
-
-
-
-
-
-
-
-
-
- template<class Iterator>
- void insert_equal(Iterator b, Iterator e)
- {
- for (; b != e; ++b)
- this->insert_equal(*b);
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- std::pair<iterator, bool> insert_unique(reference value)
- {
- insert_commit_data commit_data;
- std::pair<iterator, bool> ret = this->insert_unique_check(key_of_value()(value), commit_data);
- if(ret.second){
- ret.first = this->insert_unique_commit(value, commit_data);
- }
- return ret;
- }
-
-
-
-
-
-
-
-
-
-
-
-
- template<class Iterator>
- void insert_unique(Iterator b, Iterator e)
- {
- for (; b != e; ++b)
- this->insert_unique(*b);
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template<class KeyType, class KeyHasher, class KeyEqual>
- std::pair<iterator, bool> insert_unique_check
- ( const KeyType &key
- , KeyHasher hash_func
- , KeyEqual equal_func
- , insert_commit_data &commit_data)
- {
- const std::size_t h = hash_func(key);
- const std::size_t bn = this->priv_hash_to_nbucket(h);
- commit_data.bucket_idx = bn;
- commit_data.set_hash(h);
- bucket_ptr bp = this->priv_bucket_ptr(bn);
- siterator const s = this->priv_find_in_bucket(*bp, key, equal_func, h);
- return std::pair<iterator, bool>(this->build_iterator(s, bp), s == this->priv_end_sit());
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator, bool> insert_unique_check
- ( const key_type &key, insert_commit_data &commit_data)
- { return this->insert_unique_check(key, this->priv_hasher(), this->priv_equal(), commit_data); }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- iterator insert_unique_commit(reference value, const insert_commit_data &commit_data) BOOST_NOEXCEPT
- {
- this->priv_size_inc();
- node_ptr const n = this->priv_value_to_node_ptr(value);
- BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || slist_node_algorithms::unique(n));
- node_functions_t::store_hash(n, commit_data.get_hash(), store_hash_t());
- this->priv_insertion_update_cache(static_cast<size_type>(commit_data.bucket_idx));
- group_functions_t::insert_in_group(n, n, optimize_multikey_t());
- bucket_type& b = this->priv_bucket(commit_data.bucket_idx);
- slist_node_algorithms::link_after(b.get_node_ptr(), n);
- return this->build_iterator(siterator(n), this->to_ptr(b));
- }
-
-
-
-
-
-
-
-
- BOOST_INTRUSIVE_FORCEINLINE void erase(const_iterator i) BOOST_NOEXCEPT
- { this->erase_and_dispose(i, detail::null_disposer()); }
-
-
-
-
-
-
-
-
-
- BOOST_INTRUSIVE_FORCEINLINE void erase(const_iterator b, const_iterator e) BOOST_NOEXCEPT
- { this->erase_and_dispose(b, e, detail::null_disposer()); }
-
-
-
-
-
-
-
-
-
-
-
-
- BOOST_INTRUSIVE_FORCEINLINE size_type erase(const key_type &key)
- { return this->erase(key, this->priv_hasher(), this->priv_equal()); }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template<class KeyType, class KeyHasher, class KeyEqual>
- BOOST_INTRUSIVE_FORCEINLINE size_type erase(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func)
- { return this->erase_and_dispose(key, hash_func, equal_func, detail::null_disposer()); }
-
-
-
-
-
-
-
-
-
-
-
- template<class Disposer>
- BOOST_INTRUSIVE_DOC1ST(void
- , typename detail::disable_if_convertible<Disposer BOOST_INTRUSIVE_I const_iterator>::type)
- erase_and_dispose(const_iterator i, Disposer disposer) BOOST_NOEXCEPT
- {
-
- const bucket_ptr bp = this->priv_get_bucket_ptr(i);
- this->priv_erase_node(*bp, i.slist_it(), this->make_node_disposer(disposer), optimize_multikey_t());
- this->priv_size_dec();
- this->priv_erasure_update_cache(bp);
- }
-
-
-
-
-
-
-
-
-
-
-
-
- template<class Disposer>
- void erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) BOOST_NOEXCEPT
- {
- if(b != e){
-
- size_type first_bucket_num = this->priv_get_bucket_num(b);
- siterator before_first_local_it
- = this->priv_get_previous(this->priv_bucket(first_bucket_num), b.slist_it(), optimize_multikey_t());
- size_type last_bucket_num;
- siterator last_local_it;
-
-
- if(e == this->end()){
- last_bucket_num = size_type(this->bucket_count() - 1u);
- last_local_it = this->sit_end(this->priv_bucket(last_bucket_num));
- }
- else{
- last_local_it = e.slist_it();
- last_bucket_num = this->priv_get_bucket_num(e);
- }
- size_type const num_erased = (size_type)this->priv_erase_node_range
- ( before_first_local_it, first_bucket_num, last_local_it, last_bucket_num
- , this->make_node_disposer(disposer), optimize_multikey_t());
- this->priv_size_count(size_type(this->priv_size_count()-num_erased));
- this->priv_erasure_update_cache_range(first_bucket_num, last_bucket_num);
- }
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template<class Disposer>
- BOOST_INTRUSIVE_FORCEINLINE size_type erase_and_dispose(const key_type &key, Disposer disposer)
- { return this->erase_and_dispose(key, this->priv_hasher(), this->priv_equal(), disposer); }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template<class KeyType, class KeyHasher, class KeyEqual, class Disposer>
- size_type erase_and_dispose(const KeyType& key, KeyHasher hash_func
- ,KeyEqual equal_func, Disposer disposer)
- {
- size_type bucket_num;
- std::size_t h;
- siterator prev;
- siterator it = this->priv_find(key, hash_func, equal_func, bucket_num, h, prev);
- bool const success = it != this->priv_end_sit();
- std::size_t cnt(0);
- if(success){
- if(optimize_multikey){
- siterator past_last_in_group = it;
- (priv_go_to_last_in_group)(past_last_in_group, optimize_multikey_t());
- ++past_last_in_group;
- cnt = this->priv_erase_from_single_bucket
- ( this->priv_bucket(bucket_num), prev
- , past_last_in_group
- , this->make_node_disposer(disposer), optimize_multikey_t());
- }
- else{
- siterator const end_sit = this->priv_bucket_lend(bucket_num);
- do{
- ++cnt;
- ++it;
- }while(it != end_sit &&
- this->priv_is_value_equal_to_key
- (this->priv_value_from_siterator(it), h, key, equal_func, compare_hash_t()));
- slist_node_algorithms::unlink_after_and_dispose(prev.pointed_node(), it.pointed_node(), this->make_node_disposer(disposer));
- }
- this->priv_size_count(size_type(this->priv_size_count()-cnt));
- this->priv_erasure_update_cache();
- }
- return static_cast<size_type>(cnt);
- }
-
-
-
-
-
-
-
-
-
- void clear() BOOST_NOEXCEPT
- {
- this->priv_clear_buckets_and_cache();
- this->priv_size_count(size_type(0));
- }
-
-
-
-
-
-
-
-
-
-
-
- template<class Disposer>
- void clear_and_dispose(Disposer disposer) BOOST_NOEXCEPT
- {
- if(!constant_time_size || !this->empty()){
- size_type num_buckets = this->bucket_count();
- bucket_ptr b = this->priv_bucket_pointer();
- typename internal_type::template typeof_node_disposer<Disposer>::type d(disposer, &this->priv_value_traits());
- for(; num_buckets; ++b){
- --num_buckets;
- slist_node_algorithms::detach_and_dispose(b->get_node_ptr(), d);
- }
- this->priv_size_count(size_type(0));
- }
- this->priv_init_cache();
- }
-
-
-
-
-
- BOOST_INTRUSIVE_FORCEINLINE size_type count(const key_type &key) const
- { return this->count(key, this->priv_hasher(), this->priv_equal()); }
-
-
-
-
-
-
-
-
-
-
-
-
-
- template<class KeyType, class KeyHasher, class KeyEqual>
- size_type count(const KeyType &key, KeyHasher hash_func, KeyEqual equal_func) const
- {
- size_type cnt;
- size_type n_bucket;
- this->priv_local_equal_range(key, hash_func, equal_func, n_bucket, cnt);
- return cnt;
- }
-
-
-
-
-
-
- BOOST_INTRUSIVE_FORCEINLINE iterator find(const key_type &key)
- { return this->find(key, this->priv_hasher(), this->priv_equal()); }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template<class KeyType, class KeyHasher, class KeyEqual>
- iterator find(const KeyType &key, KeyHasher hash_func, KeyEqual equal_func)
- {
- std::size_t h = hash_func(key);
- bucket_ptr bp = this->priv_hash_to_bucket_ptr(h);
- siterator s = this->priv_find_in_bucket(*bp, key, equal_func, h);
- return this->build_iterator(s, bp);
- }
-
-
-
-
-
-
- BOOST_INTRUSIVE_FORCEINLINE const_iterator find(const key_type &key) const
- { return this->find(key, this->priv_hasher(), this->priv_equal()); }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template<class KeyType, class KeyHasher, class KeyEqual>
- const_iterator find
- (const KeyType &key, KeyHasher hash_func, KeyEqual equal_func) const
- {
- std::size_t h = hash_func(key);
- bucket_ptr bp = this->priv_hash_to_bucket_ptr(h);
- siterator s = this->priv_find_in_bucket(*bp, key, equal_func, h);
- return this->build_const_iterator(s, bp);
- }
-
-
-
-
-
-
-
- BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type &key)
- { return this->equal_range(key, this->priv_hasher(), this->priv_equal()); }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template<class KeyType, class KeyHasher, class KeyEqual>
- std::pair<iterator,iterator> equal_range
- (const KeyType &key, KeyHasher hash_func, KeyEqual equal_func)
- {
- priv_equal_range_result ret =
- this->priv_equal_range(key, hash_func, equal_func);
- return std::pair<iterator, iterator>
- ( this->build_iterator(ret.first, ret.bucket_first)
- , this->build_iterator(ret.second, ret.bucket_second));
- }
-
-
-
-
-
-
-
- BOOST_INTRUSIVE_FORCEINLINE std::pair<const_iterator, const_iterator>
- equal_range(const key_type &key) const
- { return this->equal_range(key, this->priv_hasher(), this->priv_equal()); }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- template<class KeyType, class KeyHasher, class KeyEqual>
- std::pair<const_iterator,const_iterator> equal_range
- (const KeyType &key, KeyHasher hash_func, KeyEqual equal_func) const
- {
- priv_equal_range_result ret =
- this->priv_equal_range(key, hash_func, equal_func);
- return std::pair<const_iterator, const_iterator>
- ( this->build_const_iterator(ret.first, ret.bucket_first)
- , this->build_const_iterator(ret.second, ret.bucket_second));
- }
- #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-
-
-
-
-
-
-
-
-
- iterator iterator_to(reference value) BOOST_NOEXCEPT;
-
-
-
-
-
-
-
-
-
- const_iterator iterator_to(const_reference value) const BOOST_NOEXCEPT;
-
-
-
-
-
-
-
-
-
-
-
-
- static local_iterator s_local_iterator_to(reference value) BOOST_NOEXCEPT;
-
-
-
-
-
-
-
-
-
-
-
-
- static const_local_iterator s_local_iterator_to(const_reference value) BOOST_NOEXCEPT;
-
-
-
-
-
-
-
-
-
- local_iterator local_iterator_to(reference value) BOOST_NOEXCEPT;
-
-
-
-
-
-
-
-
-
- const_local_iterator local_iterator_to(const_reference value) const BOOST_NOEXCEPT;
-
-
-
-
-
-
- size_type bucket_count() const BOOST_NOEXCEPT;
-
-
-
-
-
-
-
- size_type bucket_size(size_type n) const BOOST_NOEXCEPT;
- #endif
-
-
-
-
-
-
-
-
- BOOST_INTRUSIVE_FORCEINLINE size_type bucket(const key_type& k) const
- { return this->priv_hash_to_nbucket(this->priv_hash(k)); }
-
-
-
-
-
-
-
-
-
-
-
-
- template<class KeyType, class KeyHasher>
- BOOST_INTRUSIVE_FORCEINLINE size_type bucket(const KeyType& k, KeyHasher hash_func) const
- { return this->priv_hash_to_nbucket(hash_func(k)); }
- #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-
-
-
-
-
-
- bucket_ptr bucket_pointer() const BOOST_NOEXCEPT;
-
-
-
-
-
-
-
-
-
-
-
- local_iterator begin(size_type n) BOOST_NOEXCEPT;
-
-
-
-
-
-
-
-
-
-
-
- const_local_iterator begin(size_type n) const BOOST_NOEXCEPT;
-
-
-
-
-
-
-
-
-
-
-
- const_local_iterator cbegin(size_type n) const BOOST_NOEXCEPT;
-
-
-
-
-
-
-
-
-
-
-
- local_iterator end(size_type n) BOOST_NOEXCEPT;
-
-
-
-
-
-
-
-
-
-
-
- const_local_iterator end(size_type n) const BOOST_NOEXCEPT;
-
-
-
-
-
-
-
-
-
-
-
- const_local_iterator cend(size_type n) const BOOST_NOEXCEPT;
- #endif
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- BOOST_INTRUSIVE_FORCEINLINE void rehash(const bucket_traits &new_bucket_traits)
- { this->priv_rehash_impl(new_bucket_traits, false); }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- BOOST_INTRUSIVE_FORCEINLINE void full_rehash()
- { this->priv_rehash_impl(this->priv_bucket_traits(), true); }
-
-
-
-
-
-
-
-
-
- bool incremental_rehash(bool grow = true)
- {
-
- BOOST_STATIC_ASSERT(( incremental && power_2_buckets ));
- const std::size_t split_idx = this->split_count();
- const std::size_t bucket_cnt = this->bucket_count();
- bool ret = false;
- if(grow){
-
- if((ret = split_idx < bucket_cnt)){
- const std::size_t bucket_to_rehash = split_idx - bucket_cnt/2u;
- bucket_type &old_bucket = this->priv_bucket(bucket_to_rehash);
- this->inc_split_count();
-
-
-
- incremental_rehash_rollback<bucket_type, split_traits, slist_node_algorithms> rollback
- ( this->priv_bucket(split_idx), old_bucket, this->priv_split_traits());
- siterator before_i(old_bucket.get_node_ptr());
- siterator i(before_i); ++i;
- siterator end_sit = linear_buckets ? siterator() : before_i;
- for( ; i != end_sit; i = before_i, ++i){
- const value_type &v = this->priv_value_from_siterator(i);
- const std::size_t hash_value = this->priv_stored_or_compute_hash(v, store_hash_t());
- const std::size_t new_n = this->priv_hash_to_nbucket(hash_value);
- siterator last = i;
- (priv_go_to_last_in_group)(last, optimize_multikey_t());
- if(new_n == bucket_to_rehash){
- before_i = last;
- }
- else{
- bucket_type &new_b = this->priv_bucket(new_n);
- slist_node_algorithms::transfer_after(new_b.get_node_ptr(), before_i.pointed_node(), last.pointed_node());
- }
- }
- rollback.release();
- this->priv_erasure_update_cache();
- }
- }
- else if((ret = split_idx > bucket_cnt/2u)){
- const std::size_t target_bucket_num = split_idx - 1u - bucket_cnt/2u;
- bucket_type &target_bucket = this->priv_bucket(target_bucket_num);
- bucket_type &source_bucket = this->priv_bucket(split_idx-1u);
- slist_node_algorithms::transfer_after(target_bucket.get_node_ptr(), source_bucket.get_node_ptr());
- this->dec_split_count();
- this->priv_insertion_update_cache(target_bucket_num);
- }
- return ret;
- }
-
-
-
-
-
-
-
-
-
-
-
-
-
- bool incremental_rehash(const bucket_traits &new_bucket_traits) BOOST_NOEXCEPT
- {
-
- BOOST_STATIC_ASSERT(( incremental && power_2_buckets ));
- const bucket_ptr new_buckets = new_bucket_traits.bucket_begin();
- const size_type new_bucket_count_stdszt = static_cast<SizeType>(new_bucket_traits.bucket_count() - bucket_overhead);
- BOOST_INTRUSIVE_INVARIANT_ASSERT(sizeof(size_type) >= sizeof(std::size_t) || new_bucket_count_stdszt <= size_type(-1));
- size_type new_bucket_count = static_cast<size_type>(new_bucket_count_stdszt);
- const size_type old_bucket_count = static_cast<size_type>(this->priv_usable_bucket_count());
- const size_type split_idx = this->split_count();
-
- if(new_bucket_count/2 == old_bucket_count){
- if(!(split_idx >= old_bucket_count))
- return false;
- }
- else if(new_bucket_count == old_bucket_count/2){
- if(!(split_idx <= new_bucket_count))
- return false;
- }
- else{
- return false;
- }
- const size_type ini_n = (size_type)this->priv_get_cache_bucket_num();
- const bucket_ptr old_buckets = this->priv_bucket_pointer();
- this->priv_unset_sentinel_bucket();
- this->priv_initialize_new_buckets(old_buckets, old_bucket_count, new_buckets, new_bucket_count);
- if (&new_bucket_traits != &this->priv_bucket_traits())
- this->priv_bucket_traits() = new_bucket_traits;
- if(old_buckets != new_buckets){
- for(size_type n = ini_n; n < split_idx; ++n){
- slist_node_ptr new_bucket_nodeptr = new_bucket_traits.bucket_begin()[difference_type(n)].get_node_ptr();
- slist_node_ptr old_bucket_node_ptr = old_buckets[difference_type(n)].get_node_ptr();
- slist_node_algorithms::transfer_after(new_bucket_nodeptr, old_bucket_node_ptr);
- }
-
- this->priv_set_cache_bucket_num(ini_n);
- }
- this->priv_set_sentinel_bucket();
- return true;
- }
- #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
-
-
-
-
-
-
-
- size_type split_count() const BOOST_NOEXCEPT;
-
-
-
-
-
-
-
-
-
- static size_type suggested_upper_bucket_count(size_type n) BOOST_NOEXCEPT;
-
-
-
-
-
-
-
-
-
- static size_type suggested_lower_bucket_count(size_type n) BOOST_NOEXCEPT;
- #endif
- friend bool operator==(const hashtable_impl &x, const hashtable_impl &y)
- {
-
- if(constant_time_size && x.size() != y.size()){
- return false;
- }
- if (boost::intrusive::iterator_udistance(x.begin(), x.end()) != x.size())
- return false;
-
- for (const_iterator ix = x.cbegin(), ex = x.cend(); ix != ex; ++ix){
- std::pair<const_iterator, const_iterator> eqx(x.equal_range(key_of_value()(*ix))),
- eqy(y.equal_range(key_of_value()(*ix)));
- if (boost::intrusive::iterator_distance(eqx.first, eqx.second) !=
- boost::intrusive::iterator_distance(eqy.first, eqy.second) ||
- !(priv_algo_is_permutation)(eqx.first, eqx.second, eqy.first) ){
- return false;
- }
- ix = eqx.second;
- }
- return true;
- }
- friend bool operator!=(const hashtable_impl &x, const hashtable_impl &y)
- { return !(x == y); }
- friend bool operator<(const hashtable_impl &x, const hashtable_impl &y)
- { return ::boost::intrusive::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
- friend bool operator>(const hashtable_impl &x, const hashtable_impl &y)
- { return y < x; }
- friend bool operator<=(const hashtable_impl &x, const hashtable_impl &y)
- { return !(y < x); }
- friend bool operator>=(const hashtable_impl &x, const hashtable_impl &y)
- { return !(x < y); }
-
- BOOST_INTRUSIVE_FORCEINLINE void check() const {}
- private:
- static void priv_initialize_new_buckets
- ( bucket_ptr old_buckets, size_type old_bucket_count
- , bucket_ptr new_buckets, size_type new_bucket_count)
- {
-
- const bool same_buffer = old_buckets == new_buckets;
- if (same_buffer && new_bucket_count <= old_bucket_count) {
-
- }
- else {
- bucket_ptr p;
- size_type c;
- if (same_buffer) {
- p = old_buckets + std::ptrdiff_t(old_bucket_count);
- c = size_type(new_bucket_count - old_bucket_count);
- }
- else {
- p = new_buckets;
- c = new_bucket_count;
- }
- internal_type::priv_init_buckets(p, c);
- }
- }
- void priv_rehash_impl(const bucket_traits &new_bucket_traits, bool do_full_rehash)
- {
- const std::size_t nbc = new_bucket_traits.bucket_count() - bucket_overhead;
- BOOST_INTRUSIVE_INVARIANT_ASSERT(sizeof(SizeType) >= sizeof(std::size_t) || nbc <= SizeType(-1));
- const bucket_ptr new_buckets = new_bucket_traits.bucket_begin();
- const size_type new_bucket_count = static_cast<SizeType>(nbc);
- const bucket_ptr old_buckets = this->priv_bucket_pointer();
- const size_type old_bucket_count = this->bucket_count();
-
- BOOST_INTRUSIVE_INVARIANT_ASSERT
- (!power_2_buckets || (0 == (new_bucket_count & (new_bucket_count-1u))));
- const bool same_buffer = old_buckets == new_buckets;
-
-
- const bool fast_shrink = (!do_full_rehash) && (!incremental) && (old_bucket_count >= new_bucket_count) &&
- (power_2_buckets || (old_bucket_count % new_bucket_count) == 0);
-
-
- size_type new_first_bucket_num = new_bucket_count;
- size_type old_bucket_cache = (size_type)this->priv_get_cache_bucket_num();
- if(same_buffer && fast_shrink && (old_bucket_cache < new_bucket_count)){
- new_first_bucket_num = old_bucket_cache;
- old_bucket_cache = new_bucket_count;
- }
- if (!do_full_rehash)
- this->priv_initialize_new_buckets(old_buckets, old_bucket_count, new_buckets, new_bucket_count);
-
-
-
- typedef typename internal_type::template typeof_node_disposer<detail::null_disposer>::type NodeDisposer;
- typedef exception_bucket_disposer<bucket_type, slist_node_algorithms, NodeDisposer, size_type> ArrayDisposer;
- NodeDisposer nd(this->make_node_disposer(detail::null_disposer()));
- ArrayDisposer rollback1(new_buckets[0], nd, new_bucket_count);
- ArrayDisposer rollback2(old_buckets[0], nd, old_bucket_count);
-
- size_type const size_backup = this->priv_size_count();
- this->priv_size_count(0);
-
- this->priv_init_cache();
- this->priv_unset_sentinel_bucket();
- const size_type split = this->rehash_split_from_bucket_count(new_bucket_count);
-
- for(size_type n = old_bucket_cache; n < old_bucket_count; ++n){
- bucket_type &old_bucket = old_buckets[difference_type(n)];
- if(!fast_shrink){
- siterator before_i(old_bucket.get_node_ptr());
- siterator i(before_i); ++i;
- siterator end_sit(this->sit_end(old_bucket));
- for(
- ; i != end_sit
- ; i = before_i, ++i){
-
- std::size_t hash_value;
- if(do_full_rehash){
- value_type &v = this->priv_value_from_siterator(i);
- hash_value = this->priv_hasher()(key_of_value()(v));
- node_functions_t::store_hash(this->priv_value_to_node_ptr(v), hash_value, store_hash_t());
- }
- else{
- const value_type &v = this->priv_value_from_siterator(i);
- hash_value = this->priv_stored_or_compute_hash(v, store_hash_t());
- }
-
- const size_type new_n = (size_type)hash_to_bucket_split<power_2_buckets, incremental>
- (hash_value, new_bucket_count, split, fastmod_buckets_t());
-
- if(cache_begin && new_n < new_first_bucket_num)
- new_first_bucket_num = new_n;
-
- siterator last = i;
- (priv_go_to_last_in_group)(i, optimize_multikey_t());
- if(same_buffer && new_n == n){
- before_i = last;
- }
- else{
- bucket_type &new_b = new_buckets[difference_type(new_n)];
- slist_node_algorithms::transfer_after(new_b.get_node_ptr(), before_i.pointed_node(), last.pointed_node());
- }
- }
- }
- else{
- const size_type new_n = (size_type)hash_to_bucket_split<power_2_buckets, incremental>
- (n, new_bucket_count, split, fastmod_buckets_t());
- if(cache_begin && new_n < new_first_bucket_num)
- new_first_bucket_num = new_n;
- bucket_type &new_b = new_buckets[difference_type(new_n)];
- siterator last = this->priv_get_last(old_bucket, optimize_multikey_t());
- slist_node_algorithms::transfer_after(new_b.get_node_ptr(), old_bucket.get_node_ptr(), last.pointed_node());
- }
- }
- this->priv_size_count(size_backup);
- this->split_count(split);
- if(&new_bucket_traits != &this->priv_bucket_traits())
- this->priv_bucket_traits() = new_bucket_traits;
- this->priv_set_sentinel_bucket();
- this->priv_set_cache_bucket_num(new_first_bucket_num);
- rollback1.release();
- rollback2.release();
- }
- template <class MaybeConstHashtableImpl, class Cloner, class Disposer>
- void priv_clone_from(MaybeConstHashtableImpl &src, Cloner cloner, Disposer disposer)
- {
- this->clear_and_dispose(disposer);
- if(!constant_time_size || !src.empty()){
- const size_type src_bucket_count = src.bucket_count();
- const size_type dst_bucket_count = this->bucket_count();
-
- BOOST_INTRUSIVE_INVARIANT_ASSERT
- (!power_2_buckets || (0 == (src_bucket_count & (src_bucket_count-1))));
- BOOST_INTRUSIVE_INVARIANT_ASSERT
- (!power_2_buckets || (0 == (dst_bucket_count & (dst_bucket_count-1))));
-
- const bool structural_copy = (!incremental) && (src_bucket_count >= dst_bucket_count) &&
- (power_2_buckets || (src_bucket_count % dst_bucket_count) == 0);
- if(structural_copy){
- this->priv_structural_clone_from(src, cloner, disposer);
- }
- else{
-
-
- typedef typename detail::if_c< detail::is_const<MaybeConstHashtableImpl>::value
- , typename MaybeConstHashtableImpl::const_iterator
- , typename MaybeConstHashtableImpl::iterator
- >::type clone_iterator;
- clone_iterator b(src.begin()), e(src.end());
- detail::exception_disposer<hashtable_impl, Disposer> rollback(*this, disposer);
- for(; b != e; ++b){
-
-
- std::size_t const hash_to_store = this->priv_stored_or_compute_hash(*b, store_hash_t());
- size_type const bucket_number = this->priv_hash_to_nbucket(hash_to_store);
- typedef typename detail::if_c
- <detail::is_const<MaybeConstHashtableImpl>::value, const_reference, reference>::type reference_type;
- reference_type r = *b;
- this->priv_clone_front_in_bucket<reference_type>(bucket_number, r, hash_to_store, cloner);
- }
- rollback.release();
- }
- }
- }
- template<class ValueReference, class Cloner>
- void priv_clone_front_in_bucket( size_type const bucket_number
- , typename detail::identity<ValueReference>::type src_ref
- , std::size_t const hash_to_store, Cloner cloner)
- {
-
-
- bucket_type &cur_bucket = this->priv_bucket(bucket_number);
- siterator const prev(cur_bucket.get_node_ptr());
-
-
-
- bool const next_is_in_group = optimize_multikey && !this->priv_bucket_empty(bucket_number) &&
- this->priv_equal()( key_of_value()(src_ref)
- , key_of_value()(this->priv_value_from_siterator(++siterator(prev))));
- this->priv_insert_equal_after_find(*cloner(src_ref), bucket_number, hash_to_store, prev, next_is_in_group);
- }
- template <class MaybeConstHashtableImpl, class Cloner, class Disposer>
- void priv_structural_clone_from(MaybeConstHashtableImpl &src, Cloner cloner, Disposer disposer)
- {
-
- const size_type src_bucket_count = src.bucket_count();
- const size_type dst_bucket_count = this->bucket_count();
- size_type constructed = 0;
- typedef typename internal_type::template typeof_node_disposer<Disposer>::type NodeDisposer;
- NodeDisposer node_disp(disposer, &this->priv_value_traits());
- exception_bucket_disposer<bucket_type, slist_node_algorithms, NodeDisposer, size_type>
- rollback(this->priv_bucket(0), node_disp, constructed);
-
- for(
- ; constructed < src_bucket_count
- ; ++constructed){
- const size_type new_n = (size_type)hash_to_bucket_split<power_2_buckets, incremental>
- (constructed, dst_bucket_count, this->split_count(), fastmod_buckets_t());
- bucket_type &src_b = src.priv_bucket(constructed);
- for( siterator b(this->priv_bucket_lbegin(src_b)), e(this->priv_bucket_lend(src_b)); b != e; ++b){
- typedef typename detail::if_c
- <detail::is_const<MaybeConstHashtableImpl>::value, const_reference, reference>::type reference_type;
- reference_type r = this->priv_value_from_siterator(b);
- this->priv_clone_front_in_bucket<reference_type>
- (new_n, r, this->priv_stored_hash(b, store_hash_t()), cloner);
- }
- }
- this->priv_hasher() = src.priv_hasher();
- this->priv_equal() = src.priv_equal();
- rollback.release();
- this->priv_size_count(src.priv_size_count());
- this->split_count(dst_bucket_count);
- this->priv_set_cache_bucket_num(0u);
- this->priv_erasure_update_cache();
- }
- iterator priv_insert_equal_after_find(reference value, size_type bucket_num, std::size_t hash_value, siterator prev, bool const next_is_in_group)
- {
-
- node_ptr n = this->priv_value_to_node_ptr(value);
- node_functions_t::store_hash(n, hash_value, store_hash_t());
-
- BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || slist_node_algorithms::unique(n));
-
- group_functions_t::insert_in_group
- ( next_is_in_group ? dcast_bucket_ptr<node>((++siterator(prev)).pointed_node()) : n
- , n, optimize_multikey_t());
-
- this->priv_insertion_update_cache(bucket_num);
- this->priv_size_inc();
- slist_node_algorithms::link_after(prev.pointed_node(), n);
- return this->build_iterator(siterator(n), this->priv_bucket_ptr(bucket_num));
- }
- template<class KeyType, class KeyHasher, class KeyEqual>
- siterator priv_find
- ( const KeyType &key, KeyHasher hash_func
- , KeyEqual equal_func, size_type &bucket_number, std::size_t &h, siterator &previt) const
- {
- h = hash_func(key);
- bucket_number = this->priv_hash_to_nbucket(h);
- bucket_type& b = this->priv_bucket(bucket_number);
- siterator prev = this->sit_bbegin(b);
- siterator it = prev;
- siterator const endit = this->sit_end(b);
- while (++it != endit) {
- if (this->priv_is_value_equal_to_key
- (this->priv_value_from_siterator(it), h, key, equal_func, compare_hash_t())) {
- previt = prev;
- return it;
- }
- (priv_go_to_last_in_group)(it, optimize_multikey_t());
- prev = it;
- }
- previt = b.get_node_ptr();
- return this->priv_end_sit();
- }
- template<class KeyType, class KeyEqual>
- siterator priv_find_in_bucket
- (bucket_type &b, const KeyType& key, KeyEqual equal_func, const std::size_t h) const
- {
- siterator it(this->sit_begin(b));
- siterator const endit(this->sit_end(b));
- for (; it != endit; (priv_go_to_last_in_group)(it, optimize_multikey_t()), ++it) {
- if (BOOST_LIKELY(this->priv_is_value_equal_to_key
- (this->priv_value_from_siterator(it), h, key, equal_func, compare_hash_t()))) {
- return it;
- }
- }
- return this->priv_end_sit();
- }
- template<class KeyType, class KeyEqual>
- BOOST_INTRUSIVE_FORCEINLINE bool priv_is_value_equal_to_key
- (const value_type &v, const std::size_t h, const KeyType &key, KeyEqual equal_func, detail::true_) const
- { return this->priv_stored_or_compute_hash(v, store_hash_t()) == h && equal_func(key, key_of_value()(v)); }
- template<class KeyType, class KeyEqual>
- BOOST_INTRUSIVE_FORCEINLINE bool priv_is_value_equal_to_key
- (const value_type& v, const std::size_t , const KeyType& key, KeyEqual equal_func, detail::false_) const
- { return equal_func(key, key_of_value()(v)); }
-
- BOOST_INTRUSIVE_FORCEINLINE static void priv_go_to_last_in_group
- (siterator &it_first_in_group, detail::true_) BOOST_NOEXCEPT
- {
- it_first_in_group =
- (group_functions_t::get_last_in_group
- (dcast_bucket_ptr<node>(it_first_in_group.pointed_node()), optimize_multikey_t()));
- }
-
- BOOST_INTRUSIVE_FORCEINLINE static void priv_go_to_last_in_group
- (siterator , detail::false_) BOOST_NOEXCEPT
- { }
- template<class KeyType, class KeyHasher, class KeyEqual>
- std::pair<siterator, siterator> priv_local_equal_range
- ( const KeyType &key
- , KeyHasher hash_func
- , KeyEqual equal_func
- , size_type &found_bucket
- , size_type &cnt) const
- {
- std::size_t internal_cnt = 0;
-
-
- siterator prev;
- size_type n_bucket;
- std::size_t h;
- std::pair<siterator, siterator> to_return
- ( this->priv_find(key, hash_func, equal_func, n_bucket, h, prev)
- , this->priv_end_sit());
- if(to_return.first != to_return.second){
- found_bucket = n_bucket;
-
-
- siterator it = to_return.first;
- siterator const bend = this->priv_bucket_lend(n_bucket);
- BOOST_IF_CONSTEXPR(optimize_multikey){
- siterator past_last_in_group_it = it;
- (priv_go_to_last_in_group)(past_last_in_group_it, optimize_multikey_t());
- ++past_last_in_group_it;
- internal_cnt += boost::intrusive::iterator_udistance(++it, past_last_in_group_it) + 1u;
- if (past_last_in_group_it != bend)
- to_return.second = past_last_in_group_it;
- }
- else{
- do {
- ++internal_cnt;
- ++it;
- } while(it != bend &&
- this->priv_is_value_equal_to_key
- (this->priv_value_from_siterator(it), h, key, equal_func, compare_hash_t()));
- if (it != bend)
- to_return.second = it;
- }
- }
- cnt = size_type(internal_cnt);
- return to_return;
- }
- struct priv_equal_range_result
- {
- siterator first;
- siterator second;
- bucket_ptr bucket_first;
- bucket_ptr bucket_second;
- };
- template<class KeyType, class KeyHasher, class KeyEqual>
- priv_equal_range_result priv_equal_range
- ( const KeyType &key
- , KeyHasher hash_func
- , KeyEqual equal_func) const
- {
- size_type n_bucket;
- size_type cnt;
-
- const std::pair<siterator, siterator> to_return
- (this->priv_local_equal_range(key, hash_func, equal_func, n_bucket, cnt));
- priv_equal_range_result r;
- r.first = to_return.first;
- r.second = to_return.second;
-
-
- if(to_return.first == to_return.second) {
- r.bucket_first = r.bucket_second = this->priv_invalid_bucket_ptr();
- }
- else if (to_return.second != this->priv_end_sit()) {
- r.bucket_first = this->priv_bucket_ptr(n_bucket);
- }
- else{
- r.bucket_first = this->priv_bucket_ptr(n_bucket);
- const size_type max_bucket = this->bucket_count();
- do{
- ++n_bucket;
- } while (n_bucket != max_bucket && this->priv_bucket_empty(n_bucket));
- if (n_bucket == max_bucket){
- r.bucket_second = this->priv_invalid_bucket_ptr();
- }
- else{
- r.bucket_second = this->priv_bucket_ptr(n_bucket);
- r.second = siterator(r.bucket_second->begin_ptr());
- }
- }
- return r;
- }
- BOOST_INTRUSIVE_FORCEINLINE size_type priv_get_bucket_num(const_iterator it) BOOST_NOEXCEPT
- { return this->priv_get_bucket_num(it, linear_buckets_t()); }
- BOOST_INTRUSIVE_FORCEINLINE size_type priv_get_bucket_num(const_iterator it, detail::true_) BOOST_NOEXCEPT
- { return size_type(it.get_bucket_ptr() - this->priv_bucket_pointer()); }
- BOOST_INTRUSIVE_FORCEINLINE size_type priv_get_bucket_num(const_iterator it, detail::false_) BOOST_NOEXCEPT
- { return this->priv_get_bucket_num_hash_dispatch(it.slist_it(), store_hash_t()); }
- BOOST_INTRUSIVE_FORCEINLINE size_type priv_get_bucket_num_hash_dispatch(siterator it, detail::true_) BOOST_NOEXCEPT
- { return (size_type)this->priv_hash_to_nbucket(this->priv_stored_hash(it, store_hash_t())); }
- size_type priv_get_bucket_num_hash_dispatch(siterator it, detail::false_) BOOST_NOEXCEPT
- {
- const bucket_type &f = this->priv_bucket(0u);
- slist_node_ptr bb = group_functions_t::get_bucket_before_begin
- ( this->priv_bucket_lbbegin(0u).pointed_node()
- , this->priv_bucket_lbbegin(this->priv_usable_bucket_count() - 1u).pointed_node()
- , it.pointed_node()
- , optimize_multikey_t());
-
- const bucket_type &b = static_cast<const bucket_type&>(*bb);
-
- return static_cast<size_type>(&b - &f);
- }
- BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_get_bucket_ptr(const_iterator it) BOOST_NOEXCEPT
- { return this->priv_get_bucket_ptr(it, linear_buckets_t()); }
- BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_get_bucket_ptr(const_iterator it, detail::true_) BOOST_NOEXCEPT
- { return it.get_bucket_ptr(); }
- BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_get_bucket_ptr(const_iterator it, detail::false_) BOOST_NOEXCEPT
- { return this->priv_bucket_ptr(this->priv_get_bucket_num_hash_dispatch(it.slist_it(), store_hash_t())); }
-
- };
- template < class T
- , class PackedOptions
- >
- struct make_bucket_traits
- {
-
- typedef typename detail::get_value_traits
- <T, typename PackedOptions::proto_value_traits>::type value_traits;
- typedef typename PackedOptions::bucket_traits specified_bucket_traits;
-
- typedef bucket_traits_impl
- < typename unordered_bucket_ptr_impl
- <value_traits>::type
- , std::size_t> bucket_traits_t;
- typedef typename
- detail::if_c< detail::is_same
- < specified_bucket_traits
- , default_bucket_traits
- >::value
- , bucket_traits_t
- , specified_bucket_traits
- >::type type;
- };
- #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
- template<class T, class ...Options>
- #else
- template<class T, class O1 = void, class O2 = void
- , class O3 = void, class O4 = void
- , class O5 = void, class O6 = void
- , class O7 = void, class O8 = void
- , class O9 = void, class O10= void
- , class O11= void
- >
- #endif
- struct make_hashtable
- {
-
- typedef typename pack_options
- < hashtable_defaults,
- #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
- O1, O2, O3, O4, O5, O6, O7, O8, O9, O10, O11
- #else
- Options...
- #endif
- >::type packed_options;
- typedef typename detail::get_value_traits
- <T, typename packed_options::proto_value_traits>::type value_traits;
- typedef typename make_bucket_traits
- <T, packed_options>::type bucket_traits;
- typedef hashtable_impl
- < value_traits
- , typename packed_options::key_of_value
- , typename packed_options::hash
- , typename packed_options::equal
- , bucket_traits
- , typename packed_options::size_type
- , (std::size_t(false)*hash_bool_flags::unique_keys_pos)
- |(std::size_t(packed_options::constant_time_size)*hash_bool_flags::constant_time_size_pos)
- |(std::size_t(packed_options::power_2_buckets)*hash_bool_flags::power_2_buckets_pos)
- |(std::size_t(packed_options::cache_begin)*hash_bool_flags::cache_begin_pos)
- |(std::size_t(packed_options::compare_hash)*hash_bool_flags::compare_hash_pos)
- |(std::size_t(packed_options::incremental)*hash_bool_flags::incremental_pos)
- |(std::size_t(packed_options::linear_buckets)*hash_bool_flags::linear_buckets_pos)
- |(std::size_t(packed_options::fastmod_buckets)*hash_bool_flags::fastmod_buckets_pos)
- > implementation_defined;
-
- typedef implementation_defined type;
- };
- #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
- #if defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
- template<class T, class ...Options>
- #else
- template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9, class O10>
- #endif
- class hashtable
- : public make_hashtable<T,
- #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
- O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
- #else
- Options...
- #endif
- >::type
- {
- typedef typename make_hashtable<T,
- #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
- O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
- #else
- Options...
- #endif
- >::type Base;
- BOOST_MOVABLE_BUT_NOT_COPYABLE(hashtable)
- public:
- typedef typename Base::value_traits value_traits;
- typedef typename Base::iterator iterator;
- typedef typename Base::const_iterator const_iterator;
- typedef typename Base::bucket_ptr bucket_ptr;
- typedef typename Base::size_type size_type;
- typedef typename Base::hasher hasher;
- typedef typename Base::bucket_traits bucket_traits;
- typedef typename Base::key_equal key_equal;
-
- BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
- BOOST_INTRUSIVE_FORCEINLINE explicit hashtable ( const bucket_traits &b_traits
- , const hasher & hash_func = hasher()
- , const key_equal &equal_func = key_equal()
- , const value_traits &v_traits = value_traits())
- : Base(b_traits, hash_func, equal_func, v_traits)
- {}
- BOOST_INTRUSIVE_FORCEINLINE hashtable(BOOST_RV_REF(hashtable) x)
- : Base(BOOST_MOVE_BASE(Base, x))
- {}
- BOOST_INTRUSIVE_FORCEINLINE hashtable& operator=(BOOST_RV_REF(hashtable) x)
- { return static_cast<hashtable&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
- template <class Cloner, class Disposer>
- BOOST_INTRUSIVE_FORCEINLINE void clone_from(const hashtable &src, Cloner cloner, Disposer disposer)
- { Base::clone_from(src, cloner, disposer); }
- template <class Cloner, class Disposer>
- BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(hashtable) src, Cloner cloner, Disposer disposer)
- { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); }
- };
- #endif
- }
- }
- #include <boost/intrusive/detail/config_end.hpp>
- #endif
|