# US 5,327,562 A · Method for implementing virtual function tables in a compiler for an object-oriented programming language

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 5,327,562 A
- Document ID: US5327562A
- Status: Granted
- Kind: A
- Application number: 07/880,168
- Filed: 1992-05-06
- Granted: 1994-07-05
- Earliest claimed: 1992-05-06
- Assignees: Microsoft Corporation
- Inventors: James L. Adcock
- Web page: https://patentgrep.com/patent/US5327562A

## CPC

- G06F 8/41: Compilation
- G06F 9/449: {Object-oriented method invocation or resolution}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method for a computer compiler for an object-oriented programming language for implementing virtual functions is provided. In preferred embodiments of the present invention, the virtual function table for a class contains a tile table and a plurality of sub-tables. The tile table contains pointers to the sub-tables, and the sub-tables contain pointers to the virtual function members of the class. Each child class shares a sub-table of the parent class when the child class does not override a function in that sub-table. If the child class overrides a function, then the child is allocated its own sub-table. Each virtual function member for a class is identified by a tile table offset and a sub-table offset.

## Claims

### Claim 1

A method in a computer system for generating a virtual function table for a class, the class specifying an object type in an object-oriented environment, the computer system having memory, the class having a plurality of virtual function members, each virtual function member having associated executable code, the virtual function table having a tile table and a plurality of sub-tables, the method comprising the steps of:
receiving a class definition for the class;
after receiving the class definition, allocating a plurality of sub-tables in the memory, each sub-table having entries;
allocating a tile table for the class in the memory, the tile table containing an entry for each allocated sub-table;
storing in each tile table entry a pointer to an allocated sub-table;
storing in each sub-table entry a pointer to the executable code associated with a virtual function member; and
generating computer code to access the executable code of the virtual function members of the class through the tile table and the sub-tables.

### Claim 2

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.

### Claim 3

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.

### Claim 4

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.

### Claim 5 (depends on 4)

The method as recited in claim 4 wherein the step of allocating a plurality of sub-tables includes the step of allocating a sub-table with a number of entries that is a power of two.

### Claim 6 (depends on 4)

The method as recited in claim 4 wherein the step of storing in each sub-table entry includes storing an indirect reference through another sub-table to executable code for a virtual function member.

### Claim 7

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.

### Claim 8 (depends on 7)

The method as recited in claim 7 wherein the step of allocating a plurality of sub-tables includes the step of allocating a sub-table with a number of entries that is a power of two.

### Claim 9

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.

### Claim 10

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.

### Claim 11

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.

### Claim 12

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.

### Claim 13 (depends on 12)

The method of claim 12 wherein the step of generating a two-level virtual function table includes the steps of:
allocating a tile table, the tile table having tile table entries;
allocating a plurality of sub-tables, the sub-tables having sub-table entries; and
storing into each tile table entry a reference to a sub-table and storing into each sub-table entry a reference to a virtual function member.

### Claim 14 (depends on 12)

The method of claim 12 including the steps of:
receiving a child class definition of a child class that inherits the class, the child class definition specifying a virtual function member that overrides a virtual function member of the inherited class; and
allocating a two-level virtual function table for the child class that shares a portion of the virtual function table of the inherited class.

### Claim 15

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.

### Claim 16 (depends on 15)

The method of claim 15 wherein an entry of the first level child virtual function table refers to a second level child virtual function table when a virtual function referred to by the second level child virtual function table overrides a virtual function of the parent class.