1; void adt_HeapSiftDown(uint start, void **array, uint n, void *compare) 2; 03.2003, 08.2005 aralbrec 3 4SECTION code_clib 5PUBLIC ADTHeapSiftDown 6EXTERN l_jpix 7 8; enter: DE = start index * 2 (offset into array in bytes) 9; BC = array address 10; IX = compare (de) < (hl)? set carry if true MUST PRESERVE BC,DE,HL,IX 11; HL = N * 2 (number of items in array * 2) 12; uses : AF,DE,HL,AF' 13 14 15.ADTHeapSiftDown 16 push hl ; stack = N * 2 17 ld l,e 18 ld h,d 19 add hl,hl 20 ex de,hl ; de = child index * 2 21 add hl,bc 22 ex (sp),hl ; hl = N * 2, stack = &array[parent] 23 24; de = child index * 2 25; hl = N * 2 26; bc = array address 27; stack = &array[parent] 28 29.while 30 ld a,d ; if child < N not done yet 31 cp h 32 jr c, cont 33 jr nz, done 34 ld a,e 35 cp l 36 jr nc, done 37 38.cont 39 ex (sp),hl 40 push hl 41 push de ; stack = N * 2, &array[parent], child index * 2 42 43 ex de,hl 44 add hl,bc 45 ld e,l 46 ld d,h ; de = &array[child] 47 inc hl 48 inc hl ; hl = &array[child+1] 49 call l_jpix ; is child < child+1? (de) < (hl)? 50 pop hl 51 jr c, skip ; branch if child smaller 52 inc hl 53 inc hl ; hl = child+1 index * 2 54 inc de 55 inc de ; de = &array[child+1] 56 57.skip ; hl = child index * 2; de = &array[child]; stack = N * 2, &array[parent] 58 ex (sp),hl ; hl = &array[parent]; stack = N * 2, child index * 2 59 call l_jpix ; is child < parent? (de) < (hl) 60 jr nc, done2 ; if parent smaller it's in right place so done 61 62 ld a,(de) ; swap(child, parent) 63 ex af,af 64 ld a,(hl) 65 ld (de),a 66 ex af,af 67 ld (hl),a 68 inc hl 69 inc de 70 ld a,(de) 71 ex af,af 72 ld a,(hl) 73 ld (de),a 74 ex af,af 75 ld (hl),a 76 77 pop hl 78 add hl,hl ; hl = new child index * 2 79 dec de ; de = &array[new parent which was old child] 80 ex de,hl ; hl = &array[parent], de = child index * 2 81 ex (sp),hl ; hl = N * 2, stack = &array[parent] 82 jp while 83 84.done ; one last item to worry about 85 sbc hl,de ; carry reset at this point 86 jr nz, reallydone ; if child != N we are really done, otherwise one more compare to do 87 88 ex de,hl 89 add hl,bc ; hl = &array[child] 90 pop de ; de = &array[parent] 91 ex de,hl ; hl = &array[parent], de = &array[child] 92 call l_jpix ; is child < parent? (de) < (hl)? 93 ret nc ; if no, things are as they should be 94 95 ld a,(de) ; swap(child, parent) 96 ex af,af 97 ld a,(hl) 98 ld (de),a 99 ex af,af 100 ld (hl),a 101 inc hl 102 inc de 103 ld a,(de) 104 ex af,af 105 ld a,(hl) 106 ld (de),a 107 ex af,af 108 ld (hl),a 109 ret 110 111.done2 112 pop af 113.reallydone 114 pop af 115 ret 116