/**********************************************************************/
/*                                                                    */
/*     Module: MEMINTRL.INC                                           */
/*                                                                    */
/*     This module contains the internal routines used by MEMLIB.C.   */
/*     These functions are designed to be called by the functions     */
/*     contained in MEMLIB.C only and are not for use by an           */
/*     application.                                                   */
/*                                                                    */
/**********************************************************************/
  
/*$PAGE*/
/*====================================================================*/
/*   INCLUDE FILES                                                    */
/*====================================================================*/
  
#include <stddef.h>
#include <malloc.h>
#include <dos.h>
  
/*******************************************************************/
/* Error code definitions for MEMLIB.  Since MEMLIB makes calls to */
/* EMMLIB you may get EMM specific errors.  These errors can be    */
/* found in table A-2 in the EMS manual.                           */
/*******************************************************************/
  
#include "errors.h"
  
/********************************/
/* External Function prototypes */
/********************************/
  
#include "memlib.h"
#include "emmlib.h"
  
/********************************/
/* Internal Function prototypes */
/********************************/
  
unsigned int init_exp_mem   (void);
unsigned int break_overlap  (unsigned int *);
unsigned int check_best_fit (unsigned int, unsigned int *, long *);
unsigned int split_block    (unsigned int, unsigned int);
unsigned int search_after   (unsigned int, unsigned int *, unsigned int *);
unsigned int search_before  (unsigned int, unsigned int *, unsigned int *);
unsigned int coalesce_block (unsigned int, unsigned int, unsigned int *);
unsigned int map_dir_page   (unsigned int, unsigned int);
unsigned int check_token    (unsigned int);
unsigned int find_new_dir_start          (void);
unsigned int restore_memlib_context      (unsigned int);
unsigned int allocate_new_directory_page (void);
unsigned int allocate_new_block          (unsigned int, unsigned int);
unsigned int check_if_all_blocks_free    (unsigned int *);
unsigned int prepare_dir_mapping         (unsigned int *);
  
/*$PAGE*/
/*====================================================================*/
/*   DEFINES                                                          */
/*====================================================================*/
  
#define TRUE                       (unsigned int) 1
#define FALSE                      (unsigned int) 0
#define PASSED                     (unsigned int) 0
#define K64K                       (unsigned long) (64L * 1024L)
#define K16K                       (unsigned int) (16 * 1024)
  
#define PAGE_SIZE                  (unsigned int) K16K
#define MAX_PAGE_FRAME_SIZE        (unsigned int) 24
#define LARGEST_ALLOCATABLE_BLOCK  (unsigned int) (K64K - 1)
#define MAX_ALLOCATABLE_PAGES      (unsigned int) 4
#define MAX_CONTEXTS_AVAILABLE     (unsigned int) 10
#define MAX_DIR_ENTRIES            (unsigned int) (K64K - 1)
  
#define FIRST_PHYS_PAGE            (unsigned int) 0
#define SECOND_PHYS_PAGE           (unsigned int) 1
  
#define UNASSIGNED_TOKEN           (unsigned int) 0xFFFF
#define OFFSET_SIZE                (unsigned int) 0x0400
#define UNMAPPED                   (unsigned int) 0xFFFF
#define NO_CONTEXTS                (unsigned int) 0xFFFF
  
#define EMM_NOT_ENOUGH_PAGES       (unsigned int) 0x88
  
#define DIR_ENTRIES_PER_PAGE       (PAGE_SIZE / sizeof(DIRECTORY_NODE))
  
/*$PAGE*/
/*====================================================================*/
/*   TYPEDEFS                                                         */
/*====================================================================*/
  
/**********************************************************************/
/* This structure stores the housekeeping information used to         */
/* uniquely identify a block of memory and to do garbage collection.  */
/* The directory is an array of these structures.                     */
/*                                                                    */
/*  token        - An identifier to a block of memory which is an     */
/*                 index in the directory array.                      */
/*  size         - The size of the memory block.                      */
/*  logical_page - The array of logical pages that the block uses.    */
/*  offset       - The offset into this block's first logical page.   */
/*                 We only need to keep track of the offset since the */
/*                 segment is set by seteptrs when access is desired. */
/*                                                                    */
/* We must keep track of the directory entries in two ways (an entry  */
/* meaning the index into the directory array which gives us access   */
/* to the structure above).  One is in which the token is used as an  */
/* index into the directory array, giving us a range of 0 - 65535     */
/* directory entries.  Second is when we actually want to access a    */
/* directory entry.  Since we cannot map in the entire directory, due */
/* to its size, we must find what logical page an entry belongs to,   */
/* map that page in, and access that entry by using an index into     */
/* that page.  This index has a range of 0 to the number of entries   */
/* possible in a page.                                                */
/*                                                                    */
/* Note: The token has two uses -- one for identifying a block of     */
/* memory and other as an index into the full directory array which   */
/* gives us acces to a DIRECTORY_NODE structure.  The user of MEMLIB  */
/* always keeps track of his blocks of memory with the token value    */
/* and does not have to worry about the directory array.              */
/*                                                                    */
/* In order to know which logical page to map in we use the following */
/* formula:                                                           */
/*                                                                    */
/* directory_log_page = token / DIR_ENTRIES_PER_PAGE                  */
/*                                                                    */
/* Token is the actual entry into the directory that identifies a     */
/* block.  NUM_DIR_ENTRIES is a macro that returns the number of      */
/* directory entries possible in a given number of pages -- in this   */
/* case one page.  By performing an integer divide, we obtain the     */
/* logical page number that this token's directory entry resides in.  */
/*                                                                    */
/* In order to access a directory entry when it is mapped in we use   */
/* this formula:                                                      */
/*                                                                    */
/* directory_index = token % DIR_ENTRIES_PER_PAGE                     */
/*                                                                    */
/* This number is used as an index into the page of the directory     */
/* array that's mapped in.  This number is different than the token   */
/* which identifies the entry into the full directory array.          */
/**********************************************************************/
  
typedef struct
{
    unsigned int token;
    unsigned int size;
    unsigned int logical_page [MAX_ALLOCATABLE_PAGES];
    unsigned int offset;
  
} DIRECTORY_NODE;
  
/**********************************************************************/
/* This structure is for holding the segment and page number of a     */
/* mappable memory region.  This will be used in an array to hold the */
/* entire list of mappable memory regions.                            */
/**********************************************************************/
  
typedef struct
{
    unsigned int phys_page_segment;
    unsigned int phys_page_number;
  
} MAPPABLE_REGIONS;
  
  
/*$PAGE*/
/*====================================================================*/
/*                 MACROS                                             */
/*====================================================================*/
  
/**********************************************************************/
/* This macro returns the number of PAGE_SIZE pages needed for a      */
/* memory block of the given size.                                    */
/**********************************************************************/
#define NUM_PAGES(size) ((unsigned int) (((unsigned long) size + PAGE_SIZE - 1) / PAGE_SIZE))
  
/**********************************************************************/
/* This macro returns the number of directory entries that fit within */
/* the given amount of PAGES_SIZE pages.                              */
/**********************************************************************/
#define NUM_DIR_ENTRIES(num_pages) ((unsigned long) (PAGE_SIZE / sizeof (DIRECTORY_NODE)) * num_pages)
  
/*$PAGE*/
/*====================================================================*/
/*   GLOBAL VARIABLES                                                 */
/*====================================================================*/
  
/**********************************************************************/
/* Actual number of PAGE_SIZE pages available in the page frame       */
/**********************************************************************/
  
unsigned int num_pages_in_page_frame;
  
/**********************************************************************/
/* Store the page frame base address                                  */
/**********************************************************************/
  
void far* page_frame_base_address;
  
/**********************************************************************/
/* Store the EMM handle that the app will use                         */
/* Store the EMM handle that the memory manager will use              */
/**********************************************************************/
  
unsigned int app_handle;
unsigned int man_handle;
  
/**********************************************************************/
/* The first time that any of the external MEMLIB functions are       */
/* called the initializing routine must be called.  This flag is set  */
/* to TRUE once the call is made.                                     */
/**********************************************************************/
  
unsigned int exp_initialized = FALSE;
  
/**********************************************************************/
/* An array of pointers to each pysical page that the directory uses. */
/* When we need to access two different entries on two separate pages */
/* we can map both pages needed in.                                   */
/**********************************************************************/
  
DIRECTORY_NODE far* directory[2];
  
/**********************************************************************/
/* Number of pages for the directory (dynamically changes)            */
/**********************************************************************/
  
unsigned int dir_page_count;
  
/**********************************************************************/
/* Array tells which logical page is mapped at each physical page.    */
/* UNMAPPED ==> no page is mapped.   Unmap 24 pages (A000 - EFFF).    */
/**********************************************************************/
  
MAP_STRUCT pages_mapped[MAX_PAGE_FRAME_SIZE] =
{
    UNMAPPED,0,  UNMAPPED,1,  UNMAPPED,2,  UNMAPPED,3,
    UNMAPPED,4,  UNMAPPED,5,  UNMAPPED,6,  UNMAPPED,7,
    UNMAPPED,8,  UNMAPPED,9,  UNMAPPED,10, UNMAPPED,11,
    UNMAPPED,12, UNMAPPED,13, UNMAPPED,14, UNMAPPED,15,
    UNMAPPED,16, UNMAPPED,17, UNMAPPED,18, UNMAPPED,19,
    UNMAPPED,20, UNMAPPED,21, UNMAPPED,22, UNMAPPED,23
};
  
/**********************************************************************/
/* number_pages_mapped stores the number actually mapped.             */
/**********************************************************************/
  
unsigned int number_pages_mapped = 0;
  
/**********************************************************************/
/* The total number of pages allocated to the application.            */
/**********************************************************************/
  
unsigned int total_app_allocated_pages;
  
/**********************************************************************/
/* Used to get and restore partial page maps for push_context() and   */
/* pop_context().                                                     */
/**********************************************************************/
  
PARTIAL_CONTEXT_LIST_STRUCT partial_page_map;
  
/**********************************************************************/
/* An array of pointers to saved contexts used by the push_context()  */
/* and pop_context() functions.                                       */
/**********************************************************************/
  
CONTEXT_STRUCT* context_ptrs[MAX_CONTEXTS_AVAILABLE];
  
/**********************************************************************/
/* This variable keeps track of the top of the context_ptrs array.    */
/* This allows pop_context() to know whether there are any contexts   */
/* left to remove or for push_context() to know whether there is      */
/* enough room to store another context.                              */
/**********************************************************************/
  
unsigned int context_top;
  
