phmap_base.h 174 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672367336743675367636773678367936803681368236833684368536863687368836893690369136923693369436953696369736983699370037013702370337043705370637073708370937103711371237133714371537163717371837193720372137223723372437253726372737283729373037313732373337343735373637373738373937403741374237433744374537463747374837493750375137523753375437553756375737583759376037613762376337643765376637673768376937703771377237733774377537763777377837793780378137823783378437853786378737883789379037913792379337943795379637973798379938003801380238033804380538063807380838093810381138123813381438153816381738183819382038213822382338243825382638273828382938303831383238333834383538363837383838393840384138423843384438453846384738483849385038513852385338543855385638573858385938603861386238633864386538663867386838693870387138723873387438753876387738783879388038813882388338843885388638873888388938903891389238933894389538963897389838993900390139023903390439053906390739083909391039113912391339143915391639173918391939203921392239233924392539263927392839293930393139323933393439353936393739383939394039413942394339443945394639473948394939503951395239533954395539563957395839593960396139623963396439653966396739683969397039713972397339743975397639773978397939803981398239833984398539863987398839893990399139923993399439953996399739983999400040014002400340044005400640074008400940104011401240134014401540164017401840194020402140224023402440254026402740284029403040314032403340344035403640374038403940404041404240434044404540464047404840494050405140524053405440554056405740584059406040614062406340644065406640674068406940704071407240734074407540764077407840794080408140824083408440854086408740884089409040914092409340944095409640974098409941004101410241034104410541064107410841094110411141124113411441154116411741184119412041214122412341244125412641274128412941304131413241334134413541364137413841394140414141424143414441454146414741484149415041514152415341544155415641574158415941604161416241634164416541664167416841694170417141724173417441754176417741784179418041814182418341844185418641874188418941904191419241934194419541964197419841994200420142024203420442054206420742084209421042114212421342144215421642174218421942204221422242234224422542264227422842294230423142324233423442354236423742384239424042414242424342444245424642474248424942504251425242534254425542564257425842594260426142624263426442654266426742684269427042714272427342744275427642774278427942804281428242834284428542864287428842894290429142924293429442954296429742984299430043014302430343044305430643074308430943104311431243134314431543164317431843194320432143224323432443254326432743284329433043314332433343344335433643374338433943404341434243434344434543464347434843494350435143524353435443554356435743584359436043614362436343644365436643674368436943704371437243734374437543764377437843794380438143824383438443854386438743884389439043914392439343944395439643974398439944004401440244034404440544064407440844094410441144124413441444154416441744184419442044214422442344244425442644274428442944304431443244334434443544364437443844394440444144424443444444454446444744484449445044514452445344544455445644574458445944604461446244634464446544664467446844694470447144724473447444754476447744784479448044814482448344844485448644874488448944904491449244934494449544964497449844994500450145024503450445054506450745084509451045114512451345144515451645174518451945204521452245234524452545264527452845294530453145324533453445354536453745384539454045414542454345444545454645474548454945504551455245534554455545564557455845594560456145624563456445654566456745684569457045714572457345744575457645774578457945804581458245834584458545864587458845894590459145924593459445954596459745984599460046014602460346044605460646074608460946104611461246134614461546164617461846194620462146224623462446254626462746284629463046314632463346344635463646374638463946404641464246434644464546464647464846494650465146524653465446554656465746584659466046614662466346644665466646674668466946704671467246734674467546764677467846794680468146824683468446854686468746884689469046914692469346944695469646974698469947004701470247034704470547064707470847094710471147124713471447154716471747184719472047214722472347244725472647274728472947304731473247334734473547364737473847394740474147424743474447454746474747484749475047514752475347544755475647574758475947604761476247634764476547664767476847694770477147724773477447754776477747784779478047814782478347844785478647874788478947904791479247934794479547964797479847994800480148024803480448054806480748084809481048114812481348144815481648174818481948204821482248234824482548264827482848294830483148324833483448354836483748384839484048414842484348444845484648474848484948504851485248534854485548564857485848594860486148624863486448654866486748684869487048714872487348744875487648774878487948804881488248834884488548864887488848894890489148924893489448954896489748984899490049014902490349044905490649074908490949104911491249134914491549164917491849194920492149224923492449254926492749284929493049314932493349344935493649374938493949404941494249434944494549464947494849494950495149524953495449554956495749584959496049614962496349644965496649674968496949704971497249734974497549764977497849794980498149824983498449854986498749884989499049914992499349944995499649974998499950005001500250035004500550065007500850095010501150125013501450155016501750185019502050215022502350245025502650275028502950305031503250335034503550365037503850395040504150425043504450455046504750485049505050515052505350545055505650575058505950605061506250635064506550665067506850695070507150725073507450755076507750785079508050815082508350845085508650875088
  1. #if !defined(phmap_base_h_guard_)
  2. #define phmap_base_h_guard_
  3. // ---------------------------------------------------------------------------
  4. // Copyright (c) 2019, Gregory Popovitch - [email protected]
  5. //
  6. // Licensed under the Apache License, Version 2.0 (the "License");
  7. // you may not use this file except in compliance with the License.
  8. // You may obtain a copy of the License at
  9. //
  10. // https://www.apache.org/licenses/LICENSE-2.0
  11. //
  12. // Unless required by applicable law or agreed to in writing, software
  13. // distributed under the License is distributed on an "AS IS" BASIS,
  14. // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15. // See the License for the specific language governing permissions and
  16. // limitations under the License.
  17. //
  18. // Includes work from abseil-cpp (https://github.com/abseil/abseil-cpp)
  19. // with modifications.
  20. //
  21. // Copyright 2018 The Abseil Authors.
  22. //
  23. // Licensed under the Apache License, Version 2.0 (the "License");
  24. // you may not use this file except in compliance with the License.
  25. // You may obtain a copy of the License at
  26. //
  27. // https://www.apache.org/licenses/LICENSE-2.0
  28. //
  29. // Unless required by applicable law or agreed to in writing, software
  30. // distributed under the License is distributed on an "AS IS" BASIS,
  31. // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  32. // See the License for the specific language governing permissions and
  33. // limitations under the License.
  34. // ---------------------------------------------------------------------------
  35. #include <algorithm>
  36. #include <cassert>
  37. #include <cstddef>
  38. #include <initializer_list>
  39. #include <iterator>
  40. #include <string>
  41. #include <type_traits>
  42. #include <utility>
  43. #include <functional>
  44. #include <tuple>
  45. #include <utility>
  46. #include <memory>
  47. #include <mutex> // for std::lock
  48. #include "phmap_config.h"
  49. #ifdef PHMAP_HAVE_SHARED_MUTEX
  50. #include <shared_mutex> // after "phmap_config.h"
  51. #endif
  52. #ifdef _MSC_VER
  53. #pragma warning(push)
  54. #pragma warning(disable : 4514) // unreferenced inline function has been removed
  55. #pragma warning(disable : 4582) // constructor is not implicitly called
  56. #pragma warning(disable : 4625) // copy constructor was implicitly defined as deleted
  57. #pragma warning(disable : 4626) // assignment operator was implicitly defined as deleted
  58. #pragma warning(disable : 4710) // function not inlined
  59. #pragma warning(disable : 4711) // selected for automatic inline expansion
  60. #pragma warning(disable : 4820) // '6' bytes padding added after data member
  61. #endif // _MSC_VER
  62. namespace phmap {
  63. template <class T> using Allocator = typename std::allocator<T>;
  64. template<class T1, class T2> using Pair = typename std::pair<T1, T2>;
  65. template <class T>
  66. struct EqualTo
  67. {
  68. LL_INLINE bool operator()(const T& a, const T& b) const
  69. {
  70. return std::equal_to<T>()(a, b);
  71. }
  72. };
  73. template <class T>
  74. struct Less
  75. {
  76. LL_INLINE bool operator()(const T& a, const T& b) const
  77. {
  78. return std::less<T>()(a, b);
  79. }
  80. };
  81. namespace type_traits_internal {
  82. template <typename... Ts>
  83. struct VoidTImpl {
  84. using type = void;
  85. };
  86. // NOTE: The `is_detected` family of templates here differ from the library
  87. // fundamentals specification in that for library fundamentals, `Op<Args...>` is
  88. // evaluated as soon as the type `is_detected<Op, Args...>` undergoes
  89. // substitution, regardless of whether or not the `::value` is accessed. That
  90. // is inconsistent with all other standard traits and prevents lazy evaluation
  91. // in larger contexts (such as if the `is_detected` check is a trailing argument
  92. // of a `conjunction`. This implementation opts to instead be lazy in the same
  93. // way that the standard traits are (this "defect" of the detection idiom
  94. // specifications has been reported).
  95. // ---------------------------------------------------------------------------
  96. template <class Enabler, template <class...> class Op, class... Args>
  97. struct is_detected_impl {
  98. using type = std::false_type;
  99. };
  100. template <template <class...> class Op, class... Args>
  101. struct is_detected_impl<typename VoidTImpl<Op<Args...>>::type, Op, Args...> {
  102. using type = std::true_type;
  103. };
  104. template <template <class...> class Op, class... Args>
  105. struct is_detected : is_detected_impl<void, Op, Args...>::type {};
  106. template <class Enabler, class To, template <class...> class Op, class... Args>
  107. struct is_detected_convertible_impl {
  108. using type = std::false_type;
  109. };
  110. template <class To, template <class...> class Op, class... Args>
  111. struct is_detected_convertible_impl<
  112. typename std::enable_if<std::is_convertible<Op<Args...>, To>::value>::type,
  113. To, Op, Args...> {
  114. using type = std::true_type;
  115. };
  116. template <class To, template <class...> class Op, class... Args>
  117. struct is_detected_convertible
  118. : is_detected_convertible_impl<void, To, Op, Args...>::type {};
  119. template <typename T>
  120. using IsCopyAssignableImpl =
  121. decltype(std::declval<T&>() = std::declval<const T&>());
  122. template <typename T>
  123. using IsMoveAssignableImpl = decltype(std::declval<T&>() = std::declval<T&&>());
  124. } // namespace type_traits_internal
  125. template <typename T>
  126. struct is_copy_assignable : type_traits_internal::is_detected<
  127. type_traits_internal::IsCopyAssignableImpl, T> {
  128. };
  129. template <typename T>
  130. struct is_move_assignable : type_traits_internal::is_detected<
  131. type_traits_internal::IsMoveAssignableImpl, T> {
  132. };
  133. // ---------------------------------------------------------------------------
  134. // void_t()
  135. //
  136. // Ignores the type of any its arguments and returns `void`. In general, this
  137. // metafunction allows you to create a general case that maps to `void` while
  138. // allowing specializations that map to specific types.
  139. //
  140. // This metafunction is designed to be a drop-in replacement for the C++17
  141. // `std::void_t` metafunction.
  142. //
  143. // NOTE: `phmap::void_t` does not use the standard-specified implementation so
  144. // that it can remain compatible with gcc < 5.1. This can introduce slightly
  145. // different behavior, such as when ordering partial specializations.
  146. // ---------------------------------------------------------------------------
  147. template <typename... Ts>
  148. using void_t = typename type_traits_internal::VoidTImpl<Ts...>::type;
  149. // ---------------------------------------------------------------------------
  150. // conjunction
  151. //
  152. // Performs a compile-time logical AND operation on the passed types (which
  153. // must have `::value` members convertible to `bool`. Short-circuits if it
  154. // encounters any `false` members (and does not compare the `::value` members
  155. // of any remaining arguments).
  156. //
  157. // This metafunction is designed to be a drop-in replacement for the C++17
  158. // `std::conjunction` metafunction.
  159. // ---------------------------------------------------------------------------
  160. template <typename... Ts>
  161. struct conjunction;
  162. template <typename T, typename... Ts>
  163. struct conjunction<T, Ts...>
  164. : std::conditional<T::value, conjunction<Ts...>, T>::type {};
  165. template <typename T>
  166. struct conjunction<T> : T {};
  167. template <>
  168. struct conjunction<> : std::true_type {};
  169. // Workaround for "deprecated builtins" warnings with clang v15+. HB
  170. #if defined(__clang__)
  171. # pragma clang diagnostic push
  172. # pragma clang diagnostic ignored "-Wunknown-warning-option"
  173. # pragma clang diagnostic ignored "-Wdeprecated-builtins"
  174. #endif
  175. // ---------------------------------------------------------------------------
  176. // disjunction
  177. //
  178. // Performs a compile-time logical OR operation on the passed types (which
  179. // must have `::value` members convertible to `bool`. Short-circuits if it
  180. // encounters any `true` members (and does not compare the `::value` members
  181. // of any remaining arguments).
  182. //
  183. // This metafunction is designed to be a drop-in replacement for the C++17
  184. // `std::disjunction` metafunction.
  185. // ---------------------------------------------------------------------------
  186. template <typename... Ts>
  187. struct disjunction;
  188. template <typename T, typename... Ts>
  189. struct disjunction<T, Ts...> :
  190. std::conditional<T::value, T, disjunction<Ts...>>::type {};
  191. template <typename T>
  192. struct disjunction<T> : T {};
  193. template <>
  194. struct disjunction<> : std::false_type {};
  195. template <typename T>
  196. struct negation : std::integral_constant<bool, !T::value> {};
  197. #if defined(__clang__)
  198. # pragma clang diagnostic pop
  199. #endif
  200. // -----------------------------------------------------------------------------
  201. // C++14 "_t" trait aliases
  202. // -----------------------------------------------------------------------------
  203. template <typename T>
  204. using remove_cv_t = typename std::remove_cv<T>::type;
  205. template <typename T>
  206. using remove_const_t = typename std::remove_const<T>::type;
  207. template <typename T>
  208. using remove_volatile_t = typename std::remove_volatile<T>::type;
  209. template <typename T>
  210. using add_cv_t = typename std::add_cv<T>::type;
  211. template <typename T>
  212. using add_const_t = typename std::add_const<T>::type;
  213. template <typename T>
  214. using add_volatile_t = typename std::add_volatile<T>::type;
  215. template <typename T>
  216. using remove_reference_t = typename std::remove_reference<T>::type;
  217. template <typename T>
  218. using add_lvalue_reference_t = typename std::add_lvalue_reference<T>::type;
  219. template <typename T>
  220. using add_rvalue_reference_t = typename std::add_rvalue_reference<T>::type;
  221. template <typename T>
  222. using remove_pointer_t = typename std::remove_pointer<T>::type;
  223. template <typename T>
  224. using add_pointer_t = typename std::add_pointer<T>::type;
  225. template <typename T>
  226. using make_signed_t = typename std::make_signed<T>::type;
  227. template <typename T>
  228. using make_unsigned_t = typename std::make_unsigned<T>::type;
  229. template <typename T>
  230. using remove_extent_t = typename std::remove_extent<T>::type;
  231. template <typename T>
  232. using remove_all_extents_t = typename std::remove_all_extents<T>::type;
  233. template<std::size_t Len, std::size_t Align>
  234. struct aligned_storage {
  235. struct type {
  236. alignas(Align) unsigned char data[Len];
  237. };
  238. };
  239. template< std::size_t Len, std::size_t Align>
  240. using aligned_storage_t = typename aligned_storage<Len, Align>::type;
  241. template <typename T>
  242. using decay_t = typename std::decay<T>::type;
  243. template <bool B, typename T = void>
  244. using enable_if_t = typename std::enable_if<B, T>::type;
  245. template <bool B, typename T, typename F>
  246. using conditional_t = typename std::conditional<B, T, F>::type;
  247. template <typename... T>
  248. using common_type_t = typename std::common_type<T...>::type;
  249. template <typename T>
  250. using underlying_type_t = typename std::underlying_type<T>::type;
  251. template< class F, class... ArgTypes>
  252. #if PHMAP_HAVE_CC17 && defined(__cpp_lib_result_of_sfinae)
  253. using invoke_result_t = typename std::invoke_result_t<F, ArgTypes...>;
  254. #else
  255. using invoke_result_t = typename std::result_of<F(ArgTypes...)>::type;
  256. #endif
  257. namespace type_traits_internal {
  258. // ----------------------------------------------------------------------
  259. // In MSVC we can't probe std::hash or stdext::hash because it triggers a
  260. // static_assert instead of failing substitution. Libc++ prior to 4.0
  261. // also used a static_assert.
  262. // ----------------------------------------------------------------------
  263. #if defined(_MSC_VER) || (defined(_LIBCPP_VERSION) && \
  264. _LIBCPP_VERSION < 4000 && _LIBCPP_STD_VER > 11)
  265. #define PHMAP_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ 0
  266. #else
  267. #define PHMAP_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_ 1
  268. #endif
  269. #if !PHMAP_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
  270. template <typename Key, typename = size_t>
  271. struct IsHashable : std::true_type {};
  272. #else // PHMAP_META_INTERNAL_STD_HASH_SFINAE_FRIENDLY_
  273. template <typename Key, typename = void>
  274. struct IsHashable : std::false_type {};
  275. template <typename Key>
  276. struct IsHashable<Key,
  277. phmap::enable_if_t<std::is_convertible<
  278. decltype(std::declval<std::hash<Key>&>()(std::declval<Key const&>())),
  279. std::size_t>::value>> : std::true_type {};
  280. #endif
  281. struct AssertHashEnabledHelper
  282. {
  283. private:
  284. static void Sink(...) {}
  285. struct NAT {};
  286. template <class Key>
  287. static auto GetReturnType(int)
  288. -> decltype(std::declval<std::hash<Key>>()(std::declval<Key const&>()));
  289. template <class Key>
  290. static NAT GetReturnType(...);
  291. template <class Key>
  292. static std::nullptr_t DoIt() {
  293. static_assert(IsHashable<Key>::value,
  294. "std::hash<Key> does not provide a call operator");
  295. static_assert(
  296. std::is_default_constructible<std::hash<Key>>::value,
  297. "std::hash<Key> must be default constructible when it is enabled");
  298. static_assert(
  299. std::is_copy_constructible<std::hash<Key>>::value,
  300. "std::hash<Key> must be copy constructible when it is enabled");
  301. static_assert(phmap::is_copy_assignable<std::hash<Key>>::value,
  302. "std::hash<Key> must be copy assignable when it is enabled");
  303. // is_destructible is unchecked as it's implied by each of the
  304. // is_constructible checks.
  305. using ReturnType = decltype(GetReturnType<Key>(0));
  306. static_assert(std::is_same<ReturnType, NAT>::value ||
  307. std::is_same<ReturnType, size_t>::value,
  308. "std::hash<Key> must return size_t");
  309. return nullptr;
  310. }
  311. template <class... Ts>
  312. friend void AssertHashEnabled();
  313. };
  314. template <class... Ts>
  315. LL_INLINE void AssertHashEnabled
  316. ()
  317. {
  318. using Helper = AssertHashEnabledHelper;
  319. Helper::Sink(Helper::DoIt<Ts>()...);
  320. }
  321. } // namespace type_traits_internal
  322. } // namespace phmap
  323. // -----------------------------------------------------------------------------
  324. // hash_policy_traits
  325. // -----------------------------------------------------------------------------
  326. namespace phmap {
  327. namespace priv {
  328. // Defines how slots are initialized/destroyed/moved.
  329. template <class Policy, class = void>
  330. struct hash_policy_traits
  331. {
  332. private:
  333. struct ReturnKey
  334. {
  335. // We return `Key` here.
  336. // When Key=T&, we forward the lvalue reference.
  337. // When Key=T, we return by value to avoid a dangling reference.
  338. // eg, for string_hash_map.
  339. template <class Key, class... Args>
  340. Key operator()(Key&& k, const Args&...) const {
  341. return std::forward<Key>(k);
  342. }
  343. };
  344. template <class P = Policy, class = void>
  345. struct ConstantIteratorsImpl : std::false_type {};
  346. template <class P>
  347. struct ConstantIteratorsImpl<P, phmap::void_t<typename P::constant_iterators>>
  348. : P::constant_iterators {};
  349. public:
  350. // The actual object stored in the hash table.
  351. using slot_type = typename Policy::slot_type;
  352. // The type of the keys stored in the hashtable.
  353. using key_type = typename Policy::key_type;
  354. // The argument type for insertions into the hashtable. This is different
  355. // from value_type for increased performance. See initializer_list constructor
  356. // and insert() member functions for more details.
  357. using init_type = typename Policy::init_type;
  358. using reference = decltype(Policy::element(std::declval<slot_type*>()));
  359. using pointer = typename std::remove_reference<reference>::type*;
  360. using value_type = typename std::remove_reference<reference>::type;
  361. // Policies can set this variable to tell raw_hash_set that all iterators
  362. // should be constant, even `iterator`. This is useful for set-like
  363. // containers.
  364. // Defaults to false if not provided by the policy.
  365. using constant_iterators = ConstantIteratorsImpl<>;
  366. // PRECONDITION: `slot` is UNINITIALIZED
  367. // POSTCONDITION: `slot` is INITIALIZED
  368. template <class Alloc, class... Args>
  369. static void construct(Alloc* alloc, slot_type* slot, Args&&... args) {
  370. Policy::construct(alloc, slot, std::forward<Args>(args)...);
  371. }
  372. // PRECONDITION: `slot` is INITIALIZED
  373. // POSTCONDITION: `slot` is UNINITIALIZED
  374. template <class Alloc>
  375. static void destroy(Alloc* alloc, slot_type* slot) {
  376. Policy::destroy(alloc, slot);
  377. }
  378. // Transfers the `old_slot` to `new_slot`. Any memory allocated by the
  379. // allocator inside `old_slot` to `new_slot` can be transferred.
  380. //
  381. // OPTIONAL: defaults to:
  382. //
  383. // clone(new_slot, std::move(*old_slot));
  384. // destroy(old_slot);
  385. //
  386. // PRECONDITION: `new_slot` is UNINITIALIZED and `old_slot` is INITIALIZED
  387. // POSTCONDITION: `new_slot` is INITIALIZED and `old_slot` is
  388. // UNINITIALIZED
  389. template <class Alloc>
  390. static void transfer(Alloc* alloc, slot_type* new_slot, slot_type* old_slot) {
  391. transfer_impl(alloc, new_slot, old_slot, 0);
  392. }
  393. // PRECONDITION: `slot` is INITIALIZED
  394. // POSTCONDITION: `slot` is INITIALIZED
  395. template <class P = Policy>
  396. static auto element(slot_type* slot) -> decltype(P::element(slot)) {
  397. return P::element(slot);
  398. }
  399. // Returns the amount of memory owned by `slot`, exclusive of `sizeof(*slot)`.
  400. //
  401. // If `slot` is nullptr, returns the constant amount of memory owned by any
  402. // full slot or -1 if slots own variable amounts of memory.
  403. //
  404. // PRECONDITION: `slot` is INITIALIZED or nullptr
  405. template <class P = Policy>
  406. static size_t space_used(const slot_type* slot) {
  407. return P::space_used(slot);
  408. }
  409. // Provides generalized access to the key for elements, both for elements in
  410. // the table and for elements that have not yet been inserted (or even
  411. // constructed). We would like an API that allows us to say: `key(args...)`
  412. // but we cannot do that for all cases, so we use this more general API that
  413. // can be used for many things, including the following:
  414. //
  415. // - Given an element in a table, get its key.
  416. // - Given an element initializer, get its key.
  417. // - Given `emplace()` arguments, get the element key.
  418. //
  419. // Implementations of this must adhere to a very strict technical
  420. // specification around aliasing and consuming arguments:
  421. //
  422. // Let `value_type` be the result type of `element()` without ref- and
  423. // cv-qualifiers. The first argument is a functor, the rest are constructor
  424. // arguments for `value_type`. Returns `std::forward<F>(f)(k, xs...)`, where
  425. // `k` is the element key, and `xs...` are the new constructor arguments for
  426. // `value_type`. It's allowed for `k` to alias `xs...`, and for both to alias
  427. // `ts...`. The key won't be touched once `xs...` are used to construct an
  428. // element; `ts...` won't be touched at all, which allows `apply()` to consume
  429. // any rvalues among them.
  430. //
  431. // If `value_type` is constructible from `Ts&&...`, `Policy::apply()` must not
  432. // trigger a hard compile error unless it originates from `f`. In other words,
  433. // `Policy::apply()` must be SFINAE-friendly. If `value_type` is not
  434. // constructible from `Ts&&...`, either SFINAE or a hard compile error is OK.
  435. //
  436. // If `Ts...` is `[cv] value_type[&]` or `[cv] init_type[&]`,
  437. // `Policy::apply()` must work. A compile error is not allowed, SFINAE or not.
  438. template <class F, class... Ts, class P = Policy>
  439. static auto apply(F&& f, Ts&&... ts)
  440. -> decltype(P::apply(std::forward<F>(f), std::forward<Ts>(ts)...)) {
  441. return P::apply(std::forward<F>(f), std::forward<Ts>(ts)...);
  442. }
  443. // Returns the "key" portion of the slot.
  444. // Used for node handle manipulation.
  445. template <class P = Policy>
  446. static auto key(slot_type* slot)
  447. -> decltype(P::apply(ReturnKey(), element(slot))) {
  448. return P::apply(ReturnKey(), element(slot));
  449. }
  450. // Returns the "value" (as opposed to the "key") portion of the element. Used
  451. // by maps to implement `operator[]`, `at()` and `insert_or_assign()`.
  452. template <class T, class P = Policy>
  453. static auto value(T* elem) -> decltype(P::value(elem)) {
  454. return P::value(elem);
  455. }
  456. private:
  457. // Use auto -> decltype as an enabler.
  458. template <class Alloc, class P = Policy>
  459. static auto transfer_impl(Alloc* alloc, slot_type* new_slot,
  460. slot_type* old_slot, int)
  461. -> decltype((void)P::transfer(alloc, new_slot, old_slot)) {
  462. P::transfer(alloc, new_slot, old_slot);
  463. }
  464. template <class Alloc>
  465. static void transfer_impl(Alloc* alloc, slot_type* new_slot,
  466. slot_type* old_slot, char) {
  467. construct(alloc, new_slot, std::move(element(old_slot)));
  468. destroy(alloc, old_slot);
  469. }
  470. };
  471. } // namespace priv
  472. } // namespace phmap
  473. // -----------------------------------------------------------------------------
  474. // file utility.h
  475. // -----------------------------------------------------------------------------
  476. // --------- identity.h
  477. namespace phmap {
  478. namespace internal {
  479. template <typename T>
  480. struct identity {
  481. typedef T type;
  482. };
  483. template <typename T>
  484. using identity_t = typename identity<T>::type;
  485. } // namespace internal
  486. } // namespace phmap
  487. // --------- inline_variable.h
  488. #ifdef __cpp_inline_variables
  489. #if defined(__clang__)
  490. #define PHMAP_INTERNAL_EXTERN_DECL(type, name) \
  491. extern const ::phmap::internal::identity_t<type> name;
  492. #else // Otherwise, just define the macro to do nothing.
  493. #define PHMAP_INTERNAL_EXTERN_DECL(type, name)
  494. #endif // defined(__clang__)
  495. // See above comment at top of file for details.
  496. #define PHMAP_INTERNAL_INLINE_CONSTEXPR(type, name, init) \
  497. PHMAP_INTERNAL_EXTERN_DECL(type, name) \
  498. LL_INLINE constexpr ::phmap::internal::identity_t<type> name = init
  499. #else
  500. // See above comment at top of file for details.
  501. //
  502. // Note:
  503. // identity_t is used here so that the const and name are in the
  504. // appropriate place for pointer types, reference types, function pointer
  505. // types, etc..
  506. #define PHMAP_INTERNAL_INLINE_CONSTEXPR(var_type, name, init) \
  507. template <class /*PhmapInternalDummy*/ = void> \
  508. struct PhmapInternalInlineVariableHolder##name { \
  509. static constexpr ::phmap::internal::identity_t<var_type> kInstance = init; \
  510. }; \
  511. \
  512. template <class PhmapInternalDummy> \
  513. constexpr ::phmap::internal::identity_t<var_type> \
  514. PhmapInternalInlineVariableHolder##name<PhmapInternalDummy>::kInstance; \
  515. \
  516. static constexpr const ::phmap::internal::identity_t<var_type>& \
  517. name = /* NOLINT */ \
  518. PhmapInternalInlineVariableHolder##name<>::kInstance; \
  519. static_assert(sizeof(void (*)(decltype(name))) != 0, \
  520. "Silence unused variable warnings.")
  521. #endif // __cpp_inline_variables
  522. // ----------- throw_delegate
  523. namespace phmap {
  524. namespace base_internal {
  525. namespace {
  526. #ifdef PHMAP_HAVE_EXCEPTIONS
  527. #define PHMAP_THROW_IMPL_MSG(e, message) throw e(message)
  528. #define PHMAP_THROW_IMPL(e) throw e()
  529. #else
  530. #define PHMAP_THROW_IMPL_MSG(e, message) do { (void)(message); std::abort(); } while(0)
  531. #define PHMAP_THROW_IMPL(e) std::abort()
  532. #endif
  533. } // namespace
  534. static LL_INLINE void ThrowStdLogicError(const std::string& what_arg) {
  535. PHMAP_THROW_IMPL_MSG(std::logic_error, what_arg);
  536. }
  537. static LL_INLINE void ThrowStdLogicError(const char* what_arg) {
  538. PHMAP_THROW_IMPL_MSG(std::logic_error, what_arg);
  539. }
  540. static LL_INLINE void ThrowStdInvalidArgument(const std::string& what_arg) {
  541. PHMAP_THROW_IMPL_MSG(std::invalid_argument, what_arg);
  542. }
  543. static LL_INLINE void ThrowStdInvalidArgument(const char* what_arg) {
  544. PHMAP_THROW_IMPL_MSG(std::invalid_argument, what_arg);
  545. }
  546. static LL_INLINE void ThrowStdDomainError(const std::string& what_arg) {
  547. PHMAP_THROW_IMPL_MSG(std::domain_error, what_arg);
  548. }
  549. static LL_INLINE void ThrowStdDomainError(const char* what_arg) {
  550. PHMAP_THROW_IMPL_MSG(std::domain_error, what_arg);
  551. }
  552. static LL_INLINE void ThrowStdLengthError(const std::string& what_arg) {
  553. PHMAP_THROW_IMPL_MSG(std::length_error, what_arg);
  554. }
  555. static LL_INLINE void ThrowStdLengthError(const char* what_arg) {
  556. PHMAP_THROW_IMPL_MSG(std::length_error, what_arg);
  557. }
  558. static LL_INLINE void ThrowStdOutOfRange(const std::string& what_arg) {
  559. PHMAP_THROW_IMPL_MSG(std::out_of_range, what_arg);
  560. }
  561. static LL_INLINE void ThrowStdOutOfRange(const char* what_arg) {
  562. PHMAP_THROW_IMPL_MSG(std::out_of_range, what_arg);
  563. }
  564. static LL_INLINE void ThrowStdRuntimeError(const std::string& what_arg) {
  565. PHMAP_THROW_IMPL_MSG(std::runtime_error, what_arg);
  566. }
  567. static LL_INLINE void ThrowStdRuntimeError(const char* what_arg) {
  568. PHMAP_THROW_IMPL_MSG(std::runtime_error, what_arg);
  569. }
  570. static LL_INLINE void ThrowStdRangeError(const std::string& what_arg) {
  571. PHMAP_THROW_IMPL_MSG(std::range_error, what_arg);
  572. }
  573. static LL_INLINE void ThrowStdRangeError(const char* what_arg) {
  574. PHMAP_THROW_IMPL_MSG(std::range_error, what_arg);
  575. }
  576. static LL_INLINE void ThrowStdOverflowError(const std::string& what_arg) {
  577. PHMAP_THROW_IMPL_MSG(std::overflow_error, what_arg);
  578. }
  579. static LL_INLINE void ThrowStdOverflowError(const char* what_arg) {
  580. PHMAP_THROW_IMPL_MSG(std::overflow_error, what_arg);
  581. }
  582. static LL_INLINE void ThrowStdUnderflowError(const std::string& what_arg) {
  583. PHMAP_THROW_IMPL_MSG(std::underflow_error, what_arg);
  584. }
  585. static LL_INLINE void ThrowStdUnderflowError(const char* what_arg) {
  586. PHMAP_THROW_IMPL_MSG(std::underflow_error, what_arg);
  587. }
  588. static LL_INLINE void ThrowStdBadFunctionCall() {
  589. PHMAP_THROW_IMPL(std::bad_function_call);
  590. }
  591. static LL_INLINE void ThrowStdBadAlloc() {
  592. PHMAP_THROW_IMPL(std::bad_alloc);
  593. }
  594. } // namespace base_internal
  595. } // namespace phmap
  596. // ----------- invoke.h
  597. namespace phmap {
  598. namespace base_internal {
  599. template <typename Derived>
  600. struct StrippedAccept
  601. {
  602. template <typename... Args>
  603. struct Accept : Derived::template AcceptImpl<typename std::remove_cv<
  604. typename std::remove_reference<Args>::type>::type...> {};
  605. };
  606. // (t1.*f)(t2, ..., tN) when f is a pointer to a member function of a class T
  607. // and t1 is an object of type T or a reference to an object of type T or a
  608. // reference to an object of a type derived from T.
  609. struct MemFunAndRef : StrippedAccept<MemFunAndRef>
  610. {
  611. template <typename... Args>
  612. struct AcceptImpl : std::false_type {};
  613. template <typename R, typename C, typename... Params, typename Obj,
  614. typename... Args>
  615. struct AcceptImpl<R (C::*)(Params...), Obj, Args...>
  616. : std::is_base_of<C, Obj> {};
  617. template <typename R, typename C, typename... Params, typename Obj,
  618. typename... Args>
  619. struct AcceptImpl<R (C::*)(Params...) const, Obj, Args...>
  620. : std::is_base_of<C, Obj> {};
  621. template <typename MemFun, typename Obj, typename... Args>
  622. static decltype((std::declval<Obj>().*
  623. std::declval<MemFun>())(std::declval<Args>()...))
  624. Invoke(MemFun&& mem_fun, Obj&& obj, Args&&... args) {
  625. return (std::forward<Obj>(obj).*
  626. std::forward<MemFun>(mem_fun))(std::forward<Args>(args)...);
  627. }
  628. };
  629. // ((*t1).*f)(t2, ..., tN) when f is a pointer to a member function of a
  630. // class T and t1 is not one of the types described in the previous item.
  631. struct MemFunAndPtr : StrippedAccept<MemFunAndPtr>
  632. {
  633. template <typename... Args>
  634. struct AcceptImpl : std::false_type {};
  635. template <typename R, typename C, typename... Params, typename Ptr,
  636. typename... Args>
  637. struct AcceptImpl<R (C::*)(Params...), Ptr, Args...>
  638. : std::integral_constant<bool, !std::is_base_of<C, Ptr>::value> {};
  639. template <typename R, typename C, typename... Params, typename Ptr,
  640. typename... Args>
  641. struct AcceptImpl<R (C::*)(Params...) const, Ptr, Args...>
  642. : std::integral_constant<bool, !std::is_base_of<C, Ptr>::value> {};
  643. template <typename MemFun, typename Ptr, typename... Args>
  644. static decltype(((*std::declval<Ptr>()).*
  645. std::declval<MemFun>())(std::declval<Args>()...))
  646. Invoke(MemFun&& mem_fun, Ptr&& ptr, Args&&... args) {
  647. return ((*std::forward<Ptr>(ptr)).*
  648. std::forward<MemFun>(mem_fun))(std::forward<Args>(args)...);
  649. }
  650. };
  651. // t1.*f when N == 1 and f is a pointer to member data of a class T and t1 is
  652. // an object of type T or a reference to an object of type T or a reference
  653. // to an object of a type derived from T.
  654. struct DataMemAndRef : StrippedAccept<DataMemAndRef>
  655. {
  656. template <typename... Args>
  657. struct AcceptImpl : std::false_type {};
  658. template <typename R, typename C, typename Obj>
  659. struct AcceptImpl<R C::*, Obj> : std::is_base_of<C, Obj> {};
  660. template <typename DataMem, typename Ref>
  661. static decltype(std::declval<Ref>().*std::declval<DataMem>()) Invoke(
  662. DataMem&& data_mem, Ref&& ref) {
  663. return std::forward<Ref>(ref).*std::forward<DataMem>(data_mem);
  664. }
  665. };
  666. // (*t1).*f when N == 1 and f is a pointer to member data of a class T and t1
  667. // is not one of the types described in the previous item.
  668. struct DataMemAndPtr : StrippedAccept<DataMemAndPtr>
  669. {
  670. template <typename... Args>
  671. struct AcceptImpl : std::false_type {};
  672. template <typename R, typename C, typename Ptr>
  673. struct AcceptImpl<R C::*, Ptr>
  674. : std::integral_constant<bool, !std::is_base_of<C, Ptr>::value> {};
  675. template <typename DataMem, typename Ptr>
  676. static decltype((*std::declval<Ptr>()).*std::declval<DataMem>()) Invoke(
  677. DataMem&& data_mem, Ptr&& ptr) {
  678. return (*std::forward<Ptr>(ptr)).*std::forward<DataMem>(data_mem);
  679. }
  680. };
  681. // f(t1, t2, ..., tN) in all other cases.
  682. struct Callable
  683. {
  684. // Callable doesn't have Accept because it's the last clause that gets picked
  685. // when none of the previous clauses are applicable.
  686. template <typename F, typename... Args>
  687. static decltype(std::declval<F>()(std::declval<Args>()...)) Invoke(
  688. F&& f, Args&&... args) {
  689. return std::forward<F>(f)(std::forward<Args>(args)...);
  690. }
  691. };
  692. // Resolves to the first matching clause.
  693. template <typename... Args>
  694. struct Invoker
  695. {
  696. typedef typename std::conditional<
  697. MemFunAndRef::Accept<Args...>::value, MemFunAndRef,
  698. typename std::conditional<
  699. MemFunAndPtr::Accept<Args...>::value, MemFunAndPtr,
  700. typename std::conditional<
  701. DataMemAndRef::Accept<Args...>::value, DataMemAndRef,
  702. typename std::conditional<DataMemAndPtr::Accept<Args...>::value,
  703. DataMemAndPtr, Callable>::type>::type>::
  704. type>::type type;
  705. };
  706. // The result type of Invoke<F, Args...>.
  707. template <typename F, typename... Args>
  708. using InvokeT = decltype(Invoker<F, Args...>::type::Invoke(
  709. std::declval<F>(), std::declval<Args>()...));
  710. // Invoke(f, args...) is an implementation of INVOKE(f, args...) from section
  711. // [func.require] of the C++ standard.
  712. template <typename F, typename... Args>
  713. InvokeT<F, Args...> Invoke(F&& f, Args&&... args) {
  714. return Invoker<F, Args...>::type::Invoke(std::forward<F>(f),
  715. std::forward<Args>(args)...);
  716. }
  717. } // namespace base_internal
  718. } // namespace phmap
  719. // ----------- utility.h
  720. namespace phmap {
  721. // integer_sequence
  722. //
  723. // Class template representing a compile-time integer sequence. An instantiation
  724. // of `integer_sequence<T, Ints...>` has a sequence of integers encoded in its
  725. // type through its template arguments (which is a common need when
  726. // working with C++11 variadic templates). `phmap::integer_sequence` is designed
  727. // to be a drop-in replacement for C++14's `std::integer_sequence`.
  728. //
  729. // Example:
  730. //
  731. // template< class T, T... Ints >
  732. // void user_function(integer_sequence<T, Ints...>);
  733. //
  734. // int main()
  735. // {
  736. // // user_function's `T` will be deduced to `int` and `Ints...`
  737. // // will be deduced to `0, 1, 2, 3, 4`.
  738. // user_function(make_integer_sequence<int, 5>());
  739. // }
  740. template <typename T, T... Ints>
  741. struct integer_sequence
  742. {
  743. using value_type = T;
  744. static constexpr size_t size() noexcept { return sizeof...(Ints); }
  745. };
  746. // index_sequence
  747. //
  748. // A helper template for an `integer_sequence` of `size_t`,
  749. // `phmap::index_sequence` is designed to be a drop-in replacement for C++14's
  750. // `std::index_sequence`.
  751. template <size_t... Ints>
  752. using index_sequence = integer_sequence<size_t, Ints...>;
  753. namespace utility_internal {
  754. template <typename Seq, size_t SeqSize, size_t Rem>
  755. struct Extend;
  756. // Note that SeqSize == sizeof...(Ints). It's passed explicitly for efficiency.
  757. template <typename T, T... Ints, size_t SeqSize>
  758. struct Extend<integer_sequence<T, Ints...>, SeqSize, 0> {
  759. using type = integer_sequence<T, Ints..., (Ints + SeqSize)...>;
  760. };
  761. template <typename T, T... Ints, size_t SeqSize>
  762. struct Extend<integer_sequence<T, Ints...>, SeqSize, 1> {
  763. using type = integer_sequence<T, Ints..., (Ints + SeqSize)..., 2 * SeqSize>;
  764. };
  765. // Recursion helper for 'make_integer_sequence<T, N>'.
  766. // 'Gen<T, N>::type' is an alias for 'integer_sequence<T, 0, 1, ... N-1>'.
  767. template <typename T, size_t N>
  768. struct Gen {
  769. using type =
  770. typename Extend<typename Gen<T, N / 2>::type, N / 2, N % 2>::type;
  771. };
  772. template <typename T>
  773. struct Gen<T, 0> {
  774. using type = integer_sequence<T>;
  775. };
  776. } // namespace utility_internal
  777. // Compile-time sequences of integers
  778. // make_integer_sequence
  779. //
  780. // This template alias is equivalent to
  781. // `integer_sequence<int, 0, 1, ..., N-1>`, and is designed to be a drop-in
  782. // replacement for C++14's `std::make_integer_sequence`.
  783. template <typename T, T N>
  784. using make_integer_sequence = typename utility_internal::Gen<T, N>::type;
  785. // make_index_sequence
  786. //
  787. // This template alias is equivalent to `index_sequence<0, 1, ..., N-1>`,
  788. // and is designed to be a drop-in replacement for C++14's
  789. // `std::make_index_sequence`.
  790. template <size_t N>
  791. using make_index_sequence = make_integer_sequence<size_t, N>;
  792. // index_sequence_for
  793. //
  794. // Converts a typename pack into an index sequence of the same length, and
  795. // is designed to be a drop-in replacement for C++14's
  796. // `std::index_sequence_for()`
  797. template <typename... Ts>
  798. using index_sequence_for = make_index_sequence<sizeof...(Ts)>;
  799. // Tag types
  800. #ifdef PHMAP_HAVE_STD_OPTIONAL
  801. using std::in_place_t;
  802. using std::in_place;
  803. #else // PHMAP_HAVE_STD_OPTIONAL
  804. // in_place_t
  805. //
  806. // Tag type used to specify in-place construction, such as with
  807. // `phmap::optional`, designed to be a drop-in replacement for C++17's
  808. // `std::in_place_t`.
  809. struct in_place_t {};
  810. PHMAP_INTERNAL_INLINE_CONSTEXPR(in_place_t, in_place, {});
  811. #endif // PHMAP_HAVE_STD_OPTIONAL
  812. #if defined(PHMAP_HAVE_STD_ANY) || defined(PHMAP_HAVE_STD_VARIANT)
  813. using std::in_place_type_t;
  814. #else
  815. // in_place_type_t
  816. //
  817. // Tag type used for in-place construction when the type to construct needs to
  818. // be specified, such as with `phmap::any`, designed to be a drop-in replacement
  819. // for C++17's `std::in_place_type_t`.
  820. template <typename T>
  821. struct in_place_type_t {};
  822. #endif // PHMAP_HAVE_STD_ANY || PHMAP_HAVE_STD_VARIANT
  823. #ifdef PHMAP_HAVE_STD_VARIANT
  824. using std::in_place_index_t;
  825. #else
  826. // in_place_index_t
  827. //
  828. // Tag type used for in-place construction when the type to construct needs to
  829. // be specified, such as with `phmap::any`, designed to be a drop-in replacement
  830. // for C++17's `std::in_place_index_t`.
  831. template <size_t I>
  832. struct in_place_index_t {};
  833. #endif // PHMAP_HAVE_STD_VARIANT
  834. // Constexpr move and forward
  835. // move()
  836. //
  837. // A constexpr version of `std::move()`, designed to be a drop-in replacement
  838. // for C++14's `std::move()`.
  839. template <typename T>
  840. constexpr phmap::remove_reference_t<T>&& move(T&& t) noexcept {
  841. return static_cast<phmap::remove_reference_t<T>&&>(t);
  842. }
  843. // forward()
  844. //
  845. // A constexpr version of `std::forward()`, designed to be a drop-in replacement
  846. // for C++14's `std::forward()`.
  847. template <typename T>
  848. constexpr T&& forward(
  849. phmap::remove_reference_t<T>& t) noexcept { // NOLINT(runtime/references)
  850. return static_cast<T&&>(t);
  851. }
  852. namespace utility_internal {
  853. // Helper method for expanding tuple into a called method.
  854. template <typename Functor, typename Tuple, std::size_t... Indexes>
  855. auto apply_helper(Functor&& functor, Tuple&& t, index_sequence<Indexes...>)
  856. -> decltype(phmap::base_internal::Invoke(
  857. phmap::forward<Functor>(functor),
  858. std::get<Indexes>(phmap::forward<Tuple>(t))...)) {
  859. return phmap::base_internal::Invoke(
  860. phmap::forward<Functor>(functor),
  861. std::get<Indexes>(phmap::forward<Tuple>(t))...);
  862. }
  863. } // namespace utility_internal
  864. // apply
  865. //
  866. // Invokes a Callable using elements of a tuple as its arguments.
  867. // Each element of the tuple corresponds to an argument of the call (in order).
  868. // Both the Callable argument and the tuple argument are perfect-forwarded.
  869. // For member-function Callables, the first tuple element acts as the `this`
  870. // pointer. `phmap::apply` is designed to be a drop-in replacement for C++17's
  871. // `std::apply`. Unlike C++17's `std::apply`, this is not currently `constexpr`.
  872. //
  873. // Example:
  874. //
  875. // class Foo {
  876. // public:
  877. // void Bar(int);
  878. // };
  879. // void user_function1(int, std::string);
  880. // void user_function2(std::unique_ptr<Foo>);
  881. // auto user_lambda = [](int, int) {};
  882. //
  883. // int main()
  884. // {
  885. // std::tuple<int, std::string> tuple1(42, "bar");
  886. // // Invokes the first user function on int, std::string.
  887. // phmap::apply(&user_function1, tuple1);
  888. //
  889. // std::tuple<std::unique_ptr<Foo>> tuple2(phmap::make_unique<Foo>());
  890. // // Invokes the user function that takes ownership of the unique
  891. // // pointer.
  892. // phmap::apply(&user_function2, std::move(tuple2));
  893. //
  894. // auto foo = phmap::make_unique<Foo>();
  895. // std::tuple<Foo*, int> tuple3(foo.get(), 42);
  896. // // Invokes the method Bar on foo with one argument, 42.
  897. // phmap::apply(&Foo::Bar, tuple3);
  898. //
  899. // std::tuple<int, int> tuple4(8, 9);
  900. // // Invokes a lambda.
  901. // phmap::apply(user_lambda, tuple4);
  902. // }
  903. template <typename Functor, typename Tuple>
  904. auto apply(Functor&& functor, Tuple&& t)
  905. -> decltype(utility_internal::apply_helper(
  906. phmap::forward<Functor>(functor), phmap::forward<Tuple>(t),
  907. phmap::make_index_sequence<std::tuple_size<
  908. typename std::remove_reference<Tuple>::type>::value>{})) {
  909. return utility_internal::apply_helper(
  910. phmap::forward<Functor>(functor), phmap::forward<Tuple>(t),
  911. phmap::make_index_sequence<std::tuple_size<
  912. typename std::remove_reference<Tuple>::type>::value>{});
  913. }
  914. #ifdef _MSC_VER
  915. #pragma warning(push)
  916. #pragma warning(disable : 4365) // '=': conversion from 'T' to 'T', signed/unsigned mismatch
  917. #endif // _MSC_VER
  918. // exchange
  919. //
  920. // Replaces the value of `obj` with `new_value` and returns the old value of
  921. // `obj`. `phmap::exchange` is designed to be a drop-in replacement for C++14's
  922. // `std::exchange`.
  923. //
  924. // Example:
  925. //
  926. // Foo& operator=(Foo&& other) {
  927. // ptr1_ = phmap::exchange(other.ptr1_, nullptr);
  928. // int1_ = phmap::exchange(other.int1_, -1);
  929. // return *this;
  930. // }
  931. template <typename T, typename U = T>
  932. T exchange(T& obj, U&& new_value)
  933. {
  934. T old_value = phmap::move(obj);
  935. obj = phmap::forward<U>(new_value);
  936. return old_value;
  937. }
  938. #ifdef _MSC_VER
  939. #pragma warning(pop)
  940. #endif // _MSC_VER
  941. } // namespace phmap
  942. // -----------------------------------------------------------------------------
  943. // memory.h
  944. // -----------------------------------------------------------------------------
  945. namespace phmap {
  946. template <typename T>
  947. std::unique_ptr<T> WrapUnique(T* ptr)
  948. {
  949. static_assert(!std::is_array<T>::value, "array types are unsupported");
  950. static_assert(std::is_object<T>::value, "non-object types are unsupported");
  951. return std::unique_ptr<T>(ptr);
  952. }
  953. namespace memory_internal {
  954. // Traits to select proper overload and return type for `phmap::make_unique<>`.
  955. template <typename T>
  956. struct MakeUniqueResult {
  957. using scalar = std::unique_ptr<T>;
  958. };
  959. template <typename T>
  960. struct MakeUniqueResult<T[]> {
  961. using array = std::unique_ptr<T[]>;
  962. };
  963. template <typename T, size_t N>
  964. struct MakeUniqueResult<T[N]> {
  965. using invalid = void;
  966. };
  967. } // namespace memory_internal
  968. #if (__cplusplus > 201103L || defined(_MSC_VER)) && \
  969. !(defined(__GNUC__) && __GNUC__ == 4 && __GNUC_MINOR__ == 8)
  970. using std::make_unique;
  971. #else
  972. template <typename T, typename... Args>
  973. typename memory_internal::MakeUniqueResult<T>::scalar make_unique(
  974. Args&&... args) {
  975. return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
  976. }
  977. template <typename T>
  978. typename memory_internal::MakeUniqueResult<T>::array make_unique(size_t n) {
  979. return std::unique_ptr<T>(new typename phmap::remove_extent_t<T>[n]());
  980. }
  981. template <typename T, typename... Args>
  982. typename memory_internal::MakeUniqueResult<T>::invalid make_unique(
  983. Args&&... /* args */) = delete;
  984. #endif
  985. template <typename T>
  986. auto RawPtr(T&& ptr) -> decltype(std::addressof(*ptr))
  987. {
  988. // ptr is a forwarding reference to support Ts with non-const operators.
  989. return (ptr != nullptr) ? std::addressof(*ptr) : nullptr;
  990. }
  991. LL_INLINE std::nullptr_t RawPtr(std::nullptr_t) { return nullptr; }
  992. template <typename T, typename D>
  993. std::shared_ptr<T> ShareUniquePtr(std::unique_ptr<T, D>&& ptr) {
  994. return ptr ? std::shared_ptr<T>(std::move(ptr)) : std::shared_ptr<T>();
  995. }
  996. template <typename T>
  997. std::weak_ptr<T> WeakenPtr(const std::shared_ptr<T>& ptr) {
  998. return std::weak_ptr<T>(ptr);
  999. }
  1000. namespace memory_internal {
  1001. // ExtractOr<E, O, D>::type evaluates to E<O> if possible. Otherwise, D.
  1002. template <template <typename> class Extract, typename Obj, typename Default,
  1003. typename>
  1004. struct ExtractOr {
  1005. using type = Default;
  1006. };
  1007. template <template <typename> class Extract, typename Obj, typename Default>
  1008. struct ExtractOr<Extract, Obj, Default, void_t<Extract<Obj>>> {
  1009. using type = Extract<Obj>;
  1010. };
  1011. template <template <typename> class Extract, typename Obj, typename Default>
  1012. using ExtractOrT = typename ExtractOr<Extract, Obj, Default, void>::type;
  1013. // Extractors for the features of allocators.
  1014. template <typename T>
  1015. using GetPointer = typename T::pointer;
  1016. template <typename T>
  1017. using GetConstPointer = typename T::const_pointer;
  1018. template <typename T>
  1019. using GetVoidPointer = typename T::void_pointer;
  1020. template <typename T>
  1021. using GetConstVoidPointer = typename T::const_void_pointer;
  1022. template <typename T>
  1023. using GetDifferenceType = typename T::difference_type;
  1024. template <typename T>
  1025. using GetSizeType = typename T::size_type;
  1026. template <typename T>
  1027. using GetPropagateOnContainerCopyAssignment =
  1028. typename T::propagate_on_container_copy_assignment;
  1029. template <typename T>
  1030. using GetPropagateOnContainerMoveAssignment =
  1031. typename T::propagate_on_container_move_assignment;
  1032. template <typename T>
  1033. using GetPropagateOnContainerSwap = typename T::propagate_on_container_swap;
  1034. template <typename T>
  1035. using GetIsAlwaysEqual = typename T::is_always_equal;
  1036. template <typename T>
  1037. struct GetFirstArg;
  1038. template <template <typename...> class Class, typename T, typename... Args>
  1039. struct GetFirstArg<Class<T, Args...>> {
  1040. using type = T;
  1041. };
  1042. template <typename Ptr, typename = void>
  1043. struct ElementType {
  1044. using type = typename GetFirstArg<Ptr>::type;
  1045. };
  1046. template <typename T>
  1047. struct ElementType<T, void_t<typename T::element_type>> {
  1048. using type = typename T::element_type;
  1049. };
  1050. template <typename T, typename U>
  1051. struct RebindFirstArg;
  1052. template <template <typename...> class Class, typename T, typename... Args,
  1053. typename U>
  1054. struct RebindFirstArg<Class<T, Args...>, U> {
  1055. using type = Class<U, Args...>;
  1056. };
  1057. template <typename T, typename U, typename = void>
  1058. struct RebindPtr {
  1059. using type = typename RebindFirstArg<T, U>::type;
  1060. };
  1061. template <typename T, typename U>
  1062. struct RebindPtr<T, U, void_t<typename T::template rebind<U>>> {
  1063. using type = typename T::template rebind<U>;
  1064. };
  1065. template <typename T, typename U>
  1066. constexpr bool HasRebindAlloc(...) {
  1067. return false;
  1068. }
  1069. template <typename T, typename U>
  1070. constexpr bool HasRebindAlloc(typename std::allocator_traits<T>::template rebind_alloc<U>*) {
  1071. return true;
  1072. }
  1073. template <typename T, typename U, bool = HasRebindAlloc<T, U>(nullptr)>
  1074. struct RebindAlloc {
  1075. using type = typename RebindFirstArg<T, U>::type;
  1076. };
  1077. template <typename A, typename U>
  1078. struct RebindAlloc<A, U, true> {
  1079. using type = typename std::allocator_traits<A>::template rebind_alloc<U>;
  1080. };
  1081. } // namespace memory_internal
  1082. template <typename Ptr>
  1083. struct pointer_traits
  1084. {
  1085. using pointer = Ptr;
  1086. // element_type:
  1087. // Ptr::element_type if present. Otherwise T if Ptr is a template
  1088. // instantiation Template<T, Args...>
  1089. using element_type = typename memory_internal::ElementType<Ptr>::type;
  1090. // difference_type:
  1091. // Ptr::difference_type if present, otherwise std::ptrdiff_t
  1092. using difference_type =
  1093. memory_internal::ExtractOrT<memory_internal::GetDifferenceType, Ptr,
  1094. std::ptrdiff_t>;
  1095. // rebind:
  1096. // Ptr::rebind<U> if exists, otherwise Template<U, Args...> if Ptr is a
  1097. // template instantiation Template<T, Args...>
  1098. template <typename U>
  1099. using rebind = typename memory_internal::RebindPtr<Ptr, U>::type;
  1100. // pointer_to:
  1101. // Calls Ptr::pointer_to(r)
  1102. static pointer pointer_to(element_type& r) { // NOLINT(runtime/references)
  1103. return Ptr::pointer_to(r);
  1104. }
  1105. };
  1106. // Specialization for T*.
  1107. template <typename T>
  1108. struct pointer_traits<T*>
  1109. {
  1110. using pointer = T*;
  1111. using element_type = T;
  1112. using difference_type = std::ptrdiff_t;
  1113. template <typename U>
  1114. using rebind = U*;
  1115. // pointer_to:
  1116. // Calls std::addressof(r)
  1117. static pointer pointer_to(
  1118. element_type& r) noexcept { // NOLINT(runtime/references)
  1119. return std::addressof(r);
  1120. }
  1121. };
  1122. // -----------------------------------------------------------------------------
  1123. // Class Template: allocator_traits
  1124. // -----------------------------------------------------------------------------
  1125. //
  1126. // A C++11 compatible implementation of C++17's std::allocator_traits.
  1127. //
  1128. template <typename Alloc>
  1129. struct allocator_traits
  1130. {
  1131. using allocator_type = Alloc;
  1132. // value_type:
  1133. // Alloc::value_type
  1134. using value_type = typename Alloc::value_type;
  1135. // pointer:
  1136. // Alloc::pointer if present, otherwise value_type*
  1137. using pointer = memory_internal::ExtractOrT<memory_internal::GetPointer,
  1138. Alloc, value_type*>;
  1139. // const_pointer:
  1140. // Alloc::const_pointer if present, otherwise
  1141. // phmap::pointer_traits<pointer>::rebind<const value_type>
  1142. using const_pointer =
  1143. memory_internal::ExtractOrT<memory_internal::GetConstPointer, Alloc,
  1144. typename phmap::pointer_traits<pointer>::
  1145. template rebind<const value_type>>;
  1146. // void_pointer:
  1147. // Alloc::void_pointer if present, otherwise
  1148. // phmap::pointer_traits<pointer>::rebind<void>
  1149. using void_pointer = memory_internal::ExtractOrT<
  1150. memory_internal::GetVoidPointer, Alloc,
  1151. typename phmap::pointer_traits<pointer>::template rebind<void>>;
  1152. // const_void_pointer:
  1153. // Alloc::const_void_pointer if present, otherwise
  1154. // phmap::pointer_traits<pointer>::rebind<const void>
  1155. using const_void_pointer = memory_internal::ExtractOrT<
  1156. memory_internal::GetConstVoidPointer, Alloc,
  1157. typename phmap::pointer_traits<pointer>::template rebind<const void>>;
  1158. // difference_type:
  1159. // Alloc::difference_type if present, otherwise
  1160. // phmap::pointer_traits<pointer>::difference_type
  1161. using difference_type = memory_internal::ExtractOrT<
  1162. memory_internal::GetDifferenceType, Alloc,
  1163. typename phmap::pointer_traits<pointer>::difference_type>;
  1164. // size_type:
  1165. // Alloc::size_type if present, otherwise
  1166. // std::make_unsigned<difference_type>::type
  1167. using size_type = memory_internal::ExtractOrT<
  1168. memory_internal::GetSizeType, Alloc,
  1169. typename std::make_unsigned<difference_type>::type>;
  1170. // propagate_on_container_copy_assignment:
  1171. // Alloc::propagate_on_container_copy_assignment if present, otherwise
  1172. // std::false_type
  1173. using propagate_on_container_copy_assignment = memory_internal::ExtractOrT<
  1174. memory_internal::GetPropagateOnContainerCopyAssignment, Alloc,
  1175. std::false_type>;
  1176. // propagate_on_container_move_assignment:
  1177. // Alloc::propagate_on_container_move_assignment if present, otherwise
  1178. // std::false_type
  1179. using propagate_on_container_move_assignment = memory_internal::ExtractOrT<
  1180. memory_internal::GetPropagateOnContainerMoveAssignment, Alloc,
  1181. std::false_type>;
  1182. // propagate_on_container_swap:
  1183. // Alloc::propagate_on_container_swap if present, otherwise std::false_type
  1184. using propagate_on_container_swap =
  1185. memory_internal::ExtractOrT<memory_internal::GetPropagateOnContainerSwap,
  1186. Alloc, std::false_type>;
  1187. // is_always_equal:
  1188. // Alloc::is_always_equal if present, otherwise std::is_empty<Alloc>::type
  1189. using is_always_equal =
  1190. memory_internal::ExtractOrT<memory_internal::GetIsAlwaysEqual, Alloc,
  1191. typename std::is_empty<Alloc>::type>;
  1192. // rebind_alloc:
  1193. // Alloc::rebind<T>::other if present, otherwise Alloc<T, Args> if this Alloc
  1194. // is Alloc<U, Args>
  1195. template <typename T>
  1196. using rebind_alloc = typename memory_internal::RebindAlloc<Alloc, T>::type;
  1197. // rebind_traits:
  1198. // phmap::allocator_traits<rebind_alloc<T>>
  1199. template <typename T>
  1200. using rebind_traits = phmap::allocator_traits<rebind_alloc<T>>;
  1201. // allocate(Alloc& a, size_type n):
  1202. // Calls a.allocate(n)
  1203. static pointer allocate(Alloc& a, // NOLINT(runtime/references)
  1204. size_type n) {
  1205. return a.allocate(n);
  1206. }
  1207. // allocate(Alloc& a, size_type n, const_void_pointer hint):
  1208. // Calls a.allocate(n, hint) if possible.
  1209. // If not possible, calls a.allocate(n)
  1210. static pointer allocate(Alloc& a, size_type n, // NOLINT(runtime/references)
  1211. const_void_pointer hint) {
  1212. return allocate_impl(0, a, n, hint);
  1213. }
  1214. // deallocate(Alloc& a, pointer p, size_type n):
  1215. // Calls a.deallocate(p, n)
  1216. static void deallocate(Alloc& a, pointer p, // NOLINT(runtime/references)
  1217. size_type n) {
  1218. a.deallocate(p, n);
  1219. }
  1220. // construct(Alloc& a, T* p, Args&&... args):
  1221. // Calls a.construct(p, std::forward<Args>(args)...) if possible.
  1222. // If not possible, calls
  1223. // ::new (static_cast<void*>(p)) T(std::forward<Args>(args)...)
  1224. template <typename T, typename... Args>
  1225. static void construct(Alloc& a, T* p, // NOLINT(runtime/references)
  1226. Args&&... args) {
  1227. construct_impl(0, a, p, std::forward<Args>(args)...);
  1228. }
  1229. // destroy(Alloc& a, T* p):
  1230. // Calls a.destroy(p) if possible. If not possible, calls p->~T().
  1231. template <typename T>
  1232. static void destroy(Alloc& a, T* p) { // NOLINT(runtime/references)
  1233. destroy_impl(0, a, p);
  1234. }
  1235. // max_size(const Alloc& a):
  1236. // Returns a.max_size() if possible. If not possible, returns
  1237. // std::numeric_limits<size_type>::max() / sizeof(value_type)
  1238. static size_type max_size(const Alloc& a) { return max_size_impl(0, a); }
  1239. // select_on_container_copy_construction(const Alloc& a):
  1240. // Returns a.select_on_container_copy_construction() if possible.
  1241. // If not possible, returns a.
  1242. static Alloc select_on_container_copy_construction(const Alloc& a) {
  1243. return select_on_container_copy_construction_impl(0, a);
  1244. }
  1245. private:
  1246. template <typename A>
  1247. static auto allocate_impl(int, A& a, // NOLINT(runtime/references)
  1248. size_type n, const_void_pointer hint)
  1249. -> decltype(a.allocate(n, hint)) {
  1250. return a.allocate(n, hint);
  1251. }
  1252. static pointer allocate_impl(char, Alloc& a, // NOLINT(runtime/references)
  1253. size_type n, const_void_pointer) {
  1254. return a.allocate(n);
  1255. }
  1256. template <typename A, typename... Args>
  1257. static auto construct_impl(int, A& a, // NOLINT(runtime/references)
  1258. Args&&... args)
  1259. -> decltype(std::allocator_traits<A>::construct(a, std::forward<Args>(args)...)) {
  1260. std::allocator_traits<A>::construct(a, std::forward<Args>(args)...);
  1261. }
  1262. template <typename T, typename... Args>
  1263. static void construct_impl(char, Alloc&, T* p, Args&&... args) {
  1264. ::new (static_cast<void*>(p)) T(std::forward<Args>(args)...);
  1265. }
  1266. template <typename A, typename T>
  1267. static auto destroy_impl(int, A& a, // NOLINT(runtime/references)
  1268. T* p) -> decltype(std::allocator_traits<A>::destroy(a, p)) {
  1269. std::allocator_traits<A>::destroy(a, p);
  1270. }
  1271. template <typename T>
  1272. static void destroy_impl(char, Alloc&, T* p) {
  1273. p->~T();
  1274. }
  1275. template <typename A>
  1276. static auto max_size_impl(int, const A& a) -> decltype(a.max_size()) {
  1277. return a.max_size();
  1278. }
  1279. static size_type max_size_impl(char, const Alloc&) {
  1280. return (std::numeric_limits<size_type>::max)() / sizeof(value_type);
  1281. }
  1282. template <typename A>
  1283. static auto select_on_container_copy_construction_impl(int, const A& a)
  1284. -> decltype(a.select_on_container_copy_construction()) {
  1285. return a.select_on_container_copy_construction();
  1286. }
  1287. static Alloc select_on_container_copy_construction_impl(char,
  1288. const Alloc& a) {
  1289. return a;
  1290. }
  1291. };
  1292. namespace memory_internal {
  1293. // This template alias transforms Alloc::is_nothrow into a metafunction with
  1294. // Alloc as a parameter so it can be used with ExtractOrT<>.
  1295. template <typename Alloc>
  1296. using GetIsNothrow = typename Alloc::is_nothrow;
  1297. } // namespace memory_internal
  1298. // PHMAP_ALLOCATOR_NOTHROW is a build time configuration macro for user to
  1299. // specify whether the default allocation function can throw or never throws.
  1300. // If the allocation function never throws, user should define it to a non-zero
  1301. // value (e.g. via `-DPHMAP_ALLOCATOR_NOTHROW`).
  1302. // If the allocation function can throw, user should leave it undefined or
  1303. // define it to zero.
  1304. //
  1305. // allocator_is_nothrow<Alloc> is a traits class that derives from
  1306. // Alloc::is_nothrow if present, otherwise std::false_type. It's specialized
  1307. // for Alloc = std::allocator<T> for any type T according to the state of
  1308. // PHMAP_ALLOCATOR_NOTHROW.
  1309. //
  1310. // default_allocator_is_nothrow is a class that derives from std::true_type
  1311. // when the default allocator (global operator new) never throws, and
  1312. // std::false_type when it can throw. It is a convenience shorthand for writing
  1313. // allocator_is_nothrow<std::allocator<T>> (T can be any type).
  1314. // NOTE: allocator_is_nothrow<std::allocator<T>> is guaranteed to derive from
  1315. // the same type for all T, because users should specialize neither
  1316. // allocator_is_nothrow nor std::allocator.
  1317. template <typename Alloc>
  1318. struct allocator_is_nothrow
  1319. : memory_internal::ExtractOrT<memory_internal::GetIsNothrow, Alloc,
  1320. std::false_type> {};
  1321. #if defined(PHMAP_ALLOCATOR_NOTHROW) && PHMAP_ALLOCATOR_NOTHROW
  1322. template <typename T>
  1323. struct allocator_is_nothrow<std::allocator<T>> : std::true_type {};
  1324. struct default_allocator_is_nothrow : std::true_type {};
  1325. #else
  1326. struct default_allocator_is_nothrow : std::false_type {};
  1327. #endif
  1328. namespace memory_internal {
  1329. template <typename Allocator, typename Iterator, typename... Args>
  1330. void ConstructRange(Allocator& alloc, Iterator first, Iterator last,
  1331. const Args&... args)
  1332. {
  1333. for (Iterator cur = first; cur != last; ++cur) {
  1334. PHMAP_INTERNAL_TRY {
  1335. std::allocator_traits<Allocator>::construct(alloc, std::addressof(*cur),
  1336. args...);
  1337. }
  1338. PHMAP_INTERNAL_CATCH_ANY {
  1339. while (cur != first) {
  1340. --cur;
  1341. std::allocator_traits<Allocator>::destroy(alloc, std::addressof(*cur));
  1342. }
  1343. PHMAP_INTERNAL_RETHROW;
  1344. }
  1345. }
  1346. }
  1347. template <typename Allocator, typename Iterator, typename InputIterator>
  1348. void CopyRange(Allocator& alloc, Iterator destination, InputIterator first,
  1349. InputIterator last)
  1350. {
  1351. for (Iterator cur = destination; first != last;
  1352. static_cast<void>(++cur), static_cast<void>(++first)) {
  1353. PHMAP_INTERNAL_TRY {
  1354. std::allocator_traits<Allocator>::construct(alloc, std::addressof(*cur),
  1355. *first);
  1356. }
  1357. PHMAP_INTERNAL_CATCH_ANY {
  1358. while (cur != destination) {
  1359. --cur;
  1360. std::allocator_traits<Allocator>::destroy(alloc, std::addressof(*cur));
  1361. }
  1362. PHMAP_INTERNAL_RETHROW;
  1363. }
  1364. }
  1365. }
  1366. } // namespace memory_internal
  1367. } // namespace phmap
  1368. // -----------------------------------------------------------------------------
  1369. // optional.h
  1370. // -----------------------------------------------------------------------------
  1371. #ifdef PHMAP_HAVE_STD_OPTIONAL
  1372. #include <optional> // IWYU pragma: export
  1373. namespace phmap {
  1374. using std::bad_optional_access;
  1375. using std::optional;
  1376. using std::make_optional;
  1377. using std::nullopt_t;
  1378. using std::nullopt;
  1379. } // namespace phmap
  1380. #else
  1381. #if defined(__clang__)
  1382. #if __has_feature(cxx_inheriting_constructors)
  1383. #define PHMAP_OPTIONAL_USE_INHERITING_CONSTRUCTORS 1
  1384. #endif
  1385. #elif (defined(__GNUC__) && \
  1386. (__GNUC__ > 4 || __GNUC__ == 4 && __GNUC_MINOR__ >= 8)) || \
  1387. (__cpp_inheriting_constructors >= 200802) || \
  1388. (defined(_MSC_VER) && _MSC_VER >= 1910)
  1389. #define PHMAP_OPTIONAL_USE_INHERITING_CONSTRUCTORS 1
  1390. #endif
  1391. namespace phmap {
  1392. class bad_optional_access : public std::exception
  1393. {
  1394. public:
  1395. bad_optional_access() = default;
  1396. ~bad_optional_access() override;
  1397. const char* what() const noexcept override;
  1398. };
  1399. template <typename T>
  1400. class optional;
  1401. // --------------------------------
  1402. struct nullopt_t
  1403. {
  1404. struct init_t {};
  1405. static init_t init;
  1406. explicit constexpr nullopt_t(init_t& /*unused*/) {}
  1407. };
  1408. constexpr nullopt_t nullopt(nullopt_t::init);
  1409. namespace optional_internal {
  1410. // throw delegator
  1411. [[noreturn]] void throw_bad_optional_access();
  1412. struct empty_struct {};
  1413. // This class stores the data in optional<T>.
  1414. // It is specialized based on whether T is trivially destructible.
  1415. // This is the specialization for non trivially destructible type.
  1416. template <typename T, bool unused = std::is_trivially_destructible<T>::value>
  1417. class optional_data_dtor_base
  1418. {
  1419. struct dummy_type {
  1420. static_assert(sizeof(T) % sizeof(empty_struct) == 0, "");
  1421. // Use an array to avoid GCC 6 placement-new warning.
  1422. empty_struct data[sizeof(T) / sizeof(empty_struct)];
  1423. };
  1424. protected:
  1425. // Whether there is data or not.
  1426. bool engaged_;
  1427. // Data storage
  1428. union {
  1429. dummy_type dummy_;
  1430. T data_;
  1431. };
  1432. void destruct() noexcept {
  1433. if (engaged_) {
  1434. data_.~T();
  1435. engaged_ = false;
  1436. }
  1437. }
  1438. // dummy_ must be initialized for constexpr constructor.
  1439. constexpr optional_data_dtor_base() noexcept : engaged_(false), dummy_{{}} {}
  1440. template <typename... Args>
  1441. constexpr explicit optional_data_dtor_base(in_place_t, Args&&... args)
  1442. : engaged_(true), data_(phmap::forward<Args>(args)...) {}
  1443. ~optional_data_dtor_base() { destruct(); }
  1444. };
  1445. // Specialization for trivially destructible type.
  1446. template <typename T>
  1447. class optional_data_dtor_base<T, true>
  1448. {
  1449. struct dummy_type {
  1450. static_assert(sizeof(T) % sizeof(empty_struct) == 0, "");
  1451. // Use array to avoid GCC 6 placement-new warning.
  1452. empty_struct data[sizeof(T) / sizeof(empty_struct)];
  1453. };
  1454. protected:
  1455. // Whether there is data or not.
  1456. bool engaged_;
  1457. // Data storage
  1458. union {
  1459. dummy_type dummy_;
  1460. T data_;
  1461. };
  1462. void destruct() noexcept { engaged_ = false; }
  1463. // dummy_ must be initialized for constexpr constructor.
  1464. constexpr optional_data_dtor_base() noexcept : engaged_(false), dummy_{{}} {}
  1465. template <typename... Args>
  1466. constexpr explicit optional_data_dtor_base(in_place_t, Args&&... args)
  1467. : engaged_(true), data_(phmap::forward<Args>(args)...) {}
  1468. };
  1469. template <typename T>
  1470. class optional_data_base : public optional_data_dtor_base<T>
  1471. {
  1472. protected:
  1473. using base = optional_data_dtor_base<T>;
  1474. #if PHMAP_OPTIONAL_USE_INHERITING_CONSTRUCTORS
  1475. using base::base;
  1476. #else
  1477. optional_data_base() = default;
  1478. template <typename... Args>
  1479. constexpr explicit optional_data_base(in_place_t t, Args&&... args)
  1480. : base(t, phmap::forward<Args>(args)...) {}
  1481. #endif
  1482. template <typename... Args>
  1483. void construct(Args&&... args) {
  1484. // Use dummy_'s address to work around casting cv-qualified T* to void*.
  1485. ::new (static_cast<void*>(&this->dummy_)) T(std::forward<Args>(args)...);
  1486. this->engaged_ = true;
  1487. }
  1488. template <typename U>
  1489. void assign(U&& u) {
  1490. if (this->engaged_) {
  1491. this->data_ = std::forward<U>(u);
  1492. } else {
  1493. construct(std::forward<U>(u));
  1494. }
  1495. }
  1496. };
  1497. // TODO: Add another class using
  1498. // std::is_trivially_move_constructible trait when available to match
  1499. // http://cplusplus.github.io/LWG/lwg-defects.html#2900, for types that
  1500. // have trivial move but nontrivial copy.
  1501. // Also, we should be checking is_trivially_copyable here, which is not
  1502. // supported now, so we use is_trivially_* traits instead.
  1503. template <typename T,
  1504. bool unused =
  1505. std::is_trivially_copy_constructible<T>::value &&
  1506. std::is_trivially_copy_assignable<typename std::remove_cv<T>::type>::value &&
  1507. std::is_trivially_destructible<T>::value>
  1508. class optional_data;
  1509. // Trivially copyable types
  1510. template <typename T>
  1511. class optional_data<T, true> : public optional_data_base<T>
  1512. {
  1513. protected:
  1514. #if PHMAP_OPTIONAL_USE_INHERITING_CONSTRUCTORS
  1515. using optional_data_base<T>::optional_data_base;
  1516. #else
  1517. optional_data() = default;
  1518. template <typename... Args>
  1519. constexpr explicit optional_data(in_place_t t, Args&&... args)
  1520. : optional_data_base<T>(t, phmap::forward<Args>(args)...) {}
  1521. #endif
  1522. };
  1523. template <typename T>
  1524. class optional_data<T, false> : public optional_data_base<T>
  1525. {
  1526. protected:
  1527. #if PHMAP_OPTIONAL_USE_INHERITING_CONSTRUCTORS
  1528. using optional_data_base<T>::optional_data_base;
  1529. #else
  1530. template <typename... Args>
  1531. constexpr explicit optional_data(in_place_t t, Args&&... args)
  1532. : optional_data_base<T>(t, phmap::forward<Args>(args)...) {}
  1533. #endif
  1534. optional_data() = default;
  1535. optional_data(const optional_data& rhs) : optional_data_base<T>() {
  1536. if (rhs.engaged_) {
  1537. this->construct(rhs.data_);
  1538. }
  1539. }
  1540. optional_data(optional_data&& rhs) noexcept(
  1541. phmap::default_allocator_is_nothrow::value ||
  1542. std::is_nothrow_move_constructible<T>::value)
  1543. : optional_data_base<T>() {
  1544. if (rhs.engaged_) {
  1545. this->construct(std::move(rhs.data_));
  1546. }
  1547. }
  1548. optional_data& operator=(const optional_data& rhs) {
  1549. if (rhs.engaged_) {
  1550. this->assign(rhs.data_);
  1551. } else {
  1552. this->destruct();
  1553. }
  1554. return *this;
  1555. }
  1556. optional_data& operator=(optional_data&& rhs) noexcept(
  1557. std::is_nothrow_move_assignable<T>::value&&
  1558. std::is_nothrow_move_constructible<T>::value) {
  1559. if (rhs.engaged_) {
  1560. this->assign(std::move(rhs.data_));
  1561. } else {
  1562. this->destruct();
  1563. }
  1564. return *this;
  1565. }
  1566. };
  1567. // Ordered by level of restriction, from low to high.
  1568. // Copyable implies movable.
  1569. enum class copy_traits { copyable = 0, movable = 1, non_movable = 2 };
  1570. // Base class for enabling/disabling copy/move constructor.
  1571. template <copy_traits>
  1572. class optional_ctor_base;
  1573. template <>
  1574. class optional_ctor_base<copy_traits::copyable>
  1575. {
  1576. public:
  1577. constexpr optional_ctor_base() = default;
  1578. optional_ctor_base(const optional_ctor_base&) = default;
  1579. optional_ctor_base(optional_ctor_base&&) = default;
  1580. optional_ctor_base& operator=(const optional_ctor_base&) = default;
  1581. optional_ctor_base& operator=(optional_ctor_base&&) = default;
  1582. };
  1583. template <>
  1584. class optional_ctor_base<copy_traits::movable>
  1585. {
  1586. public:
  1587. constexpr optional_ctor_base() = default;
  1588. optional_ctor_base(const optional_ctor_base&) = delete;
  1589. optional_ctor_base(optional_ctor_base&&) = default;
  1590. optional_ctor_base& operator=(const optional_ctor_base&) = default;
  1591. optional_ctor_base& operator=(optional_ctor_base&&) = default;
  1592. };
  1593. template <>
  1594. class optional_ctor_base<copy_traits::non_movable>
  1595. {
  1596. public:
  1597. constexpr optional_ctor_base() = default;
  1598. optional_ctor_base(const optional_ctor_base&) = delete;
  1599. optional_ctor_base(optional_ctor_base&&) = delete;
  1600. optional_ctor_base& operator=(const optional_ctor_base&) = default;
  1601. optional_ctor_base& operator=(optional_ctor_base&&) = default;
  1602. };
  1603. // Base class for enabling/disabling copy/move assignment.
  1604. template <copy_traits>
  1605. class optional_assign_base;
  1606. template <>
  1607. class optional_assign_base<copy_traits::copyable>
  1608. {
  1609. public:
  1610. constexpr optional_assign_base() = default;
  1611. optional_assign_base(const optional_assign_base&) = default;
  1612. optional_assign_base(optional_assign_base&&) = default;
  1613. optional_assign_base& operator=(const optional_assign_base&) = default;
  1614. optional_assign_base& operator=(optional_assign_base&&) = default;
  1615. };
  1616. template <>
  1617. class optional_assign_base<copy_traits::movable>
  1618. {
  1619. public:
  1620. constexpr optional_assign_base() = default;
  1621. optional_assign_base(const optional_assign_base&) = default;
  1622. optional_assign_base(optional_assign_base&&) = default;
  1623. optional_assign_base& operator=(const optional_assign_base&) = delete;
  1624. optional_assign_base& operator=(optional_assign_base&&) = default;
  1625. };
  1626. template <>
  1627. class optional_assign_base<copy_traits::non_movable>
  1628. {
  1629. public:
  1630. constexpr optional_assign_base() = default;
  1631. optional_assign_base(const optional_assign_base&) = default;
  1632. optional_assign_base(optional_assign_base&&) = default;
  1633. optional_assign_base& operator=(const optional_assign_base&) = delete;
  1634. optional_assign_base& operator=(optional_assign_base&&) = delete;
  1635. };
  1636. template <typename T>
  1637. constexpr copy_traits get_ctor_copy_traits()
  1638. {
  1639. return std::is_copy_constructible<T>::value
  1640. ? copy_traits::copyable
  1641. : std::is_move_constructible<T>::value ? copy_traits::movable
  1642. : copy_traits::non_movable;
  1643. }
  1644. template <typename T>
  1645. constexpr copy_traits get_assign_copy_traits()
  1646. {
  1647. return phmap::is_copy_assignable<T>::value &&
  1648. std::is_copy_constructible<T>::value
  1649. ? copy_traits::copyable
  1650. : phmap::is_move_assignable<T>::value &&
  1651. std::is_move_constructible<T>::value
  1652. ? copy_traits::movable
  1653. : copy_traits::non_movable;
  1654. }
  1655. // Whether T is constructible or convertible from optional<U>.
  1656. template <typename T, typename U>
  1657. struct is_constructible_convertible_from_optional
  1658. : std::integral_constant<
  1659. bool, std::is_constructible<T, optional<U>&>::value ||
  1660. std::is_constructible<T, optional<U>&&>::value ||
  1661. std::is_constructible<T, const optional<U>&>::value ||
  1662. std::is_constructible<T, const optional<U>&&>::value ||
  1663. std::is_convertible<optional<U>&, T>::value ||
  1664. std::is_convertible<optional<U>&&, T>::value ||
  1665. std::is_convertible<const optional<U>&, T>::value ||
  1666. std::is_convertible<const optional<U>&&, T>::value> {};
  1667. // Whether T is constructible or convertible or assignable from optional<U>.
  1668. template <typename T, typename U>
  1669. struct is_constructible_convertible_assignable_from_optional
  1670. : std::integral_constant<
  1671. bool, is_constructible_convertible_from_optional<T, U>::value ||
  1672. std::is_assignable<T&, optional<U>&>::value ||
  1673. std::is_assignable<T&, optional<U>&&>::value ||
  1674. std::is_assignable<T&, const optional<U>&>::value ||
  1675. std::is_assignable<T&, const optional<U>&&>::value> {};
  1676. // Helper function used by [optional.relops], [optional.comp_with_t],
  1677. // for checking whether an expression is convertible to bool.
  1678. bool convertible_to_bool(bool);
  1679. // Base class for std::hash<phmap::optional<T>>:
  1680. // If std::hash<std::remove_const_t<T>> is enabled, it provides operator() to
  1681. // compute the hash; Otherwise, it is disabled.
  1682. // Reference N4659 23.14.15 [unord.hash].
  1683. template <typename T, typename = size_t>
  1684. struct optional_hash_base
  1685. {
  1686. optional_hash_base() = delete;
  1687. optional_hash_base(const optional_hash_base&) = delete;
  1688. optional_hash_base(optional_hash_base&&) = delete;
  1689. optional_hash_base& operator=(const optional_hash_base&) = delete;
  1690. optional_hash_base& operator=(optional_hash_base&&) = delete;
  1691. };
  1692. template <typename T>
  1693. struct optional_hash_base<T, decltype(std::hash<phmap::remove_const_t<T> >()(
  1694. std::declval<phmap::remove_const_t<T> >()))>
  1695. {
  1696. using argument_type = phmap::optional<T>;
  1697. using result_type = size_t;
  1698. size_t operator()(const phmap::optional<T>& opt) const {
  1699. phmap::type_traits_internal::AssertHashEnabled<phmap::remove_const_t<T>>();
  1700. if (opt) {
  1701. return std::hash<phmap::remove_const_t<T> >()(*opt);
  1702. } else {
  1703. return static_cast<size_t>(0x297814aaad196e6dULL);
  1704. }
  1705. }
  1706. };
  1707. } // namespace optional_internal
  1708. // -----------------------------------------------------------------------------
  1709. // phmap::optional class definition
  1710. // -----------------------------------------------------------------------------
  1711. template <typename T>
  1712. class optional : private optional_internal::optional_data<T>,
  1713. private optional_internal::optional_ctor_base<
  1714. optional_internal::get_ctor_copy_traits<T>()>,
  1715. private optional_internal::optional_assign_base<
  1716. optional_internal::get_assign_copy_traits<T>()>
  1717. {
  1718. using data_base = optional_internal::optional_data<T>;
  1719. public:
  1720. typedef T value_type;
  1721. // Constructors
  1722. // Constructs an `optional` holding an empty value, NOT a default constructed
  1723. // `T`.
  1724. constexpr optional() noexcept {}
  1725. // Constructs an `optional` initialized with `nullopt` to hold an empty value.
  1726. constexpr optional(nullopt_t) noexcept {} // NOLINT(runtime/explicit)
  1727. // Copy constructor, standard semantics
  1728. optional(const optional& src) = default;
  1729. // Move constructor, standard semantics
  1730. optional(optional&& src) noexcept = default;
  1731. // Constructs a non-empty `optional` direct-initialized value of type `T` from
  1732. // the arguments `std::forward<Args>(args)...` within the `optional`.
  1733. // (The `in_place_t` is a tag used to indicate that the contained object
  1734. // should be constructed in-place.)
  1735. template <typename InPlaceT, typename... Args,
  1736. phmap::enable_if_t<phmap::conjunction<
  1737. std::is_same<InPlaceT, in_place_t>,
  1738. std::is_constructible<T, Args&&...> >::value>* = nullptr>
  1739. constexpr explicit optional(InPlaceT, Args&&... args)
  1740. : data_base(in_place_t(), phmap::forward<Args>(args)...) {}
  1741. // Constructs a non-empty `optional` direct-initialized value of type `T` from
  1742. // the arguments of an initializer_list and `std::forward<Args>(args)...`.
  1743. // (The `in_place_t` is a tag used to indicate that the contained object
  1744. // should be constructed in-place.)
  1745. template <typename U, typename... Args,
  1746. typename = typename std::enable_if<std::is_constructible<
  1747. T, std::initializer_list<U>&, Args&&...>::value>::type>
  1748. constexpr explicit optional(in_place_t, std::initializer_list<U> il,
  1749. Args&&... args)
  1750. : data_base(in_place_t(), il, phmap::forward<Args>(args)...) {
  1751. }
  1752. // Value constructor (implicit)
  1753. template <
  1754. typename U = T,
  1755. typename std::enable_if<
  1756. phmap::conjunction<phmap::negation<std::is_same<
  1757. in_place_t, typename std::decay<U>::type> >,
  1758. phmap::negation<std::is_same<
  1759. optional<T>, typename std::decay<U>::type> >,
  1760. std::is_convertible<U&&, T>,
  1761. std::is_constructible<T, U&&> >::value,
  1762. bool>::type = false>
  1763. constexpr optional(U&& v) : data_base(in_place_t(), phmap::forward<U>(v)) {}
  1764. // Value constructor (explicit)
  1765. template <
  1766. typename U = T,
  1767. typename std::enable_if<
  1768. phmap::conjunction<phmap::negation<std::is_same<
  1769. in_place_t, typename std::decay<U>::type>>,
  1770. phmap::negation<std::is_same<
  1771. optional<T>, typename std::decay<U>::type>>,
  1772. phmap::negation<std::is_convertible<U&&, T>>,
  1773. std::is_constructible<T, U&&>>::value,
  1774. bool>::type = false>
  1775. explicit constexpr optional(U&& v)
  1776. : data_base(in_place_t(), phmap::forward<U>(v)) {}
  1777. // Converting copy constructor (implicit)
  1778. template <typename U,
  1779. typename std::enable_if<
  1780. phmap::conjunction<
  1781. phmap::negation<std::is_same<T, U> >,
  1782. std::is_constructible<T, const U&>,
  1783. phmap::negation<
  1784. optional_internal::
  1785. is_constructible_convertible_from_optional<T, U> >,
  1786. std::is_convertible<const U&, T> >::value,
  1787. bool>::type = false>
  1788. optional(const optional<U>& rhs) {
  1789. if (rhs) {
  1790. this->construct(*rhs);
  1791. }
  1792. }
  1793. // Converting copy constructor (explicit)
  1794. template <typename U,
  1795. typename std::enable_if<
  1796. phmap::conjunction<
  1797. phmap::negation<std::is_same<T, U>>,
  1798. std::is_constructible<T, const U&>,
  1799. phmap::negation<
  1800. optional_internal::
  1801. is_constructible_convertible_from_optional<T, U>>,
  1802. phmap::negation<std::is_convertible<const U&, T>>>::value,
  1803. bool>::type = false>
  1804. explicit optional(const optional<U>& rhs) {
  1805. if (rhs) {
  1806. this->construct(*rhs);
  1807. }
  1808. }
  1809. // Converting move constructor (implicit)
  1810. template <typename U,
  1811. typename std::enable_if<
  1812. phmap::conjunction<
  1813. phmap::negation<std::is_same<T, U> >,
  1814. std::is_constructible<T, U&&>,
  1815. phmap::negation<
  1816. optional_internal::
  1817. is_constructible_convertible_from_optional<T, U> >,
  1818. std::is_convertible<U&&, T> >::value,
  1819. bool>::type = false>
  1820. optional(optional<U>&& rhs) {
  1821. if (rhs) {
  1822. this->construct(std::move(*rhs));
  1823. }
  1824. }
  1825. // Converting move constructor (explicit)
  1826. template <
  1827. typename U,
  1828. typename std::enable_if<
  1829. phmap::conjunction<
  1830. phmap::negation<std::is_same<T, U>>, std::is_constructible<T, U&&>,
  1831. phmap::negation<
  1832. optional_internal::is_constructible_convertible_from_optional<
  1833. T, U>>,
  1834. phmap::negation<std::is_convertible<U&&, T>>>::value,
  1835. bool>::type = false>
  1836. explicit optional(optional<U>&& rhs) {
  1837. if (rhs) {
  1838. this->construct(std::move(*rhs));
  1839. }
  1840. }
  1841. // Destructor. Trivial if `T` is trivially destructible.
  1842. ~optional() = default;
  1843. // Assignment Operators
  1844. // Assignment from `nullopt`
  1845. //
  1846. // Example:
  1847. //
  1848. // struct S { int value; };
  1849. // optional<S> opt = phmap::nullopt; // Could also use opt = { };
  1850. optional& operator=(nullopt_t) noexcept {
  1851. this->destruct();
  1852. return *this;
  1853. }
  1854. // Copy assignment operator, standard semantics
  1855. optional& operator=(const optional& src) = default;
  1856. // Move assignment operator, standard semantics
  1857. optional& operator=(optional&& src) noexcept = default;
  1858. // Value assignment operators
  1859. template <
  1860. typename U = T,
  1861. typename = typename std::enable_if<phmap::conjunction<
  1862. phmap::negation<
  1863. std::is_same<optional<T>, typename std::decay<U>::type>>,
  1864. phmap::negation<
  1865. phmap::conjunction<std::is_scalar<T>,
  1866. std::is_same<T, typename std::decay<U>::type>>>,
  1867. std::is_constructible<T, U>, std::is_assignable<T&, U>>::value>::type>
  1868. optional& operator=(U&& v) {
  1869. this->assign(std::forward<U>(v));
  1870. return *this;
  1871. }
  1872. template <
  1873. typename U,
  1874. typename = typename std::enable_if<phmap::conjunction<
  1875. phmap::negation<std::is_same<T, U>>,
  1876. std::is_constructible<T, const U&>, std::is_assignable<T&, const U&>,
  1877. phmap::negation<
  1878. optional_internal::
  1879. is_constructible_convertible_assignable_from_optional<
  1880. T, U>>>::value>::type>
  1881. optional& operator=(const optional<U>& rhs) {
  1882. if (rhs) {
  1883. this->assign(*rhs);
  1884. } else {
  1885. this->destruct();
  1886. }
  1887. return *this;
  1888. }
  1889. template <typename U,
  1890. typename = typename std::enable_if<phmap::conjunction<
  1891. phmap::negation<std::is_same<T, U>>, std::is_constructible<T, U>,
  1892. std::is_assignable<T&, U>,
  1893. phmap::negation<
  1894. optional_internal::
  1895. is_constructible_convertible_assignable_from_optional<
  1896. T, U>>>::value>::type>
  1897. optional& operator=(optional<U>&& rhs) {
  1898. if (rhs) {
  1899. this->assign(std::move(*rhs));
  1900. } else {
  1901. this->destruct();
  1902. }
  1903. return *this;
  1904. }
  1905. // Modifiers
  1906. // optional::reset()
  1907. //
  1908. // Destroys the inner `T` value of an `phmap::optional` if one is present.
  1909. PHMAP_ATTRIBUTE_REINITIALIZES void reset() noexcept { this->destruct(); }
  1910. // optional::emplace()
  1911. //
  1912. // (Re)constructs the underlying `T` in-place with the given forwarded
  1913. // arguments.
  1914. //
  1915. // Example:
  1916. //
  1917. // optional<Foo> opt;
  1918. // opt.emplace(arg1,arg2,arg3); // Constructs Foo(arg1,arg2,arg3)
  1919. //
  1920. // If the optional is non-empty, and the `args` refer to subobjects of the
  1921. // current object, then behaviour is undefined, because the current object
  1922. // will be destructed before the new object is constructed with `args`.
  1923. template <typename... Args,
  1924. typename = typename std::enable_if<
  1925. std::is_constructible<T, Args&&...>::value>::type>
  1926. T& emplace(Args&&... args) {
  1927. this->destruct();
  1928. this->construct(std::forward<Args>(args)...);
  1929. return reference();
  1930. }
  1931. // Emplace reconstruction overload for an initializer list and the given
  1932. // forwarded arguments.
  1933. //
  1934. // Example:
  1935. //
  1936. // struct Foo {
  1937. // Foo(std::initializer_list<int>);
  1938. // };
  1939. //
  1940. // optional<Foo> opt;
  1941. // opt.emplace({1,2,3}); // Constructs Foo({1,2,3})
  1942. template <typename U, typename... Args,
  1943. typename = typename std::enable_if<std::is_constructible<
  1944. T, std::initializer_list<U>&, Args&&...>::value>::type>
  1945. T& emplace(std::initializer_list<U> il, Args&&... args) {
  1946. this->destruct();
  1947. this->construct(il, std::forward<Args>(args)...);
  1948. return reference();
  1949. }
  1950. // Swaps
  1951. // Swap, standard semantics
  1952. void swap(optional& rhs) noexcept(
  1953. std::is_nothrow_move_constructible<T>::value&&
  1954. std::is_trivial<T>::value) {
  1955. if (*this) {
  1956. if (rhs) {
  1957. using std::swap;
  1958. swap(**this, *rhs);
  1959. } else {
  1960. rhs.construct(std::move(**this));
  1961. this->destruct();
  1962. }
  1963. } else {
  1964. if (rhs) {
  1965. this->construct(std::move(*rhs));
  1966. rhs.destruct();
  1967. } else {
  1968. // No effect (swap(disengaged, disengaged)).
  1969. }
  1970. }
  1971. }
  1972. // Observers
  1973. // optional::operator->()
  1974. //
  1975. // Accesses the underlying `T` value's member `m` of an `optional`. If the
  1976. // `optional` is empty, behavior is undefined.
  1977. //
  1978. // If you need myOpt->foo in constexpr, use (*myOpt).foo instead.
  1979. const T* operator->() const {
  1980. assert(this->engaged_);
  1981. return std::addressof(this->data_);
  1982. }
  1983. T* operator->() {
  1984. assert(this->engaged_);
  1985. return std::addressof(this->data_);
  1986. }
  1987. // optional::operator*()
  1988. //
  1989. // Accesses the underlying `T` value of an `optional`. If the `optional` is
  1990. // empty, behavior is undefined.
  1991. constexpr const T& operator*() const & { return reference(); }
  1992. T& operator*() & {
  1993. assert(this->engaged_);
  1994. return reference();
  1995. }
  1996. constexpr const T&& operator*() const && {
  1997. return phmap::move(reference());
  1998. }
  1999. T&& operator*() && {
  2000. assert(this->engaged_);
  2001. return std::move(reference());
  2002. }
  2003. // optional::operator bool()
  2004. //
  2005. // Returns false if and only if the `optional` is empty.
  2006. //
  2007. // if (opt) {
  2008. // // do something with opt.value();
  2009. // } else {
  2010. // // opt is empty.
  2011. // }
  2012. //
  2013. constexpr explicit operator bool() const noexcept { return this->engaged_; }
  2014. // optional::has_value()
  2015. //
  2016. // Determines whether the `optional` contains a value. Returns `false` if and
  2017. // only if `*this` is empty.
  2018. constexpr bool has_value() const noexcept { return this->engaged_; }
  2019. // Suppress bogus warning on MSVC: MSVC complains call to reference() after
  2020. // throw_bad_optional_access() is unreachable.
  2021. #ifdef _MSC_VER
  2022. #pragma warning(push)
  2023. #pragma warning(disable : 4702)
  2024. #endif // _MSC_VER
  2025. // optional::value()
  2026. //
  2027. // Returns a reference to an `optional`s underlying value. The constness
  2028. // and lvalue/rvalue-ness of the `optional` is preserved to the view of
  2029. // the `T` sub-object. Throws `phmap::bad_optional_access` when the `optional`
  2030. // is empty.
  2031. constexpr const T& value() const & {
  2032. return static_cast<bool>(*this)
  2033. ? reference()
  2034. : (optional_internal::throw_bad_optional_access(), reference());
  2035. }
  2036. T& value() & {
  2037. return static_cast<bool>(*this)
  2038. ? reference()
  2039. : (optional_internal::throw_bad_optional_access(), reference());
  2040. }
  2041. T&& value() && { // NOLINT(build/c++11)
  2042. return std::move(
  2043. static_cast<bool>(*this)
  2044. ? reference()
  2045. : (optional_internal::throw_bad_optional_access(), reference()));
  2046. }
  2047. constexpr const T&& value() const && { // NOLINT(build/c++11)
  2048. return phmap::move(
  2049. static_cast<bool>(*this)
  2050. ? reference()
  2051. : (optional_internal::throw_bad_optional_access(), reference()));
  2052. }
  2053. #ifdef _MSC_VER
  2054. #pragma warning(pop)
  2055. #endif // _MSC_VER
  2056. // optional::value_or()
  2057. //
  2058. // Returns either the value of `T` or a passed default `v` if the `optional`
  2059. // is empty.
  2060. template <typename U>
  2061. constexpr T value_or(U&& v) const& {
  2062. static_assert(std::is_copy_constructible<value_type>::value,
  2063. "optional<T>::value_or: T must by copy constructible");
  2064. static_assert(std::is_convertible<U&&, value_type>::value,
  2065. "optional<T>::value_or: U must be convertible to T");
  2066. return static_cast<bool>(*this)
  2067. ? **this
  2068. : static_cast<T>(phmap::forward<U>(v));
  2069. }
  2070. template <typename U>
  2071. T value_or(U&& v) && { // NOLINT(build/c++11)
  2072. static_assert(std::is_move_constructible<value_type>::value,
  2073. "optional<T>::value_or: T must by move constructible");
  2074. static_assert(std::is_convertible<U&&, value_type>::value,
  2075. "optional<T>::value_or: U must be convertible to T");
  2076. return static_cast<bool>(*this) ? std::move(**this)
  2077. : static_cast<T>(std::forward<U>(v));
  2078. }
  2079. private:
  2080. // Private accessors for internal storage viewed as reference to T.
  2081. constexpr const T& reference() const { return this->data_; }
  2082. T& reference() { return this->data_; }
  2083. // T constraint checks. You can't have an optional of nullopt_t, in_place_t
  2084. // or a reference.
  2085. static_assert(
  2086. !std::is_same<nullopt_t, typename std::remove_cv<T>::type>::value,
  2087. "optional<nullopt_t> is not allowed.");
  2088. static_assert(
  2089. !std::is_same<in_place_t, typename std::remove_cv<T>::type>::value,
  2090. "optional<in_place_t> is not allowed.");
  2091. static_assert(!std::is_reference<T>::value,
  2092. "optional<reference> is not allowed.");
  2093. };
  2094. // Non-member functions
  2095. // swap()
  2096. //
  2097. // Performs a swap between two `phmap::optional` objects, using standard
  2098. // semantics.
  2099. //
  2100. // NOTE: we assume `is_swappable()` is always `true`. A compile error will
  2101. // result if this is not the case.
  2102. template <typename T,
  2103. typename std::enable_if<std::is_move_constructible<T>::value,
  2104. bool>::type = false>
  2105. void swap(optional<T>& a, optional<T>& b) noexcept(noexcept(a.swap(b))) {
  2106. a.swap(b);
  2107. }
  2108. // make_optional()
  2109. //
  2110. // Creates a non-empty `optional<T>` where the type of `T` is deduced. An
  2111. // `phmap::optional` can also be explicitly instantiated with
  2112. // `make_optional<T>(v)`.
  2113. //
  2114. // Note: `make_optional()` constructions may be declared `constexpr` for
  2115. // trivially copyable types `T`. Non-trivial types require copy elision
  2116. // support in C++17 for `make_optional` to support `constexpr` on such
  2117. // non-trivial types.
  2118. //
  2119. // Example:
  2120. //
  2121. // constexpr phmap::optional<int> opt = phmap::make_optional(1);
  2122. // static_assert(opt.value() == 1, "");
  2123. template <typename T>
  2124. constexpr optional<typename std::decay<T>::type> make_optional(T&& v) {
  2125. return optional<typename std::decay<T>::type>(phmap::forward<T>(v));
  2126. }
  2127. template <typename T, typename... Args>
  2128. constexpr optional<T> make_optional(Args&&... args) {
  2129. return optional<T>(in_place_t(), phmap::forward<Args>(args)...);
  2130. }
  2131. template <typename T, typename U, typename... Args>
  2132. constexpr optional<T> make_optional(std::initializer_list<U> il,
  2133. Args&&... args) {
  2134. return optional<T>(in_place_t(), il,
  2135. phmap::forward<Args>(args)...);
  2136. }
  2137. // Relational operators [optional.relops]
  2138. // Empty optionals are considered equal to each other and less than non-empty
  2139. // optionals. Supports relations between optional<T> and optional<U>, between
  2140. // optional<T> and U, and between optional<T> and nullopt.
  2141. //
  2142. // Note: We're careful to support T having non-bool relationals.
  2143. // Requires: The expression, e.g. "*x == *y" shall be well-formed and its result
  2144. // shall be convertible to bool.
  2145. // The C++17 (N4606) "Returns:" statements are translated into
  2146. // code in an obvious way here, and the original text retained as function docs.
  2147. // Returns: If bool(x) != bool(y), false; otherwise if bool(x) == false, true;
  2148. // otherwise *x == *y.
  2149. template <typename T, typename U>
  2150. constexpr auto operator==(const optional<T>& x, const optional<U>& y)
  2151. -> decltype(optional_internal::convertible_to_bool(*x == *y)) {
  2152. return static_cast<bool>(x) != static_cast<bool>(y)
  2153. ? false
  2154. : static_cast<bool>(x) == false ? true
  2155. : static_cast<bool>(*x == *y);
  2156. }
  2157. // Returns: If bool(x) != bool(y), true; otherwise, if bool(x) == false, false;
  2158. // otherwise *x != *y.
  2159. template <typename T, typename U>
  2160. constexpr auto operator!=(const optional<T>& x, const optional<U>& y)
  2161. -> decltype(optional_internal::convertible_to_bool(*x != *y)) {
  2162. return static_cast<bool>(x) != static_cast<bool>(y)
  2163. ? true
  2164. : static_cast<bool>(x) == false ? false
  2165. : static_cast<bool>(*x != *y);
  2166. }
  2167. // Returns: If !y, false; otherwise, if !x, true; otherwise *x < *y.
  2168. template <typename T, typename U>
  2169. constexpr auto operator<(const optional<T>& x, const optional<U>& y)
  2170. -> decltype(optional_internal::convertible_to_bool(*x < *y)) {
  2171. return !y ? false : !x ? true : static_cast<bool>(*x < *y);
  2172. }
  2173. // Returns: If !x, false; otherwise, if !y, true; otherwise *x > *y.
  2174. template <typename T, typename U>
  2175. constexpr auto operator>(const optional<T>& x, const optional<U>& y)
  2176. -> decltype(optional_internal::convertible_to_bool(*x > *y)) {
  2177. return !x ? false : !y ? true : static_cast<bool>(*x > *y);
  2178. }
  2179. // Returns: If !x, true; otherwise, if !y, false; otherwise *x <= *y.
  2180. template <typename T, typename U>
  2181. constexpr auto operator<=(const optional<T>& x, const optional<U>& y)
  2182. -> decltype(optional_internal::convertible_to_bool(*x <= *y)) {
  2183. return !x ? true : !y ? false : static_cast<bool>(*x <= *y);
  2184. }
  2185. // Returns: If !y, true; otherwise, if !x, false; otherwise *x >= *y.
  2186. template <typename T, typename U>
  2187. constexpr auto operator>=(const optional<T>& x, const optional<U>& y)
  2188. -> decltype(optional_internal::convertible_to_bool(*x >= *y)) {
  2189. return !y ? true : !x ? false : static_cast<bool>(*x >= *y);
  2190. }
  2191. // Comparison with nullopt [optional.nullops]
  2192. // The C++17 (N4606) "Returns:" statements are used directly here.
  2193. template <typename T>
  2194. constexpr bool operator==(const optional<T>& x, nullopt_t) noexcept {
  2195. return !x;
  2196. }
  2197. template <typename T>
  2198. constexpr bool operator==(nullopt_t, const optional<T>& x) noexcept {
  2199. return !x;
  2200. }
  2201. template <typename T>
  2202. constexpr bool operator!=(const optional<T>& x, nullopt_t) noexcept {
  2203. return static_cast<bool>(x);
  2204. }
  2205. template <typename T>
  2206. constexpr bool operator!=(nullopt_t, const optional<T>& x) noexcept {
  2207. return static_cast<bool>(x);
  2208. }
  2209. template <typename T>
  2210. constexpr bool operator<(const optional<T>&, nullopt_t) noexcept {
  2211. return false;
  2212. }
  2213. template <typename T>
  2214. constexpr bool operator<(nullopt_t, const optional<T>& x) noexcept {
  2215. return static_cast<bool>(x);
  2216. }
  2217. template <typename T>
  2218. constexpr bool operator<=(const optional<T>& x, nullopt_t) noexcept {
  2219. return !x;
  2220. }
  2221. template <typename T>
  2222. constexpr bool operator<=(nullopt_t, const optional<T>&) noexcept {
  2223. return true;
  2224. }
  2225. template <typename T>
  2226. constexpr bool operator>(const optional<T>& x, nullopt_t) noexcept {
  2227. return static_cast<bool>(x);
  2228. }
  2229. template <typename T>
  2230. constexpr bool operator>(nullopt_t, const optional<T>&) noexcept {
  2231. return false;
  2232. }
  2233. template <typename T>
  2234. constexpr bool operator>=(const optional<T>&, nullopt_t) noexcept {
  2235. return true;
  2236. }
  2237. template <typename T>
  2238. constexpr bool operator>=(nullopt_t, const optional<T>& x) noexcept {
  2239. return !x;
  2240. }
  2241. // Comparison with T [optional.comp_with_t]
  2242. // Requires: The expression, e.g. "*x == v" shall be well-formed and its result
  2243. // shall be convertible to bool.
  2244. // The C++17 (N4606) "Equivalent to:" statements are used directly here.
  2245. template <typename T, typename U>
  2246. constexpr auto operator==(const optional<T>& x, const U& v)
  2247. -> decltype(optional_internal::convertible_to_bool(*x == v)) {
  2248. return static_cast<bool>(x) ? static_cast<bool>(*x == v) : false;
  2249. }
  2250. template <typename T, typename U>
  2251. constexpr auto operator==(const U& v, const optional<T>& x)
  2252. -> decltype(optional_internal::convertible_to_bool(v == *x)) {
  2253. return static_cast<bool>(x) ? static_cast<bool>(v == *x) : false;
  2254. }
  2255. template <typename T, typename U>
  2256. constexpr auto operator!=(const optional<T>& x, const U& v)
  2257. -> decltype(optional_internal::convertible_to_bool(*x != v)) {
  2258. return static_cast<bool>(x) ? static_cast<bool>(*x != v) : true;
  2259. }
  2260. template <typename T, typename U>
  2261. constexpr auto operator!=(const U& v, const optional<T>& x)
  2262. -> decltype(optional_internal::convertible_to_bool(v != *x)) {
  2263. return static_cast<bool>(x) ? static_cast<bool>(v != *x) : true;
  2264. }
  2265. template <typename T, typename U>
  2266. constexpr auto operator<(const optional<T>& x, const U& v)
  2267. -> decltype(optional_internal::convertible_to_bool(*x < v)) {
  2268. return static_cast<bool>(x) ? static_cast<bool>(*x < v) : true;
  2269. }
  2270. template <typename T, typename U>
  2271. constexpr auto operator<(const U& v, const optional<T>& x)
  2272. -> decltype(optional_internal::convertible_to_bool(v < *x)) {
  2273. return static_cast<bool>(x) ? static_cast<bool>(v < *x) : false;
  2274. }
  2275. template <typename T, typename U>
  2276. constexpr auto operator<=(const optional<T>& x, const U& v)
  2277. -> decltype(optional_internal::convertible_to_bool(*x <= v)) {
  2278. return static_cast<bool>(x) ? static_cast<bool>(*x <= v) : true;
  2279. }
  2280. template <typename T, typename U>
  2281. constexpr auto operator<=(const U& v, const optional<T>& x)
  2282. -> decltype(optional_internal::convertible_to_bool(v <= *x)) {
  2283. return static_cast<bool>(x) ? static_cast<bool>(v <= *x) : false;
  2284. }
  2285. template <typename T, typename U>
  2286. constexpr auto operator>(const optional<T>& x, const U& v)
  2287. -> decltype(optional_internal::convertible_to_bool(*x > v)) {
  2288. return static_cast<bool>(x) ? static_cast<bool>(*x > v) : false;
  2289. }
  2290. template <typename T, typename U>
  2291. constexpr auto operator>(const U& v, const optional<T>& x)
  2292. -> decltype(optional_internal::convertible_to_bool(v > *x)) {
  2293. return static_cast<bool>(x) ? static_cast<bool>(v > *x) : true;
  2294. }
  2295. template <typename T, typename U>
  2296. constexpr auto operator>=(const optional<T>& x, const U& v)
  2297. -> decltype(optional_internal::convertible_to_bool(*x >= v)) {
  2298. return static_cast<bool>(x) ? static_cast<bool>(*x >= v) : false;
  2299. }
  2300. template <typename T, typename U>
  2301. constexpr auto operator>=(const U& v, const optional<T>& x)
  2302. -> decltype(optional_internal::convertible_to_bool(v >= *x)) {
  2303. return static_cast<bool>(x) ? static_cast<bool>(v >= *x) : true;
  2304. }
  2305. } // namespace phmap
  2306. namespace std {
  2307. // std::hash specialization for phmap::optional.
  2308. template <typename T>
  2309. struct hash<phmap::optional<T> >
  2310. : phmap::optional_internal::optional_hash_base<T> {};
  2311. } // namespace std
  2312. #endif
  2313. // -----------------------------------------------------------------------------
  2314. // common.h
  2315. // -----------------------------------------------------------------------------
  2316. namespace phmap {
  2317. namespace priv {
  2318. template <class, class = void>
  2319. struct IsTransparent : std::false_type {};
  2320. template <class T>
  2321. struct IsTransparent<T, phmap::void_t<typename T::is_transparent>>
  2322. : std::true_type {};
  2323. template <bool is_transparent>
  2324. struct KeyArg
  2325. {
  2326. // Transparent. Forward `K`.
  2327. template <typename K, typename key_type>
  2328. using type = K;
  2329. };
  2330. template <>
  2331. struct KeyArg<false>
  2332. {
  2333. // Not transparent. Always use `key_type`.
  2334. template <typename K, typename key_type>
  2335. using type = key_type;
  2336. };
  2337. #ifdef _MSC_VER
  2338. #pragma warning(push)
  2339. // warning C4820: '6' bytes padding added after data member
  2340. #pragma warning(disable : 4820)
  2341. #endif
  2342. // The node_handle concept from C++17.
  2343. // We specialize node_handle for sets and maps. node_handle_base holds the
  2344. // common API of both.
  2345. // -----------------------------------------------------------------------
  2346. template <typename PolicyTraits, typename Alloc>
  2347. class node_handle_base
  2348. {
  2349. protected:
  2350. using slot_type = typename PolicyTraits::slot_type;
  2351. public:
  2352. using allocator_type = Alloc;
  2353. constexpr node_handle_base() {}
  2354. node_handle_base(node_handle_base&& other) noexcept {
  2355. *this = std::move(other);
  2356. }
  2357. ~node_handle_base() { destroy(); }
  2358. node_handle_base& operator=(node_handle_base&& other) noexcept {
  2359. destroy();
  2360. if (!other.empty()) {
  2361. alloc_ = other.alloc_;
  2362. PolicyTraits::transfer(alloc(), slot(), other.slot());
  2363. other.reset();
  2364. }
  2365. return *this;
  2366. }
  2367. bool empty() const noexcept { return !alloc_; }
  2368. explicit operator bool() const noexcept { return !empty(); }
  2369. allocator_type get_allocator() const { return *alloc_; }
  2370. protected:
  2371. friend struct CommonAccess;
  2372. struct transfer_tag_t {};
  2373. node_handle_base(transfer_tag_t, const allocator_type& a, slot_type* s)
  2374. : alloc_(a) {
  2375. PolicyTraits::transfer(alloc(), slot(), s);
  2376. }
  2377. struct move_tag_t {};
  2378. node_handle_base(move_tag_t, const allocator_type& a, slot_type* s)
  2379. : alloc_(a) {
  2380. PolicyTraits::construct(alloc(), slot(), s);
  2381. }
  2382. node_handle_base(const allocator_type& a, slot_type* s) : alloc_(a) {
  2383. PolicyTraits::transfer(alloc(), slot(), s);
  2384. }
  2385. //node_handle_base(const node_handle_base&) = delete;
  2386. //node_handle_base& operator=(const node_handle_base&) = delete;
  2387. void destroy() {
  2388. if (!empty()) {
  2389. PolicyTraits::destroy(alloc(), slot());
  2390. reset();
  2391. }
  2392. }
  2393. void reset() {
  2394. assert(alloc_.has_value());
  2395. alloc_ = phmap::nullopt;
  2396. }
  2397. slot_type* slot() const {
  2398. assert(!empty());
  2399. return reinterpret_cast<slot_type*>(std::addressof(slot_space_));
  2400. }
  2401. allocator_type* alloc() { return std::addressof(*alloc_); }
  2402. private:
  2403. phmap::optional<allocator_type> alloc_;
  2404. mutable phmap::aligned_storage_t<sizeof(slot_type), alignof(slot_type)> slot_space_;
  2405. };
  2406. #ifdef _MSC_VER
  2407. #pragma warning(pop)
  2408. #endif
  2409. // For sets.
  2410. // ---------
  2411. template <typename Policy, typename PolicyTraits, typename Alloc,
  2412. typename = void>
  2413. class node_handle : public node_handle_base<PolicyTraits, Alloc>
  2414. {
  2415. using Base = node_handle_base<PolicyTraits, Alloc>;
  2416. public:
  2417. using value_type = typename PolicyTraits::value_type;
  2418. constexpr node_handle() {}
  2419. value_type& value() const { return PolicyTraits::element(this->slot()); }
  2420. value_type& key() const { return PolicyTraits::element(this->slot()); }
  2421. private:
  2422. friend struct CommonAccess;
  2423. using Base::Base;
  2424. };
  2425. // For maps.
  2426. // ---------
  2427. template <typename Policy, typename PolicyTraits, typename Alloc>
  2428. class node_handle<Policy, PolicyTraits, Alloc,
  2429. phmap::void_t<typename Policy::mapped_type>>
  2430. : public node_handle_base<PolicyTraits, Alloc>
  2431. {
  2432. using Base = node_handle_base<PolicyTraits, Alloc>;
  2433. using slot_type = typename PolicyTraits::slot_type;
  2434. public:
  2435. using key_type = typename Policy::key_type;
  2436. using mapped_type = typename Policy::mapped_type;
  2437. constexpr node_handle() {}
  2438. auto key() const -> decltype(PolicyTraits::key(this->slot())) {
  2439. return PolicyTraits::key(this->slot());
  2440. }
  2441. mapped_type& mapped() const {
  2442. return PolicyTraits::value(&PolicyTraits::element(this->slot()));
  2443. }
  2444. private:
  2445. friend struct CommonAccess;
  2446. using Base::Base;
  2447. };
  2448. // Provide access to non-public node-handle functions.
  2449. struct CommonAccess
  2450. {
  2451. template <typename Node>
  2452. static auto GetSlot(const Node& node) -> decltype(node.slot()) {
  2453. return node.slot();
  2454. }
  2455. template <typename Node>
  2456. static void Destroy(Node* node) {
  2457. node->destroy();
  2458. }
  2459. template <typename Node>
  2460. static void Reset(Node* node) {
  2461. node->reset();
  2462. }
  2463. template <typename T, typename... Args>
  2464. static T Make(Args&&... args) {
  2465. return T(std::forward<Args>(args)...);
  2466. }
  2467. template <typename T, typename... Args>
  2468. static T Transfer(Args&&... args) {
  2469. return T(typename T::transfer_tag_t{}, std::forward<Args>(args)...);
  2470. }
  2471. template <typename T, typename... Args>
  2472. static T Move(Args&&... args) {
  2473. return T(typename T::move_tag_t{}, std::forward<Args>(args)...);
  2474. }
  2475. };
  2476. // Implement the insert_return_type<> concept of C++17.
  2477. template <class Iterator, class NodeType>
  2478. struct InsertReturnType
  2479. {
  2480. Iterator position;
  2481. bool inserted;
  2482. NodeType node;
  2483. };
  2484. } // namespace priv
  2485. } // namespace phmap
  2486. #ifdef ADDRESS_SANITIZER
  2487. #include <sanitizer/asan_interface.h>
  2488. #endif
  2489. // ---------------------------------------------------------------------------
  2490. // span.h
  2491. // ---------------------------------------------------------------------------
  2492. namespace phmap {
  2493. template <typename T>
  2494. class Span;
  2495. namespace span_internal {
  2496. // A constexpr min function
  2497. constexpr size_t Min(size_t a, size_t b) noexcept { return a < b ? a : b; }
  2498. // Wrappers for access to container data pointers.
  2499. template <typename C>
  2500. constexpr auto GetDataImpl(C& c, char) noexcept // NOLINT(runtime/references)
  2501. -> decltype(c.data()) {
  2502. return c.data();
  2503. }
  2504. // Before C++17, std::string::data returns a const char* in all cases.
  2505. LL_INLINE char* GetDataImpl(std::string& s, // NOLINT(runtime/references)
  2506. int) noexcept {
  2507. return &s[0];
  2508. }
  2509. template <typename C>
  2510. constexpr auto GetData(C& c) noexcept // NOLINT(runtime/references)
  2511. -> decltype(GetDataImpl(c, 0)) {
  2512. return GetDataImpl(c, 0);
  2513. }
  2514. // Detection idioms for size() and data().
  2515. template <typename C>
  2516. using HasSize =
  2517. std::is_integral<phmap::decay_t<decltype(std::declval<C&>().size())>>;
  2518. // We want to enable conversion from vector<T*> to Span<const T* const> but
  2519. // disable conversion from vector<Derived> to Span<Base>. Here we use
  2520. // the fact that U** is convertible to Q* const* if and only if Q is the same
  2521. // type or a more cv-qualified version of U. We also decay the result type of
  2522. // data() to avoid problems with classes which have a member function data()
  2523. // which returns a reference.
  2524. template <typename T, typename C>
  2525. using HasData =
  2526. std::is_convertible<phmap::decay_t<decltype(GetData(std::declval<C&>()))>*,
  2527. T* const*>;
  2528. // Extracts value type from a Container
  2529. template <typename C>
  2530. struct ElementType {
  2531. using type = typename phmap::remove_reference_t<C>::value_type;
  2532. };
  2533. template <typename T, size_t N>
  2534. struct ElementType<T (&)[N]> {
  2535. using type = T;
  2536. };
  2537. template <typename C>
  2538. using ElementT = typename ElementType<C>::type;
  2539. template <typename T>
  2540. using EnableIfMutable =
  2541. typename std::enable_if<!std::is_const<T>::value, int>::type;
  2542. template <typename T>
  2543. bool EqualImpl(Span<T> a, Span<T> b) {
  2544. static_assert(std::is_const<T>::value, "");
  2545. return std::equal(a.begin(), a.end(), b.begin(), b.end());
  2546. }
  2547. template <typename T>
  2548. bool LessThanImpl(Span<T> a, Span<T> b) {
  2549. static_assert(std::is_const<T>::value, "");
  2550. return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end());
  2551. }
  2552. // The `IsConvertible` classes here are needed because of the
  2553. // `std::is_convertible` bug in libcxx when compiled with GCC. This build
  2554. // configuration is used by Android NDK toolchain. Reference link:
  2555. // https://bugs.llvm.org/show_bug.cgi?id=27538.
  2556. template <typename From, typename To>
  2557. struct IsConvertibleHelper {
  2558. static std::true_type testval(To);
  2559. static std::false_type testval(...);
  2560. using type = decltype(testval(std::declval<From>()));
  2561. };
  2562. template <typename From, typename To>
  2563. struct IsConvertible : IsConvertibleHelper<From, To>::type {};
  2564. // TODO(zhangxy): replace `IsConvertible` with `std::is_convertible` once the
  2565. // older version of libcxx is not supported.
  2566. template <typename From, typename To>
  2567. using EnableIfConvertibleToSpanConst =
  2568. typename std::enable_if<IsConvertible<From, Span<const To>>::value>::type;
  2569. } // namespace span_internal
  2570. //------------------------------------------------------------------------------
  2571. // Span
  2572. //------------------------------------------------------------------------------
  2573. //
  2574. // A `Span` is an "array view" type for holding a view of a contiguous data
  2575. // array; the `Span` object does not and cannot own such data itself. A span
  2576. // provides an easy way to provide overloads for anything operating on
  2577. // contiguous sequences without needing to manage pointers and array lengths
  2578. // manually.
  2579. // A span is conceptually a pointer (ptr) and a length (size) into an already
  2580. // existing array of contiguous memory; the array it represents references the
  2581. // elements "ptr[0] .. ptr[size-1]". Passing a properly-constructed `Span`
  2582. // instead of raw pointers avoids many issues related to index out of bounds
  2583. // errors.
  2584. //
  2585. // Spans may also be constructed from containers holding contiguous sequences.
  2586. // Such containers must supply `data()` and `size() const` methods (e.g
  2587. // `std::vector<T>`, `phmap::InlinedVector<T, N>`). All implicit conversions to
  2588. // `phmap::Span` from such containers will create spans of type `const T`;
  2589. // spans which can mutate their values (of type `T`) must use explicit
  2590. // constructors.
  2591. //
  2592. // A `Span<T>` is somewhat analogous to an `phmap::string_view`, but for an array
  2593. // of elements of type `T`. A user of `Span` must ensure that the data being
  2594. // pointed to outlives the `Span` itself.
  2595. //
  2596. // You can construct a `Span<T>` in several ways:
  2597. //
  2598. // * Explicitly from a reference to a container type
  2599. // * Explicitly from a pointer and size
  2600. // * Implicitly from a container type (but only for spans of type `const T`)
  2601. // * Using the `MakeSpan()` or `MakeConstSpan()` factory functions.
  2602. //
  2603. // Examples:
  2604. //
  2605. // // Construct a Span explicitly from a container:
  2606. // std::vector<int> v = {1, 2, 3, 4, 5};
  2607. // auto span = phmap::Span<const int>(v);
  2608. //
  2609. // // Construct a Span explicitly from a C-style array:
  2610. // int a[5] = {1, 2, 3, 4, 5};
  2611. // auto span = phmap::Span<const int>(a);
  2612. //
  2613. // // Construct a Span implicitly from a container
  2614. // void MyRoutine(phmap::Span<const int> a) {
  2615. // ...
  2616. // }
  2617. // std::vector v = {1,2,3,4,5};
  2618. // MyRoutine(v) // convert to Span<const T>
  2619. //
  2620. // Note that `Span` objects, in addition to requiring that the memory they
  2621. // point to remains alive, must also ensure that such memory does not get
  2622. // reallocated. Therefore, to avoid undefined behavior, containers with
  2623. // associated span views should not invoke operations that may reallocate memory
  2624. // (such as resizing) or invalidate iterators into the container.
  2625. //
  2626. // One common use for a `Span` is when passing arguments to a routine that can
  2627. // accept a variety of array types (e.g. a `std::vector`, `phmap::InlinedVector`,
  2628. // a C-style array, etc.). Instead of creating overloads for each case, you
  2629. // can simply specify a `Span` as the argument to such a routine.
  2630. //
  2631. // Example:
  2632. //
  2633. // void MyRoutine(phmap::Span<const int> a) {
  2634. // ...
  2635. // }
  2636. //
  2637. // std::vector v = {1,2,3,4,5};
  2638. // MyRoutine(v);
  2639. //
  2640. // phmap::InlinedVector<int, 4> my_inline_vector;
  2641. // MyRoutine(my_inline_vector);
  2642. //
  2643. // // Explicit constructor from pointer,size
  2644. // int* my_array = new int[10];
  2645. // MyRoutine(phmap::Span<const int>(my_array, 10));
  2646. template <typename T>
  2647. class Span
  2648. {
  2649. private:
  2650. // Used to determine whether a Span can be constructed from a container of
  2651. // type C.
  2652. template <typename C>
  2653. using EnableIfConvertibleFrom =
  2654. typename std::enable_if<span_internal::HasData<T, C>::value &&
  2655. span_internal::HasSize<C>::value>::type;
  2656. // Used to SFINAE-enable a function when the slice elements are const.
  2657. template <typename U>
  2658. using EnableIfConstView =
  2659. typename std::enable_if<std::is_const<T>::value, U>::type;
  2660. // Used to SFINAE-enable a function when the slice elements are mutable.
  2661. template <typename U>
  2662. using EnableIfMutableView =
  2663. typename std::enable_if<!std::is_const<T>::value, U>::type;
  2664. public:
  2665. using value_type = phmap::remove_cv_t<T>;
  2666. using pointer = T*;
  2667. using const_pointer = const T*;
  2668. using reference = T&;
  2669. using const_reference = const T&;
  2670. using iterator = pointer;
  2671. using const_iterator = const_pointer;
  2672. using reverse_iterator = std::reverse_iterator<iterator>;
  2673. using const_reverse_iterator = std::reverse_iterator<const_iterator>;
  2674. using size_type = size_t;
  2675. using difference_type = ptrdiff_t;
  2676. static const size_type npos = ~(size_type(0));
  2677. constexpr Span() noexcept : Span(nullptr, 0) {}
  2678. constexpr Span(pointer array, size_type lgth) noexcept
  2679. : ptr_(array), len_(lgth) {}
  2680. // Implicit conversion constructors
  2681. template <size_t N>
  2682. constexpr Span(T (&a)[N]) noexcept // NOLINT(runtime/explicit)
  2683. : Span(a, N) {}
  2684. // Explicit reference constructor for a mutable `Span<T>` type. Can be
  2685. // replaced with MakeSpan() to infer the type parameter.
  2686. template <typename V, typename = EnableIfConvertibleFrom<V>,
  2687. typename = EnableIfMutableView<V>>
  2688. explicit Span(V& v) noexcept // NOLINT(runtime/references)
  2689. : Span(span_internal::GetData(v), v.size()) {}
  2690. // Implicit reference constructor for a read-only `Span<const T>` type
  2691. template <typename V, typename = EnableIfConvertibleFrom<V>,
  2692. typename = EnableIfConstView<V>>
  2693. constexpr Span(const V& v) noexcept // NOLINT(runtime/explicit)
  2694. : Span(span_internal::GetData(v), v.size()) {}
  2695. // Implicit constructor from an initializer list, making it possible to pass a
  2696. // brace-enclosed initializer list to a function expecting a `Span`. Such
  2697. // spans constructed from an initializer list must be of type `Span<const T>`.
  2698. //
  2699. // void Process(phmap::Span<const int> x);
  2700. // Process({1, 2, 3});
  2701. //
  2702. // Note that as always the array referenced by the span must outlive the span.
  2703. // Since an initializer list constructor acts as if it is fed a temporary
  2704. // array (cf. C++ standard [dcl.init.list]/5), it's safe to use this
  2705. // constructor only when the `std::initializer_list` itself outlives the span.
  2706. // In order to meet this requirement it's sufficient to ensure that neither
  2707. // the span nor a copy of it is used outside of the expression in which it's
  2708. // created:
  2709. //
  2710. // // Assume that this function uses the array directly, not retaining any
  2711. // // copy of the span or pointer to any of its elements.
  2712. // void Process(phmap::Span<const int> ints);
  2713. //
  2714. // // Okay: the std::initializer_list<int> will reference a temporary array
  2715. // // that isn't destroyed until after the call to Process returns.
  2716. // Process({ 17, 19 });
  2717. //
  2718. // // Not okay: the storage used by the std::initializer_list<int> is not
  2719. // // allowed to be referenced after the first line.
  2720. // phmap::Span<const int> ints = { 17, 19 };
  2721. // Process(ints);
  2722. //
  2723. // // Not okay for the same reason as above: even when the elements of the
  2724. // // initializer list expression are not temporaries the underlying array
  2725. // // is, so the initializer list must still outlive the span.
  2726. // const int foo = 17;
  2727. // phmap::Span<const int> ints = { foo };
  2728. // Process(ints);
  2729. //
  2730. template <typename LazyT = T,
  2731. typename = EnableIfConstView<LazyT>>
  2732. Span(
  2733. std::initializer_list<value_type> v) noexcept // NOLINT(runtime/explicit)
  2734. : Span(v.begin(), v.size()) {}
  2735. // Accessors
  2736. // Span::data()
  2737. //
  2738. // Returns a pointer to the span's underlying array of data (which is held
  2739. // outside the span).
  2740. constexpr pointer data() const noexcept { return ptr_; }
  2741. // Span::size()
  2742. //
  2743. // Returns the size of this span.
  2744. constexpr size_type size() const noexcept { return len_; }
  2745. // Span::length()
  2746. //
  2747. // Returns the length (size) of this span.
  2748. constexpr size_type length() const noexcept { return size(); }
  2749. // Span::empty()
  2750. //
  2751. // Returns a boolean indicating whether or not this span is considered empty.
  2752. constexpr bool empty() const noexcept { return size() == 0; }
  2753. // Span::operator[]
  2754. //
  2755. // Returns a reference to the i'th element of this span.
  2756. constexpr reference operator[](size_type i) const noexcept {
  2757. // MSVC 2015 accepts this as constexpr, but not ptr_[i]
  2758. return *(data() + i);
  2759. }
  2760. // Span::at()
  2761. //
  2762. // Returns a reference to the i'th element of this span.
  2763. constexpr reference at(size_type i) const {
  2764. return PHMAP_PREDICT_TRUE(i < size()) //
  2765. ? *(data() + i)
  2766. : (base_internal::ThrowStdOutOfRange(
  2767. "Span::at failed bounds check"),
  2768. *(data() + i));
  2769. }
  2770. // Span::front()
  2771. //
  2772. // Returns a reference to the first element of this span.
  2773. constexpr reference front() const noexcept {
  2774. return PHMAP_ASSERT(size() > 0), *data();
  2775. }
  2776. // Span::back()
  2777. //
  2778. // Returns a reference to the last element of this span.
  2779. constexpr reference back() const noexcept {
  2780. return PHMAP_ASSERT(size() > 0), *(data() + size() - 1);
  2781. }
  2782. // Span::begin()
  2783. //
  2784. // Returns an iterator to the first element of this span.
  2785. constexpr iterator begin() const noexcept { return data(); }
  2786. // Span::cbegin()
  2787. //
  2788. // Returns a const iterator to the first element of this span.
  2789. constexpr const_iterator cbegin() const noexcept { return begin(); }
  2790. // Span::end()
  2791. //
  2792. // Returns an iterator to the last element of this span.
  2793. constexpr iterator end() const noexcept { return data() + size(); }
  2794. // Span::cend()
  2795. //
  2796. // Returns a const iterator to the last element of this span.
  2797. constexpr const_iterator cend() const noexcept { return end(); }
  2798. // Span::rbegin()
  2799. //
  2800. // Returns a reverse iterator starting at the last element of this span.
  2801. constexpr reverse_iterator rbegin() const noexcept {
  2802. return reverse_iterator(end());
  2803. }
  2804. // Span::crbegin()
  2805. //
  2806. // Returns a reverse const iterator starting at the last element of this span.
  2807. constexpr const_reverse_iterator crbegin() const noexcept { return rbegin(); }
  2808. // Span::rend()
  2809. //
  2810. // Returns a reverse iterator starting at the first element of this span.
  2811. constexpr reverse_iterator rend() const noexcept {
  2812. return reverse_iterator(begin());
  2813. }
  2814. // Span::crend()
  2815. //
  2816. // Returns a reverse iterator starting at the first element of this span.
  2817. constexpr const_reverse_iterator crend() const noexcept { return rend(); }
  2818. // Span mutations
  2819. // Span::remove_prefix()
  2820. //
  2821. // Removes the first `n` elements from the span.
  2822. void remove_prefix(size_type n) noexcept {
  2823. assert(size() >= n);
  2824. ptr_ += n;
  2825. len_ -= n;
  2826. }
  2827. // Span::remove_suffix()
  2828. //
  2829. // Removes the last `n` elements from the span.
  2830. void remove_suffix(size_type n) noexcept {
  2831. assert(size() >= n);
  2832. len_ -= n;
  2833. }
  2834. // Span::subspan()
  2835. //
  2836. // Returns a `Span` starting at element `pos` and of length `len`. Both `pos`
  2837. // and `len` are of type `size_type` and thus non-negative. Parameter `pos`
  2838. // must be <= size(). Any `len` value that points past the end of the span
  2839. // will be trimmed to at most size() - `pos`. A default `len` value of `npos`
  2840. // ensures the returned subspan continues until the end of the span.
  2841. //
  2842. // Examples:
  2843. //
  2844. // std::vector<int> vec = {10, 11, 12, 13};
  2845. // phmap::MakeSpan(vec).subspan(1, 2); // {11, 12}
  2846. // phmap::MakeSpan(vec).subspan(2, 8); // {12, 13}
  2847. // phmap::MakeSpan(vec).subspan(1); // {11, 12, 13}
  2848. // phmap::MakeSpan(vec).subspan(4); // {}
  2849. // phmap::MakeSpan(vec).subspan(5); // throws std::out_of_range
  2850. constexpr Span subspan(size_type pos = 0, size_type len = npos) const {
  2851. return (pos <= size())
  2852. ? Span(data() + pos, span_internal::Min(size() - pos, len))
  2853. : (base_internal::ThrowStdOutOfRange("pos > size()"), Span());
  2854. }
  2855. // Span::first()
  2856. //
  2857. // Returns a `Span` containing first `len` elements. Parameter `len` is of
  2858. // type `size_type` and thus non-negative. `len` value must be <= size().
  2859. //
  2860. // Examples:
  2861. //
  2862. // std::vector<int> vec = {10, 11, 12, 13};
  2863. // phmap::MakeSpan(vec).first(1); // {10}
  2864. // phmap::MakeSpan(vec).first(3); // {10, 11, 12}
  2865. // phmap::MakeSpan(vec).first(5); // throws std::out_of_range
  2866. constexpr Span first(size_type len) const {
  2867. return (len <= size())
  2868. ? Span(data(), len)
  2869. : (base_internal::ThrowStdOutOfRange("len > size()"), Span());
  2870. }
  2871. // Span::last()
  2872. //
  2873. // Returns a `Span` containing last `len` elements. Parameter `len` is of
  2874. // type `size_type` and thus non-negative. `len` value must be <= size().
  2875. //
  2876. // Examples:
  2877. //
  2878. // std::vector<int> vec = {10, 11, 12, 13};
  2879. // phmap::MakeSpan(vec).last(1); // {13}
  2880. // phmap::MakeSpan(vec).last(3); // {11, 12, 13}
  2881. // phmap::MakeSpan(vec).last(5); // throws std::out_of_range
  2882. constexpr Span last(size_type len) const {
  2883. return (len <= size())
  2884. ? Span(size() - len + data(), len)
  2885. : (base_internal::ThrowStdOutOfRange("len > size()"), Span());
  2886. }
  2887. // Support for phmap::Hash.
  2888. template <typename H>
  2889. friend H AbslHashValue(H h, Span v) {
  2890. return H::combine(H::combine_contiguous(std::move(h), v.data(), v.size()),
  2891. v.size());
  2892. }
  2893. private:
  2894. pointer ptr_;
  2895. size_type len_;
  2896. };
  2897. template <typename T>
  2898. const typename Span<T>::size_type Span<T>::npos;
  2899. // Span relationals
  2900. // Equality is compared element-by-element, while ordering is lexicographical.
  2901. // We provide three overloads for each operator to cover any combination on the
  2902. // left or right hand side of mutable Span<T>, read-only Span<const T>, and
  2903. // convertible-to-read-only Span<T>.
  2904. // TODO(zhangxy): Due to MSVC overload resolution bug with partial ordering
  2905. // template functions, 5 overloads per operator is needed as a workaround. We
  2906. // should update them to 3 overloads per operator using non-deduced context like
  2907. // string_view, i.e.
  2908. // - (Span<T>, Span<T>)
  2909. // - (Span<T>, non_deduced<Span<const T>>)
  2910. // - (non_deduced<Span<const T>>, Span<T>)
  2911. // operator==
  2912. template <typename T>
  2913. bool operator==(Span<T> a, Span<T> b) {
  2914. return span_internal::EqualImpl<const T>(a, b);
  2915. }
  2916. template <typename T>
  2917. bool operator==(Span<const T> a, Span<T> b) {
  2918. return span_internal::EqualImpl<const T>(a, b);
  2919. }
  2920. template <typename T>
  2921. bool operator==(Span<T> a, Span<const T> b) {
  2922. return span_internal::EqualImpl<const T>(a, b);
  2923. }
  2924. template <typename T, typename U,
  2925. typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
  2926. bool operator==(const U& a, Span<T> b) {
  2927. return span_internal::EqualImpl<const T>(a, b);
  2928. }
  2929. template <typename T, typename U,
  2930. typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
  2931. bool operator==(Span<T> a, const U& b) {
  2932. return span_internal::EqualImpl<const T>(a, b);
  2933. }
  2934. // operator!=
  2935. template <typename T>
  2936. bool operator!=(Span<T> a, Span<T> b) {
  2937. return !(a == b);
  2938. }
  2939. template <typename T>
  2940. bool operator!=(Span<const T> a, Span<T> b) {
  2941. return !(a == b);
  2942. }
  2943. template <typename T>
  2944. bool operator!=(Span<T> a, Span<const T> b) {
  2945. return !(a == b);
  2946. }
  2947. template <typename T, typename U,
  2948. typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
  2949. bool operator!=(const U& a, Span<T> b) {
  2950. return !(a == b);
  2951. }
  2952. template <typename T, typename U,
  2953. typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
  2954. bool operator!=(Span<T> a, const U& b) {
  2955. return !(a == b);
  2956. }
  2957. // operator<
  2958. template <typename T>
  2959. bool operator<(Span<T> a, Span<T> b) {
  2960. return span_internal::LessThanImpl<const T>(a, b);
  2961. }
  2962. template <typename T>
  2963. bool operator<(Span<const T> a, Span<T> b) {
  2964. return span_internal::LessThanImpl<const T>(a, b);
  2965. }
  2966. template <typename T>
  2967. bool operator<(Span<T> a, Span<const T> b) {
  2968. return span_internal::LessThanImpl<const T>(a, b);
  2969. }
  2970. template <typename T, typename U,
  2971. typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
  2972. bool operator<(const U& a, Span<T> b) {
  2973. return span_internal::LessThanImpl<const T>(a, b);
  2974. }
  2975. template <typename T, typename U,
  2976. typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
  2977. bool operator<(Span<T> a, const U& b) {
  2978. return span_internal::LessThanImpl<const T>(a, b);
  2979. }
  2980. // operator>
  2981. template <typename T>
  2982. bool operator>(Span<T> a, Span<T> b) {
  2983. return b < a;
  2984. }
  2985. template <typename T>
  2986. bool operator>(Span<const T> a, Span<T> b) {
  2987. return b < a;
  2988. }
  2989. template <typename T>
  2990. bool operator>(Span<T> a, Span<const T> b) {
  2991. return b < a;
  2992. }
  2993. template <typename T, typename U,
  2994. typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
  2995. bool operator>(const U& a, Span<T> b) {
  2996. return b < a;
  2997. }
  2998. template <typename T, typename U,
  2999. typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
  3000. bool operator>(Span<T> a, const U& b) {
  3001. return b < a;
  3002. }
  3003. // operator<=
  3004. template <typename T>
  3005. bool operator<=(Span<T> a, Span<T> b) {
  3006. return !(b < a);
  3007. }
  3008. template <typename T>
  3009. bool operator<=(Span<const T> a, Span<T> b) {
  3010. return !(b < a);
  3011. }
  3012. template <typename T>
  3013. bool operator<=(Span<T> a, Span<const T> b) {
  3014. return !(b < a);
  3015. }
  3016. template <typename T, typename U,
  3017. typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
  3018. bool operator<=(const U& a, Span<T> b) {
  3019. return !(b < a);
  3020. }
  3021. template <typename T, typename U,
  3022. typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
  3023. bool operator<=(Span<T> a, const U& b) {
  3024. return !(b < a);
  3025. }
  3026. // operator>=
  3027. template <typename T>
  3028. bool operator>=(Span<T> a, Span<T> b) {
  3029. return !(a < b);
  3030. }
  3031. template <typename T>
  3032. bool operator>=(Span<const T> a, Span<T> b) {
  3033. return !(a < b);
  3034. }
  3035. template <typename T>
  3036. bool operator>=(Span<T> a, Span<const T> b) {
  3037. return !(a < b);
  3038. }
  3039. template <typename T, typename U,
  3040. typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
  3041. bool operator>=(const U& a, Span<T> b) {
  3042. return !(a < b);
  3043. }
  3044. template <typename T, typename U,
  3045. typename = span_internal::EnableIfConvertibleToSpanConst<U, T>>
  3046. bool operator>=(Span<T> a, const U& b) {
  3047. return !(a < b);
  3048. }
  3049. // MakeSpan()
  3050. //
  3051. // Constructs a mutable `Span<T>`, deducing `T` automatically from either a
  3052. // container or pointer+size.
  3053. //
  3054. // Because a read-only `Span<const T>` is implicitly constructed from container
  3055. // types regardless of whether the container itself is a const container,
  3056. // constructing mutable spans of type `Span<T>` from containers requires
  3057. // explicit constructors. The container-accepting version of `MakeSpan()`
  3058. // deduces the type of `T` by the constness of the pointer received from the
  3059. // container's `data()` member. Similarly, the pointer-accepting version returns
  3060. // a `Span<const T>` if `T` is `const`, and a `Span<T>` otherwise.
  3061. //
  3062. // Examples:
  3063. //
  3064. // void MyRoutine(phmap::Span<MyComplicatedType> a) {
  3065. // ...
  3066. // };
  3067. // // my_vector is a container of non-const types
  3068. // std::vector<MyComplicatedType> my_vector;
  3069. //
  3070. // // Constructing a Span implicitly attempts to create a Span of type
  3071. // // `Span<const T>`
  3072. // MyRoutine(my_vector); // error, type mismatch
  3073. //
  3074. // // Explicitly constructing the Span is verbose
  3075. // MyRoutine(phmap::Span<MyComplicatedType>(my_vector));
  3076. //
  3077. // // Use MakeSpan() to make an phmap::Span<T>
  3078. // MyRoutine(phmap::MakeSpan(my_vector));
  3079. //
  3080. // // Construct a span from an array ptr+size
  3081. // phmap::Span<T> my_span() {
  3082. // return phmap::MakeSpan(&array[0], num_elements_);
  3083. // }
  3084. //
  3085. template <int&... ExplicitArgumentBarrier, typename T>
  3086. constexpr Span<T> MakeSpan(T* ptr, size_t size) noexcept {
  3087. return Span<T>(ptr, size);
  3088. }
  3089. template <int&... ExplicitArgumentBarrier, typename T>
  3090. Span<T> MakeSpan(T* begin, T* end) noexcept {
  3091. return PHMAP_ASSERT(begin <= end), Span<T>(begin, end - begin);
  3092. }
  3093. template <int&... ExplicitArgumentBarrier, typename C>
  3094. constexpr auto MakeSpan(C& c) noexcept // NOLINT(runtime/references)
  3095. -> decltype(phmap::MakeSpan(span_internal::GetData(c), c.size())) {
  3096. return MakeSpan(span_internal::GetData(c), c.size());
  3097. }
  3098. template <int&... ExplicitArgumentBarrier, typename T, size_t N>
  3099. constexpr Span<T> MakeSpan(T (&array)[N]) noexcept {
  3100. return Span<T>(array, N);
  3101. }
  3102. // MakeConstSpan()
  3103. //
  3104. // Constructs a `Span<const T>` as with `MakeSpan`, deducing `T` automatically,
  3105. // but always returning a `Span<const T>`.
  3106. //
  3107. // Examples:
  3108. //
  3109. // void ProcessInts(phmap::Span<const int> some_ints);
  3110. //
  3111. // // Call with a pointer and size.
  3112. // int array[3] = { 0, 0, 0 };
  3113. // ProcessInts(phmap::MakeConstSpan(&array[0], 3));
  3114. //
  3115. // // Call with a [begin, end) pair.
  3116. // ProcessInts(phmap::MakeConstSpan(&array[0], &array[3]));
  3117. //
  3118. // // Call directly with an array.
  3119. // ProcessInts(phmap::MakeConstSpan(array));
  3120. //
  3121. // // Call with a contiguous container.
  3122. // std::vector<int> some_ints = ...;
  3123. // ProcessInts(phmap::MakeConstSpan(some_ints));
  3124. // ProcessInts(phmap::MakeConstSpan(std::vector<int>{ 0, 0, 0 }));
  3125. //
  3126. template <int&... ExplicitArgumentBarrier, typename T>
  3127. constexpr Span<const T> MakeConstSpan(T* ptr, size_t size) noexcept {
  3128. return Span<const T>(ptr, size);
  3129. }
  3130. template <int&... ExplicitArgumentBarrier, typename T>
  3131. Span<const T> MakeConstSpan(T* begin, T* end) noexcept {
  3132. return PHMAP_ASSERT(begin <= end), Span<const T>(begin, end - begin);
  3133. }
  3134. template <int&... ExplicitArgumentBarrier, typename C>
  3135. constexpr auto MakeConstSpan(const C& c) noexcept -> decltype(MakeSpan(c)) {
  3136. return MakeSpan(c);
  3137. }
  3138. template <int&... ExplicitArgumentBarrier, typename T, size_t N>
  3139. constexpr Span<const T> MakeConstSpan(const T (&array)[N]) noexcept {
  3140. return Span<const T>(array, N);
  3141. }
  3142. } // namespace phmap
  3143. // ---------------------------------------------------------------------------
  3144. // layout.h
  3145. // ---------------------------------------------------------------------------
  3146. namespace phmap {
  3147. namespace priv {
  3148. // A type wrapper that instructs `Layout` to use the specific alignment for the
  3149. // array. `Layout<..., Aligned<T, N>, ...>` has exactly the same API
  3150. // and behavior as `Layout<..., T, ...>` except that the first element of the
  3151. // array of `T` is aligned to `N` (the rest of the elements follow without
  3152. // padding).
  3153. //
  3154. // Requires: `N >= alignof(T)` and `N` is a power of 2.
  3155. template <class T, size_t N>
  3156. struct Aligned;
  3157. namespace internal_layout {
  3158. template <class T>
  3159. struct NotAligned {};
  3160. template <class T, size_t N>
  3161. struct NotAligned<const Aligned<T, N>> {
  3162. static_assert(sizeof(T) == 0, "Aligned<T, N> cannot be const-qualified");
  3163. };
  3164. template <size_t>
  3165. using IntToSize = size_t;
  3166. template <class>
  3167. using TypeToSize = size_t;
  3168. template <class T>
  3169. struct Type : NotAligned<T> {
  3170. using type = T;
  3171. };
  3172. template <class T, size_t N>
  3173. struct Type<Aligned<T, N>> {
  3174. using type = T;
  3175. };
  3176. template <class T>
  3177. struct SizeOf : NotAligned<T>, std::integral_constant<size_t, sizeof(T)> {};
  3178. template <class T, size_t N>
  3179. struct SizeOf<Aligned<T, N>> : std::integral_constant<size_t, sizeof(T)> {};
  3180. // Note: workaround for https://gcc.gnu.org/PR88115
  3181. template <class T>
  3182. struct AlignOf : NotAligned<T> {
  3183. static constexpr size_t value = alignof(T);
  3184. };
  3185. template <class T, size_t N>
  3186. struct AlignOf<Aligned<T, N>> {
  3187. static_assert(N % alignof(T) == 0,
  3188. "Custom alignment can't be lower than the type's alignment");
  3189. static constexpr size_t value = N;
  3190. };
  3191. // Does `Ts...` contain `T`?
  3192. template <class T, class... Ts>
  3193. using Contains = phmap::disjunction<std::is_same<T, Ts>...>;
  3194. template <class From, class To>
  3195. using CopyConst =
  3196. typename std::conditional<std::is_const<From>::value, const To, To>::type;
  3197. // Note: We're not qualifying this with phmap:: because it doesn't compile under
  3198. // MSVC.
  3199. template <class T>
  3200. using SliceType = Span<T>;
  3201. // This namespace contains no types. It prevents functions defined in it from
  3202. // being found by ADL.
  3203. namespace adl_barrier {
  3204. template <class Needle, class... Ts>
  3205. constexpr size_t Find(Needle, Needle, Ts...) {
  3206. static_assert(!Contains<Needle, Ts...>(), "Duplicate element type");
  3207. return 0;
  3208. }
  3209. template <class Needle, class T, class... Ts>
  3210. constexpr size_t Find(Needle, T, Ts...) {
  3211. return adl_barrier::Find(Needle(), Ts()...) + 1;
  3212. }
  3213. constexpr bool IsPow2(size_t n) { return !(n & (n - 1)); }
  3214. // Returns `q * m` for the smallest `q` such that `q * m >= n`.
  3215. // Requires: `m` is a power of two. It's enforced by IsLegalElementType below.
  3216. constexpr size_t Align(size_t n, size_t m) { return (n + m - 1) & ~(m - 1); }
  3217. constexpr size_t Min(size_t a, size_t b) { return b < a ? b : a; }
  3218. constexpr size_t Max(size_t a) { return a; }
  3219. template <class... Ts>
  3220. constexpr size_t Max(size_t a, size_t b, Ts... rest) {
  3221. return adl_barrier::Max(b < a ? a : b, rest...);
  3222. }
  3223. } // namespace adl_barrier
  3224. template <bool C>
  3225. using EnableIf = typename std::enable_if<C, int>::type;
  3226. // Can `T` be a template argument of `Layout`?
  3227. // ---------------------------------------------------------------------------
  3228. template <class T>
  3229. using IsLegalElementType = std::integral_constant<
  3230. bool, !std::is_reference<T>::value && !std::is_volatile<T>::value &&
  3231. !std::is_reference<typename Type<T>::type>::value &&
  3232. !std::is_volatile<typename Type<T>::type>::value &&
  3233. adl_barrier::IsPow2(AlignOf<T>::value)>;
  3234. template <class Elements, class SizeSeq, class OffsetSeq>
  3235. class LayoutImpl;
  3236. // ---------------------------------------------------------------------------
  3237. // Public base class of `Layout` and the result type of `Layout::Partial()`.
  3238. //
  3239. // `Elements...` contains all template arguments of `Layout` that created this
  3240. // instance.
  3241. //
  3242. // `SizeSeq...` is `[0, NumSizes)` where `NumSizes` is the number of arguments
  3243. // passed to `Layout::Partial()` or `Layout::Layout()`.
  3244. //
  3245. // `OffsetSeq...` is `[0, NumOffsets)` where `NumOffsets` is
  3246. // `Min(sizeof...(Elements), NumSizes + 1)` (the number of arrays for which we
  3247. // can compute offsets).
  3248. // ---------------------------------------------------------------------------
  3249. template <class... Elements, size_t... SizeSeq, size_t... OffsetSeq>
  3250. class LayoutImpl<std::tuple<Elements...>, phmap::index_sequence<SizeSeq...>,
  3251. phmap::index_sequence<OffsetSeq...>>
  3252. {
  3253. private:
  3254. static_assert(sizeof...(Elements) > 0, "At least one field is required");
  3255. static_assert(phmap::conjunction<IsLegalElementType<Elements>...>::value,
  3256. "Invalid element type (see IsLegalElementType)");
  3257. enum {
  3258. NumTypes = sizeof...(Elements),
  3259. NumSizes = sizeof...(SizeSeq),
  3260. NumOffsets = sizeof...(OffsetSeq),
  3261. };
  3262. // These are guaranteed by `Layout`.
  3263. static_assert(NumOffsets == adl_barrier::Min(NumTypes, NumSizes + 1),
  3264. "Internal error");
  3265. static_assert(NumTypes > 0, "Internal error");
  3266. // Returns the index of `T` in `Elements...`. Results in a compilation error
  3267. // if `Elements...` doesn't contain exactly one instance of `T`.
  3268. template <class T>
  3269. static constexpr size_t ElementIndex() {
  3270. static_assert(Contains<Type<T>, Type<typename Type<Elements>::type>...>(),
  3271. "Type not found");
  3272. return adl_barrier::Find(Type<T>(),
  3273. Type<typename Type<Elements>::type>()...);
  3274. }
  3275. template <size_t N>
  3276. using ElementAlignment =
  3277. AlignOf<typename std::tuple_element<N, std::tuple<Elements...>>::type>;
  3278. public:
  3279. // Element types of all arrays packed in a tuple.
  3280. using ElementTypes = std::tuple<typename Type<Elements>::type...>;
  3281. // Element type of the Nth array.
  3282. template <size_t N>
  3283. using ElementType = typename std::tuple_element<N, ElementTypes>::type;
  3284. constexpr explicit LayoutImpl(IntToSize<SizeSeq>... sizes)
  3285. : size_{sizes...} {}
  3286. // Alignment of the layout, equal to the strictest alignment of all elements.
  3287. // All pointers passed to the methods of layout must be aligned to this value.
  3288. static constexpr size_t Alignment() {
  3289. return adl_barrier::Max(AlignOf<Elements>::value...);
  3290. }
  3291. // Offset in bytes of the Nth array.
  3292. //
  3293. // // int[3], 4 bytes of padding, double[4].
  3294. // Layout<int, double> x(3, 4);
  3295. // assert(x.Offset<0>() == 0); // The ints starts from 0.
  3296. // assert(x.Offset<1>() == 16); // The doubles starts from 16.
  3297. //
  3298. // Requires: `N <= NumSizes && N < sizeof...(Ts)`.
  3299. template <size_t N, EnableIf<N == 0> = 0>
  3300. constexpr size_t Offset() const {
  3301. return 0;
  3302. }
  3303. template <size_t N, EnableIf<N != 0> = 0>
  3304. constexpr size_t Offset() const {
  3305. static_assert(N < NumOffsets, "Index out of bounds");
  3306. return adl_barrier::Align(
  3307. Offset<N - 1>() + SizeOf<ElementType<N - 1>>::value * size_[N - 1],
  3308. ElementAlignment<N>::value);
  3309. }
  3310. // Offset in bytes of the array with the specified element type. There must
  3311. // be exactly one such array and its zero-based index must be at most
  3312. // `NumSizes`.
  3313. //
  3314. // // int[3], 4 bytes of padding, double[4].
  3315. // Layout<int, double> x(3, 4);
  3316. // assert(x.Offset<int>() == 0); // The ints starts from 0.
  3317. // assert(x.Offset<double>() == 16); // The doubles starts from 16.
  3318. template <class T>
  3319. constexpr size_t Offset() const {
  3320. return Offset<ElementIndex<T>()>();
  3321. }
  3322. // Offsets in bytes of all arrays for which the offsets are known.
  3323. constexpr std::array<size_t, NumOffsets> Offsets() const {
  3324. return {{Offset<OffsetSeq>()...}};
  3325. }
  3326. // The number of elements in the Nth array. This is the Nth argument of
  3327. // `Layout::Partial()` or `Layout::Layout()` (zero-based).
  3328. //
  3329. // // int[3], 4 bytes of padding, double[4].
  3330. // Layout<int, double> x(3, 4);
  3331. // assert(x.Size<0>() == 3);
  3332. // assert(x.Size<1>() == 4);
  3333. //
  3334. // Requires: `N < NumSizes`.
  3335. template <size_t N>
  3336. constexpr size_t Size() const {
  3337. static_assert(N < NumSizes, "Index out of bounds");
  3338. return size_[N];
  3339. }
  3340. // The number of elements in the array with the specified element type.
  3341. // There must be exactly one such array and its zero-based index must be
  3342. // at most `NumSizes`.
  3343. //
  3344. // // int[3], 4 bytes of padding, double[4].
  3345. // Layout<int, double> x(3, 4);
  3346. // assert(x.Size<int>() == 3);
  3347. // assert(x.Size<double>() == 4);
  3348. template <class T>
  3349. constexpr size_t Size() const {
  3350. return Size<ElementIndex<T>()>();
  3351. }
  3352. // The number of elements of all arrays for which they are known.
  3353. constexpr std::array<size_t, NumSizes> Sizes() const {
  3354. return {{Size<SizeSeq>()...}};
  3355. }
  3356. // Pointer to the beginning of the Nth array.
  3357. //
  3358. // `Char` must be `[const] [signed|unsigned] char`.
  3359. //
  3360. // // int[3], 4 bytes of padding, double[4].
  3361. // Layout<int, double> x(3, 4);
  3362. // unsigned char* p = new unsigned char[x.AllocSize()];
  3363. // int* ints = x.Pointer<0>(p);
  3364. // double* doubles = x.Pointer<1>(p);
  3365. //
  3366. // Requires: `N <= NumSizes && N < sizeof...(Ts)`.
  3367. // Requires: `p` is aligned to `Alignment()`.
  3368. template <size_t N, class Char>
  3369. CopyConst<Char, ElementType<N>>* Pointer(Char* p) const {
  3370. using C = typename std::remove_const<Char>::type;
  3371. static_assert(
  3372. std::is_same<C, char>() || std::is_same<C, unsigned char>() ||
  3373. std::is_same<C, signed char>(),
  3374. "The argument must be a pointer to [const] [signed|unsigned] char");
  3375. constexpr size_t alignment = Alignment();
  3376. (void)alignment;
  3377. assert(reinterpret_cast<uintptr_t>(p) % alignment == 0);
  3378. return reinterpret_cast<CopyConst<Char, ElementType<N>>*>(p + Offset<N>());
  3379. }
  3380. // Pointer to the beginning of the array with the specified element type.
  3381. // There must be exactly one such array and its zero-based index must be at
  3382. // most `NumSizes`.
  3383. //
  3384. // `Char` must be `[const] [signed|unsigned] char`.
  3385. //
  3386. // // int[3], 4 bytes of padding, double[4].
  3387. // Layout<int, double> x(3, 4);
  3388. // unsigned char* p = new unsigned char[x.AllocSize()];
  3389. // int* ints = x.Pointer<int>(p);
  3390. // double* doubles = x.Pointer<double>(p);
  3391. //
  3392. // Requires: `p` is aligned to `Alignment()`.
  3393. template <class T, class Char>
  3394. CopyConst<Char, T>* Pointer(Char* p) const {
  3395. return Pointer<ElementIndex<T>()>(p);
  3396. }
  3397. // Pointers to all arrays for which pointers are known.
  3398. //
  3399. // `Char` must be `[const] [signed|unsigned] char`.
  3400. //
  3401. // // int[3], 4 bytes of padding, double[4].
  3402. // Layout<int, double> x(3, 4);
  3403. // unsigned char* p = new unsigned char[x.AllocSize()];
  3404. //
  3405. // int* ints;
  3406. // double* doubles;
  3407. // std::tie(ints, doubles) = x.Pointers(p);
  3408. //
  3409. // Requires: `p` is aligned to `Alignment()`.
  3410. //
  3411. // Note: We're not using ElementType alias here because it does not compile
  3412. // under MSVC.
  3413. template <class Char>
  3414. std::tuple<CopyConst<
  3415. Char, typename std::tuple_element<OffsetSeq, ElementTypes>::type>*...>
  3416. Pointers(Char* p) const {
  3417. return std::tuple<CopyConst<Char, ElementType<OffsetSeq>>*...>(
  3418. Pointer<OffsetSeq>(p)...);
  3419. }
  3420. // The Nth array.
  3421. //
  3422. // `Char` must be `[const] [signed|unsigned] char`.
  3423. //
  3424. // // int[3], 4 bytes of padding, double[4].
  3425. // Layout<int, double> x(3, 4);
  3426. // unsigned char* p = new unsigned char[x.AllocSize()];
  3427. // Span<int> ints = x.Slice<0>(p);
  3428. // Span<double> doubles = x.Slice<1>(p);
  3429. //
  3430. // Requires: `N < NumSizes`.
  3431. // Requires: `p` is aligned to `Alignment()`.
  3432. template <size_t N, class Char>
  3433. SliceType<CopyConst<Char, ElementType<N>>> Slice(Char* p) const {
  3434. return SliceType<CopyConst<Char, ElementType<N>>>(Pointer<N>(p), Size<N>());
  3435. }
  3436. // The array with the specified element type. There must be exactly one
  3437. // such array and its zero-based index must be less than `NumSizes`.
  3438. //
  3439. // `Char` must be `[const] [signed|unsigned] char`.
  3440. //
  3441. // // int[3], 4 bytes of padding, double[4].
  3442. // Layout<int, double> x(3, 4);
  3443. // unsigned char* p = new unsigned char[x.AllocSize()];
  3444. // Span<int> ints = x.Slice<int>(p);
  3445. // Span<double> doubles = x.Slice<double>(p);
  3446. //
  3447. // Requires: `p` is aligned to `Alignment()`.
  3448. template <class T, class Char>
  3449. SliceType<CopyConst<Char, T>> Slice(Char* p) const {
  3450. return Slice<ElementIndex<T>()>(p);
  3451. }
  3452. // All arrays with known sizes.
  3453. //
  3454. // `Char` must be `[const] [signed|unsigned] char`.
  3455. //
  3456. // // int[3], 4 bytes of padding, double[4].
  3457. // Layout<int, double> x(3, 4);
  3458. // unsigned char* p = new unsigned char[x.AllocSize()];
  3459. //
  3460. // Span<int> ints;
  3461. // Span<double> doubles;
  3462. // std::tie(ints, doubles) = x.Slices(p);
  3463. //
  3464. // Requires: `p` is aligned to `Alignment()`.
  3465. //
  3466. // Note: We're not using ElementType alias here because it does not compile
  3467. // under MSVC.
  3468. template <class Char>
  3469. std::tuple<SliceType<CopyConst<
  3470. Char, typename std::tuple_element<SizeSeq, ElementTypes>::type>>...>
  3471. Slices(Char* p) const {
  3472. // Workaround for https://gcc.gnu.org/bugzilla/show_bug.cgi?id=63875 (fixed
  3473. // in 6.1).
  3474. (void)p;
  3475. return std::tuple<SliceType<CopyConst<Char, ElementType<SizeSeq>>>...>(
  3476. Slice<SizeSeq>(p)...);
  3477. }
  3478. // The size of the allocation that fits all arrays.
  3479. //
  3480. // // int[3], 4 bytes of padding, double[4].
  3481. // Layout<int, double> x(3, 4);
  3482. // unsigned char* p = new unsigned char[x.AllocSize()]; // 48 bytes
  3483. //
  3484. // Requires: `NumSizes == sizeof...(Ts)`.
  3485. constexpr size_t AllocSize() const {
  3486. static_assert(NumTypes == NumSizes, "You must specify sizes of all fields");
  3487. return Offset<NumTypes - 1>() +
  3488. SizeOf<ElementType<NumTypes - 1>>::value * size_[NumTypes - 1];
  3489. }
  3490. // If built with --config=asan, poisons padding bytes (if any) in the
  3491. // allocation. The pointer must point to a memory block at least
  3492. // `AllocSize()` bytes in length.
  3493. //
  3494. // `Char` must be `[const] [signed|unsigned] char`.
  3495. //
  3496. // Requires: `p` is aligned to `Alignment()`.
  3497. template <class Char, size_t N = NumOffsets - 1, EnableIf<N == 0> = 0>
  3498. void PoisonPadding(const Char* p) const {
  3499. Pointer<0>(p); // verify the requirements on `Char` and `p`
  3500. }
  3501. template <class Char, size_t N = NumOffsets - 1, EnableIf<N != 0> = 0>
  3502. void PoisonPadding(const Char* p) const {
  3503. static_assert(N < NumOffsets, "Index out of bounds");
  3504. (void)p;
  3505. #ifdef ADDRESS_SANITIZER
  3506. PoisonPadding<Char, N - 1>(p);
  3507. // The `if` is an optimization. It doesn't affect the observable behaviour.
  3508. if (ElementAlignment<N - 1>::value % ElementAlignment<N>::value) {
  3509. size_t start =
  3510. Offset<N - 1>() + SizeOf<ElementType<N - 1>>::value * size_[N - 1];
  3511. ASAN_POISON_MEMORY_REGION(p + start, Offset<N>() - start);
  3512. }
  3513. #endif
  3514. }
  3515. private:
  3516. // Arguments of `Layout::Partial()` or `Layout::Layout()`.
  3517. size_t size_[NumSizes > 0 ? NumSizes : 1];
  3518. };
  3519. template <size_t NumSizes, class... Ts>
  3520. using LayoutType = LayoutImpl<
  3521. std::tuple<Ts...>, phmap::make_index_sequence<NumSizes>,
  3522. phmap::make_index_sequence<adl_barrier::Min(sizeof...(Ts), NumSizes + 1)>>;
  3523. } // namespace internal_layout
  3524. // ---------------------------------------------------------------------------
  3525. // Descriptor of arrays of various types and sizes laid out in memory one after
  3526. // another. See the top of the file for documentation.
  3527. //
  3528. // Check out the public API of internal_layout::LayoutImpl above. The type is
  3529. // internal to the library but its methods are public, and they are inherited
  3530. // by `Layout`.
  3531. // ---------------------------------------------------------------------------
  3532. template <class... Ts>
  3533. class Layout : public internal_layout::LayoutType<sizeof...(Ts), Ts...>
  3534. {
  3535. public:
  3536. static_assert(sizeof...(Ts) > 0, "At least one field is required");
  3537. static_assert(
  3538. phmap::conjunction<internal_layout::IsLegalElementType<Ts>...>::value,
  3539. "Invalid element type (see IsLegalElementType)");
  3540. template <size_t NumSizes>
  3541. using PartialType = internal_layout::LayoutType<NumSizes, Ts...>;
  3542. template <class... Sizes>
  3543. static constexpr PartialType<sizeof...(Sizes)> Partial(Sizes&&... sizes) {
  3544. static_assert(sizeof...(Sizes) <= sizeof...(Ts), "");
  3545. return PartialType<sizeof...(Sizes)>(phmap::forward<Sizes>(sizes)...);
  3546. }
  3547. // Creates a layout with the sizes of all arrays specified. If you know
  3548. // only the sizes of the first N arrays (where N can be zero), you can use
  3549. // `Partial()` defined above. The constructor is essentially equivalent to
  3550. // calling `Partial()` and passing in all array sizes; the constructor is
  3551. // provided as a convenient abbreviation.
  3552. //
  3553. // Note: The sizes of the arrays must be specified in number of elements,
  3554. // not in bytes.
  3555. constexpr explicit Layout(internal_layout::TypeToSize<Ts>... sizes)
  3556. : internal_layout::LayoutType<sizeof...(Ts), Ts...>(sizes...) {}
  3557. };
  3558. #ifdef _MSC_VER
  3559. #pragma warning(push)
  3560. // warning warning C4324: structure was padded due to alignment specifier
  3561. #pragma warning(disable : 4324)
  3562. #endif
  3563. // ----------------------------------------------------------------------------
  3564. // Allocates at least n bytes aligned to the specified alignment.
  3565. // Alignment must be a power of 2. It must be positive.
  3566. //
  3567. // Note that many allocators don't honor alignment requirements above certain
  3568. // threshold (usually either alignof(std::max_align_t) or alignof(void*)).
  3569. // Allocate() doesn't apply alignment corrections. If the underlying allocator
  3570. // returns insufficiently alignment pointer, that's what you are going to get.
  3571. // ----------------------------------------------------------------------------
  3572. template <size_t Alignment, class Alloc>
  3573. void* Allocate(Alloc* alloc, size_t n) {
  3574. static_assert(Alignment > 0, "");
  3575. assert(n && "n must be positive");
  3576. struct alignas(Alignment) M {};
  3577. using A = typename phmap::allocator_traits<Alloc>::template rebind_alloc<M>;
  3578. using AT = typename phmap::allocator_traits<Alloc>::template rebind_traits<M>;
  3579. A mem_alloc(*alloc);
  3580. void* p = AT::allocate(mem_alloc, (n + sizeof(M) - 1) / sizeof(M));
  3581. assert(reinterpret_cast<uintptr_t>(p) % Alignment == 0 &&
  3582. "allocator does not respect alignment");
  3583. return p;
  3584. }
  3585. // ----------------------------------------------------------------------------
  3586. // The pointer must have been previously obtained by calling
  3587. // Allocate<Alignment>(alloc, n).
  3588. // ----------------------------------------------------------------------------
  3589. template <size_t Alignment, class Alloc>
  3590. void Deallocate(Alloc* alloc, void* p, size_t n) {
  3591. static_assert(Alignment > 0, "");
  3592. assert(n && "n must be positive");
  3593. struct alignas(Alignment) M {};
  3594. using A = typename phmap::allocator_traits<Alloc>::template rebind_alloc<M>;
  3595. using AT = typename phmap::allocator_traits<Alloc>::template rebind_traits<M>;
  3596. A mem_alloc(*alloc);
  3597. AT::deallocate(mem_alloc, static_cast<M*>(p),
  3598. (n + sizeof(M) - 1) / sizeof(M));
  3599. }
  3600. #ifdef _MSC_VER
  3601. #pragma warning(pop)
  3602. #endif
  3603. // Helper functions for asan and msan.
  3604. // ----------------------------------------------------------------------------
  3605. LL_INLINE void SanitizerPoisonMemoryRegion(const void* m, size_t s) {
  3606. #ifdef ADDRESS_SANITIZER
  3607. ASAN_POISON_MEMORY_REGION(m, s);
  3608. #endif
  3609. #ifdef MEMORY_SANITIZER
  3610. __msan_poison(m, s);
  3611. #endif
  3612. (void)m;
  3613. (void)s;
  3614. }
  3615. LL_INLINE void SanitizerUnpoisonMemoryRegion(const void* m, size_t s) {
  3616. #ifdef ADDRESS_SANITIZER
  3617. ASAN_UNPOISON_MEMORY_REGION(m, s);
  3618. #endif
  3619. #ifdef MEMORY_SANITIZER
  3620. __msan_unpoison(m, s);
  3621. #endif
  3622. (void)m;
  3623. (void)s;
  3624. }
  3625. template <typename T>
  3626. LL_INLINE void SanitizerPoisonObject(const T* object) {
  3627. SanitizerPoisonMemoryRegion(object, sizeof(T));
  3628. }
  3629. template <typename T>
  3630. LL_INLINE void SanitizerUnpoisonObject(const T* object) {
  3631. SanitizerUnpoisonMemoryRegion(object, sizeof(T));
  3632. }
  3633. } // namespace priv
  3634. } // namespace phmap
  3635. // ---------------------------------------------------------------------------
  3636. // thread_annotations.h
  3637. // ---------------------------------------------------------------------------
  3638. #if defined(__clang__)
  3639. #define PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(x) __attribute__((x))
  3640. #else
  3641. #define PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(x) // no-op
  3642. #endif
  3643. #define PHMAP_GUARDED_BY(x) PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(guarded_by(x))
  3644. #define PHMAP_PT_GUARDED_BY(x) PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(pt_guarded_by(x))
  3645. #define PHMAP_ACQUIRED_AFTER(...) \
  3646. PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(acquired_after(__VA_ARGS__))
  3647. #define PHMAP_ACQUIRED_BEFORE(...) \
  3648. PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(acquired_before(__VA_ARGS__))
  3649. #define PHMAP_EXCLUSIVE_LOCKS_REQUIRED(...) \
  3650. PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(exclusive_locks_required(__VA_ARGS__))
  3651. #define PHMAP_SHARED_LOCKS_REQUIRED(...) \
  3652. PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(shared_locks_required(__VA_ARGS__))
  3653. #define PHMAP_LOCKS_EXCLUDED(...) \
  3654. PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(locks_excluded(__VA_ARGS__))
  3655. #define PHMAP_LOCK_RETURNED(x) \
  3656. PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(lock_returned(x))
  3657. #define PHMAP_LOCKABLE \
  3658. PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(lockable)
  3659. #define PHMAP_SCOPED_LOCKABLE \
  3660. PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(scoped_lockable)
  3661. #define PHMAP_EXCLUSIVE_LOCK_FUNCTION(...) \
  3662. PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(exclusive_lock_function(__VA_ARGS__))
  3663. #define PHMAP_SHARED_LOCK_FUNCTION(...) \
  3664. PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(shared_lock_function(__VA_ARGS__))
  3665. #define PHMAP_UNLOCK_FUNCTION(...) \
  3666. PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(unlock_function(__VA_ARGS__))
  3667. #define PHMAP_EXCLUSIVE_TRYLOCK_FUNCTION(...) \
  3668. PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(exclusive_trylock_function(__VA_ARGS__))
  3669. #define PHMAP_SHARED_TRYLOCK_FUNCTION(...) \
  3670. PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(shared_trylock_function(__VA_ARGS__))
  3671. #define PHMAP_ASSERT_EXCLUSIVE_LOCK(...) \
  3672. PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(assert_exclusive_lock(__VA_ARGS__))
  3673. #define PHMAP_ASSERT_SHARED_LOCK(...) \
  3674. PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(assert_shared_lock(__VA_ARGS__))
  3675. #define PHMAP_NO_THREAD_SAFETY_ANALYSIS \
  3676. PHMAP_THREAD_ANNOTATION_ATTRIBUTE__(no_thread_safety_analysis)
  3677. //------------------------------------------------------------------------------
  3678. // Tool-Supplied Annotations
  3679. //------------------------------------------------------------------------------
  3680. // TS_UNCHECKED should be placed around lock expressions that are not valid
  3681. // C++ syntax, but which are present for documentation purposes. These
  3682. // annotations will be ignored by the analysis.
  3683. #define PHMAP_TS_UNCHECKED(x) ""
  3684. // TS_FIXME is used to mark lock expressions that are not valid C++ syntax.
  3685. // It is used by automated tools to mark and disable invalid expressions.
  3686. // The annotation should either be fixed, or changed to TS_UNCHECKED.
  3687. #define PHMAP_TS_FIXME(x) ""
  3688. // Like NO_THREAD_SAFETY_ANALYSIS, this turns off checking within the body of
  3689. // a particular function. However, this attribute is used to mark functions
  3690. // that are incorrect and need to be fixed. It is used by automated tools to
  3691. // avoid breaking the build when the analysis is updated.
  3692. // Code owners are expected to eventually fix the routine.
  3693. #define PHMAP_NO_THREAD_SAFETY_ANALYSIS_FIXME PHMAP_NO_THREAD_SAFETY_ANALYSIS
  3694. // Similar to NO_THREAD_SAFETY_ANALYSIS_FIXME, this macro marks a GUARDED_BY
  3695. // annotation that needs to be fixed, because it is producing thread safety
  3696. // warning. It disables the GUARDED_BY.
  3697. #define PHMAP_GUARDED_BY_FIXME(x)
  3698. // Disables warnings for a single read operation. This can be used to avoid
  3699. // warnings when it is known that the read is not actually involved in a race,
  3700. // but the compiler cannot confirm that.
  3701. #define PHMAP_TS_UNCHECKED_READ(x) thread_safety_analysis::ts_unchecked_read(x)
  3702. namespace phmap {
  3703. namespace thread_safety_analysis {
  3704. // Takes a reference to a guarded data member, and returns an unguarded
  3705. // reference.
  3706. template <typename T>
  3707. LL_INLINE const T& ts_unchecked_read(const T& v) PHMAP_NO_THREAD_SAFETY_ANALYSIS {
  3708. return v;
  3709. }
  3710. template <typename T>
  3711. LL_INLINE T& ts_unchecked_read(T& v) PHMAP_NO_THREAD_SAFETY_ANALYSIS {
  3712. return v;
  3713. }
  3714. } // namespace thread_safety_analysis
  3715. namespace priv {
  3716. namespace memory_internal {
  3717. // ----------------------------------------------------------------------------
  3718. // If Pair is a standard-layout type, OffsetOf<Pair>::kFirst and
  3719. // OffsetOf<Pair>::kSecond are equivalent to offsetof(Pair, first) and
  3720. // offsetof(Pair, second) respectively. Otherwise they are -1.
  3721. //
  3722. // The purpose of OffsetOf is to avoid calling offsetof() on non-standard-layout
  3723. // type, which is non-portable.
  3724. // ----------------------------------------------------------------------------
  3725. template <class Pair, class = std::true_type>
  3726. struct OffsetOf {
  3727. static constexpr size_t kFirst = static_cast<size_t>(-1);
  3728. static constexpr size_t kSecond = static_cast<size_t>(-1);
  3729. };
  3730. template <class Pair>
  3731. struct OffsetOf<Pair, typename std::is_standard_layout<Pair>::type>
  3732. {
  3733. static constexpr size_t kFirst = offsetof(Pair, first);
  3734. static constexpr size_t kSecond = offsetof(Pair, second);
  3735. };
  3736. // ----------------------------------------------------------------------------
  3737. template <class K, class V>
  3738. struct IsLayoutCompatible
  3739. {
  3740. private:
  3741. struct Pair {
  3742. K first;
  3743. V second;
  3744. };
  3745. // Is P layout-compatible with Pair?
  3746. template <class P>
  3747. static constexpr bool LayoutCompatible() {
  3748. return std::is_standard_layout<P>() && sizeof(P) == sizeof(Pair) &&
  3749. alignof(P) == alignof(Pair) &&
  3750. memory_internal::OffsetOf<P>::kFirst ==
  3751. memory_internal::OffsetOf<Pair>::kFirst &&
  3752. memory_internal::OffsetOf<P>::kSecond ==
  3753. memory_internal::OffsetOf<Pair>::kSecond;
  3754. }
  3755. public:
  3756. // Whether pair<const K, V> and pair<K, V> are layout-compatible. If they are,
  3757. // then it is safe to store them in a union and read from either.
  3758. static constexpr bool value = std::is_standard_layout<K>() &&
  3759. std::is_standard_layout<Pair>() &&
  3760. memory_internal::OffsetOf<Pair>::kFirst == 0 &&
  3761. LayoutCompatible<std::pair<K, V>>() &&
  3762. LayoutCompatible<std::pair<const K, V>>();
  3763. };
  3764. } // namespace memory_internal
  3765. // ----------------------------------------------------------------------------
  3766. // The internal storage type for key-value containers like flat_hash_map.
  3767. //
  3768. // It is convenient for the value_type of a flat_hash_map<K, V> to be
  3769. // pair<const K, V>; the "const K" prevents accidental modification of the key
  3770. // when dealing with the reference returned from find() and similar methods.
  3771. // However, this creates other problems; we want to be able to emplace(K, V)
  3772. // efficiently with move operations, and similarly be able to move a
  3773. // pair<K, V> in insert().
  3774. //
  3775. // The solution is this union, which aliases the const and non-const versions
  3776. // of the pair. This also allows flat_hash_map<const K, V> to work, even though
  3777. // that has the same efficiency issues with move in emplace() and insert() -
  3778. // but people do it anyway.
  3779. //
  3780. // If kMutableKeys is false, only the value member can be accessed.
  3781. //
  3782. // If kMutableKeys is true, key can be accessed through all slots while value
  3783. // and mutable_value must be accessed only via INITIALIZED slots. Slots are
  3784. // created and destroyed via mutable_value so that the key can be moved later.
  3785. //
  3786. // Accessing one of the union fields while the other is active is safe as
  3787. // long as they are layout-compatible, which is guaranteed by the definition of
  3788. // kMutableKeys. For C++11, the relevant section of the standard is
  3789. // https://timsong-cpp.github.io/cppwp/n3337/class.mem#19 (9.2.19)
  3790. // ----------------------------------------------------------------------------
  3791. template <class K, class V>
  3792. union map_slot_type
  3793. {
  3794. map_slot_type() {}
  3795. ~map_slot_type() = delete;
  3796. map_slot_type(const map_slot_type&) = delete;
  3797. map_slot_type& operator=(const map_slot_type&) = delete;
  3798. using value_type = std::pair<const K, V>;
  3799. using mutable_value_type = std::pair<K, V>;
  3800. value_type value;
  3801. mutable_value_type mutable_value;
  3802. K key;
  3803. };
  3804. // ----------------------------------------------------------------------------
  3805. // ----------------------------------------------------------------------------
  3806. template <class K, class V>
  3807. struct map_slot_policy
  3808. {
  3809. using slot_type = map_slot_type<K, V>;
  3810. using value_type = std::pair<const K, V>;
  3811. using mutable_value_type = std::pair<K, V>;
  3812. private:
  3813. static void emplace(slot_type* slot) {
  3814. // The construction of union doesn't do anything at runtime but it allows us
  3815. // to access its members without violating aliasing rules.
  3816. new (slot) slot_type;
  3817. }
  3818. // If pair<const K, V> and pair<K, V> are layout-compatible, we can accept one
  3819. // or the other via slot_type. We are also free to access the key via
  3820. // slot_type::key in this case.
  3821. using kMutableKeys = memory_internal::IsLayoutCompatible<K, V>;
  3822. public:
  3823. static value_type& element(slot_type* slot) { return slot->value; }
  3824. static const value_type& element(const slot_type* slot) {
  3825. return slot->value;
  3826. }
  3827. static const K& key(const slot_type* slot) {
  3828. return kMutableKeys::value ? slot->key : slot->value.first;
  3829. }
  3830. template <class Allocator, class... Args>
  3831. static void construct(Allocator* alloc, slot_type* slot, Args&&... args) {
  3832. emplace(slot);
  3833. if (kMutableKeys::value) {
  3834. phmap::allocator_traits<Allocator>::construct(*alloc, &slot->mutable_value,
  3835. std::forward<Args>(args)...);
  3836. } else {
  3837. phmap::allocator_traits<Allocator>::construct(*alloc, &slot->value,
  3838. std::forward<Args>(args)...);
  3839. }
  3840. }
  3841. // Construct this slot by moving from another slot.
  3842. template <class Allocator>
  3843. static void construct(Allocator* alloc, slot_type* slot, slot_type* other) {
  3844. emplace(slot);
  3845. if (kMutableKeys::value) {
  3846. phmap::allocator_traits<Allocator>::construct(
  3847. *alloc, &slot->mutable_value, std::move(other->mutable_value));
  3848. } else {
  3849. phmap::allocator_traits<Allocator>::construct(*alloc, &slot->value,
  3850. std::move(other->value));
  3851. }
  3852. }
  3853. template <class Allocator>
  3854. static void destroy(Allocator* alloc, slot_type* slot) {
  3855. if (kMutableKeys::value) {
  3856. phmap::allocator_traits<Allocator>::destroy(*alloc, &slot->mutable_value);
  3857. } else {
  3858. phmap::allocator_traits<Allocator>::destroy(*alloc, &slot->value);
  3859. }
  3860. }
  3861. template <class Allocator>
  3862. static void transfer(Allocator* alloc, slot_type* new_slot,
  3863. slot_type* old_slot) {
  3864. emplace(new_slot);
  3865. if (kMutableKeys::value) {
  3866. phmap::allocator_traits<Allocator>::construct(
  3867. *alloc, &new_slot->mutable_value, std::move(old_slot->mutable_value));
  3868. } else {
  3869. phmap::allocator_traits<Allocator>::construct(*alloc, &new_slot->value,
  3870. std::move(old_slot->value));
  3871. }
  3872. destroy(alloc, old_slot);
  3873. }
  3874. template <class Allocator>
  3875. static void swap(Allocator* alloc, slot_type* a, slot_type* b) {
  3876. if (kMutableKeys::value) {
  3877. using std::swap;
  3878. swap(a->mutable_value, b->mutable_value);
  3879. } else {
  3880. value_type tmp = std::move(a->value);
  3881. phmap::allocator_traits<Allocator>::destroy(*alloc, &a->value);
  3882. phmap::allocator_traits<Allocator>::construct(*alloc, &a->value,
  3883. std::move(b->value));
  3884. phmap::allocator_traits<Allocator>::destroy(*alloc, &b->value);
  3885. phmap::allocator_traits<Allocator>::construct(*alloc, &b->value,
  3886. std::move(tmp));
  3887. }
  3888. }
  3889. template <class Allocator>
  3890. static void move(Allocator* alloc, slot_type* src, slot_type* dest) {
  3891. if (kMutableKeys::value) {
  3892. dest->mutable_value = std::move(src->mutable_value);
  3893. } else {
  3894. phmap::allocator_traits<Allocator>::destroy(*alloc, &dest->value);
  3895. phmap::allocator_traits<Allocator>::construct(*alloc, &dest->value,
  3896. std::move(src->value));
  3897. }
  3898. }
  3899. template <class Allocator>
  3900. static void move(Allocator* alloc, slot_type* first, slot_type* last,
  3901. slot_type* result) {
  3902. for (slot_type *src = first, *dest = result; src != last; ++src, ++dest)
  3903. move(alloc, src, dest);
  3904. }
  3905. };
  3906. } // namespace priv
  3907. } // phmap
  3908. namespace phmap {
  3909. #if PHMAP_USE_BOOST_MUTEX && defined(BOOST_THREAD_LOCK_OPTIONS_HPP)
  3910. using defer_lock_t = boost::defer_lock_t;
  3911. using try_to_lock_t = boost::try_to_lock_t;
  3912. using adopt_lock_t = boost::adopt_lock_t;
  3913. #else
  3914. struct adopt_lock_t { explicit adopt_lock_t() = default; };
  3915. struct defer_lock_t { explicit defer_lock_t() = default; };
  3916. struct try_to_lock_t { explicit try_to_lock_t() = default; };
  3917. #endif
  3918. // -----------------------------------------------------------------------------
  3919. // NullMutex
  3920. // -----------------------------------------------------------------------------
  3921. // A class that implements the Mutex interface, but does nothing. This is to be
  3922. // used as a default template parameters for classes who provide optional
  3923. // internal locking (like phmap::parallel_flat_hash_map).
  3924. // -----------------------------------------------------------------------------
  3925. class NullMutex {
  3926. public:
  3927. LL_INLINE NullMutex() {}
  3928. LL_INLINE ~NullMutex() {}
  3929. LL_INLINE void lock() {}
  3930. LL_INLINE void unlock() {}
  3931. LL_INLINE bool try_lock() { return true; }
  3932. LL_INLINE void lock_shared() {}
  3933. LL_INLINE void unlock_shared() {}
  3934. LL_INLINE bool try_lock_shared() { return true; }
  3935. };
  3936. // ------------------------ lockable object used internally -------------------------
  3937. template <class MutexType>
  3938. class LockableBaseImpl
  3939. {
  3940. public:
  3941. // ----------------------------------------------------
  3942. struct DoNothing
  3943. {
  3944. using mutex_type = MutexType;
  3945. LL_INLINE DoNothing() noexcept {}
  3946. LL_INLINE explicit DoNothing(mutex_type& ) noexcept {}
  3947. LL_INLINE explicit DoNothing(mutex_type& , mutex_type&) noexcept {}
  3948. LL_INLINE DoNothing(mutex_type&, phmap::adopt_lock_t) noexcept {}
  3949. LL_INLINE DoNothing(mutex_type&, phmap::defer_lock_t) noexcept {}
  3950. LL_INLINE DoNothing(mutex_type&, phmap::try_to_lock_t) {}
  3951. template<class T> explicit LL_INLINE DoNothing(T&&) {}
  3952. LL_INLINE DoNothing& operator=(const DoNothing&) { return *this; }
  3953. LL_INLINE DoNothing& operator=(DoNothing&&) noexcept { return *this; }
  3954. LL_INLINE void swap(DoNothing &) noexcept {}
  3955. LL_INLINE bool owns_lock() const noexcept { return true; }
  3956. LL_INLINE void lock() {}
  3957. LL_INLINE void unlock() {}
  3958. LL_INLINE void lock_shared() {}
  3959. LL_INLINE void unlock_shared() {}
  3960. LL_INLINE bool switch_to_unique() { return false; }
  3961. };
  3962. // ----------------------------------------------------
  3963. class WriteLock
  3964. {
  3965. public:
  3966. using mutex_type = MutexType;
  3967. WriteLock() : m_(nullptr), locked_(false) {}
  3968. explicit WriteLock(mutex_type &m) : m_(&m) {
  3969. m_->lock();
  3970. locked_ = true;
  3971. }
  3972. WriteLock(mutex_type& m, adopt_lock_t) noexcept :
  3973. m_(&m), locked_(true)
  3974. {}
  3975. WriteLock(mutex_type& m, defer_lock_t) noexcept :
  3976. m_(&m), locked_(false)
  3977. {}
  3978. WriteLock(mutex_type& m, try_to_lock_t) :
  3979. m_(&m), locked_(false) {
  3980. m_->try_lock();
  3981. }
  3982. WriteLock(WriteLock &&o) noexcept :
  3983. m_(std::move(o.m_)), locked_(std::move(o.locked_)) {
  3984. o.locked_ = false;
  3985. o.m_ = nullptr;
  3986. }
  3987. WriteLock& operator=(WriteLock&& other) noexcept {
  3988. WriteLock temp(std::move(other));
  3989. swap(temp);
  3990. return *this;
  3991. }
  3992. ~WriteLock() {
  3993. if (locked_)
  3994. m_->unlock();
  3995. }
  3996. void lock() {
  3997. if (!locked_) {
  3998. m_->lock();
  3999. locked_ = true;
  4000. }
  4001. }
  4002. void unlock() {
  4003. if (locked_) {
  4004. m_->unlock();
  4005. locked_ = false;
  4006. }
  4007. }
  4008. bool try_lock() {
  4009. if (locked_)
  4010. return true;
  4011. locked_ = m_->try_lock();
  4012. return locked_;
  4013. }
  4014. bool owns_lock() const noexcept { return locked_; }
  4015. void swap(WriteLock &o) noexcept {
  4016. std::swap(m_, o.m_);
  4017. std::swap(locked_, o.locked_);
  4018. }
  4019. mutex_type *mutex() const noexcept { return m_; }
  4020. bool switch_to_unique() { return false; }
  4021. private:
  4022. mutex_type *m_;
  4023. bool locked_;
  4024. };
  4025. // ----------------------------------------------------
  4026. class ReadLock
  4027. {
  4028. public:
  4029. using mutex_type = MutexType;
  4030. ReadLock() : m_(nullptr), locked_(false) {}
  4031. explicit ReadLock(mutex_type &m) : m_(&m) {
  4032. m_->lock_shared();
  4033. locked_ = true;
  4034. }
  4035. ReadLock(mutex_type& m, adopt_lock_t) noexcept :
  4036. m_(&m), locked_(true)
  4037. {}
  4038. ReadLock(mutex_type& m, defer_lock_t) noexcept :
  4039. m_(&m), locked_(false)
  4040. {}
  4041. ReadLock(mutex_type& m, try_to_lock_t) :
  4042. m_(&m), locked_(false) {
  4043. m_->try_lock_shared();
  4044. }
  4045. ReadLock(ReadLock &&o) noexcept :
  4046. m_(std::move(o.m_)), locked_(std::move(o.locked_)) {
  4047. o.locked_ = false;
  4048. o.m_ = nullptr;
  4049. }
  4050. ReadLock& operator=(ReadLock&& other) noexcept {
  4051. ReadLock temp(std::move(other));
  4052. swap(temp);
  4053. return *this;
  4054. }
  4055. ~ReadLock() {
  4056. if (locked_)
  4057. m_->unlock_shared();
  4058. }
  4059. void lock() {
  4060. if (!locked_) {
  4061. m_->lock_shared();
  4062. locked_ = true;
  4063. }
  4064. }
  4065. void unlock() {
  4066. if (locked_) {
  4067. m_->unlock_shared();
  4068. locked_ = false;
  4069. }
  4070. }
  4071. bool try_lock() {
  4072. if (locked_)
  4073. return true;
  4074. locked_ = m_->try_lock_shared();
  4075. return locked_;
  4076. }
  4077. bool owns_lock() const noexcept { return locked_; }
  4078. void swap(ReadLock &o) noexcept {
  4079. std::swap(m_, o.m_);
  4080. std::swap(locked_, o.locked_);
  4081. }
  4082. mutex_type *mutex() const noexcept { return m_; }
  4083. bool switch_to_unique() { return false; }
  4084. private:
  4085. mutex_type *m_;
  4086. bool locked_;
  4087. };
  4088. // ----------------------------------------------------
  4089. class ReadWriteLock
  4090. {
  4091. public:
  4092. using mutex_type = MutexType;
  4093. ReadWriteLock() : m_(nullptr), locked_(false), locked_shared_(false) {}
  4094. explicit ReadWriteLock(mutex_type &m) : m_(&m), locked_(false), locked_shared_(true) {
  4095. m_->lock_shared();
  4096. }
  4097. ReadWriteLock(mutex_type& m, defer_lock_t) noexcept :
  4098. m_(&m), locked_(false), locked_shared_(false)
  4099. {}
  4100. ReadWriteLock(ReadWriteLock &&o) noexcept :
  4101. m_(std::move(o.m_)), locked_(o.locked_), locked_shared_(o.locked_shared_) {
  4102. o.locked_ = false;
  4103. o.locked_shared_ = false;
  4104. o.m_ = nullptr;
  4105. }
  4106. ReadWriteLock& operator=(ReadWriteLock&& other) noexcept {
  4107. ReadWriteLock temp(std::move(other));
  4108. swap(temp);
  4109. return *this;
  4110. }
  4111. ~ReadWriteLock() {
  4112. if (locked_shared_)
  4113. m_->unlock_shared();
  4114. else if (locked_)
  4115. m_->unlock();
  4116. }
  4117. void lock_shared() {
  4118. assert(!locked_);
  4119. if (!locked_shared_) {
  4120. m_->lock_shared();
  4121. locked_shared_ = true;
  4122. }
  4123. }
  4124. void unlock_shared() {
  4125. if (locked_shared_) {
  4126. m_->unlock_shared();
  4127. locked_shared_ = false;
  4128. }
  4129. }
  4130. void lock() {
  4131. assert(!locked_shared_);
  4132. if (!locked_) {
  4133. m_->lock();
  4134. locked_ = true;
  4135. }
  4136. }
  4137. void unlock() {
  4138. if (locked_) {
  4139. m_->unlock();
  4140. locked_ = false;
  4141. }
  4142. }
  4143. bool owns_lock() const noexcept { return locked_; }
  4144. bool owns_shared_lock() const noexcept { return locked_shared_; }
  4145. void swap(ReadWriteLock &o) noexcept {
  4146. std::swap(m_, o.m_);
  4147. std::swap(locked_, o.locked_);
  4148. std::swap(locked_shared_, o.locked_shared_);
  4149. }
  4150. mutex_type *mutex() const noexcept { return m_; }
  4151. bool switch_to_unique() {
  4152. assert(locked_shared_);
  4153. unlock_shared();
  4154. lock();
  4155. return true;
  4156. }
  4157. private:
  4158. mutex_type *m_;
  4159. bool locked_;
  4160. bool locked_shared_;
  4161. };
  4162. // ----------------------------------------------------
  4163. class WriteLocks
  4164. {
  4165. public:
  4166. using mutex_type = MutexType;
  4167. explicit WriteLocks(mutex_type& m1, mutex_type& m2) :
  4168. _m1(m1), _m2(m2)
  4169. {
  4170. std::lock(m1, m2);
  4171. }
  4172. WriteLocks(adopt_lock_t, mutex_type& m1, mutex_type& m2) :
  4173. _m1(m1), _m2(m2)
  4174. { // adopt means we already own the mutexes
  4175. }
  4176. ~WriteLocks()
  4177. {
  4178. _m1.unlock();
  4179. _m2.unlock();
  4180. }
  4181. WriteLocks(WriteLocks const&) = delete;
  4182. WriteLocks& operator=(WriteLocks const&) = delete;
  4183. private:
  4184. mutex_type& _m1;
  4185. mutex_type& _m2;
  4186. };
  4187. // ----------------------------------------------------
  4188. class ReadLocks
  4189. {
  4190. public:
  4191. using mutex_type = MutexType;
  4192. explicit ReadLocks(mutex_type& m1, mutex_type& m2) :
  4193. _m1(m1), _m2(m2)
  4194. {
  4195. _m1.lock_shared();
  4196. _m2.lock_shared();
  4197. }
  4198. ReadLocks(adopt_lock_t, mutex_type& m1, mutex_type& m2) :
  4199. _m1(m1), _m2(m2)
  4200. { // adopt means we already own the mutexes
  4201. }
  4202. ~ReadLocks()
  4203. {
  4204. _m1.unlock_shared();
  4205. _m2.unlock_shared();
  4206. }
  4207. ReadLocks(ReadLocks const&) = delete;
  4208. ReadLocks& operator=(ReadLocks const&) = delete;
  4209. private:
  4210. mutex_type& _m1;
  4211. mutex_type& _m2;
  4212. };
  4213. };
  4214. // ------------------------ holds a mutex ------------------------------------
  4215. // Default implementation for Lockable, should work fine for std::mutex
  4216. // -----------------------------------
  4217. // use as:
  4218. // using Lockable = phmap::LockableImpl<mutex_type>;
  4219. // Lockable m;
  4220. //
  4221. // Lockable::ReadWriteLock read_lock(m); // take a lock (read if supported, otherwise write)
  4222. // ... do something
  4223. //
  4224. // m.switch_to_unique(); // returns true if we had a read lock and switched to write
  4225. // // now locked for write
  4226. //
  4227. // ---------------------------------------------------------------------------
  4228. // Generic mutex support (always write locks)
  4229. // --------------------------------------------------------------------------
  4230. template <class Mtx_>
  4231. class LockableImpl : public Mtx_
  4232. {
  4233. public:
  4234. using mutex_type = Mtx_;
  4235. using Base = LockableBaseImpl<Mtx_>;
  4236. using SharedLock = typename Base::WriteLock;
  4237. using UniqueLock = typename Base::WriteLock;
  4238. using ReadWriteLock = typename Base::WriteLock;
  4239. using SharedLocks = typename Base::WriteLocks;
  4240. using UniqueLocks = typename Base::WriteLocks;
  4241. };
  4242. // ---------------------------------------------------------------------------
  4243. // Null mutex (no-op) - when we don't want internal synchronization
  4244. // ---------------------------------------------------------------------------
  4245. template <>
  4246. class LockableImpl<phmap::NullMutex>: public phmap::NullMutex
  4247. {
  4248. public:
  4249. using mutex_type = phmap::NullMutex;
  4250. using Base = LockableBaseImpl<phmap::NullMutex>;
  4251. using SharedLock = typename Base::DoNothing;
  4252. using ReadWriteLock = typename Base::DoNothing;
  4253. using UniqueLock = typename Base::DoNothing;
  4254. using SharedLocks = typename Base::DoNothing;
  4255. using UniqueLocks = typename Base::DoNothing;
  4256. };
  4257. // --------------------------------------------------------------------------
  4258. // Abseil Mutex support (read and write lock support)
  4259. // use: `phmap::AbslMutex` instead of `std::mutex`
  4260. // --------------------------------------------------------------------------
  4261. #ifdef ABSL_SYNCHRONIZATION_MUTEX_H_
  4262. struct AbslMutex : protected absl::Mutex
  4263. {
  4264. void lock() ABSL_EXCLUSIVE_LOCK_FUNCTION() { this->Lock(); }
  4265. void unlock() ABSL_UNLOCK_FUNCTION() { this->Unlock(); }
  4266. void try_lock() ABSL_EXCLUSIVE_TRYLOCK_FUNCTION(true) { this->TryLock(); }
  4267. void lock_shared() ABSL_SHARED_LOCK_FUNCTION() { this->ReaderLock(); }
  4268. void unlock_shared() ABSL_UNLOCK_FUNCTION() { this->ReaderUnlock(); }
  4269. void try_lock_shared() ABSL_SHARED_TRYLOCK_FUNCTION(true) { this->ReaderTryLock(); }
  4270. };
  4271. template <>
  4272. class LockableImpl<absl::Mutex> : public AbslMutex
  4273. {
  4274. public:
  4275. using mutex_type = phmap::AbslMutex;
  4276. using Base = LockableBaseImpl<phmap::AbslMutex>;
  4277. using SharedLock = typename Base::ReadLock;
  4278. using ReadWriteLock = typename Base::ReadWriteLock;
  4279. using UniqueLock = typename Base::WriteLock;
  4280. using SharedLocks = typename Base::ReadLocks;
  4281. using UniqueLocks = typename Base::WriteLocks;
  4282. };
  4283. #endif
  4284. // --------------------------------------------------------------------------
  4285. // Microsoft SRWLOCK support (read and write lock support)
  4286. // use: `phmap::srwlock` instead of `std::mutex`
  4287. // --------------------------------------------------------------------------
  4288. #if defined(_MSC_VER) && defined(SRWLOCK_INIT) && 0 // Disabled (broken). HB
  4289. class srwlock {
  4290. SRWLOCK _lock;
  4291. public:
  4292. srwlock() { InitializeSRWLock(&_lock); }
  4293. void lock() { AcquireSRWLockExclusive(&_lock); }
  4294. void unlock() { ReleaseSRWLockExclusive(&_lock); }
  4295. bool try_lock() { return !!TryAcquireSRWLockExclusive(&_lock); }
  4296. void lock_shared() { AcquireSRWLockShared(&_lock); }
  4297. void unlock_shared() { ReleaseSRWLockShared(&_lock); }
  4298. bool try_lock_shared() { return !!TryAcquireSRWLockShared(&_lock); }
  4299. };
  4300. template<>
  4301. class LockableImpl<srwlock> : public srwlock
  4302. {
  4303. public:
  4304. using mutex_type = srwlock;
  4305. using Base = LockableBaseImpl<srwlock>;
  4306. using SharedLock = typename Base::ReadLock;
  4307. using ReadWriteLock = typename Base::ReadWriteLock;
  4308. using UniqueLock = typename Base::WriteLock;
  4309. using SharedLocks = typename Base::ReadLocks;
  4310. using UniqueLocks = typename Base::WriteLocks;
  4311. };
  4312. #endif
  4313. // --------------------------------------------------------------------------
  4314. // Boost shared_mutex support (read and write lock support)
  4315. // --------------------------------------------------------------------------
  4316. #if PHMAP_USE_BOOST_MUTEX && defined(BOOST_THREAD_SHARED_MUTEX_HPP)
  4317. // ---------------------------------------------------------------------------
  4318. template <>
  4319. class LockableImpl<boost::shared_mutex> : public boost::shared_mutex
  4320. {
  4321. public:
  4322. using mutex_type = boost::shared_mutex;
  4323. using Base = LockableBaseImpl<boost::shared_mutex>;
  4324. using SharedLock = boost::shared_lock<mutex_type>;
  4325. using ReadWriteLock = typename Base::ReadWriteLock;
  4326. using UniqueLock = boost::unique_lock<mutex_type>;
  4327. using SharedLocks = typename Base::ReadLocks;
  4328. using UniqueLocks = typename Base::WriteLocks;
  4329. };
  4330. #endif // PHMAP_USE_BOOST_MUTEX && defined(BOOST_THREAD_SHARED_MUTEX_HPP)
  4331. // --------------------------------------------------------------------------
  4332. // std::shared_mutex support (read and write lock support)
  4333. // --------------------------------------------------------------------------
  4334. #ifdef PHMAP_HAVE_SHARED_MUTEX
  4335. // ---------------------------------------------------------------------------
  4336. template <>
  4337. class LockableImpl<std::shared_mutex> : public std::shared_mutex
  4338. {
  4339. public:
  4340. using mutex_type = std::shared_mutex;
  4341. using Base = LockableBaseImpl<std::shared_mutex>;
  4342. using SharedLock = std::shared_lock<mutex_type>;
  4343. using ReadWriteLock = typename Base::ReadWriteLock;
  4344. using UniqueLock = std::unique_lock<mutex_type>;
  4345. using SharedLocks = typename Base::ReadLocks;
  4346. using UniqueLocks = typename Base::WriteLocks;
  4347. };
  4348. #endif // PHMAP_HAVE_SHARED_MUTEX
  4349. } // phmap
  4350. #ifdef _MSC_VER
  4351. #pragma warning(pop)
  4352. #endif
  4353. #endif // phmap_base_h_guard_