… | |
… | |
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) |
… | |
… | |
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 |