/**********************************************************************/
/* Size of each context - set in init_exp_mem().                      */
/**********************************************************************/
  
unsigned int context_size;
  
/**********************************************************************/
/* The index into the full directory array used as the starting       */
/* location when searching through the directory for a viable entry   */
/* to keep track of a new memory block.                               */
/**********************************************************************/
  
unsigned int dir_start;
  
/**********************************************************************/
/* The index into the full directory array used as the ending         */
/* location when searching through the directory for a viable entry   */
/* to keep track of a new memory block.                               */
/**********************************************************************/
  
unsigned int dir_end;
  
/*$PAGE*/
/*====================================================================*/
/*              CODE                                                  */
/*====================================================================*/
  
/**********************************************************************/
/*     Name:  unsigned int prepare_dir_mapping (context_saved)        */
/*            unsigned int *context_saved;                            */
/*                                                                    */
/*     Definition:                                                    */
/*        To save the context before mapping in the directory.  This  */
/*     function is called before a directory page will be mapped in.  */
/*     It firsts checks to see if the expanded memory has been        */
/*     initialized and then saves the current context.  The status    */
/*     will be returned to the caller for error checking.             */
/*     'context_saved' is set to TRUE if save_context() was           */
/*     successful.                                                    */
/*                                                                    */
/*     The calling function can then call restore_memlib_context()    */
/*     depending whether 'saved' is TRUE or not.  This allows the     */
/*     caller to preserve the error status from save_context().       */
/*                                                                    */
/*     Parameters:                                                    */
/*        output  context_saved  Whether the context was saved or not */
/*                                                                    */
/*     Results returned:                                              */
/*        PASSED     Operation successful                             */
/*        error      Non-zero value, see "ERRORS.H" or EMS table A-2  */
/*                                                                    */
/*     Calls: init_exp_mem()                                          */
/*            save_context()                                          */
/*                                                                    */
/*     Called by: ememavl()                                           */
/*                ememmax()                                           */
/*                emsize()                                            */
/*                efmalloc()                                          */
/*                effree()                                            */
/*                                                                    */
/*     Globals referenced/modified: exp_initialized                   */
/*                                  man_handle                        */
/*                                                                    */
/**********************************************************************/
  
unsigned int prepare_dir_mapping (context_saved)
unsigned int *context_saved;
{
    unsigned int status;          /* The status of EMM and MEMLIB */
  
    *context_saved = FALSE;
    status         = PASSED;
  
   /**********************************************/
   /* If expanded memory hasn't been initialized */
   /* then call init_exp_mem().                  */
   /**********************************************/
  
    if (!exp_initialized)
        status = init_exp_mem();
  
    if (status == PASSED)
    {
      /*****************************/
      /* Save the current context. */
      /*****************************/
  
        status = save_context (man_handle);
        if (status == PASSED)
        {
            *context_saved = TRUE;
        }
    }
    return (status);
  
} /** prepare_dir_mapping **/
  
/*$PAGE*/
/**********************************************************************/
/*     Name:  unsigned int map_dir_page (log_page, phys_page)         */
/*            unsigned int log_page;                                  */
/*            unsigned int phys_page;                                 */
/*                                                                    */
/*     Definition:                                                    */
/*        Maps in the specified logical page for the directory into   */
/*     the specified physical page.  For use by MEMLIB only (uses     */
/*     MEMLIB handle -- man_handle).                                  */
/*                                                                    */
/*     Parameters:                                                    */
/*        input   log_page    The logical directory page to map in    */
/*        input   phys_page   Which physical page to map log_page in  */
/*                                                                    */
/*     Results returned:                                              */
/*        PASSED     Operation successful                             */
/*        error      Non-zero value, see "ERRORS.H" or EMS table A-2  */
/*                                                                    */
/*     Calls: map_unmap_pages()                                       */
/*                                                                    */
/*     Called by: ememavl()                                           */
/*                ememmax()                                           */
/*                emsize()                                            */
/*                efmalloc()                                          */
/*                effree()                                            */
/*                seteptrs()                                          */
/*                                                                    */
/*     Globals referenced/modified: exp_intialized                    */
/*                                  man_handle                        */
/*                                                                    */
/**********************************************************************/
  
unsigned int map_dir_page (log_page, phys_page)
unsigned int log_page;
unsigned int phys_page;
{
    MAP_STRUCT   directory_map[1];  /* Structure to use EMS map pages */
    unsigned int status;            /* Status of EMM and MEMLIB       */
  
    directory_map[0].log_page         = log_page;
    directory_map[0].phys_page_or_seg = phys_page;
    status = map_unmap_pages (PHYS_PAGE_MODE, 1, directory_map, man_handle);
  
    return (status);
} /** end map_dir_page **/
  
/*$PAGE*/
/**********************************************************************/
/*                                                                    */
/*     Name:    unsigned int restore_memlib_context (status)          */
/*              unsigned int status;                                  */
/*                                                                    */
/*     Description:                                                   */
/*        Restores a context saved by prepare_dir_mapping() so that   */
/*     memlib can access the directory.  If the status passed in is   */
/*     an error, then that is the status returned regardless if       */
/*     restore_context() generates an error.  If the status passed in */
/*     is PASSED, we return the status generated by restore_context().*/
/*        We do this so that in some recoverable errors we can        */
/*     successfully restore the context and still return the correct  */
/*     error code to the application.                                 */
/*                                                                    */
/*     Parameters:                                                    */
/*        input   status     The status passed in                     */
/*                                                                    */
/*     Results returned:                                              */
/*        PASSED     Operation successful                             */
/*        error      Non-zero value, see "ERRORS.H" or EMS table A-2  */
/*                                                                    */
/*     Calls: restore_context()                                       */
/*                                                                    */
/*     Called by: ememavl()                                           */
/*                ememmax()                                           */
/*                emsize()                                            */
/*                efmalloc()                                          */
/*                effree()                                            */
/*                                                                    */
/*     Globals referenced/modified: man_handle                        */
/*                                                                    */
/**********************************************************************/
  
unsigned int restore_memlib_context (status)
unsigned int status;
{
    unsigned int restore_status;  /* Status returned from restore_context */
  
    restore_status = restore_context (man_handle);
    if (status == PASSED)
        return (restore_status);
    else
        return (status);
  
} /** end restore_memlib_context **/
  
/*$PAGE*/
/**********************************************************************/
/*                                                                    */
/*     Name:  unsigned int check_token (token)                        */
/*            unsigned int token;                                     */
/*                                                                    */
/*     Description:                                                   */
/*        This function check's a token to see if it is valid.  It    */
/*     is valid if it is within the directory boundries.  A token is  */
/*     valid when it is set by efmalloc().                            */
/*                                                                    */
/*     Parameters:                                                    */
/*        input    token   The token to be validated.                 */
/*                                                                    */
/*     Results returned:                                              */
/*        PASSED     Operation successful                             */
/*        error      Non-zero value, see "ERRORS.H" or EMS table A-2  */
/*                                                                    */
/*     Calls: None                                                    */
/*                                                                    */
/*     Called by: effree()                                            */
/*                emsize()                                            */
/*                                                                    */
/*     Globals referenced/modified: dir_page_count                    */
/*                                  exp_initialized                   */
/*                                                                    */
/**********************************************************************/
  
unsigned int check_token (token)
unsigned int token;
{
    unsigned int status;          /* The status of EMM and MEMLIB */
  
   /******************/
   /* Assume PASSED. */
   /******************/
  
    status = PASSED;
  
   /****************************************************************/
   /* If the manager is not initialized then the token is invalid. */
   /****************************************************************/
  
    if (!exp_initialized)
        status = INVALID_TOKEN;
  
   /***************************************************************/
   /* First make sure the token isn't greater than the number of  */
   /* entries possible for the current number of directory pages. */
   /* Then check for a valid token.                               */
   /***************************************************************/
  
    if (status == PASSED)
    {
        if ((token > (unsigned int) (NUM_DIR_ENTRIES (dir_page_count) - 1)) ||
            (token == UNASSIGNED_TOKEN))
            status = INVALID_TOKEN;
    }
  
    return(status);
  
} /** end check_token **/
  
/*$PAGE*/
/**********************************************************************/
/*                                                                    */
/*     Name:     unsigned int init_exp_mem (void)                     */
/*                                                                    */
/*     Description:                                                   */
/*        This routine initializes the housekeeping variables needed  */
/*     to keep track of expanded memory.  It tests for the presence   */
/*     of EMM 4.0 and initializes the directory.                      */
/*                                                                    */
/*     Parameters: None                                               */
/*                                                                    */
/*     Results returned:                                              */
/*        PASSED     Operation successful                             */
/*        error      Non-zero value, see "ERRORS.H" or EMS table A-2  */
/*                                                                    */
/*     Calls: alloc_pages()                                           */
/*            EMM_installed()                                         */
/*            get_page_frame_seg()                                    */
/*            get_partial_context_size()                              */
/*            get_unalloc_page_count()                                */
/*            realloc_pages()                                         */
/*            map_dir_page()                                          */
/*            get_page_frame_count()                                  */
/*                                                                    */
/*     Called by: prepare_dir_mapping()                               */
/*                push_context()                                      */
/*                pop_context()                                       */
/*                                                                    */
/*     Globals referenced/modified: directory                         */
/*                                  app_handle                        */
/*                                  context_size                      */
/*                                  dir_page_count                    */
/*                                  exp_intialized                    */
/*                                  man_handle                        */
/*                                  number_pages_mapped               */
/*                                  page_frame_base_address           */
/*                                  num_pages_in_page_frame           */
/*                                  pages_mapped                      */
/*                                  context_top                       */
/*                                  total_app_allocated_pages         */
/*                                  dir_start                         */
/*                                  dir_end                           */
/*                                  exp_initialized                   */
/*                                  partial_page_map                  */
/*                                                                    */
/**********************************************************************/
  
