Assembly Language Programming

Program Assignment #4

Changes! (click here and read the red print)

Write a program to manage an ordered linked list. The data for the list will be taken from stdin and output to stdout. The program will be tested using a data file and command line redirection.

The input will consist of a list of words (alpha characters only). Each word is on a line by itself and will have no surrounding whitespace. Words will not exceed 200 characters in length. Each word is preceded by a + or - indicating whether the word is to be added to or removed from the list. When the * character is read, input is terminated and the contents of the list are to be displayed. Maintain the list in alphabetic order so the output appears this way. Each word in the list is written followed by the address of the object containing that word and the size of the object (2+storage for string) and a CR LF sequence. The last line of output should display the number of words in the list and the total storage used for the words and their pointers.

The linked list is implemented as a list of objects. Each object will contain a pointer (16-bit offset into the data segment) to the next word in the list, and a $ delimited string. Objects will be allocated from a memory pool called the heap. Initially, the memory pool will contain one block of storage. It should be initialized to 0FFh values to indicate the bytes are unused. 

Four public functions will manage the heap. Init (to initialize as described above), Report (to analyze), Alloc (to allocate) and Free (to deallocate). Place these functions (together with the related data definition directives) in a separate source module.

;the simulated heap storage
heapSize = 1024
dummyHeader dw 2 dup (?)
theHeap db heap_size dup(?)
endHeap = offset $ 
  db 0, 255 ;sentinel

Alloc requires an argument in CX indicating the requested size, S, of the allocated block. (S should not exceed 250). Alloc returns in BX the address of the allocated storage. Alloc locates the first available block of sufficient size (S+6 consecutive bytes of 0FFh values) to fulfill the request. The first byte of the block is set to 00h to differentiate it from any 0ffh values that might come before it. The next 2 words of this block are used to link all allocated blocks together (the in_use list). The in_use list is a doubly-linked circular list with dummy header. The first pointer of each block in the list points to the previous block, the second pointer to the next block. The 6th byte holds the requested block size (S). The next S bytes are set to 00h values. Alloc returns a pointer to byte 6 of the block which is the S-byte area available to the client. The client should restrict their usage to [BX] through [BX+S-1] and should avoid storing consecutive 0FFh bytes in this area.

Consider writing a utility function that, given a starting offset, locates the start of the next free block (at least 6 consecutive 0FFh values) and returns the address and size of that block (if found). It should restrict its search to theHeap's storage locations. It will be useful in Alloc and Report. You might design it to look for a block of specific size and make the size an argument.

Free takes an argument in BX that is the address of byte 6 of a block to be freed. The byte at [BX]-1 will be the size (S) of the block to be freed. The words at [BX-5] and [BX-3] point to the previous and next allocated blocks. Remove this block from the in_use list and fill all of the S+6 bytes of the block with 0FFh to mark it as free.

The Report function should list all of the allocated blocks (in the in_use list). For each, display the actual block address (4 hex digits) and total size (including the 6-byte overhead) (in decimal), one block per line. Also display the total amount of allocated storage and the total number and cumulative size of free storage at the end of the list of allocated blocks. To calculate the free storage, use that utility function mentioned above searching for all free blocks.

If any memory error is detected in the Alloc or Free functions, call Report and terminate the program with a suitable message.

The linked list application must dispose of unneeded nodes when words are removed from the list. You should allow duplicate words to be added to the list. 

Call the report function when the end of the input is detected, before displaying the list contents. If you then dispose of all of the allocated storage and call Report again, you should end with a single free block.

Use well designed functions of fairly short length and well-documented purpose. Make good use of the string functions covered in chapter 10. Do not use global variables (except in main and in the memory management routines). The heap size should be 1024, but vary it for testing.

Turn in a printed copy of your solution - it must look nice, so be careful about formatting and documenting. Use the usual naming conventions. E-mail the zip archive (include both modules and executable) attached to a mail message. The subject line of the message must include the words: "Assembly Language Program 4". Try to make the return address correct as well!