--- libev/ev.c	2008/05/21 21:22:10	1.247
+++ libev/ev.c	2008/05/21 23:25:21	1.248
@@ -290,6 +290,17 @@
 
 /**/
 
+/* undefined or zero: no verification done or available */
+/* 1 or higher: ev_loop_verify function available */
+/* 2 or higher: ev_loop_verify is called frequently */
+#define EV_VERIFY 1
+
+#if EV_VERIFY > 1
+# define EV_FREQUENT_CHECK ev_loop_verify (EV_A)
+#else
+# define EV_FREQUENT_CHECK do { } while (0)
+#endif
+
 /*
  * This is used to avoid floating point rounding problems.
  * It is added to ev_rt_now when scheduling periodics
@@ -446,15 +457,15 @@
     WT w;
   } ANHE;
 
-  #define ANHE_w(he)      (he).w     /* access watcher, read-write */
-  #define ANHE_at(he)     (he).at    /* access cached at, read-only */
-  #define ANHE_at_set(he) (he).at = (he).w->at /* update at from watcher */
+  #define ANHE_w(he)        (he).w     /* access watcher, read-write */
+  #define ANHE_at(he)       (he).at    /* access cached at, read-only */
+  #define ANHE_at_cache(he) (he).at = (he).w->at /* update at from watcher */
 #else
   typedef WT ANHE;
 
-  #define ANHE_w(he)      (he)
-  #define ANHE_at(he)     (he)->at
-  #define ANHE_at_set(he)
+  #define ANHE_w(he)        (he)
+  #define ANHE_at(he)       (he)->at
+  #define ANHE_at_cache(he)
 #endif
 
 #if EV_MULTIPLICITY
@@ -805,28 +816,7 @@
 #define DHEAP 4
 #define HEAP0 (DHEAP - 1) /* index of first element in heap */
 #define HPARENT(k) ((((k) - HEAP0 - 1) / DHEAP) + HEAP0)
-
-/* towards the root */
-void inline_speed
-upheap (ANHE *heap, int k)
-{
-  ANHE he = heap [k];
-
-  for (;;)
-    {
-      int p = HPARENT (k);
-
-      if (p == k || ANHE_at (heap [p]) <= ANHE_at (he))
-        break;
-
-      heap [k] = heap [p];
-      ev_active (ANHE_w (heap [k])) = k;
-      k = p;
-    }
-
-  heap [k] = he;
-  ev_active (ANHE_w (he)) = k;
-}
+#define UPHEAP_DONE(p,k) ((p) == (k))
 
 /* away from the root */
 void inline_speed