unsigned int init_exp_mem (void)
{
  
    unsigned int status;            /* The status of EMM and MEMLIB */
    unsigned int num_unalloc_pages; /* Number of unallocated pages  */
    unsigned int page_frame_seg;    /* Page frame segment           */
    unsigned int i;                 /* Looping variable             */
    unsigned int zero_pages;        /* To call realloc for 0 pages  */
  
   /********************************************************/
   /* Test for EMM presence and enough pages -- need at    */
   /* least 1 for the directory and 1 for the application. */
   /********************************************************/
  
    status = EMM_installed();
    if (status == PASSED)
    {
        status = get_unalloc_page_count (&num_unalloc_pages);
        if (status == PASSED)
            if (num_unalloc_pages <= 1)
                status = NOT_ENOUGH_UNALLOCATED_PAGES;
    }
  
    if (status == PASSED)
    {
      /*****************************************/
      /* Allocate 0 pages for the application. */
      /* We need to first alloc 1 page to get  */
      /* a handle then realloc to reduce the   */
      /* number of pages used to 0.            */
      /*****************************************/
  
        status = alloc_pages (1, &app_handle);
        if (status == PASSED)
        {
            zero_pages = 0;
            status = realloc_pages (&zero_pages, app_handle);
            if ((zero_pages != 0) ||
                (status == EMM_NOT_ENOUGH_PAGES))
                status = NOT_ENOUGH_UNALLOCATED_PAGES;
        }
  
      /*********************************************/
      /* Allocate 1 page for the manager (memlib). */
      /*********************************************/
  
        if (status == PASSED)
            status = alloc_pages (1, &man_handle);
  
        if (status == PASSED)
        {
         /****************************/
         /* Map this directory page. */
         /****************************/
  
            status = map_dir_page (0, FIRST_PHYS_PAGE);
        }
  
        if (status == PASSED)
        {
         /*********************************************************/
         /* Get the base address of the start of expanded memory. */
         /*********************************************************/
  
            status = get_page_frame_seg (&page_frame_seg);
            if (status == PASSED)
            {
            /***************************************************/
            /* Convert the page frame segment to a far pointer */
            /* and point directory[0] to it.                   */
            /***************************************************/
  
                page_frame_base_address = FP (page_frame_seg);
                directory[0] = (DIRECTORY_NODE far *) page_frame_base_address;
  
            /****************************************************/
            /* Point directory[1] to the address of the second  */
            /* physical page in the page frame.                 */
            /****************************************************/
                FP_SEG(directory[1]) = page_frame_seg + OFFSET_SIZE;
                FP_OFF(directory[1]) = 0;
            }
        }
    }
  
    if (status == PASSED)
    {
      /************************************************/
      /* Set the variable that keeps track of the how */
      /* many pages the directory is using to 1.      */
      /************************************************/
  
        dir_page_count = 1;
  
      /**************************************************************/
      /* Initialize all the directory entries so that the token     */
      /* identifiers are set UNASSIGNED_TOKEN (entry is available)  */
      /* and their size to 0.                                       */
      /**************************************************************/
  
        for (i = 0; i < DIR_ENTRIES_PER_PAGE; i++)
        {
            directory[0][i].token = UNASSIGNED_TOKEN;
            directory[0][i].size = 0;
        }
  
      /********************************************************/
      /* Set the starting and ending entries in the directory */
      /* when doing free memory block searches.               */
      /********************************************************/
  
        dir_start = 0;
        dir_end   = 0;
  
      /****************************************************************/
      /* Set the total number of pages the application is using to 0. */
      /****************************************************************/
  
        total_app_allocated_pages = 0;
  
      /**********************************************/
      /* Get the number of pages in the page frame. */
      /**********************************************/
  
        status = get_page_frame_count (&num_pages_in_page_frame);
  
        if (status == PASSED)
        {
         /*************************************************/
         /* Set the partial page map for pushes and pops. */
         /*************************************************/
  
            partial_page_map.mappable_region_count = num_pages_in_page_frame;
            partial_page_map.mappable_region_seg[0] = FP_SEG (page_frame_base_address);
  
         /*************************************************************/
         /* Set the segment value for each 16K page in the page frame */
         /* that push_context() & pop_context() will be storing.      */
         /*************************************************************/
  
            for (i = 1; i < num_pages_in_page_frame; i++)
            {
                partial_page_map.mappable_region_seg[i] =
                partial_page_map.mappable_region_seg[i - 1] + OFFSET_SIZE;
            }
  
         /***************************************************/
         /* Set the context push and pop stack to be empty. */
         /***************************************************/
  
            context_top = NO_CONTEXTS;
  
         /************************************************************/
         /* Get the number of bytes needed to save (push) a context. */
         /************************************************************/
  
            status = get_partial_context_size (num_pages_in_page_frame, &context_size);
            if (status == PASSED)
            {
            /********************/
            /* Unmap all pages. */
            /********************/
  
                for (i = 0; i < num_pages_in_page_frame; i++)
                {
                    pages_mapped[i].log_page = UNMAPPED;
                }
            }
            number_pages_mapped = 0;
        }
    }
   /***************************************************************/
   /* If status is good then update the already-initialized flag. */
   /***************************************************************/
  
    if (status == PASSED)
        exp_initialized = TRUE;
  
    return (status);
  
} /** end init_exp_mem **/
  
/*$PAGE*/
/**********************************************************************/
/*                                                                    */
/*     Name: unsigned int allocate_new_directory_page (void)          */
/*                                                                    */
/*     Description:                                                   */
/*        This routine attempts to allocate a new page for the        */
/*     directory.                                                     */
/*                                                                    */
/*     Parameters:  None                                              */
/*                                                                    */
/*     Results returned:                                              */
/*        PASSED    Operation successful                              */
/*        error     Non-zero value, see "ERRORS.H" or EMS table A-2   */
/*                                                                    */
/*     Calls: map_dir_page()                                          */
/*            realloc_pages()                                         */
/*                                                                    */
/*     Called by: allocate_new_block()                                */
/*                check_best_fit()                                    */
/*                                                                    */
/*     Globals referenced/modified: directory                         */
/*                                  dir_page_count                    */
/*                                  man_handle                        */
/*                                                                    */
/**********************************************************************/
  
unsigned int allocate_new_directory_page (void)
{
    unsigned int status;            /* The status of EMM and MEMLIB  */
    unsigned int index;             /* Index into a directory page   */
    unsigned int new_num_dir_pages; /* New number of directory pages */
  
   /*****************************/
   /* Assume status will be ok. */
   /*****************************/
  
    status = PASSED;
  
   /******************************************/
   /* Set the new number of directory pages. */
   /******************************************/
  
    new_num_dir_pages = dir_page_count + 1;
  
   /***************************************************/
   /* Make sure we don't allocate beyond the maximum  */
   /* number of directory entries allowable.          */
   /***************************************************/
  
    if ((unsigned long) NUM_DIR_ENTRIES (new_num_dir_pages) > MAX_DIR_ENTRIES)
        status = TOO_MANY_DIRECTORY_ENTRIES;
  
    if (status == PASSED)
    {
      /************************************************/
      /* Attempt to add a new page for the directory. */
      /************************************************/
  
        status = realloc_pages (&new_num_dir_pages, man_handle);
  
      /******************************************/
      /* Make sure the number of pages returned */
      /* is equal to the number we wanted.      */
      /******************************************/
  
        if ((status == EMM_NOT_ENOUGH_PAGES) ||
            (new_num_dir_pages != dir_page_count + 1))
            status = NOT_ENOUGH_UNALLOCATED_PAGES;
  
        if (status == PASSED)
        {
         /************************************************/
         /* Allocate succeeded, update the directory map */
         /************************************************/
  
            dir_page_count++;
  
            status = map_dir_page (dir_page_count - 1, FIRST_PHYS_PAGE);
            if (status == PASSED)
            {
            /*****************************************/
            /* Initialize the new directory entries. */
            /*****************************************/
  
                for (index = 0; index < DIR_ENTRIES_PER_PAGE; index++)
                {
                    directory[0][index].token = UNASSIGNED_TOKEN;
                    directory[0][index].size = 0;
                }
            }
        }
    }
    return (status);
  
}  /** end allocate_new_directory_page **/
  
/*$PAGE*/
/**********************************************************************/
/*                                                                    */
/*     Name: unsigned int allocate_new_block (size, token)            */
/*           unsigned int size;                                       */
/*           unsigned int token;                                      */
/*                                                                    */
/*     Description:                                                   */
/*        This routine attempts to allocate a block of size 'size',   */
/*     in bytes, and set the fields in directory[token] appropriately.*/
/*                                                                    */
/*     Parameters:                                                    */
/*        input size     the size, in bytes, to allocate              */
/*        input token    index into directory for this block          */
/*                                                                    */
/*     Results returned:                                              */
/*        PASSED    Operation successful                              */
/*        error     Non-zero value, see "ERRORS.H" or EMS table A-2   */
/*                                                                    */
/*     Calls: allocate_new_directory_page()                           */
/*            realloc_pages()                                         */
/*            map_dir_page()                                          */
/*                                                                    */
/*     Called by: efmalloc()                                          */
/*                                                                    */
/*     Globals referenced/modified: directory                         */
/*                                  app_handle                        */
/*                                  dir_page_count                    */
/*                                  total_app_allocated_pages         */
/*                                  dir_start                         */
/*                                  dir_end                           */
/*                                                                    */
/**********************************************************************/
  
