123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814 |
- #include <functional>
- #include "types.hpp"
- #include "duoram.hpp"
- #include "cell.hpp"
- #include "rdpf.hpp"
- #include "shapes.hpp"
- #include "heap.hpp"
- void MinHeap::insert_optimized(MPCTIO &tio, yield_t & yield, RegAS val) {
- auto HeapArray = oram.flat(tio, yield);
- num_items++;
- typename Duoram<RegAS>::Path P(HeapArray, tio, yield, num_items);
- const RegXS foundidx = P.binary_search(val);
- size_t childindex = num_items;
-
- uint64_t height = P.size();
- RegAS zero;
- HeapArray[childindex] = zero;
- #ifdef HEAP_VERBOSE
- uint64_t val_reconstruction = mpc_reconstruct(tio, yield, val);
- std::cout << "val_reconstruction = " << val_reconstruction << std::endl;
- #endif
- uint64_t logheight = std::floor(double(std::log2(height))) + 1;
- std::vector<RegBS> flag;
- std::vector<RegBS> u(height);
- typename Duoram<RegAS>::template OblivIndex<RegXS,1> oidx(tio, yield, foundidx, logheight);
- flag = oidx.unit_vector(tio, yield, height, foundidx);
- #ifdef HEAP_VERBOSE
- uint64_t foundidx_reconstruction = mpc_reconstruct(tio, yield, foundidx);
- std::cout << "foundidx_reconstruction = " << foundidx_reconstruction << std::endl;
- std::cout << std::endl << " =============== " << std::endl;
- for (size_t j = 0; j < height; ++j) {
- uint64_t reconstruction = mpc_reconstruct(tio, yield, flag[j]);
- std::cout << " --->> flag[" << j << "] = " << reconstruction << std::endl;
- }
- #endif
- for (size_t j = 0; j < height; ++j) {
- if(j > 0) {
- u[j] = flag[j] ^ u[j-1];
- } else {
- u[j] = flag[j];
- }
- }
- #ifdef HEAP_VERBOSE
- for (size_t j = 0; j < height; ++j) {
- uint64_t reconstruction = mpc_reconstruct(tio, yield, u[j]);
- std::cout << " --->> [0000111111]][" << j << "] = " << reconstruction << std::endl;
- }
- #endif
- std::vector<RegAS> path(height);
- std::vector<RegAS> w(height);
- std::vector<RegAS> v(height);
- for (size_t j = 0; j < height; ++j) path[j] = P[j];
- std::vector<coro_t> coroutines;
- for (size_t j = 0; j < height; ++j) {
- if (j > 0) {
- coroutines.emplace_back(
- [&tio, &w, &u, &path, j](yield_t &yield) {
- mpc_flagmult(tio, yield, w[j], u[j-1], path[j-1]-path[j]);
- }
- );
- }
- coroutines.emplace_back(
- [&tio, &v, flag, val, &path, j](yield_t &yield) {
- mpc_flagmult(tio, yield, v[j], flag[j], val - path[j]);
- }
- );
- }
- run_coroutines(tio, coroutines);
- #ifdef HEAP_VERBOSE
- std::cout << "\n\n=================Before===========\n\n";
- auto path_rec_before = P.reconstruct();
- for (size_t j = 0; j < height; ++j) {
- std::cout << j << " --->: " << path_rec_before[j].share() << std::endl;
- }
- std::cout << "\n\n============================\n\n";
- #endif
- coroutines.clear();
- for (size_t j = 0; j < height; ++j) {
- coroutines.emplace_back( [&tio, &v, &w, &P, j](yield_t &yield) {
- auto Pcoro = P.context(yield);
- Pcoro[j] += (w[j] + v[j]);
- });
- }
- run_coroutines(tio, coroutines);
- #ifdef HEAP_VERBOSE
- std::cout << "\n\n=================After===========\n\n";
- auto path_rec_after = P.reconstruct();
- for (size_t j = 0; j < height; ++j) {
- std::cout << j << " --->: " << path_rec_after[j].share() << std::endl;
- }
- std::cout << "\n\n============================\n\n";
- #endif
- }
- void MinHeap::insert(MPCTIO &tio, yield_t & yield, RegAS val) {
- auto HeapArray = oram.flat(tio, yield);
- num_items++;
- size_t childindex = num_items;
- size_t parentindex = childindex / 2;
- #ifdef HEAP_VERBOSE
- std::cout << "childindex = " << childindex << std::endl;
- std::cout << "parentindex = " << parentindex << std::endl;
- #endif
- HeapArray[num_items] = val;
- while (parentindex > 0) {
- RegAS sharechild = HeapArray[childindex];
- RegAS shareparent = HeapArray[parentindex];
- CDPF cdpf = tio.cdpf(yield);
- RegAS diff = sharechild - shareparent;
- auto[lt, eq, gt] = cdpf.compare(tio, yield, diff, tio.aes_ops());
- mpc_oswap(tio, yield, sharechild, shareparent, lt);
- HeapArray[childindex] = sharechild;
- HeapArray[parentindex] = shareparent;
- childindex = parentindex;
- parentindex = parentindex / 2;
- }
- }
- void MinHeap::verify_heap_property(MPCTIO &tio, yield_t & yield) {
- #ifdef HEAP_VERBOSE
- std::cout << std::endl << std::endl << "verify_heap_property is being called " << std::endl;
- #endif
- auto HeapArray = oram.flat(tio, yield);
- auto heapreconstruction = HeapArray.reconstruct();
- #ifdef HEAP_VERBOSE
- for (size_t j = 1; j < num_items + 1; ++j) {
- if(tio.player() < 2) std::cout << j << " -----> heapreconstruction[" << j << "] = " << heapreconstruction[j].share() << std::endl;
- }
- #endif
- for (size_t j = 2; j <= num_items; ++j) {
- if (heapreconstruction[j/2].share() > heapreconstruction[j].share()) {
- std::cout << "heap property failure\n\n";
- std::cout << "j = " << j << std::endl;
- std::cout << heapreconstruction[j].share() << std::endl;
- std::cout << "j/2 = " << j/2 << std::endl;
- std::cout << heapreconstruction[j/2].share() << std::endl;
- }
- assert(heapreconstruction[j/2].share() <= heapreconstruction[j].share());
- }
- }
- #ifdef HEAP_DEBUG
- static void verify_parent_children_heaps(MPCTIO &tio, yield_t & yield, RegAS parent, RegAS leftchild, RegAS rightchild) {
- uint64_t parent_reconstruction = mpc_reconstruct(tio, yield, parent);
- uint64_t leftchild_reconstruction = mpc_reconstruct(tio, yield, leftchild);
- uint64_t rightchild_reconstruction = mpc_reconstruct(tio, yield, rightchild);
- std::cout << "parent_reconstruction = " << parent_reconstruction << std::endl;
- std::cout << "leftchild_reconstruction = " << leftchild_reconstruction << std::endl;
- std::cout << "rightchild_reconstruction = " << rightchild_reconstruction << std::endl << std::endl << std::endl;
- assert(parent_reconstruction <= leftchild_reconstruction);
- assert(parent_reconstruction <= rightchild_reconstruction);
- }
- #endif
- RegXS MinHeap::restore_heap_property(MPCTIO &tio, yield_t & yield, RegXS index) {
- RegAS smallest;
- auto HeapArray = oram.flat(tio, yield);
- RegXS leftchildindex = index;
- leftchildindex = index << 1;
- RegXS rightchildindex;
- rightchildindex.xshare = leftchildindex.xshare ^ (!tio.player());
- RegAS parent, leftchild, rightchild;
- #ifdef HEAP_VERBOSE
- auto index_reconstruction = mpc_reconstruct(tio, yield, index);
- auto leftchildindex_reconstruction = mpc_reconstruct(tio, yield, leftchildindex);
- auto rightchildindex_reconstruction = mpc_reconstruct(tio, yield, rightchildindex);
- std::cout << "index_reconstruction = " << index_reconstruction << std::endl;
- std::cout << "leftchildindex_reconstruction = " << leftchildindex_reconstruction << std::endl;
- std::cout << "rightchildindex_reconstruction = " << rightchildindex_reconstruction << std::endl;
- #endif
- run_coroutines(tio, [&tio, &parent, &HeapArray, index](yield_t &yield) {
- auto Acoro = HeapArray.context(yield);
- parent = Acoro[index];},
- [&tio, &HeapArray, &leftchild, leftchildindex](yield_t &yield) {
- auto Acoro = HeapArray.context(yield);
- leftchild = Acoro[leftchildindex];},
- [&tio, &rightchild, &HeapArray, rightchildindex](yield_t &yield) {
- auto Acoro = HeapArray.context(yield);
- rightchild = Acoro[rightchildindex];});
- CDPF cdpf = tio.cdpf(yield);
- auto[lt_c, eq_c, gt_c] = cdpf.compare(tio, yield, leftchild - rightchild, tio.aes_ops());
- RegXS smallerindex;
- RegAS smallerchild;
- run_coroutines(tio, [&tio, &smallerindex, lt_c, rightchildindex, leftchildindex](yield_t &yield) {
- mpc_select(tio, yield, smallerindex, lt_c, rightchildindex, leftchildindex);
- }, [&tio, &smallerchild, lt_c, rightchild, leftchild](yield_t &yield) {
- mpc_select(tio, yield, smallerchild, lt_c, rightchild, leftchild);
- }
- );
- CDPF cdpf0 = tio.cdpf(yield);
- auto[lt_p, eq_p, gt_p] = cdpf0.compare(tio, yield, smallerchild - parent, tio.aes_ops());
- RegBS ltlt1;
- mpc_and(tio, yield, ltlt1, lt_c, lt_p);
- RegAS update_index_by, update_leftindex_by;
- run_coroutines(tio, [&tio, &update_leftindex_by, ltlt1, parent, leftchild](yield_t &yield) {
- mpc_flagmult(tio, yield, update_leftindex_by, ltlt1, parent - leftchild);
- }, [&tio, &update_index_by, lt_p, parent, smallerchild](yield_t &yield) {
- mpc_flagmult(tio, yield, update_index_by, lt_p, smallerchild - parent);
- }
- );
- run_coroutines(tio, [&tio, &HeapArray, index, update_index_by](yield_t &yield) {
- auto Acoro = HeapArray.context(yield);
- Acoro[index] += update_index_by;},
- [&tio, &HeapArray, leftchildindex, update_leftindex_by](yield_t &yield) {
- auto Acoro = HeapArray.context(yield);
- Acoro[leftchildindex] += update_leftindex_by;},
- [&tio, &HeapArray, rightchildindex, update_index_by, update_leftindex_by](yield_t &yield) {
- auto Acoro = HeapArray.context(yield);
- Acoro[rightchildindex] += -(update_index_by + update_leftindex_by);});
- #ifdef HEAP_DEBUG
- verify_parent_children_heaps(tio, yield, HeapArray[index], HeapArray[leftchildindex] , HeapArray[rightchildindex]);
- #endif
- return smallerindex;
- }
- std::pair<RegXS, RegBS> MinHeap::restore_heap_property_optimized(MPCTIO &tio, yield_t & yield, RegXS index, size_t layer, typename Duoram < RegAS > ::template OblivIndex < RegXS, 3 > oidx) {
- auto HeapArray = oram.flat(tio, yield);
- RegXS leftchildindex = index;
- leftchildindex = index << 1;
- RegXS rightchildindex;
- rightchildindex.xshare = leftchildindex.xshare ^ (!tio.player());
- typename Duoram < RegAS > ::Flat P(HeapArray, tio, yield, 1 << layer, 1 << layer);
- typename Duoram < RegAS > ::Flat C(HeapArray, tio, yield, 2 << layer, 2 << layer);
- typename Duoram < RegAS > ::Stride L(C, tio, yield, 0, 2);
- typename Duoram < RegAS > ::Stride R(C, tio, yield, 1, 2);
- RegAS parent, leftchild, rightchild;
- run_coroutines(tio, [&tio, &parent, &P, &oidx](yield_t &yield) {
- auto Pcoro = P.context(yield);
- parent = Pcoro[oidx]; },
- [&tio, &L, &leftchild, &oidx](yield_t &yield) {
- auto Lcoro = L.context(yield);
- leftchild = Lcoro[oidx];},
- [&tio, &R, &rightchild, &oidx](yield_t &yield) {
- auto Rcoro = R.context(yield);
- rightchild = Rcoro[oidx];
- });
- CDPF cdpf = tio.cdpf(yield);
- auto[lt_c, eq_c, gt_c] = cdpf.compare(tio, yield, leftchild - rightchild, tio.aes_ops());
- RegXS smallerindex;
- RegAS smallerchild;
- run_coroutines(tio, [&tio, &smallerindex, lt_c, rightchildindex, leftchildindex](yield_t &yield) {
- mpc_select(tio, yield, smallerindex, lt_c, rightchildindex, leftchildindex);
- }, [&tio, &smallerchild, lt_c, rightchild, leftchild](yield_t &yield) {
- mpc_select(tio, yield, smallerchild, lt_c, rightchild, leftchild);
- }
- );
- CDPF cdpf0 = tio.cdpf(yield);
- auto[lt_p, eq_p, gt_p] = cdpf0.compare(tio, yield, smallerchild - parent, tio.aes_ops());
- RegBS ltlt1;
- mpc_and(tio, yield, ltlt1, lt_c, lt_p);
- RegAS update_index_by, update_leftindex_by;
- run_coroutines(tio, [&tio, &update_leftindex_by, ltlt1, parent, leftchild](yield_t &yield) {
- mpc_flagmult(tio, yield, update_leftindex_by, ltlt1, parent - leftchild);
- }, [&tio, &update_index_by, lt_p, parent, smallerchild](yield_t &yield) {
- mpc_flagmult(tio, yield, update_index_by, lt_p, smallerchild - parent);
- }
- );
- run_coroutines(tio, [&tio, &P, &oidx, update_index_by](yield_t &yield) {
- auto Pcoro = P.context(yield);
- Pcoro[oidx] += update_index_by;},
- [&tio, &L, &oidx, update_leftindex_by](yield_t &yield) {
- auto Lcoro = L.context(yield);
- Lcoro[oidx] += update_leftindex_by;},
- [&tio, &R, &oidx, update_leftindex_by, update_index_by](yield_t &yield) {
- auto Rcoro = R.context(yield);
- Rcoro[oidx] += -(update_leftindex_by + update_index_by);
- });
- auto gteq = gt_c ^ eq_c;
- return {smallerindex, gteq};
- }
- void MinHeap::init(MPCTIO &tio, yield_t & yield) {
- auto HeapArray = oram.flat(tio, yield);
- HeapArray.init(0x7fffffffffffffff);
- num_items = 0;
- }
- void MinHeap::init(MPCTIO &tio, yield_t & yield, size_t n) {
- auto HeapArray = oram.flat(tio, yield);
- num_items = n;
- HeapArray.init([n](size_t i) {
- if (i >= 1 && i <= n) {
- return i*100;
- } else {
- return size_t(0x7fffffffffffffff);
- }
- });
- }
- void MinHeap::print_heap(MPCTIO &tio, yield_t & yield) {
- auto HeapArray = oram.flat(tio, yield);
- auto Pjreconstruction = HeapArray.reconstruct();
- for (size_t j = 1; j <= num_items; ++j) {
- if(2 * j <= num_items) {
- std::cout << j << "-->> HeapArray[" << j << "] = " << Pjreconstruction[j].share() << ", children are: " << Pjreconstruction[2 * j].share() << " and " << Pjreconstruction[2 * j + 1].share() << std::endl;
- } else {
- std::cout << j << "-->> HeapArray[" << j << "] = " << std::dec << Pjreconstruction[j].share() << " is a LEAF " << std::endl;
- }
- }
- }
- std::pair<RegXS, RegBS> MinHeap::restore_heap_property_at_explicit_index(MPCTIO &tio, yield_t & yield, size_t index = 1) {
- auto HeapArray = oram.flat(tio, yield);
- RegAS parent = HeapArray[index];
- RegAS leftchild = HeapArray[2 * index];
- RegAS rightchild = HeapArray[2 * index + 1];
- CDPF cdpf = tio.cdpf(yield);
- auto[lt, eq, gt] = cdpf.compare(tio, yield, leftchild - rightchild, tio.aes_ops());
- auto gteq = gt ^ eq;
- RegAS smallerchild;
- mpc_select(tio, yield, smallerchild, lt, rightchild, leftchild);
- uint64_t leftchildindex = (2 * index);
- uint64_t rightchildindex = (2 * index) + 1;
- RegXS smallerindex = (RegXS(lt) & leftchildindex) ^ (RegXS(gteq) & rightchildindex);
- CDPF cdpf0 = tio.cdpf(yield);
- auto[lt1, eq1, gt1] = cdpf0.compare(tio, yield, smallerchild - parent, tio.aes_ops());
- RegBS ltlt1;
- mpc_and(tio, yield, ltlt1, lt, lt1);
- RegAS update_index_by, update_leftindex_by;
- run_coroutines(tio, [&tio, &update_leftindex_by, ltlt1, parent, leftchild](yield_t &yield) {
- mpc_flagmult(tio, yield, update_leftindex_by, ltlt1, parent - leftchild);
- }, [&tio, &update_index_by, lt1, parent, smallerchild](yield_t &yield) {
- mpc_flagmult(tio, yield, update_index_by, lt1, smallerchild - parent);});
- run_coroutines(tio,
- [&tio, &HeapArray, &update_index_by, index](yield_t &yield) {
- auto HeapArraycoro = HeapArray.context(yield);
- HeapArraycoro[index] += update_index_by;
- },
- [&tio, &HeapArray, &update_leftindex_by, leftchildindex](yield_t &yield) {
- auto HeapArraycoro = HeapArray.context(yield);
- HeapArraycoro[leftchildindex] += update_leftindex_by;
- },
- [&tio, &HeapArray, &update_index_by, &update_leftindex_by, rightchildindex](yield_t &yield) {
- auto HeapArraycoro = HeapArray.context(yield);
- HeapArraycoro[rightchildindex] += -(update_index_by + update_leftindex_by);
- });
- #ifdef HEAP_VERBOSE
- RegAS new_parent = HeapArray[index];
- RegAS new_left = HeapArray[leftchildindex];
- RegAS new_right = HeapArray[rightchildindex];
- uint64_t parent_R = mpc_reconstruct(tio, yield, new_parent);
- uint64_t left_R = mpc_reconstruct(tio, yield, new_left);
- uint64_t right_R = mpc_reconstruct(tio, yield, new_right);
- std::cout << "parent_R = " << parent_R << std::endl;
- std::cout << "left_R = " << left_R << std::endl;
- std::cout << "right_R = " << right_R << std::endl;
- #endif
- #ifdef HEAP_DEBUG
- verify_parent_children_heaps(tio, yield, HeapArray[index], HeapArray[leftchildindex] , HeapArray[rightchildindex]);
- #endif
- return {smallerindex, gteq};
- }
- RegAS MinHeap::extract_min(MPCTIO &tio, yield_t & yield, int is_optimized) {
- size_t height = std::log2(num_items);
- RegAS minval;
- auto HeapArray = oram.flat(tio, yield);
- minval = HeapArray[1];
- HeapArray[1] = RegAS(HeapArray[num_items]);
- RegAS v;
- v.ashare = 0x7fffffffffffffff * !tio.player();
- HeapArray[num_items] = v;
- num_items--;
-
- if (num_items == 0) {
- return minval;
- }
- auto outroot = restore_heap_property_at_explicit_index(tio, yield);
- RegXS smaller = outroot.first;
- if(is_optimized > 0) {
- typename Duoram < RegAS > ::template OblivIndex < RegXS, 3 > oidx(tio, yield, height);
- oidx.incr(outroot.second);
- for (size_t i = 0; i < height-1; ++i) {
- auto out = restore_heap_property_optimized(tio, yield, smaller, i + 1, oidx);
- smaller = out.first;
- oidx.incr(out.second);
- }
- }
- if(is_optimized == 0) {
- for (size_t i = 0; i < height - 1; ++i) {
- smaller = restore_heap_property(tio, yield, smaller);
- }
- }
- return minval;
- }
- void Heap(MPCIO & mpcio, const PRACOptions & opts, char ** args) {
- MPCTIO tio(mpcio, 0, opts.num_cpu_threads);
- int nargs = 0;
- while (args[nargs] != nullptr) {
- ++nargs;
- }
- int maxdepth = 0;
- int heapdepth = 0;
- size_t n_inserts = 0;
- size_t n_extracts = 0;
- int is_optimized = 0;
- int run_sanity = 0;
- for (int i = 0; i < nargs; i += 2) {
- std::string option = args[i];
- if (option == "-m" && i + 1 < nargs) {
- maxdepth = std::atoi(args[i + 1]);
- } else if (option == "-d" && i + 1 < nargs) {
- heapdepth = 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_extracts = std::atoi(args[i + 1]);
- } else if (option == "-opt" && i + 1 < nargs) {
- is_optimized = std::atoi(args[i + 1]);
- } else if (option == "-s" && i + 1 < nargs) {
- run_sanity = std::atoi(args[i + 1]);
- }
- }
- run_coroutines(tio, [ & tio, maxdepth, heapdepth, n_inserts, n_extracts, is_optimized, run_sanity, &mpcio](yield_t & yield) {
- size_t size = size_t(1) << maxdepth;
- MinHeap tree(tio.player(), size);
-
-
- tree.init(tio, yield, (size_t(1) << heapdepth) - 1);
- std::cout << "\n===== Init Stats =====\n";
- tio.sync_lamport();
- mpcio.dump_stats(std::cout);
- mpcio.reset_stats();
- tio.reset_lamport();
- for (size_t j = 0; j < n_inserts; ++j) {
- RegAS inserted_val;
- inserted_val.randomize(8);
- #ifdef HEAP_VERBOSE
- inserted_val.ashare = inserted_val.ashare;
- uint64_t inserted_val_rec = mpc_reconstruct(tio, yield, inserted_val);
- std::cout << "inserted_val_rec = " << inserted_val_rec << std::endl << std::endl;
- #endif
- if(is_optimized > 0) tree.insert_optimized(tio, yield, inserted_val);
- if(is_optimized == 0) tree.insert(tio, yield, inserted_val);
- }
- std::cout << "\n===== Insert Stats =====\n";
- tio.sync_lamport();
- mpcio.dump_stats(std::cout);
- if(run_sanity == 1 && n_inserts != 0) tree.verify_heap_property(tio, yield);
- mpcio.reset_stats();
- tio.reset_lamport();
- #ifdef HEAP_VERBOSE
- tree.print_heap(tio, yield);
- #endif
- bool have_lastextract = false;
- uint64_t lastextract = 0;
- for (size_t j = 0; j < n_extracts; ++j) {
- if(run_sanity == 1) {
- RegAS minval = tree.extract_min(tio, yield, is_optimized);
- uint64_t minval_reconstruction = mpc_reconstruct(tio, yield, minval);
- std::cout << "minval_reconstruction = " << minval_reconstruction << std::endl;
- if (have_lastextract) {
- assert(minval_reconstruction >= lastextract);
- }
- lastextract = minval_reconstruction;
- have_lastextract = true;
- } else {
- tree.extract_min(tio, yield, is_optimized);
- }
- if (run_sanity == 1) {
- tree.verify_heap_property(tio, yield);
- }
- #ifdef HEAP_VERBOSE
- tree.print_heap(tio, yield);
- #endif
- }
- std::cout << "\n===== Extract Min Stats =====\n";
- tio.sync_lamport();
- mpcio.dump_stats(std::cout);
- #ifdef HEAP_VERBOSE
- tree.print_heap(tio, yield);
- #endif
- if(run_sanity == 1 && n_extracts != 0) tree.verify_heap_property(tio, yield);
- }
- );
- }
|