@@ -839,9 +829,9 @@
     {
       ev_tstamp minat;
       ANHE *minpos;
-      ANHE *pos = heap + DHEAP * (k - HEAP0) + HEAP0;
+      ANHE *pos = heap + DHEAP * (k - HEAP0) + HEAP0 + 1;
 
-      // find minimum child
+      /* find minimum child */
       if (expect_true (pos + DHEAP - 1 < E))
         {
           /* fast path */                               (minpos = pos + 0), (minat = ANHE_at (*minpos));
@@ -872,63 +862,63 @@
   ev_active (ANHE_w (he)) = k;
 }
 
-#else // 4HEAP
+#else /* 4HEAP */
 
 #define HEAP0 1
 #define HPARENT(k) ((k) >> 1)
+#define UPHEAP_DONE(p,k) (!(p))
 
-/* towards the root */
+/* away from the root */
 void inline_speed
-upheap (ANHE *heap, int k)
+downheap (ANHE *heap, int N, int k)
 {
   ANHE he = heap [k];
 
   for (;;)
     {
-      int p = HPARENT (k);
+      int c = k << 1;
 
-      /* maybe we could use a dummy element at heap [0]? */
-      if (!p || ANHE_at (heap [p]) <= ANHE_at (he))
+      if (c > N + HEAP0 - 1)
         break;
 
-      heap [k] = heap [p];
+      c += c + 1 < N + HEAP0 && ANHE_at (heap [c]) > ANHE_at (heap [c + 1])
+           ? 1 : 0;
+
+      if (ANHE_at (he) <= ANHE_at (heap [c]))
+        break;
+
+      heap [k] = heap [c];
       ev_active (ANHE_w (heap [k])) = k;
-      k = p;
+      
+      k = c;
     }
 
   heap [k] = he;
-  ev_active (ANHE_w (heap [k])) = k;
+  ev_active (ANHE_w (he)) = k;
 }
+#endif
 
-/* away from the root */
+/* towards the root */
 void inline_speed
-downheap (ANHE *heap, int N, int k)
+upheap (ANHE *heap, int k)
 {
   ANHE he = heap [k];
 
   for (;;)
     {
-      int c = k << 1;
-
-      if (c > N)
-        break;
-
-      c += c + 1 < N && ANHE_at (heap [c]) > ANHE_at (heap [c + 1])
-           ? 1 : 0;
+      int p = HPARENT (k);
 
-      if (ANHE_at (he) <= ANHE_at (heap [c]))
+      if (UPHEAP_DONE (p, k) || ANHE_at (heap [p]) <= ANHE_at (he))
         break;
 
-      heap [k] = heap [c];
+      heap [k] = heap [p];
       ev_active (ANHE_w (heap [k])) = k;
-      
-      k = c;
+      k = p;
     }
 
   heap [k] = he;
   ev_active (ANHE_w (he)) = k;
 }
-#endif
 
 void inline_size
 adjustheap (ANHE *heap, int N, int k)
@@ -939,6 +929,32 @@
     downheap (heap, N, k);
 }
 
+/* rebuild the heap: this function is used only once and executed rarely */
+void inline_size
+reheap (ANHE *heap, int N)
+{
+  int i;
+  /* we don't use floyds algorithm, upheap is simpler and is more cache-efficient */
+  /* also, this is easy to implement and correct for both 2-heaps and 4-heaps */
+  for (i = 0; i < N; ++i)
+    upheap (heap, i + HEAP0);
+}
+
+#if EV_VERIFY
+static void
+checkheap (ANHE *heap, int N)
+{
+  int i;
+
+  for (i = HEAP0; i < N + HEAP0; ++i)
+    {
+      assert (("active index mismatch in heap", ev_active (ANHE_w (heap [i])) == i));
+      assert (("heap condition violated", i == HEAP0 || ANHE_at (heap [HPARENT (i)]) <= ANHE_at (heap [i])));
+      assert (("heap at cache mismatch", ANHE_at (heap [i]) == ev_at (ANHE_w (heap [i]))));
+    }
+}
+#endif
+
 /*****************************************************************************/
 
 typedef struct
@@ -1491,6 +1507,40 @@
 {
   postfork = 1; /* must be in line with ev_default_fork */
 }
+
+#if EV_VERIFY
+static void
+array_check (W **ws, int cnt)
+{
+  while (cnt--)
+    assert (("active index mismatch", ev_active (ws [cnt]) == cnt + 1));
+}
+
+static void
+ev_loop_verify (EV_P)
+{
+  int i;
+
+  checkheap (timers, timercnt);
+#if EV_PERIODIC_ENABLE
+  checkheap (periodics, periodiccnt);
+#endif
+
+#if EV_IDLE_ENABLE
+  for (i = NUMPRI; i--; )
+    array_check ((W **)idles [i], idlecnt [i]);
+#endif
+#if EV_FORK_ENABLE
+  array_check ((W **)forks, forkcnt);
+#endif
+  array_check ((W **)prepares, preparecnt);
+  array_check ((W **)checks, checkcnt);
+#if EV_ASYNC_ENABLE
+  array_check ((W **)asyncs, asynccnt);
+#endif
+}
+#endif
+
 #endif
 
 #if EV_MULTIPLICITY
@@ -1566,6 +1616,8 @@
 {
   int pri;
 
+  EV_FREQUENT_CHECK;
+
   for (pri = NUMPRI; pri--; )
     while (pendingcnt [pri])
       {
@@ -1579,6 +1631,8 @@
             EV_CB_INVOKE (p->w, p->events);
           }
       }
