Range Tracking & Comparison Algorithms 
by Kirk J. Krauss


Listing One
/* The Create Range List algorithm                                   */
/* Tracks a current set of address ranges for the objects that meet  */
/* specific criteria. Coalesces the ranges of a contiguous set of    */
/* these objects into a single range list element, minimizing the    */
/* list's size and optimizing subsequent range list diff performance */
/* Returns the list of ranges that are identified and tracked here.  */

/* Input parameters */
ADDRESS startAddr
ADDRESS stopAddr

/* Local variables */
LIST    a new list of ranges
BOOL    bListRange = FALSE

/* All other variables are references to address range tracking      */
/* list  elements.  At minimum, there will be a references to the    */
/* "current" element in the new list being created.                  */

Allocate and initialize the header for the new list of ranges

IF (startAddr) DO
    Determine the first object that resides at or above startAddr
    Make that object "current"
    END
ELSE DO
    Determine the first object that can be found
    Make that object "current"
    END

/* Walk through the address space, building the list of address      */
/* that meet a user-defined set of selection criteria                */
WHILE ((the address of the "current" object) < stopAddr) DO
    IF (the "current" object meets range listability selection criteria)
        bListRange = TRUE
      
    IF (bListRange) DO
        IF (there is a "current" range tracking element) DO
            /* Add up the sizes of any contiguous objects that       */
            /* meet the selection criteria for our list.             */
            Add the "current" object's size to the size of the 
                  "current" range tracking element
            END
        ELSE DO
            /* This is the first listworthy object we've             */
            /* encountered lately.                                   */
            /*** A GOOD BREAKPOINT ***/
            Allocate a range tracking element and make it "current"
            Set the range base to the base of the "current" object
            Set the range size to the size of the "current" object
            END
        END
    ELSE
        bListRange = FALSE
    
    IF (there is a "current" range tracking element) DO
        /* Did we just walk past the "upper" end of a set of         */
        /* contiguous objects to be listed?                          */
        IF (!bListRange) DO
            /*** A GOOD BREAKPOINT ***/
            Add the "current" range element to the range list
            Update local state so that there is no "current" range 
                  element
            END
        END

        find the object at the next "higher" address
        make it "current"
END /* WHILE loop */

IF (there is a "current" range tracking element) DO
    /* Clean up loose ends. */
    Add the "current" range element to the range list
END

RETURN the new list of ranges


Listing Two 

/* The Destroy Range List algorithm                                  */
/* Frees all the memory associated with an outdated list of          */
/* contiguous address ranges.                                        */

/* Input parameter */
LIST    a list of ranges

/* All other variables are references to address range tracking      */
/* list  elements.  These include references to the "current" and    */
/* "next" elements in the list being destroyed.                      */

look up the first range on the old list and make it "current"

WHILE (there is a "current" list element) DO
    look up the next range on the old list and make it "next"
    delete the "current" list element
    make the "next" element "current"
    END

free the list header





2


