Dynamic multiple inheritance method dispatch data structure including an m-table size, i-table containing one or more holder addressor regions and type extension testing by frugal perfect hashing

A computer controlled method, to utilize a dispatch data structure for a holder, said dispatch data structure including an m-table and an i-table, said m-table having an m-table size, said i-table containing one or more holder addressor regions, said method comprising:

• determining an m-table index into said m-table by accessing an identification number of a holder of interest and computing said identification number modulo said m-table size, wherein a size of said m-table is configured such that each of the hashed values generated by hashing each of the identification numbers by the m-table size can be placed in a location in the m-table without colliding with another of the hashed values, wherein said dispatch data structure also comprises a second m-table having said m-table size, said second m-table containing one or more identification numbers, said method further comprising determining whether the contents of said second m-table respective to said m-table index is equal to said identification number;
• accessing an i-table index from said m-table responsive to said m-table index, said i-table index locating one of said one or more holder addressor regions in said i-table;
• and
• dispatching relative to said one of said one or more holder addressor regions.

An apparatus having a central processing unit (CPU) and a memory coupled to said CPU, the apparatus configured to construct a dispatch data structure in said memory for a holder, wherein said apparatus comprises:

• an inheritance determination logic configured to determine a set of member holders from which said holder inherits, one of said set of member holders having a respective set of members, each of said set of member holders uniquely identified by an identification number respectively;
• a first construction logic configured to construct an i-table responsive to the inheritance determination logic, said i-table containing one or more holder addressor regions, one of said one or more holder addressor regions containing addressors for said respective set of members, each of said one or more holder addressor regions associated with a respective i-table index;
• a collection logic configured to collect a respective set of identification numbers for said set of member holders and responsive to the inheritance determination logic, wherein each of said one or more holder addressor regions further comprises one of said respective set of identification numbers associated with said respective i-table index;
• and
• a second construction logic, responsive to the collection logic, configured to construct an m-table, said m-table having an m-table size, said m-table size selected to perfectly hash said respective set of identification numbers by said m-table size and to populate said m-table with said respective i-table index for each of said set of member holders by computing an m-table index responsive to each of said respective set of identification numbers modulo said m-table size and storing said respective i-table index in said m-table respective to said m-table index, wherein when constructing said m-table, the second construction logic is configured to construct a hash table for which there are no collisions between hashed values, wherein constructing the m-table comprises:
• determining an initial m-table size;
• hashing each of the identification numbers in the set of identification numbers by the m-table size to generate a set of corresponding hashed values;
• detecting if two or more of the hashed values are to be placed in a same location in the m-table, resulting in a collision in the m-table between the hashed values;
• and
• if so, increasing the size of the m-table and performing the hashing and detecting operations until a size is encountered for which the m-table can be perfectly-hashed.

An apparatus having a central processing unit (CPU) and a memory coupled to said CPU, to utilize a dispatch data structure for a holder in said memory, said dispatch data structure including an m-table and an i-table, said m-table having an m-table size, said i-table containing one or more holder addressor regions, wherein said apparatus comprises:

• a determination logic configured to determine an m-table index into said m-table, the determination logic configured to perform a modulo operation on an identification number of a holder of interest by said m-table size, wherein a size of said m-table is configured such that each of the hashed values generated by hashing each of the identification numbers by the m-table size can be placed in a location in the m-table without colliding with another of the hashed values, wherein said dispatch data structure also comprises a second m-table having said m-table size, said second m-table containing one or more identification numbers, said method further comprising determining whether the contents of said second m-table respective to said m-table index is equal to said identification number;
• a locator logic, responsive to the determination logic, configured to access an i-table index from said m-table responsive to said m-table index, said i-table index configured to locate one of said one or more holder addressor regions in said i-table;
• and
• a dispatch logic, responsive to the locator logic, configured to dispatch relative to said one of said one or more holder addressor regions.

A computer program product for constructing a dispatch data structure for a holder comprising a computer-usable data carrier providing instructions that, when executed by a computer, cause said computer to perform a method comprising:

• determining a set of member holders from which said holder inherits, one of said set of member holders having a respective set of members, each of said set of member holders uniquely identified by an identification number respectively;
• constructing an i-table containing one or more holder addressor regions, one of said one or more holder addressor regions containing addressors for said respective set of members, each of said one or more holder addressor regions associated with a respective i-table index;
• collecting a respective set of identification numbers for said set of member holders, wherein each of said one or more holder addressor regions further comprises one of said respective set of identification numbers associated with said respective i-table index;
• constructing an m-table, said m-table having an m-table size, said m-table size selected to perfectly hash said respective set of identification numbers by said m-table size, wherein constructing the perfectly-hashed m-table involves constructing a hash table for which there are no collisions between hashed values, wherein constructing the m-table comprises:
• determining an initial m-table size;
• hashing each of the identification numbers in the set of identification numbers by the m-table size to generate a set of corresponding hashed values;
• detecting if two or more of the hashed values are to be placed in a same location in the m-table, resulting in a collision in the m-table between the hashed values;
• and
• if so, increasing the size of the m-table and performing the hashing and detecting operations until a size is encountered for which the m-table can be perfectly-hashed;
• and
• populating said m-table with said respective i-table index for each of said set of member holders, by computing an m-table index responsive to each of said respective set of identification numbers modulo said m-table size and storing said respective i-table index in said m-table respective to said m-table index.

A computer program product for utilizing a dispatch data structure for a holder, said dispatch data structure including an m-table and an i-table, said m-table having an m-table size, said i-table containing one or more holder addressor regions, comprising a computer-usable data carrier providing instructions that, when executed by a computer, cause said computer to perform a method comprising:

• determining said m-table index into said m-table by accessing an identification number of a holder of interest and computing said identification number modulo said m-table size, wherein a size of said m-table is configured such that each of the hashed values generated by hashing each of the identification numbers by the m-table size can be placed in a location in the m-table without colliding with another of the hashed values, wherein said dispatch data structure also comprises a second m-table having said m-table size, said second m-table containing one or more identification numbers, said method further comprising determining whether the contents of said second m-table respective to said m-table index is equal to said identification number;
• accessing said i-table index from said m-table responsive to said m-table index, said i-table index locating one of said one or more holder addressor regions in said i-table;
• and
• dispatching relative to said one of said one or more holder addressor regions.