+
+  EV_FREQUENT_CHECK;
 }
 
 #if EV_IDLE_ENABLE
@@ -1607,6 +1661,8 @@
 void inline_size
 timers_reify (EV_P)
 {
+  EV_FREQUENT_CHECK;
+
   while (timercnt && ANHE_at (timers [HEAP0]) < mn_now)
     {
       ev_timer *w = (ev_timer *)ANHE_w (timers [HEAP0]);
@@ -1622,12 +1678,13 @@
 
           assert (("negative ev_timer repeat value found while processing timers", w->repeat > 0.));
 
-          ANHE_at_set (timers [HEAP0]);
+          ANHE_at_cache (timers [HEAP0]);
           downheap (timers, timercnt, HEAP0);
         }
       else
         ev_timer_stop (EV_A_ w); /* nonrepeating: stop timer */
 
+      EV_FREQUENT_CHECK;
       ev_feed_event (EV_A_ (W)w, EV_TIMEOUT);
     }
 }
@@ -1636,6 +1693,7 @@
 void inline_size
 periodics_reify (EV_P)
 {
+  EV_FREQUENT_CHECK;
   while (periodiccnt && ANHE_at (periodics [HEAP0]) < ev_rt_now)
     {
       ev_periodic *w = (ev_periodic *)ANHE_w (periodics [HEAP0]);
@@ -1649,8 +1707,9 @@
 
           assert (("ev_periodic reschedule callback returned time in the past", ev_at (w) >= ev_rt_now));
 
-          ANHE_at_set (periodics [HEAP0]);
+          ANHE_at_cache (periodics [HEAP0]);
           downheap (periodics, periodiccnt, HEAP0);
+          EV_FREQUENT_CHECK;
         }
       else if (w->interval)
         {
@@ -1668,12 +1727,13 @@
                 ev_at (w) = ev_rt_now;
             }
 
-          ANHE_at_set (periodics [HEAP0]);
+          ANHE_at_cache (periodics [HEAP0]);
           downheap (periodics, periodiccnt, HEAP0);
         }
       else
         ev_periodic_stop (EV_A_ w); /* nonrepeating: stop timer */
 
+      EV_FREQUENT_CHECK;
       ev_feed_event (EV_A_ (W)w, EV_PERIODIC);
     }
 }
@@ -1693,13 +1753,10 @@
       else if (w->interval)
         ev_at (w) = w->offset + ceil ((ev_rt_now - w->offset) / w->interval) * w->interval;
 
-      ANHE_at_set (periodics [i]);
+      ANHE_at_cache (periodics [i]);
     }
 
-  /* we don't use floyds algorithm, uphead is simpler and is more cache-efficient */
-  /* also, this is easy and corretc for both 2-heaps and 4-heaps */
-  for (i = 0; i < periodiccnt; ++i)
-    upheap (periodics, i + HEAP0);
+  reheap (periodics, periodiccnt);
 }
 #endif
 
@@ -1767,7 +1824,7 @@
             {
               ANHE *he = timers + i + HEAP0;
               ANHE_w (*he)->at += ev_rt_now - mn_now;
-              ANHE_at_set (*he);
+              ANHE_at_cache (*he);
             }
         }
 
@@ -2002,12 +2059,16 @@
 
   assert (("ev_io_start called with negative fd", fd >= 0));
 
+  EV_FREQUENT_CHECK;
+
   ev_start (EV_A_ (W)w, 1);
   array_needsize (ANFD, anfds, anfdmax, fd + 1, anfds_init);
   wlist_add (&anfds[fd].head, (WL)w);
 
   fd_change (EV_A_ fd, w->events & EV_IOFDSET | 1);
   w->events &= ~EV_IOFDSET;
+
+  EV_FREQUENT_CHECK;
 }
 
 void noinline
@@ -2019,10 +2080,14 @@
 
   assert (("ev_io_stop called with illegal fd (must stay constant after start!)", w->fd >= 0 && w->fd < anfdmax));
 