unsigned int allocate_new_block (size, token)
unsigned int size;
unsigned int token;
{
    unsigned int i;                  /* Looping variable                    */
    unsigned int page;               /* Current directory page mapped in    */
    unsigned int status;             /* Status of EMM and MEMLIB            */
    unsigned int num_pages_needed;   /* Number of pages needed              */
    unsigned int size_mod_page_size; /* Size in bytes MOD PAGE_SIZE         */
    unsigned int new_total_pages;    /* New number of pages for the         */
                                    /* application's handle                */
    unsigned int tokens_page;        /* Token's dir entry's logical page    */
    unsigned int tokens_index;       /* Token's index into its page         */
    unsigned int i_dir_entry;        /* Translate i to an entry into the    */
                                    /* full directory array                */
    unsigned int dir_starts_page;    /* Dir_start's dir entry's log page    */
    unsigned int dir_starts_index;   /* Dir_start's index into its page     */
    unsigned int found_block;        /* Whether a block was found or not    */
    unsigned int remainders_logical_page; /* The remaining portion's first  */
                                         /* logical page                   */
  
    status = PASSED;
  
   /****************************************************************/
   /* Check if we need to allocate another page for the directory. */
   /****************************************************************/
  
    if (dir_end >= (unsigned int) (NUM_DIR_ENTRIES (dir_page_count) - 2))
        status = allocate_new_directory_page();
  
    if (status == PASSED)
    {
      /********************************************/
      /* Allocate enough new pages for this block */
      /********************************************/
  
        num_pages_needed = NUM_PAGES (size);
        new_total_pages = total_app_allocated_pages + num_pages_needed;
  
      /*************************************************************/
      /* Assign the new number of pages to the application handle. */
      /*************************************************************/
  
        status = realloc_pages (&new_total_pages, app_handle);
  
      /******************************************/
      /* Make sure the number of pages returned */
      /* is equal to the number we wanted.      */
      /******************************************/
  
        if ((new_total_pages != (total_app_allocated_pages + num_pages_needed))
            || (status == EMM_NOT_ENOUGH_PAGES))
            status = NOT_ENOUGH_UNALLOCATED_PAGES;
    }
  
   /****************************************************/
   /* If allocate succeeded, set the directory entries */
   /****************************************************/
  
    if (status == PASSED)
    {
      /*******************************************************/
      /* Convert 'token' to its respective directory entry's */
      /* logical page and its index into that page.          */
      /*******************************************************/
  
        tokens_page  = token / DIR_ENTRIES_PER_PAGE;
        tokens_index = token % DIR_ENTRIES_PER_PAGE;
  
      /**************************************/
      /* Map in the token's directory page. */
      /**************************************/
  
        status = map_dir_page (tokens_page, FIRST_PHYS_PAGE);
        if (status == PASSED)
        {
         /**************************************/
         /* Set the entry in the directory for */
         /* the newly allocated block.         */
         /**************************************/
  
            directory[0][tokens_index].token  = token;
            directory[0][tokens_index].size   = size;
            directory[0][tokens_index].offset = 0;
  
         /*********************************************/
         /* Set the logical pages for this block to   */
         /* the logical pages that we just allocated. */
         /*********************************************/
  
            for (i = 0; i < num_pages_needed; i++)
            {
                directory[0][tokens_index].logical_page[i] =
                total_app_allocated_pages + i;
            }
  
         /**************************************************/
         /* If this block size is NOT a multiple of 16K,   */
         /* find an unused directory entry and have it     */
         /* point to the remaining part of the page.       */
         /**************************************************/
  
            size_mod_page_size = size % PAGE_SIZE;
  
            if (size_mod_page_size != 0)
            {
            /********************************************************/
            /* We have a remainder on the last logical page for the */
            /* new block.  Keep track of this page so that when we  */
            /* set a free directory entry to point to the remainder */
            /* we already know what logical page it uses.           */
            /********************************************************/
  
                remainders_logical_page =
                directory[0][tokens_index].logical_page[num_pages_needed - 1];
  
                dir_starts_page  = dir_start / DIR_ENTRIES_PER_PAGE;
                dir_starts_index = dir_start % DIR_ENTRIES_PER_PAGE;
                found_block = FALSE;
  
            /****************************************/
            /* Go through the directory, page by    */
            /* page, until we find an usable entry. */
            /****************************************/
  
                for (page = dir_starts_page; ((status == PASSED) &&
                    (page < dir_page_count) &&
                    (!found_block)); page++)
                {
               /***********************************/
               /* Map in the this directory page. */
               /***********************************/
  
                    status = map_dir_page (page, FIRST_PHYS_PAGE);
  
               /*********************************************************/
               /* Go through each entry for the mapped in page until we */
               /* find a usable entry or until we run out of entries.   */
               /*********************************************************/
  
                    for (i = dir_starts_index; ((i < DIR_ENTRIES_PER_PAGE) &&
                        (!found_block) &&
                        (status == PASSED)); i++)
                    {
                        if ((directory[0][i].token == UNASSIGNED_TOKEN) &&
                            (directory[0][i].size == 0))
                        {
                     /*******************************************/
                     /* We found an unused directory entry, set */
                     /* it to point to the leftover piece.      */
                     /*******************************************/
  
                            directory[0][i].offset = size_mod_page_size;
                            directory[0][i].size = PAGE_SIZE - size_mod_page_size;
                            directory[0][i].logical_page[0] = remainders_logical_page;
  
                            i_dir_entry = page * DIR_ENTRIES_PER_PAGE + i;
                            if (i_dir_entry >= dir_end)
                                dir_end = i_dir_entry + 1;
  
                            found_block = TRUE;
                        }
                    } /** end for i **/
  
                    dir_starts_index = 0;
  
                } /** end for page **/
  
            } /** end if page_mod_page_size **/
  
         /***********************************/
         /* Update the toal allocated pages */
         /***********************************/
  
            total_app_allocated_pages += num_pages_needed;
  
        }  /** end if status PASSED **/
  
    } /** end if status PASSED **/
    return (status);
  
}  /** end allocate_new_block **/
  
  
/*$PAGE*/
/**********************************************************************/
/*                                                                    */
/*     Name: unsigned int split_block (best_index, size)              */
/*           unsigned int best_index;                                 */
/*           unsigned int size;                                       */
/*                                                                    */
/*     Description:                                                   */
/*        This routine splits a block into allocated and unallocated  */
/*     portions.  The size is assigned to the allocated portion and   */
/*     the left over portion is set up as a free block.               */
/*                                                                    */
/*     Parms Passed:                                                  */
/*        input best_index   The directory entry to be broken up.     */
/*                           It will be the entry that will point to  */
/*                           the allocated portion after it is broken */
/*                           into its allocated/free portions.        */
/*              size         The size of the block to be allocated.   */
/*                                                                    */
/*     Results returned:                                              */
/*        PASSED    Operation successful                              */
/*        error     Non-zero value, see "ERRORS.H" or EMS table A-2   */
/*                                                                    */
/*     Calls: map_dir_page()                                          */
/*            break_overlap()                                         */
/*                                                                    */
/*     Called by:  efmalloc()                                         */
/*                                                                    */
/*     Globals referenced/modified: directory                         */
/*                                  dir_page_count                    */
/*                                  dir_end                           */
/*                                  dir_start                         */
/*                                                                    */
/**********************************************************************/
  
unsigned int split_block (best_index, size)
unsigned int best_index;
unsigned int size;
{
    unsigned int num_pages_for_size; /* The num of logical pages for size  */
    unsigned int size_mod_page_size; /* The size modulo the PAGE_SIZE      */
    unsigned int dir_starts_page;    /* Dir_start's dir entry's log page   */
    unsigned int best_indexs_page;   /* Best_index's dir entry's log page  */
    unsigned int best_indexs_index;  /* Best_index's index into its page   */
    unsigned int best_index_offset;  /* Best_index's logical page offset   */
    unsigned int best_index_size;    /* Best_index's memory block's size   */
    unsigned int index;              /* Current index into a logical page  */
    unsigned int page;               /* Current directory page mapped in   */
    unsigned int remainder;          /* The index into a dir page that     */
                                    /* will point to the leftover portion */
                                    /* in a logical page after allocated  */
                                    /* block is set                       */
    unsigned int remainders_entry;   /* Remainder converted to a full      */
                                    /* directory entry                    */
    unsigned int status;             /* Status of EMM and MEMLIB           */
    unsigned int j;                  /* Looping variable                   */
    unsigned int avail_entry_found;  /* An available entry has been found  */
    unsigned int start_page_for_remainder; /* The starting logical page    */
                                          /* for the remainder            */
  
   /*******************************/
   /* Initialize local variables. */
   /*******************************/
  
    avail_entry_found = FALSE;
    status            = PASSED;
  
   /*************************************************/
   /* Convert dir_start to its respective directory */
   /* entry's logcal page.                          */
   /*************************************************/
  
    dir_starts_page  = dir_start / DIR_ENTRIES_PER_PAGE;
  
   /**************************************************/
   /* Convert dir_start to its respective entry's    */
   /* page index.  We want to start the first        */
   /* page's index at the current starting location. */
   /**************************************************/
  
    index = dir_start % DIR_ENTRIES_PER_PAGE;
  
   /****************************************************************/
   /* Check if we need to allocate another page for the directory. */
   /****************************************************************/
  
    if (dir_end >= (unsigned int) (NUM_DIR_ENTRIES (dir_page_count) - 2))
        status = allocate_new_directory_page();
  
   /****************************************************************/
   /* Go through all the directory pages starting with dir_start's */
   /* page until we find an usable entry.                          */
   /****************************************************************/
  
    for (page = dir_starts_page; ((page < dir_page_count) &&
        (!avail_entry_found) &&
        (status == PASSED)); page++)
    {
      /*******************************/
      /* Map in this directory page. */
      /*******************************/
  
        status = map_dir_page (page, FIRST_PHYS_PAGE);
      /************************************************************/
      /* Go through this page's indexes looking for the first     */
      /* available directory entry to keep track of the remainder */
      /* portion.  The first time we enter this loop we start     */
      /* with the current starting location (dir_start converted  */
      /* to a page's index) from above.  All other index's after  */
      /* the first page will start with 0.                        */
      /************************************************************/
  
        for (remainder = index; ((remainder < DIR_ENTRIES_PER_PAGE) &&
            (!avail_entry_found) &&
            (status == PASSED)); remainder++)
        {
            if ((directory[0][remainder].size == 0) &&
                (directory[0][remainder].token == UNASSIGNED_TOKEN))
            {
            /**********************************************/
            /* We've found an available directory entry   */
            /* to keep track of the left-over portion.    */
            /* Time to map in the block we want to split. */
            /**********************************************/
  
                avail_entry_found = TRUE;
  
            /*******************************************************/
            /* We're going to map in two different directory pages */
            /* so that we can reference best_index's and           */
            /* remainder's directory entry at once.  Since we are  */
            /* using two different logical pages we need to use    */
            /* directory[1] to access the second page's entries.   */
            /*******************************************************/
  
                best_indexs_page  = best_index / DIR_ENTRIES_PER_PAGE;
                best_indexs_index = best_index % DIR_ENTRIES_PER_PAGE;
  
            /************************************************/
            /* Map in the best_index's directory page in at */
            /* physical page one while keeping  remainder's */
            /* directory page at physical page zero.        */
            /************************************************/
  
                status = map_dir_page (best_indexs_page, SECOND_PHYS_PAGE);
                if (status == PASSED)
                {
               /*****************************/
               /* Set some local variables. */
               /*****************************/
  
                    best_index_offset  = directory[1][best_indexs_index].offset;
                    best_index_size    = directory[1][best_indexs_index].size;
                    num_pages_for_size = NUM_PAGES (size);
  
               /*************************************************/
               /* Split this block into used and free portions. */
               /*************************************************/
  
                    directory[0][remainder].size = best_index_size - size;
  
               /***********************************************************/
               /* Find the starting logical page for the remainder block. */
               /***********************************************************/
  
                    if (((best_index_offset + size) % (PAGE_SIZE)) == 0)
                        start_page_for_remainder = num_pages_for_size;
                    else
                        start_page_for_remainder = num_pages_for_size - 1;
  
               /********************************************************/
               /* Set the logical pages for the newly allocated block. */
               /********************************************************/
  
                    for (j = start_page_for_remainder;
                        (j < NUM_PAGES (best_index_size)); j++)
                    {
                        directory[0][remainder].
                        logical_page[j - start_page_for_remainder] =
                        directory[1][best_indexs_index].logical_page[j];
                    }
  
               /*************************************************************/
               /* Set remainder's index to point to the new leftover piece. */
               /*************************************************************/
  
                    directory[0][remainder].offset =
                    (best_index_offset + size) % PAGE_SIZE;
  
               /*******************/
               /* Update dir_end. */
               /*******************/
  
                    remainders_entry = remainder + page * DIR_ENTRIES_PER_PAGE;
                    if (remainders_entry >= dir_end)
                        dir_end = remainders_entry + 1;
  
               /********************************************************/
               /* If the leftover piece takes more logical pages than  */
               /* it should (1 page / PAGE_SIZE) then we need to break */
               /* the remainder piece into two free blocks.            */
               /********************************************************/
  
                    size_mod_page_size = directory[0][remainder].size % PAGE_SIZE;
                    if (size_mod_page_size >
                        PAGE_SIZE - directory[0][remainder].offset)
                        status = break_overlap (&remainders_entry);
  
                } /** if status PASSED **/
  
            } /** end if directory **/
  
        } /** end for remainder = dir_start **/
  
        index = 0;
  
    } /** end for page **/
  
    return (status);
  
} /** end split_block() **/
  
  
/*$PAGE*/
/**********************************************************************/
/*                                                                    */
/*     Name:    unsigned int find_new_dir_start (void)                */
/*                                                                    */
/*     Description:                                                   */
/*        This function finds a new starting location in the          */
/*     directory.  This starting entry is used when looking for a     */
/*     new block of memory.                                           */
/*                                                                    */
/*     Note: We know the new starting location will always start      */
/*     after the present one except when we free a block.  In this    */
/*     case, if the freed block's directory entry is before the       */
/*     current starting entry, we set the starting location to that   */
/*     of the newly freed block's directory entry.  This is done in   */
/*     effree().                                                      */
/*                                                                    */
/*     Parameters: None                                               */
/*                                                                    */
/*     Results returned:                                              */
/*        PASSED     Operation successful                             */
/*        error      Non-zero value, see "ERRORS.H" or EMS table A-2  */
/*                                                                    */
/*     Calls: map_dir_page()                                          */
/*                                                                    */
/*     Called by:  check_best_fit()                                   */
/*                                                                    */
/*     Globals referenced/modified: directory                         */
/*                                  directory_map                     */
/*                                  dir_page_count                    */
/*                                  dir_start                         */
/*                                  dir_end                           */
/*                                                                    */
/**********************************************************************/
  
