michael@0: // Copyright (c) 2006-2008 The Chromium Authors. All rights reserved.
michael@0: // Use of this source code is governed by a BSD-style license that can be
michael@0: // found in the LICENSE file.
michael@0: 
michael@0: #include "base/tracked_objects.h"
michael@0: 
michael@0: #include <math.h>
michael@0: 
michael@0: #include "base/string_util.h"
michael@0: 
michael@0: using base::TimeDelta;
michael@0: 
michael@0: namespace tracked_objects {
michael@0: 
michael@0: // A TLS slot to the TrackRegistry for the current thread.
michael@0: // static
michael@0: TLSSlot ThreadData::tls_index_(base::LINKER_INITIALIZED);
michael@0: 
michael@0: //------------------------------------------------------------------------------
michael@0: // Death data tallies durations when a death takes place.
michael@0: 
michael@0: void DeathData::RecordDeath(const TimeDelta& duration) {
michael@0:   ++count_;
michael@0:   life_duration_ += duration;
michael@0:   int64_t milliseconds = duration.InMilliseconds();
michael@0:   square_duration_ += milliseconds * milliseconds;
michael@0: }
michael@0: 
michael@0: int DeathData::AverageMsDuration() const {
michael@0:   return static_cast<int>(life_duration_.InMilliseconds() / count_);
michael@0: }
michael@0: 
michael@0: double DeathData::StandardDeviation() const {
michael@0:   double average = AverageMsDuration();
michael@0:   double variance = static_cast<float>(square_duration_)/count_
michael@0:                     - average * average;
michael@0:   return sqrt(variance);
michael@0: }
michael@0: 
michael@0: 
michael@0: void DeathData::AddDeathData(const DeathData& other) {
michael@0:   count_ += other.count_;
michael@0:   life_duration_ += other.life_duration_;
michael@0:   square_duration_ += other.square_duration_;
michael@0: }
michael@0: 
michael@0: void DeathData::Write(std::string* output) const {
michael@0:   if (!count_)
michael@0:     return;
michael@0:   if (1 == count_)
michael@0:     StringAppendF(output, "(1)Life in %dms ", AverageMsDuration());
michael@0:   else
michael@0:     StringAppendF(output, "(%d)Lives %dms/life ", count_, AverageMsDuration());
michael@0: }
michael@0: 
michael@0: void DeathData::Clear() {
michael@0:   count_ = 0;
michael@0:   life_duration_ = TimeDelta();
michael@0:   square_duration_ = 0;
michael@0: }
michael@0: 
michael@0: //------------------------------------------------------------------------------
michael@0: 
michael@0: BirthOnThread::BirthOnThread(const Location& location)
michael@0:     : location_(location),
michael@0:       birth_thread_(ThreadData::current()) { }
michael@0: 
michael@0: //------------------------------------------------------------------------------
michael@0: Births::Births(const Location& location)
michael@0:     : BirthOnThread(location),
michael@0:       birth_count_(0) { }
michael@0: 
michael@0: //------------------------------------------------------------------------------
michael@0: // ThreadData maintains the central data for all births and death.
michael@0: 
michael@0: // static
michael@0: ThreadData* ThreadData::first_ = NULL;
michael@0: // static
michael@0: Lock ThreadData::list_lock_;
michael@0: 
michael@0: // static
michael@0: ThreadData::Status ThreadData::status_ = ThreadData::UNINITIALIZED;
michael@0: 
michael@0: ThreadData::ThreadData() : next_(NULL), message_loop_(MessageLoop::current()) {}
michael@0: 
michael@0: // static
michael@0: ThreadData* ThreadData::current() {
michael@0:   if (!tls_index_.initialized())
michael@0:     return NULL;
michael@0: 
michael@0:   ThreadData* registry = static_cast<ThreadData*>(tls_index_.Get());
michael@0:   if (!registry) {
michael@0:     // We have to create a new registry for ThreadData.
michael@0:     bool too_late_to_create = false;
michael@0:     {
michael@0:       registry = new ThreadData;
michael@0:       AutoLock lock(list_lock_);
michael@0:       // Use lock to insure we have most recent status.
michael@0:       if (!IsActive()) {
michael@0:         too_late_to_create = true;
michael@0:       } else {
michael@0:         // Use lock to insert into list.
michael@0:         registry->next_ = first_;
michael@0:         first_ = registry;
michael@0:       }
michael@0:     }  // Release lock.
michael@0:     if (too_late_to_create) {
michael@0:       delete registry;
michael@0:       registry = NULL;
michael@0:     } else {
michael@0:       tls_index_.Set(registry);
michael@0:     }
michael@0:   }
michael@0:   return registry;
michael@0: }
michael@0: 
michael@0: Births* ThreadData::FindLifetime(const Location& location) {
michael@0:   if (!message_loop_)  // In case message loop wasn't yet around...
michael@0:     message_loop_ = MessageLoop::current();  // Find it now.
michael@0: 
michael@0:   BirthMap::iterator it = birth_map_.find(location);
michael@0:   if (it != birth_map_.end())
michael@0:     return it->second;
michael@0:   Births* tracker = new Births(location);
michael@0: 
michael@0:   // Lock since the map may get relocated now, and other threads sometimes
michael@0:   // snapshot it (but they lock before copying it).
michael@0:   AutoLock lock(lock_);
michael@0:   birth_map_[location] = tracker;
michael@0:   return tracker;
michael@0: }
michael@0: 
michael@0: void ThreadData::TallyADeath(const Births& lifetimes,
michael@0:                              const TimeDelta& duration) {
michael@0:   if (!message_loop_)  // In case message loop wasn't yet around...
michael@0:     message_loop_ = MessageLoop::current();  // Find it now.
michael@0: 
michael@0:   DeathMap::iterator it = death_map_.find(&lifetimes);
michael@0:   if (it != death_map_.end()) {
michael@0:     it->second.RecordDeath(duration);
michael@0:     return;
michael@0:   }
michael@0: 
michael@0:   AutoLock lock(lock_);  // Lock since the map may get relocated now.
michael@0:   death_map_[&lifetimes].RecordDeath(duration);
michael@0: }
michael@0: 
michael@0: // static
michael@0: ThreadData* ThreadData::first() {
michael@0:   AutoLock lock(list_lock_);
michael@0:   return first_;
michael@0: }
michael@0: 
michael@0: const std::string ThreadData::ThreadName() const {
michael@0:   if (message_loop_)
michael@0:     return message_loop_->thread_name();
michael@0:   return "ThreadWithoutMessageLoop";
michael@0: }
michael@0: 
michael@0: // This may be called from another thread.
michael@0: void ThreadData::SnapshotBirthMap(BirthMap *output) const {
michael@0:   AutoLock lock(*const_cast<Lock*>(&lock_));
michael@0:   for (BirthMap::const_iterator it = birth_map_.begin();
michael@0:        it != birth_map_.end(); ++it)
michael@0:     (*output)[it->first] = it->second;
michael@0: }
michael@0: 
michael@0: // This may be called from another thread.
michael@0: void ThreadData::SnapshotDeathMap(DeathMap *output) const {
michael@0:   AutoLock lock(*const_cast<Lock*>(&lock_));
michael@0:   for (DeathMap::const_iterator it = death_map_.begin();
michael@0:        it != death_map_.end(); ++it)
michael@0:     (*output)[it->first] = it->second;
michael@0: }
michael@0: 
michael@0: #ifdef OS_WIN
michael@0: void ThreadData::RunOnAllThreads(void (*function)()) {
michael@0:   ThreadData* list = first();  // Get existing list.
michael@0: 
michael@0:   std::vector<MessageLoop*> message_loops;
michael@0:   for (ThreadData* it = list; it; it = it->next()) {
michael@0:     if (current() != it && it->message_loop())
michael@0:       message_loops.push_back(it->message_loop());
michael@0:   }
michael@0: 
michael@0:   ThreadSafeDownCounter* counter =
michael@0:     new ThreadSafeDownCounter(message_loops.size() + 1);  // Extra one for us!
michael@0: 
michael@0:   HANDLE completion_handle = CreateEvent(NULL, false, false, NULL);
michael@0:   // Tell all other threads to run.
michael@0:   for (size_t i = 0; i < message_loops.size(); ++i)
michael@0:     message_loops[i]->PostTask(FROM_HERE,
michael@0:         new RunTheStatic(function, completion_handle, counter));
michael@0: 
michael@0:   // Also run Task on our thread.
michael@0:   RunTheStatic local_task(function, completion_handle, counter);
michael@0:   local_task.Run();
michael@0: 
michael@0:   WaitForSingleObject(completion_handle, INFINITE);
michael@0:   int ret_val = CloseHandle(completion_handle);
michael@0:   DCHECK(ret_val);
michael@0: }
michael@0: #endif
michael@0: 
michael@0: // static
michael@0: bool ThreadData::StartTracking(bool status) {
michael@0: #ifndef TRACK_ALL_TASK_OBJECTS
michael@0:   return false;  // Not compiled in.
michael@0: #else
michael@0:   if (!status) {
michael@0:     AutoLock lock(list_lock_);
michael@0:     DCHECK(status_ == ACTIVE || status_ == SHUTDOWN);
michael@0:     status_ = SHUTDOWN;
michael@0:     return true;
michael@0:   }
michael@0:   AutoLock lock(list_lock_);
michael@0:   DCHECK(status_ == UNINITIALIZED);
michael@0:   CHECK(tls_index_.Initialize(NULL));
michael@0:   status_ = ACTIVE;
michael@0:   return true;
michael@0: #endif
michael@0: }
michael@0: 
michael@0: // static
michael@0: bool ThreadData::IsActive() {
michael@0:   return status_ == ACTIVE;
michael@0: }
michael@0: 
michael@0: #ifdef OS_WIN
michael@0: // static
michael@0: void ThreadData::ShutdownMultiThreadTracking() {
michael@0:   // Using lock, guarantee that no new ThreadData instances will be created.
michael@0:   if (!StartTracking(false))
michael@0:     return;
michael@0: 
michael@0:   RunOnAllThreads(ShutdownDisablingFurtherTracking);
michael@0: 
michael@0:   // Now the *only* threads that might change the database are the threads with
michael@0:   // no messages loops.  They might still be adding data to their birth records,
michael@0:   // but since no objects are deleted on those threads, there will be no further
michael@0:   // access to to cross-thread data.
michael@0:   // We could do a cleanup on all threads except for the ones without
michael@0:   // MessageLoops, but we won't bother doing cleanup (destruction of data) yet.
michael@0:   return;
michael@0: }
michael@0: #endif
michael@0: 
michael@0: // static
michael@0: void ThreadData::ShutdownSingleThreadedCleanup() {
michael@0:   // We must be single threaded... but be careful anyway.
michael@0:   if (!StartTracking(false))
michael@0:     return;
michael@0:   ThreadData* thread_data_list;
michael@0:   {
michael@0:     AutoLock lock(list_lock_);
michael@0:     thread_data_list = first_;
michael@0:     first_ = NULL;
michael@0:   }
michael@0: 
michael@0:   while (thread_data_list) {
michael@0:     ThreadData* next_thread_data = thread_data_list;
michael@0:     thread_data_list = thread_data_list->next();
michael@0: 
michael@0:     for (BirthMap::iterator it = next_thread_data->birth_map_.begin();
michael@0:          next_thread_data->birth_map_.end() != it; ++it)
michael@0:       delete it->second;  // Delete the Birth Records.
michael@0:     next_thread_data->birth_map_.clear();
michael@0:     next_thread_data->death_map_.clear();
michael@0:     delete next_thread_data;  // Includes all Death Records.
michael@0:   }
michael@0: 
michael@0:   CHECK(tls_index_.initialized());
michael@0:   tls_index_.Free();
michael@0:   DCHECK(!tls_index_.initialized());
michael@0:   status_ = UNINITIALIZED;
michael@0: }
michael@0: 
michael@0: // static
michael@0: void ThreadData::ShutdownDisablingFurtherTracking() {
michael@0:   // Redundantly set status SHUTDOWN on this thread.
michael@0:   if (!StartTracking(false))
michael@0:     return;
michael@0: }
michael@0: 
michael@0: 
michael@0: //------------------------------------------------------------------------------
michael@0: 
michael@0: ThreadData::ThreadSafeDownCounter::ThreadSafeDownCounter(size_t count)
michael@0:     : remaining_count_(count) {
michael@0:   DCHECK(remaining_count_ > 0);
michael@0: }
michael@0: 
michael@0: bool ThreadData::ThreadSafeDownCounter::LastCaller() {
michael@0:   {
michael@0:     AutoLock lock(lock_);
michael@0:     if (--remaining_count_)
michael@0:       return false;
michael@0:   }  // Release lock, so we can delete everything in this instance.
michael@0:   delete this;
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: //------------------------------------------------------------------------------
michael@0: #ifdef OS_WIN
michael@0: ThreadData::RunTheStatic::RunTheStatic(FunctionPointer function,
michael@0:                                        HANDLE completion_handle,
michael@0:                                        ThreadSafeDownCounter* counter)
michael@0:     : function_(function),
michael@0:       completion_handle_(completion_handle),
michael@0:       counter_(counter) {
michael@0: }
michael@0: 
michael@0: void ThreadData::RunTheStatic::Run() {
michael@0:   function_();
michael@0:   if (counter_->LastCaller())
michael@0:     SetEvent(completion_handle_);
michael@0: }
michael@0: #endif
michael@0: 
michael@0: //------------------------------------------------------------------------------
michael@0: // Individual 3-tuple of birth (place and thread) along with death thread, and
michael@0: // the accumulated stats for instances (DeathData).
michael@0: 
michael@0: Snapshot::Snapshot(const BirthOnThread& birth_on_thread,
michael@0:                    const ThreadData& death_thread,
michael@0:                    const DeathData& death_data)
michael@0:     : birth_(&birth_on_thread),
michael@0:       death_thread_(&death_thread),
michael@0:       death_data_(death_data) {
michael@0: }
michael@0: 
michael@0: Snapshot::Snapshot(const BirthOnThread& birth_on_thread, int count)
michael@0:     : birth_(&birth_on_thread),
michael@0:       death_thread_(NULL),
michael@0:       death_data_(DeathData(count)) {
michael@0: }
michael@0: 
michael@0: const std::string Snapshot::DeathThreadName() const {
michael@0:   if (death_thread_)
michael@0:     return death_thread_->ThreadName();
michael@0:   return "Still_Alive";
michael@0: }
michael@0: 
michael@0: void Snapshot::Write(std::string* output) const {
michael@0:   death_data_.Write(output);
michael@0:   StringAppendF(output, "%s->%s ",
michael@0:                 birth_->birth_thread()->ThreadName().c_str(),
michael@0:                 death_thread_->ThreadName().c_str());
michael@0:   birth_->location().Write(true, true, output);
michael@0: }
michael@0: 
michael@0: void Snapshot::Add(const Snapshot& other) {
michael@0:   death_data_.AddDeathData(other.death_data_);
michael@0: }
michael@0: 
michael@0: //------------------------------------------------------------------------------
michael@0: // DataCollector
michael@0: 
michael@0: DataCollector::DataCollector() {
michael@0:   DCHECK(ThreadData::IsActive());
michael@0: 
michael@0:   ThreadData* my_list = ThreadData::current()->first();
michael@0: 
michael@0:   count_of_contributing_threads_ = 0;
michael@0:   for (ThreadData* thread_data = my_list;
michael@0:        thread_data;
michael@0:        thread_data = thread_data->next()) {
michael@0:     ++count_of_contributing_threads_;
michael@0:   }
michael@0: 
michael@0:   // Gather data serially.  A different constructor could be used to do in
michael@0:   // parallel, and then invoke an OnCompletion task.
michael@0:   for (ThreadData* thread_data = my_list;
michael@0:        thread_data;
michael@0:        thread_data = thread_data->next()) {
michael@0:     Append(*thread_data);
michael@0:   }
michael@0: }
michael@0: 
michael@0: void DataCollector::Append(const ThreadData& thread_data) {
michael@0:   // Get copy of data (which is done under ThreadData's lock).
michael@0:   ThreadData::BirthMap birth_map;
michael@0:   thread_data.SnapshotBirthMap(&birth_map);
michael@0:   ThreadData::DeathMap death_map;
michael@0:   thread_data.SnapshotDeathMap(&death_map);
michael@0: 
michael@0:   // Use our lock to protect our accumulation activity.
michael@0:   AutoLock lock(accumulation_lock_);
michael@0: 
michael@0:   DCHECK(count_of_contributing_threads_);
michael@0: 
michael@0:   for (ThreadData::DeathMap::const_iterator it = death_map.begin();
michael@0:        it != death_map.end(); ++it) {
michael@0:     collection_.push_back(Snapshot(*it->first, thread_data, it->second));
michael@0:     global_birth_count_[it->first] -= it->first->birth_count();
michael@0:   }
michael@0: 
michael@0:   for (ThreadData::BirthMap::const_iterator it = birth_map.begin();
michael@0:        it != birth_map.end(); ++it) {
michael@0:     global_birth_count_[it->second] += it->second->birth_count();
michael@0:   }
michael@0: 
michael@0:   --count_of_contributing_threads_;
michael@0: }
michael@0: 
michael@0: DataCollector::Collection* DataCollector::collection() {
michael@0:   DCHECK(!count_of_contributing_threads_);
michael@0:   return &collection_;
michael@0: }
michael@0: 
michael@0: void DataCollector::AddListOfLivingObjects() {
michael@0:   DCHECK(!count_of_contributing_threads_);
michael@0:   for (BirthCount::iterator it = global_birth_count_.begin();
michael@0:        it != global_birth_count_.end(); ++it) {
michael@0:     if (it->second > 0)
michael@0:       collection_.push_back(Snapshot(*it->first, it->second));
michael@0:   }
michael@0: }
michael@0: 
michael@0: //------------------------------------------------------------------------------
michael@0: // Aggregation
michael@0: 
michael@0: void Aggregation::AddDeathSnapshot(const Snapshot& snapshot) {
michael@0:   AddBirth(snapshot.birth());
michael@0:   death_threads_[snapshot.death_thread()]++;
michael@0:   AddDeathData(snapshot.death_data());
michael@0: }
michael@0: 
michael@0: void Aggregation::AddBirths(const Births& births) {
michael@0:   AddBirth(births);
michael@0:   birth_count_ += births.birth_count();
michael@0: }
michael@0: void Aggregation::AddBirth(const BirthOnThread& birth) {
michael@0:   AddBirthPlace(birth.location());
michael@0:   birth_threads_[birth.birth_thread()]++;
michael@0: }
michael@0: 
michael@0: void Aggregation::AddBirthPlace(const Location& location) {
michael@0:   locations_[location]++;
michael@0:   birth_files_[location.file_name()]++;
michael@0: }
michael@0: 
michael@0: void Aggregation::Write(std::string* output) const {
michael@0:   if (locations_.size() == 1) {
michael@0:     locations_.begin()->first.Write(true, true, output);
michael@0:   } else {
michael@0:     StringAppendF(output, "%d Locations. ", locations_.size());
michael@0:     if (birth_files_.size() > 1)
michael@0:       StringAppendF(output, "%d Files. ", birth_files_.size());
michael@0:     else
michael@0:       StringAppendF(output, "All born in %s. ",
michael@0:                     birth_files_.begin()->first.c_str());
michael@0:   }
michael@0: 
michael@0:   if (birth_threads_.size() > 1)
michael@0:     StringAppendF(output, "%d BirthingThreads. ", birth_threads_.size());
michael@0:   else
michael@0:     StringAppendF(output, "All born on %s. ",
michael@0:                   birth_threads_.begin()->first->ThreadName().c_str());
michael@0: 
michael@0:   if (death_threads_.size() > 1) {
michael@0:     StringAppendF(output, "%d DeathThreads. ", death_threads_.size());
michael@0:   } else {
michael@0:     if (death_threads_.begin()->first)
michael@0:       StringAppendF(output, "All deleted on %s. ",
michael@0:                   death_threads_.begin()->first->ThreadName().c_str());
michael@0:     else
michael@0:       output->append("All these objects are still alive.");
michael@0:   }
michael@0: 
michael@0:   if (birth_count_ > 1)
michael@0:     StringAppendF(output, "Births=%d ", birth_count_);
michael@0: 
michael@0:   DeathData::Write(output);
michael@0: }
michael@0: 
michael@0: void Aggregation::Clear() {
michael@0:   birth_count_ = 0;
michael@0:   birth_files_.clear();
michael@0:   locations_.clear();
michael@0:   birth_threads_.clear();
michael@0:   DeathData::Clear();
michael@0:   death_threads_.clear();
michael@0: }
michael@0: 
michael@0: //------------------------------------------------------------------------------
michael@0: // Comparison object for sorting.
michael@0: 
michael@0: Comparator::Comparator()
michael@0:     : selector_(NIL),
michael@0:       tiebreaker_(NULL),
michael@0:       combined_selectors_(0),
michael@0:       use_tiebreaker_for_sort_only_(false) {}
michael@0: 
michael@0: void Comparator::Clear() {
michael@0:   if (tiebreaker_) {
michael@0:     tiebreaker_->Clear();
michael@0:     delete tiebreaker_;
michael@0:     tiebreaker_ = NULL;
michael@0:   }
michael@0:   use_tiebreaker_for_sort_only_ = false;
michael@0:   selector_ = NIL;
michael@0: }
michael@0: 
michael@0: void Comparator::Sort(DataCollector::Collection* collection) const {
michael@0:   std::sort(collection->begin(), collection->end(), *this);
michael@0: }
michael@0: 
michael@0: 
michael@0: bool Comparator::operator()(const Snapshot& left,
michael@0:                             const Snapshot& right) const {
michael@0:   switch (selector_) {
michael@0:     case BIRTH_THREAD:
michael@0:       if (left.birth_thread() != right.birth_thread() &&
michael@0:           left.birth_thread()->ThreadName() !=
michael@0:           right.birth_thread()->ThreadName())
michael@0:         return left.birth_thread()->ThreadName() <
michael@0:             right.birth_thread()->ThreadName();
michael@0:       break;
michael@0: 
michael@0:     case DEATH_THREAD:
michael@0:       if (left.death_thread() != right.death_thread() &&
michael@0:           left.DeathThreadName() !=
michael@0:           right.DeathThreadName()) {
michael@0:         if (!left.death_thread())
michael@0:           return true;
michael@0:         if (!right.death_thread())
michael@0:           return false;
michael@0:         return left.DeathThreadName() <
michael@0:              right.DeathThreadName();
michael@0:       }
michael@0:       break;
michael@0: 
michael@0:     case BIRTH_FILE:
michael@0:       if (left.location().file_name() != right.location().file_name()) {
michael@0:         int comp = strcmp(left.location().file_name(),
michael@0:                           right.location().file_name());
michael@0:         if (comp)
michael@0:           return 0 > comp;
michael@0:       }
michael@0:       break;
michael@0: 
michael@0:     case BIRTH_FUNCTION:
michael@0:       if (left.location().function_name() != right.location().function_name()) {
michael@0:         int comp = strcmp(left.location().function_name(),
michael@0:                           right.location().function_name());
michael@0:         if (comp)
michael@0:           return 0 > comp;
michael@0:       }
michael@0:       break;
michael@0: 
michael@0:     case BIRTH_LINE:
michael@0:       if (left.location().line_number() != right.location().line_number())
michael@0:         return left.location().line_number() <
michael@0:             right.location().line_number();
michael@0:       break;
michael@0: 
michael@0:     case COUNT:
michael@0:       if (left.count() != right.count())
michael@0:         return left.count() > right.count();  // Sort large at front of vector.
michael@0:       break;
michael@0: 
michael@0:     case AVERAGE_DURATION:
michael@0:       if (left.AverageMsDuration() != right.AverageMsDuration())
michael@0:         return left.AverageMsDuration() > right.AverageMsDuration();
michael@0:       break;
michael@0: 
michael@0:     default:
michael@0:       break;
michael@0:   }
michael@0:   if (tiebreaker_)
michael@0:     return tiebreaker_->operator()(left, right);
michael@0:   return false;
michael@0: }
michael@0: 
michael@0: bool Comparator::Equivalent(const Snapshot& left,
michael@0:                             const Snapshot& right) const {
michael@0:   switch (selector_) {
michael@0:     case BIRTH_THREAD:
michael@0:       if (left.birth_thread() != right.birth_thread() &&
michael@0:           left.birth_thread()->ThreadName() !=
michael@0:               right.birth_thread()->ThreadName())
michael@0:         return false;
michael@0:       break;
michael@0: 
michael@0:     case DEATH_THREAD:
michael@0:       if (left.death_thread() != right.death_thread() &&
michael@0:           left.DeathThreadName() != right.DeathThreadName())
michael@0:         return false;
michael@0:       break;
michael@0: 
michael@0:     case BIRTH_FILE:
michael@0:       if (left.location().file_name() != right.location().file_name()) {
michael@0:         int comp = strcmp(left.location().file_name(),
michael@0:                           right.location().file_name());
michael@0:         if (comp)
michael@0:           return false;
michael@0:       }
michael@0:       break;
michael@0: 
michael@0:     case BIRTH_FUNCTION:
michael@0:       if (left.location().function_name() != right.location().function_name()) {
michael@0:         int comp = strcmp(left.location().function_name(),
michael@0:                           right.location().function_name());
michael@0:         if (comp)
michael@0:           return false;
michael@0:       }
michael@0:       break;
michael@0: 
michael@0:     case COUNT:
michael@0:       if (left.count() != right.count())
michael@0:         return false;
michael@0:       break;
michael@0: 
michael@0:     case AVERAGE_DURATION:
michael@0:       if (left.life_duration() != right.life_duration())
michael@0:         return false;
michael@0:       break;
michael@0: 
michael@0:     default:
michael@0:       break;
michael@0:   }
michael@0:   if (tiebreaker_ && !use_tiebreaker_for_sort_only_)
michael@0:     return tiebreaker_->Equivalent(left, right);
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: bool Comparator::Acceptable(const Snapshot& sample) const {
michael@0:   if (required_.size()) {
michael@0:     switch (selector_) {
michael@0:       case BIRTH_THREAD:
michael@0:         if (sample.birth_thread()->ThreadName().find(required_) ==
michael@0:             std::string::npos)
michael@0:           return false;
michael@0:         break;
michael@0: 
michael@0:       case DEATH_THREAD:
michael@0:         if (sample.DeathThreadName().find(required_) == std::string::npos)
michael@0:           return false;
michael@0:         break;
michael@0: 
michael@0:       case BIRTH_FILE:
michael@0:         if (!strstr(sample.location().file_name(), required_.c_str()))
michael@0:           return false;
michael@0:         break;
michael@0: 
michael@0:       case BIRTH_FUNCTION:
michael@0:         if (!strstr(sample.location().function_name(), required_.c_str()))
michael@0:           return false;
michael@0:         break;
michael@0: 
michael@0:       default:
michael@0:         break;
michael@0:     }
michael@0:   }
michael@0:   if (tiebreaker_ && !use_tiebreaker_for_sort_only_)
michael@0:     return tiebreaker_->Acceptable(sample);
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: void Comparator::SetTiebreaker(Selector selector, const std::string required) {
michael@0:   if (selector == selector_ || NIL == selector)
michael@0:     return;
michael@0:   combined_selectors_ |= selector;
michael@0:   if (NIL == selector_) {
michael@0:     selector_ = selector;
michael@0:     if (required.size())
michael@0:       required_ = required;
michael@0:     return;
michael@0:   }
michael@0:   if (tiebreaker_) {
michael@0:     if (use_tiebreaker_for_sort_only_) {
michael@0:       Comparator* temp = new Comparator;
michael@0:       temp->tiebreaker_ = tiebreaker_;
michael@0:       tiebreaker_ = temp;
michael@0:     }
michael@0:   } else {
michael@0:     tiebreaker_ = new Comparator;
michael@0:     DCHECK(!use_tiebreaker_for_sort_only_);
michael@0:   }
michael@0:   tiebreaker_->SetTiebreaker(selector, required);
michael@0: }
michael@0: 
michael@0: bool Comparator::IsGroupedBy(Selector selector) const {
michael@0:   return 0 != (selector & combined_selectors_);
michael@0: }
michael@0: 
michael@0: void Comparator::SetSubgroupTiebreaker(Selector selector) {
michael@0:   if (selector == selector_ || NIL == selector)
michael@0:     return;
michael@0:   if (!tiebreaker_) {
michael@0:     use_tiebreaker_for_sort_only_ = true;
michael@0:     tiebreaker_ = new Comparator;
michael@0:     tiebreaker_->SetTiebreaker(selector, "");
michael@0:   } else {
michael@0:     tiebreaker_->SetSubgroupTiebreaker(selector);
michael@0:   }
michael@0: }
michael@0: 
michael@0: bool Comparator::WriteSortGrouping(const Snapshot& sample,
michael@0:                                        std::string* output) const {
michael@0:   bool wrote_data = false;
michael@0:   switch (selector_) {
michael@0:     case BIRTH_THREAD:
michael@0:       StringAppendF(output, "All new on %s ",
michael@0:                     sample.birth_thread()->ThreadName().c_str());
michael@0:       wrote_data = true;
michael@0:       break;
michael@0: 
michael@0:     case DEATH_THREAD:
michael@0:       if (sample.death_thread())
michael@0:         StringAppendF(output, "All deleted on %s ",
michael@0:                       sample.DeathThreadName().c_str());
michael@0:       else
michael@0:         output->append("All still alive ");
michael@0:       wrote_data = true;
michael@0:       break;
michael@0: 
michael@0:     case BIRTH_FILE:
michael@0:       StringAppendF(output, "All born in %s ",
michael@0:                     sample.location().file_name());
michael@0:       break;
michael@0: 
michael@0:     case BIRTH_FUNCTION:
michael@0:       output->append("All born in ");
michael@0:       sample.location().WriteFunctionName(output);
michael@0:       output->push_back(' ');
michael@0:       break;
michael@0: 
michael@0:     default:
michael@0:       break;
michael@0:   }
michael@0:   if (tiebreaker_ && !use_tiebreaker_for_sort_only_) {
michael@0:     wrote_data |= tiebreaker_->WriteSortGrouping(sample, output);
michael@0:   }
michael@0:   return wrote_data;
michael@0: }
michael@0: 
michael@0: void Comparator::WriteSnapshot(const Snapshot& sample,
michael@0:                                std::string* output) const {
michael@0:   sample.death_data().Write(output);
michael@0:   if (!(combined_selectors_ & BIRTH_THREAD) ||
michael@0:       !(combined_selectors_ & DEATH_THREAD))
michael@0:     StringAppendF(output, "%s->%s ",
michael@0:                   (combined_selectors_ & BIRTH_THREAD) ? "*" :
michael@0:                     sample.birth().birth_thread()->ThreadName().c_str(),
michael@0:                   (combined_selectors_ & DEATH_THREAD) ? "*" :
michael@0:                     sample.DeathThreadName().c_str());
michael@0:   sample.birth().location().Write(!(combined_selectors_ & BIRTH_FILE),
michael@0:                                   !(combined_selectors_ & BIRTH_FUNCTION),
michael@0:                                   output);
michael@0: }
michael@0: 
michael@0: }  // namespace tracked_objects