9
3

hashtable.hpp 152 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052305330543055305630573058305930603061306230633064306530663067306830693070307130723073307430753076307730783079308030813082308330843085308630873088308930903091309230933094309530963097309830993100310131023103310431053106310731083109311031113112311331143115311631173118311931203121312231233124312531263127312831293130313131323133313431353136313731383139314031413142314331443145314631473148314931503151315231533154315531563157315831593160316131623163316431653166316731683169317031713172317331743175317631773178317931803181318231833184318531863187318831893190319131923193319431953196319731983199320032013202320332043205320632073208320932103211321232133214321532163217321832193220322132223223322432253226322732283229323032313232323332343235323632373238323932403241324232433244324532463247324832493250325132523253325432553256325732583259326032613262326332643265326632673268326932703271327232733274327532763277327832793280328132823283328432853286328732883289329032913292329332943295329632973298329933003301330233033304330533063307330833093310331133123313331433153316331733183319332033213322332333243325332633273328332933303331333233333334333533363337333833393340334133423343334433453346334733483349335033513352335333543355335633573358335933603361336233633364336533663367336833693370337133723373337433753376337733783379338033813382338333843385338633873388338933903391339233933394339533963397339833993400340134023403340434053406340734083409341034113412341334143415341634173418341934203421342234233424342534263427342834293430343134323433343434353436343734383439344034413442344334443445344634473448344934503451345234533454345534563457345834593460346134623463346434653466346734683469347034713472347334743475347634773478347934803481348234833484348534863487348834893490349134923493349434953496349734983499350035013502350335043505350635073508350935103511351235133514351535163517351835193520352135223523352435253526352735283529353035313532353335343535353635373538353935403541354235433544354535463547354835493550355135523553355435553556355735583559356035613562356335643565356635673568356935703571357235733574357535763577357835793580358135823583358435853586358735883589359035913592359335943595359635973598359936003601360236033604360536063607360836093610361136123613361436153616361736183619362036213622362336243625362636273628362936303631363236333634363536363637363836393640364136423643364436453646364736483649365036513652365336543655365636573658365936603661366236633664
  1. /////////////////////////////////////////////////////////////////////////////
  2. //
  3. // (C) Copyright Ion Gaztanaga 2006-2015
  4. //
  5. // Distributed under the Boost Software License, Version 1.0.
  6. // (See accompanying file LICENSE_1_0.txt or copy at
  7. // http://www.boost.org/LICENSE_1_0.txt)
  8. //
  9. // See http://www.boost.org/libs/intrusive for documentation.
  10. //
  11. /////////////////////////////////////////////////////////////////////////////
  12. #ifndef BOOST_INTRUSIVE_HASHTABLE_HPP
  13. #define BOOST_INTRUSIVE_HASHTABLE_HPP
  14. #include <boost/intrusive/detail/config_begin.hpp>
  15. #include <boost/intrusive/intrusive_fwd.hpp>
  16. //General intrusive utilities
  17. #include <boost/intrusive/detail/hashtable_node.hpp>
  18. #include <boost/intrusive/detail/transform_iterator.hpp>
  19. #include <boost/intrusive/link_mode.hpp>
  20. #include <boost/intrusive/detail/ebo_functor_holder.hpp>
  21. #include <boost/intrusive/detail/is_stateful_value_traits.hpp>
  22. #include <boost/intrusive/detail/node_to_value.hpp>
  23. #include <boost/intrusive/detail/exception_disposer.hpp>
  24. #include <boost/intrusive/detail/node_cloner_disposer.hpp>
  25. #include <boost/intrusive/detail/simple_disposers.hpp>
  26. #include <boost/intrusive/detail/size_holder.hpp>
  27. #include <boost/intrusive/detail/iterator.hpp>
  28. //Implementation utilities
  29. #include <boost/intrusive/unordered_set_hook.hpp>
  30. #include <boost/intrusive/slist.hpp>
  31. #include <boost/intrusive/pointer_traits.hpp>
  32. #include <boost/intrusive/detail/mpl.hpp>
  33. //boost
  34. #include <boost/functional/hash.hpp>
  35. #include <boost/intrusive/detail/assert.hpp>
  36. #include <boost/static_assert.hpp>
  37. #include <boost/move/utility_core.hpp>
  38. #include <boost/move/adl_move_swap.hpp>
  39. //std C++
  40. #include <boost/intrusive/detail/minimal_less_equal_header.hpp> //std::equal_to
  41. #include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair
  42. #include <algorithm> //std::lower_bound, std::upper_bound
  43. #include <cstddef> //std::size_t
  44. #if defined(BOOST_HAS_PRAGMA_ONCE)
  45. # pragma once
  46. #endif
  47. namespace boost {
  48. namespace intrusive {
  49. /// @cond
  50. template<class InputIt, class T>
  51. InputIt priv_algo_find(InputIt first, InputIt last, const T& value)
  52. {
  53. for (; first != last; ++first) {
  54. if (*first == value) {
  55. return first;
  56. }
  57. }
  58. return last;
  59. }
  60. template<class InputIt, class T>
  61. typename boost::intrusive::iterator_traits<InputIt>::difference_type
  62. priv_algo_count(InputIt first, InputIt last, const T& value)
  63. {
  64. typename boost::intrusive::iterator_traits<InputIt>::difference_type ret = 0;
  65. for (; first != last; ++first) {
  66. if (*first == value) {
  67. ret++;
  68. }
  69. }
  70. return ret;
  71. }
  72. template <class ForwardIterator1, class ForwardIterator2>
  73. bool priv_algo_is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)
  74. {
  75. typedef typename
  76. boost::intrusive::iterator_traits<ForwardIterator2>::difference_type
  77. distance_type;
  78. //Efficiently compare identical prefixes: O(N) if sequences
  79. //have the same elements in the same order.
  80. for ( ; first1 != last1; ++first1, ++first2){
  81. if (! (*first1 == *first2))
  82. break;
  83. }
  84. if (first1 == last1){
  85. return true;
  86. }
  87. //Establish last2 assuming equal ranges by iterating over the
  88. //rest of the list.
  89. ForwardIterator2 last2 = first2;
  90. boost::intrusive::iterator_advance(last2, boost::intrusive::iterator_distance(first1, last1));
  91. for(ForwardIterator1 scan = first1; scan != last1; ++scan){
  92. if (scan != (priv_algo_find)(first1, scan, *scan)){
  93. continue; //We've seen this one before.
  94. }
  95. distance_type matches = (priv_algo_count)(first2, last2, *scan);
  96. if (0 == matches || (priv_algo_count)(scan, last1, *scan != matches)){
  97. return false;
  98. }
  99. }
  100. return true;
  101. }
  102. template<int Dummy = 0>
  103. struct prime_list_holder
  104. {
  105. private:
  106. template <class SizeType> // sizeof(SizeType) < sizeof(std::size_t)
  107. static BOOST_INTRUSIVE_FORCEINLINE SizeType truncate_size_type(std::size_t n, detail::true_)
  108. {
  109. return n < std::size_t(SizeType(-1)) ? static_cast<SizeType>(n) : SizeType(-1);
  110. }
  111. template <class SizeType> // sizeof(SizeType) == sizeof(std::size_t)
  112. static BOOST_INTRUSIVE_FORCEINLINE SizeType truncate_size_type(std::size_t n, detail::false_)
  113. {
  114. return static_cast<SizeType>(n);
  115. }
  116. template <class SizeType> //sizeof(SizeType) > sizeof(std::size_t)
  117. static BOOST_INTRUSIVE_FORCEINLINE SizeType suggested_upper_bucket_count_dispatch(SizeType n, detail::true_)
  118. {
  119. std::size_t const c = n > std::size_t(-1)
  120. ? std::size_t(-1)
  121. : suggested_upper_bucket_count_impl(static_cast<std::size_t>(n));
  122. return static_cast<SizeType>(c);
  123. }
  124. template <class SizeType> //sizeof(SizeType) > sizeof(std::size_t)
  125. static BOOST_INTRUSIVE_FORCEINLINE SizeType suggested_lower_bucket_count_dispatch(SizeType n, detail::true_)
  126. {
  127. std::size_t const c = n > std::size_t(-1)
  128. ? std::size_t(-1)
  129. : suggested_lower_bucket_count_impl(static_cast<std::size_t>(n));
  130. return static_cast<SizeType>(c);
  131. }
  132. template <class SizeType>
  133. static BOOST_INTRUSIVE_FORCEINLINE SizeType suggested_upper_bucket_count_dispatch(SizeType n, detail::false_)
  134. {
  135. std::size_t const c = suggested_upper_bucket_count_impl(static_cast<std::size_t>(n));
  136. return truncate_size_type<SizeType>(c, detail::bool_<(sizeof(SizeType) < sizeof(std::size_t))>());
  137. }
  138. template <class SizeType>
  139. static BOOST_INTRUSIVE_FORCEINLINE SizeType suggested_lower_bucket_count_dispatch(SizeType n, detail::false_)
  140. {
  141. std::size_t const c = suggested_lower_bucket_count_impl(static_cast<std::size_t>(n));
  142. return truncate_size_type<SizeType>(c, detail::bool_<(sizeof(SizeType) < sizeof(std::size_t))>());
  143. }
  144. static const std::size_t prime_list[];
  145. static const std::size_t prime_list_size;
  146. static std::size_t suggested_lower_bucket_count_impl(std::size_t n)
  147. {
  148. const std::size_t *primes = &prime_list_holder<0>::prime_list[0];
  149. const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size;
  150. std::size_t const* bound = std::lower_bound(primes, primes_end, n);
  151. //Tables have upper SIZE_MAX, so we must always found an entry
  152. BOOST_INTRUSIVE_INVARIANT_ASSERT(bound != primes_end);
  153. bound -= std::size_t(bound != primes);
  154. return *bound;
  155. }
  156. static std::size_t suggested_upper_bucket_count_impl(std::size_t n)
  157. {
  158. const std::size_t *primes = &prime_list_holder<0>::prime_list[0];
  159. const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size;
  160. std::size_t const* bound = std::upper_bound(primes, primes_end, n);
  161. bound -= std::size_t(bound == primes_end);
  162. return *bound;
  163. }
  164. public:
  165. template <class SizeType>
  166. static BOOST_INTRUSIVE_FORCEINLINE SizeType suggested_upper_bucket_count(SizeType n)
  167. {
  168. return (suggested_upper_bucket_count_dispatch)(n, detail::bool_<(sizeof(SizeType) > sizeof(std::size_t))>());
  169. }
  170. template <class SizeType>
  171. static BOOST_INTRUSIVE_FORCEINLINE SizeType suggested_lower_bucket_count(SizeType n)
  172. {
  173. return (suggested_lower_bucket_count_dispatch)(n, detail::bool_<(sizeof(SizeType) > sizeof(std::size_t))>());
  174. }
  175. };
  176. #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  177. //We only support LLP64(Win64) or LP64(most Unix) data models
  178. #ifdef _WIN64 //In 64 bit windows sizeof(size_t) == sizeof(unsigned long long)
  179. #define BOOST_INTRUSIVE_PRIME_C(NUMBER) NUMBER##ULL
  180. #define BOOST_INTRUSIVE_64_BIT_SIZE_T 1
  181. #else //In 32 bit windows and 32/64 bit unixes sizeof(size_t) == sizeof(unsigned long)
  182. #define BOOST_INTRUSIVE_PRIME_C(NUMBER) NUMBER##UL
  183. #define BOOST_INTRUSIVE_64_BIT_SIZE_T (((((ULONG_MAX>>16)>>16)>>16)>>15) != 0)
  184. #endif
  185. template<int Dummy>
  186. const std::size_t prime_list_holder<Dummy>::prime_list[] = {
  187. BOOST_INTRUSIVE_PRIME_C(3), BOOST_INTRUSIVE_PRIME_C(7),
  188. BOOST_INTRUSIVE_PRIME_C(11), BOOST_INTRUSIVE_PRIME_C(17),
  189. BOOST_INTRUSIVE_PRIME_C(29), BOOST_INTRUSIVE_PRIME_C(53),
  190. BOOST_INTRUSIVE_PRIME_C(97), BOOST_INTRUSIVE_PRIME_C(193),
  191. BOOST_INTRUSIVE_PRIME_C(389), BOOST_INTRUSIVE_PRIME_C(769),
  192. BOOST_INTRUSIVE_PRIME_C(1543), BOOST_INTRUSIVE_PRIME_C(3079),
  193. BOOST_INTRUSIVE_PRIME_C(6151), BOOST_INTRUSIVE_PRIME_C(12289),
  194. BOOST_INTRUSIVE_PRIME_C(24593), BOOST_INTRUSIVE_PRIME_C(49157),
  195. BOOST_INTRUSIVE_PRIME_C(98317), BOOST_INTRUSIVE_PRIME_C(196613),
  196. BOOST_INTRUSIVE_PRIME_C(393241), BOOST_INTRUSIVE_PRIME_C(786433),
  197. BOOST_INTRUSIVE_PRIME_C(1572869), BOOST_INTRUSIVE_PRIME_C(3145739),
  198. BOOST_INTRUSIVE_PRIME_C(6291469), BOOST_INTRUSIVE_PRIME_C(12582917),
  199. BOOST_INTRUSIVE_PRIME_C(25165843), BOOST_INTRUSIVE_PRIME_C(50331653),
  200. BOOST_INTRUSIVE_PRIME_C(100663319), BOOST_INTRUSIVE_PRIME_C(201326611),
  201. BOOST_INTRUSIVE_PRIME_C(402653189), BOOST_INTRUSIVE_PRIME_C(805306457),
  202. BOOST_INTRUSIVE_PRIME_C(1610612741), BOOST_INTRUSIVE_PRIME_C(3221225473),
  203. #if BOOST_INTRUSIVE_64_BIT_SIZE_T
  204. //Taken from Boost.MultiIndex code, thanks to Joaquin M Lopez Munoz.
  205. BOOST_INTRUSIVE_PRIME_C(6442450939), BOOST_INTRUSIVE_PRIME_C(12884901893),
  206. BOOST_INTRUSIVE_PRIME_C(25769803751), BOOST_INTRUSIVE_PRIME_C(51539607551),
  207. BOOST_INTRUSIVE_PRIME_C(103079215111), BOOST_INTRUSIVE_PRIME_C(206158430209),
  208. BOOST_INTRUSIVE_PRIME_C(412316860441), BOOST_INTRUSIVE_PRIME_C(824633720831),
  209. BOOST_INTRUSIVE_PRIME_C(1649267441651), BOOST_INTRUSIVE_PRIME_C(3298534883309),
  210. BOOST_INTRUSIVE_PRIME_C(6597069766657), BOOST_INTRUSIVE_PRIME_C(13194139533299),
  211. BOOST_INTRUSIVE_PRIME_C(26388279066623), BOOST_INTRUSIVE_PRIME_C(52776558133303),
  212. BOOST_INTRUSIVE_PRIME_C(105553116266489), BOOST_INTRUSIVE_PRIME_C(211106232532969),
  213. BOOST_INTRUSIVE_PRIME_C(422212465066001), BOOST_INTRUSIVE_PRIME_C(844424930131963),
  214. BOOST_INTRUSIVE_PRIME_C(1688849860263953), BOOST_INTRUSIVE_PRIME_C(3377699720527861),
  215. BOOST_INTRUSIVE_PRIME_C(6755399441055731), BOOST_INTRUSIVE_PRIME_C(13510798882111483),
  216. BOOST_INTRUSIVE_PRIME_C(27021597764222939), BOOST_INTRUSIVE_PRIME_C(54043195528445957),
  217. BOOST_INTRUSIVE_PRIME_C(108086391056891903), BOOST_INTRUSIVE_PRIME_C(216172782113783843),
  218. BOOST_INTRUSIVE_PRIME_C(432345564227567621), BOOST_INTRUSIVE_PRIME_C(864691128455135207),
  219. BOOST_INTRUSIVE_PRIME_C(1729382256910270481), BOOST_INTRUSIVE_PRIME_C(3458764513820540933),
  220. BOOST_INTRUSIVE_PRIME_C(6917529027641081903), BOOST_INTRUSIVE_PRIME_C(13835058055282163729),
  221. BOOST_INTRUSIVE_PRIME_C(18446744073709551557), BOOST_INTRUSIVE_PRIME_C(18446744073709551615) //Upper limit, just in case
  222. #else
  223. BOOST_INTRUSIVE_PRIME_C(4294967291), BOOST_INTRUSIVE_PRIME_C(4294967295) //Upper limit, just in case
  224. #endif
  225. };
  226. #undef BOOST_INTRUSIVE_PRIME_C
  227. #undef BOOST_INTRUSIVE_64_BIT_SIZE_T
  228. #endif //#if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  229. template<int Dummy>
  230. const std::size_t prime_list_holder<Dummy>::prime_list_size
  231. = sizeof(prime_list)/sizeof(std::size_t);
  232. struct hash_bool_flags
  233. {
  234. static const std::size_t unique_keys_pos = 1u;
  235. static const std::size_t constant_time_size_pos = 2u;
  236. static const std::size_t power_2_buckets_pos = 4u;
  237. static const std::size_t cache_begin_pos = 8u;
  238. static const std::size_t compare_hash_pos = 16u;
  239. static const std::size_t incremental_pos = 32u;
  240. };
  241. namespace detail {
  242. template<class SupposedValueTraits>
  243. struct get_slist_impl_from_supposed_value_traits
  244. {
  245. typedef SupposedValueTraits value_traits;
  246. typedef typename detail::get_node_traits
  247. <value_traits>::type node_traits;
  248. typedef typename get_slist_impl
  249. <typename reduced_slist_node_traits
  250. <node_traits>::type
  251. >::type type;
  252. };
  253. template<class SupposedValueTraits>
  254. struct unordered_bucket_impl
  255. {
  256. typedef typename
  257. get_slist_impl_from_supposed_value_traits
  258. <SupposedValueTraits>::type slist_impl;
  259. typedef bucket_impl<slist_impl> implementation_defined;
  260. typedef implementation_defined type;
  261. };
  262. template<class SupposedValueTraits>
  263. struct unordered_bucket_ptr_impl
  264. {
  265. typedef typename detail::get_node_traits
  266. <SupposedValueTraits>::type::node_ptr node_ptr;
  267. typedef typename unordered_bucket_impl
  268. <SupposedValueTraits>::type bucket_type;
  269. typedef typename pointer_traits
  270. <node_ptr>::template rebind_pointer
  271. < bucket_type >::type implementation_defined;
  272. typedef implementation_defined type;
  273. };
  274. template <class T>
  275. struct store_hash_is_true
  276. {
  277. template<bool Add>
  278. struct two_or_three {yes_type _[2 + Add];};
  279. template <class U> static yes_type test(...);
  280. template <class U> static two_or_three<U::store_hash> test (int);
  281. static const bool value = sizeof(test<T>(0)) > sizeof(yes_type)*2;
  282. };
  283. template <class T>
  284. struct optimize_multikey_is_true
  285. {
  286. template<bool Add>
  287. struct two_or_three {yes_type _[2 + Add];};
  288. template <class U> static yes_type test(...);
  289. template <class U> static two_or_three<U::optimize_multikey> test (int);
  290. static const bool value = sizeof(test<T>(0)) > sizeof(yes_type)*2;
  291. };
  292. struct insert_commit_data_impl
  293. {
  294. std::size_t hash;
  295. };
  296. template<class Node, class SlistNodePtr>
  297. BOOST_INTRUSIVE_FORCEINLINE typename pointer_traits<SlistNodePtr>::template rebind_pointer<Node>::type
  298. dcast_bucket_ptr(const SlistNodePtr &p)
  299. {
  300. typedef typename pointer_traits<SlistNodePtr>::template rebind_pointer<Node>::type node_ptr;
  301. return pointer_traits<node_ptr>::pointer_to(static_cast<Node&>(*p));
  302. }
  303. template<class NodeTraits>
  304. struct group_functions
  305. {
  306. // A group is reverse-linked
  307. //
  308. // A is "first in group"
  309. // C is "last in group"
  310. // __________________
  311. // | _____ _____ |
  312. // | | | | | | <- Group links
  313. // ^ V ^ V ^ V
  314. // _ _ _ _
  315. // A|_| B|_| C|_| D|_|
  316. //
  317. // ^ | ^ | ^ | ^ V <- Bucket links
  318. // _ _____| |_____| |______| |____| |
  319. // |B| |
  320. // ^________________________________|
  321. //
  322. typedef NodeTraits node_traits;
  323. typedef unordered_group_adapter<node_traits> group_traits;
  324. typedef typename node_traits::node_ptr node_ptr;
  325. typedef typename node_traits::node node;
  326. typedef typename reduced_slist_node_traits
  327. <node_traits>::type reduced_node_traits;
  328. typedef typename reduced_node_traits::node_ptr slist_node_ptr;
  329. typedef typename reduced_node_traits::node slist_node;
  330. typedef circular_slist_algorithms<group_traits> group_algorithms;
  331. typedef circular_slist_algorithms<node_traits> node_algorithms;
  332. static slist_node_ptr get_bucket_before_begin
  333. (slist_node_ptr bucket_beg, slist_node_ptr bucket_end, node_ptr p)
  334. {
  335. //First find the last node of p's group.
  336. //This requires checking the first node of the next group or
  337. //the bucket node.
  338. node_ptr prev_node = p;
  339. node_ptr nxt(node_traits::get_next(p));
  340. while(!(bucket_beg <= nxt && nxt <= bucket_end) &&
  341. (group_traits::get_next(nxt) == prev_node)){
  342. prev_node = nxt;
  343. nxt = node_traits::get_next(nxt);
  344. }
  345. //If we've reached the bucket node just return it.
  346. if(bucket_beg <= nxt && nxt <= bucket_end){
  347. return nxt;
  348. }
  349. //Otherwise, iterate using group links until the bucket node
  350. node_ptr first_node_of_group = nxt;
  351. node_ptr last_node_group = group_traits::get_next(first_node_of_group);
  352. slist_node_ptr possible_end = node_traits::get_next(last_node_group);
  353. while(!(bucket_beg <= possible_end && possible_end <= bucket_end)){
  354. first_node_of_group = detail::dcast_bucket_ptr<node>(possible_end);
  355. last_node_group = group_traits::get_next(first_node_of_group);
  356. possible_end = node_traits::get_next(last_node_group);
  357. }
  358. return possible_end;
  359. }
  360. static node_ptr get_prev_to_first_in_group(slist_node_ptr bucket_node, node_ptr first_in_group)
  361. {
  362. node_ptr nb = detail::dcast_bucket_ptr<node>(bucket_node);
  363. node_ptr n;
  364. while((n = node_traits::get_next(nb)) != first_in_group){
  365. nb = group_traits::get_next(n); //go to last in group
  366. }
  367. return nb;
  368. }
  369. static void erase_from_group(slist_node_ptr end_ptr, node_ptr to_erase_ptr, detail::true_)
  370. {
  371. node_ptr const nxt_ptr(node_traits::get_next(to_erase_ptr));
  372. //Check if the next node is in the group (not end node) and reverse linked to
  373. //'to_erase_ptr'. Erase if that's the case.
  374. if(nxt_ptr != end_ptr && to_erase_ptr == group_traits::get_next(nxt_ptr)){
  375. group_algorithms::unlink_after(nxt_ptr);
  376. }
  377. }
  378. BOOST_INTRUSIVE_FORCEINLINE static void erase_from_group(const slist_node_ptr&, const node_ptr&, detail::false_)
  379. {}
  380. BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_last_in_group(node_ptr first_in_group, detail::true_)
  381. { return group_traits::get_next(first_in_group); }
  382. BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_last_in_group(node_ptr n, detail::false_)
  383. { return n; }
  384. static node_ptr get_first_in_group(node_ptr n, detail::true_)
  385. {
  386. node_ptr ng;
  387. while(n == node_traits::get_next((ng = group_traits::get_next(n)))){
  388. n = ng;
  389. }
  390. return n;
  391. }
  392. BOOST_INTRUSIVE_FORCEINLINE static node_ptr next_group_if_first_in_group(node_ptr ptr)
  393. {
  394. return node_traits::get_next(group_traits::get_next(ptr));
  395. }
  396. BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_first_in_group(node_ptr n, detail::false_)
  397. { return n; }
  398. BOOST_INTRUSIVE_FORCEINLINE static void insert_in_group(node_ptr first_in_group, node_ptr n, true_)
  399. { group_algorithms::link_after(first_in_group, n); }
  400. static void insert_in_group(const node_ptr&, const node_ptr&, false_)
  401. {}
  402. BOOST_INTRUSIVE_FORCEINLINE static node_ptr split_group(node_ptr const new_first_in_group)
  403. {
  404. node_ptr const first((get_first_in_group)(new_first_in_group, detail::true_()));
  405. if(first != new_first_in_group){
  406. node_ptr const last = group_traits::get_next(first);
  407. group_traits::set_next(first, group_traits::get_next(new_first_in_group));
  408. group_traits::set_next(new_first_in_group, last);
  409. }
  410. return first;
  411. }
  412. };
  413. template<class BucketType, class SplitTraits>
  414. class incremental_rehash_rollback
  415. {
  416. private:
  417. typedef BucketType bucket_type;
  418. typedef SplitTraits split_traits;
  419. incremental_rehash_rollback();
  420. incremental_rehash_rollback & operator=(const incremental_rehash_rollback &);
  421. incremental_rehash_rollback (const incremental_rehash_rollback &);
  422. public:
  423. incremental_rehash_rollback
  424. (bucket_type &source_bucket, bucket_type &destiny_bucket, split_traits &split_traits)
  425. : source_bucket_(source_bucket), destiny_bucket_(destiny_bucket)
  426. , split_traits_(split_traits), released_(false)
  427. {}
  428. BOOST_INTRUSIVE_FORCEINLINE void release()
  429. { released_ = true; }
  430. ~incremental_rehash_rollback()
  431. {
  432. if(!released_){
  433. //If an exception is thrown, just put all moved nodes back in the old bucket
  434. //and move back the split mark.
  435. destiny_bucket_.splice_after(destiny_bucket_.before_begin(), source_bucket_);
  436. split_traits_.decrement();
  437. }
  438. }
  439. private:
  440. bucket_type &source_bucket_;
  441. bucket_type &destiny_bucket_;
  442. split_traits &split_traits_;
  443. bool released_;
  444. };
  445. template<class NodeTraits>
  446. struct node_functions
  447. {
  448. BOOST_INTRUSIVE_FORCEINLINE static void store_hash(typename NodeTraits::node_ptr p, std::size_t h, true_)
  449. { return NodeTraits::set_hash(p, h); }
  450. BOOST_INTRUSIVE_FORCEINLINE static void store_hash(typename NodeTraits::node_ptr, std::size_t, false_)
  451. {}
  452. };
  453. BOOST_INTRUSIVE_FORCEINLINE std::size_t hash_to_bucket(std::size_t hash_value, std::size_t bucket_cnt, detail::false_)
  454. { return hash_value % bucket_cnt; }
  455. BOOST_INTRUSIVE_FORCEINLINE std::size_t hash_to_bucket(std::size_t hash_value, std::size_t bucket_cnt, detail::true_)
  456. { return hash_value & (bucket_cnt - 1); }
  457. template<bool Power2Buckets, bool Incremental>
  458. BOOST_INTRUSIVE_FORCEINLINE std::size_t hash_to_bucket_split(std::size_t hash_value, std::size_t bucket_cnt, std::size_t split)
  459. {
  460. std::size_t bucket_number = detail::hash_to_bucket(hash_value, bucket_cnt, detail::bool_<Power2Buckets>());
  461. if(Incremental)
  462. bucket_number -= static_cast<std::size_t>(bucket_number >= split)*(bucket_cnt/2);
  463. return bucket_number;
  464. }
  465. } //namespace detail {
  466. //!This metafunction will obtain the type of a bucket
  467. //!from the value_traits or hook option to be used with
  468. //!a hash container.
  469. template<class ValueTraitsOrHookOption>
  470. struct unordered_bucket
  471. : public detail::unordered_bucket_impl
  472. <typename ValueTraitsOrHookOption::
  473. template pack<empty>::proto_value_traits
  474. >
  475. {};
  476. //!This metafunction will obtain the type of a bucket pointer
  477. //!from the value_traits or hook option to be used with
  478. //!a hash container.
  479. template<class ValueTraitsOrHookOption>
  480. struct unordered_bucket_ptr
  481. : public detail::unordered_bucket_ptr_impl
  482. <typename ValueTraitsOrHookOption::
  483. template pack<empty>::proto_value_traits
  484. >
  485. {};
  486. //!This metafunction will obtain the type of the default bucket traits
  487. //!(when the user does not specify the bucket_traits<> option) from the
  488. //!value_traits or hook option to be used with
  489. //!a hash container.
  490. template<class ValueTraitsOrHookOption>
  491. struct unordered_default_bucket_traits
  492. {
  493. typedef typename ValueTraitsOrHookOption::
  494. template pack<empty>::proto_value_traits supposed_value_traits;
  495. typedef typename detail::
  496. get_slist_impl_from_supposed_value_traits
  497. <supposed_value_traits>::type slist_impl;
  498. typedef bucket_traits_impl
  499. <slist_impl> implementation_defined;
  500. typedef implementation_defined type;
  501. };
  502. struct default_bucket_traits;
  503. //hashtable default hook traits
  504. struct default_hashtable_hook_applier
  505. { template <class T> struct apply{ typedef typename T::default_hashtable_hook type; }; };
  506. template<>
  507. struct is_default_hook_tag<default_hashtable_hook_applier>
  508. { static const bool value = true; };
  509. struct hashtable_defaults
  510. {
  511. typedef default_hashtable_hook_applier proto_value_traits;
  512. typedef std::size_t size_type;
  513. typedef void key_of_value;
  514. typedef void equal;
  515. typedef void hash;
  516. typedef default_bucket_traits bucket_traits;
  517. static const bool constant_time_size = true;
  518. static const bool power_2_buckets = false;
  519. static const bool cache_begin = false;
  520. static const bool compare_hash = false;
  521. static const bool incremental = false;
  522. };
  523. template<class ValueTraits, bool IsConst>
  524. struct downcast_node_to_value_t
  525. : public detail::node_to_value<ValueTraits, IsConst>
  526. {
  527. typedef detail::node_to_value<ValueTraits, IsConst> base_t;
  528. typedef typename base_t::result_type result_type;
  529. typedef ValueTraits value_traits;
  530. typedef typename get_slist_impl
  531. <typename reduced_slist_node_traits
  532. <typename value_traits::node_traits>::type
  533. >::type slist_impl;
  534. typedef typename detail::add_const_if_c
  535. <typename slist_impl::node, IsConst>::type & first_argument_type;
  536. typedef typename detail::add_const_if_c
  537. < typename ValueTraits::node_traits::node
  538. , IsConst>::type & intermediate_argument_type;
  539. typedef typename pointer_traits
  540. <typename ValueTraits::pointer>::
  541. template rebind_pointer
  542. <const ValueTraits>::type const_value_traits_ptr;
  543. BOOST_INTRUSIVE_FORCEINLINE downcast_node_to_value_t(const const_value_traits_ptr &ptr)
  544. : base_t(ptr)
  545. {}
  546. BOOST_INTRUSIVE_FORCEINLINE result_type operator()(first_argument_type arg) const
  547. { return this->base_t::operator()(static_cast<intermediate_argument_type>(arg)); }
  548. };
  549. template<class F, class SlistNodePtr, class NodePtr>
  550. struct node_cast_adaptor
  551. //Use public inheritance to avoid MSVC bugs with closures
  552. : public detail::ebo_functor_holder<F>
  553. {
  554. typedef detail::ebo_functor_holder<F> base_t;
  555. typedef typename pointer_traits<SlistNodePtr>::element_type slist_node;
  556. typedef typename pointer_traits<NodePtr>::element_type node;
  557. template<class ConvertibleToF, class RealValuTraits>
  558. BOOST_INTRUSIVE_FORCEINLINE node_cast_adaptor(const ConvertibleToF &c2f, const RealValuTraits *traits)
  559. : base_t(base_t(c2f, traits))
  560. {}
  561. BOOST_INTRUSIVE_FORCEINLINE typename base_t::node_ptr operator()(const slist_node &to_clone)
  562. { return base_t::operator()(static_cast<const node &>(to_clone)); }
  563. BOOST_INTRUSIVE_FORCEINLINE void operator()(SlistNodePtr to_clone)
  564. {
  565. base_t::operator()(pointer_traits<NodePtr>::pointer_to(static_cast<node &>(*to_clone)));
  566. }
  567. };
  568. //bucket_plus_vtraits stores ValueTraits + BucketTraits
  569. //this data is needed by iterators to obtain the
  570. //value from the iterator and detect the bucket
  571. template<class ValueTraits, class BucketTraits>
  572. struct bucket_plus_vtraits
  573. {
  574. typedef BucketTraits bucket_traits;
  575. typedef ValueTraits value_traits;
  576. static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value;
  577. typedef typename
  578. detail::get_slist_impl_from_supposed_value_traits
  579. <value_traits>::type slist_impl;
  580. typedef typename value_traits::node_traits node_traits;
  581. typedef unordered_group_adapter<node_traits> group_traits;
  582. typedef typename slist_impl::iterator siterator;
  583. typedef bucket_impl<slist_impl> bucket_type;
  584. typedef detail::group_functions<node_traits> group_functions_t;
  585. typedef typename slist_impl::node_algorithms node_algorithms;
  586. typedef typename slist_impl::node_ptr slist_node_ptr;
  587. typedef typename node_traits::node_ptr node_ptr;
  588. typedef typename node_traits::node node;
  589. typedef typename value_traits::value_type value_type;
  590. typedef typename value_traits::pointer pointer;
  591. typedef typename value_traits::const_pointer const_pointer;
  592. typedef typename pointer_traits<pointer>::reference reference;
  593. typedef typename pointer_traits
  594. <const_pointer>::reference const_reference;
  595. typedef circular_slist_algorithms<group_traits> group_algorithms;
  596. typedef typename pointer_traits
  597. <typename value_traits::pointer>::
  598. template rebind_pointer
  599. <const value_traits>::type const_value_traits_ptr;
  600. typedef typename pointer_traits
  601. <typename value_traits::pointer>::
  602. template rebind_pointer
  603. <const bucket_plus_vtraits>::type const_bucket_value_traits_ptr;
  604. typedef typename detail::unordered_bucket_ptr_impl
  605. <value_traits>::type bucket_ptr;
  606. template<class BucketTraitsType>
  607. BOOST_INTRUSIVE_FORCEINLINE bucket_plus_vtraits(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits)
  608. : data(val_traits, ::boost::forward<BucketTraitsType>(b_traits))
  609. {}
  610. BOOST_INTRUSIVE_FORCEINLINE bucket_plus_vtraits & operator =(const bucket_plus_vtraits &x)
  611. { data.bucket_traits_ = x.data.bucket_traits_; return *this; }
  612. BOOST_INTRUSIVE_FORCEINLINE const_value_traits_ptr priv_value_traits_ptr() const
  613. { return pointer_traits<const_value_traits_ptr>::pointer_to(this->priv_value_traits()); }
  614. //bucket_value_traits
  615. //
  616. BOOST_INTRUSIVE_FORCEINLINE const bucket_plus_vtraits &get_bucket_value_traits() const
  617. { return *this; }
  618. BOOST_INTRUSIVE_FORCEINLINE bucket_plus_vtraits &get_bucket_value_traits()
  619. { return *this; }
  620. BOOST_INTRUSIVE_FORCEINLINE const_bucket_value_traits_ptr bucket_value_traits_ptr() const
  621. { return pointer_traits<const_bucket_value_traits_ptr>::pointer_to(this->get_bucket_value_traits()); }
  622. //value traits
  623. //
  624. BOOST_INTRUSIVE_FORCEINLINE const value_traits &priv_value_traits() const
  625. { return this->data; }
  626. BOOST_INTRUSIVE_FORCEINLINE value_traits &priv_value_traits()
  627. { return this->data; }
  628. //bucket_traits
  629. //
  630. BOOST_INTRUSIVE_FORCEINLINE const bucket_traits &priv_bucket_traits() const
  631. { return this->data.bucket_traits_; }
  632. BOOST_INTRUSIVE_FORCEINLINE bucket_traits &priv_bucket_traits()
  633. { return this->data.bucket_traits_; }
  634. //bucket operations
  635. BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_bucket_pointer() const
  636. { return this->priv_bucket_traits().bucket_begin(); }
  637. std::size_t priv_bucket_count() const
  638. { return this->priv_bucket_traits().bucket_count(); }
  639. BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_invalid_bucket() const
  640. {
  641. const bucket_traits &rbt = this->priv_bucket_traits();
  642. return rbt.bucket_begin() + rbt.bucket_count();
  643. }
  644. BOOST_INTRUSIVE_FORCEINLINE siterator priv_invalid_local_it() const
  645. { return this->priv_bucket_traits().bucket_begin()->before_begin(); }
  646. template<class NodeDisposer>
  647. static std::size_t priv_erase_from_single_bucket(bucket_type &b, siterator sbefore_first, siterator slast, NodeDisposer node_disposer, detail::true_) //optimize multikey
  648. {
  649. std::size_t n = 0;
  650. siterator const sfirst(++siterator(sbefore_first));
  651. if(sfirst != slast){
  652. node_ptr const nf = detail::dcast_bucket_ptr<node>(sfirst.pointed_node());
  653. node_ptr const nl = detail::dcast_bucket_ptr<node>(slast.pointed_node());
  654. node_ptr const ne = detail::dcast_bucket_ptr<node>(b.end().pointed_node());
  655. if(group_functions_t::next_group_if_first_in_group(nf) != nf) {
  656. // The node is at the beginning of a group.
  657. if(nl != ne){
  658. group_functions_t::split_group(nl);
  659. }
  660. }
  661. else {
  662. node_ptr const group1 = group_functions_t::split_group(nf);
  663. if(nl != ne) {
  664. node_ptr const group2 = group_functions_t::split_group(ne);
  665. if(nf == group2) { //Both first and last in the same group
  666. //so join group1 and group2
  667. node_ptr const end1 = group_traits::get_next(group1);
  668. node_ptr const end2 = group_traits::get_next(group2);
  669. group_traits::set_next(group1, end2);
  670. group_traits::set_next(group2, end1);
  671. }
  672. }
  673. }
  674. siterator it(++siterator(sbefore_first));
  675. while(it != slast){
  676. node_disposer((it++).pointed_node());
  677. ++n;
  678. }
  679. b.erase_after(sbefore_first, slast);
  680. }
  681. return n;
  682. }
  683. template<class NodeDisposer>
  684. static std::size_t priv_erase_from_single_bucket(bucket_type &b, siterator sbefore_first, siterator slast, NodeDisposer node_disposer, detail::false_) //optimize multikey
  685. {
  686. std::size_t n = 0;
  687. siterator it(++siterator(sbefore_first));
  688. while(it != slast){
  689. node_disposer((it++).pointed_node());
  690. ++n;
  691. }
  692. b.erase_after(sbefore_first, slast);
  693. return n;
  694. }
  695. template<class NodeDisposer>
  696. static void priv_erase_node(bucket_type &b, siterator i, NodeDisposer node_disposer, detail::true_) //optimize multikey
  697. {
  698. node_ptr const ne(detail::dcast_bucket_ptr<node>(b.end().pointed_node()));
  699. node_ptr n(detail::dcast_bucket_ptr<node>(i.pointed_node()));
  700. node_ptr pos = node_traits::get_next(group_traits::get_next(n));
  701. node_ptr bn;
  702. node_ptr nn(node_traits::get_next(n));
  703. if(pos != n) {
  704. //Node is the first of the group
  705. bn = group_functions_t::get_prev_to_first_in_group(ne, n);
  706. //Unlink the rest of the group if it's not the last node of its group
  707. if(nn != ne && group_traits::get_next(nn) == n){
  708. group_algorithms::unlink_after(nn);
  709. }
  710. }
  711. else if(nn != ne && group_traits::get_next(nn) == n){
  712. //Node is not the end of the group
  713. bn = group_traits::get_next(n);
  714. group_algorithms::unlink_after(nn);
  715. }
  716. else{
  717. //Node is the end of the group
  718. bn = group_traits::get_next(n);
  719. node_ptr const x(group_algorithms::get_previous_node(n));
  720. group_algorithms::unlink_after(x);
  721. }
  722. b.erase_after_and_dispose(bucket_type::s_iterator_to(*bn), node_disposer);
  723. }
  724. template<class NodeDisposer>
  725. BOOST_INTRUSIVE_FORCEINLINE static void priv_erase_node(bucket_type &b, siterator i, NodeDisposer node_disposer, detail::false_) //optimize multikey
  726. { b.erase_after_and_dispose(b.previous(i), node_disposer); }
  727. template<class NodeDisposer, bool OptimizeMultikey>
  728. std::size_t priv_erase_node_range( siterator const &before_first_it, std::size_t const first_bucket
  729. , siterator const &last_it, std::size_t const last_bucket
  730. , NodeDisposer node_disposer, detail::bool_<OptimizeMultikey> optimize_multikey_tag)
  731. {
  732. std::size_t num_erased(0);
  733. siterator last_step_before_it;
  734. if(first_bucket != last_bucket){
  735. bucket_type *b = (&this->priv_bucket_pointer()[0]);
  736. num_erased += this->priv_erase_from_single_bucket
  737. (b[first_bucket], before_first_it, b[first_bucket].end(), node_disposer, optimize_multikey_tag);
  738. for(std::size_t i = 0, n = (last_bucket - first_bucket - 1); i != n; ++i){
  739. num_erased += this->priv_erase_whole_bucket(b[first_bucket+i+1], node_disposer);
  740. }
  741. last_step_before_it = b[last_bucket].before_begin();
  742. }
  743. else{
  744. last_step_before_it = before_first_it;
  745. }
  746. num_erased += this->priv_erase_from_single_bucket
  747. (this->priv_bucket_pointer()[last_bucket], last_step_before_it, last_it, node_disposer, optimize_multikey_tag);
  748. return num_erased;
  749. }
  750. static siterator priv_get_last(bucket_type &b, detail::true_) //optimize multikey
  751. {
  752. //First find the last node of p's group.
  753. //This requires checking the first node of the next group or
  754. //the bucket node.
  755. slist_node_ptr end_ptr(b.end().pointed_node());
  756. node_ptr possible_end(node_traits::get_next( detail::dcast_bucket_ptr<node>(end_ptr)));
  757. node_ptr last_node_group(possible_end);
  758. while(end_ptr != possible_end){
  759. last_node_group = group_traits::get_next(detail::dcast_bucket_ptr<node>(possible_end));
  760. possible_end = node_traits::get_next(last_node_group);
  761. }
  762. return bucket_type::s_iterator_to(*last_node_group);
  763. }
  764. template<class NodeDisposer>
  765. std::size_t priv_erase_whole_bucket(bucket_type &b, NodeDisposer node_disposer)
  766. {
  767. std::size_t num_erased = 0;
  768. siterator b_begin(b.before_begin());
  769. siterator nxt(b_begin);
  770. ++nxt;
  771. siterator const end_sit(b.end());
  772. while(nxt != end_sit){
  773. //No need to init group links as we'll delete all bucket nodes
  774. nxt = bucket_type::s_erase_after_and_dispose(b_begin, node_disposer);
  775. ++num_erased;
  776. }
  777. return num_erased;
  778. }
  779. BOOST_INTRUSIVE_FORCEINLINE static siterator priv_get_last(bucket_type &b, detail::false_) //NOT optimize multikey
  780. { return b.previous(b.end()); }
  781. static siterator priv_get_previous(bucket_type &b, siterator i, detail::true_) //optimize multikey
  782. {
  783. node_ptr const elem(detail::dcast_bucket_ptr<node>(i.pointed_node()));
  784. node_ptr const prev_in_group(group_traits::get_next(elem));
  785. bool const first_in_group = node_traits::get_next(prev_in_group) != elem;
  786. typename bucket_type::node &n = first_in_group
  787. ? *group_functions_t::get_prev_to_first_in_group(b.end().pointed_node(), elem)
  788. : *group_traits::get_next(elem)
  789. ;
  790. return bucket_type::s_iterator_to(n);
  791. }
  792. BOOST_INTRUSIVE_FORCEINLINE static siterator priv_get_previous(bucket_type &b, siterator i, detail::false_) //NOT optimize multikey
  793. { return b.previous(i); }
  794. std::size_t priv_get_bucket_num_no_hash_store(siterator it, detail::true_) //optimize multikey
  795. {
  796. const bucket_ptr f(this->priv_bucket_pointer()), l(f + this->priv_bucket_count() - 1);
  797. slist_node_ptr bb = group_functions_t::get_bucket_before_begin
  798. ( f->end().pointed_node()
  799. , l->end().pointed_node()
  800. , detail::dcast_bucket_ptr<node>(it.pointed_node()));
  801. //Now get the bucket_impl from the iterator
  802. const bucket_type &b = static_cast<const bucket_type&>
  803. (bucket_type::slist_type::container_from_end_iterator(bucket_type::s_iterator_to(*bb)));
  804. //Now just calculate the index b has in the bucket array
  805. return static_cast<std::size_t>(&b - &*f);
  806. }
  807. std::size_t priv_get_bucket_num_no_hash_store(siterator it, detail::false_) //NO optimize multikey
  808. {
  809. bucket_ptr f(this->priv_bucket_pointer()), l(f + this->priv_bucket_count() - 1);
  810. slist_node_ptr first_ptr(f->cend().pointed_node())
  811. , last_ptr(l->cend().pointed_node());
  812. //The end node is embedded in the singly linked list:
  813. //iterate until we reach it.
  814. while(!(first_ptr <= it.pointed_node() && it.pointed_node() <= last_ptr)){
  815. ++it;
  816. }
  817. //Now get the bucket_impl from the iterator
  818. const bucket_type &b = static_cast<const bucket_type&>
  819. (bucket_type::container_from_end_iterator(it));
  820. //Now just calculate the index b has in the bucket array
  821. return static_cast<std::size_t>(&b - &*f);
  822. }
  823. BOOST_INTRUSIVE_FORCEINLINE static std::size_t priv_stored_hash(slist_node_ptr n, detail::true_) //store_hash
  824. { return node_traits::get_hash(detail::dcast_bucket_ptr<node>(n)); }
  825. BOOST_INTRUSIVE_FORCEINLINE static std::size_t priv_stored_hash(slist_node_ptr, detail::false_) //NO store_hash
  826. { return std::size_t(-1); }
  827. BOOST_INTRUSIVE_FORCEINLINE node &priv_value_to_node(reference v)
  828. { return *this->priv_value_traits().to_node_ptr(v); }
  829. BOOST_INTRUSIVE_FORCEINLINE const node &priv_value_to_node(const_reference v) const
  830. { return *this->priv_value_traits().to_node_ptr(v); }
  831. BOOST_INTRUSIVE_FORCEINLINE reference priv_value_from_slist_node(slist_node_ptr n)
  832. { return *this->priv_value_traits().to_value_ptr(detail::dcast_bucket_ptr<node>(n)); }
  833. BOOST_INTRUSIVE_FORCEINLINE const_reference priv_value_from_slist_node(slist_node_ptr n) const
  834. { return *this->priv_value_traits().to_value_ptr(detail::dcast_bucket_ptr<node>(n)); }
  835. void priv_clear_buckets(const bucket_ptr buckets_ptr, const std::size_t bucket_cnt)
  836. {
  837. bucket_ptr buckets_it = buckets_ptr;
  838. for(std::size_t bucket_i = 0; bucket_i != bucket_cnt; ++buckets_it, ++bucket_i){
  839. if(safemode_or_autounlink){
  840. buckets_it->clear_and_dispose(detail::init_disposer<node_algorithms>());
  841. }
  842. else{
  843. buckets_it->clear();
  844. }
  845. }
  846. }
  847. BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_stored_or_compute_hash(const value_type &v, detail::true_) const //For store_hash == true
  848. { return node_traits::get_hash(this->priv_value_traits().to_node_ptr(v)); }
  849. typedef hashtable_iterator<bucket_plus_vtraits, false> iterator;
  850. typedef hashtable_iterator<bucket_plus_vtraits, true> const_iterator;
  851. BOOST_INTRUSIVE_FORCEINLINE iterator end()
  852. { return iterator(this->priv_invalid_local_it(), 0); }
  853. BOOST_INTRUSIVE_FORCEINLINE const_iterator end() const
  854. { return this->cend(); }
  855. BOOST_INTRUSIVE_FORCEINLINE const_iterator cend() const
  856. { return const_iterator(this->priv_invalid_local_it(), 0); }
  857. //Public functions:
  858. struct data_type : public ValueTraits
  859. {
  860. template<class BucketTraitsType>
  861. BOOST_INTRUSIVE_FORCEINLINE data_type(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits)
  862. : ValueTraits(val_traits), bucket_traits_(::boost::forward<BucketTraitsType>(b_traits))
  863. {}
  864. bucket_traits bucket_traits_;
  865. } data;
  866. };
  867. template<class Hash, class>
  868. struct get_hash
  869. {
  870. typedef Hash type;
  871. };
  872. template<class T>
  873. struct get_hash<void, T>
  874. {
  875. typedef ::boost::hash<T> type;
  876. };
  877. template<class EqualTo, class>
  878. struct get_equal_to
  879. {
  880. typedef EqualTo type;
  881. };
  882. template<class T>
  883. struct get_equal_to<void, T>
  884. {
  885. typedef std::equal_to<T> type;
  886. };
  887. template<class KeyOfValue, class T>
  888. struct get_hash_key_of_value
  889. {
  890. typedef KeyOfValue type;
  891. };
  892. template<class T>
  893. struct get_hash_key_of_value<void, T>
  894. {
  895. typedef ::boost::intrusive::detail::identity<T> type;
  896. };
  897. template<class T, class VoidOrKeyOfValue>
  898. struct hash_key_types_base
  899. {
  900. typedef typename get_hash_key_of_value
  901. < VoidOrKeyOfValue, T>::type key_of_value;
  902. typedef typename key_of_value::type key_type;
  903. };
  904. template<class T, class VoidOrKeyOfValue, class VoidOrKeyHash>
  905. struct hash_key_hash
  906. : get_hash
  907. < VoidOrKeyHash
  908. , typename hash_key_types_base<T, VoidOrKeyOfValue>::key_type
  909. >
  910. {};
  911. template<class T, class VoidOrKeyOfValue, class VoidOrKeyEqual>
  912. struct hash_key_equal
  913. : get_equal_to
  914. < VoidOrKeyEqual
  915. , typename hash_key_types_base<T, VoidOrKeyOfValue>::key_type
  916. >
  917. {};
  918. //bucket_hash_t
  919. //Stores bucket_plus_vtraits plust the hash function
  920. template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class BucketTraits>
  921. struct bucket_hash_t
  922. //Use public inheritance to avoid MSVC bugs with closures
  923. : public detail::ebo_functor_holder
  924. <typename hash_key_hash < typename bucket_plus_vtraits<ValueTraits,BucketTraits>::value_traits::value_type
  925. , VoidOrKeyOfValue
  926. , VoidOrKeyHash
  927. >::type
  928. >
  929. , bucket_plus_vtraits<ValueTraits, BucketTraits> //4
  930. {
  931. typedef typename bucket_plus_vtraits<ValueTraits,BucketTraits>::value_traits value_traits;
  932. typedef typename value_traits::value_type value_type;
  933. typedef typename value_traits::node_traits node_traits;
  934. typedef hash_key_hash
  935. < value_type, VoidOrKeyOfValue, VoidOrKeyHash> hash_key_hash_t;
  936. typedef typename hash_key_hash_t::type hasher;
  937. typedef typename hash_key_types_base<value_type, VoidOrKeyOfValue>::key_of_value key_of_value;
  938. typedef BucketTraits bucket_traits;
  939. typedef bucket_plus_vtraits<ValueTraits, BucketTraits> bucket_plus_vtraits_t;
  940. typedef detail::ebo_functor_holder<hasher> base_t;
  941. template<class BucketTraitsType>
  942. BOOST_INTRUSIVE_FORCEINLINE bucket_hash_t(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits, const hasher & h)
  943. : detail::ebo_functor_holder<hasher>(h), bucket_plus_vtraits_t(val_traits, ::boost::forward<BucketTraitsType>(b_traits))
  944. {}
  945. BOOST_INTRUSIVE_FORCEINLINE const hasher &priv_hasher() const
  946. { return this->base_t::get(); }
  947. hasher &priv_hasher()
  948. { return this->base_t::get(); }
  949. using bucket_plus_vtraits_t::priv_stored_or_compute_hash; //For store_hash == true
  950. BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_stored_or_compute_hash(const value_type &v, detail::false_) const //For store_hash == false
  951. { return this->priv_hasher()(key_of_value()(v)); }
  952. };
  953. template<class ValueTraits, class BucketTraits, class VoidOrKeyOfValue, class VoidOrKeyEqual>
  954. struct hashtable_equal_holder
  955. {
  956. typedef detail::ebo_functor_holder
  957. < typename hash_key_equal < typename bucket_plus_vtraits<ValueTraits, BucketTraits>::value_traits::value_type
  958. , VoidOrKeyOfValue
  959. , VoidOrKeyEqual
  960. >::type
  961. > type;
  962. };
  963. //bucket_hash_equal_t
  964. //Stores bucket_hash_t and the equality function when the first
  965. //non-empty bucket shall not be cached.
  966. template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits, bool>
  967. struct bucket_hash_equal_t
  968. //Use public inheritance to avoid MSVC bugs with closures
  969. : public bucket_hash_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, BucketTraits> //3
  970. , public hashtable_equal_holder<ValueTraits, BucketTraits, VoidOrKeyOfValue, VoidOrKeyEqual>::type //equal
  971. {
  972. typedef typename hashtable_equal_holder
  973. <ValueTraits, BucketTraits, VoidOrKeyOfValue, VoidOrKeyEqual>::type equal_holder_t;
  974. typedef bucket_hash_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, BucketTraits> bucket_hash_type;
  975. typedef bucket_plus_vtraits<ValueTraits,BucketTraits> bucket_plus_vtraits_t;
  976. typedef ValueTraits value_traits;
  977. typedef typename equal_holder_t::functor_type key_equal;
  978. typedef typename bucket_hash_type::hasher hasher;
  979. typedef BucketTraits bucket_traits;
  980. typedef typename bucket_plus_vtraits_t::slist_impl slist_impl;
  981. typedef typename slist_impl::iterator siterator;
  982. typedef bucket_impl<slist_impl> bucket_type;
  983. typedef typename detail::unordered_bucket_ptr_impl<value_traits>::type bucket_ptr;
  984. template<class BucketTraitsType>
  985. bucket_hash_equal_t(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits, const hasher & h, const key_equal &e)
  986. : bucket_hash_type(val_traits, ::boost::forward<BucketTraitsType>(b_traits), h)
  987. , equal_holder_t(e)
  988. {}
  989. BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_get_cache()
  990. { return this->bucket_hash_type::priv_bucket_pointer(); }
  991. BOOST_INTRUSIVE_FORCEINLINE void priv_set_cache(const bucket_ptr &)
  992. {}
  993. BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_get_cache_bucket_num()
  994. { return 0u; }
  995. BOOST_INTRUSIVE_FORCEINLINE void priv_initialize_cache()
  996. {}
  997. BOOST_INTRUSIVE_FORCEINLINE void priv_swap_cache(bucket_hash_equal_t &)
  998. {}
  999. siterator priv_begin() const
  1000. {
  1001. std::size_t n = 0;
  1002. std::size_t bucket_cnt = this->bucket_hash_type::priv_bucket_count();
  1003. for (n = 0; n < bucket_cnt; ++n){
  1004. bucket_type &b = this->bucket_hash_type::priv_bucket_pointer()[n];
  1005. if(!b.empty()){
  1006. return b.begin();
  1007. }
  1008. }
  1009. return this->bucket_hash_type::priv_invalid_local_it();
  1010. }
  1011. BOOST_INTRUSIVE_FORCEINLINE void priv_insertion_update_cache(std::size_t)
  1012. {}
  1013. BOOST_INTRUSIVE_FORCEINLINE void priv_erasure_update_cache_range(std::size_t, std::size_t)
  1014. {}
  1015. BOOST_INTRUSIVE_FORCEINLINE void priv_erasure_update_cache()
  1016. {}
  1017. BOOST_INTRUSIVE_FORCEINLINE const key_equal &priv_equal() const
  1018. { return this->equal_holder_t::get(); }
  1019. BOOST_INTRUSIVE_FORCEINLINE key_equal &priv_equal()
  1020. { return this->equal_holder_t::get(); }
  1021. };
  1022. //bucket_hash_equal_t
  1023. //Stores bucket_hash_t and the equality function when the first
  1024. //non-empty bucket shall be cached.
  1025. template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits> //cache_begin == true version
  1026. struct bucket_hash_equal_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, true>
  1027. //Use public inheritance to avoid MSVC bugs with closures
  1028. : bucket_hash_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, BucketTraits> //2
  1029. , hashtable_equal_holder<ValueTraits, BucketTraits, VoidOrKeyOfValue, VoidOrKeyEqual>::type
  1030. {
  1031. typedef typename hashtable_equal_holder
  1032. <ValueTraits, BucketTraits, VoidOrKeyOfValue, VoidOrKeyEqual>::type equal_holder_t;
  1033. typedef bucket_plus_vtraits<ValueTraits,BucketTraits> bucket_plus_vtraits_t;
  1034. typedef ValueTraits value_traits;
  1035. typedef typename equal_holder_t::functor_type key_equal;
  1036. typedef bucket_hash_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, BucketTraits> bucket_hash_type;
  1037. typedef typename bucket_hash_type::hasher hasher;
  1038. typedef BucketTraits bucket_traits;
  1039. typedef typename bucket_plus_vtraits_t::slist_impl::iterator siterator;
  1040. template<class BucketTraitsType>
  1041. bucket_hash_equal_t(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits, const hasher & h, const key_equal &e)
  1042. : bucket_hash_type(val_traits, ::boost::forward<BucketTraitsType>(b_traits), h)
  1043. , equal_holder_t(e)
  1044. {}
  1045. typedef typename detail::unordered_bucket_ptr_impl
  1046. <typename bucket_hash_type::value_traits>::type bucket_ptr;
  1047. BOOST_INTRUSIVE_FORCEINLINE bucket_ptr &priv_get_cache()
  1048. { return cached_begin_; }
  1049. BOOST_INTRUSIVE_FORCEINLINE const bucket_ptr &priv_get_cache() const
  1050. { return cached_begin_; }
  1051. BOOST_INTRUSIVE_FORCEINLINE void priv_set_cache(const bucket_ptr &p)
  1052. { cached_begin_ = p; }
  1053. BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_get_cache_bucket_num()
  1054. { return this->cached_begin_ - this->bucket_hash_type::priv_bucket_pointer(); }
  1055. BOOST_INTRUSIVE_FORCEINLINE void priv_initialize_cache()
  1056. { this->cached_begin_ = this->bucket_hash_type::priv_invalid_bucket(); }
  1057. BOOST_INTRUSIVE_FORCEINLINE void priv_swap_cache(bucket_hash_equal_t &other)
  1058. {
  1059. ::boost::adl_move_swap(this->cached_begin_, other.cached_begin_);
  1060. }
  1061. siterator priv_begin() const
  1062. {
  1063. if(this->cached_begin_ == this->bucket_hash_type::priv_invalid_bucket()){
  1064. return this->bucket_hash_type::priv_invalid_local_it();
  1065. }
  1066. else{
  1067. return this->cached_begin_->begin();
  1068. }
  1069. }
  1070. void priv_insertion_update_cache(std::size_t insertion_bucket)
  1071. {
  1072. bucket_ptr p = this->bucket_hash_type::priv_bucket_pointer() + insertion_bucket;
  1073. if(p < this->cached_begin_){
  1074. this->cached_begin_ = p;
  1075. }
  1076. }
  1077. BOOST_INTRUSIVE_FORCEINLINE const key_equal &priv_equal() const
  1078. { return this->equal_holder_t::get(); }
  1079. BOOST_INTRUSIVE_FORCEINLINE key_equal &priv_equal()
  1080. { return this->equal_holder_t::get(); }
  1081. void priv_erasure_update_cache_range(std::size_t first_bucket_num, std::size_t last_bucket_num)
  1082. {
  1083. //If the last bucket is the end, the cache must be updated
  1084. //to the last position if all
  1085. if(this->priv_get_cache_bucket_num() == first_bucket_num &&
  1086. this->bucket_hash_type::priv_bucket_pointer()[first_bucket_num].empty() ){
  1087. this->priv_set_cache(this->bucket_hash_type::priv_bucket_pointer() + last_bucket_num);
  1088. this->priv_erasure_update_cache();
  1089. }
  1090. }
  1091. void priv_erasure_update_cache()
  1092. {
  1093. if(this->cached_begin_ != this->bucket_hash_type::priv_invalid_bucket()){
  1094. std::size_t current_n = this->priv_get_cache() - this->bucket_hash_type::priv_bucket_pointer();
  1095. for( const std::size_t num_buckets = this->bucket_hash_type::priv_bucket_count()
  1096. ; current_n < num_buckets
  1097. ; ++current_n, ++this->priv_get_cache()){
  1098. if(!this->priv_get_cache()->empty()){
  1099. return;
  1100. }
  1101. }
  1102. this->priv_initialize_cache();
  1103. }
  1104. }
  1105. bucket_ptr cached_begin_;
  1106. };
  1107. //This wrapper around size_traits is used
  1108. //to maintain minimal container size with compilers like MSVC
  1109. //that have problems with EBO and multiple empty base classes
  1110. template<class DeriveFrom, class SizeType, bool>
  1111. struct hashtable_size_traits_wrapper
  1112. : public DeriveFrom
  1113. {
  1114. template<class Base, class Arg0, class Arg1, class Arg2>
  1115. hashtable_size_traits_wrapper( BOOST_FWD_REF(Base) base, BOOST_FWD_REF(Arg0) arg0
  1116. , BOOST_FWD_REF(Arg1) arg1, BOOST_FWD_REF(Arg2) arg2)
  1117. : DeriveFrom(::boost::forward<Base>(base)
  1118. , ::boost::forward<Arg0>(arg0)
  1119. , ::boost::forward<Arg1>(arg1)
  1120. , ::boost::forward<Arg2>(arg2))
  1121. {}
  1122. typedef detail::size_holder < true, SizeType> size_traits;//size_traits
  1123. size_traits size_traits_;
  1124. typedef const size_traits & size_traits_const_t;
  1125. typedef size_traits & size_traits_t;
  1126. BOOST_INTRUSIVE_FORCEINLINE size_traits_const_t priv_size_traits() const
  1127. { return size_traits_; }
  1128. BOOST_INTRUSIVE_FORCEINLINE size_traits_t priv_size_traits()
  1129. { return size_traits_; }
  1130. };
  1131. template<class DeriveFrom, class SizeType>
  1132. struct hashtable_size_traits_wrapper<DeriveFrom, SizeType, false>
  1133. : public DeriveFrom
  1134. {
  1135. template<class Base, class Arg0, class Arg1, class Arg2>
  1136. hashtable_size_traits_wrapper( BOOST_FWD_REF(Base) base, BOOST_FWD_REF(Arg0) arg0
  1137. , BOOST_FWD_REF(Arg1) arg1, BOOST_FWD_REF(Arg2) arg2)
  1138. : DeriveFrom(::boost::forward<Base>(base)
  1139. , ::boost::forward<Arg0>(arg0)
  1140. , ::boost::forward<Arg1>(arg1)
  1141. , ::boost::forward<Arg2>(arg2))
  1142. {}
  1143. typedef detail::size_holder< false, SizeType> size_traits;
  1144. typedef size_traits size_traits_const_t;
  1145. typedef size_traits size_traits_t;
  1146. BOOST_INTRUSIVE_FORCEINLINE size_traits priv_size_traits() const
  1147. { return size_traits(); }
  1148. };
  1149. //hashdata_internal
  1150. //Stores bucket_hash_equal_t and split_traits
  1151. template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits, class SizeType, std::size_t BoolFlags>
  1152. struct hashdata_internal
  1153. : public hashtable_size_traits_wrapper
  1154. < bucket_hash_equal_t
  1155. < ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual
  1156. , BucketTraits
  1157. , 0 != (BoolFlags & hash_bool_flags::cache_begin_pos)
  1158. > //2
  1159. , SizeType
  1160. , (BoolFlags & hash_bool_flags::incremental_pos) != 0
  1161. >
  1162. {
  1163. typedef hashtable_size_traits_wrapper
  1164. < bucket_hash_equal_t
  1165. < ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual
  1166. , BucketTraits
  1167. , 0 != (BoolFlags & hash_bool_flags::cache_begin_pos)
  1168. > //2
  1169. , SizeType
  1170. , (BoolFlags & hash_bool_flags::incremental_pos) != 0
  1171. > internal_type;
  1172. typedef typename internal_type::key_equal key_equal;
  1173. typedef typename internal_type::hasher hasher;
  1174. typedef bucket_plus_vtraits<ValueTraits,BucketTraits> bucket_plus_vtraits_t;
  1175. typedef SizeType size_type;
  1176. typedef typename internal_type::size_traits split_traits;
  1177. typedef typename bucket_plus_vtraits_t::bucket_ptr bucket_ptr;
  1178. typedef typename bucket_plus_vtraits_t::const_value_traits_ptr const_value_traits_ptr;
  1179. typedef typename bucket_plus_vtraits_t::siterator siterator;
  1180. typedef typename bucket_plus_vtraits_t::bucket_traits bucket_traits;
  1181. typedef typename bucket_plus_vtraits_t::value_traits value_traits;
  1182. typedef typename bucket_plus_vtraits_t::bucket_type bucket_type;
  1183. typedef typename value_traits::value_type value_type;
  1184. typedef typename value_traits::pointer pointer;
  1185. typedef typename value_traits::const_pointer const_pointer;
  1186. typedef typename pointer_traits<pointer>::reference reference;
  1187. typedef typename pointer_traits
  1188. <const_pointer>::reference const_reference;
  1189. typedef typename value_traits::node_traits node_traits;
  1190. typedef typename node_traits::node node;
  1191. typedef typename node_traits::node_ptr node_ptr;
  1192. typedef typename node_traits::const_node_ptr const_node_ptr;
  1193. typedef detail::node_functions<node_traits> node_functions_t;
  1194. typedef typename get_slist_impl
  1195. <typename reduced_slist_node_traits
  1196. <typename value_traits::node_traits>::type
  1197. >::type slist_impl;
  1198. typedef typename slist_impl::node_algorithms node_algorithms;
  1199. typedef typename slist_impl::node_ptr slist_node_ptr;
  1200. typedef hash_key_types_base
  1201. < typename ValueTraits::value_type
  1202. , VoidOrKeyOfValue
  1203. > hash_types_base;
  1204. typedef typename hash_types_base::key_of_value key_of_value;
  1205. static const bool store_hash = detail::store_hash_is_true<node_traits>::value;
  1206. static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value;
  1207. static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value;
  1208. typedef detail::bool_<store_hash> store_hash_t;
  1209. typedef detail::transform_iterator
  1210. < typename slist_impl::iterator
  1211. , downcast_node_to_value_t
  1212. < value_traits
  1213. , false> > local_iterator;
  1214. typedef detail::transform_iterator
  1215. < typename slist_impl::iterator
  1216. , downcast_node_to_value_t
  1217. < value_traits
  1218. , true> > const_local_iterator;
  1219. //
  1220. template<class BucketTraitsType>
  1221. hashdata_internal( const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits
  1222. , const hasher & h, const key_equal &e)
  1223. : internal_type(val_traits, ::boost::forward<BucketTraitsType>(b_traits), h, e)
  1224. {}
  1225. BOOST_INTRUSIVE_FORCEINLINE typename internal_type::size_traits_t priv_split_traits()
  1226. { return this->priv_size_traits(); }
  1227. BOOST_INTRUSIVE_FORCEINLINE typename internal_type::size_traits_const_t priv_split_traits() const
  1228. { return this->priv_size_traits(); }
  1229. ~hashdata_internal()
  1230. { this->priv_clear_buckets(); }
  1231. void priv_clear_buckets()
  1232. {
  1233. this->internal_type::priv_clear_buckets
  1234. ( this->priv_get_cache()
  1235. , this->internal_type::priv_bucket_count()
  1236. - (this->priv_get_cache()
  1237. - this->internal_type::priv_bucket_pointer()));
  1238. }
  1239. void priv_clear_buckets_and_cache()
  1240. {
  1241. this->priv_clear_buckets();
  1242. this->priv_initialize_cache();
  1243. }
  1244. void priv_initialize_buckets_and_cache()
  1245. {
  1246. this->internal_type::priv_clear_buckets
  1247. ( this->internal_type::priv_bucket_pointer()
  1248. , this->internal_type::priv_bucket_count());
  1249. this->priv_initialize_cache();
  1250. }
  1251. typedef hashtable_iterator<bucket_plus_vtraits_t, false> iterator;
  1252. typedef hashtable_iterator<bucket_plus_vtraits_t, true> const_iterator;
  1253. static std::size_t priv_stored_hash(slist_node_ptr n, detail::true_ true_value)
  1254. { return bucket_plus_vtraits<ValueTraits, BucketTraits>::priv_stored_hash(n, true_value); }
  1255. static std::size_t priv_stored_hash(slist_node_ptr n, detail::false_ false_value)
  1256. { return bucket_plus_vtraits<ValueTraits, BucketTraits>::priv_stored_hash(n, false_value); }
  1257. //public functions
  1258. BOOST_INTRUSIVE_FORCEINLINE SizeType split_count() const
  1259. {
  1260. return this->priv_split_traits().get_size();
  1261. }
  1262. BOOST_INTRUSIVE_FORCEINLINE iterator iterator_to(reference value)
  1263. {
  1264. return iterator(bucket_type::s_iterator_to
  1265. (this->priv_value_to_node(value)), &this->get_bucket_value_traits());
  1266. }
  1267. const_iterator iterator_to(const_reference value) const
  1268. {
  1269. siterator const sit = bucket_type::s_iterator_to
  1270. ( *pointer_traits<node_ptr>::const_cast_from
  1271. (pointer_traits<const_node_ptr>::pointer_to(this->priv_value_to_node(value)))
  1272. );
  1273. return const_iterator(sit, &this->get_bucket_value_traits());
  1274. }
  1275. static local_iterator s_local_iterator_to(reference value)
  1276. {
  1277. BOOST_STATIC_ASSERT((!stateful_value_traits));
  1278. siterator sit = bucket_type::s_iterator_to(*value_traits::to_node_ptr(value));
  1279. return local_iterator(sit, const_value_traits_ptr());
  1280. }
  1281. static const_local_iterator s_local_iterator_to(const_reference value)
  1282. {
  1283. BOOST_STATIC_ASSERT((!stateful_value_traits));
  1284. siterator const sit = bucket_type::s_iterator_to
  1285. ( *pointer_traits<node_ptr>::const_cast_from
  1286. (value_traits::to_node_ptr(value))
  1287. );
  1288. return const_local_iterator(sit, const_value_traits_ptr());
  1289. }
  1290. local_iterator local_iterator_to(reference value)
  1291. {
  1292. siterator sit = bucket_type::s_iterator_to(this->priv_value_to_node(value));
  1293. return local_iterator(sit, this->priv_value_traits_ptr());
  1294. }
  1295. const_local_iterator local_iterator_to(const_reference value) const
  1296. {
  1297. siterator sit = bucket_type::s_iterator_to
  1298. ( *pointer_traits<node_ptr>::const_cast_from
  1299. (pointer_traits<const_node_ptr>::pointer_to(this->priv_value_to_node(value)))
  1300. );
  1301. return const_local_iterator(sit, this->priv_value_traits_ptr());
  1302. }
  1303. BOOST_INTRUSIVE_FORCEINLINE size_type bucket_count() const
  1304. {
  1305. const std::size_t bc = this->priv_bucket_count();
  1306. BOOST_INTRUSIVE_INVARIANT_ASSERT(sizeof(size_type) >= sizeof(std::size_t) || bc <= size_type(-1));
  1307. return static_cast<size_type>(bc);
  1308. }
  1309. BOOST_INTRUSIVE_FORCEINLINE size_type bucket_size(size_type n) const
  1310. { return this->priv_bucket_pointer()[n].size(); }
  1311. BOOST_INTRUSIVE_FORCEINLINE bucket_ptr bucket_pointer() const
  1312. { return this->priv_bucket_pointer(); }
  1313. BOOST_INTRUSIVE_FORCEINLINE local_iterator begin(size_type n)
  1314. { return local_iterator(this->priv_bucket_pointer()[n].begin(), this->priv_value_traits_ptr()); }
  1315. BOOST_INTRUSIVE_FORCEINLINE const_local_iterator begin(size_type n) const
  1316. { return this->cbegin(n); }
  1317. static BOOST_INTRUSIVE_FORCEINLINE size_type suggested_upper_bucket_count(size_type n)
  1318. {
  1319. return prime_list_holder<0>::suggested_upper_bucket_count(n);
  1320. }
  1321. static BOOST_INTRUSIVE_FORCEINLINE size_type suggested_lower_bucket_count(size_type n)
  1322. {
  1323. return prime_list_holder<0>::suggested_lower_bucket_count(n);
  1324. }
  1325. const_local_iterator cbegin(size_type n) const
  1326. {
  1327. return const_local_iterator
  1328. ( pointer_traits<bucket_ptr>::const_cast_from(this->priv_bucket_pointer())[n].begin()
  1329. , this->priv_value_traits_ptr());
  1330. }
  1331. using internal_type::end;
  1332. using internal_type::cend;
  1333. local_iterator end(size_type n)
  1334. { return local_iterator(this->priv_bucket_pointer()[n].end(), this->priv_value_traits_ptr()); }
  1335. BOOST_INTRUSIVE_FORCEINLINE const_local_iterator end(size_type n) const
  1336. { return this->cend(n); }
  1337. const_local_iterator cend(size_type n) const
  1338. {
  1339. return const_local_iterator
  1340. ( pointer_traits<bucket_ptr>::const_cast_from(this->priv_bucket_pointer())[n].end()
  1341. , this->priv_value_traits_ptr());
  1342. }
  1343. //Public functions for hashtable_impl
  1344. BOOST_INTRUSIVE_FORCEINLINE iterator begin()
  1345. { return iterator(this->priv_begin(), &this->get_bucket_value_traits()); }
  1346. BOOST_INTRUSIVE_FORCEINLINE const_iterator begin() const
  1347. { return this->cbegin(); }
  1348. BOOST_INTRUSIVE_FORCEINLINE const_iterator cbegin() const
  1349. { return const_iterator(this->priv_begin(), &this->get_bucket_value_traits()); }
  1350. BOOST_INTRUSIVE_FORCEINLINE hasher hash_function() const
  1351. { return this->priv_hasher(); }
  1352. BOOST_INTRUSIVE_FORCEINLINE key_equal key_eq() const
  1353. { return this->priv_equal(); }
  1354. };
  1355. /// @endcond
  1356. //! The class template hashtable is an intrusive hash table container, that
  1357. //! is used to construct intrusive unordered_set and unordered_multiset containers. The
  1358. //! no-throw guarantee holds only, if the VoidOrKeyEqual object and Hasher don't throw.
  1359. //!
  1360. //! hashtable is a semi-intrusive container: each object to be stored in the
  1361. //! container must contain a proper hook, but the container also needs
  1362. //! additional auxiliary memory to work: hashtable needs a pointer to an array
  1363. //! of type `bucket_type` to be passed in the constructor. This bucket array must
  1364. //! have at least the same lifetime as the container. This makes the use of
  1365. //! hashtable more complicated than purely intrusive containers.
  1366. //! `bucket_type` is default-constructible, copyable and assignable
  1367. //!
  1368. //! The template parameter \c T is the type to be managed by the container.
  1369. //! The user can specify additional options and if no options are provided
  1370. //! default options are used.
  1371. //!
  1372. //! The container supports the following options:
  1373. //! \c base_hook<>/member_hook<>/value_traits<>,
  1374. //! \c constant_time_size<>, \c size_type<>, \c hash<> and \c equal<>
  1375. //! \c bucket_traits<>, power_2_buckets<>, cache_begin<> and incremental<>.
  1376. //!
  1377. //! hashtable only provides forward iterators but it provides 4 iterator types:
  1378. //! iterator and const_iterator to navigate through the whole container and
  1379. //! local_iterator and const_local_iterator to navigate through the values
  1380. //! stored in a single bucket. Local iterators are faster and smaller.
  1381. //!
  1382. //! It's not recommended to use non constant-time size hashtables because several
  1383. //! key functions, like "empty()", become non-constant time functions. Non
  1384. //! constant_time size hashtables are mainly provided to support auto-unlink hooks.
  1385. //!
  1386. //! hashtables, does not make automatic rehashings nor
  1387. //! offers functions related to a load factor. Rehashing can be explicitly requested
  1388. //! and the user must provide a new bucket array that will be used from that moment.
  1389. //!
  1390. //! Since no automatic rehashing is done, iterators are never invalidated when
  1391. //! inserting or erasing elements. Iterators are only invalidated when rehashing.
  1392. #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  1393. template<class T, class ...Options>
  1394. #else
  1395. template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits, class SizeType, std::size_t BoolFlags>
  1396. #endif
  1397. class hashtable_impl
  1398. : private hashtable_size_traits_wrapper
  1399. < hashdata_internal
  1400. < ValueTraits
  1401. , VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual
  1402. , BucketTraits, SizeType
  1403. , BoolFlags & (hash_bool_flags::incremental_pos | hash_bool_flags::cache_begin_pos) //1
  1404. >
  1405. , SizeType
  1406. , (BoolFlags & hash_bool_flags::constant_time_size_pos) != 0
  1407. >
  1408. {
  1409. typedef hashtable_size_traits_wrapper
  1410. < hashdata_internal
  1411. < ValueTraits
  1412. , VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual
  1413. , BucketTraits, SizeType
  1414. , BoolFlags & (hash_bool_flags::incremental_pos | hash_bool_flags::cache_begin_pos) //1
  1415. >
  1416. , SizeType
  1417. , (BoolFlags & hash_bool_flags::constant_time_size_pos) != 0
  1418. > internal_type;
  1419. typedef typename internal_type::size_traits size_traits;
  1420. typedef hash_key_types_base
  1421. < typename ValueTraits::value_type
  1422. , VoidOrKeyOfValue
  1423. > hash_types_base;
  1424. public:
  1425. typedef ValueTraits value_traits;
  1426. /// @cond
  1427. typedef BucketTraits bucket_traits;
  1428. typedef typename internal_type::slist_impl slist_impl;
  1429. typedef bucket_plus_vtraits<ValueTraits, BucketTraits> bucket_plus_vtraits_t;
  1430. typedef typename bucket_plus_vtraits_t::const_value_traits_ptr const_value_traits_ptr;
  1431. using internal_type::begin;
  1432. using internal_type::cbegin;
  1433. using internal_type::end;
  1434. using internal_type::cend;
  1435. using internal_type::hash_function;
  1436. using internal_type::key_eq;
  1437. using internal_type::bucket_size;
  1438. using internal_type::bucket_count;
  1439. using internal_type::local_iterator_to;
  1440. using internal_type::s_local_iterator_to;
  1441. using internal_type::iterator_to;
  1442. using internal_type::bucket_pointer;
  1443. using internal_type::suggested_upper_bucket_count;
  1444. using internal_type::suggested_lower_bucket_count;
  1445. using internal_type::split_count;
  1446. /// @endcond
  1447. typedef typename value_traits::pointer pointer;
  1448. typedef typename value_traits::const_pointer const_pointer;
  1449. typedef typename value_traits::value_type value_type;
  1450. typedef typename hash_types_base::key_type key_type;
  1451. typedef typename hash_types_base::key_of_value key_of_value;
  1452. typedef typename pointer_traits<pointer>::reference reference;
  1453. typedef typename pointer_traits<const_pointer>::reference const_reference;
  1454. typedef typename pointer_traits<pointer>::difference_type difference_type;
  1455. typedef SizeType size_type;
  1456. typedef typename internal_type::key_equal key_equal;
  1457. typedef typename internal_type::hasher hasher;
  1458. typedef bucket_impl<slist_impl> bucket_type;
  1459. typedef typename internal_type::bucket_ptr bucket_ptr;
  1460. typedef typename slist_impl::iterator siterator;
  1461. typedef typename slist_impl::const_iterator const_siterator;
  1462. typedef typename internal_type::iterator iterator;
  1463. typedef typename internal_type::const_iterator const_iterator;
  1464. typedef typename internal_type::local_iterator local_iterator;
  1465. typedef typename internal_type::const_local_iterator const_local_iterator;
  1466. typedef typename value_traits::node_traits node_traits;
  1467. typedef typename node_traits::node node;
  1468. typedef typename pointer_traits
  1469. <pointer>::template rebind_pointer
  1470. < node >::type node_ptr;
  1471. typedef typename pointer_traits
  1472. <pointer>::template rebind_pointer
  1473. < const node >::type const_node_ptr;
  1474. typedef typename pointer_traits
  1475. <node_ptr>::reference node_reference;
  1476. typedef typename pointer_traits
  1477. <const_node_ptr>::reference const_node_reference;
  1478. typedef typename slist_impl::node_algorithms node_algorithms;
  1479. static const bool stateful_value_traits = internal_type::stateful_value_traits;
  1480. static const bool store_hash = internal_type::store_hash;
  1481. static const bool unique_keys = 0 != (BoolFlags & hash_bool_flags::unique_keys_pos);
  1482. static const bool constant_time_size = 0 != (BoolFlags & hash_bool_flags::constant_time_size_pos);
  1483. static const bool cache_begin = 0 != (BoolFlags & hash_bool_flags::cache_begin_pos);
  1484. static const bool compare_hash = 0 != (BoolFlags & hash_bool_flags::compare_hash_pos);
  1485. static const bool incremental = 0 != (BoolFlags & hash_bool_flags::incremental_pos);
  1486. static const bool power_2_buckets = incremental || (0 != (BoolFlags & hash_bool_flags::power_2_buckets_pos));
  1487. static const bool optimize_multikey
  1488. = detail::optimize_multikey_is_true<node_traits>::value && !unique_keys;
  1489. /// @cond
  1490. static const bool is_multikey = !unique_keys;
  1491. private:
  1492. //Configuration error: compare_hash<> can't be specified without store_hash<>
  1493. //See documentation for more explanations
  1494. BOOST_STATIC_ASSERT((!compare_hash || store_hash));
  1495. typedef typename slist_impl::node_ptr slist_node_ptr;
  1496. typedef typename pointer_traits
  1497. <slist_node_ptr>::template rebind_pointer
  1498. < void >::type void_pointer;
  1499. //We'll define group traits, but these won't be instantiated if
  1500. //optimize_multikey is not true
  1501. typedef unordered_group_adapter<node_traits> group_traits;
  1502. typedef circular_slist_algorithms<group_traits> group_algorithms;
  1503. typedef typename internal_type::store_hash_t store_hash_t;
  1504. typedef detail::bool_<optimize_multikey> optimize_multikey_t;
  1505. typedef detail::bool_<cache_begin> cache_begin_t;
  1506. typedef detail::bool_<power_2_buckets> power_2_buckets_t;
  1507. typedef typename internal_type::split_traits split_traits;
  1508. typedef detail::group_functions<node_traits> group_functions_t;
  1509. typedef detail::node_functions<node_traits> node_functions_t;
  1510. private:
  1511. //noncopyable, movable
  1512. BOOST_MOVABLE_BUT_NOT_COPYABLE(hashtable_impl)
  1513. static const bool safemode_or_autounlink = internal_type::safemode_or_autounlink;
  1514. //Constant-time size is incompatible with auto-unlink hooks!
  1515. BOOST_STATIC_ASSERT(!(constant_time_size && ((int)value_traits::link_mode == (int)auto_unlink)));
  1516. //Cache begin is incompatible with auto-unlink hooks!
  1517. BOOST_STATIC_ASSERT(!(cache_begin && ((int)value_traits::link_mode == (int)auto_unlink)));
  1518. template<class Disposer>
  1519. struct typeof_node_disposer
  1520. {
  1521. typedef node_cast_adaptor
  1522. < detail::node_disposer< Disposer, value_traits, CircularSListAlgorithms>
  1523. , slist_node_ptr, node_ptr > type;
  1524. };
  1525. template<class Disposer>
  1526. typename typeof_node_disposer<Disposer>::type
  1527. make_node_disposer(const Disposer &disposer) const
  1528. {
  1529. typedef typename typeof_node_disposer<Disposer>::type return_t;
  1530. return return_t(disposer, &this->priv_value_traits());
  1531. }
  1532. /// @endcond
  1533. public:
  1534. typedef detail::insert_commit_data_impl insert_commit_data;
  1535. public:
  1536. //! <b>Requires</b>: buckets must not be being used by any other resource.
  1537. //!
  1538. //! <b>Effects</b>: Constructs an empty unordered_set, storing a reference
  1539. //! to the bucket array and copies of the key_hasher and equal_func functors.
  1540. //!
  1541. //! <b>Complexity</b>: Constant.
  1542. //!
  1543. //! <b>Throws</b>: If value_traits::node_traits::node
  1544. //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
  1545. //! or the copy constructor or invocation of hash_func or equal_func throws.
  1546. //!
  1547. //! <b>Notes</b>: buckets array must be disposed only after
  1548. //! *this is disposed.
  1549. explicit hashtable_impl ( const bucket_traits &b_traits
  1550. , const hasher & hash_func = hasher()
  1551. , const key_equal &equal_func = key_equal()
  1552. , const value_traits &v_traits = value_traits())
  1553. : internal_type(v_traits, b_traits, hash_func, equal_func)
  1554. {
  1555. this->priv_initialize_buckets_and_cache();
  1556. this->priv_size_traits().set_size(size_type(0));
  1557. size_type bucket_sz = this->bucket_count();
  1558. BOOST_INTRUSIVE_INVARIANT_ASSERT(bucket_sz != 0);
  1559. //Check power of two bucket array if the option is activated
  1560. BOOST_INTRUSIVE_INVARIANT_ASSERT
  1561. (!power_2_buckets || (0 == (bucket_sz & (bucket_sz-1))));
  1562. this->priv_split_traits().set_size(bucket_sz>>1);
  1563. }
  1564. //! <b>Requires</b>: buckets must not be being used by any other resource
  1565. //! and dereferencing iterator must yield an lvalue of type value_type.
  1566. //!
  1567. //! <b>Effects</b>: Constructs an empty container and inserts elements from
  1568. //! [b, e).
  1569. //!
  1570. //! <b>Complexity</b>: If N is distance(b, e): Average case is O(N)
  1571. //! (with a good hash function and with buckets_len >= N),worst case O(N^2).
  1572. //!
  1573. //! <b>Throws</b>: If value_traits::node_traits::node
  1574. //! constructor throws (this does not happen with predefined Boost.Intrusive hooks)
  1575. //! or the copy constructor or invocation of hasher or key_equal throws.
  1576. //!
  1577. //! <b>Notes</b>: buckets array must be disposed only after
  1578. //! *this is disposed.
  1579. template<class Iterator>
  1580. hashtable_impl ( bool unique, Iterator b, Iterator e
  1581. , const bucket_traits &b_traits
  1582. , const hasher & hash_func = hasher()
  1583. , const key_equal &equal_func = key_equal()
  1584. , const value_traits &v_traits = value_traits())
  1585. : internal_type(v_traits, b_traits, hash_func, equal_func)
  1586. {
  1587. this->priv_initialize_buckets_and_cache();
  1588. this->priv_size_traits().set_size(size_type(0));
  1589. size_type bucket_sz = this->bucket_count();
  1590. BOOST_INTRUSIVE_INVARIANT_ASSERT(bucket_sz != 0);
  1591. //Check power of two bucket array if the option is activated
  1592. BOOST_INTRUSIVE_INVARIANT_ASSERT
  1593. (!power_2_buckets || (0 == (bucket_sz & (bucket_sz-1))));
  1594. this->priv_split_traits().set_size(bucket_sz>>1);
  1595. //Now insert
  1596. if(unique)
  1597. this->insert_unique(b, e);
  1598. else
  1599. this->insert_equal(b, e);
  1600. }
  1601. //! <b>Effects</b>: Constructs a container moving resources from another container.
  1602. //! Internal value traits, bucket traits, hasher and comparison are move constructed and
  1603. //! nodes belonging to x are linked to *this.
  1604. //!
  1605. //! <b>Complexity</b>: Constant.
  1606. //!
  1607. //! <b>Throws</b>: If value_traits::node_traits::node's
  1608. //! move constructor throws (this does not happen with predefined Boost.Intrusive hooks)
  1609. //! or the move constructor of value traits, bucket traits, hasher or comparison throws.
  1610. hashtable_impl(BOOST_RV_REF(hashtable_impl) x)
  1611. : internal_type( ::boost::move(x.priv_value_traits())
  1612. , ::boost::move(x.priv_bucket_traits())
  1613. , ::boost::move(x.priv_hasher())
  1614. , ::boost::move(x.priv_equal())
  1615. )
  1616. {
  1617. this->priv_swap_cache(x);
  1618. x.priv_initialize_cache();
  1619. this->priv_size_traits().set_size(x.priv_size_traits().get_size());
  1620. x.priv_size_traits().set_size(size_type(0));
  1621. this->priv_split_traits().set_size(x.priv_split_traits().get_size());
  1622. x.priv_split_traits().set_size(size_type(0));
  1623. }
  1624. //! <b>Effects</b>: Equivalent to swap.
  1625. //!
  1626. hashtable_impl& operator=(BOOST_RV_REF(hashtable_impl) x)
  1627. { this->swap(x); return *this; }
  1628. #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  1629. //! <b>Effects</b>: Detaches all elements from this. The objects in the unordered_set
  1630. //! are not deleted (i.e. no destructors are called).
  1631. //!
  1632. //! <b>Complexity</b>: Linear to the number of elements in the unordered_set, if
  1633. //! it's a safe-mode or auto-unlink value. Otherwise constant.
  1634. //!
  1635. //! <b>Throws</b>: Nothing.
  1636. ~hashtable_impl();
  1637. //! <b>Effects</b>: Returns an iterator pointing to the beginning of the unordered_set.
  1638. //!
  1639. //! <b>Complexity</b>: Amortized constant time.
  1640. //! Worst case (empty unordered_set): O(this->bucket_count())
  1641. //!
  1642. //! <b>Throws</b>: Nothing.
  1643. iterator begin();
  1644. //! <b>Effects</b>: Returns a const_iterator pointing to the beginning
  1645. //! of the unordered_set.
  1646. //!
  1647. //! <b>Complexity</b>: Amortized constant time.
  1648. //! Worst case (empty unordered_set): O(this->bucket_count())
  1649. //!
  1650. //! <b>Throws</b>: Nothing.
  1651. const_iterator begin() const;
  1652. //! <b>Effects</b>: Returns a const_iterator pointing to the beginning
  1653. //! of the unordered_set.
  1654. //!
  1655. //! <b>Complexity</b>: Amortized constant time.
  1656. //! Worst case (empty unordered_set): O(this->bucket_count())
  1657. //!
  1658. //! <b>Throws</b>: Nothing.
  1659. const_iterator cbegin() const;
  1660. //! <b>Effects</b>: Returns an iterator pointing to the end of the unordered_set.
  1661. //!
  1662. //! <b>Complexity</b>: Constant.
  1663. //!
  1664. //! <b>Throws</b>: Nothing.
  1665. iterator end();
  1666. //! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_set.
  1667. //!
  1668. //! <b>Complexity</b>: Constant.
  1669. //!
  1670. //! <b>Throws</b>: Nothing.
  1671. const_iterator end() const;
  1672. //! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_set.
  1673. //!
  1674. //! <b>Complexity</b>: Constant.
  1675. //!
  1676. //! <b>Throws</b>: Nothing.
  1677. const_iterator cend() const;
  1678. //! <b>Effects</b>: Returns the hasher object used by the unordered_set.
  1679. //!
  1680. //! <b>Complexity</b>: Constant.
  1681. //!
  1682. //! <b>Throws</b>: If hasher copy-constructor throws.
  1683. hasher hash_function() const;
  1684. //! <b>Effects</b>: Returns the key_equal object used by the unordered_set.
  1685. //!
  1686. //! <b>Complexity</b>: Constant.
  1687. //!
  1688. //! <b>Throws</b>: If key_equal copy-constructor throws.
  1689. key_equal key_eq() const;
  1690. #endif
  1691. //! <b>Effects</b>: Returns true if the container is empty.
  1692. //!
  1693. //! <b>Complexity</b>: if constant-time size and cache_begin options are disabled,
  1694. //! average constant time (worst case, with empty() == true: O(this->bucket_count()).
  1695. //! Otherwise constant.
  1696. //!
  1697. //! <b>Throws</b>: Nothing.
  1698. bool empty() const
  1699. {
  1700. if(constant_time_size){
  1701. return !this->size();
  1702. }
  1703. else if(cache_begin){
  1704. return this->begin() == this->end();
  1705. }
  1706. else{
  1707. size_type bucket_cnt = this->bucket_count();
  1708. const bucket_type *b = boost::movelib::to_raw_pointer(this->priv_bucket_pointer());
  1709. for (size_type n = 0; n < bucket_cnt; ++n, ++b){
  1710. if(!b->empty()){
  1711. return false;
  1712. }
  1713. }
  1714. return true;
  1715. }
  1716. }
  1717. //! <b>Effects</b>: Returns the number of elements stored in the unordered_set.
  1718. //!
  1719. //! <b>Complexity</b>: Linear to elements contained in *this if
  1720. //! constant_time_size is false. Constant-time otherwise.
  1721. //!
  1722. //! <b>Throws</b>: Nothing.
  1723. size_type size() const
  1724. {
  1725. if(constant_time_size)
  1726. return this->priv_size_traits().get_size();
  1727. else{
  1728. size_type len = 0;
  1729. size_type bucket_cnt = this->bucket_count();
  1730. const bucket_type *b = boost::movelib::to_raw_pointer(this->priv_bucket_pointer());
  1731. for (size_type n = 0; n < bucket_cnt; ++n, ++b){
  1732. len += b->size();
  1733. }
  1734. return len;
  1735. }
  1736. }
  1737. //! <b>Requires</b>: the hasher and the equality function unqualified swap
  1738. //! call should not throw.
  1739. //!
  1740. //! <b>Effects</b>: Swaps the contents of two unordered_sets.
  1741. //! Swaps also the contained bucket array and equality and hasher functors.
  1742. //!
  1743. //! <b>Complexity</b>: Constant.
  1744. //!
  1745. //! <b>Throws</b>: If the swap() call for the comparison or hash functors
  1746. //! found using ADL throw. Basic guarantee.
  1747. void swap(hashtable_impl& other)
  1748. {
  1749. //These can throw
  1750. ::boost::adl_move_swap(this->priv_equal(), other.priv_equal());
  1751. ::boost::adl_move_swap(this->priv_hasher(), other.priv_hasher());
  1752. //These can't throw
  1753. ::boost::adl_move_swap(this->priv_bucket_traits(), other.priv_bucket_traits());
  1754. ::boost::adl_move_swap(this->priv_value_traits(), other.priv_value_traits());
  1755. this->priv_swap_cache(other);
  1756. this->priv_size_traits().swap(other.priv_size_traits());
  1757. this->priv_split_traits().swap(other.priv_split_traits());
  1758. }
  1759. //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw
  1760. //! Cloner should yield to nodes that compare equal and produce the same
  1761. //! hash than the original node.
  1762. //!
  1763. //! <b>Effects</b>: Erases all the elements from *this
  1764. //! calling Disposer::operator()(pointer), clones all the
  1765. //! elements from src calling Cloner::operator()(const_reference )
  1766. //! and inserts them on *this. The hash function and the equality
  1767. //! predicate are copied from the source.
  1768. //!
  1769. //! If store_hash option is true, this method does not use the hash function.
  1770. //!
  1771. //! If any operation throws, all cloned elements are unlinked and disposed
  1772. //! calling Disposer::operator()(pointer).
  1773. //!
  1774. //! <b>Complexity</b>: Linear to erased plus inserted elements.
  1775. //!
  1776. //! <b>Throws</b>: If cloner or hasher throw or hash or equality predicate copying
  1777. //! throws. Basic guarantee.
  1778. template <class Cloner, class Disposer>
  1779. BOOST_INTRUSIVE_FORCEINLINE void clone_from(const hashtable_impl &src, Cloner cloner, Disposer disposer)
  1780. { this->priv_clone_from(src, cloner, disposer); }
  1781. //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw
  1782. //! Cloner should yield to nodes that compare equal and produce the same
  1783. //! hash than the original node.
  1784. //!
  1785. //! <b>Effects</b>: Erases all the elements from *this
  1786. //! calling Disposer::operator()(pointer), clones all the
  1787. //! elements from src calling Cloner::operator()(reference)
  1788. //! and inserts them on *this. The hash function and the equality
  1789. //! predicate are copied from the source.
  1790. //!
  1791. //! If store_hash option is true, this method does not use the hash function.
  1792. //!
  1793. //! If any operation throws, all cloned elements are unlinked and disposed
  1794. //! calling Disposer::operator()(pointer).
  1795. //!
  1796. //! <b>Complexity</b>: Linear to erased plus inserted elements.
  1797. //!
  1798. //! <b>Throws</b>: If cloner or hasher throw or hash or equality predicate copying
  1799. //! throws. Basic guarantee.
  1800. template <class Cloner, class Disposer>
  1801. BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(hashtable_impl) src, Cloner cloner, Disposer disposer)
  1802. { this->priv_clone_from(static_cast<hashtable_impl&>(src), cloner, disposer); }
  1803. //! <b>Requires</b>: value must be an lvalue
  1804. //!
  1805. //! <b>Effects</b>: Inserts the value into the unordered_set.
  1806. //!
  1807. //! <b>Returns</b>: An iterator to the inserted value.
  1808. //!
  1809. //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
  1810. //!
  1811. //! <b>Throws</b>: If the internal hasher or the equality functor throws. Strong guarantee.
  1812. //!
  1813. //! <b>Note</b>: Does not affect the validity of iterators and references.
  1814. //! No copy-constructors are called.
  1815. iterator insert_equal(reference value)
  1816. {
  1817. size_type bucket_num;
  1818. std::size_t hash_value;
  1819. siterator prev;
  1820. siterator const it = this->priv_find
  1821. (key_of_value()(value), this->priv_hasher(), this->priv_equal(), bucket_num, hash_value, prev);
  1822. bool const next_is_in_group = optimize_multikey && it != this->priv_invalid_local_it();
  1823. return this->priv_insert_equal_after_find(value, bucket_num, hash_value, prev, next_is_in_group);
  1824. }
  1825. //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
  1826. //! of type value_type.
  1827. //!
  1828. //! <b>Effects</b>: Equivalent to this->insert_equal(t) for each element in [b, e).
  1829. //!
  1830. //! <b>Complexity</b>: Average case O(N), where N is distance(b, e).
  1831. //! Worst case O(N*this->size()).
  1832. //!
  1833. //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
  1834. //!
  1835. //! <b>Note</b>: Does not affect the validity of iterators and references.
  1836. //! No copy-constructors are called.
  1837. template<class Iterator>
  1838. void insert_equal(Iterator b, Iterator e)
  1839. {
  1840. for (; b != e; ++b)
  1841. this->insert_equal(*b);
  1842. }
  1843. //! <b>Requires</b>: value must be an lvalue
  1844. //!
  1845. //! <b>Effects</b>: Tries to inserts value into the unordered_set.
  1846. //!
  1847. //! <b>Returns</b>: If the value
  1848. //! is not already present inserts it and returns a pair containing the
  1849. //! iterator to the new value and true. If there is an equivalent value
  1850. //! returns a pair containing an iterator to the already present value
  1851. //! and false.
  1852. //!
  1853. //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
  1854. //!
  1855. //! <b>Throws</b>: If the internal hasher or the equality functor throws. Strong guarantee.
  1856. //!
  1857. //! <b>Note</b>: Does not affect the validity of iterators and references.
  1858. //! No copy-constructors are called.
  1859. std::pair<iterator, bool> insert_unique(reference value)
  1860. {
  1861. insert_commit_data commit_data;
  1862. std::pair<iterator, bool> ret = this->insert_unique_check(key_of_value()(value), commit_data);
  1863. if(ret.second){
  1864. ret.first = this->insert_unique_commit(value, commit_data);
  1865. }
  1866. return ret;
  1867. }
  1868. //! <b>Requires</b>: Dereferencing iterator must yield an lvalue
  1869. //! of type value_type.
  1870. //!
  1871. //! <b>Effects</b>: Equivalent to this->insert_unique(t) for each element in [b, e).
  1872. //!
  1873. //! <b>Complexity</b>: Average case O(N), where N is distance(b, e).
  1874. //! Worst case O(N*this->size()).
  1875. //!
  1876. //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee.
  1877. //!
  1878. //! <b>Note</b>: Does not affect the validity of iterators and references.
  1879. //! No copy-constructors are called.
  1880. template<class Iterator>
  1881. void insert_unique(Iterator b, Iterator e)
  1882. {
  1883. for (; b != e; ++b)
  1884. this->insert_unique(*b);
  1885. }
  1886. //! <b>Requires</b>: "hash_func" must be a hash function that induces
  1887. //! the same hash values as the stored hasher. The difference is that
  1888. //! "hash_func" hashes the given key instead of the value_type.
  1889. //!
  1890. //! "equal_func" must be a equality function that induces
  1891. //! the same equality as key_equal. The difference is that
  1892. //! "equal_func" compares an arbitrary key with the contained values.
  1893. //!
  1894. //! <b>Effects</b>: Checks if a value can be inserted in the unordered_set, using
  1895. //! a user provided key instead of the value itself.
  1896. //!
  1897. //! <b>Returns</b>: If there is an equivalent value
  1898. //! returns a pair containing an iterator to the already present value
  1899. //! and false. If the value can be inserted returns true in the returned
  1900. //! pair boolean and fills "commit_data" that is meant to be used with
  1901. //! the "insert_commit" function.
  1902. //!
  1903. //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
  1904. //!
  1905. //! <b>Throws</b>: If hash_func or equal_func throw. Strong guarantee.
  1906. //!
  1907. //! <b>Notes</b>: This function is used to improve performance when constructing
  1908. //! a value_type is expensive: if there is an equivalent value
  1909. //! the constructed object must be discarded. Many times, the part of the
  1910. //! node that is used to impose the hash or the equality is much cheaper to
  1911. //! construct than the value_type and this function offers the possibility to
  1912. //! use that the part to check if the insertion will be successful.
  1913. //!
  1914. //! If the check is successful, the user can construct the value_type and use
  1915. //! "insert_commit" to insert the object in constant-time.
  1916. //!
  1917. //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
  1918. //! objects are inserted or erased from the unordered_set.
  1919. //!
  1920. //! After a successful rehashing insert_commit_data remains valid.
  1921. template<class KeyType, class KeyHasher, class KeyEqual>
  1922. std::pair<iterator, bool> insert_unique_check
  1923. ( const KeyType &key
  1924. , KeyHasher hash_func
  1925. , KeyEqual equal_func
  1926. , insert_commit_data &commit_data)
  1927. {
  1928. size_type bucket_num;
  1929. siterator prev;
  1930. siterator const pos = this->priv_find(key, hash_func, equal_func, bucket_num, commit_data.hash, prev);
  1931. return std::pair<iterator, bool>
  1932. ( iterator(pos, &this->get_bucket_value_traits())
  1933. , pos == this->priv_invalid_local_it());
  1934. }
  1935. //! <b>Effects</b>: Checks if a value can be inserted in the unordered_set, using
  1936. //! a user provided key instead of the value itself.
  1937. //!
  1938. //! <b>Returns</b>: If there is an equivalent value
  1939. //! returns a pair containing an iterator to the already present value
  1940. //! and false. If the value can be inserted returns true in the returned
  1941. //! pair boolean and fills "commit_data" that is meant to be used with
  1942. //! the "insert_commit" function.
  1943. //!
  1944. //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
  1945. //!
  1946. //! <b>Throws</b>: If hasher or key_compare throw. Strong guarantee.
  1947. //!
  1948. //! <b>Notes</b>: This function is used to improve performance when constructing
  1949. //! a value_type is expensive: if there is an equivalent value
  1950. //! the constructed object must be discarded. Many times, the part of the
  1951. //! node that is used to impose the hash or the equality is much cheaper to
  1952. //! construct than the value_type and this function offers the possibility to
  1953. //! use that the part to check if the insertion will be successful.
  1954. //!
  1955. //! If the check is successful, the user can construct the value_type and use
  1956. //! "insert_commit" to insert the object in constant-time.
  1957. //!
  1958. //! "commit_data" remains valid for a subsequent "insert_commit" only if no more
  1959. //! objects are inserted or erased from the unordered_set.
  1960. //!
  1961. //! After a successful rehashing insert_commit_data remains valid.
  1962. BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator, bool> insert_unique_check
  1963. ( const key_type &key, insert_commit_data &commit_data)
  1964. { return this->insert_unique_check(key, this->priv_hasher(), this->priv_equal(), commit_data); }
  1965. //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data
  1966. //! must have been obtained from a previous call to "insert_check".
  1967. //! No objects should have been inserted or erased from the unordered_set between
  1968. //! the "insert_check" that filled "commit_data" and the call to "insert_commit".
  1969. //!
  1970. //! <b>Effects</b>: Inserts the value in the unordered_set using the information obtained
  1971. //! from the "commit_data" that a previous "insert_check" filled.
  1972. //!
  1973. //! <b>Returns</b>: An iterator to the newly inserted object.
  1974. //!
  1975. //! <b>Complexity</b>: Constant time.
  1976. //!
  1977. //! <b>Throws</b>: Nothing.
  1978. //!
  1979. //! <b>Notes</b>: This function has only sense if a "insert_check" has been
  1980. //! previously executed to fill "commit_data". No value should be inserted or
  1981. //! erased between the "insert_check" and "insert_commit" calls.
  1982. //!
  1983. //! After a successful rehashing insert_commit_data remains valid.
  1984. iterator insert_unique_commit(reference value, const insert_commit_data &commit_data)
  1985. {
  1986. size_type bucket_num = this->priv_hash_to_bucket(commit_data.hash);
  1987. bucket_type &b = this->priv_bucket_pointer()[bucket_num];
  1988. this->priv_size_traits().increment();
  1989. node_ptr const n = pointer_traits<node_ptr>::pointer_to(this->priv_value_to_node(value));
  1990. BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(n));
  1991. node_functions_t::store_hash(n, commit_data.hash, store_hash_t());
  1992. this->priv_insertion_update_cache(bucket_num);
  1993. group_functions_t::insert_in_group(n, n, optimize_multikey_t());
  1994. return iterator(b.insert_after(b.before_begin(), *n), &this->get_bucket_value_traits());
  1995. }
  1996. //! <b>Effects</b>: Erases the element pointed to by i.
  1997. //!
  1998. //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
  1999. //!
  2000. //! <b>Throws</b>: Nothing.
  2001. //!
  2002. //! <b>Note</b>: Invalidates the iterators (but not the references)
  2003. //! to the erased element. No destructors are called.
  2004. BOOST_INTRUSIVE_FORCEINLINE void erase(const_iterator i)
  2005. { this->erase_and_dispose(i, detail::null_disposer()); }
  2006. //! <b>Effects</b>: Erases the range pointed to by b end e.
  2007. //!
  2008. //! <b>Complexity</b>: Average case O(distance(b, e)),
  2009. //! worst case O(this->size()).
  2010. //!
  2011. //! <b>Throws</b>: Nothing.
  2012. //!
  2013. //! <b>Note</b>: Invalidates the iterators (but not the references)
  2014. //! to the erased elements. No destructors are called.
  2015. BOOST_INTRUSIVE_FORCEINLINE void erase(const_iterator b, const_iterator e)
  2016. { this->erase_and_dispose(b, e, detail::null_disposer()); }
  2017. //! <b>Effects</b>: Erases all the elements with the given value.
  2018. //!
  2019. //! <b>Returns</b>: The number of erased elements.
  2020. //!
  2021. //! <b>Complexity</b>: Average case O(this->count(value)).
  2022. //! Worst case O(this->size()).
  2023. //!
  2024. //! <b>Throws</b>: If the internal hasher or the equality functor throws.
  2025. //! Basic guarantee.
  2026. //!
  2027. //! <b>Note</b>: Invalidates the iterators (but not the references)
  2028. //! to the erased elements. No destructors are called.
  2029. BOOST_INTRUSIVE_FORCEINLINE size_type erase(const key_type &key)
  2030. { return this->erase(key, this->priv_hasher(), this->priv_equal()); }
  2031. //! <b>Requires</b>: "hash_func" must be a hash function that induces
  2032. //! the same hash values as the stored hasher. The difference is that
  2033. //! "hash_func" hashes the given key instead of the value_type.
  2034. //!
  2035. //! "equal_func" must be a equality function that induces
  2036. //! the same equality as key_equal. The difference is that
  2037. //! "equal_func" compares an arbitrary key with the contained values.
  2038. //!
  2039. //! <b>Effects</b>: Erases all the elements that have the same hash and
  2040. //! compare equal with the given key.
  2041. //!
  2042. //! <b>Returns</b>: The number of erased elements.
  2043. //!
  2044. //! <b>Complexity</b>: Average case O(this->count(value)).
  2045. //! Worst case O(this->size()).
  2046. //!
  2047. //! <b>Throws</b>: If hash_func or equal_func throw. Basic guarantee.
  2048. //!
  2049. //! <b>Note</b>: Invalidates the iterators (but not the references)
  2050. //! to the erased elements. No destructors are called.
  2051. template<class KeyType, class KeyHasher, class KeyEqual>
  2052. BOOST_INTRUSIVE_FORCEINLINE size_type erase(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func)
  2053. { return this->erase_and_dispose(key, hash_func, equal_func, detail::null_disposer()); }
  2054. //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
  2055. //!
  2056. //! <b>Effects</b>: Erases the element pointed to by i.
  2057. //! Disposer::operator()(pointer) is called for the removed element.
  2058. //!
  2059. //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
  2060. //!
  2061. //! <b>Throws</b>: Nothing.
  2062. //!
  2063. //! <b>Note</b>: Invalidates the iterators
  2064. //! to the erased elements.
  2065. template<class Disposer>
  2066. BOOST_INTRUSIVE_DOC1ST(void
  2067. , typename detail::disable_if_convertible<Disposer BOOST_INTRUSIVE_I const_iterator>::type)
  2068. erase_and_dispose(const_iterator i, Disposer disposer)
  2069. {
  2070. //Get the bucket number and local iterator for both iterators
  2071. siterator const first_local_it(i.slist_it());
  2072. size_type const first_bucket_num = this->priv_get_bucket_num(first_local_it);
  2073. this->priv_erase_node(this->priv_bucket_pointer()[first_bucket_num], first_local_it, make_node_disposer(disposer), optimize_multikey_t());
  2074. this->priv_size_traits().decrement();
  2075. this->priv_erasure_update_cache_range(first_bucket_num, first_bucket_num);
  2076. }
  2077. //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
  2078. //!
  2079. //! <b>Effects</b>: Erases the range pointed to by b end e.
  2080. //! Disposer::operator()(pointer) is called for the removed elements.
  2081. //!
  2082. //! <b>Complexity</b>: Average case O(distance(b, e)),
  2083. //! worst case O(this->size()).
  2084. //!
  2085. //! <b>Throws</b>: Nothing.
  2086. //!
  2087. //! <b>Note</b>: Invalidates the iterators
  2088. //! to the erased elements.
  2089. template<class Disposer>
  2090. void erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer)
  2091. {
  2092. if(b != e){
  2093. //Get the bucket number and local iterator for both iterators
  2094. siterator first_local_it(b.slist_it());
  2095. size_type first_bucket_num = this->priv_get_bucket_num(first_local_it);
  2096. const bucket_ptr buck_ptr = this->priv_bucket_pointer();
  2097. siterator before_first_local_it
  2098. = this->priv_get_previous(buck_ptr[first_bucket_num], first_local_it);
  2099. size_type last_bucket_num;
  2100. siterator last_local_it;
  2101. //For the end iterator, we will assign the end iterator
  2102. //of the last bucket
  2103. if(e == this->end()){
  2104. last_bucket_num = this->bucket_count() - 1;
  2105. last_local_it = buck_ptr[last_bucket_num].end();
  2106. }
  2107. else{
  2108. last_local_it = e.slist_it();
  2109. last_bucket_num = this->priv_get_bucket_num(last_local_it);
  2110. }
  2111. size_type const num_erased = this->priv_erase_node_range
  2112. ( before_first_local_it, first_bucket_num, last_local_it, last_bucket_num
  2113. , make_node_disposer(disposer), optimize_multikey_t());
  2114. this->priv_size_traits().set_size(this->priv_size_traits().get_size()-num_erased);
  2115. this->priv_erasure_update_cache_range(first_bucket_num, last_bucket_num);
  2116. }
  2117. }
  2118. //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
  2119. //!
  2120. //! <b>Effects</b>: Erases all the elements with the given value.
  2121. //! Disposer::operator()(pointer) is called for the removed elements.
  2122. //!
  2123. //! <b>Returns</b>: The number of erased elements.
  2124. //!
  2125. //! <b>Complexity</b>: Average case O(this->count(value)).
  2126. //! Worst case O(this->size()).
  2127. //!
  2128. //! <b>Throws</b>: If the internal hasher or the equality functor throws.
  2129. //! Basic guarantee.
  2130. //!
  2131. //! <b>Note</b>: Invalidates the iterators (but not the references)
  2132. //! to the erased elements. No destructors are called.
  2133. template<class Disposer>
  2134. BOOST_INTRUSIVE_FORCEINLINE size_type erase_and_dispose(const key_type &key, Disposer disposer)
  2135. { return this->erase_and_dispose(key, this->priv_hasher(), this->priv_equal(), disposer); }
  2136. //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
  2137. //!
  2138. //! <b>Effects</b>: Erases all the elements with the given key.
  2139. //! according to the comparison functor "equal_func".
  2140. //! Disposer::operator()(pointer) is called for the removed elements.
  2141. //!
  2142. //! <b>Returns</b>: The number of erased elements.
  2143. //!
  2144. //! <b>Complexity</b>: Average case O(this->count(value)).
  2145. //! Worst case O(this->size()).
  2146. //!
  2147. //! <b>Throws</b>: If hash_func or equal_func throw. Basic guarantee.
  2148. //!
  2149. //! <b>Note</b>: Invalidates the iterators
  2150. //! to the erased elements.
  2151. template<class KeyType, class KeyHasher, class KeyEqual, class Disposer>
  2152. size_type erase_and_dispose(const KeyType& key, KeyHasher hash_func
  2153. ,KeyEqual equal_func, Disposer disposer)
  2154. {
  2155. size_type bucket_num;
  2156. std::size_t h;
  2157. siterator prev;
  2158. siterator it = this->priv_find(key, hash_func, equal_func, bucket_num, h, prev);
  2159. bool const success = it != this->priv_invalid_local_it();
  2160. size_type cnt(0);
  2161. if(success){
  2162. if(optimize_multikey){
  2163. cnt = this->priv_erase_from_single_bucket
  2164. (this->priv_bucket_pointer()[bucket_num], prev, ++(priv_last_in_group)(it), make_node_disposer(disposer), optimize_multikey_t());
  2165. }
  2166. else{
  2167. bucket_type &b = this->priv_bucket_pointer()[bucket_num];
  2168. siterator const end_sit = b.end();
  2169. do{
  2170. ++cnt;
  2171. ++it;
  2172. }while(it != end_sit &&
  2173. this->priv_is_value_equal_to_key
  2174. (this->priv_value_from_slist_node(it.pointed_node()), h, key, equal_func));
  2175. bucket_type::s_erase_after_and_dispose(prev, it, make_node_disposer(disposer));
  2176. }
  2177. this->priv_size_traits().set_size(this->priv_size_traits().get_size()-cnt);
  2178. this->priv_erasure_update_cache();
  2179. }
  2180. return cnt;
  2181. }
  2182. //! <b>Effects</b>: Erases all of the elements.
  2183. //!
  2184. //! <b>Complexity</b>: Linear to the number of elements on the container.
  2185. //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise.
  2186. //!
  2187. //! <b>Throws</b>: Nothing.
  2188. //!
  2189. //! <b>Note</b>: Invalidates the iterators (but not the references)
  2190. //! to the erased elements. No destructors are called.
  2191. void clear()
  2192. {
  2193. this->priv_clear_buckets_and_cache();
  2194. this->priv_size_traits().set_size(size_type(0));
  2195. }
  2196. //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw.
  2197. //!
  2198. //! <b>Effects</b>: Erases all of the elements.
  2199. //!
  2200. //! <b>Complexity</b>: Linear to the number of elements on the container.
  2201. //! Disposer::operator()(pointer) is called for the removed elements.
  2202. //!
  2203. //! <b>Throws</b>: Nothing.
  2204. //!
  2205. //! <b>Note</b>: Invalidates the iterators (but not the references)
  2206. //! to the erased elements. No destructors are called.
  2207. template<class Disposer>
  2208. void clear_and_dispose(Disposer disposer)
  2209. {
  2210. if(!constant_time_size || !this->empty()){
  2211. size_type num_buckets = this->bucket_count();
  2212. bucket_ptr b = this->priv_bucket_pointer();
  2213. typename typeof_node_disposer<Disposer>::type d(disposer, &this->priv_value_traits());
  2214. for(; num_buckets--; ++b){
  2215. b->clear_and_dispose(d);
  2216. }
  2217. this->priv_size_traits().set_size(size_type(0));
  2218. }
  2219. this->priv_initialize_cache();
  2220. }
  2221. //! <b>Effects</b>: Returns the number of contained elements with the given value
  2222. //!
  2223. //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
  2224. //!
  2225. //! <b>Throws</b>: If the internal hasher or the equality functor throws.
  2226. BOOST_INTRUSIVE_FORCEINLINE size_type count(const key_type &key) const
  2227. { return this->count(key, this->priv_hasher(), this->priv_equal()); }
  2228. //! <b>Requires</b>: "hash_func" must be a hash function that induces
  2229. //! the same hash values as the stored hasher. The difference is that
  2230. //! "hash_func" hashes the given key instead of the value_type.
  2231. //!
  2232. //! "equal_func" must be a equality function that induces
  2233. //! the same equality as key_equal. The difference is that
  2234. //! "equal_func" compares an arbitrary key with the contained values.
  2235. //!
  2236. //! <b>Effects</b>: Returns the number of contained elements with the given key
  2237. //!
  2238. //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
  2239. //!
  2240. //! <b>Throws</b>: If hash_func or equal throw.
  2241. template<class KeyType, class KeyHasher, class KeyEqual>
  2242. size_type count(const KeyType &key, KeyHasher hash_func, KeyEqual equal_func) const
  2243. {
  2244. size_type cnt;
  2245. size_type n_bucket;
  2246. this->priv_local_equal_range(key, hash_func, equal_func, n_bucket, cnt);
  2247. return cnt;
  2248. }
  2249. //! <b>Effects</b>: Finds an iterator to the first element is equal to
  2250. //! "value" or end() if that element does not exist.
  2251. //!
  2252. //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
  2253. //!
  2254. //! <b>Throws</b>: If the internal hasher or the equality functor throws.
  2255. BOOST_INTRUSIVE_FORCEINLINE iterator find(const key_type &key)
  2256. { return this->find(key, this->priv_hasher(), this->priv_equal()); }
  2257. //! <b>Requires</b>: "hash_func" must be a hash function that induces
  2258. //! the same hash values as the stored hasher. The difference is that
  2259. //! "hash_func" hashes the given key instead of the value_type.
  2260. //!
  2261. //! "equal_func" must be a equality function that induces
  2262. //! the same equality as key_equal. The difference is that
  2263. //! "equal_func" compares an arbitrary key with the contained values.
  2264. //!
  2265. //! <b>Effects</b>: Finds an iterator to the first element whose key is
  2266. //! "key" according to the given hash and equality functor or end() if
  2267. //! that element does not exist.
  2268. //!
  2269. //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
  2270. //!
  2271. //! <b>Throws</b>: If hash_func or equal_func throw.
  2272. //!
  2273. //! <b>Note</b>: This function is used when constructing a value_type
  2274. //! is expensive and the value_type can be compared with a cheaper
  2275. //! key type. Usually this key is part of the value_type.
  2276. template<class KeyType, class KeyHasher, class KeyEqual>
  2277. iterator find(const KeyType &key, KeyHasher hash_func, KeyEqual equal_func)
  2278. {
  2279. size_type bucket_n;
  2280. std::size_t hash;
  2281. siterator prev;
  2282. return iterator( this->priv_find(key, hash_func, equal_func, bucket_n, hash, prev)
  2283. , &this->get_bucket_value_traits());
  2284. }
  2285. //! <b>Effects</b>: Finds a const_iterator to the first element whose key is
  2286. //! "key" or end() if that element does not exist.
  2287. //!
  2288. //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
  2289. //!
  2290. //! <b>Throws</b>: If the internal hasher or the equality functor throws.
  2291. BOOST_INTRUSIVE_FORCEINLINE const_iterator find(const key_type &key) const
  2292. { return this->find(key, this->priv_hasher(), this->priv_equal()); }
  2293. //! <b>Requires</b>: "hash_func" must be a hash function that induces
  2294. //! the same hash values as the stored hasher. The difference is that
  2295. //! "hash_func" hashes the given key instead of the value_type.
  2296. //!
  2297. //! "equal_func" must be a equality function that induces
  2298. //! the same equality as key_equal. The difference is that
  2299. //! "equal_func" compares an arbitrary key with the contained values.
  2300. //!
  2301. //! <b>Effects</b>: Finds an iterator to the first element whose key is
  2302. //! "key" according to the given hasher and equality functor or end() if
  2303. //! that element does not exist.
  2304. //!
  2305. //! <b>Complexity</b>: Average case O(1), worst case O(this->size()).
  2306. //!
  2307. //! <b>Throws</b>: If hash_func or equal_func throw.
  2308. //!
  2309. //! <b>Note</b>: This function is used when constructing a value_type
  2310. //! is expensive and the value_type can be compared with a cheaper
  2311. //! key type. Usually this key is part of the value_type.
  2312. template<class KeyType, class KeyHasher, class KeyEqual>
  2313. const_iterator find
  2314. (const KeyType &key, KeyHasher hash_func, KeyEqual equal_func) const
  2315. {
  2316. size_type bucket_n;
  2317. std::size_t hash_value;
  2318. siterator prev;
  2319. return const_iterator( this->priv_find(key, hash_func, equal_func, bucket_n, hash_value, prev)
  2320. , &this->get_bucket_value_traits());
  2321. }
  2322. //! <b>Effects</b>: Returns a range containing all elements with values equivalent
  2323. //! to value. Returns std::make_pair(this->end(), this->end()) if no such
  2324. //! elements exist.
  2325. //!
  2326. //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).
  2327. //!
  2328. //! <b>Throws</b>: If the internal hasher or the equality functor throws.
  2329. BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type &key)
  2330. { return this->equal_range(key, this->priv_hasher(), this->priv_equal()); }
  2331. //! <b>Requires</b>: "hash_func" must be a hash function that induces
  2332. //! the same hash values as the stored hasher. The difference is that
  2333. //! "hash_func" hashes the given key instead of the value_type.
  2334. //!
  2335. //! "equal_func" must be a equality function that induces
  2336. //! the same equality as key_equal. The difference is that
  2337. //! "equal_func" compares an arbitrary key with the contained values.
  2338. //!
  2339. //! <b>Effects</b>: Returns a range containing all elements with equivalent
  2340. //! keys. Returns std::make_pair(this->end(), this->end()) if no such
  2341. //! elements exist.
  2342. //!
  2343. //! <b>Complexity</b>: Average case O(this->count(key, hash_func, equal_func)).
  2344. //! Worst case O(this->size()).
  2345. //!
  2346. //! <b>Throws</b>: If hash_func or the equal_func throw.
  2347. //!
  2348. //! <b>Note</b>: This function is used when constructing a value_type
  2349. //! is expensive and the value_type can be compared with a cheaper
  2350. //! key type. Usually this key is part of the value_type.
  2351. template<class KeyType, class KeyHasher, class KeyEqual>
  2352. std::pair<iterator,iterator> equal_range
  2353. (const KeyType &key, KeyHasher hash_func, KeyEqual equal_func)
  2354. {
  2355. std::pair<siterator, siterator> ret =
  2356. this->priv_equal_range(key, hash_func, equal_func);
  2357. return std::pair<iterator, iterator>
  2358. ( iterator(ret.first, &this->get_bucket_value_traits())
  2359. , iterator(ret.second, &this->get_bucket_value_traits()));
  2360. }
  2361. //! <b>Effects</b>: Returns a range containing all elements with values equivalent
  2362. //! to value. Returns std::make_pair(this->end(), this->end()) if no such
  2363. //! elements exist.
  2364. //!
  2365. //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()).
  2366. //!
  2367. //! <b>Throws</b>: If the internal hasher or the equality functor throws.
  2368. BOOST_INTRUSIVE_FORCEINLINE std::pair<const_iterator, const_iterator>
  2369. equal_range(const key_type &key) const
  2370. { return this->equal_range(key, this->priv_hasher(), this->priv_equal()); }
  2371. //! <b>Requires</b>: "hash_func" must be a hash function that induces
  2372. //! the same hash values as the stored hasher. The difference is that
  2373. //! "hash_func" hashes the given key instead of the value_type.
  2374. //!
  2375. //! "equal_func" must be a equality function that induces
  2376. //! the same equality as key_equal. The difference is that
  2377. //! "equal_func" compares an arbitrary key with the contained values.
  2378. //!
  2379. //! <b>Effects</b>: Returns a range containing all elements with equivalent
  2380. //! keys. Returns std::make_pair(this->end(), this->end()) if no such
  2381. //! elements exist.
  2382. //!
  2383. //! <b>Complexity</b>: Average case O(this->count(key, hash_func, equal_func)).
  2384. //! Worst case O(this->size()).
  2385. //!
  2386. //! <b>Throws</b>: If the hasher or equal_func throw.
  2387. //!
  2388. //! <b>Note</b>: This function is used when constructing a value_type
  2389. //! is expensive and the value_type can be compared with a cheaper
  2390. //! key type. Usually this key is part of the value_type.
  2391. template<class KeyType, class KeyHasher, class KeyEqual>
  2392. std::pair<const_iterator,const_iterator> equal_range
  2393. (const KeyType &key, KeyHasher hash_func, KeyEqual equal_func) const
  2394. {
  2395. std::pair<siterator, siterator> ret =
  2396. this->priv_equal_range(key, hash_func, equal_func);
  2397. return std::pair<const_iterator, const_iterator>
  2398. ( const_iterator(ret.first, &this->get_bucket_value_traits())
  2399. , const_iterator(ret.second, &this->get_bucket_value_traits()));
  2400. }
  2401. #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  2402. //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
  2403. //! appropriate type. Otherwise the behavior is undefined.
  2404. //!
  2405. //! <b>Effects</b>: Returns: a valid iterator belonging to the unordered_set
  2406. //! that points to the value
  2407. //!
  2408. //! <b>Complexity</b>: Constant.
  2409. //!
  2410. //! <b>Throws</b>: If the internal hash function throws.
  2411. iterator iterator_to(reference value);
  2412. //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
  2413. //! appropriate type. Otherwise the behavior is undefined.
  2414. //!
  2415. //! <b>Effects</b>: Returns: a valid const_iterator belonging to the
  2416. //! unordered_set that points to the value
  2417. //!
  2418. //! <b>Complexity</b>: Constant.
  2419. //!
  2420. //! <b>Throws</b>: If the internal hash function throws.
  2421. const_iterator iterator_to(const_reference value) const;
  2422. //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
  2423. //! appropriate type. Otherwise the behavior is undefined.
  2424. //!
  2425. //! <b>Effects</b>: Returns: a valid local_iterator belonging to the unordered_set
  2426. //! that points to the value
  2427. //!
  2428. //! <b>Complexity</b>: Constant.
  2429. //!
  2430. //! <b>Throws</b>: Nothing.
  2431. //!
  2432. //! <b>Note</b>: This static function is available only if the <i>value traits</i>
  2433. //! is stateless.
  2434. static local_iterator s_local_iterator_to(reference value);
  2435. //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
  2436. //! appropriate type. Otherwise the behavior is undefined.
  2437. //!
  2438. //! <b>Effects</b>: Returns: a valid const_local_iterator belonging to
  2439. //! the unordered_set that points to the value
  2440. //!
  2441. //! <b>Complexity</b>: Constant.
  2442. //!
  2443. //! <b>Throws</b>: Nothing.
  2444. //!
  2445. //! <b>Note</b>: This static function is available only if the <i>value traits</i>
  2446. //! is stateless.
  2447. static const_local_iterator s_local_iterator_to(const_reference value);
  2448. //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
  2449. //! appropriate type. Otherwise the behavior is undefined.
  2450. //!
  2451. //! <b>Effects</b>: Returns: a valid local_iterator belonging to the unordered_set
  2452. //! that points to the value
  2453. //!
  2454. //! <b>Complexity</b>: Constant.
  2455. //!
  2456. //! <b>Throws</b>: Nothing.
  2457. local_iterator local_iterator_to(reference value);
  2458. //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of
  2459. //! appropriate type. Otherwise the behavior is undefined.
  2460. //!
  2461. //! <b>Effects</b>: Returns: a valid const_local_iterator belonging to
  2462. //! the unordered_set that points to the value
  2463. //!
  2464. //! <b>Complexity</b>: Constant.
  2465. //!
  2466. //! <b>Throws</b>: Nothing.
  2467. const_local_iterator local_iterator_to(const_reference value) const;
  2468. //! <b>Effects</b>: Returns the number of buckets passed in the constructor
  2469. //! or the last rehash function.
  2470. //!
  2471. //! <b>Complexity</b>: Constant.
  2472. //!
  2473. //! <b>Throws</b>: Nothing.
  2474. size_type bucket_count() const;
  2475. //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
  2476. //!
  2477. //! <b>Effects</b>: Returns the number of elements in the nth bucket.
  2478. //!
  2479. //! <b>Complexity</b>: Constant.
  2480. //!
  2481. //! <b>Throws</b>: Nothing.
  2482. size_type bucket_size(size_type n) const;
  2483. #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  2484. //! <b>Effects</b>: Returns the index of the bucket in which elements
  2485. //! with keys equivalent to k would be found, if any such element existed.
  2486. //!
  2487. //! <b>Complexity</b>: Constant.
  2488. //!
  2489. //! <b>Throws</b>: If the hash functor throws.
  2490. //!
  2491. //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
  2492. BOOST_INTRUSIVE_FORCEINLINE size_type bucket(const key_type& k) const
  2493. { return this->bucket(k, this->priv_hasher()); }
  2494. //! <b>Requires</b>: "hash_func" must be a hash function that induces
  2495. //! the same hash values as the stored hasher. The difference is that
  2496. //! "hash_func" hashes the given key instead of the value_type.
  2497. //!
  2498. //! <b>Effects</b>: Returns the index of the bucket in which elements
  2499. //! with keys equivalent to k would be found, if any such element existed.
  2500. //!
  2501. //! <b>Complexity</b>: Constant.
  2502. //!
  2503. //! <b>Throws</b>: If hash_func throws.
  2504. //!
  2505. //! <b>Note</b>: the return value is in the range [0, this->bucket_count()).
  2506. template<class KeyType, class KeyHasher>
  2507. BOOST_INTRUSIVE_FORCEINLINE size_type bucket(const KeyType& k, KeyHasher hash_func) const
  2508. { return this->priv_hash_to_bucket(hash_func(k)); }
  2509. #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  2510. //! <b>Effects</b>: Returns the bucket array pointer passed in the constructor
  2511. //! or the last rehash function.
  2512. //!
  2513. //! <b>Complexity</b>: Constant.
  2514. //!
  2515. //! <b>Throws</b>: Nothing.
  2516. bucket_ptr bucket_pointer() const;
  2517. //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
  2518. //!
  2519. //! <b>Effects</b>: Returns a local_iterator pointing to the beginning
  2520. //! of the sequence stored in the bucket n.
  2521. //!
  2522. //! <b>Complexity</b>: Constant.
  2523. //!
  2524. //! <b>Throws</b>: Nothing.
  2525. //!
  2526. //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
  2527. //! containing all of the elements in the nth bucket.
  2528. local_iterator begin(size_type n);
  2529. //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
  2530. //!
  2531. //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning
  2532. //! of the sequence stored in the bucket n.
  2533. //!
  2534. //! <b>Complexity</b>: Constant.
  2535. //!
  2536. //! <b>Throws</b>: Nothing.
  2537. //!
  2538. //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
  2539. //! containing all of the elements in the nth bucket.
  2540. const_local_iterator begin(size_type n) const;
  2541. //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
  2542. //!
  2543. //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning
  2544. //! of the sequence stored in the bucket n.
  2545. //!
  2546. //! <b>Complexity</b>: Constant.
  2547. //!
  2548. //! <b>Throws</b>: Nothing.
  2549. //!
  2550. //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
  2551. //! containing all of the elements in the nth bucket.
  2552. const_local_iterator cbegin(size_type n) const;
  2553. //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
  2554. //!
  2555. //! <b>Effects</b>: Returns a local_iterator pointing to the end
  2556. //! of the sequence stored in the bucket n.
  2557. //!
  2558. //! <b>Complexity</b>: Constant.
  2559. //!
  2560. //! <b>Throws</b>: Nothing.
  2561. //!
  2562. //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
  2563. //! containing all of the elements in the nth bucket.
  2564. local_iterator end(size_type n);
  2565. //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
  2566. //!
  2567. //! <b>Effects</b>: Returns a const_local_iterator pointing to the end
  2568. //! of the sequence stored in the bucket n.
  2569. //!
  2570. //! <b>Complexity</b>: Constant.
  2571. //!
  2572. //! <b>Throws</b>: Nothing.
  2573. //!
  2574. //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
  2575. //! containing all of the elements in the nth bucket.
  2576. const_local_iterator end(size_type n) const;
  2577. //! <b>Requires</b>: n is in the range [0, this->bucket_count()).
  2578. //!
  2579. //! <b>Effects</b>: Returns a const_local_iterator pointing to the end
  2580. //! of the sequence stored in the bucket n.
  2581. //!
  2582. //! <b>Complexity</b>: Constant.
  2583. //!
  2584. //! <b>Throws</b>: Nothing.
  2585. //!
  2586. //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range
  2587. //! containing all of the elements in the nth bucket.
  2588. const_local_iterator cend(size_type n) const;
  2589. #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  2590. //! <b>Requires</b>: new_bucket_traits can hold a pointer to a new bucket array
  2591. //! or the same as the old bucket array with a different length. new_size is the length of the
  2592. //! the array pointed by new_buckets. If new_bucket_traits.bucket_begin() == this->bucket_pointer()
  2593. //! new_bucket_traits.bucket_count() can be bigger or smaller than this->bucket_count().
  2594. //! 'new_bucket_traits' copy constructor should not throw.
  2595. //!
  2596. //! <b>Effects</b>:
  2597. //! If `new_bucket_traits.bucket_begin() == this->bucket_pointer()` is false,
  2598. //! unlinks values from the old bucket and inserts then in the new one according
  2599. //! to the hash value of values.
  2600. //!
  2601. //! If `new_bucket_traits.bucket_begin() == this->bucket_pointer()` is true,
  2602. //! the implementations avoids moving values as much as possible.
  2603. //!
  2604. //! Bucket traits hold by *this is assigned from new_bucket_traits.
  2605. //! If the container is configured as incremental<>, the split bucket is set
  2606. //! to the new bucket_count().
  2607. //!
  2608. //! If store_hash option is true, this method does not use the hash function.
  2609. //! If false, the implementation tries to minimize calls to the hash function
  2610. //! (e.g. once for equivalent values if optimize_multikey<true> is true).
  2611. //!
  2612. //! If rehash is successful updates the internal bucket_traits with new_bucket_traits.
  2613. //!
  2614. //! <b>Complexity</b>: Average case linear in this->size(), worst case quadratic.
  2615. //!
  2616. //! <b>Throws</b>: If the hasher functor throws. Basic guarantee.
  2617. BOOST_INTRUSIVE_FORCEINLINE void rehash(const bucket_traits &new_bucket_traits)
  2618. { this->rehash_impl(new_bucket_traits, false); }
  2619. //! <b>Note</b>: This function is used when keys from inserted elements are changed
  2620. //! (e.g. a language change when key is a string) but uniqueness and hash properties are
  2621. //! preserved so a fast full rehash recovers invariants for *this without extracting and
  2622. //! reinserting all elements again.
  2623. //!
  2624. //! <b>Requires</b>: Calls produced to the hash function should not alter the value uniqueness
  2625. //! properties of already inserted elements. If hasher(key1) == hasher(key2) was true when
  2626. //! elements were inserted, it shall be true during calls produced in the execution of this function.
  2627. //!
  2628. //! key_equal is not called inside this function so it is assumed that key_equal(value1, value2)
  2629. //! should produce the same results as before for inserted elements.
  2630. //!
  2631. //! <b>Effects</b>: Reprocesses all values hold by *this, recalculating their hash values
  2632. //! and redistributing them though the buckets.
  2633. //!
  2634. //! If store_hash option is true, this method uses the hash function and updates the stored hash value.
  2635. //!
  2636. //! <b>Complexity</b>: Average case linear in this->size(), worst case quadratic.
  2637. //!
  2638. //! <b>Throws</b>: If the hasher functor throws. Basic guarantee.
  2639. BOOST_INTRUSIVE_FORCEINLINE void full_rehash()
  2640. { this->rehash_impl(this->priv_bucket_traits(), true); }
  2641. //! <b>Requires</b>:
  2642. //!
  2643. //! <b>Effects</b>:
  2644. //!
  2645. //! <b>Complexity</b>:
  2646. //!
  2647. //! <b>Throws</b>:
  2648. //!
  2649. //! <b>Note</b>: this method is only available if incremental<true> option is activated.
  2650. bool incremental_rehash(bool grow = true)
  2651. {
  2652. //This function is only available for containers with incremental hashing
  2653. BOOST_STATIC_ASSERT(( incremental && power_2_buckets ));
  2654. const size_type split_idx = this->priv_split_traits().get_size();
  2655. const size_type bucket_cnt = this->bucket_count();
  2656. const bucket_ptr buck_ptr = this->priv_bucket_pointer();
  2657. bool ret = false;
  2658. if(grow){
  2659. //Test if the split variable can be changed
  2660. if((ret = split_idx < bucket_cnt)){
  2661. const size_type bucket_to_rehash = split_idx - bucket_cnt/2;
  2662. bucket_type &old_bucket = buck_ptr[bucket_to_rehash];
  2663. this->priv_split_traits().increment();
  2664. //Anti-exception stuff: if an exception is thrown while
  2665. //moving elements from old_bucket to the target bucket, all moved
  2666. //elements are moved back to the original one.
  2667. detail::incremental_rehash_rollback<bucket_type, split_traits> rollback
  2668. ( buck_ptr[split_idx], old_bucket, this->priv_split_traits());
  2669. for( siterator before_i(old_bucket.before_begin()), i(old_bucket.begin()), end_sit(old_bucket.end())
  2670. ; i != end_sit; i = before_i, ++i){
  2671. const value_type &v = this->priv_value_from_slist_node(i.pointed_node());
  2672. const std::size_t hash_value = this->priv_stored_or_compute_hash(v, store_hash_t());
  2673. const size_type new_n = this->priv_hash_to_bucket(hash_value);
  2674. siterator const last = (priv_last_in_group)(i);
  2675. if(new_n == bucket_to_rehash){
  2676. before_i = last;
  2677. }
  2678. else{
  2679. bucket_type &new_b = buck_ptr[new_n];
  2680. new_b.splice_after(new_b.before_begin(), old_bucket, before_i, last);
  2681. }
  2682. }
  2683. rollback.release();
  2684. this->priv_erasure_update_cache();
  2685. }
  2686. }
  2687. else if((ret = split_idx > bucket_cnt/2)){ //!grow
  2688. const size_type target_bucket_num = split_idx - 1 - bucket_cnt/2;
  2689. bucket_type &target_bucket = buck_ptr[target_bucket_num];
  2690. bucket_type &source_bucket = buck_ptr[split_idx-1];
  2691. target_bucket.splice_after(target_bucket.cbefore_begin(), source_bucket);
  2692. this->priv_split_traits().decrement();
  2693. this->priv_insertion_update_cache(target_bucket_num);
  2694. }
  2695. return ret;
  2696. }
  2697. //! <b>Effects</b>: If new_bucket_traits.bucket_count() is not
  2698. //! this->bucket_count()/2 or this->bucket_count()*2, or
  2699. //! this->split_bucket() != new_bucket_traits.bucket_count() returns false
  2700. //! and does nothing.
  2701. //!
  2702. //! Otherwise, copy assigns new_bucket_traits to the internal bucket_traits
  2703. //! and transfers all the objects from old buckets to the new ones.
  2704. //!
  2705. //! <b>Complexity</b>: Linear to size().
  2706. //!
  2707. //! <b>Throws</b>: Nothing
  2708. //!
  2709. //! <b>Note</b>: this method is only available if incremental<true> option is activated.
  2710. bool incremental_rehash(const bucket_traits &new_bucket_traits)
  2711. {
  2712. //This function is only available for containers with incremental hashing
  2713. BOOST_STATIC_ASSERT(( incremental && power_2_buckets ));
  2714. size_type const new_bucket_traits_size = new_bucket_traits.bucket_count();
  2715. size_type const cur_bucket_traits = this->bucket_count();
  2716. const size_type split_idx = this->split_count();
  2717. //Test new bucket size is consistent with internal bucket size and split count
  2718. if(new_bucket_traits_size/2 == cur_bucket_traits){
  2719. if(!(split_idx >= cur_bucket_traits))
  2720. return false;
  2721. }
  2722. else if(new_bucket_traits_size == cur_bucket_traits/2){
  2723. if(!(split_idx <= new_bucket_traits_size))
  2724. return false;
  2725. }
  2726. else{
  2727. return false;
  2728. }
  2729. const size_type ini_n = this->priv_get_cache_bucket_num();
  2730. const bucket_ptr old_buckets = this->priv_bucket_pointer();
  2731. this->priv_bucket_traits() = new_bucket_traits;
  2732. if(new_bucket_traits.bucket_begin() != old_buckets){
  2733. for(size_type n = ini_n; n < split_idx; ++n){
  2734. bucket_type &new_bucket = new_bucket_traits.bucket_begin()[n];
  2735. bucket_type &old_bucket = old_buckets[n];
  2736. new_bucket.splice_after(new_bucket.cbefore_begin(), old_bucket);
  2737. }
  2738. //Put cache to safe position
  2739. this->priv_initialize_cache();
  2740. this->priv_insertion_update_cache(ini_n);
  2741. }
  2742. return true;
  2743. }
  2744. #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  2745. //! <b>Requires</b>: incremental<> option must be set
  2746. //!
  2747. //! <b>Effects</b>: returns the current split count
  2748. //!
  2749. //! <b>Complexity</b>: Constant
  2750. //!
  2751. //! <b>Throws</b>: Nothing
  2752. size_type split_count() const;
  2753. //! <b>Effects</b>: Returns the nearest new bucket count optimized for
  2754. //! the container that is bigger or equal than n. This suggestion can be
  2755. //! used to create bucket arrays with a size that will usually improve
  2756. //! container's performance. If such value does not exist, the
  2757. //! higher possible value is returned.
  2758. //!
  2759. //! <b>Complexity</b>: Amortized constant time.
  2760. //!
  2761. //! <b>Throws</b>: Nothing.
  2762. static size_type suggested_upper_bucket_count(size_type n);
  2763. //! <b>Effects</b>: Returns the nearest new bucket count optimized for
  2764. //! the container that is smaller or equal than n. This suggestion can be
  2765. //! used to create bucket arrays with a size that will usually improve
  2766. //! container's performance. If such value does not exist, the
  2767. //! lowest possible value is returned.
  2768. //!
  2769. //! <b>Complexity</b>: Amortized constant time.
  2770. //!
  2771. //! <b>Throws</b>: Nothing.
  2772. static size_type suggested_lower_bucket_count(size_type n);
  2773. #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  2774. friend bool operator==(const hashtable_impl &x, const hashtable_impl &y)
  2775. {
  2776. //Taken from N3068
  2777. if(constant_time_size && x.size() != y.size()){
  2778. return false;
  2779. }
  2780. for (const_iterator ix = x.cbegin(), ex = x.cend(); ix != ex; ++ix){
  2781. std::pair<const_iterator, const_iterator> eqx(x.equal_range(key_of_value()(*ix))),
  2782. eqy(y.equal_range(key_of_value()(*ix)));
  2783. if (boost::intrusive::iterator_distance(eqx.first, eqx.second) !=
  2784. boost::intrusive::iterator_distance(eqy.first, eqy.second) ||
  2785. !(priv_algo_is_permutation)(eqx.first, eqx.second, eqy.first) ){
  2786. return false;
  2787. }
  2788. ix = eqx.second;
  2789. }
  2790. return true;
  2791. }
  2792. friend bool operator!=(const hashtable_impl &x, const hashtable_impl &y)
  2793. { return !(x == y); }
  2794. friend bool operator<(const hashtable_impl &x, const hashtable_impl &y)
  2795. { return ::boost::intrusive::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); }
  2796. friend bool operator>(const hashtable_impl &x, const hashtable_impl &y)
  2797. { return y < x; }
  2798. friend bool operator<=(const hashtable_impl &x, const hashtable_impl &y)
  2799. { return !(y < x); }
  2800. friend bool operator>=(const hashtable_impl &x, const hashtable_impl &y)
  2801. { return !(x < y); }
  2802. /// @cond
  2803. BOOST_INTRUSIVE_FORCEINLINE void check() const {}
  2804. private:
  2805. void rehash_impl(const bucket_traits &new_bucket_traits, bool do_full_rehash)
  2806. {
  2807. const bucket_ptr new_buckets = new_bucket_traits.bucket_begin();
  2808. size_type new_bucket_count = new_bucket_traits.bucket_count();
  2809. const bucket_ptr old_buckets = this->priv_bucket_pointer();
  2810. size_type old_bucket_count = this->bucket_count();
  2811. //Check power of two bucket array if the option is activated
  2812. BOOST_INTRUSIVE_INVARIANT_ASSERT
  2813. (!power_2_buckets || (0 == (new_bucket_count & (new_bucket_count-1u))));
  2814. size_type n = this->priv_get_cache_bucket_num();
  2815. const bool same_buffer = old_buckets == new_buckets;
  2816. //If the new bucket length is a common factor
  2817. //of the old one we can avoid hash calculations.
  2818. const bool fast_shrink = (!do_full_rehash) && (!incremental) && (old_bucket_count >= new_bucket_count) &&
  2819. (power_2_buckets || (old_bucket_count % new_bucket_count) == 0);
  2820. //If we are shrinking the same bucket array and it's
  2821. //is a fast shrink, just rehash the last nodes
  2822. size_type new_first_bucket_num = new_bucket_count;
  2823. if(same_buffer && fast_shrink && (n < new_bucket_count)){
  2824. new_first_bucket_num = n;
  2825. n = new_bucket_count;
  2826. }
  2827. //Anti-exception stuff: they destroy the elements if something goes wrong.
  2828. //If the source and destination buckets are the same, the second rollback function
  2829. //is harmless, because all elements have been already unlinked and destroyed
  2830. typedef detail::init_disposer<node_algorithms> NodeDisposer;
  2831. typedef detail::exception_array_disposer<bucket_type, NodeDisposer, size_type> ArrayDisposer;
  2832. NodeDisposer node_disp;
  2833. ArrayDisposer rollback1(new_buckets[0], node_disp, new_bucket_count);
  2834. ArrayDisposer rollback2(old_buckets[0], node_disp, old_bucket_count);
  2835. //Put size in a safe value for rollback exception
  2836. size_type const size_backup = this->priv_size_traits().get_size();
  2837. this->priv_size_traits().set_size(0);
  2838. //Put cache to safe position
  2839. this->priv_initialize_cache();
  2840. this->priv_insertion_update_cache(size_type(0u));
  2841. //Iterate through nodes
  2842. for(; n < old_bucket_count; ++n){
  2843. bucket_type &old_bucket = old_buckets[n];
  2844. if(!fast_shrink){
  2845. for( siterator before_i(old_bucket.before_begin()), i(old_bucket.begin()), end_sit(old_bucket.end())
  2846. ; i != end_sit
  2847. ; i = before_i, ++i){
  2848. //First obtain hash value (and store it if do_full_rehash)
  2849. std::size_t hash_value;
  2850. if(do_full_rehash){
  2851. value_type &v = this->priv_value_from_slist_node(i.pointed_node());
  2852. hash_value = this->priv_hasher()(key_of_value()(v));
  2853. node_functions_t::store_hash(pointer_traits<node_ptr>::pointer_to(this->priv_value_to_node(v)), hash_value, store_hash_t());
  2854. }
  2855. else{
  2856. const value_type &v = this->priv_value_from_slist_node(i.pointed_node());
  2857. hash_value = this->priv_stored_or_compute_hash(v, store_hash_t());
  2858. }
  2859. //Now calculate the new bucket position
  2860. const size_type new_n = detail::hash_to_bucket_split<power_2_buckets, incremental>
  2861. (hash_value, new_bucket_count, new_bucket_count);
  2862. //Update first used bucket cache
  2863. if(cache_begin && new_n < new_first_bucket_num)
  2864. new_first_bucket_num = new_n;
  2865. //If the target bucket is new, transfer the whole group
  2866. siterator const last = (priv_last_in_group)(i);
  2867. if(same_buffer && new_n == n){
  2868. before_i = last;
  2869. }
  2870. else{
  2871. bucket_type &new_b = new_buckets[new_n];
  2872. new_b.splice_after(new_b.before_begin(), old_bucket, before_i, last);
  2873. }
  2874. }
  2875. }
  2876. else{
  2877. const size_type new_n = detail::hash_to_bucket_split<power_2_buckets, incremental>(n, new_bucket_count, new_bucket_count);
  2878. if(cache_begin && new_n < new_first_bucket_num)
  2879. new_first_bucket_num = new_n;
  2880. bucket_type &new_b = new_buckets[new_n];
  2881. new_b.splice_after( new_b.before_begin()
  2882. , old_bucket
  2883. , old_bucket.before_begin()
  2884. , bucket_plus_vtraits_t::priv_get_last(old_bucket, optimize_multikey_t()));
  2885. }
  2886. }
  2887. this->priv_size_traits().set_size(size_backup);
  2888. this->priv_split_traits().set_size(new_bucket_count);
  2889. if(&new_bucket_traits != &this->priv_bucket_traits()){
  2890. this->priv_bucket_traits() = new_bucket_traits;
  2891. }
  2892. this->priv_initialize_cache();
  2893. this->priv_insertion_update_cache(new_first_bucket_num);
  2894. rollback1.release();
  2895. rollback2.release();
  2896. }
  2897. template <class MaybeConstHashtableImpl, class Cloner, class Disposer>
  2898. void priv_clone_from(MaybeConstHashtableImpl &src, Cloner cloner, Disposer disposer)
  2899. {
  2900. this->clear_and_dispose(disposer);
  2901. if(!constant_time_size || !src.empty()){
  2902. const size_type src_bucket_count = src.bucket_count();
  2903. const size_type dst_bucket_count = this->bucket_count();
  2904. //Check power of two bucket array if the option is activated
  2905. BOOST_INTRUSIVE_INVARIANT_ASSERT
  2906. (!power_2_buckets || (0 == (src_bucket_count & (src_bucket_count-1))));
  2907. BOOST_INTRUSIVE_INVARIANT_ASSERT
  2908. (!power_2_buckets || (0 == (dst_bucket_count & (dst_bucket_count-1))));
  2909. //If src bucket count is bigger or equal, structural copy is possible
  2910. const bool structural_copy = (!incremental) && (src_bucket_count >= dst_bucket_count) &&
  2911. (power_2_buckets || (src_bucket_count % dst_bucket_count) == 0);
  2912. if(structural_copy){
  2913. this->priv_structural_clone_from(src, cloner, disposer);
  2914. }
  2915. else{
  2916. //Unlike previous cloning algorithm, this can throw
  2917. //if cloner, hasher or comparison functor throw
  2918. typedef typename detail::if_c< detail::is_const<MaybeConstHashtableImpl>::value
  2919. , typename MaybeConstHashtableImpl::const_iterator
  2920. , typename MaybeConstHashtableImpl::iterator
  2921. >::type clone_iterator;
  2922. clone_iterator b(src.begin()), e(src.end());
  2923. detail::exception_disposer<hashtable_impl, Disposer> rollback(*this, disposer);
  2924. for(; b != e; ++b){
  2925. //No need to check for duplicates and insert it in the first position
  2926. //as this is an unordered container. So use minimal insertion code
  2927. std::size_t const hash_to_store = this->priv_stored_or_compute_hash(*b, store_hash_t());;
  2928. size_type const bucket_number = this->priv_hash_to_bucket(hash_to_store);
  2929. typedef typename detail::if_c
  2930. <detail::is_const<MaybeConstHashtableImpl>::value, const_reference, reference>::type reference_type;
  2931. reference_type r = *b;
  2932. this->priv_clone_front_in_bucket<reference_type>(bucket_number, r, hash_to_store, cloner);
  2933. }
  2934. rollback.release();
  2935. }
  2936. }
  2937. }
  2938. template<class ValueReference, class Cloner>
  2939. void priv_clone_front_in_bucket( size_type const bucket_number
  2940. , typename detail::identity<ValueReference>::type src_ref
  2941. , std::size_t const hash_to_store, Cloner cloner)
  2942. {
  2943. //No need to check for duplicates and insert it in the first position
  2944. //as this is an unordered container. So use minimal insertion code
  2945. //std::size_t const hash_value = this->priv_stored_or_compute_hash(src_ref, store_hash_t());;
  2946. //size_type const bucket_number = this->priv_hash_to_bucket(hash_value);
  2947. bucket_type &cur_bucket = this->priv_bucket_pointer()[bucket_number];
  2948. siterator const prev(cur_bucket.before_begin());
  2949. //Just check if the cloned node is equal to the first inserted value in the new bucket
  2950. //as equal src values were contiguous and they should be already inserted in the
  2951. //destination bucket.
  2952. bool const next_is_in_group = optimize_multikey && !cur_bucket.empty() &&
  2953. this->priv_equal()( key_of_value()(src_ref)
  2954. , key_of_value()(this->priv_value_from_slist_node((++siterator(prev)).pointed_node())));
  2955. this->priv_insert_equal_after_find(*cloner(src_ref), bucket_number, hash_to_store, prev, next_is_in_group);
  2956. }
  2957. template <class MaybeConstHashtableImpl, class Cloner, class Disposer>
  2958. void priv_structural_clone_from(MaybeConstHashtableImpl &src, Cloner cloner, Disposer disposer)
  2959. {
  2960. //First clone the first ones
  2961. const size_type src_bucket_count = src.bucket_count();
  2962. const size_type dst_bucket_count = this->bucket_count();
  2963. const bucket_ptr src_buckets = src.priv_bucket_pointer();
  2964. const bucket_ptr dst_buckets = this->priv_bucket_pointer();
  2965. size_type constructed = 0;
  2966. typedef node_cast_adaptor< detail::node_disposer<Disposer, value_traits, CircularSListAlgorithms>
  2967. , slist_node_ptr, node_ptr > NodeDisposer;
  2968. NodeDisposer node_disp(disposer, &this->priv_value_traits());
  2969. detail::exception_array_disposer<bucket_type, NodeDisposer, size_type>
  2970. rollback(dst_buckets[0], node_disp, constructed);
  2971. //Now insert the remaining ones using the modulo trick
  2972. for( //"constructed" already initialized
  2973. ; constructed < src_bucket_count
  2974. ; ++constructed){
  2975. //Since incremental hashing can't be structurally copied, avoid hash_to_bucket_split
  2976. const std::size_t new_n = detail::hash_to_bucket(constructed, dst_bucket_count, detail::bool_<power_2_buckets>());
  2977. bucket_type &src_b = src_buckets[constructed];
  2978. for( siterator b(src_b.begin()), e(src_b.end()); b != e; ++b){
  2979. slist_node_ptr const n(b.pointed_node());
  2980. typedef typename detail::if_c
  2981. <detail::is_const<MaybeConstHashtableImpl>::value, const_reference, reference>::type reference_type;
  2982. reference_type r = this->priv_value_from_slist_node(n);
  2983. this->priv_clone_front_in_bucket<reference_type>
  2984. (new_n, r, this->priv_stored_hash(n, store_hash_t()), cloner);
  2985. }
  2986. }
  2987. this->priv_hasher() = src.priv_hasher();
  2988. this->priv_equal() = src.priv_equal();
  2989. rollback.release();
  2990. this->priv_size_traits().set_size(src.priv_size_traits().get_size());
  2991. this->priv_split_traits().set_size(dst_bucket_count);
  2992. this->priv_insertion_update_cache(0u);
  2993. this->priv_erasure_update_cache();
  2994. }
  2995. std::size_t priv_hash_to_bucket(std::size_t hash_value) const
  2996. {
  2997. return detail::hash_to_bucket_split<power_2_buckets, incremental>
  2998. (hash_value, this->priv_bucket_traits().bucket_count(), this->priv_split_traits().get_size());
  2999. }
  3000. 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)
  3001. {
  3002. //Now store hash if needed
  3003. node_ptr n = pointer_traits<node_ptr>::pointer_to(this->priv_value_to_node(value));
  3004. node_functions_t::store_hash(n, hash_value, store_hash_t());
  3005. //Checks for some modes
  3006. BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(n));
  3007. //Shortcut to optimize_multikey cases
  3008. group_functions_t::insert_in_group
  3009. ( next_is_in_group ? detail::dcast_bucket_ptr<node>((++siterator(prev)).pointed_node()) : n
  3010. , n, optimize_multikey_t());
  3011. //Update cache and increment size if needed
  3012. this->priv_insertion_update_cache(bucket_num);
  3013. this->priv_size_traits().increment();
  3014. //Insert the element in the bucket after it
  3015. return iterator(bucket_type::s_insert_after(prev, *n), &this->get_bucket_value_traits());
  3016. }
  3017. template<class KeyType, class KeyHasher, class KeyEqual>
  3018. siterator priv_find //In case it is not found previt is bucket.before_begin()
  3019. ( const KeyType &key, KeyHasher hash_func
  3020. , KeyEqual equal_func, size_type &bucket_number, std::size_t &h, siterator &previt) const
  3021. {
  3022. h = hash_func(key);
  3023. return this->priv_find_with_hash(key, equal_func, bucket_number, h, previt);
  3024. }
  3025. template<class KeyType, class KeyEqual>
  3026. bool priv_is_value_equal_to_key(const value_type &v, const std::size_t h, const KeyType &key, KeyEqual equal_func) const
  3027. {
  3028. (void)h;
  3029. return (!compare_hash || this->priv_stored_or_compute_hash(v, store_hash_t()) == h) && equal_func(key, key_of_value()(v));
  3030. }
  3031. //return previous iterator to the next equal range group in case
  3032. static siterator priv_last_in_group(const siterator &it_first_in_group)
  3033. {
  3034. return bucket_type::s_iterator_to
  3035. (*group_functions_t::get_last_in_group
  3036. (detail::dcast_bucket_ptr<node>(it_first_in_group.pointed_node()), optimize_multikey_t()));
  3037. }
  3038. template<class KeyType, class KeyEqual>
  3039. siterator priv_find_with_hash //In case it is not found previt is bucket.before_begin()
  3040. ( const KeyType &key, KeyEqual equal_func, size_type &bucket_number, const std::size_t h, siterator &previt) const
  3041. {
  3042. bucket_number = this->priv_hash_to_bucket(h);
  3043. bucket_type &b = this->priv_bucket_pointer()[bucket_number];
  3044. previt = b.before_begin();
  3045. siterator it = previt;
  3046. siterator const endit = b.end();
  3047. while(++it != endit){
  3048. if(this->priv_is_value_equal_to_key(this->priv_value_from_slist_node(it.pointed_node()), h, key, equal_func)){
  3049. return it;
  3050. }
  3051. previt = it = (priv_last_in_group)(it);
  3052. }
  3053. previt = b.before_begin();
  3054. return this->priv_invalid_local_it();
  3055. }
  3056. template<class KeyType, class KeyHasher, class KeyEqual>
  3057. std::pair<siterator, siterator> priv_local_equal_range
  3058. ( const KeyType &key
  3059. , KeyHasher hash_func
  3060. , KeyEqual equal_func
  3061. , size_type &found_bucket
  3062. , size_type &cnt) const
  3063. {
  3064. size_type internal_cnt = 0;
  3065. //Let's see if the element is present
  3066. siterator prev;
  3067. size_type n_bucket;
  3068. std::size_t h;
  3069. std::pair<siterator, siterator> to_return
  3070. ( this->priv_find(key, hash_func, equal_func, n_bucket, h, prev)
  3071. , this->priv_invalid_local_it());
  3072. if(to_return.first != to_return.second){
  3073. found_bucket = n_bucket;
  3074. //If it's present, find the first that it's not equal in
  3075. //the same bucket
  3076. bucket_type &b = this->priv_bucket_pointer()[n_bucket];
  3077. siterator it = to_return.first;
  3078. ++internal_cnt; //At least one is found
  3079. if(optimize_multikey){
  3080. to_return.second = ++(priv_last_in_group)(it);
  3081. internal_cnt += boost::intrusive::iterator_distance(++it, to_return.second);
  3082. }
  3083. else{
  3084. siterator const bend = b.end();
  3085. while(++it != bend &&
  3086. this->priv_is_value_equal_to_key(this->priv_value_from_slist_node(it.pointed_node()), h, key, equal_func)){
  3087. ++internal_cnt;
  3088. }
  3089. to_return.second = it;
  3090. }
  3091. }
  3092. cnt = internal_cnt;
  3093. return to_return;
  3094. }
  3095. template<class KeyType, class KeyHasher, class KeyEqual>
  3096. std::pair<siterator, siterator> priv_equal_range
  3097. ( const KeyType &key
  3098. , KeyHasher hash_func
  3099. , KeyEqual equal_func) const
  3100. {
  3101. size_type n_bucket;
  3102. size_type cnt;
  3103. //Let's see if the element is present
  3104. std::pair<siterator, siterator> to_return
  3105. (this->priv_local_equal_range(key, hash_func, equal_func, n_bucket, cnt));
  3106. //If not, find the next element as ".second" if ".second" local iterator
  3107. //is not pointing to an element.
  3108. bucket_ptr const bp = this->priv_bucket_pointer();
  3109. if(to_return.first != to_return.second &&
  3110. to_return.second == bp[n_bucket].end()){
  3111. to_return.second = this->priv_invalid_local_it();
  3112. ++n_bucket;
  3113. for( const size_type max_bucket = this->bucket_count()
  3114. ; n_bucket != max_bucket
  3115. ; ++n_bucket){
  3116. bucket_type &b = bp[n_bucket];
  3117. if(!b.empty()){
  3118. to_return.second = b.begin();
  3119. break;
  3120. }
  3121. }
  3122. }
  3123. return to_return;
  3124. }
  3125. std::size_t priv_get_bucket_num(siterator it)
  3126. { return this->priv_get_bucket_num_hash_dispatch(it, store_hash_t()); }
  3127. std::size_t priv_get_bucket_num_hash_dispatch(siterator it, detail::true_) //store_hash
  3128. {
  3129. return this->priv_hash_to_bucket
  3130. (this->priv_stored_hash(it.pointed_node(), store_hash_t()));
  3131. }
  3132. std::size_t priv_get_bucket_num_hash_dispatch(siterator it, detail::false_) //NO store_hash
  3133. { return this->priv_get_bucket_num_no_hash_store(it, optimize_multikey_t()); }
  3134. static siterator priv_get_previous(bucket_type &b, siterator i)
  3135. { return bucket_plus_vtraits_t::priv_get_previous(b, i, optimize_multikey_t()); }
  3136. /// @endcond
  3137. };
  3138. /// @cond
  3139. template < class T
  3140. , bool UniqueKeys
  3141. , class PackedOptions
  3142. >
  3143. struct make_bucket_traits
  3144. {
  3145. //Real value traits must be calculated from options
  3146. typedef typename detail::get_value_traits
  3147. <T, typename PackedOptions::proto_value_traits>::type value_traits;
  3148. typedef typename PackedOptions::bucket_traits specified_bucket_traits;
  3149. //Real bucket traits must be calculated from options and calculated value_traits
  3150. typedef typename get_slist_impl
  3151. <typename reduced_slist_node_traits
  3152. <typename value_traits::node_traits>::type
  3153. >::type slist_impl;
  3154. typedef typename
  3155. detail::if_c< detail::is_same
  3156. < specified_bucket_traits
  3157. , default_bucket_traits
  3158. >::value
  3159. , bucket_traits_impl<slist_impl>
  3160. , specified_bucket_traits
  3161. >::type type;
  3162. };
  3163. /// @endcond
  3164. //! Helper metafunction to define a \c hashtable that yields to the same type when the
  3165. //! same options (either explicitly or implicitly) are used.
  3166. #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  3167. template<class T, class ...Options>
  3168. #else
  3169. template<class T, class O1 = void, class O2 = void
  3170. , class O3 = void, class O4 = void
  3171. , class O5 = void, class O6 = void
  3172. , class O7 = void, class O8 = void
  3173. , class O9 = void, class O10= void
  3174. >
  3175. #endif
  3176. struct make_hashtable
  3177. {
  3178. /// @cond
  3179. typedef typename pack_options
  3180. < hashtable_defaults,
  3181. #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  3182. O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
  3183. #else
  3184. Options...
  3185. #endif
  3186. >::type packed_options;
  3187. typedef typename detail::get_value_traits
  3188. <T, typename packed_options::proto_value_traits>::type value_traits;
  3189. typedef typename make_bucket_traits
  3190. <T, false, packed_options>::type bucket_traits;
  3191. typedef hashtable_impl
  3192. < value_traits
  3193. , typename packed_options::key_of_value
  3194. , typename packed_options::hash
  3195. , typename packed_options::equal
  3196. , bucket_traits
  3197. , typename packed_options::size_type
  3198. , (std::size_t(false)*hash_bool_flags::unique_keys_pos)
  3199. |(std::size_t(packed_options::constant_time_size)*hash_bool_flags::constant_time_size_pos)
  3200. |(std::size_t(packed_options::power_2_buckets)*hash_bool_flags::power_2_buckets_pos)
  3201. |(std::size_t(packed_options::cache_begin)*hash_bool_flags::cache_begin_pos)
  3202. |(std::size_t(packed_options::compare_hash)*hash_bool_flags::compare_hash_pos)
  3203. |(std::size_t(packed_options::incremental)*hash_bool_flags::incremental_pos)
  3204. > implementation_defined;
  3205. /// @endcond
  3206. typedef implementation_defined type;
  3207. };
  3208. #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  3209. #if defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  3210. template<class T, class ...Options>
  3211. #else
  3212. template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9, class O10>
  3213. #endif
  3214. class hashtable
  3215. : public make_hashtable<T,
  3216. #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  3217. O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
  3218. #else
  3219. Options...
  3220. #endif
  3221. >::type
  3222. {
  3223. typedef typename make_hashtable<T,
  3224. #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  3225. O1, O2, O3, O4, O5, O6, O7, O8, O9, O10
  3226. #else
  3227. Options...
  3228. #endif
  3229. >::type Base;
  3230. BOOST_MOVABLE_BUT_NOT_COPYABLE(hashtable)
  3231. public:
  3232. typedef typename Base::value_traits value_traits;
  3233. typedef typename Base::iterator iterator;
  3234. typedef typename Base::const_iterator const_iterator;
  3235. typedef typename Base::bucket_ptr bucket_ptr;
  3236. typedef typename Base::size_type size_type;
  3237. typedef typename Base::hasher hasher;
  3238. typedef typename Base::bucket_traits bucket_traits;
  3239. typedef typename Base::key_equal key_equal;
  3240. //Assert if passed value traits are compatible with the type
  3241. BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
  3242. BOOST_INTRUSIVE_FORCEINLINE explicit hashtable ( const bucket_traits &b_traits
  3243. , const hasher & hash_func = hasher()
  3244. , const key_equal &equal_func = key_equal()
  3245. , const value_traits &v_traits = value_traits())
  3246. : Base(b_traits, hash_func, equal_func, v_traits)
  3247. {}
  3248. BOOST_INTRUSIVE_FORCEINLINE hashtable(BOOST_RV_REF(hashtable) x)
  3249. : Base(BOOST_MOVE_BASE(Base, x))
  3250. {}
  3251. BOOST_INTRUSIVE_FORCEINLINE hashtable& operator=(BOOST_RV_REF(hashtable) x)
  3252. { return static_cast<hashtable&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); }
  3253. template <class Cloner, class Disposer>
  3254. BOOST_INTRUSIVE_FORCEINLINE void clone_from(const hashtable &src, Cloner cloner, Disposer disposer)
  3255. { Base::clone_from(src, cloner, disposer); }
  3256. template <class Cloner, class Disposer>
  3257. BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(hashtable) src, Cloner cloner, Disposer disposer)
  3258. { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); }
  3259. };
  3260. #endif
  3261. } //namespace intrusive
  3262. } //namespace boost
  3263. #include <boost/intrusive/detail/config_end.hpp>
  3264. #endif //BOOST_INTRUSIVE_HASHTABLE_HPP