[Back to POINTERS SWAG index] [Back to Main SWAG index] [Original]

    {
           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.

[Back to POINTERS SWAG index] [Back to Main SWAG index] [Original]