From 4d9e83c2e00a1fc8aa7a1e8b367a21f731013c65 Mon Sep 17 00:00:00 2001 From: Vitaly Buka Date: Wed, 9 May 2018 20:42:11 +0000 Subject: [sanitizer] Cleanup sorting functions git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@331915 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/asan/asan_memory_profile.cc | 8 ++++---- lib/lsan/lsan_common.cc | 2 +- .../sanitizer_allocator_secondary.h | 2 +- lib/sanitizer_common/sanitizer_common.cc | 13 ------------ lib/sanitizer_common/sanitizer_common.h | 23 ++++++++++++---------- .../sanitizer_common_interceptors_ioctl.inc | 2 +- .../sanitizer_coverage_libcdep_new.cc | 2 +- .../sanitizer_interceptors_ioctl_netbsd.inc | 2 +- lib/sanitizer_common/sanitizer_mac.cc | 2 +- lib/sanitizer_common/sanitizer_stackdepot.cc | 2 +- .../tests/sanitizer_common_test.cc | 12 +++++------ 11 files changed, 30 insertions(+), 40 deletions(-) (limited to 'lib') diff --git a/lib/asan/asan_memory_profile.cc b/lib/asan/asan_memory_profile.cc index 600db8c48..8c86d9fe4 100644 --- a/lib/asan/asan_memory_profile.cc +++ b/lib/asan/asan_memory_profile.cc @@ -49,10 +49,10 @@ class HeapProfile { } void Print(uptr top_percent, uptr max_number_of_contexts) { - InternalSort(&allocations_, allocations_.size(), - [](const AllocationSite &a, const AllocationSite &b) { - return a.total_size > b.total_size; - }); + Sort(allocations_.data(), allocations_.size(), + [](const AllocationSite &a, const AllocationSite &b) { + return a.total_size > b.total_size; + }); CHECK(total_allocated_user_size_); uptr total_shown = 0; Printf("Live Heap Allocations: %zd bytes in %zd chunks; quarantined: " diff --git a/lib/lsan/lsan_common.cc b/lib/lsan/lsan_common.cc index 12ea8c2bb..bdc825d76 100644 --- a/lib/lsan/lsan_common.cc +++ b/lib/lsan/lsan_common.cc @@ -685,7 +685,7 @@ void LeakReport::ReportTopLeaks(uptr num_leaks_to_report) { uptr unsuppressed_count = UnsuppressedLeakCount(); if (num_leaks_to_report > 0 && num_leaks_to_report < unsuppressed_count) Printf("The %zu top leak(s):\n", num_leaks_to_report); - InternalSort(&leaks_, leaks_.size(), LeakComparator); + Sort(leaks_.data(), leaks_.size(), &LeakComparator); uptr leaks_reported = 0; for (uptr i = 0; i < leaks_.size(); i++) { if (leaks_[i].is_suppressed) continue; diff --git a/lib/sanitizer_common/sanitizer_allocator_secondary.h b/lib/sanitizer_common/sanitizer_allocator_secondary.h index a67d70dcc..db52bf565 100644 --- a/lib/sanitizer_common/sanitizer_allocator_secondary.h +++ b/lib/sanitizer_common/sanitizer_allocator_secondary.h @@ -202,7 +202,7 @@ class LargeMmapAllocator { void EnsureSortedChunks() { if (chunks_sorted_) return; - SortArray(reinterpret_cast(chunks_), n_chunks_); + Sort(reinterpret_cast(chunks_), n_chunks_); for (uptr i = 0; i < n_chunks_; i++) chunks_[i]->chunk_idx = i; chunks_sorted_ = true; diff --git a/lib/sanitizer_common/sanitizer_common.cc b/lib/sanitizer_common/sanitizer_common.cc index 5cd63d410..7d72b0cfe 100644 --- a/lib/sanitizer_common/sanitizer_common.cc +++ b/lib/sanitizer_common/sanitizer_common.cc @@ -58,19 +58,6 @@ void NORETURN ReportMmapFailureAndDie(uptr size, const char *mem_type, typedef bool UptrComparisonFunction(const uptr &a, const uptr &b); typedef bool U32ComparisonFunction(const u32 &a, const u32 &b); -template -static inline bool CompareLess(const T &a, const T &b) { - return a < b; -} - -void SortArray(uptr *array, uptr size) { - InternalSort(&array, size, CompareLess); -} - -void SortArray(u32 *array, uptr size) { - InternalSort(&array, size, CompareLess); -} - const char *StripPathPrefix(const char *filepath, const char *strip_path_prefix) { if (!filepath) return nullptr; diff --git a/lib/sanitizer_common/sanitizer_common.h b/lib/sanitizer_common/sanitizer_common.h index 39f9414fa..81336d22f 100644 --- a/lib/sanitizer_common/sanitizer_common.h +++ b/lib/sanitizer_common/sanitizer_common.h @@ -243,8 +243,6 @@ void SleepForMillis(int millis); u64 NanoTime(); u64 MonotonicNanoTime(); int Atexit(void (*function)(void)); -void SortArray(uptr *array, uptr size); -void SortArray(u32 *array, uptr size); bool TemplateMatch(const char *templ, const char *str); // Exit @@ -572,9 +570,14 @@ class InternalScopedString : public InternalMmapVector { uptr length_; }; +template +struct CompareLess { + bool operator()(const T &a, const T &b) const { return a < b; } +}; + // HeapSort for arrays and InternalMmapVector. -template -void InternalSort(Container *v, uptr size, Compare comp) { +template > +void Sort(T *v, uptr size, Compare comp = {}) { if (size < 2) return; // Stage 1: insert elements to the heap. @@ -582,8 +585,8 @@ void InternalSort(Container *v, uptr size, Compare comp) { uptr j, p; for (j = i; j > 0; j = p) { p = (j - 1) / 2; - if (comp((*v)[p], (*v)[j])) - Swap((*v)[j], (*v)[p]); + if (comp(v[p], v[j])) + Swap(v[j], v[p]); else break; } @@ -591,18 +594,18 @@ void InternalSort(Container *v, uptr size, Compare comp) { // Stage 2: swap largest element with the last one, // and sink the new top. for (uptr i = size - 1; i > 0; i--) { - Swap((*v)[0], (*v)[i]); + Swap(v[0], v[i]); uptr j, max_ind; for (j = 0; j < i; j = max_ind) { uptr left = 2 * j + 1; uptr right = 2 * j + 2; max_ind = j; - if (left < i && comp((*v)[max_ind], (*v)[left])) + if (left < i && comp(v[max_ind], v[left])) max_ind = left; - if (right < i && comp((*v)[max_ind], (*v)[right])) + if (right < i && comp(v[max_ind], v[right])) max_ind = right; if (max_ind != j) - Swap((*v)[j], (*v)[max_ind]); + Swap(v[j], v[max_ind]); else break; } diff --git a/lib/sanitizer_common/sanitizer_common_interceptors_ioctl.inc b/lib/sanitizer_common/sanitizer_common_interceptors_ioctl.inc index b6bf4638c..2d633c173 100644 --- a/lib/sanitizer_common/sanitizer_common_interceptors_ioctl.inc +++ b/lib/sanitizer_common/sanitizer_common_interceptors_ioctl.inc @@ -480,7 +480,7 @@ struct ioctl_desc_compare { static void ioctl_init() { ioctl_table_fill(); - InternalSort(&ioctl_table, ioctl_table_size, ioctl_desc_compare()); + Sort(ioctl_table, ioctl_table_size, ioctl_desc_compare()); bool bad = false; for (unsigned i = 0; i < ioctl_table_size - 1; ++i) { diff --git a/lib/sanitizer_common/sanitizer_coverage_libcdep_new.cc b/lib/sanitizer_common/sanitizer_coverage_libcdep_new.cc index 8a41d235c..bea277587 100644 --- a/lib/sanitizer_common/sanitizer_coverage_libcdep_new.cc +++ b/lib/sanitizer_common/sanitizer_coverage_libcdep_new.cc @@ -63,7 +63,7 @@ static void SanitizerDumpCoverage(const uptr* unsorted_pcs, uptr len) { uptr* pcs = static_cast(InternalAlloc(len * sizeof(uptr))); internal_memcpy(pcs, unsorted_pcs, len * sizeof(uptr)); - SortArray(pcs, len); + Sort(pcs, len); bool module_found = false; uptr last_base = 0; diff --git a/lib/sanitizer_common/sanitizer_interceptors_ioctl_netbsd.inc b/lib/sanitizer_common/sanitizer_interceptors_ioctl_netbsd.inc index f07694018..9a2a9f120 100644 --- a/lib/sanitizer_common/sanitizer_interceptors_ioctl_netbsd.inc +++ b/lib/sanitizer_common/sanitizer_interceptors_ioctl_netbsd.inc @@ -1372,7 +1372,7 @@ struct ioctl_desc_compare { static void ioctl_init() { ioctl_table_fill(); - InternalSort(&ioctl_table, ioctl_table_size, ioctl_desc_compare()); + Sort(ioctl_table, ioctl_table_size, ioctl_desc_compare()); bool bad = false; for (unsigned i = 0; i < ioctl_table_size - 1; ++i) { diff --git a/lib/sanitizer_common/sanitizer_mac.cc b/lib/sanitizer_common/sanitizer_mac.cc index 858d69839..b0376a470 100644 --- a/lib/sanitizer_common/sanitizer_mac.cc +++ b/lib/sanitizer_common/sanitizer_mac.cc @@ -1035,7 +1035,7 @@ void PrintModuleMap() { InternalMmapVector modules; modules.reserve(128); memory_mapping.DumpListOfModules(&modules); - InternalSort(&modules, modules.size(), CompareBaseAddress); + Sort(modules.data(), modules.size(), CompareBaseAddress); for (uptr i = 0; i < modules.size(); ++i) { char uuid_str[128]; FormatUUID(uuid_str, sizeof(uuid_str), modules[i].uuid()); diff --git a/lib/sanitizer_common/sanitizer_stackdepot.cc b/lib/sanitizer_common/sanitizer_stackdepot.cc index dc75729ed..3bd5b677a 100644 --- a/lib/sanitizer_common/sanitizer_stackdepot.cc +++ b/lib/sanitizer_common/sanitizer_stackdepot.cc @@ -146,7 +146,7 @@ StackDepotReverseMap::StackDepotReverseMap() { map_.push_back(pair); } } - InternalSort(&map_, map_.size(), IdDescPair::IdComparator); + Sort(map_.data(), map_.size(), &IdDescPair::IdComparator); } StackTrace StackDepotReverseMap::Get(u32 id) { diff --git a/lib/sanitizer_common/tests/sanitizer_common_test.cc b/lib/sanitizer_common/tests/sanitizer_common_test.cc index 02fecddbc..6e5bb5b68 100644 --- a/lib/sanitizer_common/tests/sanitizer_common_test.cc +++ b/lib/sanitizer_common/tests/sanitizer_common_test.cc @@ -39,37 +39,37 @@ TEST(SanitizerCommon, SortTest) { for (uptr i = 0; i < n; i++) { array[i] = i; } - SortArray(array, n); + Sort(array, n); EXPECT_TRUE(IsSorted(array, n)); // Reverse order. for (uptr i = 0; i < n; i++) { array[i] = n - 1 - i; } - SortArray(array, n); + Sort(array, n); EXPECT_TRUE(IsSorted(array, n)); // Mixed order. for (uptr i = 0; i < n; i++) { array[i] = (i % 2 == 0) ? i : n - 1 - i; } - SortArray(array, n); + Sort(array, n); EXPECT_TRUE(IsSorted(array, n)); // All equal. for (uptr i = 0; i < n; i++) { array[i] = 42; } - SortArray(array, n); + Sort(array, n); EXPECT_TRUE(IsSorted(array, n)); // All but one sorted. for (uptr i = 0; i < n - 1; i++) { array[i] = i; } array[n - 1] = 42; - SortArray(array, n); + Sort(array, n); EXPECT_TRUE(IsSorted(array, n)); // Minimal case - sort three elements. array[0] = 1; array[1] = 0; - SortArray(array, 2); + Sort(array, 2); EXPECT_TRUE(IsSorted(array, 2)); } -- cgit v1.2.3