ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/libev/ev.c
(Generate patch)

Comparing libev/ev.c (file contents):
Revision 1.242 by root, Fri May 9 14:07:19 2008 UTC vs.
Revision 1.247 by root, Wed May 21 21:22:10 2008 UTC

… …
235# else 235# else
236# define EV_USE_EVENTFD 0 236# define EV_USE_EVENTFD 0
237# endif 237# endif
238#endif 238#endif
239 239
240#ifndef EV_USE_4HEAP
241# define EV_USE_4HEAP !EV_MINIMAL
242#endif
243
244#ifndef EV_HEAP_CACHE_AT
245# define EV_HEAP_CACHE_AT !EV_MINIMAL
246#endif
247
240/* this block fixes any misconfiguration where we know we run into trouble otherwise */ 248/* this block fixes any misconfiguration where we know we run into trouble otherwise */
241 249
242#ifndef CLOCK_MONOTONIC 250#ifndef CLOCK_MONOTONIC
243# undef EV_USE_MONOTONIC 251# undef EV_USE_MONOTONIC
244# define EV_USE_MONOTONIC 0 252# define EV_USE_MONOTONIC 0
… …
430 WL head; 438 WL head;
431} ANFS; 439} ANFS;
432#endif 440#endif
433 441
434/* Heap Entry */ 442/* Heap Entry */
435#define EV_HEAP_CACHE_AT 0
436#if EV_HEAP_CACHE_AT 443#if EV_HEAP_CACHE_AT
437 typedef struct { 444 typedef struct {
445 ev_tstamp at;
438 WT w; 446 WT w;
439 ev_tstamp at;
440 } ANHE; 447 } ANHE;
441 448
442 #define ANHE_w(he) (he).w /* access watcher, read-write */ 449 #define ANHE_w(he) (he).w /* access watcher, read-write */
443 #define ANHE_at(he) (he).at /* access cached at, read-only */ 450 #define ANHE_at(he) (he).at /* access cached at, read-only */
444 #define ANHE_at_set(he) (he).at = (he).w->at /* update at from watcher */ 451 #define ANHE_at_set(he) (he).at = (he).w->at /* update at from watcher */
… …
791 * at the moment we allow libev the luxury of two heaps, 798 * at the moment we allow libev the luxury of two heaps,
792 * a small-code-size 2-heap one and a ~1.5kb larger 4-heap 799 * a small-code-size 2-heap one and a ~1.5kb larger 4-heap
793 * which is more cache-efficient. 800 * which is more cache-efficient.
794 * the difference is about 5% with 50000+ watchers. 801 * the difference is about 5% with 50000+ watchers.
795 */ 802 */
796#define EV_USE_4HEAP !EV_MINIMAL
797#if EV_USE_4HEAP 803#if EV_USE_4HEAP
798 804
799#define DHEAP 4 805#define DHEAP 4
800#define HEAP0 (DHEAP - 1) /* index of first element in heap */ 806#define HEAP0 (DHEAP - 1) /* index of first element in heap */
807#define HPARENT(k) ((((k) - HEAP0 - 1) / DHEAP) + HEAP0)
801 808
802/* towards the root */ 809/* towards the root */
803void inline_speed 810void inline_speed
804upheap (ANHE *heap, int k) 811upheap (ANHE *heap, int k)
805{ 812{
806 ANHE he = heap [k]; 813 ANHE he = heap [k];
807 814
808 for (;;) 815 for (;;)
809 { 816 {
810 int p = ((k - HEAP0 - 1) / DHEAP) + HEAP0; 817 int p = HPARENT (k);
811 818
812 if (p == k || ANHE_at (heap [p]) <= ANHE_at (he)) 819 if (p == k || ANHE_at (heap [p]) <= ANHE_at (he))
813 break; 820 break;
814 821
815 heap [k] = heap [p]; 822 heap [k] = heap [p];
816 ev_active (ANHE_w (heap [k])) = k; 823 ev_active (ANHE_w (heap [k])) = k;
817 k = p; 824 k = p;
818 } 825 }
819 826
827 heap [k] = he;
820 ev_active (ANHE_w (he)) = k; 828 ev_active (ANHE_w (he)) = k;
821 heap [k] = he;
822} 829}
823 830
824/* away from the root */ 831/* away from the root */
825void inline_speed 832void inline_speed
826downheap (ANHE *heap, int N, int k) 833downheap (ANHE *heap, int N, int k)
… …
835 ANHE *pos = heap + DHEAP * (k - HEAP0) + HEAP0; 842 ANHE *pos = heap + DHEAP * (k - HEAP0) + HEAP0;
836 843
837 // find minimum child 844 // find minimum child
838 if (expect_true (pos + DHEAP - 1 < E)) 845 if (expect_true (pos + DHEAP - 1 < E))
839 { 846 {
840 /* fast path */ (minpos = pos + 0), (minat = ANHE_at (*minpos)); 847 /* fast path */ (minpos = pos + 0), (minat = ANHE_at (*minpos));
841 if (ANHE_at (pos [1]) < minat) (minpos = pos + 1), (minat = ANHE_at (*minpos)); 848 if ( ANHE_at (pos [1]) < minat) (minpos = pos + 1), (minat = ANHE_at (*minpos));
842 if (ANHE_at (pos [2]) < minat) (minpos = pos + 2), (minat = ANHE_at (*minpos)); 849 if ( ANHE_at (pos [2]) < minat) (minpos = pos + 2), (minat = ANHE_at (*minpos));
843 if (ANHE_at (pos [3]) < minat) (minpos = pos + 3), (minat = ANHE_at (*minpos)); 850 if ( ANHE_at (pos [3]) < minat) (minpos = pos + 3), (minat = ANHE_at (*minpos));
844 } 851 }
845 else if (pos < E) 852 else if (pos < E)
846 { 853 {
847 /* slow path */ (minpos = pos + 0), (minat = ANHE_at (*minpos)); 854 /* slow path */ (minpos = pos + 0), (minat = ANHE_at (*minpos));
848 if (pos + 1 < E && ANHE_at (pos [1]) < minat) (minpos = pos + 1), (minat = ANHE_at (*minpos)); 855 if (pos + 1 < E && ANHE_at (pos [1]) < minat) (minpos = pos + 1), (minat = ANHE_at (*minpos));
… …
853 break; 860 break;
854 861
855 if (ANHE_at (he) <= minat) 862 if (ANHE_at (he) <= minat)
856 break; 863 break;
857 864
865 heap [k] = *minpos;
858 ev_active (ANHE_w (*minpos)) = k; 866 ev_active (ANHE_w (*minpos)) = k;
859 heap [k] = *minpos;
860 867
861 k = minpos - heap; 868 k = minpos - heap;
862 } 869 }
863 870
871 heap [k] = he;
864 ev_active (ANHE_w (he)) = k; 872 ev_active (ANHE_w (he)) = k;
865 heap [k] = he;
866} 873}
867 874
868#else // 4HEAP 875#else // 4HEAP
869 876
870#define HEAP0 1 877#define HEAP0 1
878#define HPARENT(k) ((k) >> 1)
871 879
872/* towards the root */ 880/* towards the root */
873void inline_speed 881void inline_speed
874upheap (ANHE *heap, int k) 882upheap (ANHE *heap, int k)
875{ 883{
876 ANHE he = heap [k]; 884 ANHE he = heap [k];
877 885
878 for (;;) 886 for (;;)
879 { 887 {
880 int p = k >> 1; 888 int p = HPARENT (k);
881 889
882 /* maybe we could use a dummy element at heap [0]? */ 890 /* maybe we could use a dummy element at heap [0]? */
883 if (!p || ANHE_at (heap [p]) <= ANHE_at (he)) 891 if (!p || ANHE_at (heap [p]) <= ANHE_at (he))
884 break; 892 break;
885 893
886 heap [k] = heap [p]; 894 heap [k] = heap [p];
887 ev_active (ANHE_w (heap [k])) = k; 895 ev_active (ANHE_w (heap [k])) = k;
888 k = p; 896 k = p;
889 } 897 }
890 898
891 heap [k] = w; 899 heap [k] = he;
892 ev_active (ANHE_w (heap [k])) = k; 900 ev_active (ANHE_w (heap [k])) = k;
893} 901}
894 902
895/* away from the root */ 903/* away from the root */
896void inline_speed 904void inline_speed
… …
906 break; 914 break;
907 915
908 c += c + 1 < N && ANHE_at (heap [c]) > ANHE_at (heap [c + 1]) 916 c += c + 1 < N && ANHE_at (heap [c]) > ANHE_at (heap [c + 1])
909 ? 1 : 0; 917 ? 1 : 0;
910 918
911 if (w->at <= ANHE_at (heap [c])) 919 if (ANHE_at (he) <= ANHE_at (heap [c]))
912 break; 920 break;
913 921
914 heap [k] = heap [c]; 922 heap [k] = heap [c];
915 ev_active (ANHE_w (heap [k])) = k; 923 ev_active (ANHE_w (heap [k])) = k;
916 924
… …
923#endif 931#endif
924 932
925void inline_size 933void inline_size
926adjustheap (ANHE *heap, int N, int k) 934adjustheap (ANHE *heap, int N, int k)
927{ 935{
936 if (k > HEAP0 && ANHE_at (heap [HPARENT (k)]) >= ANHE_at (heap [k]))
928 upheap (heap, k); 937 upheap (heap, k);
938 else
929 downheap (heap, N, k); 939 downheap (heap, N, k);
930} 940}
931 941
932/*****************************************************************************/ 942/*****************************************************************************/
933 943
934typedef struct 944typedef struct
… …
1595#endif 1605#endif
1596 1606
1597void inline_size 1607void inline_size
1598timers_reify (EV_P) 1608timers_reify (EV_P)
1599{ 1609{
1600 while (timercnt && ANHE_at (timers [HEAP0]) <= mn_now) 1610 while (timercnt && ANHE_at (timers [HEAP0]) < mn_now)
1601 { 1611 {
1602 ev_timer *w = (ev_timer *)ANHE_w (timers [HEAP0]); 1612 ev_timer *w = (ev_timer *)ANHE_w (timers [HEAP0]);
1603 1613
1604 /*assert (("inactive timer on timer heap detected", ev_is_active (w)));*/ 1614 /*assert (("inactive timer on timer heap detected", ev_is_active (w)));*/
1605 1615
1606 /* first reschedule or stop timer */ 1616 /* first reschedule or stop timer */
1607 if (w->repeat) 1617 if (w->repeat)
1608 { 1618 {
1609 assert (("negative ev_timer repeat value found while processing timers", w->repeat > 0.));
1610
1611 ev_at (w) += w->repeat; 1619 ev_at (w) += w->repeat;
1612 if (ev_at (w) < mn_now) 1620 if (ev_at (w) < mn_now)
1613 ev_at (w) = mn_now; 1621 ev_at (w) = mn_now;
1622
1623 assert (("negative ev_timer repeat value found while processing timers", w->repeat > 0.));
1614 1624
1615 ANHE_at_set (timers [HEAP0]); 1625 ANHE_at_set (timers [HEAP0]);
1616 downheap (timers, timercnt, HEAP0); 1626 downheap (timers, timercnt, HEAP0);
1617 } 1627 }
1618 else 1628 else
… …
1624 1634
1625#if EV_PERIODIC_ENABLE 1635#if EV_PERIODIC_ENABLE
1626void inline_size 1636void inline_size
1627periodics_reify (EV_P) 1637periodics_reify (EV_P)
1628{ 1638{
1629 while (periodiccnt && ANHE_at (periodics [HEAP0]) <= ev_rt_now) 1639 while (periodiccnt && ANHE_at (periodics [HEAP0]) < ev_rt_now)
1630 { 1640 {
1631 ev_periodic *w = (ev_periodic *)ANHE_w (periodics [HEAP0]); 1641 ev_periodic *w = (ev_periodic *)ANHE_w (periodics [HEAP0]);
1632 1642
1633 /*assert (("inactive timer on periodic heap detected", ev_is_active (w)));*/ 1643 /*assert (("inactive timer on periodic heap detected", ev_is_active (w)));*/
1634 1644
1635 /* first reschedule or stop timer */ 1645 /* first reschedule or stop timer */
1636 if (w->reschedule_cb) 1646 if (w->reschedule_cb)
1637 { 1647 {
1638 ev_at (w) = w->reschedule_cb (w, ev_rt_now + TIME_EPSILON); 1648 ev_at (w) = w->reschedule_cb (w, ev_rt_now);
1649
1639 assert (("ev_periodic reschedule callback returned time in the past", ev_at (w) > ev_rt_now)); 1650 assert (("ev_periodic reschedule callback returned time in the past", ev_at (w) >= ev_rt_now));
1651
1640 ANHE_at_set (periodics [HEAP0]); 1652 ANHE_at_set (periodics [HEAP0]);
1641 downheap (periodics, periodiccnt, HEAP0); 1653 downheap (periodics, periodiccnt, HEAP0);
1642 } 1654 }
1643 else if (w->interval) 1655 else if (w->interval)
1644 { 1656 {
1645 ev_at (w) = w->offset + ceil ((ev_rt_now - w->offset) / w->interval) * w->interval; 1657 ev_at (w) = w->offset + ceil ((ev_rt_now - w->offset) / w->interval) * w->interval;
1658 /* if next trigger time is not sufficiently in the future, put it there */
1659 /* this might happen because of floating point inexactness */
1646 if (ev_at (w) - ev_rt_now <= TIME_EPSILON) ev_at (w) += w->interval; 1660 if (ev_at (w) - ev_rt_now < TIME_EPSILON)
1647 assert (("ev_periodic timeout in the past detected while processing timers, negative interval?", ev_at (w) > ev_rt_now)); 1661 {
1662 ev_at (w) += w->interval;
1663
1664 /* if interval is unreasonably low we might still have a time in the past */
1665 /* so correct this. this will make the periodic very inexact, but the user */
1666 /* has effectively asked to get triggered more often than possible */
1667 if (ev_at (w) < ev_rt_now)
1668 ev_at (w) = ev_rt_now;
1669 }
1670
1648 ANHE_at_set (periodics [HEAP0]); 1671 ANHE_at_set (periodics [HEAP0]);
1649 downheap (periodics, periodiccnt, HEAP0); 1672 downheap (periodics, periodiccnt, HEAP0);
1650 } 1673 }
1651 else 1674 else
1652 ev_periodic_stop (EV_A_ w); /* nonrepeating: stop timer */ 1675 ev_periodic_stop (EV_A_ w); /* nonrepeating: stop timer */
… …
1671 ev_at (w) = w->offset + ceil ((ev_rt_now - w->offset) / w->interval) * w->interval; 1694 ev_at (w) = w->offset + ceil ((ev_rt_now - w->offset) / w->interval) * w->interval;
1672 1695
1673 ANHE_at_set (periodics [i]); 1696 ANHE_at_set (periodics [i]);
1674 } 1697 }
1675 1698
1676 /* now rebuild the heap, this for the 2-heap, inefficient for the 4-heap, but correct */ 1699 /* we don't use floyds algorithm, uphead is simpler and is more cache-efficient */
1677 for (i = periodiccnt >> 1; --i; ) 1700 /* also, this is easy and corretc for both 2-heaps and 4-heaps */
1701 for (i = 0; i < periodiccnt; ++i)
1678 downheap (periodics, periodiccnt, i + HEAP0); 1702 upheap (periodics, i + HEAP0);
1679} 1703}
1680#endif 1704#endif
1681 1705
1682void inline_speed 1706void inline_speed
1683time_update (EV_P_ ev_tstamp max_block) 1707time_update (EV_P_ ev_tstamp max_block)
… …
2086 ev_at (w) = w->offset; 2110 ev_at (w) = w->offset;
2087 2111
2088 ev_start (EV_A_ (W)w, ++periodiccnt + HEAP0 - 1); 2112 ev_start (EV_A_ (W)w, ++periodiccnt + HEAP0 - 1);
2089 array_needsize (ANHE, periodics, periodicmax, ev_active (w) + 1, EMPTY2); 2113 array_needsize (ANHE, periodics, periodicmax, ev_active (w) + 1, EMPTY2);
2090 ANHE_w (periodics [ev_active (w)]) = (WT)w; 2114 ANHE_w (periodics [ev_active (w)]) = (WT)w;
2115 ANHE_at_set (periodics [ev_active (w)]);
2091 upheap (periodics, ev_active (w)); 2116 upheap (periodics, ev_active (w));
2092 2117
2093 /*assert (("internal periodic heap corruption", ANHE_w (periodics [ev_active (w)]) == (WT)w));*/ 2118 /*assert (("internal periodic heap corruption", ANHE_w (periodics [ev_active (w)]) == (WT)w));*/
2094} 2119}
2095 2120

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines