Determining the actual class of an object at run time

• US 6,138,269 A
• Filed: 05/20/1998
• Issued: 10/24/2000
• Est. Priority Date: 05/20/1998
• Status: Expired due to Term

• Current Assignee: Cornell Dubilier Marketing, Inc. (Cornell-Dubilier Electric Corp.), Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Ball, Michael S., Ebnesajjad, Soroor
• Primary Examiner(s): Chaki, Kakali
• Application Number:
  US09/082,316
• Time in Patent Office: 888 Days
• Field of Search: 717/1, 717/2, 717/4, 717/5, 717/10, 707/103, 709/315, 709/316, 709/331, 709/332
• US Class Current: 717/108
• CPC Class Codes: G06F 9/4492 Inheritance
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A dynamic down cast or cross cast is performed at run time within an object-oriented programming language such as C++. The compiler generates data structures during a compile; at run time a routine in the language support library accesses the generated data structures in order to perform the dynamic cast. Class structure information is provided in a size that varies linearly as the total number of classes in the class hierarchy. Cryptographic hashing of class names is used to provide uniqueness. The dynamic cast addresses complications in C++ due to "virtual" and "nonvirtual" inheritance. A run time type identification (RTTI) data structure is created at compile time. An offset within an object description is calculated for each sub-object of the object. Those virtual base classes that are duplicates are skipped producing a data structure that may be searched linearly as the number of classes in the hierarchy. An identifier for each sub-object is stored in the data structure along with its offset. Each virtual table also stores the offset of its corresponding sub-object. A cast operation is performed at run time using the RTTI data structure. The static type object pointer is used to access the object through a particular sub-object. The virtual table associated with the sub-object is used to access the RTTI data structure. The data structure is searched for the target type, and the offset associated with the target type is combined with the offset from the virtual table to adjust the object pointer to cast it to the target type.

Claims

1. A computer-implemented method of performing a dynamic cast operation for an object-oriented program at run time, said method comprising:

receiving an object pointer of a static type that points to an object having a dynamic type;

receiving a target type to which said static type is to be cast;

determining an object pointer offset associated with said object pointer indicative of the location pointed to within said object by said object pointer;

determining a target offset associated with said target type indicative of the location of a target type sub-object within said object; and

combining the value of said object pointer with said object pointer offset and said target offset to produce an adjusted object pointer, said adjusted object pointer being of said target type, whereby said dynamic cast operation is performed by the adjustment of said object pointer.

2. A method as recited in claim 1 wherein said object-oriented program includes a plurality of classes each having a class identifier, and said step of determining a target offset includes the sub-step of:

searching a subset of said class identifiers associated with said object using an algorithm that varies linearly with the number of classes in said object-oriented program, whereby said method may be performed faster.

3. A method as recited in claim 1 wherein said object-oriented program includes a plurality of classes each having a class identifier and allows nonvirtual inheritance, and said step of determining a target offset includes the sub-steps of:

searching a subset of said class identifiers associated with said object for a first entry matching said static type and having the same offset as said object pointer offset; and

searching from said first entry in said subset of said class identifiers for a second entry matching said target type, whereby said dynamic cast operation operates correctly when nonvirtual inheritance is used in association with said object.

4. A method as recited in claim 1 wherein said object-oriented program allows both nonvirtual inheritance and virtual inheritance and wherein said dynamic cast operation operates correctly when nonvirtual inheritance and virtual inheritance are used in association with said object.

5. A computer-implemented method of generating a run time type identification (RTTI) data structure for an object description of a class for use at run time in an object-oriented program to assist in performing a dynamic cast operation, said method comprising:

determining an offset for each sub-object within said object description;

storing each offset for each sub-object with a virtual table corresponding to said each sub-object;

generating a unique identifier for said class and associating said unique identifier with said RTTI data structure;

determining a unique sub-object identifier for each sub-object within said object description;

storing each of said sub-object identifiers in association with said RTTI data structure; and

storing each of said offsets with its corresponding sub-object identifier in association with said RTTI data structure, whereby at run time a single one of said offsets stored with one of said virtual tables may be combined with a single one of said offsets stored in said RTTI data structure to adjust an object pointer that points to an object of said class to assist in performing said dynamic cast operation.

6. A method as recited in claim 5 wherein said object-oriented program includes a plurality of classes in a class hierarchy, and wherein said class is a member of said class hierarchy and is associated with a number of base classes, said method further comprising:

stepping through said base classes of said class to determine said sub-objects;

determining whether a found base class has already been encountered; and

wherein when it is determined that said found base class has already been encountered, said method includes skipping over said found base class, whereby said dynamic cast operation used at run time varies linearly with the number of classes in said class hierarchy.

7. A method as recited in claim 5 wherein said object-oriented program allows both nonvirtual inheritance and virtual inheritance and wherein said generated RTTI data structure is arranged to allow said dynamic cast operation to operate correctly when nonvirtual inheritance and virtual inheritance are used in association with said object.