unsigned int find_new_dir_start()
{
    unsigned int i;                 /* Looping variable                  */
    unsigned int avail_entry_found; /* An available entry has been found */
    unsigned int dir_starts_page;   /* Dir_start's dir entry's log page  */
    unsigned int index;             /* The current index into a page     */
    unsigned int page;              /* The current dir page mapped in    */
    unsigned int status;            /* Status of EMM and MEMLIB          */
  
   /*******************************/
   /* Initialize local variables. */
   /*******************************/
  
    avail_entry_found  = FALSE;
    status = PASSED;
  
   /***********************************************************/
   /* Convert dir_start + 1 to its respective directory page. */
   /***********************************************************/
  
    dir_starts_page = (dir_start + 1) / DIR_ENTRIES_PER_PAGE;
  
   /***************************************************************/
   /* Convert dir_start + 1 to its respective entry's page index. */
   /* We want to start the first page's index from one after the  */
   /* current starting location.                                  */
   /***************************************************************/
  
    index = (dir_start + 1) % DIR_ENTRIES_PER_PAGE;
  
   /****************************************************************/
   /* Go through all the directory pages starting with dir_start's */
   /* page until we find an usable entry.                          */
   /****************************************************************/
  
    for (page = dir_starts_page; ((page < dir_page_count) &&
        (!avail_entry_found) &&
        (status == PASSED)); page++)
    {
      /************************************************/
      /* Map in the directory page specified by page. */
      /************************************************/
  
        status = map_dir_page (page, FIRST_PHYS_PAGE);
        if (status == PASSED)
        {
         /*****************************************************************/
         /* Go through this page's entries looking for to first available */
         /* entry.  The first time we enter this loop we start with the   */
         /* current starting location + 1 (converted to a page's index)   */
         /* from above.  All other index's after the first page will      */
         /* start with 0.                                                 */
         /*****************************************************************/
  
            for (i = index; ((i < DIR_ENTRIES_PER_PAGE) &&
                (!avail_entry_found)); i++)
            {
                if (directory[0][i].token == UNASSIGNED_TOKEN)
                {
               /*****************************************/
               /* Translate the i index into an entry   */
               /* into the full directory array for the */
               /* new starting location for dir_start.  */
               /*****************************************/
  
                    dir_start = i + page * DIR_ENTRIES_PER_PAGE;
  
               /***************************************/
               /* Make sure the new starting location */
               /* isn't greater than the end.  If so, */
               /* than reset dir_end.                 */
               /***************************************/
  
                    if (dir_start > dir_end)
                        dir_end = dir_start + 1;
                    avail_entry_found = TRUE;
                }
            } /** end for i **/
  
        } /** end if status PASSED **/
  
        index = 0;
  
    } /** end for page **/
  
    return (status);
  
} /** end find_new_dir_start() **/
  
/*$PAGE*/
/**********************************************************************/
/*                                                                    */
/*     Name:    unsigned int break_overlap (best_index)               */
/*              unsigned int *best_index;                             */
/*                                                                    */
/*     Description:                                                   */
/*        This function breaks a free block into two parts at a page  */
/*     boundry.  This is done because check_best_fit() determined     */
/*     that the requested block would overlap a page boundry          */
/*     unnecessarily.  For example, we don't want an 8K block using   */
/*     two logical pages (part of it on one page and the rest on      */
/*     another).  Suppose we want to allocate a 9K block and          */
/*     check_best_fit() determined that a 22K block (6K on one page,  */
/*     16K on the another) was the best fit.  We want to start the 9K */
/*     block on a page boundry so that it will fit in one logical     */
/*     page.  This means that we eventually need to split the 22K     */
/*     block into three pieces:                                       */
/*                                                                    */
/*              6K first free piece on the first logical page.        */
/*              9K allocated piece on the second logical page.        */
/*              7K free space on the second logical page.             */
/*                                                                    */
/*     This routine will do the first split of 6K and 16K.  The       */
/*     function split_block(), called from efmalloc(), (which does    */
/*     all the normal splitting) will split the 16K block into its 9K */
/*     allocated and 7K free pieces.                                  */
/*                                                                    */
/*     Parameters:                                                    */
/*        output  best_index The directory entry of the best fit loc  */
/*                                                                    */
/*     Results returned:                                              */
/*        PASSED     Operation successful                             */
/*        error      Non-zero value, see "ERRORS.H" or EMS table A-2  */
/*                                                                    */
/*     Calls: map_dir_page()                                          */
/*                                                                    */
/*     Called by:  efmalloc()                                         */
/*                 split_block()                                      */
/*                                                                    */
/*     Globals referenced/modified: dir_page_count                    */
/*                                  directory                         */
/*                                  directory_map                     */
/*                                  dir_end                           */
/*                                                                    */
/**********************************************************************/
  
unsigned int break_overlap (best_index)
unsigned int *best_index;
{
    unsigned int i;                 /* Looping variable                  */
    unsigned int entry_found;       /* Whether an entry was found        */
    unsigned int free_space;        /* The free space before a page      */
                                   /* boundry in an overlaping block    */
    unsigned int new_size;          /* The free space starting on a page */
                                   /* boundry in an overlaping block    */
    unsigned int status;            /* Status of EMM and MEMLIB          */
    unsigned int best_indexs_page;  /* Best_index's dir entry's log page */
    unsigned int best_indexs_index; /* Best_index's index into its page  */
    unsigned int page;              /* Current directory page mapped in  */
    unsigned int index;             /* Index into a directory page       */
    unsigned int j;                 /* Loop variable                     */
  
    status = PASSED;
  
   /****************************************************************/
   /* Check if we need to allocate another page for the directory. */
   /****************************************************************/
  
    if (dir_end >= (unsigned int) (NUM_DIR_ENTRIES (dir_page_count) - 2))
        status = allocate_new_directory_page();
  
   /******************************************************************/
   /* Convert best_index to its respective directory page and index. */
   /******************************************************************/
  
    best_indexs_page  = *best_index / DIR_ENTRIES_PER_PAGE;
    best_indexs_index = *best_index % DIR_ENTRIES_PER_PAGE;
  
   /*******************************************/
   /* Map in the best_index's directory page. */
   /*******************************************/
  
    status = map_dir_page (best_indexs_page, FIRST_PHYS_PAGE);
    if (status == PASSED)
    {
      /***************************************/
      /* Set sizes for breaking the overlap. */
      /***************************************/
  
        free_space = PAGE_SIZE - directory[0][best_indexs_index].offset;
        new_size   = directory[0][best_indexs_index].size - free_space;
  
      /**********************************/
      /* Initialize variables for loop. */
      /**********************************/
  
        entry_found = FALSE;
        index       = best_indexs_index;
  
      /****************************************************/
      /* Go through all the directory pages starting with */
      /* best_index's page until we find an usable entry. */
      /****************************************************/
  
        for (page = best_indexs_page; ((page < dir_page_count) &&
            (!entry_found) &&
            (status == PASSED)); page++)
        {
         /************************************************/
         /* Map in the directory page specified by page. */
         /************************************************/
  
            status = map_dir_page (page, SECOND_PHYS_PAGE);
            if (status == PASSED)
            {
            /********************************************************/
            /* Go through this page's entries looking for the first */
            /* available entry.  The first time we enter this loop  */
            /* we start with best_index's entry (converted to a     */
            /* page's index from above).  All other index's after   */
            /* the first page will start with 0.                    */
            /********************************************************/
  
                for (i = index; ((i < DIR_ENTRIES_PER_PAGE) &&
                    (!entry_found) &&
                    (status == PASSED)); i++)
                {
                    if ((directory[1][i].token == UNASSIGNED_TOKEN) &&
                        (directory[1][i].size == 0))
                    {
                  /********************************************/
                  /* We found a usable entry.  Convert i to   */
                  /* a full directory entry for best_index.   */
                  /* Best_index will now point to this        */
                  /* directory entry though best_indexs_index */
                  /* and best_indexs_page will still refer to */
                  /* the original best_index.  Set this       */
                  /* directory entry to point to the          */
                  /* allocated block.                         */
                  /********************************************/
  
                        *best_index            = i + (page * DIR_ENTRIES_PER_PAGE);
                        directory[1][i].token  = *best_index;
                        directory[1][i].size   = new_size;
                        directory[1][i].offset = 0;
  
                  /*************************************/
                  /* Set logical pages for this block. */
                  /*************************************/
  
                        for (j = 0; j < NUM_PAGES (new_size); j++)
                        {
                            directory[1][i].logical_page[j] =
                            directory[0][best_indexs_index].logical_page[j + 1];
                        }
  
                  /***********************************/
                  /* Update size for original block. */
                  /***********************************/
  
                        directory[0][best_indexs_index].size = free_space;
  
                  /*****************************/
                  /* Update dir_end if needed. */
                  /*****************************/
  
                        if (*best_index >= dir_end)
                            dir_end = *best_index + 1;
  
                        entry_found = TRUE;
  
                    } /** end if directory[1][i] **/
  
                } /** end for i **/
  
                index = 0;
  
            } /** end if status PASSED **/
  
        } /** end for page **/
  
    } /** end if status PASSED **/
  
    return (status);
  
} /** done break_overlap() **/
  
