Method for implementing virtual function tables in a compiler for an object-oriented programming language

A method in a computer system for generating a virtual function table for a child class, the computer system having an associated memory, the child class defined in terms of a parent class and function members, the parent class having a plurality of virtual function members, the parent class having a virtual function table, the parent virtual function table comprising a parent tile table and a plurality of parent sub-tables, the parent tile table containing pointers to the parent sub-tables, the parent sub-tables containing pointers to the parent virtual function members, the child class having a function member that overrides a virtual function member of the parent class, the method comprising the steps of:

• receiving a class definition for the child class;
• after receiving the class definition, allocating a tile table for the child class in the memory, the child tile table containing an entry for each sub-table in the parent class;
• and
• for each parent tile table entry,
• when the sub-table pointed to by the parent tile table entry does not contain a pointer to a virtual function member that is overridden in the child class, storing the parent tile table entry in the child tile table;
• and
• when the sub-table pointed to by the parent tile table entry contains a pointer to a function member that is overridden in the child class, allocating a sub-table for the child class in the memory, and storing a pointer to the overriding function member in the allocated sub-table;
• and
• generating instructions for accessing the function members of the child class through the child tile table and sub-tables.

A method in a computer system for accessing a virtual function member for a class, the class having a virtual function table and a plurality of virtual function members, the virtual function members having associated executable code, the virtual function table having a tile table and a plurality of sub-tables, the tile table containing pointers to the sub-tables, the sub-tables containing pointers to the executable code of the virtual function members, each virtual function member having a unique identifier, the unique identifier indicating a tile table entry and a sub-table entry, the method comprising the steps of:

• receiving an identification of an object of the class;
• receiving the unique identifier for a virtual function member of the class to be invoked for the object;
• retrieving the tile table entry of the virtual function table indicated by the received unique identifier;
• retrieving a sub-table entry from the sub-table pointed to by the retrieved tile table entry, the sub-table entry indicated by the received unique identifier;
• and
• executing the executable code pointed to by the retrieved sub-table entry to effect the accessing of the virtual function member for the class.

A method in a computer system for compiling a computer program, the computer program having a class definition for a class, the method comprising the steps of:

• receiving the class definition, the class definition including a plurality of virtual function members;
• allocating a plurality of sub-tables for the class in accordance with the received class definition, each sub-table having entries, each entry containing a reference to executable code for a virtual function member;
• allocating a tile table for the class, the tile table containing an entry for each allocated sub-table;
• storing in each tile table entry a reference to an allocated sub-table;
• storing in each sub-table entry of each allocated sub-table a reference to executable code for a virtual function member;
• and
• generating code to access the executable code of the virtual function members through the tile table and the sub-tables.

A method in a computer system for compiling a computer program, the program having a parent class definition for a parent class, the parent class definition including a plurality of virtual function members, the parent class having a tile table and a plurality of sub-tables, the tile table containing reference to the sub-tables, the sub-tables containing references to the virtual function members of the parent class, the method comprising the steps of:

• receiving a class definition of a child class, the child class definition inheriting the parent class definition and containing a function member that overrides a virtual function member of the parent class;
• allocating a tile table for the child class, the child tile table containing a reference to each sub-table of the parent class;
• for each reference to a sub-table in the parent tile table,
• when the referenced sub-table does not contain a reference to a virtual function member that is overridden in the child class, storing the reference to the child tile table;
• and
• when the referenced sub-table contains a reference to a virtual function member that is overridden in the child class, allocating a sub-table for the child class, storing a reference to the allocated sub-table in the child tile table, and storing a reference to the overriding virtual function member in the allocated sub-table;
• and
• generating code to access a non-overridden function member indirectly through the child tile table and a parent sub-table and an overridden function member indirectly through the child tile table and child sub-table.

A method in a computer system for accessing a virtual function member of a class during execution of an object-oriented program, the method comprising the steps of:

• receiving a unique identifier for a virtual function member of the class;
• identifying a tile table indicated by the received unique identifier;
• retrieving a tile table entry of the identified tile table;
• identifying a sub-table indicated by the retrieved tile table entry;
• retrieving a sub-table entry from the identified sub-table, the sub-table entry indicated by the received unique identifier;
• and
• executing executable code pointed to by the retrieved sub-table entry to effect the accessing of the virtual function member for the class.

A method in a computer system for generating a virtual function table from a class definition of a class, the method comprising the steps of:

• receiving the class definition for the class, the class definition specifying virtual function members of the class;
• allocating a plurality of virtual function member reference tables for the virtual function table, each virtual function member reference table having entries, each entry containing a reference to a virtual function member;
• allocating an index table for the virtual function table, the index table containing an entry for each allocated virtual function member reference table;
• storing in each virtual function member reference table entry of each allocated virtual function member reference table a reference to the executable code of a virtual function member;
• and
• generating code to access the virtual function members through the index table and the virtual function reference tables.

A method in a computer system for generating a virtual function for a child class, the computer system having an associated memory, the child class defined in terms of a parent class and function members, the parent class having a plurality of virtual function members, the parent class having a virtual function table, the parent virtual function table comprising a parent tile table and a plurality of parent sub-tables, the parent tile table containing pointers to the parent sub-tables, the parent sub-tables containing pointers to the parent virtual function members, the child class having a function member that overrides a virtual function member of the parent class, the method comprising the steps of:

• receiving a child class definition;
• after receiving the child class definition, allocating a tile table for the child class in the memory, the child tile table containing an entry for each sub-table in the parent class;
• copying each entry of the parent tile table into an entry of the child tile table;
• for each parent tile table entry, when the sub-table pointed to by the parent tile table entry contains a pointer to a virtual function member that is overridden in the child class, allocating a sub-table for the child class in the memory, storing a pointer to the allocated sub-table in the child tile table, and storing a pointer to the overriding function member in the allocated sub-table;
• and
• generating computer code to access function members through the child tile table and the sub-tables.

A method in a computer system for compiling a computer program, the computer system having a class, the class having a class definition, the method comprising the steps of:

• receiving the class definition of the class, the class definition specifying a plurality of virtual function members;
• generating a two-level virtual function table for the class, the two-level virtual function table containing references to the virtual function members of the class;
• and
• generating computer code to access the virtual function members through the two-level virtual function table.

A method in a computer system for compiling a computer program, the computer program having a parent class definition of a parent class and having a child class definition of a child class, the parent class and the child class having a plurality of virtual functions, the child class inheriting the parent class, the method comprising the steps of:

• receiving the class definitions of the child class and the parent class;
• allocating a parent virtual function table for the parent class, the parent virtual function table having a first and a second level, the first level parent virtual function table having references to a plurality of second level parent virtual function tables, the second level parent virtual function tables having references to virtual functions of the parent class;
• allocating a child virtual function table for the child class, the child virtual function table having a first and a second level, the first level child virtual function table having entries wherein an entry in the first level child virtual function table refers to a second level parent virtual function table when the virtual functions referred to by the second level parent virtual function table are not overridden by a virtual function of the child class;
• and
• generating computer code to access the virtual functions of the child class through both the child virtual function table and the parent virtual function table.