home *** CD-ROM | disk | FTP | other *** search
/ C!T ROM 5 / ctrom5b.zip / ctrom5b / PROGRAM / ASM / ALIB30B / SORT22.ASM < prev    next >
Assembly Source File  |  1994-11-13  |  5KB  |  206 lines
  1. ;***************************** SORT22.ASM ***********************************
  2.  
  3. LIBSEG           segment byte public "LIB"
  4.         assume cs:LIBSEG , ds:nothing
  5.  
  6. ;----------------------------------------------------------------------------
  7. .xlist
  8.     include  mac.inc
  9.     include  common.inc
  10.     extrn    index_length:word
  11.     extrn    sort_column:word
  12.     extrn    sort_field_len:word
  13.     extrn    last_sort_column:word
  14.     extrn    dos_mem_allocate:far
  15.     extrn    dos_mem_release:far
  16. .list
  17. comment 
  18. ;- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -(  SORT   )
  19. ; merge_sort - sort indexed buffer. 
  20. ;  inputs:  ds:0 - ptr to index struc. <word buf_ptr>, <word record_length>
  21. ;           es:   - buffer seg,(index has offsets)
  22. ;              cx - length of sort field
  23. ;           cs:sort_column - starting column of sort field
  24. ;
  25. ;  Output:  index structure is sorted in decending order
  26. ;
  27. ;  Notes:   The index must have at least one entry.
  28. ;           Short or empty records are placed at top of index without
  29. ;           attempting to sort.
  30. ;
  31. ;****************************
  32. 
  33.  
  34. data_buffer_seg        dw    0    ;contains data to be sorted
  35. work_seg        dw    0    ;temp index sort area
  36.  
  37. delta            dw    0
  38. no_sort_flag        db    0    ;set =1 if no sort in merge pass
  39. sorted_flag        db    0    ;set =1 if index already sorted
  40.  
  41.     public    merge_sort              
  42. merge_sort    proc    near
  43.     cld
  44.     cmp    cs:index_length,4
  45.     jbe    sort_exit
  46.     mov    cs:sorted_flag,1    ;preload already sorted flag
  47.     mov    cs:data_buffer_seg,es
  48.     mov    dx,cs:sort_column
  49.     add    dx,cx
  50.     mov    cs:last_sort_column,dx
  51. ;
  52. ; allocate work area to sort index
  53. ;
  54.     mov    dx,0
  55.     mov    ax,cs:index_length
  56.     call    dos_mem_allocate
  57.     mov    cs:work_seg,es
  58.     
  59.     mov    cs:delta,4
  60.  
  61. lp1:    mov    ax,cs:delta
  62.     cmp    ax,cs:index_length
  63.     jae    ms_done            ;jmp if done
  64.  
  65.     mov    cs:move_ptr,0        ;temp index ptr for 'merge' routine
  66.  
  67.     mov    bx,0            ;set bx at top of buffer
  68.     mov    bp,cs:delta
  69. lp2:    cmp    bx,cs:index_length
  70.     jae    ms_4            ;jmp if lp2 done
  71.     call    merge
  72.     add    bx,cs:delta
  73.     add    bp,cs:delta
  74.     mov    cl,cs:no_sort_flag    ;get 1 if no sort occured
  75.     and    cs:sorted_flag,cl    ;keep 1 in sorted_flag if block sorted
  76.     jmp    lp2
  77. ;
  78. ; move the temp index back to origional
  79. ;    
  80. ms_4:    cmp    cs:sorted_flag,1
  81.     je    ms_done            ;jmp if no sort needed
  82.     
  83.     shl    cs:delta,1        ;delta * 2
  84.     mov    cx,cs:index_length    ;get length of move
  85.     shr    cx,1            ;length
  86.     mov    di,0            ;destination
  87.     mov    si,0            ;source
  88.     push    ds
  89.     pop    es
  90.     mov    ds,cs:work_seg
  91.     rep    movsw            ;move work index -> origional index
  92.     push    es
  93.     pop    ds            ;restore origional index seg
  94.     jmp    lp1
  95.  
  96. ms_done:
  97.     mov    es,cs:work_seg
  98.     call    dos_mem_release    
  99. sort_exit:    
  100.     ret
  101. merge_sort    endp
  102.  
  103. ;--------------------------------------------------------------------
  104. ; MERGE - combine two sorted lists
  105. ;   inputs:  ds:bx = list1 index top
  106. ;            ds:bp = list2 index top, (may have -1 terminator)
  107. ;          cs:delta = length of each list
  108. ;          cs:data_buffer_seg = segment of data area
  109. ;          cs:work_seg = segment of work area
  110. ;          cs:sort_field_len
  111. ;          cs:sort_column
  112. ;
  113. ;  output: bx,bp updated to end of field
  114. ;
  115. list1_length    dw    0
  116. list2_length    dw    0
  117. move_ptr    dw    0    ;current store posn in work_seg
  118. ds_save        dw    0
  119.  
  120. merge:    mov    cs:ds_save,ds
  121.     mov    cs:no_sort_flag,0    ;preload data unsorted state
  122.     mov    ax,cs:delta        ;get list1 length
  123.     mov    cs:list1_length,ax    ;set list1 length
  124.     mov    cs:list2_length,ax    ;set list2 length
  125.     
  126. m_lp:    cmp    word ptr cs:list1_length,0
  127.     je    sort2_only
  128.     cmp    word ptr cs:list2_length,0
  129.     je    move1
  130.     cmp    word ptr ds:[bp],-1
  131.     je    move1            ;jmp if list2 empty
  132.     cmp    bp,cs:index_length
  133.     jae    move1
  134. ;
  135. ; list1 & list2 have data, look for short records
  136. ;
  137.     mov    si,word ptr ds:[bx]    ;get list1 record ptr
  138.     add    si,cs:sort_column    ;move to sort point
  139.     mov    ax,word ptr ds:[bx+2]    ;get length of record
  140.     cmp    ax,cs:last_sort_column    ;check if short record
  141.     jb    move1            ;jmp if list1 record short
  142. ;
  143. ; list1 has valid data, si = data buffer ptr
  144. ;
  145.     mov    di,word ptr ds:[bp]    ;get list2 record ptr
  146.     add    di,cs:sort_column    ;move to sort point
  147.     mov    ax,word ptr ds:[bp+2]    ;get record lenght
  148.     cmp    ax,cs:last_sort_column    ;check if short record
  149.     jb    move2            ;jmp if list2 record short
  150. ;
  151. ; both lists have valid records, do compare
  152. ;
  153.     mov    cx,cs:cs:data_buffer_seg
  154.     mov    ds,cx
  155.     mov    es,cx
  156.     mov    cx,cs:sort_field_len
  157.     repe    cmpsb
  158.     mov    ds,cs:ds_save        ;restore index seg
  159.     ja    move2            ;jmp if list2 data smaller
  160.     jmp    move1            ;jmp if list1 data smaller    
  161. ;
  162. ; list1 is empty, check list2
  163. ;
  164. sort2_only:
  165.     cmp    cs:list2_length,0
  166.     je    merge_done1        ;jmp if end of both lists
  167. ;
  168. ; check if no sort was needed for list1, (everything already sorted)
  169. ;
  170.     mov    cx,cs:list2_length
  171.     cmp    cx,cs:delta        ;has list2 data been merged
  172.     jne    sort2_cont        ;jmp if merge occured
  173.     mov    cs:no_sort_flag,1    ;set no sort this pass flag
  174. sort2_cont:    
  175.     cmp    word ptr ds:[bp],-1
  176.     je    merge_done1        ;jmp if end of both lists
  177. ;
  178. ; list2 has data move it
  179. ;
  180. move2:    mov    ax,word ptr ds:[bp]    ;get record ptr
  181.     mov    dx,word ptr ds:[bp+2]    ;get record length
  182.     add    bp,4
  183.     sub    cs:list2_length,4
  184.     jmp    do_move
  185. ;
  186. ; list1 has data move it
  187. ;
  188. move1:    mov    ax,word ptr ds:[bx]    ;get record ptr
  189.     mov    dx,word ptr ds:[bx+2]    ;get record length
  190.     add    bx,4
  191.     sub    cs:list1_length,4
  192. do_move:mov    di,cs:move_ptr
  193.     mov    es,cs:work_seg
  194.     stosw
  195.     mov    ax,dx
  196.     stosw
  197.     mov    cs:move_ptr,di
  198.     jmp    m_lp
  199. ;
  200. merge_done1:
  201.     ret
  202.  
  203. ;
  204. LIBSEG    ENDS
  205.     end
  206.