/*$PAGE*/
/**********************************************************************/
/*                                                                    */
/*     Name:  unsigned int check_best_fit (size, best_index,          */
/*                                           min_difference)          */
/*            unsigned int size;                                      */
/*            unsigned int *best_index;                               */
/*            long         *min_difference;                           */
/*                                                                    */
/*     Description:                                                   */
/*        This function finds the best fit for a block of memory      */
/*     asked for in efmalloc().                                       */
/*                                                                    */
/*     Parameters:                                                    */
/*        input    size           The desired size of the block of    */
/*                                memory.                             */
/*        output   best_index     The directory entry of the best fit */
/*        output   min_difference The remainder from best_fit()       */
/*                                                                    */
/*     Results returned:                                              */
/*        PASSED     Operation successful                             */
/*        error      Non-zero value, see "ERRORS.H" or EMS table A-2  */
/*                                                                    */
/*     Calls: allocate_new_directory_page()                           */
/*            map_dir_page()                                          */
/*            break_overlap()                                         */
/*            find_new_dir_start()                                    */
/*                                                                    */
/*     Called by: efmalloc()                                          */
/*                                                                    */
/*     Globals referenced/modified: dir_page_count                    */
/*                                  directory                         */
/*                                  directory_map                     */
/*                                  dir_start                         */
/*                                  dir_end                           */
/*                                                                    */
/**********************************************************************/
  
unsigned int check_best_fit (size, best_index, min_difference)
unsigned int size;
unsigned int *best_index;
long         *min_difference;
{
    unsigned int index;                  /* Index into a directory page      */
    unsigned int status;                 /* Status of EMM and MEMLIB         */
    unsigned int page;                   /* Directory page to map in         */
    unsigned int size_mod_page_size;     /* Size of block MOD PAGE_SIZE      */
    unsigned int free_space;             /* The free space before a page     */
                                        /* boundry in a free block          */
    unsigned int dir_starts_page;        /* Dir_start's dir entry's log page */
    long         this_ones_min_diff;     /* Current block's min difference   */
    unsigned int this_ones_offset;       /* Current block's offset into a    */
                                        /* logical page                     */
    long         new_size;               /* Free space after page boundry    */
    unsigned int found_exact_fit;        /* Whether we found an exact fit    */
    unsigned int overlap;                /* Whether we have an overlapping   */
                                        /* block                            */
    long         overlap_min_difference; /* Minimum difference for the       */
                                        /* overlapping block                */
  
   /************************************************/
   /* Initialize variables for best fit algorithm. */
   /************************************************/
  
    index                  = dir_start % DIR_ENTRIES_PER_PAGE;
    *best_index            = UNASSIGNED_TOKEN;
    found_exact_fit        = FALSE;
    overlap                = FALSE;
    *min_difference        = LARGEST_ALLOCATABLE_BLOCK;
    status                 = PASSED;
    overlap_min_difference = LARGEST_ALLOCATABLE_BLOCK;
    size_mod_page_size     = size % PAGE_SIZE;
  
    if (size_mod_page_size == 0)
        size_mod_page_size = PAGE_SIZE;
  
   /**************************************************/
   /* Make sure a new directory page is allocated    */
   /* before it is needed.  This done so the a block */
   /* that has free mem will not be lost to the      */
   /* the purple zone before a new directory page    */
   /* is allocated in allocate_new_block().         */
   /* Allocate_new_directory_page() is called when   */
   /* the current directory entries is two from      */
   /* being filled up.                               */
   /**************************************************/
  
    if (dir_end >= (unsigned int) (NUM_DIR_ENTRIES (dir_page_count) - 2))
        status = allocate_new_directory_page();
  
    if (status == PASSED)
    {
        dir_starts_page = dir_start / DIR_ENTRIES_PER_PAGE;
  
      /*****************************************/
      /* Go through all of the directory pages */
      /* until we find an exact fit.           */
      /*****************************************/
  
        for (page = dir_starts_page; ((page < dir_page_count) &&
            (!found_exact_fit) &&
            (status == PASSED)); page++)
        {
         /**********************************/
         /* Map in the this directory page */
         /**********************************/
  
            status = map_dir_page (page, FIRST_PHYS_PAGE);
            if (status == PASSED)
            {
            /*********************************************************/
            /* Go through the current page looking for the best fit. */
            /*********************************************************/
  
                while ((index < DIR_ENTRIES_PER_PAGE) &&
                    ((index + page * DIR_ENTRIES_PER_PAGE) <= dir_end) &&
                    (!found_exact_fit))
                {
               /*****************************************/
               /* If this block of memory is available. */
               /*****************************************/
  
                    if (directory[0][index].token == UNASSIGNED_TOKEN)
                    {
                  /************************************************/
                  /* If size is 0 then this block is unallocated. */
                  /************************************************/
  
                        if (directory[0][index].size == 0)
                        {
                     /*********************************************/
                     /* If best_index = UNASSIGNED_TOKEN we       */
                     /* haven't found any previous blocks to use. */
                     /*********************************************/
  
                            if (*best_index == UNASSIGNED_TOKEN)
                                *best_index = index + (page * DIR_ENTRIES_PER_PAGE);
                        }
                        else
                        {
                     /************************************************/
                     /* This is a previously freed block and we need */
                     /* to check how close of a fit it is.           */
                     /************************************************/
  
                            this_ones_min_diff = (long) directory[0][index].size - size;
                            if ((this_ones_min_diff >= 0) &&
                                (this_ones_min_diff < *min_difference))
                            {
                        /**************************************/
                        /* If exact fit then take this block. */
                        /**************************************/
  
                                if (this_ones_min_diff == 0)
                                {
                                    found_exact_fit = TRUE;
                                    *best_index     = index + (page * DIR_ENTRIES_PER_PAGE);
                                    *min_difference = 0;
                                    overlap         = FALSE;
                                }
                                else
                                {
                           /***********************************************/
                           /* Make sure that putting the newly allocated  */
                           /* block at the beginning of the free block    */
                           /* won't cause the new block to overlap more   */
                           /* logical pages than it needs.                */
                           /*                                             */
                           /* If the remainder of the requested block     */
                           /* size MOD PAGE_SIZE will fit in the first    */
                           /* logical page of the freed block, then the   */
                           /* requested block will fit correctly.         */
                           /***********************************************/
  
                           /*******************************************/
                           /* Where this free block starts within its */
                           /* first logical page.                     */
                           /*******************************************/
  
                                    this_ones_offset = directory[0][index].offset;
  
                           /********************************************/
                           /* The room left on the first logical page. */
                           /********************************************/
  
                                    free_space = PAGE_SIZE - this_ones_offset;
  
                                    if (free_space >= size_mod_page_size)
                                    {
                              /******************************************/
                              /* The block will fit just fine.  We will */
                              /* have the block itself and a remainder. */
                              /******************************************/
  
                                        *best_index     = index + (page * DIR_ENTRIES_PER_PAGE);
                                        *min_difference = this_ones_min_diff;
                                        overlap         = FALSE;
                                    }
                                    else
                                    {
                              /********************************************/
                              /* The new block will fit but we have to    */
                              /* start it on this free block's first page */
                              /* boundry.  We will need to keep track of  */
                              /* the space before the page boundry, the   */
                              /* new block, and any remainder from the    */
                              /* new block.  We will have an overlap to   */
                              /* break.                                   */
                              /********************************************/
  
                                        new_size = (long) directory[0][index].size - free_space;
                                        if (new_size >= size)
                                        {
                                            overlap = TRUE;
                                            this_ones_min_diff = new_size - size;
                                            if (this_ones_min_diff < overlap_min_difference)
                                            {
                                                overlap_min_difference = new_size - size;
                                                *best_index = index + (page * DIR_ENTRIES_PER_PAGE);
                                            }
                                        }
                                    } /** end else **/
  
                                } /** end else **/
  
                            } /** end if temp_difference ... **/
  
                        } /** end else **/
  
                    } /** end if directory **/
  
                    index++;
  
                } /** end while **/
  
            } /** end if passed **/
            index = 0;
  
        } /** end if page **/
  
      /**********************************************/
      /* If we have an overlap we need to break it. */
      /**********************************************/
  
        if ((overlap) &&
            (status == PASSED))
        {
            *min_difference = overlap_min_difference;
            status = break_overlap (best_index);
        }
  
      /****************************************************/
      /* Update our starting entry if the current one ==  */
      /* to best_index and we don't have an overlap.      */
      /****************************************************/
  
        if ((dir_start == *best_index) &&
            (!overlap) &&
            (status == PASSED))
            status = find_new_dir_start();
  
      /**************************************/
      /* Update our ending entry if needed. */
      /**************************************/
  
        if ((*best_index >= dir_end) &&
            (status == PASSED))
            dir_end = *best_index + 1;
  
    } /** end if passed **/
  
    return (status);
  
} /* end check_best_fit() */
  
