From 5c9f12580ae4e515ef48d0891c7d85a3d7eb2b04 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Sun, 30 Dec 2012 23:05:27 +0100 Subject: [PATCH] Scrapping as much as possible from the heap operations. Gained ~10% for tracking time! --- mtp_graph.cc | 44 ++++++++++++++++++++++++-------------------- 1 file changed, 24 insertions(+), 20 deletions(-) diff --git a/mtp_graph.cc b/mtp_graph.cc index c17917e..5b42781 100644 --- a/mtp_graph.cc +++ b/mtp_graph.cc @@ -97,36 +97,40 @@ void Vertex::del_leaving_edge(Edge *e) { void Vertex::decrease_distance_in_heap(Vertex **heap) { Vertex **p, **h; - // There is some beauty in that h = heap_slot; - while(h > heap && - (p = heap + (h - heap + 1) / 2 - 1, - (*p)->distance_from_source > (*h)->distance_from_source)) { + while(1) { + if(h <= heap) break; + p = heap + ((h - heap + 1) >> 1) - 1; + if((*p)->distance_from_source <= distance_from_source) break; + swap((*p)->heap_slot, heap_slot); swap(*p, *h); - swap((*p)->heap_slot, (*h)->heap_slot); h = p; } } void Vertex::increase_distance_in_heap(Vertex **heap, Vertex **heap_bottom) { Vertex **c1, **c2, **h; - // omg, that's beautiful h = heap_slot; - while(c1 = heap + 2 * (h - heap) + 1, - c1 < heap_bottom && - (c2 = c1 + 1, - (*c1)->distance_from_source < (*h)->distance_from_source - || - (c2 < heap_bottom && (*c2)->distance_from_source < (*h)->distance_from_source) - )) { - if(c2 < heap_bottom && (*c2)->distance_from_source <= (*c1)->distance_from_source) { - swap(*c2, *h); - swap((*c2)->heap_slot, (*h)->heap_slot); - h = c2; + while(1) { + c1 = heap + 2 * (h - heap) + 1; + if(c1 >= heap_bottom) break; + c2 = c1 + 1; + if((*c1)->distance_from_source < distance_from_source) { + if(c2 < heap_bottom && (*c2)->distance_from_source < (*c1)->distance_from_source) { + swap((*c2)->heap_slot, heap_slot); + swap(*c2, *h); + h = c2; + } else { + swap((*c1)->heap_slot, heap_slot); + swap(*c1, *h); + h = c1; + } } else { - swap(*c1, *h); - swap((*c1)->heap_slot, (*h)->heap_slot); - h = c1; + if(c2 < heap_bottom && (*c2)->distance_from_source < distance_from_source) { + swap((*c2)->heap_slot, heap_slot); + swap(*c2, *h); + h = c2; + } else break; } } } -- 2.39.5