8. A computer-implemented method of generating a run time type identification (RTTI) data structure for an object description of a class for use at run time in an object-oriented program to assist in performing a dynamic cast operation, said method comprising:

generating a list of sub-objects within said object description based upon base classes of said class;

skipping duplicate virtual base classes such that for each virtual base class there is only a single corresponding sub-object within said object description;

generating said RTTI data structure for said object description, said RTTI data structure including a unique identifier for said class, said list of sub-objects, and an offset for each sub-object indicating the location of each sub-object within said object description; and

creating a pointer associated with each sub-object to said RTTI data structure, whereby at run time an offset of one of said sub-objects may be combined with a single one of said offsets stored in said RTTI data structure to adjust an object pointer that points to an object of said class to assist in performing said dynamic cast operation.

9. A method as recited in claim 8 wherein said object-oriented program includes a plurality of classes in a class hierarchy, and wherein said class is a member of said class hierarchy, and wherein said dynamic cast operation used at run time varies linearly with the number of classes in said class hierarchy.

10. A method as recited in claim 8 wherein said object-oriented program allows both nonvirtual inheritance and virtual inheritance and wherein said generated RTTI data structure is arranged to allow said dynamic cast operation to operate correctly when nonvirtual inheritance and virtual inheritance are used in association with said object.

11. A run time type identification (RTTI) data structure embodied in a computer-readable medium, said RTTI data structure comprising:

a unique identifier identifying the most derived base class of an object description to which said RTTI data structure corresponds, said most derived base class being part of a class hierarchy of a plurality of classes;

a list of unique identifiers corresponding to classes within said class hierarchy from which said most derived base class is derived, such that for each virtual base class from which said most derived base class is derived there is a single unique identifier in said list; and

an offset for each of said unique identifiers, each offset representing the location within said object description of a sub-object corresponding to one of said classes from which said most derived base class is derived, whereby said list may be searched at run time to produce a single one of said offsets to be used in adjusting an object pointer that points to said object description to perform a dynamic cast operation.

12. A computer-implemented method of performing a dynamic down cast operation for an object-oriented program at run time, said method comprising:

receiving an object pointer of a static type that points to an object having a dynamic type, said static type being a nonvirtual base class of said object;

receiving a target type to which said static type is to be cast;

determining an object pointer offset associated with said object pointer indicative of the location pointed to within said object by said object pointer;

searching a list of base classes of said object to find a first matching entry for said static type that is associated with an offset entry that matches said object pointer offset;

searching said list of base classes beginning from said first matching entry to find a second matching entry that matches said target type, said second matching entry being associated with a target offset, said target offset indicative of the location of a target type sub-object within said object; and

combining the value of said object pointer with said object pointer offset and said target offset to produce an adjusted object pointer, said adjusted object pointer being of said target type, whereby said dynamic down cast operation is performed by the adjustment of said object pointer.

13. A method as recited in claim 12 wherein said object-oriented program includes a plurality of classes each having a class identifier, and said step of searching said list of base classes beginning from said first matching entry includes the sub-step of:

searching a subset of said class identifiers associated with said object using an algorithm that varies linearly with the number of classes in said object-oriented program, whereby said method may be performed faster.

14. A method as recited in claim 12 wherein for any duplicate base classes of said object there exists a separate sub-object for each of said duplicate base classes.

15. A computer-implemented method of performing a dynamic down cast operation for an object-oriented program at run time, said object-oriented program including a plurality of virtual classes and a plurality of nonvirtual classes, and each class having a class identifier, aid method comprising:

receiving an object pointer of a static type that points to an object having a dynamic type, said static type being a virtual base class of said object;

receiving a target type to which said static type is to be cast;

determining an object pointer offset associated with said object pointer indicative of the location pointed to within said object by said object pointer;

searching a list of base classes of said object to find a first matching entry for said static type that is associated with an offset entry that matches said object pointer offset;

searching said list of base classes beginning from said first matching entry to find a second matching entry that matches said target type, said second matching entry being associated with a target offset, said target offset indicative of the location of a target type sub-object within said object; and

determining the number of entries matching said target type, wherein when it is determined that zero or two entries match said target type, said method includes failing said dynamic down cast operation, and wherein when it is determined that only one entry matches said target type, said method includes combining the value of said object pointer with said object pointer offset and said target offset to produce an adjusted object pointer, said adjusted object pointer being of said target type, whereby said dynamic down cast operation is performed by the adjustment of said object pointer.

16. A method as recited in claim 15 wherein said step of searching said list of base classes beginning from said first matching entry includes the sub-step of:

searching a subset of said class identifiers associated with said object using an algorithm that varies linearly with the number of classes in said object-oriented program, whereby said method may be performed faster.

17. A method as recited in claim 15 wherein for any duplicate nonvirtual base classes of said object there exists a separate sub-object for each of said duplicate nonvirtual base classes, and wherein for any duplicate virtual base classes of said object there exists a single sub-object for each of said duplicate virtual base classes.