… | |
… | |
802 | */ |
802 | */ |
803 | #if EV_USE_4HEAP |
803 | #if EV_USE_4HEAP |
804 | |
804 | |
805 | #define DHEAP 4 |
805 | #define DHEAP 4 |
806 | #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) |
807 | |
808 | |
808 | /* towards the root */ |
809 | /* towards the root */ |
809 | void inline_speed |
810 | void inline_speed |
810 | upheap (ANHE *heap, int k) |
811 | upheap (ANHE *heap, int k) |
811 | { |
812 | { |
812 | ANHE he = heap [k]; |
813 | ANHE he = heap [k]; |
813 | |
814 | |
814 | for (;;) |
815 | for (;;) |
815 | { |
816 | { |
816 | int p = ((k - HEAP0 - 1) / DHEAP) + HEAP0; |
817 | int p = HPARENT (k); |
817 | |
818 | |
818 | if (p == k || ANHE_at (heap [p]) <= ANHE_at (he)) |
819 | if (p == k || ANHE_at (heap [p]) <= ANHE_at (he)) |
819 | break; |
820 | break; |
820 | |
821 | |
821 | heap [k] = heap [p]; |
822 | heap [k] = heap [p]; |
822 | ev_active (ANHE_w (heap [k])) = k; |
823 | ev_active (ANHE_w (heap [k])) = k; |
823 | k = p; |
824 | k = p; |
824 | } |
825 | } |
825 | |
826 | |
|
|
827 | heap [k] = he; |
826 | ev_active (ANHE_w (he)) = k; |
828 | ev_active (ANHE_w (he)) = k; |
827 | heap [k] = he; |
|
|
828 | } |
829 | } |
829 | |
830 | |
830 | /* away from the root */ |
831 | /* away from the root */ |
831 | void inline_speed |
832 | void inline_speed |
832 | downheap (ANHE *heap, int N, int k) |
833 | downheap (ANHE *heap, int N, int k) |
… | |
… | |
841 | ANHE *pos = heap + DHEAP * (k - HEAP0) + HEAP0; |
842 | ANHE *pos = heap + DHEAP * (k - HEAP0) + HEAP0; |
842 | |
843 | |
843 | // find minimum child |
844 | // find minimum child |
844 | if (expect_true (pos + DHEAP - 1 < E)) |
845 | if (expect_true (pos + DHEAP - 1 < E)) |
845 | { |
846 | { |
846 | /* fast path */ (minpos = pos + 0), (minat = ANHE_at (*minpos)); |
847 | /* fast path */ (minpos = pos + 0), (minat = ANHE_at (*minpos)); |
847 | 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)); |
848 | 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)); |
849 | 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)); |
850 | } |
851 | } |
851 | else if (pos < E) |
852 | else if (pos < E) |
852 | { |
853 | { |
853 | /* slow path */ (minpos = pos + 0), (minat = ANHE_at (*minpos)); |
854 | /* slow path */ (minpos = pos + 0), (minat = ANHE_at (*minpos)); |
854 | 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)); |
… | |
… | |
859 | break; |
860 | break; |
860 | |
861 | |
861 | if (ANHE_at (he) <= minat) |
862 | if (ANHE_at (he) <= minat) |
862 | break; |
863 | break; |
863 | |
864 | |
|
|
865 | heap [k] = *minpos; |
864 | ev_active (ANHE_w (*minpos)) = k; |
866 | ev_active (ANHE_w (*minpos)) = k; |
865 | heap [k] = *minpos; |
|
|
866 | |
867 | |
867 | k = minpos - heap; |
868 | k = minpos - heap; |
868 | } |
869 | } |
869 | |
870 | |
|
|
871 | heap [k] = he; |
870 | ev_active (ANHE_w (he)) = k; |
872 | ev_active (ANHE_w (he)) = k; |
871 | heap [k] = he; |
|
|
872 | } |
873 | } |
873 | |
874 | |
874 | #else // 4HEAP |
875 | #else // 4HEAP |
875 | |
876 | |
876 | #define HEAP0 1 |
877 | #define HEAP0 1 |
|
|
878 | #define HPARENT(k) ((k) >> 1) |
877 | |
879 | |
878 | /* towards the root */ |
880 | /* towards the root */ |
879 | void inline_speed |
881 | void inline_speed |
880 | upheap (ANHE *heap, int k) |
882 | upheap (ANHE *heap, int k) |
881 | { |
883 | { |
882 | ANHE he = heap [k]; |
884 | ANHE he = heap [k]; |
883 | |
885 | |
884 | for (;;) |
886 | for (;;) |
885 | { |
887 | { |
886 | int p = k >> 1; |
888 | int p = HPARENT (k); |
887 | |
889 | |
888 | /* maybe we could use a dummy element at heap [0]? */ |
890 | /* maybe we could use a dummy element at heap [0]? */ |
889 | if (!p || ANHE_at (heap [p]) <= ANHE_at (he)) |
891 | if (!p || ANHE_at (heap [p]) <= ANHE_at (he)) |
890 | break; |
892 | break; |
891 | |
893 | |
… | |
… | |
929 | #endif |
931 | #endif |
930 | |
932 | |
931 | void inline_size |
933 | void inline_size |
932 | adjustheap (ANHE *heap, int N, int k) |
934 | adjustheap (ANHE *heap, int N, int k) |
933 | { |
935 | { |
|
|
936 | if (k > HEAP0 && ANHE_at (heap [HPARENT (k)]) >= ANHE_at (heap [k])) |
934 | upheap (heap, k); |
937 | upheap (heap, k); |
|
|
938 | else |
935 | downheap (heap, N, k); |
939 | downheap (heap, N, k); |
936 | } |
940 | } |
937 | |
941 | |
938 | /*****************************************************************************/ |
942 | /*****************************************************************************/ |
939 | |
943 | |
940 | typedef struct |
944 | typedef struct |
… | |
… | |
1649 | downheap (periodics, periodiccnt, HEAP0); |
1653 | downheap (periodics, periodiccnt, HEAP0); |
1650 | } |
1654 | } |
1651 | else if (w->interval) |
1655 | else if (w->interval) |
1652 | { |
1656 | { |
1653 | 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 */ |
1654 | if (ev_at (w) - ev_rt_now <= TIME_EPSILON) ev_at (w) += w->interval; |
1660 | if (ev_at (w) - ev_rt_now < TIME_EPSILON) |
|
|
1661 | { |
|
|
1662 | ev_at (w) += w->interval; |
1655 | |
1663 | |
1656 | assert (("ev_periodic timeout in the past detected while processing timers, negative interval?", ev_at (w) >= ev_rt_now)); |
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 | } |
1657 | |
1670 | |
1658 | ANHE_at_set (periodics [HEAP0]); |
1671 | ANHE_at_set (periodics [HEAP0]); |
1659 | downheap (periodics, periodiccnt, HEAP0); |
1672 | downheap (periodics, periodiccnt, HEAP0); |
1660 | } |
1673 | } |
1661 | else |
1674 | else |