Computer-implemented object-oriented method for relating objects in a compiler to locations in the source program and to inlined call histories6106574Abstract An object-oriented method and apparatus for relating objects in a compiler program running on a computer for compiling source files into a binary code file for execution on a target computer to source code locations, said apparatus includes a type of object that identifies a source location, and where inlining occurs, a list of inlined source locations. The type of object has only one instance variable, an integer. The invention includes a method for relating objects in a compiler to source code locations. The method includes the steps of registering source files and their ranges of line numbers for a source type; for each language element parsed by the compiler, creating a source object for its source location; and, creating an instance variable of type source for each compiler object in order to relate to their source locations. Claims What is claimed is: Description A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
______________________________________
LINE NO. FILE1
______________________________________
1 int f(int x)
2 {return 10 / x;}
______________________________________
LINE NO. FILE2
______________________________________
1 #include "FILE1"
2 int main ( )
3 {int a, b;
4 a = f(10);
5 b = f(0);
6 return a + b;}
______________________________________
EXAMPLE Execution of the binary program resulting from compiling the files set forth in the EXAMPLE above with a C compiler is interrupted in the function f in FILE 1 at line 2 when the machine instruction doing a divide operation tries to divide by zero. That is, the call history is (FILE1, line 2), (FILE2, line 5). The second source location in the call history is the place where the function f is called when it is interrupted. In the EXAMPLE illustrated and explained above, if the function f is inlined, then there is no call instruction from which to determine a call history if the prior art multipass compiler is used. For call histories to be properly determined for inlined functions, the tables in the binary file must include portions of call histories in place of mere source locations. Using the present invention, the inlined divide operation for the first call on the function f is mapped to the call history (FILE1, line 2), (FILE2, line 4), and the inlined divide operation for the second call is mapped to the call history (FILE1, line 2), (FILE2, line 5). Having call histories for inlined functions stored in the binary file allows a debugging tool or other diagnostic software to show complete call histories. The tables below show the information mapping machine instructions to source locations that would be stored along with the machine instructions in a binary file for example. Actual machine instructions are not shown. The first column of each table describes in words what would actually be numerical offsets into the stream of machine instructions stored in the binary file. When the function f is not inlined:
TABLE I
______________________________________
Index into machine Corresponding source
instructions for: locations
______________________________________
return 10 / x FILE2 line 2
Allocation of a and b
FILE1 line 3
call f(10) and assignment to a
FILE1 line 4
call f(0) and assignment to b
FILE1 line 5
return a + b FILE1 line 6
______________________________________
When the function f is inlined:
TABLE II
______________________________________
Index into machine
Corresponding source
instructions for: locations
______________________________________
Allocation of a and b
FILE1 line 3
10 / 10 FILE2 line 2, FILE1 line 4
assignment to a FILE1 line 4
10 / 0 FILE2 line 2, FILE1 line 5
assignment to b FILE1 line 5
return a + b FILE1 line 6
______________________________________
Both tables allow a debugging tool or other diagnostic software to provide the same correct call history, using the call instruction in TABLE I, and the inlined call history in TABLE II. Referring now to FIG. 2A, a Source Coarse Table is shown that corresponds to the source files illustrated in the EXAMPLE above when the function f is not inlined. A Source Fine Table is shown in FIG. 2B that corresponds to the source files illustrated in the EXAMPLE when the function f is not inlined. FIG. 2C illustrates a Source Coarse Table that corresponds to the source files illustrated in the EXAMPLE when the function f is inlined. FIG. 2D illustrates a Source Fine Table that corresponds to the source files illustrated in the EXAMPLE when the function is inlined. It is noted that the Source Coarse and Fine Tables illustrated in FIGS. 2A through 2D are stored in the compiler 20 and are an intermediate form of the source information that allows one to build tables (e.g., TABLES I and II, above) in the binary file. Again referring to FIG. 2A, the illustrated Source Coarse Table object shown is the root source table. A Source Coarse Table object contains four instance variables. For the Source Coarse Table object shown in FIG. 2A, the first instance variable, my last index ("myLastX"), has a value of zero, which indicates that the last used index in my coarse table is zero. The second instance variable, my current index ("myCurrentX"), has a value of zero and is used to optimize repeated inquires on the same element in my coarse table. The third instance variable, my coarse level ("myCoarseLvl"), has a value of zero, which indicates that there are only Source Fine Table objects contained in my coarse table. Finally, the fourth instance variable, my coarse table ("myCoarseTbl"), is the table containing Source Table Range objects. In this particular coarse table there is only one Source Table Range object currently in use. A Source Table Range object contains four instance variables. For the Source Table Range object shown in FIG. 2A, the first and second instance variables, my first index and my last index, have the values one and eight, respectively, giving a total of eight source indexes, which corresponds to the total number of source lines in FILE1 and FILE2 from the EXAMPLE. The third instance variable, my table range type ("myTblRangeType"), has a value that indicates this Source Table Range object points to a Source Fine Table object. Finally, the fourth instance variable, my source table pointer ("mySrcTablePtr"), points to the Source Fine Table object labeled (F1) shown in FIG. 2B. Referring now to FIG. 2B, the Source Fine Table object shown is labeled (F1). A Source Fine Table object contains three instance variables. For this Source Fine Table object, the first instance variable, my last index ("myLastX"), has a value of two, which indicates that the last used index in my fine table is two. The second instance variable, my current index ("myCurrentX"), has a value of zero and is used to optimize repeated inquires on the same element in my fine table. Finally, the third instance variable, my fine table ("myFineTbl"), is the table containing Source Range objects. In this particular fine table there are three Source Range objects currently in use. A Source Range object contains six instance variables. For the Source Range objects shown in FIG. 2B, the first and second instance variables, my first index and my last index, have values that break the source files, FILE1 and FILE2, into contiguous ranges that correspond to the order in which they are scanned during the compilation process. The three Source Range objects in FIG. 2B have a total of eight source indexes that corresponds to the total number of source lines in FILE1 and FILE2 from the EXAMPLE, and also to the number of source indexes in the Source Table Range object shown in the Source Coarse Table object in FIG. 2A. The third instance variable, my range type ("myRangeType"), has a value of simple for all three Source Range objects in my fine table, which indicates hat these Source Range objects refer to ordinary source lines and not to source lines that have been inlined from one source location to another. Finally, the fourth, fifth and sixth instance variables, my source file name ("mySrcFileName"), my object file name (myObjFileName") and my line number ("myLineNum"), respectively, contain information about the source range. That is, the source file name that contains the source range, the object file that stores the binary code (if any) for this source range and the line number form the source file that corresponds to the value of my first index. Referring now to FIGS. 2C and 2D, a Source Coarse Table object and a Source Fine Table object are shown. These objects correspond to the sources files shown in the EXAMPLE just as did the objects from FIGS. 2A and 2B described above, except for one difference. These objects reflect how additional source information is stored when the function f of the EXAMPLE is inlined. In FIG. 2C, the Source Table Range object in the Source Coarse Table object has a value of twelve for my last index instead of eight as shown in FIG. 2A. This increase indicates that there is additional source range information in the Source Fine Table object in FIG. 2D. Referring again to FIG. 2D, the Source Fine Table object shown contains two additional Source Range objects at elements three and four in my fine table as compared to the Source Fine Table object shown in FIG. 2B. The value of my range type for these two Source Range objects is inlined. The last three instance variables of an inlined source range provide the source index of the function call, the source index of the beginning of the function definition and the function identifier. Referring now to FIGS. 3A and 3B, a combined flow chart of the method for defining a Source Range object from beginning and ending source file offsets is illustrated. The process begins with a start bubble 100 followed by an inquiry as to whether or not there is a root source table (diamond 101). If the answer to this inquiry is no, then a Source Coarse Table object is constructed and established as the root source table (block 102). On the other hand, if the answer to this inquiry is yes, or upon completion of the step depicted by the block 102, the first and last index is computed from my base and the given starting and ending offsets are computed (block 103). Another inquiry is next made as to whether or not my last index is less than the previously computed last index (diamond 104). If the answer to this inquiry is yes, then my last index is set to the last index (block 105). On the other hand, if the answer to this inquiry is no, or upon completion of the step depicted by the block 105, a Source Range object is constructed from the previously computed first and last index, the given object file name, and the given source file name (block 106). As a result of the foregoing an object has been created that represents a sequence of lines from a source file being compiled. The process illustration continues in FIG. 3B as denoted by a connector A. Referring to FIG. 3B at the connector A, an inquiry is made as to whether or not there is space available for the Source Range object in the source table (diamond 107, see FIGS. 8A and 8B, described hereafter). If the answer to this inquiry is no, then a Source Coarse Table object is constructed containing the previous root source table (block 108). Next, the newly constructed table is made the root source table (block 109). Following this, the Source Range object is inserted into the source table (block 110, see FIGS. 9A and 8B). Upon completion of this step, or if the answer to the inquiry in the diamond 108 is yes, a branch is taken to the end (bubble 111). Accordingly, the source table now contains the object that represents the given sequence of lines from a source file being compiled. Referring now to FIG. 4, the process for determining the primary Source of a Source object is illustrated. The process begins with a start bubble 115, followed by an inquiry as to whether or not this is a null Source object (diamond 116). If the answer to this inquiry is no, then another inquiry is made as to whether or not there is a root source table (diamond 117). If the answer to this inquiry is yes, then the process finds the Source Range object containing the index of this Source object (block 118, see FIGS. 7A and 73). Next, still another inquiry is made as to whether or not the Source Range object is an inlined range (diamond 119). If the answer to this inquiry is yes, then a new Source object is returned which is constructed from the index of the inlined function definition in the Source Range object (bubble 120). If the answer to the inquiry depicted by the diamond 116 is yes, or if the answer to the inquiries in the diamonds 117 or 119 is no, then this Source object is returned (bubble 121). Referring now to FIGS. 5A and 5B, a process for constructing an inlined Source object is illustrated. The process begins with a start bubble 125 followed by an inquiry as to whether or not the given index of the Source object of the inlined function call is null (diamond 126). If the answer to this inquiry is yes, then the index of this Source object is set to the given index of the inlined function definition as depicted by a block 127. After this the process ends (bubble 128). If the answer to the inquiry depicted by the diamond 126 is no, then another inquiry is made as to whether or not the given index of the Source object of the inlined function definition is null (diamond 129). If the answer to this inquiry is yes, then the index of this Source object is set to the index of the Source Object of the inlined function call as depicted by a block 130, after which the process ends (bubble 128). On the other hand, if the answer to the inquiry in the diamond 129 is no, then still another inquiry is made as to whether or not there is a root source table (diamond 131). If the answer to this inquiry is no, then the a Source Coarse Table object is constructed and made the root source table (block 132). On the other hand, if the answer to this inquiry is yes, or upon completion of the step depicted by the block 132, yet another inquiry is made as to whether or not a Source Range object in the source table can be adjusted to include this inlined Source object (diamond 133, see FIGS. 6A & 6B). The process illustration continues in FIG. 5B as denoted by a connector B if the answer to the inquiry depicted by the diamond 133 is yes, or by a connector C if the answer is no. Referring now to FIG. 5B at the connector B, the index of this Source object is set to the last index of the adjusted Source Range object (block 135). Next, an inquiry is made as to whether or not the index of this Source object is greater than my last index (diamond 136). If the answer to this inquiry is yes, then my last index is set to the index of this Source object (block 137). Following this, the process ends (bubble 138). Referring back to the connector C from FIG. 5A, my last index is incremented by one (block 139). Next, the index of this Source object is set to my last index (block 140). Then, an inlined Source Range object is inserted into the source table whose first and last indexes are the same as the index of this Source object (block 141, see FIGS. 8A and 8B). The process ends at the bubble 138. Referring now to FIGS. 6A and 6B, a flow chart illustrating the process for adjusting a Source Range object from a Source Coarse Table ("SrcCoarseTbl") object is shown. The process begins with a start bubble 140 followed by an inquiry as to whether or not my last index is greater than or equal to zero (diamond 141). If the answer to this inquiry is no, then null is returned (bubble 142). On the other hand, if the answer is yes, then another inquiry is made as to whether or not the last table in my coarse table is a fine table (diamond 143). If the answer to this inquiry is yes, then the last Source Range object in the fine table is adjusted (if possible) for the given inlined Source Range object (block 144, see FIGS. 10A and 10B). If the answer to the inquiry depicted by the diamond 143 is no, then the last Table Range object in the coarse table is adjusted (if possible) for the given inlined Source Range object (block 145, see FIGS. 6A and 6B). Upon completion of either the step depicted by the block 144 or the block 145, another inquiry is made as to whether or not the last range of the table was adjusted (diamond 146). If the answer to this inquiry is no, then a return of null is made (bubble 147). On the other hand, if the answer is yes, then a branch of the illustration of the process is continued in FIG. 6B as depicted by a connector D. Referring now to FIG. 6B at the connector D, still another inquiry is made as to whether or not the last index of the last Source Range object in my coarse table is less than the last index of the adjusted Source Range object (diamond 148). If the answer to this inquiry is yes, then the last index of the last Source Range object in my coarse table is set to the last index of the adjusted Source Range object (block 149). On the other hand, if the answer to this inquiry is no, or upon completion of the process step depicted by the block 149, the adjusted Source Range object is returned (bubble 150). Referring now to FIGS. 7A and 7B, a flow chart of the process for finding a Source Range object from a Source Coarse Table object is illustrated. The process begins with a start bubble 155 followed by an inquiry as to whether or not my current index is greater than or equal to zero (diamond 156). If the answer to this inquiry is yes, then another inquiry is made as to whether or not the given index is greater than or equal to the first index of the current Table Range object in my coarse table (diamond 157). If the answer to this inquiry is yes, then still another inquiry is made as to whether or not the given index is less than or equal to the last index of the current Table Range object in my coarse table (diamond 158). If the answer to this inquiry is yes, the yet another inquiry is made as to whether or not the current table in my coarse table is a fine table (diamond 159). If the answer to the inquiries depicted by the diamonds 156-158 is no then a branch is taken to FIG. 7B as depicted by a connector E. If the answer to the inquiry depicted by the diamond 159 is yes, a branch is taken to FIG. 7B as denoted by a connector F and if the answer to this inquiry is no, then a branch is taken to FIG. 7B as depicted by a connector G. Referring now to FIG. 7B at the connector F, the Source Range object for the given index found in the fine table is returned (bubble 160, see FIGS. 11A and 11B). From the connector G, the Source Range object for the index found in the coarse table is returned (bubble 161, see FIGS. 7A and 7B). From the connector E my current index is set to the result of the binary search for the given index in my coarse table (block 162). Following this, an inquiry is made as to whether or not my current index is greater than or equal to zero (diamond 163). If the answer to this inquiry is no, then null is returned (bubble 164). If the answer to the inquiry in the diamond 163 is yes, then another inquiry is made as to whether or not the current table in my coarse table is a fine table (diamond 165). If the answer to this inquiry is no, then the Source Range object for the given index found in the coarse table is returned (bubble 166, see FIGS. 7A and 7B). On the other hand, if the answer to the inquiry in the diamond 165 is yes, then the Source Range object for the given index found in the fine table is returned (bubble 167, see FIGS. 11A and 11B). Referring now to FIGS. 8A and 8B, a flow chart of the process for creating a Source Range object from a Source Coarse Table object is illustrated. The process begins with a start bubble 170 followed by an inquiry as to whether or not my last index is greater than or equal to zero (diamond 171). If the answer to this inquiry is no, then null is returned (bubble 172). If the answer to this inquiry is yes, then another inquiry is made as to whether or not the last table in my coarse table is a fine table (diamond 173). If the answer to this inquiry is yes, then a new Source Range object is created (if possible) in the fine table (block 174, see FIG. 12). On the other hand, if the answer to this inquiry is no, then a new Source Range object is created (if possible) in the coarse table (block 175, see FIGS. 8A and SB). Upon completion of the step depicted by either block 174 or 175, yet another inquiry is made as to whether or not a new Source Range object was created (diamond 176). If the answer to this inquiry is no, then a branch is taken to FIG. 8B as depicted by a connector H. On the other hand, if the answer is yes, then still another inquiry is made as to whether or not the last index of the last Table Range object in my coarse table is less than the last index of the created Source Range object (diamond 177). If the answer to this inquiry is no, then a branch is taken to FIG. 8B as depicted by a connector I. On the other hand if the answer to this inquiry is yes, then the last index of the last Table Range object in my coarse table is set to the last index of the created Source Range object (block 178). Upon completion of this step a branch is taken to FIG. 8B via the connector I. Referring now to FIG. 8B at the connector H, an inquiry is made as to whether or not my last index is less than the maximum index of a coarse table (diamond 180). If the answer to this inquiry is no, the a null is returned (bubble 181). On the other hand, if the answer to this inquiry is yes, then my last index is incremented by one (block 182). Next, another inquiry is made as to whether or not this is a level zero coarse table (diamond 183). If the answer to this inquiry is yes, then a new Source Fine Table object is created at my last index in my coarse table (block 184). Next, a new Source Range object is created in the fine table (block 185, see FIG. 12) Following this, the created Source Range object is returned (bubble 186). If the answer to the inquiry depicted by the diamond 183 is no, then a new Source Coarse Table is created at my last index in my coarse table (block 187). Next, a new Source Range object is created in the coarse table (block 188, see FIGS. 8A and 8B). Finally, the created Source Range object is returned (block 186). It is pointed out that if the last index of the last table range in my coarse table is not less than the last index of the created source range (no leg of the diamond 177, FIG. 8A, via the connector I), the created source range is returned (bubble 186). Referring now to FIG. 9, a flow chart of the process for constructing a Source Coarse Table object above a given Source Coarse Table object is illustrated. The process begins with a start bubble 190, followed by a process step of setting my last index to zero (block 191). Next, my current index is set to a negative one (block 192), and my coarse level is set to the level of the given Source Coarse Table object plus one (block 193). Following this, the first table range of my coarse table is set to a newly created Table Range object constructed from the given Source Coarse Table object (block 194), whereupon the process ends (bubble 195). Referring now to FIGS. 10A and 10B, a flow chart of a process for adjusting a Source Range object from a Source Fine Table object is illustrated. The process begins with a start bubble 200 followed by an inquiry as to whether or not my last index is greater than or equal to zero (diamond 201). If the answer to this inquiry is yes, then another inquiry is made as to whether or not the last Source Range object in my fine table is an inlined source range (diamond 202). If the answer to this inquiry is no, then a null is returned (bubble 203). On the other hand, if the answer is yes, then a complex inquiry is made as follows: Is the last Source Range object in my fine table the same as the given Source Range object except that the difference of the inlined function definition indexes is less than 100 more than the difference of the first and last indexes of the last Source Range object in my fine table (diamond 204). If the answer to the inquiry in the diamond 204 is yes, then the first index of the given Source Range object is set to the first index of the last Source Range object in my fine table plus the difference of the indexes of the inlined function definition (block 205). Next, the last index of the given Source Range object is set to its first index (block 206). The illustration of the process is continued in FIG. 10B as depicted by a connector P. If the answer to the either of the inquiries depicted by the diamonds 201 or 204 is no, then a null is returned (bubble 207). Referring now to FIG. 10B at the connector P, another inquiry is made as to whether or not the last index of the given Source Range object is greater than the last index of the last Source Range object in my fine table (diamond 208). If the answer to this inquiry is yes, then the last index of the last Source Range object in my fine table is set to the last index of the given Source Range object (block 209). Next, the last Source Range object of my fine table is returned (bubble 210). If the answer to the inquiry in the diamond 208 is no, then the last Source Range object of my fine table is likewise returned. Referring now to FIGS. 11A and 11B, a flow chart of a process for finding a Source Range object from a Source Fine Table object is illustrated. The process begins with a start bubble 215 followed by an inquiry as to whether or not my current index is greater than or equal to zero (diamond 216). If the answer to this inquiry is yes, then another inquiry is made as to whether or not the given index is greater than or equal to the first index of the current Source Range object in my fine table (diamond 217). If the answer to this inquiry is yes, then yet another inquiry is made as to whether or not the given index is less than or equal to the last index of the current Source Range object in my fine table (diamond 218). If the answer to this inquiry is yes, then the current Source Range object in my fine table is returned (bubble 219). If the answer to the inquiries depicted by any of the diamonds 216, 217 or 218 is no, then a branch is taken to FIG. 11B as depicted by a connector Q. Referring now to FIG. 11B at the connector Q, my current index is set to the result of a binary search for the given index in my fine table (block 220). Next, an inquiry is made as to whether or not my current index is greater than or equal to zero (diamond 221). If the answer to this inquiry is no, then a null is returned (bubble 222). On the other hand, if the answer to this inquiry is yes, then the current Source Range object in my fine table is returned (bubble 223). Referring now to FIG. 12, a flow chart of a process for creating a Source Range object from a Source Fine Table object is illustrated. The process begins with a start bubble 225 followed by an inquiry as to whether or not my last index is less than the maximum size of a fine table (diamond 226). If the answer to this inquiry is yes, then my last index is incremented by one (block 227). Next, the last Source Range object in my fine table is set to the given Source Range object (block 228). Finally, the last Source Range object in my fine table is returned (bubble 229). If the answer to the inquiry depicted by the diamond 226 is no, then a null is returned (bubble 230). Although the invention has been described with reference to a specific embodiment, this description is not meant to be construed in a limiting sense. Various modifications of the disclosed embodiment as well as alternative embodiments of the invention will become apparent to one skilled in the art upon reference to the description of the invention. It is therefore contemplated that the appended claims will cover any such modifications of embodiments that fall within the true scope of the invention.
APPENDIX I
______________________________________
The objects are fully defined in the C++
programming language.
______________________________________
Defining a source range from starting and ending offsets, FIGS. 3A &
3B
a) is there a root source table?
Yes
No: a) construct a coarse table and make it the root source table
b) compute the first and last index from my base and the given
starting and ending offsets
c) is my last index less than the last index?
Yes: a) set my last index to the last index
No:
d) construct a source range from the first and last index
e) is there space available for the source range in the source table
(see FIGS. 8A and 8B)?
Yes:
No: a) construct a coarse table containing the previous root
source table
b) make the newly constructed table the root source table
c) insert the source range into the source table (see FIGS.
8A and 8B)
Determining the primary source of a Source object, FIG. 4
a) is this a null source?
Yes:
No: a) is there a root source table?
Yes: a) find the source range containing the index of
this source (see FIGS. 7A and 7B)
b) is the source range an inlined range?
Yes: a) return a new source constructed from the
index of the inlined function in the
source range
No:
No:
b) return this source
Constructing an inlined Source object, FIGS. 5A and 5B
a) is the given index of the source of the inlined function call null?
Yes: a) set the index of this source to the given index of the
source of the inlined function definition
b) return
No:
b) is the given index of the source of the inlined function definition
null?
Yes: a) set the index of this source to the given index of the
source of the inlined function call
b) return
No:
c) is there a root source table?
Yes:
No: construct a coarse table and take it the root source table
d) can a source range in the source table be adjusted to include this
inlined source (see FIGS. 6A & 6B).
Yes: a) set the index of this source to the last index of the
adjusted source range
b) is the index of this source greater than my last index?
Yes: a) set last index to the index of this source
No:
No: a) increment my last index by one
b) set the index of this source to my last index
c) insert an inlined source range into the source table whose
first and last indexes are the same as the index of this
source (see FIGS. 8A and 8B)
Adjusting a range from a Source Coarse Table object, FIG. 6A & 6B
a) is my last index greater than or equal to zero?
Yes: a) is the last table in my coarse table a fine table?
Yes: a) adjust the last source range in the fine table
(if possible) for the given inlined source range
(see FIGS. 10A and 10B)
No: a) adjust the last table range in the coarse table
(if possible) for the given inlined source range
(see FIGS. 6A & 6B)
No: a) return null
b) was the last range of the table adjusted?
Yes: a) is the last index of the last range in my coarse table
less than the last index of the adjusted source range?
Yes: a) set the last index of the last range in my coarse
table to the last index of the adjusted source
range
No:
b) return the adjusted source range
No: a) return null
Finding a range from a Source Coarse Table object, FIGS. 7A and 7B
a) is my current index greater than or equal to zero?
Yes: a) is the given index greater than or equal to the first
index of the current table range in my coarse table?
Yes: a) is the given index less than or equal to the last
index of the current table range in my coarse
table?
Yes: a) is the current table in my coarse table
a fine table?
Yes: a) return the source range for
the given index found in the
fine table (see FIG. 11A and
11B)
No: a) return the source range for
the given index found in the
coarse table (see FIGS. 7A and
7B)
No:
No:
No:
b) set my current index to the result of the binary search for the
given index in my coarse table;
c) is my current index greater than or equal to zero?
Yes: a) is the current table in my coarse table a fine table?
Yes: a) return the source range for the given index found
in the fine table (see FIGS. 11A and 11B)
No: a) return the source range for the given index found
in the coarse table (see FIGS. 7A and 7B)
No: a) return null
Creating a range from a Source Coarse Table object, FIGS. 8A and 8B
a) is my last index greater than or equal to zero?
Yes: a) is the last table in my coarse table a fine table?
Yes: a) create a new source range (if possible) in the
fine table (see FIG. 12)
No: a) create a new source range (if possible) in the
coarse table (see FIGS. 8A and 8B)
No: a) return null
b) was a new source range created?
Yes: a) is the last index of the last table range in my coarse
table
less than the last index of the created source range?
Yes: a) set the last index of the last table range in my
coarse table to the last index of the created
source range
No:
No: a) is my last index less than the maximum index of a coarse
table?
Yes: a) increment my last index by one
b) is this a level zero coarse table?
Yes: a) create a new fine table at my last index
in my coarse table
b) create a new source range in the created
fine table (see FIG. 12)
No: a) create a new coarse table at my last
index in my coarse table
b) create a new source range in the created
coarse table (see FIG. 8A & 8B)
No: a) return null
c) return the created source range
Constructing a Source Coarse Table object above a given coarse table,
FIG. 9
a) set my last index to zero
b) set my current index to negative one
c) set my coarse level to the level of the given coarse table plus one
d) set the first table range of my coarse table to a newly created
table range constructed from the given coarse table
Adjusting a range from a Source Fine Table object, FIGS. 10A and 10B
a) is my last index greater than or equal to zero?
Yes: a) is the last source range in my fine table an inlined
source range?
Yes: a) is the last source range in my fine table the
same as the given source range except that the
difference of the inlined function definition
indexes is less than 100 more than the difference
of the first and last indexes of the last source
range in my fine table?
Yes: a) set the first index of the given source
range to the first index of the last
source range in my fine table plus the
difference of the indexes of the inlined
function definition
b) set the last index of the given source
range to its first index
c) is the last index of the given source
range greater than the last index of the
last source range in my fine table?
Yes: a) set the last index of the last
source range in my fine table
to the last index of the given
source range
No:
d) return the last source range of my fine
table
No:
No:
No:
b) return null
Finding a range from a Source Fine Table object, FIGS. 11A & 11B
a) is my current index greater than or equal to zero?
Yes: a) is the given index greater than or equal to the first
index of the current source range in my fine table?
Yes: a) is the given index less than or equal to the last
index of the current source range in my fine
table?
Yes: a) return the current source range in my
fine table
No:
No:
No:
b) set my current index to the result of the binary search for the
given index in my fine table
c) is my current index greater than or equal to zero?
Yes: a) return the current source range in my fine table
No: a) return null
Creating a range from a Source Fine Table object, FIG. 12
a) is my last index less than the maximum size of a fine table?
Yes: a) increment my last index by one
b) set the last source range in my fine table to the given
source range
c) return the last source range in my fine table
No: a) :return null
______________________________________
|
Same subclass Same class Consider this |
||||||||||