{ PROTOTYPE PROCEDURES FOR CREATING AND ACCESSING SORTED LINKED LISTS IN EXPANDED MEMORY GARRY J. VASS [72307,3311] The procedures and functions given below present a prototype method for creating and accesing linked lists in expanded memory. Although pointer variables are used in a way that appears to conform to the TPascal pointer syntax, there are several major differences: - there are none of the standard NEW, GETMEM, MARK, RELEASE, DISPOSE, FREEMEM, and MAXAVAIL calls made. These are bound to the program's physical location in memory, and have no effect in expanded memory. Attempting to use these here, or to implement standard linked procedures by altering the HeapPtr standard variable is dangerous and highly discouraged. - pointer variables are set and queried by a simulation of TPascal's internal procedures that is specially customized to the EMS page frame segment. - the MEMAVAIL function is useless here. These procedures will support a list of up to 64K. The general pseudo-code for creating a linked list in expanded memory is: 1. Get a handle and allocate memory from the EMM. 2. Get the page frame segment for the handle to mark the physical beginning of the list in expanded memory. 3. Initialize the root pointer to the page frame segment. 4. For each new record (or list member): a. Calculate a new physical location for the record using a simulated normalization procedure. b. Set the appropriate values to the pointers using a simulated pointer assignment procedure. c. Assure that the last logical record contains a pointer value of NIL. Accessing the list is basically the same as the standard algorithms. The procedures here assume that each list record (or member) is composed of three elements: - a pointer to the next logical record. If the member is the last logical record, this pointer is NIL. - an index, or logical sort key. This value determines the logical position of the record in the list. These routines and the demo use an integer type for index. The index, however, can be of any type where ordinal comparisons can be made, including pointers. - an area for the actual data in each record. These routines and the demo use a string of length 255, but this area can be of any type, including pointers to other lists. Please note that these routines are exploratory and prototype. In no way are they intended to be definitive, accurate, efficient, or exemplary. Areas for further analysis are: 1. A reliable analog to the MEMAVAIL function. 2. Creating linked lists that cross handle boundaries. 3. Creating linked lists that begin in heapspace and extend to expanded memory. 4. A reliable method for assigning the standard variable, HeapPtr, to the base page. Please let me know of your progress in these areas, or improvements to the routines below via the BORLAND SIG [72307,3311] or my PASCAL/ PROLOG SIG at the POLICE STATION BBS (201-963-3115). } PROGRAM LINKED_LISTS; Uses dos,crt; CONST ALLOCATE_MEMORY = $43; EMS_SERVICES = $67; FOREVER:BOOLEAN = FALSE; GET_PAGE_FRAME = $41; LOGICAL_PAGES = 5; MAP_MEMORY = $44; RELEASE_HANDLE = $45; TYPE ANYSTRING = STRING[255]; LISTPTR = ^LISTREC; LISTREC = RECORD NEXT_POINTER : LISTPTR; INDEX_PART : INTEGER; DATA_PART : ANYSTRING; END; VAR ANYINTEGER : INTEGER; ANYSTR : ANYSTRING; HANDLE : INTEGER; { HANDLE ASSIGNED BY EMM } LIST : LISTREC; NEWOFFSET : INTEGER; { PHYSICAL OFFSET OF RECORD } NEWSEGMENT : INTEGER; { PHYSICAL SEGMENT OF RECORD } REGS1 : Registers; ROOT : LISTPTR; { POINTER TO LIST ROOT } SEGMENT : INTEGER; { PAGE FRAME SEGMENT } {--------------------- GENERAL SUPPORT ROUTINES ----------------------} FUNCTION HEXBYTE(N:INTEGER):ANYSTRING; CONST H:ANYSTRING='0123456789ABCDEF'; BEGIN HEXBYTE:=H[((LO(N)DIV 16)MOD 16)+1]+H[(LO(N) MOD 16)+1]; END; FUNCTION HEXWORD(N:INTEGER):ANYSTRING; BEGIN HEXWORD:= HEXBYTE(HI(N))+HEXBYTE(LO(N)); END; FUNCTION CARDINAL(I:INTEGER):REAL; BEGIN CARDINAL:=256.0*HI(I)+LO(I); END; PROCEDURE PAUSE; VAR CH:CHAR; BEGIN WRITELN;WRITELN('-- PAUSING FOR KEYBOARD INPUT...'); READ(CH); WRITELN; END; PROCEDURE DIE(M:ANYSTRING); BEGIN WRITELN('ERROR IN: ',M); WRITELN('HALTING HERE, SUGGEST REBOOT'); HALT; END; FUNCTION EXIST(FILENAME:ANYSTRING):BOOLEAN;VAR FILVAR:FILE;BEGIN ASSIGN(FILVAR,FILENAME);{$I-} RESET(FILVAR);{$I+}EXIST := (IORESULT = 0);END; {--------------------- END OF GENERAL SUPPORT ROUTINES ----------------} {---------------------- EMS SUPPORT ROUTINES -------------------------} FUNCTION EMS_INSTALLED:BOOLEAN; { RETURNS TRUE IF EMS IS INSTALLED } BEGIN { ASSURED DEVICE NAME OF EMMXXXX0 } EMS_INSTALLED := EXIST('EMMXXXX0');{ BY LOTUS/INTEL/MS STANDARDS } END; FUNCTION NEWHANDLE(NUMBER_OF_LOGICAL_PAGES_NEEDED:INTEGER):INTEGER; BEGIN REGS1.AH := ALLOCATE_MEMORY; REGS1.BX := NUMBER_OF_LOGICAL_PAGES_NEEDED; INTR(EMS_SERVICES, REGS1); IF REGS1.AH <> 0 THEN DIE('ALLOCATE MEMORY'); NEWHANDLE := REGS1.DX; END; PROCEDURE KILL_HANDLE(HANDLE_TO_KILL:INTEGER); { RELEASES EMS HANDLE. } BEGIN { THIS MUST BE DONE IF } REPEAT { OTHER APPLICATIONS ARE } WRITELN('RELEASING EMS HANDLE'); { TO USE THE EM ARES. DUE} REGS1.AH := RELEASE_HANDLE; { TO CONCURRENT PROCESSES,} REGS1.DX := HANDLE_TO_KILL; { SEVERAL TRIES MAY BE } INTR(EMS_SERVICES, REGS1); { NECESSARY. } UNTIL REGS1.AH = 0; WRITELN('HANDLE RELEASED'); END; FUNCTION PAGE_FRAME_SEGMENT:INTEGER; { RETURNS PFS } BEGIN REGS1.AH := GET_PAGE_FRAME; INTR(EMS_SERVICES, REGS1); IF REGS1.AH <> 0 THEN DIE('GETTING PFS'); PAGE_FRAME_SEGMENT := REGS1.BX; END; PROCEDURE MAP_MEM(HANDLE_TO_MAP:INTEGER); {MAPS HANDLE TO PHYSICAL} CONST PHYSICAL_PAGE = 0; {PAGES.} BEGIN REGS1.AH := MAP_MEMORY; REGS1.AL := PHYSICAL_PAGE; REGS1.BX := PHYSICAL_PAGE; REGS1.DX := HANDLE_TO_MAP; INTR(EMS_SERVICES, REGS1); IF REGS1.AH <> 0 THEN DIE('MAPPING MEMORY'); END; PROCEDURE GET_EMS_MEMORY(NUMBER_OF_16K_LOGICAL_PAGES:INTEGER); VAR TH:INTEGER; { REQUESTS EM FROM EMM IN 16K INCREMENTS } BEGIN HANDLE := NEWHANDLE(NUMBER_OF_16K_LOGICAL_PAGES); SEGMENT := PAGE_FRAME_SEGMENT; MAP_MEM(HANDLE); END; {----------------- END OF EMS SUPPORT ROUTINES -----------------------} {----------------- CUSTOMIZED LINKED LIST SUPPORT ---------------------} FUNCTION ABSOLUTE_ADDRESS(S, O:INTEGER):REAL; { RETURNS THE REAL } BEGIN { ABSOLUTE ADDRESS } ABSOLUTE_ADDRESS := (CARDINAL(S) * $10) { FOR SEGMENT "S" } + CARDINAL(O); { AND OFFSET "O". } END; PROCEDURE NORMALIZE(VAR S, O:INTEGER); { SIMULATION OF TURBO'S INTERNAL } VAR { NORMALIZATION ROUTINES FOR } NEW_SEGMENT: INTEGER; { POINTER VARIABLES. } NEW_OFFSET : INTEGER; { NORMALIZES SEGMENT "S" AND } BEGIN { OFFSET "O" INTO LEGITAMATE } NEW_SEGMENT := S; { POINTER VALUES. } NEW_OFFSET := O; REPEAT CASE NEW_OFFSET OF $00..$0E : NEW_OFFSET := SUCC(NEW_OFFSET); $0F..$FF : BEGIN NEW_OFFSET := 0; NEW_SEGMENT := SUCC(NEW_SEGMENT); END; END; UNTIL (ABSOLUTE_ADDRESS(NEW_SEGMENT, NEW_OFFSET) > ABSOLUTE_ADDRESS(S, O) + SIZEOF(LIST)); S := NEW_SEGMENT; O := NEW_OFFSET; END; FUNCTION VALUEOF(P:LISTPTR):ANYSTRING; { RETURNS A STRING IN } { SEGMENT:OFFSET FORMAT } { WHICH CONTAINS VALUE } BEGIN { OF A POINTER VARIABLE } VALUEOF := HEXBYTE(MEM[SEG(P):OFS(P) + 3]) + HEXBYTE(MEM[SEG(P):OFS(P) + 2]) +':'+ HEXBYTE(MEM[SEG(P):OFS(P) + 1]) + HEXBYTE(MEM[SEG(P):OFS(P) + 0]); END; PROCEDURE SNAP(P:LISTPTR); { FOR THE RECORD BEING } BEGIN { POINTED TO BY "P", THIS } WRITELN(VALUEOF(P):10, { PRINTS THE SEGMENT/OFFSET } VALUEOF(P^.NEXT_POINTER):20, { LOCATION, THE SEGMENT/ } P^.INDEX_PART:5, { OFFSET OF THE RECORD PONTER, } ' ',P^.DATA_PART); { RECORD INDEX, AND DATA. } END; PROCEDURE PROCESS_LIST; { GET AND PRINT MEMBERS OF A LIST } VAR M1:LISTPTR; { SORTED IN INDEX ORDER. } BEGIN PAUSE; M1 := ROOT; WRITELN; WRITELN('---------------- LINKED LIST ---------------------------------'); WRITELN('MEMBER LOCATION MEMBER CONTENTS'); WRITELN('IN MEMORY POINTER INDEX DATA '); WRITELN('--------------- -----------------------------------------'); WRITELN; REPEAT SNAP(M1); M1 := M1^.NEXT_POINTER; UNTIL M1 = NIL; WRITELN('------------ END OF LIST----------'); END; PROCEDURE LOAD_MEMBER_HIGH (IND:INTEGER; DAT:ANYSTRING); VAR M1:LISTPTR; P:LISTPTR; { INSERTS A RECORD AT THE HIGH } BEGIN { END OF THE LIST. } M1 := ROOT; REPEAT IF M1^.NEXT_POINTER <> NIL THEN M1 := M1^.NEXT_POINTER; UNTIL M1^.NEXT_POINTER = NIL; NORMALIZE(NEWSEGMENT, NEWOFFSET); M1^.NEXT_POINTER := PTR(NEWSEGMENT, NEWOFFSET); P := M1^.NEXT_POINTER; P^.INDEX_PART := IND; P^.DATA_PART := DAT; P^.NEXT_POINTER := NIL; END; PROCEDURE LOAD_MEMBER_MIDDLE (IND:INTEGER; DAT:ANYSTRING); VAR M1:LISTPTR; M2:LISTPTR; P :LISTPTR; T :LISTPTR; BEGIN { INSERTS A MEMBER INTO THE MIDDLE } M1 := ROOT; { OF A LIST. } REPEAT M2 := M1; IF M1^.NEXT_POINTER <> NIL THEN M1 := M1^.NEXT_POINTER; UNTIL (M1^.NEXT_POINTER = NIL) OR (M1^.INDEX_PART >= IND); IF (M1^.NEXT_POINTER = NIL) AND (M1^.INDEX_PART < IND) THEN BEGIN LOAD_MEMBER_HIGH (IND, DAT); EXIT; END; T := M2^.NEXT_POINTER; NORMALIZE(NEWSEGMENT, NEWOFFSET); M2^.NEXT_POINTER := PTR(NEWSEGMENT, NEWOFFSET); P := M2^.NEXT_POINTER; P^.INDEX_PART := IND; P^.DATA_PART := DAT; P^.NEXT_POINTER := T; END; PROCEDURE LOAD_MEMBER (IND:INTEGER; DAT:ANYSTRING); VAR M1:LISTPTR; BEGIN WRITELN('ADDING: ',DAT,' WITH AGE OF ',IND); WRITELN('TURBO`S HEAP POINTER: ',VALUEOF(HEAPPTR), ', MEMAVAIL = ',MEMAVAIL * 16.0:8:0); WRITELN; PAUSE; WRITELN('... SEARCHING FOR ADD POINT ...'); IF ROOT^.INDEX_PART <= IND THEN { ENTRY POINT ROUTINE FOR } BEGIN { ADDING NEW LIST MEMBERS } LOAD_MEMBER_MIDDLE(IND, DAT); { ACTS ONLY IF NEW MEMBER } EXIT; { SHOULD REPLACE CURRENT } END; { ROOT. } M1 := ROOT; NORMALIZE(NEWSEGMENT, NEWOFFSET); ROOT := PTR(NEWSEGMENT, NEWOFFSET); ROOT^.INDEX_PART := IND; ROOT^.DATA_PART := DAT; ROOT^.NEXT_POINTER := M1; END; PROCEDURE INITIALIZE_ROOT_ENTRY(IND:INTEGER; DAT:ANYSTRING); BEGIN ROOT := PTR(NEWSEGMENT, NEWOFFSET); { INITIALIZES A LIST AND } ROOT^.INDEX_PART := IND; { ADDS FIRST MEMBER AS } ROOT^.DATA_PART := DAT; { "ROOT". } ROOT^.NEXT_POINTER := NIL; END; BEGIN TEXTCOLOR(15); IF NOT EMS_INSTALLED THEN DIE('LOCATING EMS DRIVER'); CLRSCR; WRITELN('DEMO OF LINKED LIST IN EXPANDED MEMORY...'); WRITELN('SETTING UP EMS PARAMETERS...'); GET_EMS_MEMORY(LOGICAL_PAGES); WRITELN; WRITELN('ASSIGNED HANDLE: ',HANDLE); NEWSEGMENT := SEGMENT; NEWOFFSET := 0; WRITELN('EMS PARAMETERS SET. BASE PAGE IS: ',HEXWORD(SEGMENT)); WRITELN; WRITELN('TURBO`S HEAP POINTER IS ',VALUEOF(HEAPPTR)); WRITELN('READY TO ADD RECORDS...'); PAUSE; { Demo: Create a linked list of names and ages with age as the index/sort key. Use random numbers for the ages so as to get a different sequence each time the demo is run.} INITIALIZE_ROOT_ENTRY(RANDOM(10) + 20, 'Anne Baxter (original root)'); LOAD_MEMBER(RANDOM(10) + 20, 'Rosie Mallory '); LOAD_MEMBER(RANDOM(10) + 20, 'Sue Perkins '); LOAD_MEMBER(RANDOM(10) + 20, 'Betty Williams '); LOAD_MEMBER(RANDOM(10) + 20, 'Marge Holly '); LOAD_MEMBER(RANDOM(10) + 20, 'Lisa Taylor '); LOAD_MEMBER(RANDOM(10) + 20, 'Carmen Abigail '); LOAD_MEMBER(RANDOM(10) + 20, 'Rhonda Perlman '); PROCESS_LIST; KILL_HANDLE(HANDLE); END.