/*$PAGE*/
/**********************************************************************/
/*                                                                    */
/*     Name: unsigned int check_if_all_blocks_free (all_blocks_free)  */
/*           unsigned int *all_blocks_free;                           */
/*                                                                    */
/*     Description:                                                   */
/*        If the block being freed by effree() is the last one to be  */
/*     freed then we need to deallocate all the pages allocated to    */
/*     this application.  This tells us that the program using MEMLIB */
/*     may be terminating and we want to be sure that all pages for   */
/*     this application have been deallocated.  This function will    */
/*     see if there are any blocks left in the directory that are     */
/*     allocated and if not, will deallocate all pages that this      */
/*     application owns.                                              */
/*                                                                    */
/*     Parameters:                                                    */
/*        output  free_status     TRUE - all blocks are free          */
/*                                FALSE - there are some blocks used  */
/*                                                                    */
/*     Results returned:                                              */
/*        PASSED    Operation successful                              */
/*        error     Non-zero value, see "ERRORS.H" or EMS table A-2   */
/*                                                                    */
/*     Calls: map_dir_page()                                          */
/*                                                                    */
/*     Called by: effree()                                            */
/*                                                                    */
/*     Globals referenced/modified: dir_page_count                    */
/*                                  directory                         */
/*                                  directory_map                     */
/*                                                                    */
/**********************************************************************/
  
unsigned int check_if_all_blocks_free (all_blocks_free)
unsigned int *all_blocks_free;
{
    unsigned int status;       /* Status of EMM and MEMLIB          */
    unsigned int page;         /* Current directory page mapped in  */
    unsigned int index;        /* Current index into a logical page */
  
   /******************************/
   /* Assume all blocks are free */
   /* and status OK.             */
   /******************************/
  
    *all_blocks_free = TRUE;
    status           = PASSED;
  
   /**************************************************************/
   /* Loop through the directory, checking for non-freed blocks. */
   /**************************************************************/
  
    for (page = 0; ((page < dir_page_count) &&
        (*all_blocks_free) &&
        (status == PASSED)); page++)
    {
      /*******************************/
      /* Map in this directory page. */
      /*******************************/
  
        status = map_dir_page (page, FIRST_PHYS_PAGE);
        if (status == PASSED)
        {
         /************************************/
         /* Check all index's for this page. */
         /************************************/
  
            for (index = 0; ((index < DIR_ENTRIES_PER_PAGE) &&
                (*all_blocks_free)); index++)
            {
                if (directory[0][index].token != UNASSIGNED_TOKEN)
                {
               /**********************************************/
               /* If we find a block that's being used, set  */
               /* all_block_free to FALSE and stop checking. */
               /**********************************************/
  
                    *all_blocks_free = FALSE;
                }
            } /** end for index **/
  
        } /** end if status PASSED **/
  
    } /** end for page **/
  
    return (status);
  
}  /** end if_all_blocks_free **/
  
  
/*$PAGE*/
/**********************************************************************/
/*                                                                    */
/*     Name:  unsigned int coalesce_block (block1, block2, coalasce)  */
/*            unsigned int block1;                                    */
/*            unsigned int block2;                                    */
/*            unsigned int *coalesce;                                 */
/*                                                                    */
/*     Description:                                                   */
/*        This coalesces one block of free expanded memory (block1)   */
/*     to another (block2).                                           */
/*                                                                    */
/*     Parameters:                                                    */
/*        input    block1      The identifier for the first block.    */
/*                 block2      The identifier for the second block.   */
/*         output  coalesce    Whether we really coalesced or not.    */
/*                                                                    */
/*     Results returned:                                              */
/*        PASSED     Coalescing successful or not needed              */
/*        error      Non-zero value, see "ERRORS.H" or EMS table A-2  */
/*                                                                    */
/*     Calls: map_dir_page()                                          */
/*            get_context()                                           */
/*            set_context()                                           */
/*                                                                    */
/*     Called by:  search_before()                                    */
/*                 search_after()                                     */
/*                                                                    */
/*     Globals referenced/modified: directory                         */
/*                                  directory_map                     */
/*                                                                    */
/**********************************************************************/
  
unsigned int coalesce_block (block1, block2, coalesce)
unsigned int block1;
unsigned int block2;
unsigned int *coalesce;
{
    unsigned int   j;              /* Looping variable                     */
    unsigned int   block1s_page;   /* Block1's directory entry's log page  */
    unsigned int   block1s_index;  /* Block1's index into its logical page */
    unsigned int   block2s_page;   /* Block2's directory entry's log page  */
    unsigned int   block2s_index;  /* Block2's index into its logical page */
    unsigned int   end_of_block2;  /* End of block2 (size+offset)          */
    unsigned int   start_page;     /* Starting logical page for coalescing */
    unsigned int   status;         /* Status of EMM and MEMLIB             */
    CONTEXT_STRUCT context;        /* For storing the current context      */
  
   /******************************************************************/
   /* We need to continue where we left off from when we return      */
   /* to search_before() or search_after(), so we need to save       */
   /* the pages they had mapped in before they called this function. */
   /******************************************************************/
  
    status = get_context (&context);
    if (status == PASSED)
    {
      /**************************************************************/
      /* Convert block1 to its respective directory page and index. */
      /**************************************************************/
  
        block1s_page  = block1 / DIR_ENTRIES_PER_PAGE;
        block1s_index = block1 % DIR_ENTRIES_PER_PAGE;
  
      /***********************************/
      /* Map in block1's directory page. */
      /***********************************/
  
        status = map_dir_page (block1s_page, FIRST_PHYS_PAGE);
    }
  
    if (status == PASSED)
    {
      /*********************************************************/
      /* Convert block1 to its respective directory page and   */
      /* index.  We're going to map this page into the second  */
      /* physical page.  In order to access this pages entries */
      /* we need to offset its indexes by DIR_ENTRIES_PER_PAGE */
      /* from the beginning of the first physical page.        */
      /*********************************************************/
  
        block2s_page  = block2 / DIR_ENTRIES_PER_PAGE;
        block2s_index = block2 % DIR_ENTRIES_PER_PAGE;
  
      /*****************************************************/
      /* Map in block2's directory page using the          */
      /* directory_map's second array element to map this  */
      /* page in at physical page one while keeping        */
      /* block1's  directory page at physical page zero.   */
      /*****************************************************/
  
        status = map_dir_page (block2s_page, SECOND_PHYS_PAGE);
  
      /****************************/
      /* Coalesce the two blocks. */
      /****************************/
  
        if (status == PASSED)
        {
         /****************************************/
         /* Assume we will coalesce these blocks */
         /****************************************/
  
            *coalesce = TRUE;
  
         /*********************************************/
         /* Set the starting logical page for block2. */
         /*********************************************/
  
            end_of_block2 = (directory[1][block2s_index].offset +
            directory[1][block2s_index].size) % PAGE_SIZE;
  
            if (end_of_block2 == 0)
                start_page = NUM_PAGES (directory[1][block2s_index].size);
            else
                start_page = NUM_PAGES (directory[1][block2s_index].size) - 1;
  
         /********************************************************/
         /* If combining the blocks would cause too many logical */
         /* pages to be used, DON'T coalesce them.               */
         /********************************************************/
  
            if ((start_page + NUM_PAGES (directory[0][block1s_index].size))
                >= MAX_ALLOCATABLE_PAGES)
                *coalesce = FALSE;
  
            if (*coalesce)
            {
  
            /*****************************************************/
            /* Combine the logical pages for block1 into block2. */
            /*****************************************************/
  
                for (j = 0; j < NUM_PAGES (directory[0][block1s_index].size); j++)
                {
                    directory[1][block2s_index].logical_page[start_page + j] =
                    directory[0][block1s_index].logical_page[j];
                }
  
            /******************************************/
            /* Set block2's size to the combined size */
            /* and zero out block 1.                  */
            /******************************************/
  
                directory[1][block2s_index].size += directory[0][block1s_index].size;
                directory[0][block1s_index].size = 0;
  
            }
        }
    }
  
   /************************************/
   /* Restore the pages that were here */
   /* before this function was called. */
   /************************************/
  
    if (status == PASSED)
        status = set_context (&context);
  
    return (status);
  
} /** end coalesce_block() **/
  
/*$PAGE*/
/**********************************************************************/
/*                                                                    */
/*     Name:  unsigned int search_after (token, final_entry,          */
/*                                         usable_entry)              */
/*            unsigned int token;                                     */
/*            unsigned int *final_entry;                              */
/*            unsigned int *usable_entry;                             */
/*                                                                    */
/*     Description:                                                   */
/*        This function searches for a free block of memory after the */
/*     block of memory we just freed.  This is done in order to       */
/*     coalesce the two blocks.                                       */
/*                                                                    */
/*     Parameters:                                                    */
/*        input   token        The token of the block of memory       */
/*                             that's been freed                      */
/*        output  final_entry  The directory entry of the final       */
/*                             coalesced block or unassigned if no    */
/*                             blocks were found.                     */
/*                usable_entry The directory entry of a usable block  */
/*                                                                    */
/*     Results returned:                                              */
/*        PASSED     Operation successful                             */
/*        error      Non-zero value, see "ERRORS.H" or EMS table A-2  */
/*                                                                    */
/*     Calls: coalesce_block()                                        */
/*            map_dir_page()                                          */
/*                                                                    */
/*     Called by: effree()                                            */
/*                                                                    */
/*     Globals referenced/modified: directory                         */
/*                                  directory_map                     */
/*                                  dir_page_count                    */
/*                                                                    */
/**********************************************************************/
  
