home *** CD-ROM | disk | FTP | other *** search
/ Shareware Overload / ShartewareOverload.cdr / windows / mlocal.zip / LISTMGR.ASM next >
Assembly Source File  |  1991-03-16  |  38KB  |  1,001 lines
  1. PAGE 60, 132
  2. ;------------------------------------------------------------------------------
  3. ; Linked List Manager Routines 386 only!!!!!
  4. ; Dan Quigley 11-11-90
  5. ;------------------------------------------------------------------------------
  6.  
  7. IF1
  8. %OUT Linked List Manager Routines 386 only!!!!
  9. ENDIF
  10.  
  11.  
  12. ;;;DEBUG       EQU         1
  13.  
  14. DUMP        EQU         1
  15.  
  16. IFDEF       DUMP
  17.  
  18. IF1
  19. %OUT ListMgr: dump routines enabled
  20. ENDIF
  21.  
  22. DumpOutW    MACRO       st,wTmp,wSz             ; dump word
  23.             mov         di,offset DGROUP:st
  24.             add         di, wSz
  25.             FarPtr      lpStr, es, di
  26.             cCall       Hex16Cvt <wTmp,lpStr>
  27.             ENDM
  28.  
  29. DumpOutD    MACRO       st,lpTmp,wSz            ; dump dword
  30.             mov         di,offset DGROUP:st
  31.             add         di,wSz
  32.             mov         cx,wptr lpTmp+2
  33.             cCall       Hex16Cvt <cx,es,di>
  34.             add         di,4
  35.             mov         cx,wptr lpTmp
  36.             cCall       Hex16Cvt <cx,es,di>
  37.             ENDM
  38.  
  39.                                                 ; dump far pointer
  40. DumpOutA    MACRO       st,lpTmp,wSz
  41.             mov         di,offset DGROUP:st
  42.             add         di,wSz
  43.             mov         cx,wptr lpTmp+2
  44.             cCall       Hex16Cvt <cx,es,di>
  45.             add         di,5
  46.             mov         cx,wptr lpTmp
  47.             cCall       Hex16Cvt <cx,es,di>
  48.             ENDM
  49.  
  50. DebugOut    MACRO       st                      ; dump string
  51.             pushad
  52.             mov         ax,SEG _DATA
  53.             push        ax
  54.             push        offset DGROUP:st
  55.             cCall       OUTPUTDEBUGSTRING
  56.             popad
  57.             ENDM
  58.  
  59. ENDIF       ; IFDEF DUMP
  60.  
  61. IFDEF DEBUG
  62. IF1
  63. %OUT ListMgr: debug routines enabled
  64. ENDIF
  65.  
  66. DebugBreak  MACRO
  67.             int         1
  68.             ENDM
  69. ENDIF
  70.  
  71. ;------------------------------------------------------------------------------
  72. ; Equates and structures
  73. ;------------------------------------------------------------------------------
  74. jmps        EQU         <jmp short>             ; Helper equates
  75. bptr        EQU         <byte ptr>
  76. wptr        EQU         <word ptr>
  77. dwptr       EQU         <dword ptr>
  78.  
  79. DList       struc
  80.             dwPrev      dd      ?
  81.             dwNext      dd      ?
  82. DList       ends
  83.  
  84. ListStruc   struc
  85.             wListSize   dw      ?               ; size of list record - link
  86.             dwListCount dd      ?               ; Count of records in list
  87.             hListTop    dd      ?               ; FarLocal handle to top
  88.             hListEnd    dd      ?               ; FarLocal handle to end
  89.             lpCompare   dd      ?               ; Compare proc for sort/search
  90.             hListDS     dw      ?               ; callers ds
  91. ListStruc   ends
  92.  
  93. ;------------------------------------------------------------------------------
  94. ; CMACRO Setup        
  95. ;------------------------------------------------------------------------------
  96.  
  97. .xlist                                          ; Suspend listing
  98. ?DF  = 1                                        ; Don't generate default segs
  99. ?PLM = 1                                        ; Support Pascal calling
  100. ?WIN = 1                                        ; Support WINDOWS
  101. include cmacros.inc
  102. include windows.inc
  103. .list
  104.  
  105. LISTMEM     EQU         (LMEM_FIXED OR LMEM_ZEROINIT)
  106.  
  107. ;------------------------------------------------------------------------------
  108. ; Segment definitions
  109. ;------------------------------------------------------------------------------
  110. createSeg   LISTMGR_TEXT,CODE,PARA,PUBLIC,CODE  ; Define code segment
  111.  
  112. IFDEF       DUMP
  113.  
  114. createSeg   _DATA,DATA,PARA,PUBLIC,DATA,DGROUP  ; Define data segment
  115. defGrp      DGROUP,DATA                         ; Declare DGROUP
  116. assumes     DS,DATA                             ; Tell assembler where DS is
  117.  
  118. ;------------------------------------------------------------------------------
  119. ; Global variables   
  120. ;------------------------------------------------------------------------------
  121. sBegin      DATA
  122.             staticD     holdrand,1
  123.             staticW     wNodeCount, 0
  124.             staticB     DumpHdr0,<'wListSize :         ',13,10,0>
  125.             staticB     DumpHdr1,<'dwCount   :         ',13,10,0>
  126.             staticB     DumpHdr2,<'hListTop  :    :    ',13,10,0>
  127.             staticB     DumpHdr3,<'hListEnd  :    :    ',13,10,0>
  128.             staticB     NodesHdr,<'Node        Previous      Next',13,10,0>
  129.             staticB     NodeList,<'               :         :    ',13,10,0>
  130. sEnd        DATA
  131.  
  132. ENDIF       ; IFDEF DUMP
  133.  
  134. ;------------------------------------------------------------------------------
  135. ; External procedures
  136. ;------------------------------------------------------------------------------
  137. externFP    <FARLOCALALLOC>
  138. externFP    <FARLOCALFREE>
  139. externFP    <OUTPUTDEBUGSTRING>
  140.  
  141. ;------------------------------------------------------------------------------
  142. ;------------------------------------------------------------------------------
  143. .386                                            ; Enable 386 instruction set
  144. sBegin      CODE
  145. assumes     CS,CODE                             ; Reference CS
  146.  
  147. IFDEF       DUMP
  148.  
  149. ;------------------------------------------------------------------------------
  150. ; Hex16Cvt - Converts 16-bit binary to ascii Hex
  151. ;
  152. ; Returns : Nothing
  153. ;------------------------------------------------------------------------------
  154. cProc       Hex16Cvt,<NEAR>,<es,di>
  155.             parmW       wNum
  156.             parmD       lStr
  157. cBegin
  158.             les         di, lStr
  159.             mov         dx, wNum
  160.             mov         cx, 4
  161.  
  162. HCLoop:     push        cx
  163.             mov         cl, 4
  164.             rol         dx, cl
  165.             mov         al, dl
  166.             and         al,00Fh
  167.             daa
  168.             add         al,0F0h
  169.             adc         al,040h
  170.             stosb
  171.             pop         cx
  172.             loop        HCLoop
  173. cEnd
  174.  
  175.  
  176. ;------------------------------------------------------------------------------
  177. ; DumpNode - Dumps a Node to the debug monitor
  178. ;         : bx = record length
  179. ;
  180. ; Returns : Nothing
  181. ;------------------------------------------------------------------------------
  182. cProc       DumpNode,<NEAR>,<ds,es>
  183.             parmD hNode
  184. cBegin
  185.             pushad
  186.             mov         ax,SEG _DATA
  187.             mov         es,ax
  188.             DumpOutW    NodeList, es:wNodeCount,0
  189.             lds         si, hNode
  190.             add         si, bx
  191.             DumpOutA    NodeList, [si].dwPrev, 11
  192.             DumpOutA    NodeList, [si].dwNext, 21
  193.             DebugOut    NodeList
  194.             popad
  195. cEnd
  196.  
  197. ;------------------------------------------------------------------------------
  198. ; ListDump - Dumps a list to the debug monitor
  199. ;
  200. ; Returns : Nothing
  201. ;------------------------------------------------------------------------------
  202. cProc       ListDump,<PUBLIC,FAR>,<es,ds,si,di>
  203.             parmD hList
  204. cBegin
  205.             mov         ax,SEG _DATA
  206.             mov         es,ax
  207.             mov         es:wNodeCount,1         ; initialize node counter
  208.             lds         si,hList                ; access list header
  209.  
  210.             DumpOutW    DumpHdr0,[si].wListSize,11
  211.             DumpOutD    DumpHdr1,[si].dwListCount,11
  212.             DumpOutA    DumpHdr2,[si].hListTop,11
  213.             DumpOutA    DumpHdr3,[si].hListEnd,11
  214.  
  215.             DebugOut    DumpHdr0
  216.             DebugOut    DumpHdr1
  217.             DebugOut    DumpHdr2
  218.             DebugOut    DumpHdr3
  219.             DebugOut    NodesHdr
  220.  
  221.             mov         bx,[si].wListSize
  222.             mov         eax,[si].hListTop
  223.             cmp         eax,0
  224.             je          LDExit
  225.  
  226.             cCall       DumpNode <eax>
  227.             mov         ecx,[si].hListEnd
  228.             lds         si,[si].hListTop
  229.  
  230. LDLoop:     cmp         eax,ecx                 ; are we at the end
  231.             je          LDExit                  ; yes
  232.             inc         es:wNodeCount           ; bump the node count
  233.             mov         eax,[si+bx].dwNext
  234.             lds         si,[si+bx].dwNext       ; get the next node
  235.             cCall       DumpNode <eax>
  236.             jmps        LDLoop
  237. LDExit:
  238. cEnd
  239.  
  240. ENDIF       ;IFDEF DUMP
  241.  
  242.  
  243. ;------------------------------------------------------------------------------
  244. ; ListAllocNode - Allocates memory for a new node
  245. ;
  246. ; Returns : DX:AX = Handle to node
  247. ;------------------------------------------------------------------------------
  248. cProc       ListAllocNode,<PUBLIC,FAR>,<ds,si>
  249.             parmD       hList
  250. cBegin
  251.             lds         si,hList                ; access list header
  252.             mov         bx,[si].wListSize       ; get the record size
  253.             mov         ax,[si].hListDS         ; get ds of calling app
  254.             mov         ds,ax                   ; and reset it for alloc
  255.             add         bx,size DList           ; add space for our pointers
  256.             mov         ax,LISTMEM              ; allocation flags
  257.             cCall       FARLOCALALLOC <ax,bx>   ; allocate a record
  258. cEnd
  259.  
  260. ;------------------------------------------------------------------------------
  261. ; ListCreate - Creates a linked list
  262. ;
  263. ; Returns : DX:AX = Handle to list
  264. ;------------------------------------------------------------------------------
  265. cProc       ListCreate,<PUBLIC,FAR>,<ds,si>
  266.             parmW       wRecSize
  267. cBegin
  268.             mov         ax,LISTMEM
  269.             mov         cx,size ListStruc
  270.             cCall       FARLOCALALLOC <ax,cx>   ; allocate a header
  271.             cmp         dx,0                    ; success?
  272.             je          LIExit                  ; no then exit
  273.  
  274.             push        ds                      ; save tasks ds
  275.             mov         ds,dx                   ; ds:si ---> header
  276.             mov         si,ax
  277.             mov         ax,wRecSize             ; retrieve and
  278.             test        ax,1                    ; insure word alignment
  279.             jz          LCEven                  ; for faster sorts on large
  280.             inc         ax                      ; records
  281. LCEven:     mov         [si].wListSize, ax      ; store the record size
  282.             pop         ax                      ; store the calling tasks ds
  283.             mov         [si].hListDS,ax
  284.             mov         ax,si
  285. LIExit:
  286. cEnd
  287.  
  288. ;------------------------------------------------------------------------------
  289. ; ListIsNodeLast - Test to determine if we are at the end of the list
  290. ;
  291. ; Returns : AX = TRUE if at the end of the list
  292. ;------------------------------------------------------------------------------
  293. cProc       ListIsNodeLast,<PUBLIC,FAR>,<ds,si,di>
  294.             parmD       hList
  295.             parmD       dwNode
  296. cBegin
  297.             lds         si,hList                ; access list header
  298.             mov         bx,[si].wListSize       ; get the record size
  299.             mov         eax,[si].hListEnd
  300.             cmp         eax, dwNode
  301.             je          LINLIsEnd
  302.             mov         ax, FALSE
  303.             jmps        LINLExit
  304. LINLIsEnd:  mov         ax, TRUE
  305. LINLExit:
  306. cEnd
  307.  
  308. ;------------------------------------------------------------------------------
  309. ; ListIsNodeFirst - Test to determine if we are at the top of the list
  310. ;
  311. ; Returns : AX = TRUE if at the end of the list
  312. ;------------------------------------------------------------------------------
  313. cProc       ListIsNodeFirst,<PUBLIC,FAR>,<ds,si,di>
  314.             parmD       hList
  315.             parmD       dwNode
  316. cBegin
  317.             lds         si,hList                ; access list header
  318.             mov         bx,[si].wListSize       ; get the record size
  319.             mov         eax,[si].hListTop
  320.             cmp         eax,dwNode
  321.             je          LINFIsTop
  322.             mov         ax, FALSE
  323.             jmps        LINFExit
  324. LINFIsTop:  mov         ax, TRUE
  325. LINFExit:
  326. cEnd
  327.  
  328. ;------------------------------------------------------------------------------
  329. ; ListGetFirstNode - Gets the First record in a list
  330. ;
  331. ; Returns : DX:AX Handle to the record
  332. ;------------------------------------------------------------------------------
  333. cProc       ListGetFirstNode,<PUBLIC,FAR>,<ds,si>
  334.             parmD       hList
  335. cBegin
  336.             lds         si,hList                ; access list header
  337.             cmp         dwptr [si].hListTop,0   ; is there a list yet?
  338.             je          LGFNErr
  339.             lds         si,[si].hListTop        ; get the first node
  340.             mov         ax,si
  341.             mov         dx,ds
  342.             jmps        LGFNExit
  343. LGFNErr:    mov         ax,0
  344.             mov         dx,0
  345. LGFNExit:
  346. cEnd
  347.  
  348. ;------------------------------------------------------------------------------
  349. ; ListGetNodeCount - Gets the record count in a list
  350. ;
  351. ; Returns : DX:AX count
  352. ;------------------------------------------------------------------------------
  353. cProc       ListGetNodeCount,<PUBLIC,FAR>,<ds,si>
  354.             parmD       hList
  355. cBegin
  356.             lds         si,hList                ; access list header
  357.             cmp         dwptr [si].hListTop,0   ; is there a list yet?
  358.             je          LGNCErr
  359.             mov         ax,wptr [si].dwListCount
  360.             mov         dx,wptr [si].dwListCount+2
  361.             jmps        LGNCExit
  362. LGNCErr:    mov         ax, 0
  363.             mov         dx, 0
  364. LGNCExit:
  365. cEnd
  366.  
  367.  
  368. ;------------------------------------------------------------------------------
  369. ; ListGetLastNode - Gets the Last Node in a list
  370. ;
  371. ; Returns : DX:AX Handle to the record
  372. ;------------------------------------------------------------------------------
  373. cProc       ListGetLastNode,<PUBLIC,FAR>,<ds,si>
  374.             parmD       hList
  375. cBegin
  376.             lds         si,hList                ; access list header
  377.             cmp         dwptr [si].hListEnd,0   ; is there a list yet?
  378.             je          LGLNErr
  379.             lds         si,[si].hListEnd        ; get the last node
  380.             mov         dx,ds
  381.             mov         ax,si
  382.             jmps        LGLNExit
  383. LGLNErr:    mov         ax, 0
  384.             mov         dx, 0
  385. LGLNExit:
  386. cEnd
  387.  
  388. ;------------------------------------------------------------------------------
  389. ; ListGetNextNode - Gets the Next record in a list
  390. ;
  391. ; Returns : DX:AX Handle to the record
  392. ;------------------------------------------------------------------------------
  393. cProc       ListGetNextNode,<PUBLIC,FAR>,<ds,si>
  394.             parmD       hList
  395.             parmD       dwNode
  396. cBegin
  397.  
  398. IFDEF DEBUG
  399.             DebugOut    ListGetNextNode
  400.             DebugBreak
  401. ENDIF
  402.             lds         si,hList                ; access list header
  403.             mov         bx,[si].wListSize       ; get the record size
  404.             cCall       ListIsNodeLast <hList,dwNode>
  405.             cmp         ax,0                    ; is current the last node
  406.             jne         LGNNErr                 ; yes
  407.             lds         si,dwNode               ; get the current node
  408.             lds         si,[si+bx].dwNext       ; no, load the record
  409.             mov         dx,ds
  410.             mov         ax,si
  411.             jmps        LGNNExit
  412. LGNNErr:    mov         dx,0
  413.             mov         ax,0                    ; signal failure
  414. LGNNExit:
  415. cEnd
  416.  
  417. ;------------------------------------------------------------------------------
  418. ; ListGetPrevNode - Gets the Previous record in a list
  419. ;
  420. ; Returns : DX:AX Handle to the record
  421. ;------------------------------------------------------------------------------
  422. cProc       ListGetPrevNode,<PUBLIC,FAR>,<ds,si>
  423.             parmD       hList
  424.             parmD       dwNode
  425. cBegin
  426.             lds         si,hList                ; access list header
  427.             mov         bx,[si].wListSize       ; get the record size
  428.             cCall       ListIsNodeFirst <hList,dwNode>
  429.             cmp         ax,0                    ; is this the First node
  430.             jne         LGPNErr                 ; yes
  431.             lds         si, dwNode
  432.             lds         si,[si+bx].dwPrev
  433.             mov         dx, ds
  434.             mov         ax, si
  435.             jmps        LGPNExit
  436. LGPNErr:    mov         dx,0
  437.             mov         ax,0                    ; signal failure
  438. LGPNExit:
  439. cEnd
  440.  
  441. ;------------------------------------------------------------------------------
  442. ; ListGetNode - Gets the nth record of a list
  443. ;
  444. ; Returns : DX:AX Handle to the record
  445. ;------------------------------------------------------------------------------
  446. cProc       ListGetNode,<PUBLIC,FAR>,<ds,si,di>
  447.             parmD       hList
  448.             parmD       dwNode
  449. cBegin
  450.             lds         si,hList                ; access list header
  451.             mov         bx,[si].wListSize       ; get the record size
  452.  
  453.             mov         ecx,dwNode              ; get the requested record #
  454.             jecxz       LGNPastEnd              ; zero records
  455.             cmp         ecx,[si].dwListCount    ; greater than count
  456.             ja          LGNPastEnd
  457.             lds         si,[si].hListTop        ; get the first record
  458.             dec         ecx
  459.             jz          LGNIsRec                ; just one record
  460.  
  461. LGNTop:     lds         si,[si+bx].dwNext
  462.             db          66h                     ; force LOOP on ECX
  463.             loop        LGNTop
  464.  
  465. LGNIsRec:   mov         dx, ds
  466.             mov         ax, si
  467.             jmps        LGNExit
  468.  
  469. LGNPastEnd: mov         dx, 0
  470.             mov         ax, 0                    ; assume failure
  471. LGNExit:
  472. cEnd
  473.  
  474. ;------------------------------------------------------------------------------
  475. ; ListSwapNode - Swaps positions of two nodes by copying data not pointers
  476. ;
  477. ; Returns : AX = NONZERO = Success
  478. ;------------------------------------------------------------------------------
  479. cProc       ListSwapNode,<PUBLIC,FAR>,<cx,es,ds,si,di>
  480.             parmD       hList
  481.             parmD       dwNode1
  482.             parmD       dwNode2
  483. cBegin
  484.             cmp         dwptr dwNode1,0         ; nullcheck pointer
  485.             je          LSNErr
  486.  
  487.             cmp         dwptr dwNode2,0
  488.             je          LSNErr
  489.  
  490.             lds         si,hList                ; access list header
  491.             mov         cx,[si].wListSize       ; get the record size
  492.             shr         cx,1                    ; move words
  493.             jcxz        LSNExit
  494.  
  495.             lds         si,dwNode1
  496.             les         di,dwNode2
  497.             cld                                 ; clear direction flag
  498.  
  499. LSNLoop:    mov         ax,es:[di]
  500.             xchg        [si],ax
  501.             stosw
  502.             add         si,2
  503.             loop        LSNLoop
  504.             mov         ax,TRUE                 ; signal success
  505.             jmps        LSNExit
  506.  
  507. LSNErr:     mov         ax,FALSE
  508.  
  509. LSNExit:
  510. cEnd
  511.  
  512. ;------------------------------------------------------------------------------
  513. ; ListAddNode - Adds a Node to the end of the designated list
  514. ;
  515. ; Returns : AX = NONZERO = success
  516. ;------------------------------------------------------------------------------
  517. cProc       ListAddNode,<PUBLIC,FAR>,<ds,si,di>
  518.             parmD       hList
  519.             parmD       pNode
  520. cBegin
  521.             mov         eax,pNode
  522.             cmp         eax,0                   ; null pointer check
  523.             je          LANExit
  524.             
  525.             lds         si, hList
  526.             mov         bx,[si].wListSize       ; get the record size
  527.             inc         [si].dwListCount        ; bump record count
  528.             cmp         dwptr [si].hListTop,0   ; is this the first node?
  529.             jne         LANSkip
  530.  
  531.             mov         [si].hListTop,eax       ; initialize top and end ptrs
  532.             mov         [si].hListEnd,eax       ; set the new list end
  533.             lds         si,pNode                ; address new node
  534.             mov         [si+bx].dwPrev,eax
  535.             mov         [si+bx].dwNext,eax
  536.             jmps        LANDone
  537.  
  538. LANSkip:    les         di,[si].hListEnd        ; address last record
  539.             mov         [si].hListEnd,eax       ; set the new list end
  540.             lds         si,pNode                ; address new node
  541.  
  542.             push        es:[di+bx].dwNext       ; save the last record handle
  543.             mov         es:[di+bx].dwNext,eax   ; save the new record as next
  544.             mov         [si+bx].dwNext,eax      ; last record points to itself
  545.             pop         [si+bx].dwPrev          ; former last is prev now
  546. LANDone:    mov         ax, TRUE
  547. LANExit:
  548. cEnd
  549.  
  550. ;------------------------------------------------------------------------------
  551. ; ListAllocAddNode - Allocs and Adds a Node to the end of the designated list
  552. ;                    copies the passed node parameter to the newly alloc'd
  553. ;
  554. ; Returns : AX = NONZERO = success
  555. ;------------------------------------------------------------------------------
  556. cProc       ListAllocAddNode,<PUBLIC,FAR>,<ds,si,di>
  557.             parmD       hList
  558.             parmD       pNode
  559. cBegin
  560.  
  561.             mov         eax,hList
  562.             cCall       LISTALLOCNODE <eax>
  563.             cmp         dx,0
  564.             je          LAAError
  565.  
  566.                                                     
  567.             lds         si,hList                    ; copy the passed node
  568.             mov         cx,[si].wListSize           ; to the newly alloc'd
  569.             lds         si,pNode
  570.             mov         es,dx
  571.             mov         di,ax
  572.             repnz       movsb
  573.  
  574.             cCall       LISTADDNODE <hList,dx,ax>
  575.             jmps        LAAExit
  576.  
  577. LAAError:   mov         ax, TRUE
  578. LAAExit:
  579. cEnd
  580.  
  581.  
  582.  
  583. ;------------------------------------------------------------------------------
  584. ; ListDeleteNode - Deletes a Node in designated list
  585. ;
  586. ; Returns : AX = NONZERO = success
  587. ;------------------------------------------------------------------------------
  588. cProc       ListDeleteNode,<PUBLIC,FAR>,<ds,si,di>
  589.             parmD       hList
  590.             parmD       pNode
  591. cBegin
  592.             mov         eax, pNode
  593.             cmp         eax, 0
  594.             je          LDNExit
  595.             
  596.             lds         si,hList                ; access list header
  597.             mov         edx,[si].hListEnd       ; edx ---> hListEnd
  598.  
  599.             cmp         edx,0                   ; is there no list at all
  600.             je          LDNFreNode              ; yes, just free the node
  601.  
  602.             mov         ecx,[si].hListTop       ; ecx ---> hListTop
  603.             mov         bx,[si].wListSize       ; bx  ---> wListSize
  604.  
  605.             dec         [si].dwListCount        ; decrement count
  606.  
  607.             cmp         eax,edx                 ; is this the last record
  608.             je          LDNLastRec              ; yes, then special case
  609.  
  610.             cmp         eax,ecx                 ; is this the first record
  611.             je          LDNFirstRec             ; yes, then special case
  612.  
  613.             lds         si,pNode                ; get the node to delete
  614.             mov         eax,[si+bx].dwNext      ; eax has next
  615.             mov         ecx,[si+bx].dwPrev      ; ecx has prev
  616.             les         di,[si+bx].dwPrev       ; access previous record
  617.             lds         si,[si+bx].dwNext       ; access next record
  618.  
  619.             mov         es:[di+bx].dwNext,eax   ; swap pointers
  620.             mov         [si+bx].dwPrev,ecx
  621.             jmps        LDNFreNode              ; go free the node
  622.  
  623. LDNLastRec: cmp         eax,ecx                 ; is the record the top
  624.             je          LDNFinalRec             ; yes, then is the last
  625.  
  626.             les         di,pNode                ; get the node to delete
  627.             mov         eax,es:[di+bx].dwPrev   ; eax gets previous
  628.             les         di,es:[di+bx].dwPrev    ; access previous record
  629.             mov         [si].hListEnd,eax       ; reset the end of list
  630.             mov         es:[di+bx].dwNext,eax   ; next = itself for last
  631.             jmps        LDNFreNode
  632.  
  633. LDNFirstRec:cmp         eax,edx                 ; is the record the last
  634.             je          LDNFinalRec             ; yes, then is the last
  635.  
  636.             les         di,pNode                ; get the node to delete
  637.             mov         eax,es:[di+bx].dwNext   ; eax gets previous
  638.             les         di,es:[di+bx].dwNext    ; access next record
  639.             mov         [si].hListTop,eax       ; reset top of list
  640.             mov         es:[di+bx].dwPrev,eax   ; prev = itself for top
  641.             jmps        LDNFreNode
  642.  
  643. LDNFinalRec:mov         dwptr [si].hListTop,0   ; only executed if
  644.             mov         dwptr [si].hListEnd,0   ; final record is freed
  645.  
  646. LDNFreNode: lds         si,hList                ; access list header again
  647.             mov         ax,[si].hListDS         ; restore callers ds
  648.             mov         ds,ax
  649.             cCall       FARLOCALFREE <pNode>    ; free the node
  650. LDNExit:
  651. cEnd
  652.  
  653. ;------------------------------------------------------------------------------
  654. ; ListInsertNode - Inserts a Node in designated list before AtNode
  655. ;
  656. ; Returns : AX = NONZERO = success
  657. ;------------------------------------------------------------------------------
  658. cProc       ListInsertNode,<PUBLIC,FAR>,<ds,si,di>
  659.             parmD       hList
  660.             parmD       lpAtNode
  661.             parmD       pNode
  662. cBegin
  663.             mov         ax, 0
  664.             cmp         dwptr pNode,0           ; proof ptrs
  665.             je          LINExit
  666.             cmp         dwptr lpAtNode,0
  667.             je          LINExit
  668.  
  669.             lds         si,hList                ; access list header
  670.             mov         bx,[si].wListSize       ; get the record size
  671.             inc         [si].dwListCount        ; increment count
  672.  
  673.             mov         eax,lpAtNode            ; get ptr to At Node
  674.             cmp         eax,[si].hListTop       ; is this the first record
  675.             mov         eax,pNode               ; get ptr to InsNode
  676.             je          LINTopNode              ; yes, handle differently
  677.  
  678.             lds         si,lpAtNode             ; access at node
  679.             les         di,[si+bx].dwPrev       ; access prev node
  680.  
  681.             mov         eax,pNode               ; get ptr to InsNode
  682.             push        dwptr es:[di+bx].dwNext ; push prev/next pointer
  683.             mov         es:[di+bx].dwNext,eax   ; store the ptr to insnode
  684.  
  685.             push        dwptr [si+bx].dwPrev    ; push at/prev pointer
  686.             mov         [si+bx].dwPrev,eax      ; our record is in
  687.             lds         si, pNode
  688.  
  689.             pop         dwptr [si+bx].dwPrev    ; pop the prev/next ptr
  690.             pop         dwptr [si+bx].dwNext    ; pop the at/prev ptr
  691.             mov         ax,1                    ; done
  692.             jmps        LINExit
  693.  
  694. LINTopNode: les         di,[si].hListTop        ; es:di has TopNode
  695.             push        dwptr [si].hListTop     ; save the TopNode ptr
  696.             mov         [si].hListTop,eax       ; our record is new list top
  697.             lds         si,pNode                ; get our record
  698.             mov         [si+bx].dwPrev,eax      ; Top's Prev points to itself
  699.             pop         [si+bx].dwNext          ; Next is oldTop
  700.             mov         es:[di+bx].dwPrev,eax   ; OldTop's prev is our new
  701.             mov         ax,1                    ; Done
  702.  
  703. LINExit:
  704. cEnd
  705.  
  706. ;------------------------------------------------------------------------------
  707. ; ListFree - Frees a linked list
  708. ;
  709. ; Returns  : Nothing
  710. ;------------------------------------------------------------------------------
  711. cProc       ListFree,<PUBLIC,FAR>,<ds,di,si>
  712.             parmD       hList
  713. cBegin
  714.             lds         si, hList
  715.  
  716. LFLoop:     cmp         dwptr [si].hListTop, 0
  717.             je          LFExit
  718.             cCall       ListDeleteNode <hList, [si].hListTop>
  719.             jmps        LFLoop
  720.  
  721. LFExit:     mov         ax,[si].hListDS
  722.             mov         ds,ax
  723.             cCall       FARLOCALFREE <hList>
  724. cEnd
  725.  
  726. ;------------------------------------------------------------------------------
  727. ; ListQSort - Sorts a linked list with a users compare routine
  728. ;
  729. ; Returns  : Nothing
  730. ;
  731. ;   0. do minimal checks on arguments
  732. ;   1. check to see if array needs sorting
  733. ;   2. start QuickSort
  734. ;------------------------------------------------------------------------------
  735. cProc       ListQSort,<PUBLIC, FAR>,<ds,si,di>
  736.             parmD       hList
  737.             parmD       compare
  738. cBegin
  739.             lds         si, hList
  740.             mov         ecx,[si].dwListCount
  741.  
  742.             jecxz       QsortDone           ; ecx = 0 => list has no elements
  743.  
  744.             dec         ecx
  745.             jz          QsortDone           ; ecx = 0 => list has only 1 element
  746.  
  747.             mov         bx,[si].wListSize   ; size of records in list
  748.             les         di,[si].hListTop    ; first record = es:di
  749.  
  750.             ;  1. check to see if array needs sorting
  751.  
  752. CheckLoop:  push        ecx                 ; see if array is already sorted
  753.             push        bx                  ; save necessary registers
  754.             push        es
  755.  
  756.             push        dwptr es:[di+bx].dwNext; pass the next pointer
  757.             push        es
  758.             push        di                  ; pass the current pointer
  759.             call        dwptr compare       ; call the users compare routine
  760.  
  761.             pop         es
  762.             pop         bx
  763.             pop         ecx
  764.  
  765.             or          ax,ax               ; if ax is negative i.e. < 0 then
  766.             js          Need2Sort           ; do QuickSort
  767.  
  768.             les         di,es:[di+bx].dwNext ; get next node
  769.             loop        CheckLoop
  770.             jmps        QSortDone
  771.  
  772. Need2Sort:  mov         eax,compare
  773.             mov         [si].lpCompare,eax
  774.             mov         eax,1
  775.             cCall       QuickSort <eax, [si].dwListCount>
  776. QSortDone:
  777. cEnd
  778.  
  779. ;------------------------------------------------------------------------------
  780. ; Random - Generates a pseudorandom integer between Low and High
  781. ; Returns : EAX pseudorandom int
  782. ;------------------------------------------------------------------------------
  783. cProc       Random,<NEAR>,<ds>
  784.             parmD       dwLow
  785.             parmD       dwHigh
  786. cBegin
  787.             push        ecx
  788.             push        edx
  789.             mov         ax, SEG _DATA
  790.             mov         ds,ax
  791.             mov         eax,holdrand
  792.             mov         ecx,214013
  793.             mul         ecx
  794.             add         eax,2531011
  795.             mov         holdrand,eax
  796.             shr         eax,16
  797.             and         ax,7FFFh
  798.             mov         ecx,dwHigh
  799.             sub         ecx,dwLow
  800.             cdq
  801.             div         ecx
  802.             add         edx,dwLow
  803.             mov         eax,edx
  804.             pop         edx
  805.             pop         ecx
  806. cEnd
  807.  
  808.  
  809. ;------------------------------------------------------------------------------
  810. ; FastGetNode - Gets the nth record of a list
  811. ;           NO Error Checking!!!
  812. ;           DS:SI header
  813. ;           BX    List Size
  814. ; Returns : DX:AX Handle to the record
  815. ;------------------------------------------------------------------------------
  816. cProc       FastGetNode,<NEAR>,<ds,si>
  817.             parmD       dwNode
  818. cBegin
  819.             push        ecx
  820.             mov         ecx,dwNode
  821.             mov         bx,[si].wListSize
  822.             lds         si,[si].hListTop
  823.             dec         ecx
  824.             jz          FGNDone
  825.  
  826. FGNTop:     lds         si,[si+bx].dwNext
  827.             db          66h                     ; force LOOP on ECX
  828.             loop        FGNTop
  829.  
  830. FGNDone:    mov         dx,ds
  831.             mov         ax,si
  832.             pop         ecx
  833. cEnd
  834.  
  835.  
  836. ;------------------------------------------------------------------------------
  837. ; CallCompare - Calls the user supplied compare routine with pointers
  838. ;
  839. ; ON ENTRY : DS:SI      List Header
  840. ; Returns  : Nothing
  841. ;------------------------------------------------------------------------------
  842. cProc       CallCompare,<NEAR>,<es,ds,si,di>
  843.             parmD       Record1
  844.             parmD       Record2
  845. cBegin
  846.             push        edx
  847.             cCall       FastGetNode <Record1>
  848.             push        dx
  849.             push        ax
  850.             cCall       FastGetNode <Record2>
  851.             push        dx
  852.             push        ax
  853.             call        dwptr [si].lpCompare
  854.             pop         edx
  855. cEnd
  856.  
  857. ;------------------------------------------------------------------------------
  858. ; SwapNode - Swaps the two records associated with the indexes
  859. ;
  860. ; ON ENTRY : DS:SI      List Header
  861. ; Returns  : Nothing
  862. ;------------------------------------------------------------------------------
  863. cProc       SwapNode,<NEAR>,<es,ds,si,di>
  864.             parmD       Record1
  865.             parmD       Record2
  866. cBegin
  867.             push        eax
  868.             push        edx
  869.  
  870.             push        ds                      ; hList
  871.             push        si
  872.             cCall       FastGetNode <Record1>
  873.             push        dx                      ; lpRecord1
  874.             push        ax
  875.             cCall       FastGetNode <Record2>
  876.             push        dx                      ; lpRecord2
  877.             push        ax
  878.             cCall       ListSwapNode
  879.  
  880.             pop         edx
  881.             pop         eax
  882. cEnd
  883.  
  884. ;------------------------------------------------------------------------------
  885. ;   QuickSort (Low, High)
  886. ;
  887. ;   ON ENTRY:   DS:SI   List Header
  888. ;
  889. ;   QuickSort works by picking a random "pivot" record in hList, then
  890. ;   moving every record that is bigger to one side of the pivot, and every
  891. ;   record that is smaller to the other side.  QuickSort is then called
  892. ;   recursively with the two subdivisions created by the pivot.  Once the
  893. ;   number of elements in a subdivision reaches two, the recursive calls end
  894. ;   and the list is sorted.
  895. ;------------------------------------------------------------------------------
  896. cProc       QuickSort,<NEAR>,<eax>
  897.             parmD       LowPtr
  898.             parmD       HighPtr
  899. cBegin
  900.  
  901.             mov         eax,HighPtr            ; if (LowPtr < HighPtr)
  902.             cmp         eax,LowPtr
  903.             jbe         QSExit
  904.  
  905.  
  906.             sub         eax,LowPtr             ; if (HighPtr - LowPtr) = 1
  907.             cmp         eax,1
  908.             jne         else1
  909.  
  910.             ; Only two elements in this subdivision swap them if they are out
  911.             ; order, then end recursive calls
  912.             
  913.             cCall       CallCompare <LowPtr, HighPtr>
  914.             cmp         ax,1
  915.             jne         QSExit
  916.  
  917.             ; (if [LowPtr] > [HighPtr])
  918.             ;   swap(LowPtr, HighPtr)
  919.  
  920.             cCall       SwapNode <LowPtr, HighPtr>
  921.             jmp         QSExit
  922.  
  923. else1:      ; ELSE
  924.  
  925.             ; Pick a pivot record, then move it to the end:
  926.             cCall       Random <LowPtr, HighPtr>
  927.             
  928.             cCall       SwapNode <eax, HighPtr>
  929.  
  930. do1:        ; DO
  931.  
  932.             ; Move in from both sides towards the pivot element:
  933.             mov         eax,LowPtr      ; I = LowPtr
  934.             mov         edx,HighPtr     ; J = HighPtr
  935.  
  936. do2:        cmp         eax,edx         ; DO WHILE (I < J)
  937.             jge         enddo2
  938.  
  939.             push        eax             ;    AND ([I] <= [pivot])
  940.             cCall       CallCompare <eax, HighPtr>
  941.             cmp         ax,1
  942.             pop         eax
  943.             je          enddo2
  944.  
  945.             inc         eax             ;    I = I + 1
  946.             jmps        do2
  947. enddo2:
  948.  
  949. do3:        cmp         edx,eax         ; DO WHILE (J > I)
  950.             jbe         enddo3
  951.  
  952.             push        eax             ;    AND ([J] >= [pivot])
  953.             cCall       CallCompare <edx, HighPtr>
  954.             cmp         ax,-1
  955.             pop         eax
  956.             je          enddo3
  957.             
  958.             dec         edx             ;    J = J - 1
  959.             jmps        do3
  960. enddo3:
  961.  
  962.             ; If we haven't reached the pivot element, it means that two
  963.             ; elements on either side are out of order, so swap them:
  964.             cmp         eax,edx         ;    IF I < J
  965.             jge         enddo1
  966.  
  967.             cCall       SwapNode <eax, edx>
  968.  
  969. enddo1:     cmp         eax,edx
  970.             jb          do1             ; LOOP WHILE I < J
  971.  
  972.             ; Move the pivot element back to its proper place in the array:
  973.             cCall       SwapNode <eax, HighPtr>
  974.  
  975.             ; Recursively call QuickSort
  976.  
  977.             push        eax
  978.  
  979.             push        dwptr LowPtr
  980.             dec         eax
  981.             push        eax
  982.             call        QuickSort       ; QuickSort (LowPtr, I - 1)
  983.  
  984.             pop         eax
  985.             push        eax
  986.  
  987.             inc         eax
  988.             push        eax
  989.             push        dwptr HighPtr
  990.             call        QuickSort       ; QuickSort (I + 1, HighPtr)
  991.  
  992.             pop         eax
  993.  
  994. QSExit:
  995. cEnd
  996.  
  997. sEnd        CODE
  998. END
  999.  
  1000.  
  1001.