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

Comparing libev/ev.c (file contents):
Revision 1.246 by root, Wed May 21 12:51:38 2008 UTC vs.
Revision 1.247 by root, Wed May 21 21:22:10 2008 UTC

… …
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 */
809void inline_speed 810void inline_speed
810upheap (ANHE *heap, int k) 811upheap (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 */
831void inline_speed 832void inline_speed
832downheap (ANHE *heap, int N, int k) 833downheap (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 */
879void inline_speed 881void inline_speed
880upheap (ANHE *heap, int k) 882upheap (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
931void inline_size 933void inline_size
932adjustheap (ANHE *heap, int N, int k) 934adjustheap (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
940typedef struct 944typedef struct

Diff Legend

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