From 21822b9cfb88284c4d8d7cace7ac74a7356612ec Mon Sep 17 00:00:00 2001 From: Arnaud Giersch Date: Tue, 24 Nov 2020 17:30:28 +0100 Subject: [PATCH] Use std algorithms for binary search. --- src/mc/compare.cpp | 20 ++---- src/mc/inspect/ObjectInformation.cpp | 68 ++++-------------- src/mc/remote/RemoteSimulation.cpp | 101 +++++---------------------- 3 files changed, 35 insertions(+), 154 deletions(-) diff --git a/src/mc/compare.cpp b/src/mc/compare.cpp index 4a0f4191b2..d72827bdc9 100644 --- a/src/mc/compare.cpp +++ b/src/mc/compare.cpp @@ -10,6 +10,8 @@ #include "src/mc/mc_smx.hpp" #include "src/mc/sosp/Snapshot.hpp" +#include + XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_compare, xbt, "Logging specific to mc_compare in mc"); using simgrid::mc::remote; @@ -134,21 +136,9 @@ public: static ssize_t heap_comparison_ignore_size(const std::vector* ignore_list, const void* address) { - int start = 0; - int end = ignore_list->size() - 1; - - while (start <= end) { - unsigned int cursor = (start + end) / 2; - simgrid::mc::IgnoredHeapRegion const& region = (*ignore_list)[cursor]; - if (region.address == address) - return region.size; - if (region.address < address) - start = cursor + 1; - if (region.address > address) - end = cursor - 1; - } - - return -1; + auto pos = std::lower_bound(ignore_list->begin(), ignore_list->end(), address, + [](auto const& reg, const void* address) { return reg.address < address; }); + return (pos != ignore_list->end() && pos->address == address) ? pos->size : -1; } static bool is_stack(const void *address) diff --git a/src/mc/inspect/ObjectInformation.cpp b/src/mc/inspect/ObjectInformation.cpp index a1c090cb62..ce6d4db754 100644 --- a/src/mc/inspect/ObjectInformation.cpp +++ b/src/mc/inspect/ObjectInformation.cpp @@ -3,6 +3,7 @@ /* This program is free software; you can redistribute it and/or modify it * under the terms of the license (GNU LGPL) which comes with this package. */ +#include #include #include // PROT_READ and friends #include @@ -89,41 +90,14 @@ const Variable* ObjectInformation::find_variable(const char* name) const void ObjectInformation::remove_global_variable(const char* name) { - using size_type = std::vector::size_type; - - if (this->global_variables.empty()) - return; - // Binary search: - size_type first = 0; - size_type last = this->global_variables.size() - 1; - - while (first <= last) { - size_type cursor = first + (last - first) / 2; - const Variable& current_var = this->global_variables[cursor]; - int cmp = current_var.name.compare(name); - - if (cmp == 0) { - // Find the whole range: - first = cursor; - while (first != 0 && this->global_variables[first - 1].name == name) - first--; - size_type size = this->global_variables.size(); - last = cursor; - while (last != size - 1 && this->global_variables[last + 1].name == name) - last++; - - // Remove the whole range: - this->global_variables.erase(this->global_variables.begin() + first, this->global_variables.begin() + last + 1); - - return; - } else if (cmp < 0) - first = cursor + 1; - else if (cursor != 0) - last = cursor - 1; - else - break; - } + auto pos1 = std::lower_bound(this->global_variables.begin(), this->global_variables.end(), name, + [](auto const& var, const char* var_name) { return var.name.compare(var_name) < 0; }); + // Find the whole range: + auto pos2 = std::upper_bound(pos1, this->global_variables.end(), name, + [](const char* var_name, auto const& var) { return var.name.compare(var_name) > 0; }); + // Remove the whole range: + this->global_variables.erase(pos1, pos2); } /** Ignore a local variable in a scope @@ -139,30 +113,16 @@ void ObjectInformation::remove_global_variable(const char* name) static void remove_local_variable(Frame& scope, const char* var_name, const char* subprogram_name, Frame const& subprogram) { - using size_type = std::vector::size_type; - // If the current subprogram matches the given name: - if ((subprogram_name == nullptr || (not subprogram.name.empty() && subprogram.name == subprogram_name)) && - not scope.variables.empty()) { + if (subprogram_name == nullptr || (not subprogram.name.empty() && subprogram.name == subprogram_name)) { // Try to find the variable and remove it: - size_type start = 0; - size_type end = scope.variables.size() - 1; // Binary search: - while (start <= end) { - size_type cursor = start + (end - start) / 2; - const Variable& current_var = scope.variables[cursor]; - int compare = current_var.name.compare(var_name); - if (compare == 0) { - // Variable found, remove it: - scope.variables.erase(scope.variables.begin() + cursor); - break; - } else if (compare < 0) - start = cursor + 1; - else if (cursor != 0) - end = cursor - 1; - else - break; + auto pos = std::lower_bound(scope.variables.begin(), scope.variables.end(), var_name, + [](auto const& var, const char* var_name) { return var.name.compare(var_name) < 0; }); + if (pos != scope.variables.end() && pos->name.compare(var_name) == 0) { + // Variable found, remove it: + scope.variables.erase(pos); } } diff --git a/src/mc/remote/RemoteSimulation.cpp b/src/mc/remote/RemoteSimulation.cpp index 75895f150d..f50f60f4f8 100644 --- a/src/mc/remote/RemoteSimulation.cpp +++ b/src/mc/remote/RemoteSimulation.cpp @@ -16,6 +16,7 @@ #include #include // PROT_* +#include #include #include @@ -480,102 +481,32 @@ void RemoteSimulation::ignore_region(std::uint64_t addr, std::size_t size) region.addr = addr; region.size = size; - if (ignored_regions_.empty()) { - ignored_regions_.push_back(region); - return; - } - - unsigned int cursor = 0; - const IgnoredRegion* current_region = nullptr; - - int start = 0; - int end = ignored_regions_.size() - 1; - while (start <= end) { - cursor = (start + end) / 2; - current_region = &ignored_regions_[cursor]; - if (current_region->addr == addr) { - if (current_region->size == size) - return; - else if (current_region->size < size) - start = cursor + 1; - else - end = cursor - 1; - } else if (current_region->addr < addr) - start = cursor + 1; - else - end = cursor - 1; - } - - std::size_t position; - if (current_region->addr == addr) { - if (current_region->size < size) - position = cursor + 1; - else - position = cursor; - } else if (current_region->addr < addr) - position = cursor + 1; - else - position = cursor; - ignored_regions_.insert(ignored_regions_.begin() + position, region); + auto pos = std::lower_bound(ignored_regions_.begin(), ignored_regions_.end(), region, + [](auto const& reg1, auto const& reg2) { + return reg1.addr < reg2.addr || (reg1.addr == reg2.addr && reg1.size < reg2.size); + }); + if (pos == ignored_regions_.end() || pos->addr != addr || pos->size != size) + ignored_regions_.insert(pos, region); } void RemoteSimulation::ignore_heap(IgnoredHeapRegion const& region) { - if (ignored_heap_.empty()) { - ignored_heap_.push_back(region); - return; - } - - using size_type = std::vector::size_type; - - size_type start = 0; - size_type end = ignored_heap_.size() - 1; - // Binary search the position of insertion: - size_type cursor; - while (start <= end) { - cursor = start + (end - start) / 2; - auto const& current_region = ignored_heap_[cursor]; - if (current_region.address == region.address) - return; - else if (current_region.address < region.address) - start = cursor + 1; - else if (cursor != 0) - end = cursor - 1; - // Avoid underflow: - else - break; + auto pos = std::lower_bound(ignored_heap_.begin(), ignored_heap_.end(), region.address, + [](auto const& reg, const void* address) { return reg.address < address; }); + if (pos == ignored_heap_.end() || pos->address != region.address) { + // Insert it: + ignored_heap_.insert(pos, region); } - - // Insert it mc_heap_ignore_region_t: - if (ignored_heap_[cursor].address < region.address) - ++cursor; - ignored_heap_.insert(ignored_heap_.begin() + cursor, region); } void RemoteSimulation::unignore_heap(void* address, size_t size) { - using size_type = std::vector::size_type; - - size_type start = 0; - size_type end = ignored_heap_.size() - 1; - // Binary search: - size_type cursor; - while (start <= end) { - cursor = (start + end) / 2; - auto const& region = ignored_heap_[cursor]; - if (region.address < address) - start = cursor + 1; - else if ((char*)region.address <= ((char*)address + size)) { - ignored_heap_.erase(ignored_heap_.begin() + cursor); - return; - } else if (cursor != 0) - end = cursor - 1; - // Avoid underflow: - else - break; - } + auto pos = std::lower_bound(ignored_heap_.begin(), ignored_heap_.end(), address, + [](auto const& reg, const void* address) { return reg.address < address; }); + if (pos != ignored_heap_.end() && static_cast(pos->address) <= static_cast(address) + size) + ignored_heap_.erase(pos); } void RemoteSimulation::ignore_local_variable(const char* var_name, const char* frame_name) const -- 2.20.1