unsigned int search_after (token, final_entry, usable_entry)
unsigned int token;
unsigned int *final_entry;
unsigned int *usable_entry;
{
    unsigned int index;              /* Index into a directory page         */
    unsigned int indexs_entry;       /* Index translated to a full dir entry*/
    unsigned int coalesce;           /* Whether we should coalesce or not   */
    unsigned int tokens_last_page;   /* Last logical page for token's block */
    unsigned int end_of_tokens_block;/* The end of token's block            */
    unsigned int page;               /* Directory pages to loop through     */
    unsigned int tokens_page;        /* Token's directory entry's log page  */
    unsigned int tokens_index;       /* Token's index into its logical page */
    unsigned int status;             /* Status of EMM and MEMLIB            */
  
   /****************************************************************/
   /* Convert the token passed in to its respective directory page */
   /* and index.  We're going to map this page into the second     */
   /* physical page.  In order to access this pages entries we     */
   /* need to use second_dir_page.                                 */
   /****************************************************************/
  
    tokens_page  = token / DIR_ENTRIES_PER_PAGE;
    tokens_index = token % DIR_ENTRIES_PER_PAGE;
  
   /*********************************************************/
   /* Map in the token's directory page using the           */
   /* directory_map's second array element to map this page */
   /* in at physical page one while keeping the block to be */
   /* coalesced's directory page at physical page zero.     */
   /*********************************************************/
  
    status = map_dir_page (tokens_page, SECOND_PHYS_PAGE);
    if (status == PASSED)
    {
      /**********************************/
      /* Find the end of token's block. */
      /**********************************/
  
        end_of_tokens_block = (directory[1][tokens_index].size +
        directory[1][tokens_index].offset) % PAGE_SIZE;
  
      /**************************/
      /* Set variables for loop */
      /**************************/
  
        *final_entry     = UNASSIGNED_TOKEN;
        tokens_last_page = NUM_PAGES (directory[1][tokens_index].size) - 1;
        coalesce         = FALSE;
  
      /******************************************************/
      /* Search for a free block of memory after this block */
      /* to coalesce into one free block.                   */
      /******************************************************/
  
        for (page = 0; ((page < dir_page_count) &&
            (status == PASSED) &&
            (!coalesce)); page++)
        {
         /*******************************/
         /* Map in this directory page. */
         /*******************************/
  
            status = map_dir_page (page, FIRST_PHYS_PAGE);
         /*********************************************/
         /* Go through all the indexes for this page. */
         /*********************************************/
  
            for (index = 0; ((index < DIR_ENTRIES_PER_PAGE) &&
                (status == PASSED) &&
                (!coalesce)); index++)
            {
            /********************************************/
            /* Convert index to a full directory entry. */
            /********************************************/
  
                indexs_entry = index + page * DIR_ENTRIES_PER_PAGE;
  
            /*********************************************************/
            /* For index's block test:                               */
            /* Is it free?                                           */
            /* Is it > 0?                                            */
            /* Is it different than the block we called effree with? */
            /* Would its size make a coalesced block > 64K?          */
            /*********************************************************/
  
                if ((directory[0][index].token == UNASSIGNED_TOKEN) &&
                    (directory[0][index].size > 0) &&
                    (indexs_entry != token) &&
                    ((unsigned long) directory[0][index].size +
                    directory[1][tokens_index].size < K64K))
                {
               /****************************************************/
               /* If the end of token's block equals the beginning */
               /* of index's block then index's block could lie    */
               /* AFTER our block.                                 */
               /****************************************************/
  
                    if (end_of_tokens_block == directory[0][index].offset)
                    {
                  /******************************************************/
                  /* Test the logical pages for these two blocks to     */
                  /* see if we want to coalesce them.  We will coalesce */
                  /* if either of the following is true:                */
                  /*                                                    */
                  /* 1. If the token's block ends on an exact page      */
                  /*    boundry (end_of_tokens_block == 0) then we do   */
                  /*    NOT want the last logical page of token's block */
                  /*    to match the first logical page of index's      */
                  /*    block.                                          */
                  /*                                                    */
                  /* 2. If token's block ends in the middle of a        */
                  /*    logical page (end_of_tokens_block != 0) the we  */
                  /*    DO want token's block's last logical page to    */
                  /*    match index's block's first logical page.       */
                  /******************************************************/
  
                        if (end_of_tokens_block == 0)
                        {
                            if (directory[1][tokens_index].logical_page[tokens_last_page]
                                != directory[0][index].logical_page[0])
                            {
                                coalesce = TRUE;
                            }
                        }
                        else
                        {
                            if (directory[1][tokens_index].logical_page[tokens_last_page]
                                == directory[0][index].logical_page[0])
                            {
                                coalesce = TRUE;
                            }
                        }
                        if (coalesce)
                        {
                     /************************************/
                     /* We've got a winner! Coalesce the */
                     /* i'th block into our block.       */
                     /************************************/
  
                            status = coalesce_block (indexs_entry, token, &coalesce);
  
                            if ((status == PASSED) && coalesce)
                            {
                                *final_entry  = token;
                                *usable_entry = indexs_entry;
                            }
  
                        } /** end if coalesce **/
  
                    } /** end if end_of_tokens_block **/
  
                }  /** end if directory **/
  
            }  /** end for index **/
  
        }  /** end for page **/
  
    } /** end if PASSED **/
  
    return (status);
  
} /** end search_after() **/
  
/*$PAGE*/
/**********************************************************************/
/*                                                                    */
/*     Name:  unsigned int search_before (token, final_entry,         */
/*                                          usable_entry)             */
/*            unsigned int token;                                     */
/*            unsigned int *final_entry;                              */
/*            unsigned int *usable_entry;                             */
/*                                                                    */
/*     Description:                                                   */
/*        This function searches for a free block of memory before    */
/*     the block of memory we just freed.  This is done in order to   */
/*     coalesce the two blocks.                                       */
/*                                                                    */
/*     Parameters:                                                    */
/*        input   token        The token of the block of memory       */
/*                             that's been freed                      */
/*        output  final_entry  The directory entry of the final       */
/*                             coalesced block or unassigned if no    */
/*                             blocks were found.                     */
/*                temp_entry   The directory entry of a usable block  */
/*                                                                    */
/*     Results returned:                                              */
/*        PASSED     Operation successful                             */
/*        error      Non-zero value, see "ERRORS.H" or EMS table A-2  */
/*                                                                    */
/*     Calls: coalesce_block()                                        */
/*            map_dir_page()                                          */
/*                                                                    */
/*     Called by: effree()                                            */
/*                                                                    */
/*     Globals referenced/modified: directory                         */
/*                                  directory_map                     */
/*                                  dir_page_count                    */
/*                                                                    */
/**********************************************************************/
  
unsigned int search_before (token, final_entry, usable_entry)
unsigned int token;
unsigned int *final_entry;
unsigned int *usable_entry;
{
    unsigned int index;              /* Index into a directory page          */
    unsigned int indexs_entry;       /* Index translated to a full dir entry */
    unsigned int indexs_last_page;   /* Last logical page for index's block  */
    unsigned int coalesce;           /* Whether we should coalesce or not    */
    unsigned int end_of_indexs_block;/* The end of token's block             */
    unsigned int page;               /* Directory pages to loop through      */
    unsigned int tokens_page;        /* Token's directory entry's log page   */
    unsigned int tokens_index;       /* Token's index into its logical page  */
    unsigned int status;             /* Status of EMM and MEMLIB             */
  
   /****************************************************************/
   /* Convert the token passed in to its respective directory page */
   /* and index.  We're going to map this page into the second     */
   /* physical page.  In order to access this page's entries we    */
   /* need to use directory[1].                                    */
   /****************************************************************/
  
    tokens_page  = token / DIR_ENTRIES_PER_PAGE;
    tokens_index = token % DIR_ENTRIES_PER_PAGE;
  
   /*********************************************************/
   /* Map in the token's directory page using the           */
   /* directory_map's second array element to map this page */
   /* in at physical page one while keeping the block to be */
   /* coalesced's directory page at physical page zero.     */
   /*********************************************************/
  
    status = map_dir_page (tokens_page, SECOND_PHYS_PAGE);
    if (status == PASSED)
    {
      /***************************/
      /* Set variables for loop. */
      /***************************/
  
        coalesce = FALSE;
  
      /*************************************************/
      /* Search for a free block of memory before this */
      /* block to coalesce into one free block.        */
      /*************************************************/
  
        for (page = 0; ((page < dir_page_count) &&
            (status == PASSED) &&
            (!coalesce)); page++)
        {
         /*******************************/
         /* Map in this directory page. */
         /*******************************/
  
            status = map_dir_page (page, FIRST_PHYS_PAGE);
  
         /*********************************************/
         /* Go through all the indexes for this page. */
         /*********************************************/
  
            for (index = 0; ((index < DIR_ENTRIES_PER_PAGE) &&
                (status == PASSED) &&
                (!coalesce)); index++)
            {
            /********************************************/
            /* Convert index to a full directory entry. */
            /********************************************/
  
                indexs_entry = index + page * DIR_ENTRIES_PER_PAGE;
  
            /*********************************************************/
            /* For index's block test:                               */
            /* Is it free?                                           */
            /* Is it > 0?                                            */
            /* Is it different than the block we called effree with? */
            /* Would its size make a coalesced block > 64K?          */
            /*********************************************************/
  
                if ((directory[0][index].token == UNASSIGNED_TOKEN) &&
                    (directory[0][index].size > 0) &&
                    (indexs_entry != token) &&
                    ((unsigned long) directory[0][index].size +
                    directory[1][tokens_index].size < K64K))
                {
                    end_of_indexs_block = (directory[0][index].offset +
                    directory[0][index].size) % PAGE_SIZE;
  
                    indexs_last_page = NUM_PAGES (directory[0][index].size) - 1;
  
  
               /*********************************************/
               /* If the beginning of token's block exactly */
               /* matches the end of index's block then     */
               /* index's block could lie BEFORE our block. */
               /*********************************************/
  
                    if (directory[1][tokens_index].offset == end_of_indexs_block)
                    {
                  /******************************************************/
                  /* Test the logical pages for these two blocks to     */
                  /* see if we want to coalesce them.  We will coalesce */
                  /* if either of the following is true:                */
                  /*                                                    */
                  /* 1. If the token's block ends on an exact page      */
                  /*    boundry (end_of_indexs_block == 0) then we do   */
                  /*    NOT want the first logical page of token's      */
                  /*    block to match the last logical page of index's */
                  /*    block.                                          */
                  /*                                                    */
                  /* 2. If token's block ends in the middle of a        */
                  /*    logical page (end_of_indexs_block != 0) the we  */
                  /*    DO want token's block's first logical page to   */
                  /*    match index's block's last logical page.        */
                  /******************************************************/
  
                        if (end_of_indexs_block == 0)
                        {
                            if (directory[0][index].logical_page[indexs_last_page] !=
                                directory[1][tokens_index].logical_page[0])
                            {
                                coalesce   = TRUE;
                            }
                        }
                        else
                        {
                            if (directory[0][index].logical_page[indexs_last_page] ==
                                directory[1][tokens_index].logical_page[0])
                            {
                                coalesce   = TRUE;
                            }
                        }
                        if (coalesce)
                        {
                     /************************************/
                     /* We've got a winner! Coalesce the */
                     /* i'th block into our block.       */
                     /************************************/
  
                            status = coalesce_block (token, indexs_entry, &coalesce);
  
                            if ((status == PASSED) &&
                                coalesce)
                            {
                                *final_entry  = indexs_entry;
                                *usable_entry = token;
                            }
  
                        } /** end if coalesce **/
  
                    } /** end if directory **/
  
                }  /** end if directory **/
  
            }  /** end for index = 0 **/
  
        }  /** end for page **/
  
    } /** end if PASSED **/
  
    return (status);
}  /** end search_before() **/
  
  
  
  
  