+  EV_FREQUENT_CHECK;
+
   wlist_del (&anfds[w->fd].head, (WL)w);
   ev_stop (EV_A_ (W)w);
 
   fd_change (EV_A_ w->fd, 1);
+
+  EV_FREQUENT_CHECK;
 }
 
 void noinline
@@ -2035,12 +2100,17 @@
 
   assert (("ev_timer_start called with negative timer repeat value", w->repeat >= 0.));
 
-  ev_start (EV_A_ (W)w, ++timercnt + HEAP0 - 1);
+  EV_FREQUENT_CHECK;
+
+  ++timercnt;
+  ev_start (EV_A_ (W)w, timercnt + HEAP0 - 1);
   array_needsize (ANHE, timers, timermax, ev_active (w) + 1, EMPTY2);
   ANHE_w (timers [ev_active (w)]) = (WT)w;
-  ANHE_at_set (timers [ev_active (w)]);
+  ANHE_at_cache (timers [ev_active (w)]);
   upheap (timers, ev_active (w));
 
+  EV_FREQUENT_CHECK;
+
   /*assert (("internal timer heap corruption", timers [ev_active (w)] == (WT)w));*/
 }
 
@@ -2051,20 +2121,24 @@
   if (expect_false (!ev_is_active (w)))
     return;
 
+  EV_FREQUENT_CHECK;
+
   {
     int active = ev_active (w);
 
     assert (("internal timer heap corruption", ANHE_w (timers [active]) == (WT)w));
 
-    if (expect_true (active < timercnt + HEAP0 - 1))
+    --timercnt;
+
+    if (expect_true (active < timercnt + HEAP0))
       {
-        timers [active] = timers [timercnt + HEAP0 - 1];
+        timers [active] = timers [timercnt + HEAP0];
         adjustheap (timers, timercnt, active);
       }
-
-    --timercnt;
   }
 
+  EV_FREQUENT_CHECK;
+
   ev_at (w) -= mn_now;
 
   ev_stop (EV_A_ (W)w);
@@ -2073,12 +2147,14 @@
 void noinline
 ev_timer_again (EV_P_ ev_timer *w)
 {
+  EV_FREQUENT_CHECK;
+
   if (ev_is_active (w))
     {
       if (w->repeat)
         {
           ev_at (w) = mn_now + w->repeat;
-          ANHE_at_set (timers [ev_active (w)]);
+          ANHE_at_cache (timers [ev_active (w)]);
           adjustheap (timers, timercnt, ev_active (w));
         }
       else
@@ -2089,6 +2165,8 @@
       ev_at (w) = w->repeat;
       ev_timer_start (EV_A_ w);
     }
+
+  EV_FREQUENT_CHECK;
 }
 
 #if EV_PERIODIC_ENABLE
@@ -2109,12 +2187,17 @@
   else
     ev_at (w) = w->offset;
 
-  ev_start (EV_A_ (W)w, ++periodiccnt + HEAP0 - 1);
+  EV_FREQUENT_CHECK;
+
+  ++periodiccnt;
+  ev_start (EV_A_ (W)w, periodiccnt + HEAP0 - 1);
   array_needsize (ANHE, periodics, periodicmax, ev_active (w) + 1, EMPTY2);
   ANHE_w (periodics [ev_active (w)]) = (WT)w;
-  ANHE_at_set (periodics [ev_active (w)]);
+  ANHE_at_cache (periodics [ev_active (w)]);
   upheap (periodics, ev_active (w));
 
+  EV_FREQUENT_CHECK;
+
   /*assert (("internal periodic heap corruption", ANHE_w (periodics [ev_active (w)]) == (WT)w));*/
 }
 
@@ -2125,20 +2208,24 @@
   if (expect_false (!ev_is_active (w)))
     return;
 
