Liren Large Software Subsidy 7

home *** CD-ROM | disk | FTP | other *** search

/ Liren Large Software Subsidy 7 / 07.iso / c / c065 / 2.ddi / CLIB2.ZIP / FARHEAP.ASM < prev next >

Wrap

Assembly Source File | 1990-06-07 | 22.3 KB | 744 lines

;[]-----------------------------------------------------------------[] ;| FARHEAP.ASM | ;| | ;| Turbo-C Run Time Library Version 3.0 | ;| | ;| Copyright (c) 1987,1988,1990 by Borland International Inc. | ;| All Rights Reserved. | ;[]-----------------------------------------------------------------[] INCLUDE RULES.ASI LOCALS INCLUDE _HEAP.INC ;----------------------------------------------------------------------- ; Memory Block Header (far heap) ;----------------------------------------------------------------------- ; Each block in the heap, whether allocated or free, has a header. ; For an allocated block, only the first two fields of the header are ; used. For a free block all ten bytes are used. Blocks are aligned on ; paragraph boundaries, thus the smallest possible block sixteen bytes. ; ; Field Description ; --------- ---------------------------------------------------------- ; size total size, in paragraphs, of this block ; prev_real segment of the physically previous block in the heap ; prev_real is 0 this block is free, get the prev_real from prev_real2 ; prev_free segment of the logically previous free block ; next_free segment of the logically next free block ; prev_real2 segment of the physically previous block in the heap ; free_space first byte of free space available ; ; A doubly-linked queue is maintained of the free blocks and it is important ; to know that ordering of the blocks in this queue is logical rather than ; physical. If there is only one free block on the heap prev_free and ; next_free point to itself. ;----------------------------------------------------------------------- bsize EQU 0 prev_real EQU 2 prev_free EQU 4 next_free EQU 6 prev_real2 EQU 8 free_space EQU 10 ;----------------------------------------------------------------------- ; heapinfo structure (far heap) ;----------------------------------------------------------------------- ; Used by the heapwalk function. ; heapwalk accepts a pointer to a struct of this type. ; On entry, the pointer field contains the address of the previous ; memory block in the heap (NULL for the first call). The next block ; in the heap is then found and its address is stored in the structure ; along with its size, in bytes, and a 'used' flag. ;----------------------------------------------------------------------- HeapInfo STRUC hi_ptr dd ? hi_size dd ? hi_inuse dw ? ENDS UsedHeaderSize EQU 4 FreeHeaderSize EQU 10 EXTRN __brk:NEAR, __sbrk:NEAR _TEXT SEGMENT PUBLIC 'CODE' ASSUME CS:_TEXT ;----------------------------------------------------------------------- ; Only three variables are needed to efficiently manage the heap. ; These reside in our own code segment for speed. ; We also set aside some scratch save areas. ;----------------------------------------------------------------------- PUBLIC ___first,___last,___rover ALIGN 2 ___first dw 0 ;segment of the first block ___last dw 0 ;segment of the last block ___rover dw 0 ;segment of an arbitrary free block data_seg dw ? ;old ds save area save_hi dw ? ;for realloc save_lo dw ? ;----------------------------------------------------------------------------- ; Frees the last block on the heap ; free helper function ;----------------------------------------------------------------------------- ; Args: Pointer to the block (dx) ; Returns: void ;----------------------------------------------------------------------------- FreeLastBlock PROC NEAR cmp dx,cs:[___first] ;are we freeing the ONLY block? je @@KillHeap mov ds,dx mov ds,ds:[prev_real] ;ds = next-to-last block cmp WORD PTR ds:[prev_real],0 ;is the previous block used? je @@PreviousBlockIsFree @@PreviousBlockIsUsed: mov cs:___last,ds jmp short @@Cleanup1 @@PreviousBlockIsFree: mov ax,ds cmp ax,cs:[___first] ;is the previous block the je @@ResetHeap ;first block in the heap? mov ax,ds:[prev_real2] mov cs:___last,ax push ds ;save for call to __brk xor ax,ax push ax call PullFreeBlock mov ds,cs:[data_seg] jmp short @@Cleanup2 @@ResetHeap: mov dx,cs:[___first] @@KillHeap: mov cs:___first,0 mov cs:___last,0 mov cs:___rover,0 @@Cleanup1: mov ds,cs:[data_seg] push dx xor ax,ax push ax @@Cleanup2: call __brk ;reset the break level pop ax ;cleanup stack pop ax ret ENDP ;----------------------------------------------------------------------------- ; Frees an interior block from within the heap ; free helper function ;----------------------------------------------------------------------------- ; Args: Pointer to the block (dx) ; Returns: void ;----------------------------------------------------------------------------- FreeInnerBlock PROC NEAR mov ds,dx ;ds = block to free push ds ;save block address mov es,ds:[prev_real] ;es = previous block mov WORD PTR ds:[prev_real],0 ;mark the block as free mov ds:[prev_real2],es cmp dx,cs:[___first] ;freeing first block? je @@PreviousBlockIsUsed cmp WORD PTR es:[prev_real],0 ;is the previous block free? jne @@PreviousBlockIsUsed @@PreviousBlockIsFree: mov ax,ds:[bsize] ;ax = size of this block pop bx push es add es:[bsize],ax ;add it to the previous block mov cx,es ;cx = previous block add dx,ax ;dx = next block mov es,dx ;es = next block cmp WORD PTR es:[prev_real],0 jne @@NextBlockIsUsed @@NextBlockIsFree: mov es:[prev_real2],cx jmp SHORT @@CheckNextBlock @@NextBlockIsUsed: mov es:[prev_real],cx jmp SHORT @@CheckNextBlock @@PreviousBlockIsUsed: call InsertFreeBlock @@CheckNextBlock: pop es ;es = retrieve block mov ax,es ;ax = block add ax,es:[bsize] ;ax = next block mov ds,ax ;ds = next block cmp WORD PTR ds:[prev_real],0 ;is next block free? je JoinFreeBlocks @@AllDone: ret ENDP ;----------------------------------------------------------------------------- ; Joins two physically adjacent free blocks together ; free helper function ;----------------------------------------------------------------------------- ; Args: Pointer to the lower block (es) ; Pointer to the upper block (ds) ; Returns: void ; This routine falls through to PullFreeBlock ;----------------------------------------------------------------------------- JoinFreeBlocks PROC NEAR mov ax,ds:[bsize] ;ax = size of upper block add es:[bsize],ax ;add it to lower block size mov ax,es ;ax = lower block mov bx,ds ;bx = upper block add bx,ds:[bsize] ;bx = next block mov es,bx ;es = next block mov es:[prev_real],ax ;fixup link ;;;; jmp SHORT PullFreeBlock ENDP ;----------------------------------------------------------------------------- ; Removes a block from the free block queue ; free helper function ; malloc helper function ;----------------------------------------------------------------------------- ; Args: Pointer to the block (ds) ; Returns: void ;----------------------------------------------------------------------------- PullFreeBlock PROC NEAR mov bx,ds ;bx = this block cmp bx,ds:[next_free] ;only ONE free block? je @@NoFreeBlocks mov es,ds:[next_free] ;es = next free block mov ds,ds:[prev_free] ;ds = previous free block mov ds:[next_free],es mov es:[prev_free],ds mov cs:___rover,ds mov ds,bx ret @@NoFreeBlocks: mov cs:___rover,0 ret ENDP ;----------------------------------------------------------------------------- ; Inserts a block into the free block queue ; free helper function ;----------------------------------------------------------------------------- ; Args: Pointer to the block (ds) ; Returns: void ;----------------------------------------------------------------------------- InsertFreeBlock PROC NEAR mov ax,cs:[___rover] ;ax = rover pointer or ax,ax ;no free blocks? jz @@firstFreeBlock mov bx,ss ;save ss cli ;XXXXXXXXXXXXXXXXXXXXX mov ss,ax ;ss = rover pointer mov es,ss:[next_free] ;es = next free block mov ss:next_free,ds ;fixup links mov ds:prev_free,ss mov ss,bx ;restore ss sti ;XXXXXXXXXXXXXXXXXXXXX mov es:prev_free,ds mov ds:next_free,es ret @@FirstFreeBlock: mov cs:___rover,ds mov ds:[prev_free],ds mov ds:[next_free],ds ret ENDP ;----------------------------------------------------------------------------- ; C callable function to free a memory block ;----------------------------------------------------------------------------- ; Args: Pointer to the block to free (stack) ; Returns: void ;----------------------------------------------------------------------------- IF LDATA PUBLIC _free _free LABEL DIST ENDIF PUBLIC _farfree _farfree PROC DIST ARG O:word, S:word push bp mov bp,sp push si push di mov cs:data_seg,ds mov dx,[S] ;dx = segment to free or dx,dx ;is it NULL jz @@AllDone ; yes, skip it cmp dx,cs:[___last] ;last block in the heap? jne @@InnerBlock @@LastBlock: call FreeLastBlock jmp SHORT @@AllDone @@InnerBlock: call FreeInnerBlock @@AllDone: mov ds,cs:[data_seg] pop di pop si pop bp ret ENDP ;----------------------------------------------------------------------------- ; Creates a heap from scratch ; malloc helper function ;----------------------------------------------------------------------------- ; Args: Number of paragraphs for the first block requested (ax) ; Returns: Address of the first byte of user space available ; from the heap if successful (dx:ax) ; NULL if failure (dx:ax) ;----------------------------------------------------------------------------- CreateHeap PROC NEAR push ax ;save the size mov ds,cs:[data_seg] xor ax,ax ;align the heap on paragraph push ax push ax call __sbrk ;retrieve the break level pop bx ;cleanup stack pop bx and ax,000fh jz @@Aligned mov dx,16d sub dx,ax xor ax,ax mov ds,cs:[data_seg] push ax push dx call __sbrk ;align the heap pop bx ;cleanup stack pop bx @@Aligned: pop ax ;retrieve and save the size push ax xor bx,bx ;convert size to long in bx:ax mov bl,ah mov cl,4 shr bx,cl shl ax,cl mov ds,cs:[data_seg] push bx push ax call __sbrk ;adjust the break level pop bx ;cleanup stack pop bx pop bx ;retrieve the size cmp ax,-1 ;failure? je @@NoRoom mov cs:___first,dx ;update heap pointers mov cs:___last,dx mov ds,dx mov WORD PTR ds:[bsize],bx mov WORD PTR ds:[prev_real],dx ;just so we know it is used mov ax,UsedHeaderSize ret @@NoRoom: xor ax,ax cwd ret ENDP ;----------------------------------------------------------------------------- ; Attempts to extend the heap. ; malloc helper function ;----------------------------------------------------------------------------- ; Args: Number of paragraphs for the block requested (ax) ; Returns: Address of the first byte of user space available ; from the heap if successful (dx:ax) ; NULL if failure (dx:ax) ;----------------------------------------------------------------------------- ExtendHeap PROC NEAR push ax ;save the size xor bx,bx ;convert size to long in bx:ax mov bl,ah mov cl,4 shr bx,cl shl ax,cl mov ds,cs:[data_seg] push bx push ax call __sbrk ;adjust the break level pop bx ;cleanup stack pop bx pop bx ;retrieve the size cmp ax,-1 ;failure? je @@NoRoom mov cx,cs:[___last] ;cx = old last-block pointer mov cs:___last,dx ;update last-block pointer mov ds,dx mov WORD PTR ds:[bsize],bx mov WORD PTR ds:[prev_real],cx mov ax,UsedHeaderSize ret @@NoRoom: xor ax,ax cwd ret ENDP ;----------------------------------------------------------------------------- ; Divides a free block into two pieces. ; malloc helper function ;----------------------------------------------------------------------------- ; Args: Number of paragraphs for the block requested (ax) ; Pointer of the block to divide (ds & dx) ; Returns: Address of the first byte of user space available ; from the heap (dx:ax) ;----------------------------------------------------------------------------- AllocatePartialBlock PROC NEAR mov bx,dx ;save block sub ds:[bsize],ax ;make room for new block add dx,ds:[bsize] mov ds,dx ;ds = new block mov ds:[bsize],ax mov ds:[prev_real],bx mov bx,dx ;save block add bx,ds:[bsize] mov ds,bx ;ds = next block mov ds:[prev_real],dx mov ax,UsedHeaderSize ret ENDP ;----------------------------------------------------------------------------- ; C callable function to allocates a given number of bytes from the far heap ;----------------------------------------------------------------------------- ; Args: Number of bytes requested (long, stack) ; Returns: Address of the first byte of user space available ; from the heap if successful (dx:ax) ; NULL if failure (ds:ax) ;----------------------------------------------------------------------------- PROC GenericMalloc DIST IF LDATA PUBLIC _malloc _malloc LABEL DIST ARG R2:word push bp mov bp,sp xor dx,dx mov ax,[R2] ;dx:ax = size requested (long) jmp SHORT @@GotTheSize ENDIF PUBLIC _farmalloc _farmalloc LABEL DIST ARG R2:word, R1:word push bp mov bp,sp mov dx,[R1] mov ax,[R2] ;dx:ax = size requested (long) @@GotTheSize: push si push di mov cs:data_seg,ds mov cx,ax or cx,dx ;does he want 0 bytes? jz @@AllDone add ax,UsedHeaderSize+15 ;add the header size and adc dx,0 ;force paragraph boundary jc @@NoCanDo ;size too big? test dx,0fff0h jnz @@NoCanDo ;size too big? mov cl,4 shr ax,cl shl dx,cl or ah,dl ;ax = number of paragraphs mov dx,cs:[___first] ;dx = first block in the heap or dx,dx ;is there any heap at all? jz @@BuildHeap mov dx,cs:[___rover] ;dx = rover pointer or dx,dx jz @@AddToHeap mov bx,dx ;bx = rover pointer @@SearchHeap: mov ds,dx ;ds = free block cmp ds:[bsize],ax ;is it big enough? jae @@AllocateBlock @@TooSmall: mov dx,ds:[next_free] ;dx = next free block cmp dx,bx ;are we done? jne @@SearchHeap @@AddToHeap: call ExtendHeap jmp SHORT @@AllDone @@BuildHeap: call CreateHeap jmp SHORT @@AllDone @@DivideFreeBlock: call AllocatePartialBlock jmp SHORT @@AllDone @@NoCanDo: xor ax,ax cwd jmp SHORT @@AllDone @@AllocateBlock: ja @@DivideFreeBlock call PullFreeBlock ;remove it from the free-block queue mov bx,ds:[prev_real2] ;mark it as allocated mov ds:[prev_real],bx mov ax,UsedHeaderSize @@AllDone: mov ds,cs:[data_seg] pop di pop si pop bp ret ENDP ;----------------------------------------------------------------------------- ; Attempts to expand a block, relocating it if necessary ; realloc helper function ;----------------------------------------------------------------------------- ; Args: Pointer to the old block (bx) ; Number of paragraphs requested (ax) ; Returns: Address of the first byte of user space available ; from the heap if successful (dx:ax) ; NULL if failure (dx:ax) ;----------------------------------------------------------------------------- ExpandBlock PROC NEAR push bx ;save the old block mov si,cs:[save_hi] ;get size parms from _farrealloc push si ;setup for _farmalloc mov si,cs:[save_lo] ;get size parms from _farrealloc push si ;setup for _farmalloc call _farmalloc pop bx ;cleanup stack pop bx or dx,dx jnz @@MallocOK @@MallocFailed: pop bx ;cleanup stack ret @@MallocOK: pop ds ;ds = old block mov es,dx ;es = new block push es ;save new block push ds ;save old block for _farfree push bx mov dx,ds:[bsize] ;dx = old block size @@MoveFirstBlock: cld dec dx ;subtract one paragraph mov di,UsedHeaderSize mov si,di mov cx,(16d-UsedHeaderSize)/2 rep movsw or dx,dx jz @@FreeOldBlock mov ax,es ;increment segments inc ax mov es,ax mov ax,ds inc ax mov ds,ax @@MoveLoop: xor di,di mov si,di mov cx,dx ;cx = paragraphs remaining cmp cx,1000h jbe @@MoveIt mov cx,1000h @@MoveIt: shl cx,1 ;cx = number of words shl cx,1 shl cx,1 rep movsw sub dx,1000h jbe @@FreeOldBlock mov ax,es ;increment segments add ax,1000h ;add 64k mov es,ax mov ax,ds add ax,1000h ;add 64k mov ds,ax jmp SHORT @@MoveLoop @@FreeOldBlock: mov ds,cs:[data_seg] call _farfree ;free the old block pop dx ;cleanup stack pop dx pop dx mov ax,UsedHeaderSize @@AllDone: ret ENDP ;----------------------------------------------------------------------------- ; Shrinks a block ; realloc helper function ;----------------------------------------------------------------------------- ; Args: Pointer to the block (bx) ; Size of the block (cx) ; Normalized number of paragraphs requested (ax) ; Returns: Address of the first byte of user space available ; from the heap if successful (dx:ax) ;----------------------------------------------------------------------------- ShrinkBlock PROC NEAR cmp bx,cs:[___last] ;last block in the heap? je @@LastBlock @@InnerBlock: mov di,bx ;di = old block add di,ax ;di = new block mov es,di ;es = new block mov si,cx ;si = old block size sub si,ax ;si -= new block size mov es:[bsize],si ;setup new block mov es:[prev_real],bx push es ;save for _farfree push ax mov es,bx ;es = original block mov es:[bsize],ax mov dx,bx ;dx = old block add dx,cx ;dx = block after new mov es,dx ;es = block after new cmp WORD PTR es:[prev_real],0 ;is it used? je @@NextIsFree @@NextIsUsed: mov es:[prev_real],di jmp SHORT @@UnlinkIt @@NextIsFree: mov es:[prev_real2],di @@UnlinkIt: mov si,bx ;si = old block call _farfree pop dx ;cleanup stack pop dx mov dx,si mov ax,UsedHeaderSize ret @@LastBlock: push bx ;save block mov es,bx mov es:[bsize],ax add bx,ax push bx xor ax,ax push ax call __brk ;reset the break level pop dx ;cleanup stack pop dx pop dx ;restore block mov ax,UsedHeaderSize ret ENDP ;----------------------------------------------------------------------------- ; Attempts to reallocate a block ;----------------------------------------------------------------------------- ; Args: Pointer to the old block (stack) ; Number of bytes requested (stack) ; Returns: Address of the first byte of user space available ; from the heap if successful (dx:ax) ; NULL if failure (dx:ax) ;----------------------------------------------------------------------------- PROC GenericRealloc DIST IF LDATA PUBLIC _realloc _realloc LABEL DIST ARG O:word, S:word, LO:word push bp mov bp,sp xor dx,dx jmp SHORT @@GetTheSize ENDIF PUBLIC _farrealloc _farrealloc LABEL DIST ARG O:word, S:word, LO:word, HI:word push bp mov bp,sp mov dx,[HI] @@GetTheSize: mov ax,[LO] ;dx:ax = size requested (long) mov bx,[S] ;bx = segment to realloc push si push di mov cs:data_seg,ds mov cs:save_hi,dx mov cs:save_lo,ax or bx,bx ;is it a null pointer? jz @@MallocIt mov cx,ax or cx,dx ;does he want 0 bytes? jz @@FreeIt add ax,UsedHeaderSize+15 ;add the header size and adc dx,0 ;force paragraph boundary mov cl,4 shr ax,cl shl dx,cl or ah,dl ;ax = number of paragraphs mov es,bx ;es = segment to realloc mov cx,es:[bsize] ;cx = current block size cmp cx,ax jb @@ExpandIt ja @@ShrinkIt @@NoChange: mov dx,bx mov ax,UsedHeaderSize jmp SHORT @@AllDone @@ShrinkIt: call ShrinkBlock jmp SHORT @@AllDone @@ExpandIt: call ExpandBlock jmp SHORT @@AllDone @@MallocIt: push dx push ax call _farmalloc jmp SHORT @@Cleanup @@FreeIt: push bx push ax ;has a zero left over call _farfree @@Cleanup: pop di ;cleanup stack pop di @@AllDone: mov ds,cs:[data_seg] pop di pop si pop bp ret ENDP ENDS END