… | |
… | |
422 | W w; |
422 | W w; |
423 | int events; |
423 | int events; |
424 | } ANPENDING; |
424 | } ANPENDING; |
425 | |
425 | |
426 | #if EV_USE_INOTIFY |
426 | #if EV_USE_INOTIFY |
|
|
427 | /* hash table entry per inotify-id */ |
427 | typedef struct |
428 | typedef struct |
428 | { |
429 | { |
429 | WL head; |
430 | WL head; |
430 | } ANFS; |
431 | } ANFS; |
|
|
432 | #endif |
|
|
433 | |
|
|
434 | /* Heap Entry */ |
|
|
435 | #if EV_HEAP_CACHE_AT |
|
|
436 | typedef struct { |
|
|
437 | WT w; |
|
|
438 | ev_tstamp at; |
|
|
439 | } ANHE; |
|
|
440 | |
|
|
441 | #define ANHE_w(he) (he) /* access watcher, read-write */ |
|
|
442 | #define ANHE_at(he) (he)->at /* acces cahced at, read-only */ |
|
|
443 | #define ANHE_at_set(he) (he)->at = (he)->w->at /* update at from watcher */ |
|
|
444 | #else |
|
|
445 | typedef WT ANHE; |
|
|
446 | |
|
|
447 | #define ANHE_w(he) (he) |
|
|
448 | #define ANHE_at(he) (he)->at |
|
|
449 | #define ANHE_at_set(he) |
431 | #endif |
450 | #endif |
432 | |
451 | |
433 | #if EV_MULTIPLICITY |
452 | #if EV_MULTIPLICITY |
434 | |
453 | |
435 | struct ev_loop |
454 | struct ev_loop |
… | |
… | |
760 | } |
779 | } |
761 | |
780 | |
762 | /*****************************************************************************/ |
781 | /*****************************************************************************/ |
763 | |
782 | |
764 | /* |
783 | /* |
|
|
784 | * the heap functions want a real array index. array index 0 uis guaranteed to not |
|
|
785 | * be in-use at any time. the first heap entry is at array [HEAP0]. DHEAP gives |
|
|
786 | * the branching factor of the d-tree. |
|
|
787 | */ |
|
|
788 | |
|
|
789 | /* |
765 | * at the moment we allow libev the luxury of two heaps, |
790 | * at the moment we allow libev the luxury of two heaps, |
766 | * a small-code-size 2-heap one and a ~1.5kb larger 4-heap |
791 | * a small-code-size 2-heap one and a ~1.5kb larger 4-heap |
767 | * which is more cache-efficient. |
792 | * which is more cache-efficient. |
768 | * the difference is about 5% with 50000+ watchers. |
793 | * the difference is about 5% with 50000+ watchers. |
769 | */ |
794 | */ |
770 | #define USE_4HEAP !EV_MINIMAL |
795 | #define EV_USE_4HEAP !EV_MINIMAL |
771 | #if USE_4HEAP |
796 | #if EV_USE_4HEAP |
772 | |
797 | |
773 | #define DHEAP 4 |
798 | #define DHEAP 4 |
774 | #define HEAP0 (DHEAP - 1) /* index of first element in heap */ |
799 | #define HEAP0 (DHEAP - 1) /* index of first element in heap */ |
775 | |
800 | |
776 | /* towards the root */ |
801 | /* towards the root */ |
777 | void inline_speed |
802 | void inline_speed |
778 | upheap (WT *heap, int k) |
803 | upheap (ANHE *heap, int k) |
779 | { |
804 | { |
780 | WT w = heap [k]; |
805 | ANHE he = heap [k]; |
781 | |
806 | |
782 | for (;;) |
807 | for (;;) |
783 | { |
808 | { |
784 | int p = ((k - HEAP0 - 1) / DHEAP) + HEAP0; |
809 | int p = ((k - HEAP0 - 1) / DHEAP) + HEAP0; |
785 | |
810 | |
786 | if (p >= HEAP0 || heap [p]->at <= w->at) |
811 | if (p == k || ANHE_at (heap [p]) <= ANHE_at (he)) |
787 | break; |
812 | break; |
788 | |
813 | |
789 | heap [k] = heap [p]; |
814 | heap [k] = heap [p]; |
790 | ev_active (heap [k]) = k; |
815 | ev_active (ANHE_w (heap [k])) = k; |
791 | k = p; |
816 | k = p; |
792 | } |
817 | } |
793 | |
818 | |
|
|
819 | ev_active (ANHE_w (he)) = k; |
794 | heap [k] = w; |
820 | heap [k] = he; |
795 | ev_active (heap [k]) = k; |
|
|
796 | } |
821 | } |
797 | |
822 | |
798 | /* away from the root */ |
823 | /* away from the root */ |
799 | void inline_speed |
824 | void inline_speed |
800 | downheap (WT *heap, int N, int k) |
825 | downheap (ANHE *heap, int N, int k) |
801 | { |
826 | { |
802 | WT w = heap [k]; |
827 | ANHE he = heap [k]; |
803 | WT *E = heap + N + HEAP0; |
828 | ANHE *E = heap + N + HEAP0; |
804 | |
829 | |
805 | for (;;) |
830 | for (;;) |
806 | { |
831 | { |
807 | ev_tstamp minat; |
832 | ev_tstamp minat; |
808 | WT *minpos; |
833 | ANHE *minpos; |
809 | WT *pos = heap + DHEAP * (k - HEAP0) + HEAP0; |
834 | ANHE *pos = heap + DHEAP * (k - HEAP0) + HEAP0; |
810 | |
835 | |
811 | // find minimum child |
836 | // find minimum child |
812 | if (expect_true (pos + DHEAP - 1 < E)) |
837 | if (expect_true (pos + DHEAP - 1 < E)) |
813 | { |
838 | { |
814 | /* fast path */ |
|
|
815 | (minpos = pos + 0), (minat = (*minpos)->at); |
839 | /* fast path */ (minpos = pos + 0), (minat = ANHE_at (*minpos)); |
816 | if (pos [1]->at < minat) (minpos = pos + 1), (minat = (*minpos)->at); |
840 | if (ANHE_at (pos [1]) < minat) (minpos = pos + 1), (minat = ANHE_at (*minpos)); |
817 | if (pos [2]->at < minat) (minpos = pos + 2), (minat = (*minpos)->at); |
841 | if (ANHE_at (pos [2]) < minat) (minpos = pos + 2), (minat = ANHE_at (*minpos)); |
818 | if (pos [3]->at < minat) (minpos = pos + 3), (minat = (*minpos)->at); |
842 | if (ANHE_at (pos [3]) < minat) (minpos = pos + 3), (minat = ANHE_at (*minpos)); |
|
|
843 | } |
|
|
844 | else if (pos < E) |
|
|
845 | { |
|
|
846 | /* 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)); |
|
|
848 | if (pos + 2 < E && ANHE_at (pos [2]) < minat) (minpos = pos + 2), (minat = ANHE_at (*minpos)); |
|
|
849 | if (pos + 3 < E && ANHE_at (pos [3]) < minat) (minpos = pos + 3), (minat = ANHE_at (*minpos)); |
819 | } |
850 | } |
820 | else |
851 | else |
821 | { |
|
|
822 | /* slow path */ |
|
|
823 | if (pos >= E) |
|
|
824 | break; |
|
|
825 | (minpos = pos + 0), (minat = (*minpos)->at); |
|
|
826 | if (pos + 1 < E && pos [1]->at < minat) (minpos = pos + 1), (minat = (*minpos)->at); |
|
|
827 | if (pos + 2 < E && pos [2]->at < minat) (minpos = pos + 2), (minat = (*minpos)->at); |
|
|
828 | if (pos + 3 < E && pos [3]->at < minat) (minpos = pos + 3), (minat = (*minpos)->at); |
|
|
829 | } |
|
|
830 | |
|
|
831 | if (w->at <= minat) |
|
|
832 | break; |
852 | break; |
833 | |
853 | |
|
|
854 | if (ANHE_at (he) <= minat) |
|
|
855 | break; |
|
|
856 | |
834 | ev_active (*minpos) = k; |
857 | ev_active (ANHE_w (*minpos)) = k; |
835 | heap [k] = *minpos; |
858 | heap [k] = *minpos; |
836 | |
859 | |
837 | k = minpos - heap; |
860 | k = minpos - heap; |
838 | } |
861 | } |
839 | |
862 | |
|
|
863 | ev_active (ANHE_w (he)) = k; |
840 | heap [k] = w; |
864 | heap [k] = he; |
841 | ev_active (heap [k]) = k; |
|
|
842 | } |
865 | } |
843 | |
866 | |
844 | #else // 4HEAP |
867 | #else // 4HEAP |
845 | |
868 | |
846 | #define HEAP0 1 |
869 | #define HEAP0 1 |
847 | |
870 | |
848 | /* towards the root */ |
871 | /* towards the root */ |
849 | void inline_speed |
872 | void inline_speed |
850 | upheap (WT *heap, int k) |
873 | upheap (ANHE *heap, int k) |
851 | { |
874 | { |
852 | WT w = heap [k]; |
875 | ANHE he = heap [k]; |
853 | |
876 | |
854 | for (;;) |
877 | for (;;) |
855 | { |
878 | { |
856 | int p = k >> 1; |
879 | int p = k >> 1; |
857 | |
880 | |
858 | /* maybe we could use a dummy element at heap [0]? */ |
881 | /* maybe we could use a dummy element at heap [0]? */ |
859 | if (!p || heap [p]->at <= w->at) |
882 | if (!p || ANHE_at (heap [p]) <= ANHE_at (he)) |
860 | break; |
883 | break; |
861 | |
884 | |
862 | heap [k] = heap [p]; |
885 | heap [k] = heap [p]; |
863 | ev_active (heap [k]) = k; |
886 | ev_active (ANHE_w (heap [k])) = k; |
864 | k = p; |
887 | k = p; |
865 | } |
888 | } |
866 | |
889 | |
867 | heap [k] = w; |
890 | heap [k] = w; |
868 | ev_active (heap [k]) = k; |
891 | ev_active (ANHE_w (heap [k])) = k; |
869 | } |
892 | } |
870 | |
893 | |
871 | /* away from the root */ |
894 | /* away from the root */ |
872 | void inline_speed |
895 | void inline_speed |
873 | downheap (WT *heap, int N, int k) |
896 | downheap (ANHE *heap, int N, int k) |
874 | { |
897 | { |
875 | WT w = heap [k]; |
898 | ANHE he = heap [k]; |
876 | |
899 | |
877 | for (;;) |
900 | for (;;) |
878 | { |
901 | { |
879 | int c = k << 1; |
902 | int c = k << 1; |
880 | |
903 | |
881 | if (c > N) |
904 | if (c > N) |
882 | break; |
905 | break; |
883 | |
906 | |
884 | c += c + 1 < N && heap [c]->at > heap [c + 1]->at |
907 | c += c + 1 < N && ANHE_at (heap [c]) > ANHE_at (heap [c + 1]) |
885 | ? 1 : 0; |
908 | ? 1 : 0; |
886 | |
909 | |
887 | if (w->at <= heap [c]->at) |
910 | if (w->at <= ANHE_at (heap [c])) |
888 | break; |
911 | break; |
889 | |
912 | |
890 | heap [k] = heap [c]; |
913 | heap [k] = heap [c]; |
891 | ((W)heap [k])->active = k; |
914 | ev_active (ANHE_w (heap [k])) = k; |
892 | |
915 | |
893 | k = c; |
916 | k = c; |
894 | } |
917 | } |
895 | |
918 | |
896 | heap [k] = w; |
919 | heap [k] = he; |
897 | ev_active (heap [k]) = k; |
920 | ev_active (ANHE_w (he)) = k; |
898 | } |
921 | } |
899 | #endif |
922 | #endif |
900 | |
923 | |
901 | void inline_size |
924 | void inline_size |
902 | adjustheap (WT *heap, int N, int k) |
925 | adjustheap (ANHE *heap, int N, int k) |
903 | { |
926 | { |
904 | upheap (heap, k); |
927 | upheap (heap, k); |
905 | downheap (heap, N, k); |
928 | downheap (heap, N, k); |
906 | } |
929 | } |
907 | |
930 | |
… | |
… | |
1571 | #endif |
1594 | #endif |
1572 | |
1595 | |
1573 | void inline_size |
1596 | void inline_size |
1574 | timers_reify (EV_P) |
1597 | timers_reify (EV_P) |
1575 | { |
1598 | { |
1576 | while (timercnt && ev_at (timers [HEAP0]) <= mn_now) |
1599 | while (timercnt && ANHE_at (timers [HEAP0]) <= mn_now) |
1577 | { |
1600 | { |
1578 | ev_timer *w = (ev_timer *)timers [HEAP0]; |
1601 | ev_timer *w = (ev_timer *)ANHE_w (timers [HEAP0]); |
1579 | |
1602 | |
1580 | /*assert (("inactive timer on timer heap detected", ev_is_active (w)));*/ |
1603 | /*assert (("inactive timer on timer heap detected", ev_is_active (w)));*/ |
1581 | |
1604 | |
1582 | /* first reschedule or stop timer */ |
1605 | /* first reschedule or stop timer */ |
1583 | if (w->repeat) |
1606 | if (w->repeat) |
… | |
… | |
1599 | |
1622 | |
1600 | #if EV_PERIODIC_ENABLE |
1623 | #if EV_PERIODIC_ENABLE |
1601 | void inline_size |
1624 | void inline_size |
1602 | periodics_reify (EV_P) |
1625 | periodics_reify (EV_P) |
1603 | { |
1626 | { |
1604 | while (periodiccnt && ev_at (periodics [HEAP0]) <= ev_rt_now) |
1627 | while (periodiccnt && ANHE_at (periodics [HEAP0]) <= ev_rt_now) |
1605 | { |
1628 | { |
1606 | ev_periodic *w = (ev_periodic *)periodics [HEAP0]; |
1629 | ev_periodic *w = (ev_periodic *)ANHE_w (periodics [HEAP0]); |
1607 | |
1630 | |
1608 | /*assert (("inactive timer on periodic heap detected", ev_is_active (w)));*/ |
1631 | /*assert (("inactive timer on periodic heap detected", ev_is_active (w)));*/ |
1609 | |
1632 | |
1610 | /* first reschedule or stop timer */ |
1633 | /* first reschedule or stop timer */ |
1611 | if (w->reschedule_cb) |
1634 | if (w->reschedule_cb) |
… | |
… | |
1632 | periodics_reschedule (EV_P) |
1655 | periodics_reschedule (EV_P) |
1633 | { |
1656 | { |
1634 | int i; |
1657 | int i; |
1635 | |
1658 | |
1636 | /* adjust periodics after time jump */ |
1659 | /* adjust periodics after time jump */ |
1637 | for (i = 1; i <= periodiccnt; ++i) |
1660 | for (i = HEAP0; i < periodiccnt + HEAP0; ++i) |
1638 | { |
1661 | { |
1639 | ev_periodic *w = (ev_periodic *)periodics [i]; |
1662 | ev_periodic *w = (ev_periodic *)ANHE_w (periodics [i]); |
1640 | |
1663 | |
1641 | if (w->reschedule_cb) |
1664 | if (w->reschedule_cb) |
1642 | ev_at (w) = w->reschedule_cb (w, ev_rt_now); |
1665 | ev_at (w) = w->reschedule_cb (w, ev_rt_now); |
1643 | else if (w->interval) |
1666 | else if (w->interval) |
1644 | ev_at (w) = w->offset + ceil ((ev_rt_now - w->offset) / w->interval) * w->interval; |
1667 | ev_at (w) = w->offset + ceil ((ev_rt_now - w->offset) / w->interval) * w->interval; |
1645 | } |
1668 | } |
1646 | |
1669 | |
1647 | /* now rebuild the heap */ |
1670 | /* now rebuild the heap, this for the 2-heap, inefficient for the 4-heap, but correct */ |
1648 | for (i = periodiccnt >> 1; --i; ) |
1671 | for (i = periodiccnt >> 1; --i; ) |
1649 | downheap (periodics, periodiccnt, i + HEAP0); |
1672 | downheap (periodics, periodiccnt, i + HEAP0); |
1650 | } |
1673 | } |
1651 | #endif |
1674 | #endif |
1652 | |
1675 | |
… | |
… | |
1708 | { |
1731 | { |
1709 | #if EV_PERIODIC_ENABLE |
1732 | #if EV_PERIODIC_ENABLE |
1710 | periodics_reschedule (EV_A); |
1733 | periodics_reschedule (EV_A); |
1711 | #endif |
1734 | #endif |
1712 | /* adjust timers. this is easy, as the offset is the same for all of them */ |
1735 | /* adjust timers. this is easy, as the offset is the same for all of them */ |
1713 | for (i = 1; i <= timercnt; ++i) |
1736 | for (i = 0; i < timercnt; ++i) |
1714 | ev_at (timers [i]) += ev_rt_now - mn_now; |
1737 | { |
|
|
1738 | ANHE *he = timers + i + HEAP0; |
|
|
1739 | ANHE_w (*he)->at += ev_rt_now - mn_now; |
|
|
1740 | ANHE_at_set (*he); |
|
|
1741 | } |
1715 | } |
1742 | } |
1716 | |
1743 | |
1717 | mn_now = ev_rt_now; |
1744 | mn_now = ev_rt_now; |
1718 | } |
1745 | } |
1719 | } |
1746 | } |
… | |
… | |
1789 | |
1816 | |
1790 | waittime = MAX_BLOCKTIME; |
1817 | waittime = MAX_BLOCKTIME; |
1791 | |
1818 | |
1792 | if (timercnt) |
1819 | if (timercnt) |
1793 | { |
1820 | { |
1794 | ev_tstamp to = ev_at (timers [HEAP0]) - mn_now + backend_fudge; |
1821 | ev_tstamp to = ANHE_at (timers [HEAP0]) - mn_now + backend_fudge; |
1795 | if (waittime > to) waittime = to; |
1822 | if (waittime > to) waittime = to; |
1796 | } |
1823 | } |
1797 | |
1824 | |
1798 | #if EV_PERIODIC_ENABLE |
1825 | #if EV_PERIODIC_ENABLE |
1799 | if (periodiccnt) |
1826 | if (periodiccnt) |
1800 | { |
1827 | { |
1801 | ev_tstamp to = ev_at (periodics [HEAP0]) - ev_rt_now + backend_fudge; |
1828 | ev_tstamp to = ANHE_at (periodics [HEAP0]) - ev_rt_now + backend_fudge; |
1802 | if (waittime > to) waittime = to; |
1829 | if (waittime > to) waittime = to; |
1803 | } |
1830 | } |
1804 | #endif |
1831 | #endif |
1805 | |
1832 | |
1806 | if (expect_false (waittime < timeout_blocktime)) |
1833 | if (expect_false (waittime < timeout_blocktime)) |
… | |
… | |
1977 | ev_at (w) += mn_now; |
2004 | ev_at (w) += mn_now; |
1978 | |
2005 | |
1979 | assert (("ev_timer_start called with negative timer repeat value", w->repeat >= 0.)); |
2006 | assert (("ev_timer_start called with negative timer repeat value", w->repeat >= 0.)); |
1980 | |
2007 | |
1981 | ev_start (EV_A_ (W)w, ++timercnt + HEAP0 - 1); |
2008 | ev_start (EV_A_ (W)w, ++timercnt + HEAP0 - 1); |
1982 | array_needsize (WT, timers, timermax, timercnt + HEAP0, EMPTY2); |
2009 | array_needsize (ANHE, timers, timermax, ev_active (w) + 1, EMPTY2); |
1983 | timers [ev_active (w)] = (WT)w; |
2010 | ANHE_w (timers [ev_active (w)]) = (WT)w; |
|
|
2011 | ANHE_at_set (timers [ev_active (w)]); |
1984 | upheap (timers, ev_active (w)); |
2012 | upheap (timers, ev_active (w)); |
1985 | |
2013 | |
1986 | /*assert (("internal timer heap corruption", timers [ev_active (w)] == w));*/ |
2014 | /*assert (("internal timer heap corruption", timers [ev_active (w)] == w));*/ |
1987 | } |
2015 | } |
1988 | |
2016 | |
… | |
… | |
1994 | return; |
2022 | return; |
1995 | |
2023 | |
1996 | { |
2024 | { |
1997 | int active = ev_active (w); |
2025 | int active = ev_active (w); |
1998 | |
2026 | |
1999 | assert (("internal timer heap corruption", timers [active] == (WT)w)); |
2027 | assert (("internal timer heap corruption", ANHE_w (timers [active]) == (WT)w)); |
2000 | |
2028 | |
2001 | if (expect_true (active < timercnt + HEAP0 - 1)) |
2029 | if (expect_true (active < timercnt + HEAP0 - 1)) |
2002 | { |
2030 | { |
2003 | timers [active] = timers [timercnt + HEAP0 - 1]; |
2031 | timers [active] = timers [timercnt + HEAP0 - 1]; |
2004 | adjustheap (timers, timercnt, active); |
2032 | adjustheap (timers, timercnt, active); |
… | |
… | |
2018 | if (ev_is_active (w)) |
2046 | if (ev_is_active (w)) |
2019 | { |
2047 | { |
2020 | if (w->repeat) |
2048 | if (w->repeat) |
2021 | { |
2049 | { |
2022 | ev_at (w) = mn_now + w->repeat; |
2050 | ev_at (w) = mn_now + w->repeat; |
|
|
2051 | ANHE_at_set (timers [ev_active (w)]); |
2023 | adjustheap (timers, timercnt, ev_active (w)); |
2052 | adjustheap (timers, timercnt, ev_active (w)); |
2024 | } |
2053 | } |
2025 | else |
2054 | else |
2026 | ev_timer_stop (EV_A_ w); |
2055 | ev_timer_stop (EV_A_ w); |
2027 | } |
2056 | } |
… | |
… | |
2049 | } |
2078 | } |
2050 | else |
2079 | else |
2051 | ev_at (w) = w->offset; |
2080 | ev_at (w) = w->offset; |
2052 | |
2081 | |
2053 | ev_start (EV_A_ (W)w, ++periodiccnt + HEAP0 - 1); |
2082 | ev_start (EV_A_ (W)w, ++periodiccnt + HEAP0 - 1); |
2054 | array_needsize (WT, periodics, periodicmax, periodiccnt + HEAP0, EMPTY2); |
2083 | array_needsize (ANHE, periodics, periodicmax, ev_active (w) + 1, EMPTY2); |
2055 | periodics [ev_active (w)] = (WT)w; |
2084 | ANHE_w (periodics [ev_active (w)]) = (WT)w; |
2056 | upheap (periodics, ev_active (w)); |
2085 | upheap (periodics, ev_active (w)); |
2057 | |
2086 | |
2058 | /*assert (("internal periodic heap corruption", periodics [ev_active (w)] == w));*/ |
2087 | /*assert (("internal periodic heap corruption", ANHE_w (periodics [ev_active (w)]) == (WT)w));*/ |
2059 | } |
2088 | } |
2060 | |
2089 | |
2061 | void noinline |
2090 | void noinline |
2062 | ev_periodic_stop (EV_P_ ev_periodic *w) |
2091 | ev_periodic_stop (EV_P_ ev_periodic *w) |
2063 | { |
2092 | { |
… | |
… | |
2066 | return; |
2095 | return; |
2067 | |
2096 | |
2068 | { |
2097 | { |
2069 | int active = ev_active (w); |
2098 | int active = ev_active (w); |
2070 | |
2099 | |
2071 | assert (("internal periodic heap corruption", periodics [active] == (WT)w)); |
2100 | assert (("internal periodic heap corruption", ANHE_w (periodics [active]) == (WT)w)); |
2072 | |
2101 | |
2073 | if (expect_true (active < periodiccnt + HEAP0 - 1)) |
2102 | if (expect_true (active < periodiccnt + HEAP0 - 1)) |
2074 | { |
2103 | { |
2075 | periodics [active] = periodics [periodiccnt + HEAP0 - 1]; |
2104 | periodics [active] = periodics [periodiccnt + HEAP0 - 1]; |
2076 | adjustheap (periodics, periodiccnt, active); |
2105 | adjustheap (periodics, periodiccnt, active); |