+  EV_FREQUENT_CHECK;
+
   {
     int active = ev_active (w);
 
     assert (("internal periodic heap corruption", ANHE_w (periodics [active]) == (WT)w));
 
-    if (expect_true (active < periodiccnt + HEAP0 - 1))
+    --periodiccnt;
+
+    if (expect_true (active < periodiccnt + HEAP0))
       {
-        periodics [active] = periodics [periodiccnt + HEAP0 - 1];
+        periodics [active] = periodics [periodiccnt + HEAP0];
         adjustheap (periodics, periodiccnt, active);
       }
-
-    --periodiccnt;
   }
 
+  EV_FREQUENT_CHECK;
+
   ev_stop (EV_A_ (W)w);
 }
 
@@ -2168,6 +2255,8 @@
 
   evpipe_init (EV_A);
 
+  EV_FREQUENT_CHECK;
+
   {
 #ifndef _WIN32
     sigset_t full, prev;
@@ -2197,6 +2286,8 @@
       sigaction (w->signum, &sa, 0);
 #endif
     }
+
+  EV_FREQUENT_CHECK;
 }
 
 void noinline
@@ -2206,11 +2297,15 @@
   if (expect_false (!ev_is_active (w)))
     return;
 
+  EV_FREQUENT_CHECK;
+
   wlist_del (&signals [w->signum - 1].head, (WL)w);
   ev_stop (EV_A_ (W)w);
 
   if (!signals [w->signum - 1].head)
     signal (w->signum, SIG_DFL);
+
+  EV_FREQUENT_CHECK;
 }
 
 void
@@ -2222,8 +2317,12 @@
   if (expect_false (ev_is_active (w)))
     return;
 
+  EV_FREQUENT_CHECK;
+
   ev_start (EV_A_ (W)w, 1);
   wlist_add (&childs [w->pid & (EV_PID_HASHSIZE - 1)], (WL)w);
+
+  EV_FREQUENT_CHECK;
 }
 
 void
@@ -2233,8 +2332,12 @@
   if (expect_false (!ev_is_active (w)))
     return;
 
+  EV_FREQUENT_CHECK;
+
   wlist_del (&childs [w->pid & (EV_PID_HASHSIZE - 1)], (WL)w);
   ev_stop (EV_A_ (W)w);
+
+  EV_FREQUENT_CHECK;
 }
 
 #if EV_STAT_ENABLE
@@ -2472,6 +2575,8 @@
     ev_timer_start (EV_A_ &w->timer);
 
   ev_start (EV_A_ (W)w, 1);
+
+  EV_FREQUENT_CHECK;
 }
 
 void
@@ -2481,12 +2586,16 @@
   if (expect_false (!ev_is_active (w)))
     return;
 
+  EV_FREQUENT_CHECK;
+
 #if EV_USE_INOTIFY
   infy_del (EV_A_ w);
 #endif
   ev_timer_stop (EV_A_ &w->timer);
 
   ev_stop (EV_A_ (W)w);
+
+  EV_FREQUENT_CHECK;
 }
 #endif
 
@@ -2499,6 +2608,8 @@
 
   pri_adjust (EV_A_ (W)w);
 
+  EV_FREQUENT_CHECK;
+
   {
     int active = ++idlecnt [ABSPRI (w)];
 
@@ -2508,6 +2619,8 @@
     array_needsize (ev_idle *, idles [ABSPRI (w)], idlemax [ABSPRI (w)], active, EMPTY2);
     idles [ABSPRI (w)][active - 1] = w;
   }
+
+  EV_FREQUENT_CHECK;
 }
 
 void
@@ -2517,6 +2630,8 @@
   if (expect_false (!ev_is_active (w)))
     return;
 
+  EV_FREQUENT_CHECK;
+
   {
     int active = ev_active (w);
 
@@ -2526,6 +2641,8 @@
     ev_stop (EV_A_ (W)w);
     --idleall;
   }
+
+  EV_FREQUENT_CHECK;
 }
 #endif
 
@@ -2535,9 +2652,13 @@
   if (expect_false (ev_is_active (w)))
     return;
 
