123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378 |
- #include <functional>
- #include "avl.hpp"
- #define KNRM "\x1B[0m"
- #define KRED "\x1B[31m"
- #define KGRN "\x1B[32m"
- #define KYEL "\x1B[33m"
- #define KBLU "\x1B[34m"
- #define KMAG "\x1B[35m"
- #define KCYN "\x1B[36m"
- #define KWHT "\x1B[37m"
- static void randomize_node(Node &a) {
- a.key.randomize(8);
- a.pointers.set(0);
- a.value.randomize();
- }
- void print_green(std::string line) {
- printf("%s%s%s", KGRN, line.c_str(), KNRM);
- }
- void print_red(std::string line) {
- printf("%s%s%s", KRED, line.c_str(), KNRM);
- }
- void AVL::pretty_print(const std::vector<Node> &R, value_t node,
- const std::string &prefix = "", bool is_left_child = false,
- bool is_right_child = false)
- {
- if (node == 0) {
-
- if (is_left_child) {
- printf("%s\xE2\x95\xA7\n", prefix.c_str());
- } else if (is_right_child) {
- printf("%s\xE2\x95\xA4\n", prefix.c_str());
- } else {
- printf("%s\xE2\x95\xA2\n", prefix.c_str());
- }
- return;
- }
- const Node &n = R[node];
- value_t left_ptr = getAVLLeftPtr(n.pointers).xshare;
- value_t right_ptr = getAVLRightPtr(n.pointers).xshare;
- std::string rightprefix(prefix), leftprefix(prefix),
- nodeprefix(prefix);
- if (is_left_child) {
- rightprefix.append("\xE2\x94\x82");
- leftprefix.append(" ");
- nodeprefix.append("\xE2\x94\x94");
- } else if (is_right_child) {
- rightprefix.append(" ");
- leftprefix.append("\xE2\x94\x82");
- nodeprefix.append("\xE2\x94\x8C");
- } else {
- rightprefix.append(" ");
- leftprefix.append(" ");
- nodeprefix.append("\xE2\x94\x80");
- }
- pretty_print(R, right_ptr, rightprefix, false, true);
- printf("%s\xE2\x94\xA4", nodeprefix.c_str());
- dumpAVL(n);
- printf("\n");
- pretty_print(R, left_ptr, leftprefix, true, false);
- }
- void AVL::print_oram(MPCTIO &tio, yield_t &yield) {
- auto A = oram.flat(tio, yield);
- auto R = A.reconstruct();
- for(size_t i=0;i<R.size();++i) {
- printf("\n%04lx ", i);
- R[i].dump();
- }
- printf("\n");
- }
- void AVL::pretty_print(MPCTIO &tio, yield_t &yield) {
- RegXS peer_root;
- RegXS reconstructed_root = root;
- if (tio.player() == 1) {
- tio.queue_peer(&root, sizeof(root));
- yield();
- } else {
- RegXS peer_root;
- yield();
- tio.recv_peer(&peer_root, sizeof(peer_root));
- reconstructed_root += peer_root;
- }
- auto A = oram.flat(tio, yield);
- auto R = A.reconstruct();
- if(tio.player()==0) {
- pretty_print(R, reconstructed_root.xshare);
- }
- }
- std::tuple<bool, bool, bool, address_t> AVL::check_avl(const std::vector<Node> &R,
- value_t node, value_t min_key = 0, value_t max_key = ~0)
- {
- if (node == 0) {
- return { true, true, true, 0};
- }
- const Node &n = R[node];
- value_t key = n.key.ashare;
- value_t left_ptr = getAVLLeftPtr(n.pointers).xshare;
- value_t right_ptr = getAVLRightPtr(n.pointers).xshare;
- auto [leftok, leftavlok, leftbbok, leftheight ] = check_avl(R, left_ptr, min_key, key);
- auto [rightok, rightavlok, rightbbok, rightheight ] = check_avl(R, right_ptr, key, max_key);
- address_t height = leftheight;
- if (rightheight > height) {
- height = rightheight;
- }
- height += 1;
- int heightgap = leftheight - rightheight;
- bool leftbal = (getLeftBal(n.pointers)).bshare;
- bool rightbal = (getRightBal(n.pointers)).bshare;
- bool avlok = (abs(heightgap)<2);
- bool bb_ok = false;
- if(heightgap==-1) {
- if(rightbal==1 && leftbal==0){
- bb_ok = true;
- }
- } else if(heightgap==1){
- if(leftbal==1 && rightbal==0){
- bb_ok = true;
- }
- } else if(heightgap==0){
- if(rightbal==0 && leftbal==0) {
- bb_ok = true;
- }
- }
- #ifdef AVL_DEBUG_BB
- if(bb_ok == false){
- printf("BB check failed at node with key = %ld\n", key);
- }
- #endif
-
- return { leftok && rightok && key >= min_key && key <= max_key,
- avlok && leftavlok && rightavlok, bb_ok && leftbbok && rightbbok, height};
- }
- bool AVL::check_avl(MPCTIO &tio, yield_t &yield) {
- auto A = oram.flat(tio, yield);
- auto R = A.reconstruct();
- RegXS rec_root = this->root;
- if (tio.player() == 1) {
- tio.queue_peer(&(this->root), sizeof(this->root));
- yield();
- } else {
- RegXS peer_root;
- yield();
- tio.recv_peer(&peer_root, sizeof(peer_root));
- rec_root+= peer_root;
- }
- if (tio.player() == 0) {
- auto [ bst_ok, avl_ok, bb_ok, height ] = check_avl(R, rec_root.xshare);
- printf("BST structure %s\nAVL structure %s\nBalance Bits %s\nTree height = %u\n",
- bst_ok ? "ok" : "NOT OK", avl_ok ? "ok" : "NOT OK", bb_ok? "ok" : "NOT OK", height);
- return (bst_ok && avl_ok && bb_ok);
- }
- else {
- return false;
- }
- }
- void AVL::rotate(MPCTIO &tio, yield_t &yield, RegXS &gp_pointers, RegXS p_ptr,
- RegXS &p_pointers, RegXS c_ptr, RegXS &c_pointers, RegBS dir_gpp,
- RegBS dir_pc, RegBS isReal, RegBS F_gp) {
- bool player0 = tio.player()==0;
- RegXS gp_left = getAVLLeftPtr(gp_pointers);
- RegXS gp_right = getAVLRightPtr(gp_pointers);
- RegXS p_left = getAVLLeftPtr(p_pointers);
- RegXS p_right = getAVLRightPtr(p_pointers);
- RegXS c_left = getAVLLeftPtr(c_pointers);
- RegXS c_right = getAVLRightPtr(c_pointers);
- RegXS ptr_upd;
-
-
-
- RegBS F_gpp, F_pc_l, F_pc_r, F_gppr, F_gppl;
-
-
-
- if(player0) {
- F_gp^=1;
- }
- mpc_and(tio, yield, F_gpp, F_gp, isReal);
-
- RegBS not_dir_gpp = dir_gpp;
- if(player0) {
- not_dir_gpp^=1;
- }
- mpc_select(tio, yield, ptr_upd, F_gpp, p_ptr, c_ptr);
- RegBS not_dir_pc_l = dir_pc, not_dir_pc_r = dir_pc;
- if(player0) {
- not_dir_pc_r^=1;
- }
- RegXS c_not_dir_pc;
-
-
- RegBS F_ndpc_right, F_ndpc_left;
- RegBS nt_dir_pc = dir_pc;
- if(player0) {
- nt_dir_pc^=1;
- }
- std::vector<coro_t> coroutines;
- coroutines.emplace_back(
- [&tio, &F_gppr, F_gpp, dir_gpp](yield_t &yield) {
- mpc_and(tio, yield, F_gppr, F_gpp, dir_gpp);
- });
- coroutines.emplace_back(
- [&tio, &F_gppl, F_gpp, not_dir_gpp](yield_t &yield) {
- mpc_and(tio, yield, F_gppl, F_gpp, not_dir_gpp);
- });
-
- coroutines.emplace_back(
- [&tio, &F_ndpc_right, isReal, not_dir_pc_r](yield_t &yield) {
- mpc_and(tio, yield, F_ndpc_right, isReal, not_dir_pc_r);
- });
- coroutines.emplace_back(
- [&tio, &F_ndpc_left, isReal, not_dir_pc_l](yield_t &yield) {
- mpc_and(tio, yield, F_ndpc_left, isReal, not_dir_pc_l);
- });
- coroutines.emplace_back(
- [&tio, &F_pc_l, dir_pc, isReal](yield_t &yield) {
- mpc_and(tio, yield, F_pc_l, dir_pc, isReal);
- });
- coroutines.emplace_back(
- [&tio, &F_pc_r, nt_dir_pc, isReal](yield_t &yield) {
- mpc_and(tio, yield, F_pc_r, nt_dir_pc, isReal);
- });
- run_coroutines(tio, coroutines);
- run_coroutines(tio, [&tio, &gp_right, F_gppr, ptr_upd](yield_t &yield)
- { mpc_select(tio, yield, gp_right, F_gppr, gp_right, ptr_upd);},
- [&tio, &gp_left, F_gppl, ptr_upd](yield_t &yield)
- { mpc_select(tio, yield, gp_left, F_gppl, gp_left, ptr_upd);},
- [&tio, &c_not_dir_pc, F_ndpc_right, c_right](yield_t &yield)
- { mpc_select(tio, yield, c_not_dir_pc, F_ndpc_right, c_not_dir_pc, c_right, AVL_PTR_SIZE);});
-
- mpc_select(tio, yield, c_not_dir_pc, F_ndpc_left, c_not_dir_pc, c_left, AVL_PTR_SIZE);
-
-
- run_coroutines(tio, [&tio, &p_left, F_ndpc_right, c_not_dir_pc](yield_t &yield)
- { mpc_select(tio, yield, p_left, F_ndpc_right, p_left, c_not_dir_pc, AVL_PTR_SIZE);},
- [&tio, &p_right, F_ndpc_left, c_not_dir_pc](yield_t &yield)
- { mpc_select(tio, yield, p_right, F_ndpc_left, p_right, c_not_dir_pc, AVL_PTR_SIZE);},
- [&tio, &ptr_upd, isReal, c_not_dir_pc, p_ptr](yield_t &yield)
- { mpc_select(tio, yield, ptr_upd, isReal, c_not_dir_pc, p_ptr, AVL_PTR_SIZE);});
- run_coroutines(tio, [&tio, &c_left, F_pc_l, ptr_upd](yield_t &yield)
- { mpc_select(tio, yield, c_left, F_pc_l, c_left, ptr_upd, AVL_PTR_SIZE);},
- [&tio, &c_right, F_pc_r, ptr_upd](yield_t &yield)
- { mpc_select(tio, yield, c_right, F_pc_r, c_right, ptr_upd, AVL_PTR_SIZE);});
- setAVLLeftPtr(gp_pointers, gp_left);
- setAVLRightPtr(gp_pointers, gp_right);
- setAVLLeftPtr(p_pointers, p_left);
- setAVLRightPtr(p_pointers, p_right);
- setAVLLeftPtr(c_pointers, c_left);
- setAVLRightPtr(c_pointers, c_right);
- }
- std::tuple<RegBS, RegBS, RegBS, RegBS> AVL::updateBalanceIns(MPCTIO &tio, yield_t &yield,
- RegBS bal_l, RegBS bal_r, RegBS bal_upd, RegBS child_dir) {
- bool player0 = tio.player()==0;
- RegBS s0;
- RegBS F_rs, F_ls, balanced, imbalance, nt_child_dir;
-
- balanced = bal_l ^ bal_r;
- nt_child_dir = child_dir;
- if(player0){
- nt_child_dir^=1;
- }
- if(player0) {
- balanced^=1;
- }
- run_coroutines(tio, [&tio, &F_rs, child_dir, bal_upd](yield_t &yield)
- {
- mpc_and(tio, yield, F_rs, child_dir, bal_upd);},
- [&tio, &F_ls, nt_child_dir, bal_upd](yield_t &yield)
- {
- mpc_and(tio, yield, F_ls, nt_child_dir, bal_upd);});
- std::vector<coro_t> coroutines;
-
- coroutines.emplace_back(
- [&tio, &imbalance, F_rs, bal_r, balanced](yield_t &yield) {
- mpc_select(tio, yield, imbalance, F_rs, imbalance, bal_r);
- });
- coroutines.emplace_back(
- [&tio, &bal_r, F_rs, balanced](yield_t &yield) {
- mpc_select(tio, yield, bal_r, F_rs, bal_r, balanced);
- });
- coroutines.emplace_back(
- [&tio, &balanced, F_rs, bal_l](yield_t &yield) {
- mpc_select(tio, yield, balanced, F_rs, balanced, bal_l);
- });
- coroutines.emplace_back(
- [&tio, &bal_l, F_rs, s0](yield_t &yield) {
- mpc_select(tio, yield, bal_l, F_rs, bal_l, s0);
- });
- run_coroutines(tio, coroutines);
- coroutines.clear();
-
- coroutines.emplace_back(
- [&tio, &imbalance, F_ls, bal_l] (yield_t &yield) {
- mpc_select(tio, yield, imbalance, F_ls, imbalance, bal_l);
- });
- coroutines.emplace_back(
- [&tio, &bal_l, F_ls, balanced] (yield_t &yield) {
- mpc_select(tio, yield, bal_l, F_ls, bal_l, balanced);
- });
- coroutines.emplace_back(
- [&tio, &balanced, F_ls, bal_r] (yield_t &yield) {
- mpc_select(tio, yield, balanced, F_ls, balanced, bal_r);
- });
- coroutines.emplace_back(
- [&tio, &bal_r, F_ls, s0](yield_t &yield) {
- mpc_select(tio, yield, bal_r, F_ls, bal_r, s0);
- });
- run_coroutines(tio, coroutines);
-
- RegBS F_bu0;
- mpc_and(tio, yield, F_bu0, bal_upd, balanced);
- mpc_select(tio, yield, bal_upd, F_bu0, bal_upd, s0);
- mpc_select(tio, yield, bal_upd, imbalance, bal_upd, s0);
- return {bal_l, bal_r, bal_upd, imbalance};
- }
- std::tuple<RegBS, RegBS, RegBS, RegBS> AVL::updateBalanceDel(MPCTIO &tio, yield_t &yield,
- RegBS bal_l, RegBS bal_r, RegBS bal_upd, RegBS child_dir) {
- bool player0 = tio.player()==0;
- RegBS s0;
- RegBS F_rs, F_ls, balanced, imbalance, not_imbalance;
- RegBS nt_child_dir = child_dir;
- if(player0) {
- nt_child_dir^=1;
- }
-
- balanced = bal_l ^ bal_r;
- if(player0) {
- balanced^=1;
- }
-
-
- run_coroutines(tio, [&tio, &F_ls, child_dir, bal_upd](yield_t &yield)
- { mpc_and(tio, yield, F_ls, child_dir, bal_upd);},
- [&tio, &F_rs, nt_child_dir, bal_upd](yield_t &yield)
- { mpc_and(tio, yield, F_rs, nt_child_dir, bal_upd);});
-
- run_coroutines(tio, [&tio, &imbalance, F_ls, bal_l](yield_t &yield)
- { mpc_select(tio, yield, imbalance, F_ls, imbalance, bal_l);},
- [&tio, &bal_l, F_ls, balanced](yield_t &yield)
- { mpc_select(tio, yield, bal_l, F_ls, bal_l, balanced);},
- [&tio, &balanced, F_ls, bal_r](yield_t &yield)
- { mpc_select(tio, yield, balanced, F_ls, balanced, bal_r);},
- [&tio, &bal_r, F_ls, s0](yield_t &yield)
- { mpc_select(tio, yield, bal_r, F_ls, bal_r, s0);});
-
- run_coroutines(tio, [&tio, &imbalance, F_rs, bal_r](yield_t &yield)
- { mpc_select(tio, yield, imbalance, F_rs, imbalance, bal_r);},
- [&tio, &bal_r, F_rs, balanced](yield_t &yield)
- { mpc_select(tio, yield, bal_r, F_rs, bal_r, balanced);},
- [&tio, &balanced, F_rs, bal_l](yield_t &yield)
- { mpc_select(tio, yield, balanced, F_rs, balanced, bal_l);},
- [&tio, &bal_l, F_rs, s0](yield_t &yield)
- { mpc_select(tio, yield, bal_l, F_rs, bal_l, s0);});
-
- RegBS LR_heavy, bu0;
- LR_heavy = bal_l ^ bal_r;
- mpc_and(tio, yield, bu0, bal_upd, LR_heavy);
- mpc_select(tio, yield, bal_upd, bu0, bal_upd, s0);
- return {bal_l, bal_r, bal_upd, imbalance};
- }
- std::tuple<RegBS, RegBS, RegXS, RegBS> AVL::insert(MPCTIO &tio, yield_t &yield, RegXS ptr, RegXS ins_addr,
- RegAS insert_key, Duoram<Node>::Flat &A, int TTL, RegBS isDummy, avl_insert_return &ret) {
- if(TTL==0) {
- RegBS z;
- return {z, z, z, z};
- }
- RegBS isReal = isDummy ^ (!tio.player());
- Node cnode;
- std::optional<Duoram<Node>::OblivIndex<RegXS, 1>> oidx;
- RegXS old_pointers;
- nbits_t width = ceil(log2(cur_max_index+1));
- if(OPTIMIZED) {
- oidx.emplace(tio, yield, ptr, width);
- cnode = A[oidx.value()];
- old_pointers = cnode.pointers;
- } else {
- cnode = A[ptr];
- }
-
- auto [lteq, gt] = compare_keys(tio, yield, cnode.key, insert_key);
-
- RegXS next_ptr;
- RegXS left = getAVLLeftPtr(cnode.pointers);
- RegXS right = getAVLRightPtr(cnode.pointers);
- RegBS bal_l = getLeftBal(cnode.pointers);
- RegBS bal_r = getRightBal(cnode.pointers);
-
- mpc_select(tio, yield, next_ptr, gt, left, right, AVL_PTR_SIZE);
-
- CDPF dpf = tio.cdpf(yield);
- size_t &aes_ops = tio.aes_ops();
-
- RegBS F_z = dpf.is_zero(tio, yield, next_ptr, aes_ops);
- RegBS F_i;
-
- mpc_and(tio, yield, F_i, (isReal), F_z);
- isDummy^=F_i;
- auto [bal_upd, F_gp, prev_node, prev_dir] = insert(tio, yield,
- next_ptr, ins_addr, insert_key, A, TTL-1, isDummy, ret);
-
-
-
- mpc_or(tio, yield, bal_upd, bal_upd, F_i);
- auto [new_bal_l, new_bal_r, new_bal_upd, imbalance] = updateBalanceIns(tio, yield, bal_l, bal_r, bal_upd, gt);
-
- ret.imbalance ^= imbalance;
- std::vector<coro_t> coroutines;
-
- coroutines.emplace_back(
- [&tio, &ret, F_gp, ptr](yield_t &yield) {
- mpc_select(tio, yield, ret.gp_node, F_gp, ret.gp_node, ptr, AVL_PTR_SIZE);
- });
- coroutines.emplace_back(
- [&tio, &ret, F_gp, gt](yield_t &yield) {
- mpc_select(tio, yield, ret.dir_gpp, F_gp, ret.dir_gpp, gt);
- });
-
- coroutines.emplace_back(
- [&tio, &ret, imbalance, ptr](yield_t &yield) {
- mpc_select(tio, yield, ret.p_node, imbalance, ret.p_node, ptr, AVL_PTR_SIZE);
- });
- coroutines.emplace_back(
- [&tio, &ret, imbalance, gt](yield_t &yield) {
- mpc_select(tio, yield, ret.dir_pc, imbalance, ret.dir_pc, gt);
- });
-
- coroutines.emplace_back(
- [&tio, &ret, imbalance, prev_node](yield_t &yield) {
- mpc_select(tio, yield, ret.c_node, imbalance, ret.c_node, prev_node, AVL_PTR_SIZE);
- });
- coroutines.emplace_back(
- [&tio, &ret, imbalance, prev_dir](yield_t &yield) {
- mpc_select(tio, yield, ret.dir_cn, imbalance, ret.dir_cn, prev_dir);
- });
- run_coroutines(tio, coroutines);
-
- setLeftBal(cnode.pointers, new_bal_l);
- setRightBal(cnode.pointers, new_bal_r);
-
-
- RegBS F_ir, F_il;
- run_coroutines(tio, [&tio, &F_ir, F_i, gt](yield_t &yield)
- { mpc_and(tio, yield, F_ir, F_i, gt); },
- [&tio, &F_il, F_i, lteq](yield_t &yield)
- { mpc_and(tio, yield, F_il, F_i, lteq); });
- run_coroutines(tio, [&tio, &left, F_il, ins_addr](yield_t &yield)
- { mpc_select(tio, yield, left, F_il, left, ins_addr);},
- [&tio, &right, F_ir, ins_addr](yield_t &yield)
- { mpc_select(tio, yield, right, F_ir, right, ins_addr);});
- setAVLLeftPtr(cnode.pointers, left);
- setAVLRightPtr(cnode.pointers, right);
-
- if(OPTIMIZED) {
- A[oidx.value()].NODE_POINTERS+=(cnode.pointers - old_pointers);
- } else {
- A[ptr].NODE_POINTERS = cnode.pointers;
- }
-
- RegBS s0;
-
-
- return {new_bal_upd, imbalance, ptr, gt};
- }
- void AVL::insert(MPCTIO &tio, yield_t &yield, const Node &node) {
- bool player0 = tio.player()==0;
-
- if(num_items==0) {
- auto A = oram.flat(tio, yield);
- Node zero;
- A[0] = zero;
- A[1] = node;
-
- root.set(1*tio.player());
- num_items++;
- cur_max_index++;
- return;
- } else {
-
- int new_id;
- RegXS insert_address;
- num_items++;
- int TTL = AVL_TTL(num_items);
- bool insertAtEmptyLocation = (empty_locations.size() > 0);
- if(!insertAtEmptyLocation) {
- cur_max_index++;
- }
- auto A = oram.flat(tio, yield, 0, cur_max_index+1);
- if(insertAtEmptyLocation) {
- insert_address = empty_locations.back();
- empty_locations.pop_back();
- A[insert_address] = node;
- } else {
- new_id = num_items;
- A[new_id] = node;
- insert_address.set(new_id * tio.player());
- }
- RegBS isDummy;
- avl_insert_return ret;
- RegAS insert_key = node.key;
-
- auto [bal_upd, F_gp, prev_node, prev_dir] = insert(tio, yield, root,
- insert_address, insert_key, A, TTL, isDummy, ret);
-
-
- RegXS gp_pointers, parent_pointers, child_pointers;
- std::vector<coro_t> coroutines;
- std::optional<Duoram<Node>::template OblivIndex<RegXS, 1>> oidx_gp;
- std::optional<Duoram<Node>::template OblivIndex<RegXS, 1>> oidx_p;
- std::optional<Duoram<Node>::template OblivIndex<RegXS, 1>> oidx_c;
- nbits_t width = ceil(log2(cur_max_index+1));
- if(OPTIMIZED) {
- oidx_gp.emplace(tio, yield, ret.gp_node, width);
- oidx_p.emplace(tio, yield, ret.p_node, width);
- oidx_c.emplace(tio, yield, ret.c_node, width);
- coroutines.emplace_back(
- [&tio, &A, &oidx_gp, &gp_pointers](yield_t &yield) {
- auto acont = A.context(yield);
- gp_pointers = acont[oidx_gp.value()].NODE_POINTERS;});
- coroutines.emplace_back(
- [&tio, &A, &oidx_p, &parent_pointers](yield_t &yield) {
- auto acont = A.context(yield);
- parent_pointers = acont[oidx_p.value()].NODE_POINTERS;});
- coroutines.emplace_back(
- [&tio, &A, &oidx_c, &child_pointers](yield_t &yield) {
- auto acont = A.context(yield);
- child_pointers = acont[oidx_c.value()].NODE_POINTERS;});
- run_coroutines(tio, coroutines);
- coroutines.clear();
-
-
- } else {
- gp_pointers = A[ret.gp_node].NODE_POINTERS;
- parent_pointers = A[ret.p_node].NODE_POINTERS;
- child_pointers = A[ret.c_node].NODE_POINTERS;
- }
-
- RegXS child_left = getAVLLeftPtr(child_pointers);
- RegXS child_right = getAVLRightPtr(child_pointers);
- RegXS n_node, n_pointers;
- mpc_select(tio, yield, n_node, ret.dir_cn, child_left, child_right, AVL_PTR_SIZE);
- std::optional <Duoram<Node>::template OblivIndex<RegXS,1>> oidx_n;
- if(OPTIMIZED) {
- oidx_n.emplace(tio, yield, n_node, width);
- n_pointers = A[oidx_n.value()].NODE_POINTERS;
- } else {
- n_pointers = A[n_node].NODE_POINTERS;
- }
- RegXS old_gp_pointers, old_parent_pointers, old_child_pointers, old_n_pointers;
- if(OPTIMIZED) {
- old_gp_pointers = gp_pointers;
- old_parent_pointers = parent_pointers;
- old_child_pointers = child_pointers;
- old_n_pointers = n_pointers;
- }
-
-
- RegBS F_dr = (ret.dir_pc) ^ (ret.dir_cn);
-
- RegBS F_cn_rot, F_ur, s0;
- run_coroutines(tio, [&tio, &F_ur, F_gp, ret](yield_t &yield)
- {mpc_and(tio, yield, F_ur, F_gp, ret.imbalance);},
- [&tio, &F_cn_rot, ret, F_dr](yield_t &yield)
- {mpc_and(tio, yield, F_cn_rot, ret.imbalance, F_dr);});
-
- RegBS n_bal_l, n_bal_r;
- RegXS n_l = getAVLLeftPtr(n_pointers);
- RegXS n_r = getAVLRightPtr(n_pointers);
- n_bal_l = getLeftBal(n_pointers);
- n_bal_r = getRightBal(n_pointers);
-
- rotate(tio, yield, parent_pointers, ret.c_node, child_pointers, n_node,
- n_pointers, ret.dir_pc, ret.dir_cn, F_cn_rot, s0);
-
- RegXS new_child_pointers, new_child;
- run_coroutines(tio, [&tio, &new_child_pointers, F_cn_rot, child_pointers, n_pointers] (yield_t &yield)
- {mpc_select(tio, yield, new_child_pointers, F_cn_rot, child_pointers, n_pointers);},
- [&tio, &new_child, F_cn_rot, ret, n_node](yield_t &yield)
- {mpc_select(tio, yield, new_child, F_cn_rot, ret.c_node, n_node, AVL_PTR_SIZE);});
-
- rotate(tio, yield, gp_pointers, ret.p_node, parent_pointers, new_child,
- new_child_pointers, ret.dir_gpp, ret.dir_pc, ret.imbalance, F_gp);
-
-
- RegBS temp_bal, p_bal_l, p_bal_r, p_bal_ndpc;
- RegBS c_bal_l, c_bal_r, c_bal_dpc, n_bal_dpc, n_bal_ndpc;
- p_bal_l = getLeftBal(parent_pointers);
- p_bal_r = getRightBal(parent_pointers);
- run_coroutines(tio, [&tio, &child_pointers, F_cn_rot, new_child_pointers] (yield_t &yield)
- {mpc_select(tio, yield, child_pointers, F_cn_rot, new_child_pointers, child_pointers);},
- [&tio, &n_pointers, F_cn_rot, new_child_pointers] (yield_t &yield)
- {mpc_select(tio, yield, n_pointers, F_cn_rot, n_pointers, new_child_pointers);});
- c_bal_l = getLeftBal(child_pointers);
- c_bal_r = getRightBal(child_pointers);
- run_coroutines(tio, [&tio, &c_bal_l, ret, s0] (yield_t &yield)
- {mpc_select(tio, yield, c_bal_l, ret.imbalance, c_bal_l, s0);},
- [&tio, &c_bal_r, ret, s0] (yield_t &yield)
- {mpc_select(tio, yield, c_bal_r, ret.imbalance, c_bal_r, s0);});
-
- size_t &aes_ops = tio.aes_ops();
- RegBS n_l0, n_r0;
- run_coroutines(tio, [&tio, &n_l0, n_l, &aes_ops] (yield_t &yield)
- { CDPF cdpf = tio.cdpf(yield);
- n_l0 = cdpf.is_zero(tio, yield, n_l, aes_ops);},
- [&tio, &n_r0, n_r, &aes_ops] (yield_t &yield)
- { CDPF cdpf = tio.cdpf(yield);
- n_r0 = cdpf.is_zero(tio, yield, n_r, aes_ops);});
- RegBS p_c_update, n_has_children;
-
- mpc_and(tio, yield, n_has_children, n_l0, n_r0);
- if(player0) {
- n_has_children^=1;
- }
- run_coroutines(tio, [&tio, &p_c_update, F_cn_rot, n_has_children] (yield_t &yield)
- {mpc_and(tio, yield, p_c_update, F_cn_rot, n_has_children);},
- [&tio, &n_bal_ndpc, ret, n_bal_l, n_bal_r] (yield_t &yield)
- {mpc_select(tio, yield, n_bal_ndpc, ret.dir_pc, n_bal_r, n_bal_l);},
- [&tio, &n_bal_dpc, ret, n_bal_l, n_bal_r] (yield_t &yield)
- {mpc_select(tio, yield, n_bal_dpc, ret.dir_pc, n_bal_l, n_bal_r);},
- [&tio, &p_bal_ndpc, ret, p_bal_r, p_bal_l] (yield_t &yield)
- {mpc_select(tio, yield, p_bal_ndpc, ret.dir_pc, p_bal_r, p_bal_l);});
-
- if(player0) {
- n_bal_ndpc^=1;
- n_bal_dpc^=1;
- }
- run_coroutines(tio, [&tio, &p_bal_ndpc, p_c_update, n_bal_ndpc] (yield_t &yield)
- {mpc_select(tio, yield, p_bal_ndpc, p_c_update, p_bal_ndpc, n_bal_ndpc);},
- [&tio, &c_bal_dpc, p_c_update, n_bal_dpc] (yield_t &yield)
- {mpc_select(tio, yield, c_bal_dpc, p_c_update, c_bal_dpc, n_bal_dpc);});
- coroutines.emplace_back([&tio, &p_bal_r, ret, p_bal_ndpc] (yield_t &yield)
- {mpc_select(tio, yield, p_bal_r, ret.dir_pc, p_bal_ndpc, p_bal_r);});
- coroutines.emplace_back([&tio, &p_bal_l, ret, p_bal_ndpc] (yield_t &yield)
- {mpc_select(tio, yield, p_bal_l, ret.dir_pc, p_bal_l, p_bal_ndpc);});
- coroutines.emplace_back([&tio, &c_bal_r, ret, c_bal_dpc] (yield_t &yield)
- {mpc_select(tio, yield, c_bal_r, ret.dir_pc, c_bal_r, c_bal_dpc);});
- coroutines.emplace_back([&tio, &c_bal_l, ret, c_bal_dpc] (yield_t &yield)
- {mpc_select(tio, yield, c_bal_l, ret.dir_pc, c_bal_dpc, c_bal_l);});
-
-
- coroutines.emplace_back([&tio, &n_bal_l, F_cn_rot, s0] (yield_t &yield)
- {mpc_select(tio, yield, n_bal_l, F_cn_rot, n_bal_l, s0);});
- coroutines.emplace_back([&tio, &n_bal_r, F_cn_rot, s0] (yield_t &yield)
- {mpc_select(tio, yield, n_bal_r, F_cn_rot, n_bal_r, s0);});
- run_coroutines(tio, coroutines);
- setLeftBal(parent_pointers, p_bal_l);
- setRightBal(parent_pointers, p_bal_r);
- setLeftBal(child_pointers, c_bal_l);
- setRightBal(child_pointers, c_bal_r);
- setLeftBal(n_pointers, n_bal_l);
- setRightBal(n_pointers, n_bal_r);
-
- if(OPTIMIZED) {
- run_coroutines(tio,
- [&tio, &A, &oidx_n, n_pointers, old_n_pointers]
- (yield_t &yield) {
- auto Acont = A.context(yield);
- Acont[oidx_n.value()].NODE_POINTERS+=(n_pointers - old_n_pointers);
- },
- [&tio, &A, &oidx_c, child_pointers, old_child_pointers]
- (yield_t &yield) {
- auto Acont = A.context(yield);
- Acont[oidx_c.value()].NODE_POINTERS+=(child_pointers - old_child_pointers);
- },
- [&tio, &A, &oidx_p, parent_pointers, old_parent_pointers]
- (yield_t &yield) {
- auto Acont = A.context(yield);
- Acont[oidx_p.value()].NODE_POINTERS+=(parent_pointers - old_parent_pointers);
- },
- [&tio, &A, &oidx_gp, gp_pointers, old_gp_pointers]
- (yield_t &yield) {
- auto Acont = A.context(yield);
- Acont[oidx_gp.value()].NODE_POINTERS+=(gp_pointers - old_gp_pointers);
- });
- } else {
- A[ret.c_node].NODE_POINTERS = child_pointers;
- A[ret.p_node].NODE_POINTERS = parent_pointers;
- A[ret.gp_node].NODE_POINTERS = gp_pointers;
- A[n_node].NODE_POINTERS = n_pointers;
- }
-
-
-
- RegXS temp_root = root;
- run_coroutines(tio, [&tio, &temp_root, F_ur, ret] (yield_t &yield)
- {mpc_select(tio, yield, temp_root, F_ur, temp_root, ret.c_node, AVL_PTR_SIZE);},
- [&tio, &F_ur, F_gp, F_dr] (yield_t &yield)
- {mpc_and(tio, yield, F_ur, F_gp, F_dr);});
- mpc_select(tio, yield, temp_root, F_ur, temp_root, n_node, AVL_PTR_SIZE);
- root = temp_root;
- }
- }
- bool AVL::lookup(MPCTIO &tio, yield_t &yield, RegXS ptr, RegAS key, Duoram<Node>::Flat &A,
- int TTL, RegBS isDummy, Node *ret_node) {
- if(TTL==0) {
-
-
- bool found = reconstruct_RegBS(tio, yield, isDummy);
- return found;
- }
- RegBS isNotDummy = isDummy ^ (!tio.player());
- Node cnode = A[ptr];
-
- CDPF cdpf = tio.cdpf(yield);
- auto [lt, eq, gt] = cdpf.compare(tio, yield, key - cnode.key, tio.aes_ops());
-
-
-
-
- RegXS left = getAVLLeftPtr(cnode.pointers);
- RegXS right = getAVLRightPtr(cnode.pointers);
- RegXS next_ptr;
- mpc_select(tio, yield, next_ptr, gt, left, right, 32);
- RegBS F_found;
-
-
-
-
-
-
- run_coroutines(tio,
- [&tio, &F_found, isNotDummy, eq](yield_t &yield)
- { mpc_and(tio, yield, F_found, isNotDummy, eq);},
- [&tio, &ret_node, F_found, &cnode](yield_t &yield)
- { mpc_select(tio, yield, ret_node->key, F_found, ret_node->key, cnode.key);},
- [&tio, &ret_node, F_found, &cnode](yield_t &yield)
- { mpc_select(tio, yield, ret_node->value, F_found, ret_node->value, cnode.value);});
- isDummy^=F_found;
- bool found = lookup(tio, yield, next_ptr, key, A, TTL-1, isDummy, ret_node);
- return found;
- }
- bool AVL::lookup(MPCTIO &tio, yield_t &yield, RegAS key, Node *ret_node) {
- auto A = oram.flat(tio, yield);
- RegBS isDummy;
- bool found = lookup(tio, yield, root, key, A, num_items, isDummy, ret_node);
- return found;
- }
- void AVL::updateChildPointers(MPCTIO &tio, yield_t &yield, RegXS &left, RegXS &right,
- RegBS c_prime, const avl_del_return &ret_struct) {
- bool player0 = tio.player()==0;
- RegBS F_rr;
- RegBS F_rl;
- RegBS nt_c_prime = c_prime;
- if(player0) {
- nt_c_prime^=1;
- }
- run_coroutines(tio, [&tio, &F_rr, c_prime, ret_struct](yield_t &yield)
- { mpc_and(tio, yield, F_rr, c_prime, ret_struct.F_r);},
- [&tio, &F_rl, nt_c_prime, ret_struct](yield_t &yield)
- { mpc_and(tio, yield, F_rl, nt_c_prime, ret_struct.F_r);});
- run_coroutines(tio, [&tio, &right, F_rr, ret_struct](yield_t &yield)
- { mpc_select(tio, yield, right, F_rr, right, ret_struct.ret_ptr);},
- [&tio, &left, F_rl, ret_struct](yield_t &yield)
- { mpc_select(tio, yield, left, F_rl, left, ret_struct.ret_ptr);});
- }
- void AVL::fixImbalance(MPCTIO &tio, yield_t &yield, Duoram<Node>::Flat &A,
- Duoram<Node>::OblivIndex<RegXS, 1> oidx, RegXS oidx_oldptrs, RegXS ptr,
- RegXS nodeptrs, RegBS new_p_bal_l, RegBS new_p_bal_r, RegBS &bal_upd,
- RegBS c_prime, RegXS cs_ptr, RegBS imb, RegBS &F_ri,
- avl_del_return &ret_struct) {
- bool player0 = tio.player()==0;
- RegBS s0, s1;
- s1.set(tio.player()==1);
- Node cs_node, gcs_node;
- std::optional<Duoram<Node>::OblivIndex<RegXS,1>> oidx_cs;
- RegXS old_cs_ptr, old_gcs_ptr;
- nbits_t width = ceil(log2(cur_max_index+1));
- if(OPTIMIZED) {
- oidx_cs.emplace(tio, yield, cs_ptr, width);
- cs_node = A[oidx_cs.value()];
- old_cs_ptr = cs_node.pointers;
- } else {
- cs_node = A[cs_ptr];
- }
-
- RegBS cs_bal_l, cs_bal_r, cs_bal_dpc, cs_bal_ndpc, p_bal_ndpc, p_bal_dpc;
- RegBS F_dr, not_c_prime;
- RegXS gcs_ptr, cs_left, cs_right, cs_dpc, cs_ndpc, null;
- not_c_prime = c_prime;
- if(player0) {
- not_c_prime^=1;
- }
-
- cs_bal_l = getLeftBal(cs_node.pointers);
- cs_bal_r = getRightBal(cs_node.pointers);
- cs_left = getAVLLeftPtr(cs_node.pointers);
- cs_right = getAVLRightPtr(cs_node.pointers);
- std::vector<coro_t> coroutines;
- RegBS gcs_balanced, gcs_bal_dpc, gcs_bal_ndpc;
- RegBS ndpc_is_l, ndpc_is_r, dpc_is_l, dpc_is_r;
-
-
-
-
- coroutines.emplace_back([&tio, &ndpc_is_l, c_prime, imb] (yield_t &yield)
- { mpc_and(tio, yield, ndpc_is_l, imb, c_prime);});
- coroutines.emplace_back([&tio, &ndpc_is_r, imb, not_c_prime](yield_t &yield)
- { mpc_and(tio, yield, ndpc_is_r, imb, not_c_prime);});
- coroutines.emplace_back([&tio, &dpc_is_l, imb, not_c_prime](yield_t &yield)
- { mpc_and(tio, yield, dpc_is_l, imb, not_c_prime);});
- coroutines.emplace_back([&tio, &dpc_is_r, imb, c_prime](yield_t &yield)
- { mpc_and(tio, yield, dpc_is_r, imb, c_prime);});
- run_coroutines(tio, coroutines);
- coroutines.clear();
- coroutines.emplace_back(
- [&tio, &cs_bal_dpc, dpc_is_r, cs_bal_l, cs_bal_r] (yield_t &yield)
- { mpc_select(tio, yield, cs_bal_dpc, dpc_is_r, cs_bal_l, cs_bal_r);});
- coroutines.emplace_back(
- [&tio, &cs_bal_ndpc, ndpc_is_l, cs_bal_r, cs_bal_l](yield_t &yield)
- { mpc_select(tio, yield, cs_bal_ndpc, ndpc_is_l, cs_bal_r, cs_bal_l);});
- coroutines.emplace_back(
- [&tio, &cs_dpc, dpc_is_r, cs_left, cs_right](yield_t &yield)
- { mpc_select(tio, yield, cs_dpc, dpc_is_r, cs_left, cs_right);});
- coroutines.emplace_back(
- [&tio, &cs_ndpc, ndpc_is_l, cs_right, cs_left](yield_t &yield)
- { mpc_select(tio, yield, cs_ndpc, ndpc_is_l, cs_right, cs_left);});
- coroutines.emplace_back(
- [&tio, &p_bal_ndpc, ndpc_is_r, new_p_bal_l, new_p_bal_r](yield_t &yield)
- { mpc_select(tio, yield, p_bal_ndpc, ndpc_is_r, new_p_bal_l, new_p_bal_r);});
- coroutines.emplace_back(
- [&tio, &p_bal_dpc, dpc_is_r, new_p_bal_l, new_p_bal_r] (yield_t &yield)
- { mpc_select(tio, yield, p_bal_dpc, dpc_is_r, new_p_bal_l, new_p_bal_r);});
- run_coroutines(tio, coroutines);
- coroutines.clear();
-
- run_coroutines(tio, [&tio, &F_dr, imb, cs_bal_dpc] (yield_t &yield)
- { mpc_and(tio, yield, F_dr, imb, cs_bal_dpc);},
- [&tio, &gcs_ptr, cs_bal_dpc, cs_ndpc, cs_dpc](yield_t &yield)
- { mpc_select(tio, yield, gcs_ptr, cs_bal_dpc, cs_ndpc, cs_dpc, AVL_PTR_SIZE);});
- std::optional<Duoram<Node>::template OblivIndex<RegXS,1>> oidx_gcs;
- if(OPTIMIZED) {
- oidx_gcs.emplace(tio, yield, gcs_ptr, width);
- gcs_node = A[oidx_gcs.value()];
- old_gcs_ptr = gcs_node.pointers;
- } else {
- gcs_node = A[gcs_ptr];
- }
- RegBS gcs_bal_l = getLeftBal(gcs_node.pointers);
- RegBS gcs_bal_r = getRightBal(gcs_node.pointers);
- run_coroutines(tio, [&tio, &gcs_bal_dpc, dpc_is_r, gcs_bal_l, gcs_bal_r](yield_t &yield)
- { mpc_select(tio, yield, gcs_bal_dpc, dpc_is_r, gcs_bal_l, gcs_bal_r);},
- [&tio, &gcs_bal_ndpc, ndpc_is_r, gcs_bal_l, gcs_bal_r](yield_t &yield)
- { mpc_select(tio, yield, gcs_bal_ndpc, ndpc_is_r, gcs_bal_l, gcs_bal_r);});
-
- rotate(tio, yield, nodeptrs, cs_ptr, cs_node.pointers, gcs_ptr,
- gcs_node.pointers, not_c_prime, c_prime, F_dr, s0);
-
- RegXS new_cs_pointers, new_cs, new_ptr;
- run_coroutines(tio, [&tio, &new_cs_pointers, F_dr, cs_node, gcs_node](yield_t &yield)
- { mpc_select(tio, yield, new_cs_pointers, F_dr, cs_node.pointers, gcs_node.pointers);},
- [&tio, &new_cs, F_dr, cs_ptr, gcs_ptr](yield_t &yield)
- { mpc_select(tio, yield, new_cs, F_dr, cs_ptr, gcs_ptr, AVL_PTR_SIZE);},
- [&tio, &new_ptr, F_dr, cs_ptr, gcs_ptr](yield_t &yield)
- { mpc_select(tio, yield, new_ptr, F_dr, cs_ptr, gcs_ptr);});
-
-
-
-
- rotate(tio, yield, null, ptr, nodeptrs, new_cs,
- new_cs_pointers, s0, not_c_prime, imb, s1);
-
-
-
- F_ri = imb;
- coroutines.emplace_back([&tio, &ret_struct, imb, new_ptr](yield_t &yield) {
- mpc_select(tio, yield, ret_struct.ret_ptr, imb, ret_struct.ret_ptr, new_ptr);
- });
-
-
- coroutines.emplace_back([&tio, &cs_node, F_dr, new_cs_pointers](yield_t &yield) {
- mpc_select(tio, yield, cs_node.pointers, F_dr, new_cs_pointers, cs_node.pointers);
- });
- coroutines.emplace_back([&tio, &gcs_node, F_dr, new_cs_pointers](yield_t &yield) {
- mpc_select(tio, yield, gcs_node.pointers, F_dr, gcs_node.pointers, new_cs_pointers);
- });
- run_coroutines(tio, coroutines);
- coroutines.clear();
-
- RegBS IC1, IC2, IC3;
- RegBS cs_zero_bal = cs_bal_dpc ^ cs_bal_ndpc;
- if(player0) {
- cs_zero_bal^=1;
- }
- run_coroutines(tio, [&tio, &IC1, imb, cs_bal_ndpc] (yield_t &yield) {
-
- mpc_and(tio, yield, IC1, imb, cs_bal_ndpc);
- },
-
- [&tio, &IC2, imb, cs_zero_bal](yield_t &yield) {
- mpc_and(tio, yield, IC2, imb, cs_zero_bal);
- },
- [&tio, &IC3, imb, cs_bal_dpc](yield_t &yield) {
-
- mpc_and(tio, yield, IC3, imb, cs_bal_dpc);
- });
-
- RegBS IC3_S1, IC3_S2, IC3_S3;
- gcs_balanced = gcs_bal_dpc ^ gcs_bal_ndpc;
- if(player0) {
- gcs_balanced^=1;
- }
-
-
- coroutines.emplace_back([&tio, &cs_bal_ndpc, IC1, s0](yield_t &yield)
- { mpc_select(tio, yield, cs_bal_ndpc, IC1, cs_bal_ndpc, s0);});
- coroutines.emplace_back([&tio, &cs_bal_dpc, IC2, s1](yield_t &yield)
- { mpc_select(tio, yield, cs_bal_dpc, IC2, cs_bal_dpc, s1);});
- coroutines.emplace_back([&tio, &p_bal_ndpc, IC2, s1](yield_t &yield)
- { mpc_select(tio, yield, p_bal_ndpc, IC2, p_bal_ndpc, s1);});
- coroutines.emplace_back([&tio, &IC3_S1, IC3, gcs_bal_ndpc](yield_t &yield)
- { mpc_and(tio, yield, IC3_S1, IC3, gcs_bal_ndpc);});
- coroutines.emplace_back([&tio, &IC3_S2, IC3, gcs_bal_dpc](yield_t &yield)
- { mpc_and(tio, yield, IC3_S2, IC3, gcs_bal_dpc);});
- coroutines.emplace_back([&tio, &IC3_S3, IC3, gcs_balanced](yield_t &yield)
- { mpc_and(tio, yield, IC3_S3, IC3, gcs_balanced);});
-
-
- coroutines.emplace_back([&tio, &bal_upd, IC2, s0](yield_t &yield)
- { mpc_select(tio, yield, bal_upd, IC2, bal_upd, s0);});
- run_coroutines(tio, coroutines);
- coroutines.clear();
-
- coroutines.emplace_back([&tio, &cs_bal_dpc, IC3, s0](yield_t &yield)
- { mpc_select(tio, yield, cs_bal_dpc, IC3, cs_bal_dpc, s0);});
- coroutines.emplace_back([&tio, &p_bal_dpc, IC3_S1, s1](yield_t &yield)
- { mpc_select(tio, yield, p_bal_dpc, IC3_S1, p_bal_dpc, s1);});
- coroutines.emplace_back([&tio, &cs_bal_ndpc, IC3_S2, s1](yield_t &yield)
- { mpc_select(tio, yield, cs_bal_ndpc, IC3_S2, cs_bal_ndpc, s1);});
- coroutines.emplace_back([&tio, &gcs_bal_dpc, IC3_S2, s0](yield_t &yield)
- { mpc_select(tio, yield, gcs_bal_dpc, IC3_S2, gcs_bal_dpc, s0);});
- run_coroutines(tio, coroutines);
- coroutines.clear();
-
-
- coroutines.emplace_back([&tio, &gcs_bal_r, dpc_is_r, gcs_bal_dpc](yield_t &yield)
- { mpc_select(tio, yield, gcs_bal_r, dpc_is_r, gcs_bal_r, gcs_bal_dpc);});
- coroutines.emplace_back([&tio, &gcs_bal_l, dpc_is_l, gcs_bal_dpc](yield_t &yield)
- { mpc_select(tio, yield, gcs_bal_l, dpc_is_l, gcs_bal_l, gcs_bal_dpc);});
-
- coroutines.emplace_back([&tio, &cs_bal_r, dpc_is_r, cs_bal_dpc](yield_t &yield)
- { mpc_select(tio, yield, cs_bal_r, dpc_is_r, cs_bal_r, cs_bal_dpc);});
- coroutines.emplace_back([&tio, &cs_bal_l, dpc_is_l, cs_bal_dpc](yield_t &yield)
- { mpc_select(tio, yield, cs_bal_l, dpc_is_l, cs_bal_l, cs_bal_dpc);});
-
- coroutines.emplace_back([&tio, &new_p_bal_r, ndpc_is_r, p_bal_ndpc] (yield_t &yield)
- { mpc_select(tio, yield, new_p_bal_r, ndpc_is_r, new_p_bal_r, p_bal_ndpc);});
- coroutines.emplace_back([&tio, &new_p_bal_l, ndpc_is_l, p_bal_ndpc](yield_t &yield)
- { mpc_select(tio, yield, new_p_bal_l, ndpc_is_l, new_p_bal_l, p_bal_ndpc);});
- run_coroutines(tio, coroutines);
- coroutines.clear();
-
- coroutines.emplace_back([&tio, &cs_bal_r, ndpc_is_r, cs_bal_ndpc] (yield_t &yield)
- { mpc_select(tio, yield, cs_bal_r, ndpc_is_r, cs_bal_r, cs_bal_ndpc);});
- coroutines.emplace_back([&tio, &cs_bal_l, ndpc_is_l, cs_bal_ndpc](yield_t &yield)
- { mpc_select(tio, yield, cs_bal_l, ndpc_is_l, cs_bal_l, cs_bal_ndpc);});
- run_coroutines(tio, coroutines);
- coroutines.clear();
-
- setLeftBal(gcs_node.pointers, gcs_bal_l);
- setRightBal(gcs_node.pointers, gcs_bal_r);
- setLeftBal(cs_node.pointers, cs_bal_l);
- setRightBal(cs_node.pointers, cs_bal_r);
- setLeftBal(nodeptrs, new_p_bal_l);
- setRightBal(nodeptrs, new_p_bal_r);
-
- if(OPTIMIZED) {
- coroutines.emplace_back(
- [&tio, &A, &oidx_cs, &cs_node, old_cs_ptr] (yield_t &yield) {
- auto acont = A.context(yield);
- (acont[oidx_cs.value()].NODE_POINTERS)+= (cs_node.pointers - old_cs_ptr);});
- coroutines.emplace_back(
- [&tio, &A, &oidx_gcs, &gcs_node, old_gcs_ptr] (yield_t &yield) {
- auto acont = A.context(yield);
- (acont[oidx_gcs.value()].NODE_POINTERS)+= (gcs_node.pointers - old_gcs_ptr);});
- coroutines.emplace_back(
- [&tio, &A, &oidx, nodeptrs, oidx_oldptrs] (yield_t &yield) {
- auto acont = A.context(yield);
- (acont[oidx].NODE_POINTERS)+=(nodeptrs - oidx_oldptrs);});
- run_coroutines(tio, coroutines);
- coroutines.clear();
- } else {
- A[cs_ptr].NODE_POINTERS = cs_node.pointers;
- A[gcs_ptr].NODE_POINTERS = gcs_node.pointers;
- A[ptr].NODE_POINTERS = nodeptrs;
- }
- }
- void AVL::updateRetStruct(MPCTIO &tio, yield_t &yield, RegXS ptr, RegBS F_rs, RegBS F_dh,
- RegBS F_ri, RegBS &bal_upd, avl_del_return &ret_struct) {
- bool player0 = tio.player()==0;
- RegBS s0, s1;
- s1.set(tio.player()==1);
-
-
-
- RegBS F_nr;
- mpc_or(tio, yield, F_nr, F_rs, F_ri);
-
- ret_struct.F_r = F_nr;
- if(player0) {
- F_nr^=1;
- }
-
- run_coroutines(tio, [&tio, &ret_struct, F_nr, ptr](yield_t &yield)
- { mpc_select(tio, yield, ret_struct.ret_ptr, F_nr, ret_struct.ret_ptr, ptr);},
- [&tio, &bal_upd, F_rs, s1](yield_t &yield)
- {
- mpc_select(tio, yield, bal_upd, F_rs, bal_upd, s1);});
- }
- std::tuple<bool, RegBS> AVL::del(MPCTIO &tio, yield_t &yield, RegXS ptr, RegAS del_key,
- Duoram<Node>::Flat &A, RegBS found, RegBS find_successor, int TTL,
- avl_del_return &ret_struct) {
- bool player0 = tio.player()==0;
- if(TTL==0) {
-
- bool success = reconstruct_RegBS(tio, yield, found);
- RegBS zero;
- return {success, zero};
- } else {
- Node node;
- RegXS oldptrs;
-
-
-
- nbits_t width = ceil(log2(cur_max_index+1));
- typename Duoram<Node>::template OblivIndex<RegXS,1> oidx(tio, yield, ptr, width);
- if(OPTIMIZED) {
- node = A[oidx];
- oldptrs = node.pointers;
- } else {
- node = A[ptr];
- }
- RegXS left = getAVLLeftPtr(node.pointers);
- RegXS right = getAVLRightPtr(node.pointers);
- size_t &aes_ops = tio.aes_ops();
- RegBS l0, r0, lt, eq, gt;
-
-
-
- run_coroutines(tio, [&tio, &l0, left, &aes_ops](yield_t &yield)
- { CDPF cdpf = tio.cdpf(yield);
- l0 = cdpf.is_zero(tio, yield, left, aes_ops);},
- [&tio, &r0, right, &aes_ops](yield_t &yield)
- { CDPF cdpf = tio.cdpf(yield);
- r0 = cdpf.is_zero(tio, yield, right, aes_ops);},
-
- [&tio, <, &eq, >, del_key, node, aes_ops](yield_t &yield)
- { CDPF cdpf = tio.cdpf(yield);
- auto [a, b, c] = cdpf.compare(tio, yield, del_key - node.key, tio.aes_ops());
- lt = a; eq = b; gt = c;});
-
-
- RegBS c = gt;
-
- RegBS lf = eq;
-
-
-
- RegBS F_0, F_1, F_2, F_n2;
- RegBS F_c1, F_c2, F_c3, F_c4, c_prime, F_dh, F_rs;
- RegXS next_ptr, cs_ptr;
- RegBS not_found = found;
- if(player0) {
- not_found^=1;
- }
-
- F_1 = l0 ^ r0;
-
-
- run_coroutines(tio, [&tio, &F_0, l0, r0](yield_t &yield)
- { mpc_and(tio, yield, F_0, l0, r0);},
- [&tio, &F_c1, lf, F_1](yield_t &yield)
- { mpc_and(tio, yield, F_c1, lf, F_1);},
-
-
- [&tio, &F_dh, not_found, lf](yield_t &yield)
- { mpc_and(tio, yield, F_dh, not_found, lf);});
-
- F_n2 = F_0 ^ F_1;
- F_2 = F_n2;
- if(player0) {
- F_2^=1;
- }
-
- RegBS s1, s0;
- s1.set(tio.player()==1);
-
-
-
-
-
- run_coroutines(tio, [&tio, &c_prime, F_c1, c, l0](yield_t &yield)
- { mpc_select(tio, yield, c_prime, F_c1, c, l0);},
- [&tio, &F_c2, lf, F_2](yield_t &yield)
- { mpc_and(tio, yield, F_c2, lf, F_2);},
-
-
-
-
- [&tio, &F_rs, F_dh, F_n2](yield_t &yield)
- { mpc_and(tio, yield, F_rs, F_dh, F_n2);});
-
-
-
-
-
- run_coroutines(tio, [&tio, &c_prime, F_c2, s1](yield_t &yield)
- { mpc_select(tio, yield, c_prime, F_c2, c_prime, s1);},
- [&tio, &F_c3, find_successor, F_2](yield_t &yield)
- { mpc_and(tio, yield, F_c3, find_successor, F_2);});
-
-
-
- run_coroutines(tio, [&tio, &c_prime, F_c3, s0](yield_t &yield)
- { mpc_select(tio, yield, c_prime, F_c3, c_prime, s0);},
- [&tio, &F_c4, find_successor, l0](yield_t &yield)
- { mpc_and(tio, yield, F_c4, find_successor, l0);},
-
-
- [&tio, &ret_struct, F_c2](yield_t &yield)
- { mpc_or(tio, yield, ret_struct.F_ss, ret_struct.F_ss, F_c2);},
- [&tio, &ret_struct, F_dh, ptr](yield_t &yield)
- { mpc_select(tio, yield, ret_struct.N_d, F_dh, ret_struct.N_d, ptr);});
- RegBS found_prime, find_successor_prime;
-
- RegBS F_sf = F_c4;
- run_coroutines(tio, [&tio, &c_prime, F_c4, l0](yield_t &yield)
- { mpc_select(tio, yield, c_prime, F_c4, c_prime, l0);},
- [&tio, &F_rs, F_sf](yield_t &yield)
- { mpc_or(tio, yield, F_rs, F_rs, F_sf);},
- [&tio, &ret_struct, F_sf, ptr](yield_t &yield)
- { mpc_select(tio, yield, ret_struct.N_s, F_sf, ret_struct.N_s, ptr);});
-
- mpc_select(tio, yield, next_ptr, c_prime, left, right, AVL_PTR_SIZE);
-
- run_coroutines(tio, [&tio, &cs_ptr, c_prime, right, left](yield_t &yield)
- { mpc_select(tio, yield, cs_ptr, c_prime, right, left, AVL_PTR_SIZE);},
- [&tio, &found_prime, found, lf](yield_t &yield)
- { mpc_or(tio, yield, found_prime, found, lf);},
-
- [&tio, &find_successor_prime, find_successor, F_c2](yield_t &yield)
- { mpc_or(tio, yield, find_successor_prime, find_successor, F_c2);});
-
- find_successor_prime=find_successor_prime^F_c4;
- TTL-=1;
- auto [key_found, bal_upd] = del(tio, yield, next_ptr, del_key, A, found_prime, find_successor_prime, TTL, ret_struct);
-
- if(!key_found) {
- return {false, s0};
- }
- updateChildPointers(tio, yield, left, right, c_prime, ret_struct);
- setAVLLeftPtr(node.pointers, left);
- setAVLRightPtr(node.pointers, right);
-
-
-
- ret_struct.F_r = s0;
- RegBS p_bal_l, p_bal_r;
- p_bal_l = getLeftBal(node.pointers);
- p_bal_r = getRightBal(node.pointers);
- #ifdef AVL_DEBUG
- size_t rec_key = mpc_reconstruct(tio, yield, node.key);
- bool rec_bal_upd = mpc_reconstruct(tio, yield, bal_upd);
- printf("current_key = %ld, bal_upd (before updateBalanceDel) = %d\n", rec_key, rec_bal_upd);
- #endif
- auto [new_p_bal_l, new_p_bal_r, new_bal_upd, imb] =
- updateBalanceDel(tio, yield, p_bal_l, p_bal_r, bal_upd, c_prime);
- bal_upd = new_bal_upd;
- #ifdef AVL_DEBUG
- bool rec_imb = mpc_reconstruct(tio, yield, imb);
- bool rec_new_bal_upd = mpc_reconstruct(tio, yield, new_bal_upd);
- printf("new_bal_upd (after updateBalanceDel) = %d, imb = %d\n", rec_new_bal_upd, rec_imb);
- #endif
-
- RegBS F_ri;
- fixImbalance(tio, yield, A, oidx, oldptrs, ptr, node.pointers, new_p_bal_l, new_p_bal_r, bal_upd,
- c_prime, cs_ptr, imb, F_ri, ret_struct);
- #ifdef AVL_DEBUG
- rec_imb = mpc_reconstruct(tio, yield, imb);
- rec_bal_upd = mpc_reconstruct(tio, yield, bal_upd);
- printf("imb (after fixImbalance) = %d, bal_upd = %d\n", rec_imb, rec_bal_upd);
- #endif
- updateRetStruct(tio, yield, ptr, F_rs, F_dh, F_ri, bal_upd, ret_struct);
- #ifdef AVL_DEBUG
- rec_bal_upd = mpc_reconstruct(tio, yield, bal_upd);
- printf("bal_upd (after updateRetStruct) = %d\n", rec_bal_upd);
- #endif
- return {key_found, bal_upd};
- }
- }
- bool AVL::del(MPCTIO &tio, yield_t &yield, RegAS del_key) {
- if(num_items==0) {
- return false;
- }
- auto A = oram.flat(tio, yield, 0, cur_max_index+1);
- if(num_items==1) {
-
- Node zero;
- nbits_t width = ceil(log2(cur_max_index+1));
- typename Duoram<Node>::template OblivIndex<RegXS,1> oidx(tio, yield, root, width);
- Node node = A[oidx];
-
- CDPF cdpf = tio.cdpf(yield);
- auto [lt, eq, gt] = cdpf.compare(tio, yield, del_key - node.key, tio.aes_ops());
- bool success = reconstruct_RegBS(tio, yield, eq);
- if(success) {
- empty_locations.emplace_back(root);
- A[oidx] = zero;
- num_items--;
- return true;
- } else {
- return false;
- }
- } else {
- int TTL = AVL_TTL(num_items);
-
-
- RegBS found, find_successor;
- avl_del_return ret_struct;
- auto [success, bal_upd] = del(tio, yield, root, del_key, A, found, find_successor, TTL, ret_struct);
-
- if(!success){
- return false;
- }
- else{
- num_items--;
-
- Node del_node, suc_node;
- nbits_t width = ceil(log2(cur_max_index+1));
- std::optional<Duoram<Node>::template OblivIndex<RegXS,2>> oidx_nd;
- std::optional<Duoram<Node>::template OblivIndex<RegXS,2>> oidx_ns;
- std::vector<coro_t> coroutines;
- if(OPTIMIZED) {
- oidx_nd.emplace(tio, yield, ret_struct.N_d, width);
- oidx_ns.emplace(tio, yield, ret_struct.N_s, width);
- coroutines.emplace_back(
- [&tio, &A, &oidx_nd, &del_node](yield_t &yield) {
- auto acont = A.context(yield);
- del_node = acont[oidx_nd.value()];});
- coroutines.emplace_back(
- [&tio, &A, &oidx_ns, &suc_node](yield_t &yield) {
- auto acont = A.context(yield);
- suc_node = acont[oidx_ns.value()];});
- run_coroutines(tio, coroutines);
- coroutines.clear();
- } else{
- del_node = A[ret_struct.N_d];
- suc_node = A[ret_struct.N_s];
- }
- RegAS zero_as; RegXS zero_xs;
-
- mpc_select(tio, yield, root, ret_struct.F_r, root, ret_struct.ret_ptr);
-
- RegXS old_del_value;
- RegAS old_del_key;
- RegXS empty_loc;
- if(OPTIMIZED) {
- old_del_value = del_node.value;
- old_del_key = del_node.key;
- }
- run_coroutines(tio, [&tio, &del_node, ret_struct, suc_node](yield_t &yield)
- { mpc_select(tio, yield, del_node.key, ret_struct.F_ss, del_node.key, suc_node.key);},
- [&tio, &del_node, ret_struct, suc_node] (yield_t &yield)
- { mpc_select(tio, yield, del_node.value, ret_struct.F_ss, del_node.value, suc_node.value);},
- [&tio, &empty_loc, ret_struct](yield_t &yield)
- { mpc_select(tio, yield, empty_loc, ret_struct.F_ss, ret_struct.N_d, ret_struct.N_s);});
- if(OPTIMIZED) {
- coroutines.emplace_back(
- [&tio, &A, &oidx_nd, &del_node, old_del_key] (yield_t &yield) {
- auto acont = A.context(yield);
- acont[oidx_nd.value()].NODE_KEY+=(del_node.key - old_del_key);
- });
- coroutines.emplace_back(
- [&tio, &A, &oidx_nd, &del_node, old_del_value] (yield_t &yield) {
- auto acont = A.context(yield);
- acont[oidx_nd.value()].NODE_VALUE+=(del_node.value - old_del_value);
- });
- coroutines.emplace_back(
- [&tio, &A, &oidx_ns, &suc_node] (yield_t &yield) {
- auto acont = A.context(yield);
- acont[oidx_ns.value()].NODE_KEY+=(-suc_node.key);
- });
- coroutines.emplace_back(
- [&tio, &A, &oidx_ns, &suc_node] (yield_t &yield) {
- auto acont = A.context(yield);
- acont[oidx_ns.value()].NODE_VALUE+=(-suc_node.value);
- });
- run_coroutines(tio, coroutines);
- coroutines.clear();
- } else {
- A[ret_struct.N_d].NODE_KEY = del_node.key;
- A[ret_struct.N_d].NODE_VALUE = del_node.value;
- A[ret_struct.N_s].NODE_KEY = zero_as;
- A[ret_struct.N_s].NODE_VALUE = zero_xs;
- }
-
- empty_locations.emplace_back(empty_loc);
- }
- return true;
- }
- }
- void AVL::initialize(MPCTIO &tio, yield_t &yield, size_t depth) {
- size_t init_size = (size_t(1)<<depth) - 1;
- auto A = oram.flat(tio, yield);
- A.explicitonly(true);
- for(size_t i=1; i<=depth; i++) {
- size_t start = size_t(1)<<(i-1);
- size_t gap = size_t(1)<<i;
- size_t current = start;
- for(size_t j=1; j<=(size_t(1)<<(depth-i)); j++) {
-
- Node node;
- node.key.set(current * tio.player());
- if(i!=1) {
-
- size_t ptr_gap = start/2;
- RegXS lptr, rptr;
- lptr.set(tio.player() * (current-(ptr_gap)));
- rptr.set(tio.player() * (current+(ptr_gap)));
- setAVLLeftPtr(node.pointers, lptr);
- setAVLRightPtr(node.pointers, rptr);
- }
- A[current] = node;
- current+=gap;
- }
- }
- A.explicitonly(false);
-
- num_items = init_size;
- cur_max_index = num_items;
-
- root.set(tio.player() * size_t(1)<<(depth-1));
- }
- void avl(MPCIO &mpcio,
- const PRACOptions &opts, char **args)
- {
- int nargs = 0;
- while(args[nargs]!=nullptr) {
- ++nargs;
- }
- int depth = 0;
- size_t n_inserts = 0;
- size_t n_deletes = 0;
- bool run_sanity = 0;
- bool optimized = false;
-
- for (int i = 0; i < nargs; i += 2) {
- std::string option = args[i];
- if (option == "-m" && i + 1 < nargs) {
- depth = std::atoi(args[i + 1]);
- } else if (option == "-i" && i + 1 < nargs) {
- n_inserts = std::atoi(args[i + 1]);
- } else if (option == "-e" && i + 1 < nargs) {
- n_deletes = std::atoi(args[i + 1]);
- } else if (option == "-opt" && i + 1 < nargs) {
- optimized = std::atoi(args[i + 1]);
- } else if (option == "-s" && i + 1 < nargs) {
- run_sanity = std::atoi(args[i + 1]);
- }
- }
-
- size_t init_size = (size_t(1)<<(depth));
- size_t oram_size = init_size + n_inserts;
- MPCTIO tio(mpcio, 0, opts.num_cpu_threads);
- run_coroutines(tio, [&tio, &mpcio, depth, oram_size, init_size, n_inserts, n_deletes, run_sanity, optimized] (yield_t &yield) {
-
- std::cout << "\n===== SETUP =====\n";
- AVL tree(tio.player(), oram_size, optimized);
- tree.initialize(tio, yield, depth);
-
- tio.sync_lamport();
- Node node;
- mpcio.dump_stats(std::cout);
- std::cout << "\n===== INSERTS =====\n";
- mpcio.reset_stats();
- tio.reset_lamport();
- for(size_t i = 1; i<=n_inserts; i++) {
- randomize_node(node);
- size_t ikey;
- #ifdef AVL_RANDOMIZE_INSERTS
- ikey = (1+(rand()%oram_size));
- #else
- ikey = (i+init_size);
- #endif
- printf("Insert key = %ld\n", ikey);
- node.key.set(ikey * tio.player());
- tree.insert(tio, yield, node);
- if(run_sanity) {
- tree.pretty_print(tio, yield);
- if(tio.player()==0) {
- assert(tree.check_avl(tio, yield));
- } else {
- tree.check_avl(tio, yield);
- }
- }
-
- }
- tio.sync_lamport();
- mpcio.dump_stats(std::cout);
- std::cout << "\n===== DELETES =====\n";
- mpcio.reset_stats();
- tio.reset_lamport();
- for(size_t i = 1; i<=n_deletes; i++) {
- RegAS del_key;
- size_t dkey;
- #ifdef AVL_RANDOMIZE_INSERTS
- dkey = 1 + (rand()%init_size);
- #else
- dkey = i + 0;
- #endif
- del_key.set(dkey * tio.player());
- printf("Deletion key = %ld\n", dkey);
- tree.del(tio, yield, del_key);
- if(run_sanity) {
- tree.pretty_print(tio, yield);
- if(tio.player()==0) {
- assert(tree.check_avl(tio, yield));
- } else {
- tree.check_avl(tio, yield);
- }
- }
- }
- });
- }
- void avl_tests(MPCIO &mpcio,
- const PRACOptions &opts, char **args)
- {
-
- nbits_t depth=4;
- size_t items = (size_t(1)<<depth)-1;
- MPCTIO tio(mpcio, 0, opts.num_cpu_threads);
- run_coroutines(tio, [&tio, depth, items] (yield_t &yield) {
- size_t size = size_t(1)<<depth;
- bool player0 = tio.player()==0;
- AVL tree(tio.player(), size);
-
-
- {
- bool success = true;
- int insert_array[] = {5, 7, 9};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, left_node, right_node;
- size_t left_index, right_index;
- root_node = R[root];
- if((root_node.key).share()!=7) {
- success = false;
- }
- left_index = (getAVLLeftPtr(root_node.pointers)).share();
- right_index = (getAVLRightPtr(root_node.pointers)).share();
- left_node = R[left_index];
- right_node = R[right_index];
- if(left_node.key.share()!=5 || right_node.key.share()!=9) {
- success = false;
- }
-
- size_t sum = left_node.pointers.share() + right_node.pointers.share();
- if(sum!=0) {
- success = false;
- }
- if(player0) {
- if(success) {
- print_green("T1 : SUCCESS\n");
- } else {
- print_red("T1 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
-
-
- {
- bool success = true;
- int insert_array[] = {5, 3, 7, 9, 12};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, n3, n7, n9, n12;
- size_t n3_index, n7_index, n9_index, n12_index;
- root_node = R[root];
- if((root_node.key).share()!=5) {
- success = false;
- }
- n3_index = (getAVLLeftPtr(root_node.pointers)).share();
- n9_index = (getAVLRightPtr(root_node.pointers)).share();
- n3 = R[n3_index];
- n9 = R[n9_index];
- n7_index = getAVLLeftPtr(n9.pointers).share();
- n12_index = getAVLRightPtr(n9.pointers).share();
- n7 = R[n7_index];
- n12 = R[n12_index];
-
- if(n3.key.share()!=3 || n9.key.share()!=9) {
- success = false;
- }
- if(n7.key.share()!=7 || n12.key.share()!=12) {
- success = false;
- }
-
- size_t zero = 0;
- zero+=(n3.pointers.share());
- zero+=(n7.pointers.share());
- zero+=(n12.pointers.share());
- zero+=(getLeftBal(root_node.pointers).share());
- zero+=(getLeftBal(n9.pointers).share());
- zero+=(getRightBal(n9.pointers).share());
- if(zero!=0) {
- success = false;
- }
- int one = (getRightBal(root_node.pointers).share());
- if(one!=1) {
- success = false;
- }
- if(player0) {
- if(success) {
- print_green("T2 : SUCCESS\n");
- } else {
- print_red("T2 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
-
-
- {
- bool success = true;
- int insert_array[] = {9, 7, 5};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, left_node, right_node;
- size_t left_index, right_index;
- root_node = R[root];
- if((root_node.key).share()!=7) {
- success = false;
- }
- left_index = (getAVLLeftPtr(root_node.pointers)).share();
- right_index = (getAVLRightPtr(root_node.pointers)).share();
- left_node = R[left_index];
- right_node = R[right_index];
- if(left_node.key.share()!=5 || right_node.key.share()!=9) {
- success = false;
- }
-
- size_t sum = left_node.pointers.share() + right_node.pointers.share();
- if(sum!=0) {
- success = false;
- }
- if(player0) {
- if(success) {
- print_green("T3 : SUCCESS\n");
- } else{
- print_red("T3 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
-
-
- {
- bool success = true;
- int insert_array[] = {9, 12, 7, 5, 3};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, n3, n7, n5, n12;
- size_t n3_index, n7_index, n5_index, n12_index;
- root_node = R[root];
- if((root_node.key).share()!=9) {
- success = false;
- }
- n5_index = (getAVLLeftPtr(root_node.pointers)).share();
- n12_index = (getAVLRightPtr(root_node.pointers)).share();
- n5 = R[n5_index];
- n12 = R[n12_index];
- n3_index = getAVLLeftPtr(n5.pointers).share();
- n7_index = getAVLRightPtr(n5.pointers).share();
- n7 = R[n7_index];
- n3 = R[n3_index];
-
- if(n12.key.share()!=12 || n5.key.share()!=5) {
- success = false;
- }
- if(n3.key.share()!=3 || n7.key.share()!=7) {
- success = false;
- }
-
- size_t zero = 0;
- zero+=(n3.pointers.share());
- zero+=(n7.pointers.share());
- zero+=(n12.pointers.share());
- zero+=(getRightBal(root_node.pointers).share());
- zero+=(getLeftBal(n5.pointers).share());
- zero+=(getRightBal(n5.pointers).share());
- if(zero!=0) {
- success = false;
- }
- int one = (getLeftBal(root_node.pointers).share());
- if(one!=1) {
- success = false;
- }
- if(player0) {
- if(success) {
- print_green("T4 : SUCCESS\n");
- } else {
- print_red("T4 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
-
-
- {
- bool success = true;
- int insert_array[] = {9, 5, 7};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, n9, n5;
- size_t n9_index, n5_index;
- root_node = R[root];
- if((root_node.key).share()!=7) {
- success = false;
- }
- n5_index = (getAVLLeftPtr(root_node.pointers)).share();
- n9_index = (getAVLRightPtr(root_node.pointers)).share();
- n5 = R[n5_index];
- n9 = R[n9_index];
-
- if(n9.key.share()!=9 || n5.key.share()!=5) {
- success = false;
- }
-
- size_t zero = 0;
- zero+=(n5.pointers.share());
- zero+=(n9.pointers.share());
- zero+=(getRightBal(root_node.pointers).share());
- zero+=(getLeftBal(n5.pointers).share());
- zero+=(getRightBal(n5.pointers).share());
- zero+=(getLeftBal(n5.pointers).share());
- zero+=(getRightBal(n9.pointers).share());
- zero+=(getLeftBal(n9.pointers).share());
- if(zero!=0) {
- success = false;
- }
- if(player0) {
- if(success) {
- print_green("T5 : SUCCESS\n");
- } else {
- print_red("T5 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
-
-
- {
- bool success = true;
- int insert_array[] = {9, 12, 7, 3, 5};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, n3, n7, n5, n12;
- size_t n3_index, n7_index, n5_index, n12_index;
- root_node = R[root];
- if((root_node.key).share()!=9) {
- success = false;
- }
- n5_index = (getAVLLeftPtr(root_node.pointers)).share();
- n12_index = (getAVLRightPtr(root_node.pointers)).share();
- n5 = R[n5_index];
- n12 = R[n12_index];
- n3_index = getAVLLeftPtr(n5.pointers).share();
- n7_index = getAVLRightPtr(n5.pointers).share();
- n7 = R[n7_index];
- n3 = R[n3_index];
-
- if(n5.key.share()!=5 || n12.key.share()!=12) {
- success = false;
- }
- if(n3.key.share()!=3 || n7.key.share()!=7) {
- success = false;
- }
-
- size_t zero = 0;
- zero+=(n3.pointers.share());
- zero+=(n7.pointers.share());
- zero+=(n12.pointers.share());
- zero+=(getRightBal(root_node.pointers).share());
- zero+=(getLeftBal(n5.pointers).share());
- zero+=(getRightBal(n5.pointers).share());
- if(zero!=0) {
- success = false;
- }
- int one = (getLeftBal(root_node.pointers).share());
- if(one!=1) {
- success = false;
- }
- if(player0) {
- if(success) {
- print_green("T6 : SUCCESS\n");
- } else {
- print_red("T6 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
-
-
- {
- bool success = true;
- int insert_array[] = {5, 9, 7};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, n9, n5;
- size_t n9_index, n5_index;
- root_node = R[root];
- if((root_node.key).share()!=7) {
- success = false;
- }
- n5_index = (getAVLLeftPtr(root_node.pointers)).share();
- n9_index = (getAVLRightPtr(root_node.pointers)).share();
- n5 = R[n5_index];
- n9 = R[n9_index];
-
- if(n9.key.share()!=9 || n5.key.share()!=5) {
- success = false;
- }
-
- size_t zero = 0;
- zero+=(n5.pointers.share());
- zero+=(n9.pointers.share());
- zero+=(getRightBal(root_node.pointers).share());
- zero+=(getLeftBal(n5.pointers).share());
- zero+=(getRightBal(n5.pointers).share());
- zero+=(getLeftBal(n5.pointers).share());
- zero+=(getRightBal(n9.pointers).share());
- zero+=(getLeftBal(n9.pointers).share());
- if(zero!=0) {
- success = false;
- }
- if(player0) {
- if(success) {
- print_green("T7 : SUCCESS\n");
- } else {
- print_red("T7 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
-
-
- {
- bool success = true;
- int insert_array[] = {5, 3, 12, 7, 9};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, n3, n7, n9, n12;
- size_t n3_index, n7_index, n9_index, n12_index;
- root_node = R[root];
- if((root_node.key).share()!=5) {
- success = false;
- }
- n3_index = (getAVLLeftPtr(root_node.pointers)).share();
- n9_index = (getAVLRightPtr(root_node.pointers)).share();
- n3 = R[n3_index];
- n9 = R[n9_index];
- n7_index = getAVLLeftPtr(n9.pointers).share();
- n12_index = getAVLRightPtr(n9.pointers).share();
- n7 = R[n7_index];
- n12 = R[n12_index];
-
- if(n3.key.share()!=3 || n9.key.share()!=9) {
- success = false;
- }
- if(n7.key.share()!=7 || n12.key.share()!=12) {
- success = false;
- }
-
- size_t zero = 0;
- zero+=(n3.pointers.share());
- zero+=(n7.pointers.share());
- zero+=(n12.pointers.share());
- zero+=(getLeftBal(root_node.pointers).share());
- zero+=(getLeftBal(n9.pointers).share());
- zero+=(getRightBal(n9.pointers).share());
- if(zero!=0) {
- success = false;
- }
- int one = (getRightBal(root_node.pointers).share());
- if(one!=1) {
- success = false;
- }
- if(player0) {
- if(success) {
- print_green("T8 : SUCCESS\n");
- } else {
- print_red("T8 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
-
-
-
- {
- bool success = true;
- int insert_array[] = {5, 3, 7, 9};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- RegAS del_key;
- del_key.set(3 * tio.player());
- bool del_ret;
- del_ret = tree.del(tio, yield, del_key);
- success &= tree.check_avl(tio, yield);
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, left_node, right_node;
- size_t left_index, right_index;
- root_node = R[root];
- if((root_node.key).share()!=7) {
- success = false;
- }
- left_index = (getAVLLeftPtr(root_node.pointers)).share();
- right_index = (getAVLRightPtr(root_node.pointers)).share();
- left_node = R[left_index];
- right_node = R[right_index];
- if(left_node.key.share()!=5 || right_node.key.share()!=9) {
- success = false;
- }
-
- size_t sum = left_node.pointers.share() + right_node.pointers.share();
- if(sum!=0) {
- success = false;
- }
- success &= del_ret;
- if(player0) {
- if(success) {
- print_green("T9 : SUCCESS\n");
- } else {
- print_red("T9 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
-
-
- {
- bool success = true;
- int insert_array[] = {5, 3, 7, 9, 6, 1, 12};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- RegAS del_key;
- del_key.set(6 * tio.player());
- bool del_ret;
- del_ret = tree.del(tio, yield, del_key);
- success &= tree.check_avl(tio, yield);
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, n1, n3, n7, n9, n12;
- size_t n1_index, n3_index, n7_index, n9_index, n12_index;
- root_node = R[root];
- if((root_node.key).share()!=5) {
- success = false;
- }
- n3_index = (getAVLLeftPtr(root_node.pointers)).share();
- n9_index = (getAVLRightPtr(root_node.pointers)).share();
- n3 = R[n3_index];
- n9 = R[n9_index];
- n7_index = getAVLLeftPtr(n9.pointers).share();
- n12_index = getAVLRightPtr(n9.pointers).share();
- n7 = R[n7_index];
- n12 = R[n12_index];
- n1_index = getAVLLeftPtr(n3.pointers).share();
- n1 = R[n1_index];
-
- if(n3.key.share()!=3 || n9.key.share()!=9) {
- success = false;
- }
- if(n7.key.share()!=7 || n12.key.share()!=12 || n1.key.share()!=1) {
- success = false;
- }
-
- size_t zero = 0;
- zero+=(n1.pointers.share());
- zero+=(n7.pointers.share());
- zero+=(n12.pointers.share());
- zero+=(getLeftBal(root_node.pointers).share());
- zero+=(getRightBal(root_node.pointers).share());
- zero+=(getLeftBal(n9.pointers).share());
- zero+=(getRightBal(n9.pointers).share());
- zero+=(getRightBal(n3.pointers).share());
- if(zero!=0) {
- success = false;
- }
- int one = (getLeftBal(n3.pointers).share());
- if(one!=1) {
- success = false;
- }
- success &= del_ret;
- if(player0) {
- if(success) {
- print_green("T10 : SUCCESS\n");
- } else {
- print_red("T10 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
-
-
- {
- bool success = true;
- int insert_array[] = {9, 7, 12, 5};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- RegAS del_key;
- del_key.set(12 * tio.player());
- bool del_ret;
- del_ret = tree.del(tio, yield, del_key);
- success &= tree.check_avl(tio, yield);
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, left_node, right_node;
- size_t left_index, right_index;
- root_node = R[root];
- if((root_node.key).share()!=7) {
- success = false;
- }
- left_index = (getAVLLeftPtr(root_node.pointers)).share();
- right_index = (getAVLRightPtr(root_node.pointers)).share();
- left_node = R[left_index];
- right_node = R[right_index];
- if(left_node.key.share()!=5 || right_node.key.share()!=9) {
- success = false;
- }
-
- size_t zero = left_node.pointers.share() + right_node.pointers.share();
- zero+=(getLeftBal(left_node.pointers).share());
- zero+=(getRightBal(left_node.pointers).share());
- zero+=(getLeftBal(right_node.pointers).share());
- zero+=(getRightBal(right_node.pointers).share());
- if(zero!=0) {
- success = false;
- }
- success &= del_ret;
- if(player0) {
- if(success) {
- print_green("T11 : SUCCESS\n");
- } else{
- print_red("T11 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
-
-
- {
- bool success = true;
- int insert_array[] = {9, 12, 7, 5, 8, 15, 3};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- RegAS del_key;
- del_key.set(8 * tio.player());
- bool del_ret;
- del_ret = tree.del(tio, yield, del_key);
- success &= tree.check_avl(tio, yield);
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, n3, n7, n5, n12, n15;
- size_t n3_index, n7_index, n5_index, n12_index, n15_index;
- root_node = R[root];
- if((root_node.key).share()!=9) {
- success = false;
- }
- n5_index = (getAVLLeftPtr(root_node.pointers)).share();
- n12_index = (getAVLRightPtr(root_node.pointers)).share();
- n5 = R[n5_index];
- n12 = R[n12_index];
- n3_index = getAVLLeftPtr(n5.pointers).share();
- n7_index = getAVLRightPtr(n5.pointers).share();
- n7 = R[n7_index];
- n3 = R[n3_index];
- n15_index = getAVLRightPtr(n12.pointers).share();
- n15 = R[n15_index];
-
- if(n12.key.share()!=12 || n5.key.share()!=5) {
- success = false;
- }
- if(n3.key.share()!=3 || n7.key.share()!=7 || n15.key.share()!=15) {
- success = false;
- }
-
- size_t zero = 0;
- zero+=(n3.pointers.share());
- zero+=(n7.pointers.share());
- zero+=(n15.pointers.share());
- zero+=(getRightBal(root_node.pointers).share());
- zero+=(getLeftBal(root_node.pointers).share());
- zero+=(getLeftBal(n5.pointers).share());
- zero+=(getRightBal(n5.pointers).share());
- if(zero!=0) {
- success = false;
- }
- int one = (getRightBal(n12.pointers).share());
- if(one!=1) {
- success = false;
- }
- success &= del_ret;
- if(player0) {
- if(success) {
- print_green("T12 : SUCCESS\n");
- } else {
- print_red("T12 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
-
-
- {
- bool success = true;
- int insert_array[] = {9, 5, 12, 7};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- RegAS del_key;
- del_key.set(12 * tio.player());
- bool del_ret;
- del_ret = tree.del(tio, yield, del_key);
- success &= tree.check_avl(tio, yield);
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, n9, n5;
- size_t n9_index, n5_index;
- root_node = R[root];
- if((root_node.key).share()!=7) {
- success = false;
- }
- n5_index = (getAVLLeftPtr(root_node.pointers)).share();
- n9_index = (getAVLRightPtr(root_node.pointers)).share();
- n5 = R[n5_index];
- n9 = R[n9_index];
-
- if(n9.key.share()!=9 || n5.key.share()!=5) {
- success = false;
- }
-
- size_t zero = 0;
- zero+=(n5.pointers.share());
- zero+=(n9.pointers.share());
- zero+=(getRightBal(root_node.pointers).share());
- zero+=(getLeftBal(n5.pointers).share());
- zero+=(getRightBal(n5.pointers).share());
- zero+=(getLeftBal(n5.pointers).share());
- zero+=(getRightBal(n9.pointers).share());
- zero+=(getLeftBal(n9.pointers).share());
- if(zero!=0) {
- success = false;
- }
- success &= del_ret;
- if(player0) {
- if(success) {
- print_green("T13 : SUCCESS\n");
- } else {
- print_red("T13 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
-
-
- {
- bool success = true;
- int insert_array[] = {9, 12, 7, 3, 5};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- RegAS del_key;
- del_key.set(8 * tio.player());
- bool del_ret;
- del_ret = tree.del(tio, yield, del_key);
- success &= tree.check_avl(tio, yield);
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, n3, n7, n5, n12;
- size_t n3_index, n7_index, n5_index, n12_index;
- root_node = R[root];
- if((root_node.key).share()!=9) {
- success = false;
- }
- n5_index = (getAVLLeftPtr(root_node.pointers)).share();
- n12_index = (getAVLRightPtr(root_node.pointers)).share();
- n5 = R[n5_index];
- n12 = R[n12_index];
- n3_index = getAVLLeftPtr(n5.pointers).share();
- n7_index = getAVLRightPtr(n5.pointers).share();
- n7 = R[n7_index];
- n3 = R[n3_index];
-
- if(n5.key.share()!=5 || n12.key.share()!=12) {
- success = false;
- }
- if(n3.key.share()!=3 || n7.key.share()!=7) {
- success = false;
- }
-
- size_t zero = 0;
- zero+=(n3.pointers.share());
- zero+=(n7.pointers.share());
- zero+=(n12.pointers.share());
- zero+=(getRightBal(root_node.pointers).share());
- zero+=(getLeftBal(n5.pointers).share());
- zero+=(getRightBal(n5.pointers).share());
- if(zero!=0) {
- success = false;
- }
- int one = (getLeftBal(root_node.pointers).share());
- if(one!=1) {
- success = false;
- }
- success &=(!del_ret);
- if(player0) {
- if(success) {
- print_green("T14 : SUCCESS\n");
- } else {
- print_red("T14 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
-
-
- {
- bool success = true;
- int insert_array[] = {5, 9, 3, 7};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- RegAS del_key;
- del_key.set(3 * tio.player());
- bool del_ret;
- del_ret = tree.del(tio, yield, del_key);
- success &= tree.check_avl(tio, yield);
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, n9, n5;
- size_t n9_index, n5_index;
- root_node = R[root];
- if((root_node.key).share()!=7) {
- success = false;
- }
- n5_index = (getAVLLeftPtr(root_node.pointers)).share();
- n9_index = (getAVLRightPtr(root_node.pointers)).share();
- n5 = R[n5_index];
- n9 = R[n9_index];
-
- if(n9.key.share()!=9 || n5.key.share()!=5) {
- success = false;
- }
-
- size_t zero = 0;
- zero+=(n5.pointers.share());
- zero+=(n9.pointers.share());
- zero+=(getRightBal(root_node.pointers).share());
- zero+=(getLeftBal(n5.pointers).share());
- zero+=(getRightBal(n5.pointers).share());
- zero+=(getLeftBal(n5.pointers).share());
- zero+=(getRightBal(n9.pointers).share());
- zero+=(getLeftBal(n9.pointers).share());
- if(zero!=0) {
- success = false;
- }
- success &= del_ret;
- if(player0) {
- if(success) {
- print_green("T15 : SUCCESS\n");
- } else {
- print_red("T15 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
-
-
- {
- bool success = true;
- int insert_array[] = {5, 3, 8, 7, 1, 12, 9};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- RegAS del_key;
- del_key.set(7 * tio.player());
- bool del_ret;
- del_ret = tree.del(tio, yield, del_key);
- success &= tree.check_avl(tio, yield);
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, n1, n3, n8, n9, n12;
- size_t n1_index, n3_index, n8_index, n9_index, n12_index;
- root_node = R[root];
- if((root_node.key).share()!=5) {
- success = false;
- }
- n3_index = (getAVLLeftPtr(root_node.pointers)).share();
- n9_index = (getAVLRightPtr(root_node.pointers)).share();
- n3 = R[n3_index];
- n9 = R[n9_index];
- n1_index = getAVLLeftPtr(n3.pointers).share();
- n8_index = getAVLLeftPtr(n9.pointers).share();
- n12_index = getAVLRightPtr(n9.pointers).share();
- n1 = R[n1_index];
- n8 = R[n8_index];
- n12 = R[n12_index];
-
- if(n1.key.share()!=1) {
- success = false;
- }
- if(n3.key.share()!=3 || n9.key.share()!=9) {
- success = false;
- }
- if(n8.key.share()!=8 || n12.key.share()!=12) {
- success = false;
- }
-
- size_t zero = 0;
- zero+=(n1.pointers.share());
- zero+=(getRightBal(n3.pointers).share());
- zero+=(n8.pointers.share());
- zero+=(n12.pointers.share());
- zero+=(getLeftBal(root_node.pointers).share());
- zero+=(getRightBal(root_node.pointers).share());
- zero+=(getLeftBal(n9.pointers).share());
- zero+=(getRightBal(n9.pointers).share());
- if(zero!=0) {
- success = false;
- }
- success &= del_ret;
- if(player0) {
- if(success) {
- print_green("T16 : SUCCESS\n");
- } else {
- print_red("T16 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
-
-
- {
- bool success = true;
- int insert_array[] = {9, 5, 12, 7, 3, 10, 15, 2, 4, 6, 8, 20, 1};
- size_t insert_array_size = sizeof(insert_array)/sizeof(int);
- Node node;
- for(size_t i = 0; i<insert_array_size; i++) {
- randomize_node(node);
- node.key.set(insert_array[i] * tio.player());
- tree.insert(tio, yield, node);
- success &= tree.check_avl(tio, yield);
- }
- RegAS del_key;
- del_key.set(10 * tio.player());
- bool del_ret;
- del_ret = tree.del(tio, yield, del_key);
- success &= tree.check_avl(tio, yield);
- Duoram<Node>* oram = tree.get_oram();
- RegXS root_xs = tree.get_root();
- size_t root = mpc_reconstruct(tio, yield, root_xs);
- auto A = oram->flat(tio, yield);
- auto R = A.reconstruct();
- Node root_node, n3, n7, n9;
- Node n1, n2, n4, n6, n8, n12, n15, n20;
- size_t n3_index, n7_index, n9_index;
- size_t n1_index, n2_index, n4_index, n6_index;
- size_t n8_index, n12_index, n15_index, n20_index;
- root_node = R[root];
- if((root_node.key).share()!=5) {
- success = false;
- }
- n3_index = (getAVLLeftPtr(root_node.pointers)).share();
- n9_index = (getAVLRightPtr(root_node.pointers)).share();
- n3 = R[n3_index];
- n9 = R[n9_index];
- n2_index = getAVLLeftPtr(n3.pointers).share();
- n4_index = getAVLRightPtr(n3.pointers).share();
- n7_index = getAVLLeftPtr(n9.pointers).share();
- n15_index = getAVLRightPtr(n9.pointers).share();
- n2 = R[n2_index];
- n4 = R[n4_index];
- n7 = R[n7_index];
- n15 = R[n15_index];
- n1_index = getAVLLeftPtr(n2.pointers).share();
- n6_index = getAVLLeftPtr(n7.pointers).share();
- n8_index = getAVLRightPtr(n7.pointers).share();
- n12_index = getAVLLeftPtr(n15.pointers).share();
- n20_index = getAVLRightPtr(n15.pointers).share();
- n1 = R[n1_index];
- n6 = R[n6_index];
- n8 = R[n8_index];
- n12 = R[n12_index];
- n20 = R[n20_index];
-
- if(n3.key.share()!=3 || n9.key.share()!=9) {
- success = false;
- }
- if(n2.key.share()!=2 || n4.key.share()!=4) {
- success = false;
- }
- if(n7.key.share()!=7 || n15.key.share()!=15) {
- success = false;
- }
- if(n1.key.share()!=1 || n6.key.share()!=6 || n8.key.share()!=8) {
- success = false;
- }
- if(n12.key.share()!=12 || n20.key.share()!=20) {
- success = false;
- }
-
- size_t zero = 0;
- zero+=(n1.pointers.share());
- zero+=(n4.pointers.share());
- zero+=(n6.pointers.share());
- zero+=(n8.pointers.share());
- zero+=(n12.pointers.share());
- zero+=(n20.pointers.share());
- zero+=(getLeftBal(n7.pointers).share());
- zero+=(getRightBal(n7.pointers).share());
- zero+=(getLeftBal(n9.pointers).share());
- zero+=(getRightBal(n9.pointers).share());
- zero+=(getLeftBal(n15.pointers).share());
- zero+=(getRightBal(n15.pointers).share());
- zero+=(getRightBal(n3.pointers).share());
- zero+=(getLeftBal(root_node.pointers).share());
- zero+=(getRightBal(root_node.pointers).share());
- if(zero!=0) {
- success = false;
- }
- int one = (getLeftBal(n3.pointers).share());
- if(one!=1) {
- success = false;
- }
- success &= del_ret;
- if(player0) {
- if(success) {
- print_green("T17 : SUCCESS\n");
- } else {
- print_red("T17 : FAIL\n");
- }
- }
- A.init();
- tree.init();
- }
- });
- }
|