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

Comparing libev/ev.c (file contents):
Revision 1.241 by root, Fri May 9 13:57:00 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
… …
432#endif 440#endif
433 441
434/* Heap Entry */ 442/* Heap Entry */
435#if EV_HEAP_CACHE_AT 443#if EV_HEAP_CACHE_AT
436 typedef struct { 444 typedef struct {
445 ev_tstamp at;
437 WT w; 446 WT w;
438 ev_tstamp at;
439 } ANHE; 447 } ANHE;
440 448
441 #define ANHE_w(he) (he) /* access watcher, read-write */ 449 #define ANHE_w(he) (he).w /* access watcher, read-write */
442 #define ANHE_at(he) (he)->at /* acces cahced at, read-only */ 450 #define ANHE_at(he) (he).at /* access cached at, read-only */
443 #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 */
444#else 452#else
445 typedef WT ANHE; 453 typedef WT ANHE;
446 454
447 #define ANHE_w(he) (he) 455 #define ANHE_w(he) (he)
448 #define ANHE_at(he) (he)->at 456 #define ANHE_at(he) (he)->at
… …
790 * at the moment we allow libev the luxury of two heaps, 798 * at the moment we allow libev the luxury of two heaps,
791 * 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
792 * which is more cache-efficient. 800 * which is more cache-efficient.
793 * the difference is about 5% with 50000+ watchers. 801 * the difference is about 5% with 50000+ watchers.
794 */ 802 */
795#define EV_USE_4HEAP !EV_MINIMAL
796#if EV_USE_4HEAP 803#if EV_USE_4HEAP
797 804
798#define DHEAP 4 805#define DHEAP 4
799#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)
800 808
801/* towards the root */ 809/* towards the root */
802void inline_speed 810void inline_speed
803upheap (ANHE *heap, int k) 811upheap (ANHE *heap, int k)
804{ 812{
805 ANHE he = heap [k]; 813 ANHE he = heap [k];
806 814
807 for (;;) 815 for (;;)
808 { 816 {
809 int p = ((k - HEAP0 - 1) / DHEAP) + HEAP0; 817 int p = HPARENT (k);
810 818
811 if (p == k || ANHE_at (heap [p]) <= ANHE_at (he)) 819 if (p == k || ANHE_at (heap [p]) <= ANHE_at (he))
812 break; 820 break;
813 821
814 heap [k] = heap [p]; 822 heap [k] = heap [p];
815 ev_active (ANHE_w (heap [k])) = k; 823 ev_active (ANHE_w (heap [k])) = k;
816 k = p; 824 k = p;
817 } 825 }
818 826
827 heap [k] = he;
819 ev_active (ANHE_w (he)) = k; 828 ev_active (ANHE_w (he)) = k;
820 heap [k] = he;
821} 829}
822 830
823/* away from the root */ 831/* away from the root */
824void inline_speed 832void inline_speed
825downheap (ANHE *heap, int N, int k) 833downheap (ANHE *heap, int N, int k)
… …
834 ANHE *pos = heap + DHEAP * (k - HEAP0) + HEAP0; 842 ANHE *pos = heap + DHEAP * (k - HEAP0) + HEAP0;
835 843
836 // find minimum child 844 // find minimum child
837 if (expect_true (pos + DHEAP - 1 < E)) 845 if (expect_true (pos + DHEAP - 1 < E))
838 { 846 {
839 /* fast path */ (minpos = pos + 0), (minat = ANHE_at (*minpos)); 847 /* fast path */ (minpos = pos + 0), (minat = ANHE_at (*minpos));
840 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));
841 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));
842 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));
843 } 851 }
844 else if (pos < E) 852 else if (pos < E)
845 { 853 {
846 /* slow path */ (minpos = pos + 0), (minat = ANHE_at (*minpos)); 854 /* slow path */ (minpos = pos + 0), (minat = ANHE_at (*minpos));
847 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));
… …
852 break; 860 break;
853 861
854 if (ANHE_at (he) <= minat) 862 if (ANHE_at (he) <= minat)
855 break; 863 break;
856 864
865 heap [k] = *minpos;
857 ev_active (ANHE_w (*minpos)) = k; 866 ev_active (ANHE_w (*minpos)) = k;
858 heap [k] = *minpos;
859 867
860 k = minpos - heap; 868 k = minpos - heap;
861 } 869 }
862 870
871 heap [k] = he;
863 ev_active (ANHE_w (he)) = k; 872 ev_active (ANHE_w (he)) = k;
864 heap [k] = he;
865} 873}
866 874
867#else // 4HEAP 875#else // 4HEAP
868 876
869#define HEAP0 1 877#define HEAP0 1
878#define HPARENT(k) ((k) >> 1)
870 879
871/* towards the root */ 880/* towards the root */
872void inline_speed 881void inline_speed
873upheap (ANHE *heap, int k) 882upheap (ANHE *heap, int k)
874{ 883{
875 ANHE he = heap [k]; 884 ANHE he = heap [k];
876 885
877 for (;;) 886 for (;;)
878 { 887 {
879 int p = k >> 1; 888 int p = HPARENT (k);
880 889
881 /* maybe we could use a dummy element at heap [0]? */ 890 /* maybe we could use a dummy element at heap [0]? */
882 if (!p || ANHE_at (heap [p]) <= ANHE_at (he)) 891 if (!p || ANHE_at (heap [p]) <= ANHE_at (he))
883 break; 892 break;
884 893
885 heap [k] = heap [p]; 894 heap [k] = heap [p];
886 ev_active (ANHE_w (heap [k])) = k; 895 ev_active (ANHE_w (heap [k])) = k;
887 k = p; 896 k = p;
888 } 897 }
889 898
890 heap [k] = w; 899 heap [k] = he;
891 ev_active (ANHE_w (heap [k])) = k; 900 ev_active (ANHE_w (heap [k])) = k;
892} 901}
893 902
894/* away from the root */ 903/* away from the root */
895void inline_speed 904void inline_speed
… …
905 break; 914 break;
906 915
907 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])
908 ? 1 : 0; 917 ? 1 : 0;
909 918
910 if (w->at <= ANHE_at (heap [c])) 919 if (ANHE_at (he) <= ANHE_at (heap [c]))
911 break; 920 break;
912 921
913 heap [k] = heap [c]; 922 heap [k] = heap [c];
914 ev_active (ANHE_w (heap [k])) = k; 923 ev_active (ANHE_w (heap [k])) = k;
915 924
… …
922#endif 931#endif
923 932
924void inline_size 933void inline_size
925adjustheap (ANHE *heap, int N, int k) 934adjustheap (ANHE *heap, int N, int k)
926{ 935{
936 if (k > HEAP0 && ANHE_at (heap [HPARENT (k)]) >= ANHE_at (heap [k]))
927 upheap (heap, k); 937 upheap (heap, k);
938 else
928 downheap (heap, N, k); 939 downheap (heap, N, k);
929} 940}
930 941
931/*****************************************************************************/ 942/*****************************************************************************/
932 943
933typedef struct 944typedef struct
… …
1594#endif 1605#endif
1595 1606
1596void inline_size 1607void inline_size
1597timers_reify (EV_P) 1608timers_reify (EV_P)
1598{ 1609{
1599 while (timercnt && ANHE_at (timers [HEAP0]) <= mn_now) 1610 while (timercnt && ANHE_at (timers [HEAP0]) < mn_now)
1600 { 1611 {
1601 ev_timer *w = (ev_timer *)ANHE_w (timers [HEAP0]); 1612 ev_timer *w = (ev_timer *)ANHE_w (timers [HEAP0]);
1602 1613
1603 /*assert (("inactive timer on timer heap detected", ev_is_active (w)));*/ 1614 /*assert (("inactive timer on timer heap detected", ev_is_active (w)));*/
1604 1615
1605 /* first reschedule or stop timer */ 1616 /* first reschedule or stop timer */
1606 if (w->repeat) 1617 if (w->repeat)
1607 { 1618 {
1608 assert (("negative ev_timer repeat value found while processing timers", w->repeat > 0.));
1609
1610 ev_at (w) += w->repeat; 1619 ev_at (w) += w->repeat;
1611 if (ev_at (w) < mn_now) 1620 if (ev_at (w) < mn_now)
1612 ev_at (w) = mn_now; 1621 ev_at (w) = mn_now;
1613 1622
1623 assert (("negative ev_timer repeat value found while processing timers", w->repeat > 0.));
1624
1625 ANHE_at_set (timers [HEAP0]);
1614 downheap (timers, timercnt, HEAP0); 1626 downheap (timers, timercnt, HEAP0);
1615 } 1627 }
1616 else 1628 else
1617 ev_timer_stop (EV_A_ w); /* nonrepeating: stop timer */ 1629 ev_timer_stop (EV_A_ w); /* nonrepeating: stop timer */
1618 1630
… …
1622 1634
1623#if EV_PERIODIC_ENABLE 1635#if EV_PERIODIC_ENABLE
1624void inline_size 1636void inline_size
1625periodics_reify (EV_P) 1637periodics_reify (EV_P)
1626{ 1638{
1627 while (periodiccnt && ANHE_at (periodics [HEAP0]) <= ev_rt_now) 1639 while (periodiccnt && ANHE_at (periodics [HEAP0]) < ev_rt_now)
1628 { 1640 {
1629 ev_periodic *w = (ev_periodic *)ANHE_w (periodics [HEAP0]); 1641 ev_periodic *w = (ev_periodic *)ANHE_w (periodics [HEAP0]);
1630 1642
1631 /*assert (("inactive timer on periodic heap detected", ev_is_active (w)));*/ 1643 /*assert (("inactive timer on periodic heap detected", ev_is_active (w)));*/
1632 1644
1633 /* first reschedule or stop timer */ 1645 /* first reschedule or stop timer */
1634 if (w->reschedule_cb) 1646 if (w->reschedule_cb)
1635 { 1647 {
1636 ev_at (w) = w->reschedule_cb (w, ev_rt_now + TIME_EPSILON); 1648 ev_at (w) = w->reschedule_cb (w, ev_rt_now);
1649
1637 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
1652 ANHE_at_set (periodics [HEAP0]);
1638 downheap (periodics, periodiccnt, 1); 1653 downheap (periodics, periodiccnt, HEAP0);
1639 } 1654 }
1640 else if (w->interval) 1655 else if (w->interval)
1641 { 1656 {
1642 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 */
1643 if (ev_at (w) - ev_rt_now <= TIME_EPSILON) ev_at (w) += w->interval; 1660 if (ev_at (w) - ev_rt_now < TIME_EPSILON)
1644 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
1671 ANHE_at_set (periodics [HEAP0]);
1645 downheap (periodics, periodiccnt, HEAP0); 1672 downheap (periodics, periodiccnt, HEAP0);
1646 } 1673 }
1647 else 1674 else
1648 ev_periodic_stop (EV_A_ w); /* nonrepeating: stop timer */ 1675 ev_periodic_stop (EV_A_ w); /* nonrepeating: stop timer */
1649 1676
… …
1663 1690
1664 if (w->reschedule_cb) 1691 if (w->reschedule_cb)
1665 ev_at (w) = w->reschedule_cb (w, ev_rt_now); 1692 ev_at (w) = w->reschedule_cb (w, ev_rt_now);
1666 else if (w->interval) 1693 else if (w->interval)
1667 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;
1668 }
1669 1695
1670 /* now rebuild the heap, this for the 2-heap, inefficient for the 4-heap, but correct */ 1696 ANHE_at_set (periodics [i]);
1671 for (i = periodiccnt >> 1; --i; ) 1697 }
1698
1699 /* we don't use floyds algorithm, uphead is simpler and is more cache-efficient */
1700 /* also, this is easy and corretc for both 2-heaps and 4-heaps */
1701 for (i = 0; i < periodiccnt; ++i)
1672 downheap (periodics, periodiccnt, i + HEAP0); 1702 upheap (periodics, i + HEAP0);
1673} 1703}
1674#endif 1704#endif
1675 1705
1676void inline_speed 1706void inline_speed
1677time_update (EV_P_ ev_tstamp max_block) 1707time_update (EV_P_ ev_tstamp max_block)
… …
1985{ 2015{
1986 clear_pending (EV_A_ (W)w); 2016 clear_pending (EV_A_ (W)w);
1987 if (expect_false (!ev_is_active (w))) 2017 if (expect_false (!ev_is_active (w)))
1988 return; 2018 return;
1989 2019
1990 assert (("ev_io_start called with illegal fd (must stay constant after start!)", w->fd >= 0 && w->fd < anfdmax)); 2020 assert (("ev_io_stop called with illegal fd (must stay constant after start!)", w->fd >= 0 && w->fd < anfdmax));
1991 2021
1992 wlist_del (&anfds[w->fd].head, (WL)w); 2022 wlist_del (&anfds[w->fd].head, (WL)w);
1993 ev_stop (EV_A_ (W)w); 2023 ev_stop (EV_A_ (W)w);
1994 2024
1995 fd_change (EV_A_ w->fd, 1); 2025 fd_change (EV_A_ w->fd, 1);
… …
2009 array_needsize (ANHE, timers, timermax, ev_active (w) + 1, EMPTY2); 2039 array_needsize (ANHE, timers, timermax, ev_active (w) + 1, EMPTY2);
2010 ANHE_w (timers [ev_active (w)]) = (WT)w; 2040 ANHE_w (timers [ev_active (w)]) = (WT)w;
2011 ANHE_at_set (timers [ev_active (w)]); 2041 ANHE_at_set (timers [ev_active (w)]);
2012 upheap (timers, ev_active (w)); 2042 upheap (timers, ev_active (w));
2013 2043
2014 /*assert (("internal timer heap corruption", timers [ev_active (w)] == w));*/ 2044 /*assert (("internal timer heap corruption", timers [ev_active (w)] == (WT)w));*/
2015} 2045}
2016 2046
2017void noinline 2047void noinline
2018ev_timer_stop (EV_P_ ev_timer *w) 2048ev_timer_stop (EV_P_ ev_timer *w)
2019{ 2049{
… …
2080 ev_at (w) = w->offset; 2110 ev_at (w) = w->offset;
2081 2111
2082 ev_start (EV_A_ (W)w, ++periodiccnt + HEAP0 - 1); 2112 ev_start (EV_A_ (W)w, ++periodiccnt + HEAP0 - 1);
2083 array_needsize (ANHE, periodics, periodicmax, ev_active (w) + 1, EMPTY2); 2113 array_needsize (ANHE, periodics, periodicmax, ev_active (w) + 1, EMPTY2);
2084 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)]);
2085 upheap (periodics, ev_active (w)); 2116 upheap (periodics, ev_active (w));
2086 2117
2087 /*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));*/
2088} 2119}
2089 2120

Diff Legend

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