From: Arnaud Giersch <arnaud.giersch@univ-fcomte.fr>
Date: Thu, 9 Nov 2017 15:03:33 +0000 (+0100)
Subject: Use a std::priority_queue for simix_timers.
X-Git-Tag: v3.18~242^2~63
X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/0a600adfb6d3e9d5969581e26ce815dac3792572

Use a std::priority_queue for simix_timers.

Note that canceled timers are only disabled and stay in the queue until their trigger date.
Use SIMIX_timer_flush() to remove disabled timers from the top of the queue.
---

diff --git a/src/simix/smx_global.cpp b/src/simix/smx_global.cpp
index 6e770e8fcc..50019eae59 100644
--- a/src/simix/smx_global.cpp
+++ b/src/simix/smx_global.cpp
@@ -5,6 +5,7 @@
 
 #include <functional>
 #include <memory>
+#include <queue>
 
 #include "src/internal_config.h"
 #include <csignal> /* Signal handling */
@@ -50,19 +51,31 @@ XBT_LOG_NEW_CATEGORY(simix, "All SIMIX categories");
 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(simix_kernel, simix, "Logging specific to SIMIX (kernel)");
 
 std::unique_ptr<simgrid::simix::Global> simix_global;
-static xbt_heap_t simix_timers = nullptr;
 
 /** @brief Timer datatype */
 class s_smx_timer_t {
   double date = 0.0;
-  s_smx_timer_t() = default;
 
 public:
   simgrid::xbt::Task<void()> callback;
+  void disable() { date = -1.0; }
+  bool isDisabled() { return date == -1.0; }
   double getDate() { return date; }
   s_smx_timer_t(double date, simgrid::xbt::Task<void()> callback) : date(date), callback(std::move(callback)) {}
 };
 
+namespace {
+typedef std::pair<double, smx_timer_t> TimerQelt;
+std::priority_queue<TimerQelt, std::vector<TimerQelt>, std::greater<TimerQelt>> simix_timers;
+void SIMIX_timer_flush()
+{
+  while (not simix_timers.empty() && simix_timers.top().second->isDisabled()) {
+    delete simix_timers.top().second;
+    simix_timers.pop();
+  }
+}
+}
+
 void (*SMPI_switch_data_segment)(int) = nullptr;
 
 int _sg_do_verbose_exit = 1;
@@ -156,7 +169,7 @@ static void install_segvhandler()
 /********************************* SIMIX **************************************/
 double SIMIX_timer_next()
 {
-  return xbt_heap_size(simix_timers) > 0 ? xbt_heap_maxkey(simix_timers) : -1.0;
+  return simix_timers.empty() ? -1.0 : simix_timers.top().first;
 }
 
 static void kill_process(smx_actor_t process)
@@ -240,11 +253,6 @@ void SIMIX_global_init(int *argc, char **argv)
     });
   }
 
-  if (not simix_timers)
-    simix_timers = xbt_heap_new(8, [](void* p) {
-      delete static_cast<smx_timer_t>(p);
-    });
-
   if (xbt_cfg_get_boolean("clean-atexit"))
     atexit(SIMIX_clean);
 
@@ -292,8 +300,10 @@ void SIMIX_clean()
   /* Exit the SIMIX network module */
   SIMIX_mailbox_exit();
 
-  xbt_heap_free(simix_timers);
-  simix_timers = nullptr;
+  while (not simix_timers.empty()) {
+    delete simix_timers.top().second;
+    simix_timers.pop();
+  }
   /* Free the remaining data structures */
   simix_global->process_to_run.clear();
   simix_global->process_that_ran.clear();
@@ -363,18 +373,19 @@ static void SIMIX_wake_processes()
 static bool SIMIX_execute_timers()
 {
   bool result = false;
-  while (xbt_heap_size(simix_timers) > 0 && SIMIX_get_clock() >= SIMIX_timer_next()) {
+  while (not simix_timers.empty() && SIMIX_get_clock() >= simix_timers.top().first) {
     result = true;
-     //FIXME: make the timers being real callbacks
-     // (i.e. provide dispatchers that read and expand the args)
-     smx_timer_t timer = (smx_timer_t) xbt_heap_pop(simix_timers);
-     try {
-       timer->callback();
-     }
-     catch(...) {
-       xbt_die("Exception throwed ouf of timer callback");
-     }
-     delete timer;
+    // FIXME: make the timers being real callbacks
+    // (i.e. provide dispatchers that read and expand the args)
+    smx_timer_t timer = simix_timers.top().second;
+    simix_timers.pop();
+    SIMIX_timer_flush();
+    try {
+      timer->callback();
+    } catch (...) {
+      xbt_die("Exception thrown ouf of timer callback");
+    }
+    delete timer;
   }
   return result;
 }
@@ -564,20 +575,21 @@ void SIMIX_run()
 smx_timer_t SIMIX_timer_set(double date, void (*callback)(void*), void *arg)
 {
   smx_timer_t timer = new s_smx_timer_t(date, [callback, arg]() { callback(arg); });
-  xbt_heap_push(simix_timers, timer, date);
+  simix_timers.emplace(date, timer);
   return timer;
 }
 
 smx_timer_t SIMIX_timer_set(double date, simgrid::xbt::Task<void()> callback)
 {
   smx_timer_t timer = new s_smx_timer_t(date, std::move(callback));
-  xbt_heap_push(simix_timers, timer, date);
+  simix_timers.emplace(date, timer);
   return timer;
 }
 
 /** @brief cancels a timer that was added earlier */
 void SIMIX_timer_remove(smx_timer_t timer) {
-  delete static_cast<smx_timer_t>(xbt_heap_rm_elm(simix_timers, timer, timer->getDate()));
+  timer->disable();
+  SIMIX_timer_flush();
 }
 
 /** @brief Returns the date at which the timer will trigger (or 0 if nullptr timer) */