+  EV_FREQUENT_CHECK;
+
   ev_start (EV_A_ (W)w, ++preparecnt);
   array_needsize (ev_prepare *, prepares, preparemax, preparecnt, EMPTY2);
   prepares [preparecnt - 1] = w;
+
+  EV_FREQUENT_CHECK;
 }
 
 void
@@ -2547,6 +2668,8 @@
   if (expect_false (!ev_is_active (w)))
     return;
 
+  EV_FREQUENT_CHECK;
+
   {
     int active = ev_active (w);
 
@@ -2555,6 +2678,8 @@
   }
 
   ev_stop (EV_A_ (W)w);
+
+  EV_FREQUENT_CHECK;
 }
 
 void
@@ -2563,9 +2688,13 @@
   if (expect_false (ev_is_active (w)))
     return;
 
+  EV_FREQUENT_CHECK;
+
   ev_start (EV_A_ (W)w, ++checkcnt);
   array_needsize (ev_check *, checks, checkmax, checkcnt, EMPTY2);
   checks [checkcnt - 1] = w;
+
+  EV_FREQUENT_CHECK;
 }
 
 void
@@ -2575,6 +2704,8 @@
   if (expect_false (!ev_is_active (w)))
     return;
 
+  EV_FREQUENT_CHECK;
+
   {
     int active = ev_active (w);
 
@@ -2583,6 +2714,8 @@
   }
 
   ev_stop (EV_A_ (W)w);
+
+  EV_FREQUENT_CHECK;
 }
 
 #if EV_EMBED_ENABLE
@@ -2639,6 +2772,8 @@
     ev_io_init (&w->io, embed_io_cb, backend_fd, EV_READ);
   }
 
+  EV_FREQUENT_CHECK;
+
   ev_set_priority (&w->io, ev_priority (w));
   ev_io_start (EV_A_ &w->io);
 
@@ -2649,6 +2784,8 @@
   /*ev_idle_init (&w->idle, e,bed_idle_cb);*/
 
   ev_start (EV_A_ (W)w, 1);
+
+  EV_FREQUENT_CHECK;
 }
 
 void
@@ -2658,10 +2795,14 @@
   if (expect_false (!ev_is_active (w)))
     return;
 
+  EV_FREQUENT_CHECK;
+
   ev_io_stop (EV_A_ &w->io);
   ev_prepare_stop (EV_A_ &w->prepare);
 
   ev_stop (EV_A_ (W)w);
+
+  EV_FREQUENT_CHECK;
 }
 #endif
 
@@ -2672,9 +2813,13 @@
   if (expect_false (ev_is_active (w)))
     return;
 
+  EV_FREQUENT_CHECK;
+
   ev_start (EV_A_ (W)w, ++forkcnt);
   array_needsize (ev_fork *, forks, forkmax, forkcnt, EMPTY2);
   forks [forkcnt - 1] = w;
+
+  EV_FREQUENT_CHECK;
 }
 
 void
@@ -2684,6 +2829,8 @@
   if (expect_false (!ev_is_active (w)))
     return;
 
+  EV_FREQUENT_CHECK;
+
   {
     int active = ev_active (w);
 
@@ -2692,6 +2839,8 @@
   }
 
   ev_stop (EV_A_ (W)w);
+
+  EV_FREQUENT_CHECK;
 }
 #endif
 
@@ -2704,9 +2853,13 @@
 
   evpipe_init (EV_A);
 
+  EV_FREQUENT_CHECK;
+
   ev_start (EV_A_ (W)w, ++asynccnt);
   array_needsize (ev_async *, asyncs, asyncmax, asynccnt, EMPTY2);
   asyncs [asynccnt - 1] = w;
+
+  EV_FREQUENT_CHECK;
 }
 
 void
@@ -2716,6 +2869,8 @@
   if (expect_false (!ev_is_active (w)))
     return;
 
+  EV_FREQUENT_CHECK;
+
   {
     int active = ev_active (w);
 
@@ -2724,6 +2879,8 @@
   }
 
   ev_stop (EV_A_ (W)w);
+
+  EV_FREQUENT_CHECK;
 }
 
 void