Abstract:
Method and system for interface checking and interface method dispatching for wireless devices. Relationships between classes and object-oriented interfaces are analyzed and certain properties are exploited for use in performing interface checking and/or interface method dispatching.

Description:
RELATED CASE  
       [0001]     This application claims the benefit of and priority to U.S. provisional patent application Ser. No. 60/368,138, filed Mar. 29, 2002, the entire disclosure of which is incorporated herein by reference. 
     
    
     BACKGROUND  
       [0002]     1. Technical Field  
         [0003]     The present invention relates generally to wireless devices, and more particularly to handling software objects operating on a wireless device.  
         [0004]     2. Description of the Related Art  
         [0005]      FIG. 1  illustrates a set  10  of object-oriented classes. Each class  15  is typically compiled from source code into object code. A class  15  typically defines attributes and implements methods. A class  15  may also provide a constructor method for constructing objects that are instances of that particular class, which are said to be objects of that class type. Classes  10  may be related to one another via a class hierarchy, wherein a subclass is related to a parent class whereby the subclass may inherit attributes and/or methods from the parent class.  
         [0006]      FIG. 2  illustrates a set  20  of object-oriented interfaces. Each interface  25  is typically compiled from source code into object code. An interface  25  typically defines method signatures. As was the case with classes, interfaces  20  may be related to one another via an interface hierarchy, wherein a sub-interface is related to a parent interface and whereby a sub-interface may inherit method signatures from a parent interface. However, interfaces  20  differ from classes in at least two respects. First, interfaces do not implement methods, but rather define method signatures. Second, interfaces do not provide object constructors, but rather are used to cast objects of a particular class type into a particular interface type to enforce the exclusive use of the methods implemented in the class and accessible to the object, whose method signatures are defined in the interface.  
       SUMMARY  
       [0007]     In accordance with the teachings contained herein, a method and system are provided for interface checking and interface method dispatching on wireless devices. Relationships between classes and object-oriented interfaces are analyzed and certain properties are exploited for use in performing interface checking and/or interface method dispatching. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0008]      FIG. 1  illustrates a set of object-oriented classes;  
         [0009]      FIG. 2  illustrates a set of object-oriented interfaces;  
         [0010]      FIG. 3  illustrates the relationship between a typical class Cc and several interfaces;  
         [0011]      FIG. 4  illustrates a class that implements two interfaces directly;  
         [0012]      FIG. 5  illustrates a class that implements an interface indirectly via another interface;  
         [0013]      FIG. 6  illustrates a class that implements an interface indirectly via the class hierarchy;  
         [0014]      FIG. 7  illustrates an example set of classes and a set of interfaces;  
         [0015]      FIG. 8  illustrates a flowchart of an example embodiment of the method;  
         [0016]      FIG. 9  illustrates an exemplary embodiment of a method to carry out step  100  of  FIG. 8 ;  
         [0017]      FIG. 10  illustrates the first constraint of  FIG. 9 ;  
         [0018]      FIG. 11  illustrates a sample interface ordinal table;  
         [0019]      FIG. 12  illustrates an exemplary technique for optimizing the NP-complete steps  110  and  130  of  FIG. 10 ;  
         [0020]      FIG. 13  illustrates a method to carry out step  120  of  FIG. 9  to provide a class interface check (CIC) table;  
         [0021]      FIG. 14  illustrates a sample CIC table, as can be provided by the method of  FIG. 13 ;  
         [0022]      FIG. 15  illustrates the second constraint of  FIG. 9 ;  
         [0023]      FIG. 16  illustrates a sample method ordinal table;  
         [0024]      FIG. 17  illustrates a method of carrying out step  140  of  FIG. 9  to provide a class interface dispatch (CID) table;  
         [0025]      FIG. 18  illustrates a sample CID table, as can be provided by the method of  FIG. 17 ;  
         [0026]      FIG. 19  illustrates a method to carry out the step  200  of  FIG. 8  to communicate direct check and dispatch information to a runtime device;  
         [0027]      FIG. 20  illustrates a method to carry out the step  300  of  FIG. 8  to perform a direct check and dispatch on a runtime device;  
         [0028]      FIG. 21  illustrates an example embodiment of a direct interface check method;  
         [0029]      FIG. 22  illustrates an example embodiment of a direct dispatch method;  
         [0030]      FIG. 23  illustrates a direct check and dispatch system;  
         [0031]      FIG. 24  illustrates in greater detail a compiler system and media of  FIG. 23 ;  
         [0032]      FIG. 25  illustrates an example storage media of  FIGS. 23 and 24  in further detail;  
         [0033]      FIG. 26  illustrates an example runtime device;  
         [0034]      FIG. 27  illustrates in greater detail the exemplary runtime storage of  FIG. 26 ;  
         [0035]      FIG. 28  illustrates an embodiment of a method of compacting sparse CID tables in accordance with the optional step  800  of  FIG. 17 ;  
         [0036]      FIG. 29  illustrates sparse tables; and  
         [0037]      FIG. 30  illustrates the same table information found in  FIG. 29  but compacted by the method of  FIG. 28 . 
     
    
     DETAILED DESCRIPTION  
       [0038]      FIG. 3  depicts relationships between a typical class Cc  15  and several interfaces  25 . It was observed above that, in order for class Cc  15  to provide a constructor method for objects of type Cc, class Cc implements—either directly or indirectly—the methods whose signatures are defined in the interfaces  25  class Cc implements.  
         [0039]     For the purposes of this description (and the appended claims), the term implements takes on a “deep” meaning as compared to the traditional “shallow” meaning, where “deep” and “shallow” refer to the traversal of the class and interface hierarchies to ascertain whether a class implements a method signature or an interface. However, it should be understood that certain situations may involve the term “implements” as having solely a “shallow” traversal while other situations may entail a wider meaning for the term “implements.” 
         [0040]     When considering the interfaces “shallowly” implemented by a class, only those interfaces explicitly declared as implemented by the class are considered. The concept of “shallow” implementation may be extended into a “deep” implementation, wherein the class and interface hierarchies are used to determine those method signatures and interfaces that are either directly (equivalent to “shallow”) or indirectly implemented by the class.  
         [0041]     The concept of direct vs. indirect implementation of method signatures and interfaces is described as follows. As used herein, a class implements directly any method signature or interface for which it explicitly declares and provides an implementation.  
         [0042]     Furthermore, as used herein, a class implements indirectly via class hierarchy any method signature or interface it inherits from any of its super classes via the class hierarchy (i.e., from its parent class, or the parent class of its parent class, etc.; collectively known as the super classes of the class).  
         [0043]     Further still, as used herein, a class implements indirectly via interface hierarchy any method signature or interface it inherits from any of its super interfaces via the class hierarchy (i.e., from its declared interfaces, from its super classes declared interfaces, or from any of the super interfaces of these declared interfaces).  
         [0044]     In this description, whenever the term implements is used by itself, it will be understood that this is meant to include both direct and indirect implementation. Furthermore, whenever the term indirectly is used by itself, it will be understood that this is meant to include both indirectly via class hierarchy and indirectly via interface hierarchy.  
         [0045]      FIGS. 4-6  illustrate, by example, cases of direct and indirect implementation of interfaces by classes. In particular, three cases wherein a class implements at an interface—either directly or indirectly—are illustrated. Rather than illustrating all possible combinations of direct and indirect implementation, the drawings illustrate the concept of considering the relationship between classes and interfaces, such as whether a class implements two interfaces simultaneously. As used in this description and in the appended claims, a class implements two interfaces simultaneously if the class can implement multiple interfaces and the class inherits, either directly or indirectly, from each of the two interfaces. The method considers this type of relationship between interfaces and classes and is described in greater detail in reference to  FIGS. 8-22 .  
         [0046]     In the example of  FIG. 4 , class  15 A implements two interfaces  25 X,  25 Y directly.  
         [0047]     In the example of  FIG. 5 , a class  15 B implements an interface  25 Y indirectly via another interface  25 X. Class  15 B, like class  15 A in  FIG. 4 , implements directly interface  25 X—as illustrated by the solid arrow connecting class  15 B to interface  25 X. However, unlike class  15 A in  FIG. 4 , class  15 B implements indirectly (via the interface hierarchy) interface  25 Y. As illustrated, interface  25 X is a sub-interface of  25 Y, i.e.,  25 Y is either the parent interface of I x  or of any of the parent interfaces of  25 Y in the interface hierarchy.  
         [0048]     Finally, in the example of  FIG. 6 , class  15 C implements an interface  25 X indirectly via the class hierarchy, i.e., via another class  15 D.  
         [0049]     With respect to  FIG. 7 , a specific set of classes  15 P,  15 R and a set of interfaces  25 X,  25 Y will be used, as an example, to illustrate the embodiments of the method and system illustrated in the remaining figures. As shown, class  15 P implements interface  25 Y directly. Furthermore, class  15 R implements interface  25 X directly. Class  15 R is a subclass of  15 P and thereby implements interface  25 Y indirectly. Interface  25 X contains method signature  26 W, which is implemented by class  15 R in method implementation  16 W. Similarly, interface  25 Y contains method signature  26 Z, which is implemented by class  15 P in method implementation  16 Z.  
         [0050]     Also shown in  FIG. 7 , is example runtime object  35 R, an instance of class  15 R, which will be further described in reference to the runtime portions of the system and method, in  FIGS. 22 and 27 .  
         [0051]     With respect to the ternary relationship between class  15 R and interfaces  25 X and  25 Y, class  15 R implements simultaneously interfaces  25 X and  25 Y. In an assignment method, interface ordinal numbers  27 X and  27 Y are assigned to interfaces  25 X and  25 Y respectively. Furthermore, method ordinal numbers  28 W and  28 Z are assigned to method signatures  26 M and  26 Z respectively.  
         [0052]     The ordinal assignments to the interfaces and interface methods are stored in direct check and dispatch information data structures. During operation of a runtime device, the device may use the data structures to directly check if a runtime object can be cast into a particular type of interface. If so, then the device may further use the data structures to facilitate a direct dispatch of the desired method(s) associated with the checked interface. Generation of check and dispatch information is described in greater detail in reference to  FIGS. 8-22 .  
         [0053]     With reference to  FIG. 8 , a flowchart of one embodiment of the method, by way of example, is illustrated. Three steps  100 ,  200 , and  300  are illustrated.  
         [0054]     In the first step  100 , check and dispatch information is generated on a compiler system. This step is described in greater detail with reference to  FIGS. 9-18 . Furthermore, an exemplary embodiment of the compiler system is described in further detail with reference to  FIG. 23  wherein the compiler system is illustrated as a part of a larger system, and with reference to  FIG. 24  wherein an exemplary compiler system is illustrated. In an alternative embodiment, it is contemplated that this step may be carried out on the runtime device.  
         [0055]     In the second step  200 , the check and dispatch information generated in step  100  is communicated to a runtime device. This step is described in greater detail in reference to  FIG. 19 . Check and dispatch information may be prepared, stored, and communicated to a runtime device, via media which is described with reference to  FIG. 23  wherein the media is illustrated as a part of a larger system, and with reference to  FIG. 25  wherein an exemplary media is illustrated. In an alternative embodiment, it is contemplated that this step may be carried out on the runtime device.  
         [0056]     In the third and final step  300 , the check and dispatch information generated in step  100 , and communicated in step  200 , is used to perform, first a direct check step and then a direct dispatch step on a runtime device. This step is further illustrated in greater detail in  FIG. 20 , wherein direct check and direct dispatch steps are also illustrated. The direct check step is further detailed with reference to  FIG. 21 , whereas the direct dispatch step is further detailed with reference to  FIG. 22 . The runtime device is illustrated as a part of a larger system in  FIG. 23 , and an exemplary runtime device, a wireless device, is illustrated in greater detail in  FIGS. 26 and 27 .  
         [0057]     Although not expressly shown in the drawings, some portions of step  100  can be carried out on the runtime device. In the case where all portions of step  100  are carried out on the runtime device, then step  200  may need not be carried out as the runtime device and compiler system can be coterminous.  
         [0058]     With reference to  FIG. 9 , an exemplary embodiment of a method to carry out step  100  of  FIG. 8  is illustrated.  
         [0059]     At step  110 , interface ordinals are assigned to interfaces, while optimizing a first constraint. The constraint is illustrated by the expression  115  of  FIG. 10 , which states that interface ordinals are to be assigned to enforce the rule that two interface ordinals (such as for example with reference to  FIG. 7  interface ordinal  27 X and ordinal  27 Y) are different if there exists a class in the system that directly or indirectly implements both interfaces at the same time, such as for example with reference to  FIG. 7  class  15 R. At the end of step  110 , max i  interface ordinals will have been assigned to the interfaces of the system.  
         [0060]     A sample interface ordinal table  117  is illustrated in  FIG. 11 . Note that more than one interface may share the same interface ordinal in order to minimize the value of max i , the number of interface ordinals. In the sample interface ordinal table  117  of  FIG. 11 , additional entries are shown to illustrate the cases where many more classes and interfaces are in the system, not only those shown in the example of  FIG. 7 . Step  110  can be accomplished using any number of techniques for optimizing NP-complete problems. One such technique  300  is illustrated in  FIG. 12 , which will be described next.  
         [0061]     With reference to  FIG. 12 , a constraint is provided at step  310 , and at step  320  a set of items to be assigned ordinals is also provided. Items are assigned the same ordinal  0  at step  330 . At step  340 , the items are tested for satisfying the constraint. If the constraint is not satisfied (such as due to at least two items not satisfying the constraint and thereby resulting in a “collision” of their ordinal assignments), step  350  resolves this by using any one of a number of known techniques such as randomly choosing or using a weighted method. For example, by randomly choosing one of the interfaces involved in a conflict to have its ordinal changed (e.g., by adding a value of one to it) the conflict is thus resolved. Processing returns to step  340 .  
         [0062]     If the constraint is satisfied as determined at step  340 , then step  360  ensues. At step  360 , the ordinal assignments and the maximum number of ordinals in the system are stored.  
         [0063]     With reference back to  FIG. 9 , having described step  110 , the next step  120  of creating class interface check (CIC) tables is described next in greater detail with reference to  FIG. 13 . At step  121 , all classes in the system are processed in turn through steps  122  through  127 . At step  122 , a CIC table is created with max i  null references for the class Cc currently being processed. At step  123 , all interfaces in the system are processed in turn through steps  125  through  126 . At step  125 , the class Cc currently being processed is tested for directly or indirectly implementing the interface I i  currently being processed. If class Cc implements interface I i , then at step  125 , the reference corresponding to the interface ordinal of interface I i  in the CIC table of class Cc is set to point to the interface I i . At step  126 , if all interfaces have been processed, then step  127  ensues, if not then the next interface to process is selected, and processing continues at step  124 . At step  127 , if all classes have been processed, then the method ends, if not then the next class to process is selected, and processing continues at step  122 .  
         [0064]     A sample CIC table  128 , as can be provided by the method of  FIG. 13 , is illustrated in  FIG. 14 . Note that optionally only entries that correspond to interface ordinals of methods that are implemented by the particular class have non-null entries. For example with reference to  FIG. 7 , the CIC table corresponding to class Cr would have non-null entries at ordinals  27 X and  27 Y corresponding to interfaces  25 X and  25 Y respectively. In the sample CIC table  128  of  FIG. 14 , additional entries are shown to illustrate the cases where many more classes and interfaces are in the system, not only those shown in the example of  FIG. 7 .  
         [0065]     With reference back to  FIG. 9 , having described step  120 , the next step  130  of assigning method ordinals to interface method signatures, while optimizing a second constraint, is described next in greater detail with reference to  FIGS. 15, 16  and  FIG. 12 . The constraint is illustrated by the expression  135  of  FIG. 15 , which states that method ordinals are to be assigned to enforce the rule that two method ordinals (such as for example with reference to  FIG. 7  method ordinal  28 W and ordinal  28 Z) are different if there exists a class in the system that directly or indirectly implements both methods at the same time, such as for example with reference to  FIG. 7  class  15 R. At the end of step  130 , max m  method ordinals will have been assigned to the interface method signatures of the system.  
         [0066]     A sample method ordinal table  137  is illustrated in  FIG. 16 . It is noted that more than one method may share the same method ordinal in order to minimize the value of max m , the number of method ordinals. In the sample method ordinal table  135  of  FIG. 16 , additional entries are shown to illustrate the cases where many more classes and interfaces are in the system, not only those shown in the example of  FIG. 7 . As was the case with step  110 , step  130  can be accomplished using any number of techniques for optimizing NP-complete problems. One such technique  300  is illustrated in  FIG. 12 , which was already described above.  
         [0067]     With reference back to  FIG. 9 , having described step  130 , the next step  140  of creating class interface dispatch (CID) tables is described next in greater detail with reference to  FIG. 17 . At step  141 , all classes in the system are processed in turn through steps  142  through  147 . At step  142 , a CID table is created with max m  null references for the class Cc currently being processed. At step  143 , all interfaces in the system are processed in turn through steps  145  through  146 . At step  145 , the class Cc currently being processed is tested for directly or indirectly implementing the interface I i  currently being processed, and may use the CIC table. If class Cc implements interface I i , then at step  145 , the reference corresponding to the method ordinal of each method signature in interface I i  in the CID table of class Cc is set to point to the implementation of the method signature of Class Cc. This step may involve the use of the virtual function table for class Cc and a deep traversal of the class hierarchy of class Cc. At step  146 , if all interfaces have been processed, then step  147  ensues, if not then the next interface to process is selected, and processing continues at step  144 . At step  147 , if all classes have been processed, then the method ends, if not then the next class to process is selected, and processing continues at step  142 . After all classes have been processed, step  800  may follow in order to compact the tables. This step  800  is an optional improvement. A method of carrying out step  800  is discussed in greater detail with reference to  FIGS. 28-30 .  
         [0068]     A sample CID table  148 , as can be provided by the method of  FIG. 17 , is illustrated in  FIG. 18 . Note that optionally only entries that correspond to method ordinals of methods that are implemented by the particular class have non-null entries. For example with reference to  FIG. 7 , the CID table corresponding to class Cr would have non-null entries at ordinals  28 W and  28 Z corresponding to method signatures  26 W and  26 Z respectively. In the sample CID table  148  of  FIG. 18 , additional entries are shown to illustrate the cases where many more classes and interfaces are in the system, not only those shown in the example of  FIG. 7 .  
         [0069]     With reference back to  FIG. 8 , having described step  100 , the next step  200  of communicating direct check and dispatch information to a runtime device is described next in greater detail with reference to  FIG. 19 .  
         [0070]     With reference to  FIG. 19 , at step  210  direct check and dispatch information is provided, which was generated at step  100 . Direct check information includes interface ordinal assignments and CIC tables. Direct dispatch information includes method ordinal assignments and CID tables. Direct check and dispatch information may be provided by itself, or optionally bundled with auxiliary information such as the set of classes and interfaces, as part of a larger direct check and dispatch output.  
         [0071]     At step  220 , it is determined whether the compiler system that provided the direct check and dispatch information at step  210 , is physically connected to a runtime device. An example of physical connection is if he runtime device is electrically connected to the compiler system, such as for instance sitting in a cradle connected to the compiler system via a serial interface or fiber. An example of a non-physical connection is envisaged when the runtime device is a wireless communication device.  
         [0072]     At step  230 , if the runtime device was found to be connected physically to the compiler system at step  220 , the direct check and dispatch information is communicated to the runtime device by the compiler system over the physical connection.  
         [0073]     At step  240 , if the runtime device was not found to be connected physically to the compiler system at step  220 , the direct check and dispatch information is communicated to the runtime device wirelessly, if the runtime device is a wireless device.  
         [0074]     With reference back to  FIG. 8 , having described step  200 , the next step  300  of performing direct check and dispatch on a runtime device is described next in greater detail with reference to  FIG. 20 .  
         [0075]     With reference to  FIG. 20 , at step  310  a runtime object Or is provided, such as for example, with reference to the example of  FIG. 7 , runtime object  35 R.  
         [0076]     At step  320 , an interface Ir is provided, such as for example, with reference to the example of  FIG. 7 , interface  25 Y.  
         [0077]     At step  330 , a direct interface check is performed to verify if runtime object Or can be cast into the type of interface Ir. An example embodiment of a method to carry out this step is illustrated in  FIG. 21 , and will be described immediately after  FIG. 20 . If the object Or passes the check, then steps  340  and  350  ensue.  
         [0078]     At step  340 , a method signature m m  is provided, selected from the method signatures found in interface Ir for the purpose of calling the implementation of method m m  provided via object Or.  
         [0079]     At step  350 , a direct dispatch is performed of method m m  via interface Ir of object Or. An example embodiment of a method to carry out this step is illustrated in  FIG. 22 , and will be described after  FIG. 21 .  
         [0080]     However, if the object Or does not pass the check at step  330 , then at step  360  a runtime exception is thrown.  
         [0081]     With reference to  FIG. 21 , an example embodiment of a direct interface check method is described next. At step  331 , the class data Cr for object Or is provided. This class data allows the runtime system to determine what class type provided the constructor for the Or object.  
         [0082]     At step  332 , knowing the class Cr of object Or, the CIC(Cr) table for Cr found in the direct check and dispatch information, is provided.  
         [0083]     At step  333 , the interface ordinal ordinali(I i ) of interface I i  is provided, for example by looking it up in the interface ordinal table of the direct check and dispatch information.  
         [0084]     At step  334 , the entry in the CIC(Cr) table corresponding to the interface ordinal ordinali(I i ) of interface I i  is compared to a reference to interface I i  to perform the direct check. If the reference is equal to I i , then Object Or can be cast into the type corresponding to interface I i , and step  335  ensues wherein object Or is asserted as an instance of interface I i . However, if the reference is not equal to I i , then object Or cannot be cast into the type corresponding to interface I i , and wherein object Or is asserted as not being an instance of interface I i .  
         [0085]     With reference back to  FIG. 20 , having described step  330  performing a direct check with reference to  FIG. 21 , the step  350  of performing direct dispatch is described next in greater detail with reference to  FIG. 22 .  
         [0086]     With reference to  FIG. 22 , an example embodiment of a direct dispatch method is described next. At step  351 , the class data Cr for object Or is provided. This class data allows the runtime system to determine what class type provided the constructor for the Or object.  
         [0087]     At step  352 , knowing the class Cr of object Or, the CID(Cr) table for Cr found in the direct check and dispatch information, is provided.  
         [0088]     At step  353 , the method ordinal ordinal m (m m ) of interface method m m  is provided, for example by looking it up in the method ordinal table of the direct check and dispatch information.  
         [0089]     At step  355 , method mm is directly dispatched.  
         [0090]     Having described the three steps of the method of  FIG. 8 , a system suitable to cooperate with an embodiment of the method will be described next with reference to  FIGS. 23-27 .  
         [0091]     With reference to  FIG. 23 , a direct check and dispatch system  400  is illustrated. The direct check and dispatch system  400  includes a compiler system  500 , media  600 , and a runtime system  700 . The compiler system  500  generates the direct check and dispatch information. The media  600  is used to prepare or store the direct check and dispatch information for communication to the runtime device  700 . The runtime device  700  performs the direct check and dispatch using the direct check and dispatch information. Examples of each of these components of system  400  will be described next in reference to  FIGS. 24-27 .  
         [0092]     With reference to  FIG. 24 , the compiler system  500  and media  600  of  FIG. 23  are illustrated in greater detail.  
         [0093]     The compiler system  500  may include compiler storage  510  wherein can be stored a representation of a set of classes  512  and a representation of a set of interfaces  518 . The representations  512 ,  518  may be in source code form, object form, a reference to a network source, or any other representation that allows processor  520  to provide the set of interfaces and classes to the direct check and dispatch compiler software module  530 . The direct check and dispatch compiler software module  530  may embody the method steps  100  and  200  of  FIG. 8 .  
         [0094]     In some situations, the direct check and dispatch compiler software module  530  generates CIC and CID tables wherein interface and method ordinals are respectively assigned to interfaces and interface methods such that a first and second constraint are substantially satisfied. The constraints are used along with a technique for optimizing NP-complete ordinal assignment problems (as described above) during the generation of the direct check and dispatch information. The check and dispatch information is later used by a runtime device, such as for performing a direct interface check method wherein the CIC table is directly consulted using the interface ordinal to perform the check. The runtime device can also perform a direct dispatch method wherein the CID table is directly consulted using the method ordinal to perform the dispatch.  
         [0095]     The generated check and dispatch information  615  may be stored on media  600 . Although not necessary, the media  600  may also include as part of the direct check and dispatch output  610  not only the direct check and dispatch information  615 , but optionally a representation of the corresponding set of classes  612  and a representation of the set of interfaces  618 . The representations  612  and  618  need not be the same as the corresponding representations  512  and  518  found in the compiler system. The media  600  itself is intended to encompass both storage devices, such as RAM, flash, and disks, and communication media such as network connections and data streams.  
         [0096]     With reference to  FIG. 25 , an exemplary storage media  600 , such as flash, is illustrated. For a logical view of some of the same elements, see  FIG. 7 . Direct check and dispatch output  610  includes a set of classes  612 , a set of interfaces  618 , and direct check and dispatch information  615 . The set of classes illustrated includes Cr class data  15 R and other class data  15 P (see  FIG. 7  for a logical view). The set of interfaces  618  includes I x    25 X interface data, and  25 Y interface data. Direct check and dispatch information  615  includes CIC tables  616  and CID tables  617 , as well as interface and method ordinals  27 X,  27 Y and  28 W,  28 Z respectively. Only one CIC table CIC(Cr) and one CID table CID(Cr), both related to class Cr  15 R, are illustrated. CIC(Cr) table  616  has non-null entries at interface ordinal positions ord i (I x ) and ord i (I y ) corresponding to interface ordinals of interfaces I x    25 X and I y    25 Y respectively. CID(Cr) table  617  has non-null entries at method ordinal positions ord m (m w ) and ord m (m z ) corresponding to method ordinals of interface methods m w  and m z  of interfaces I y    25 Y and I x    25 X respectively.  
         [0097]     With reference to  FIG. 26 , an exemplary runtime device, which happens to be a wireless device  700 , is illustrated. Runtime device  700  includes runtime storage  705  to receive and store a representation of direct check and dispatch information  715  via media  600 . The direct check and dispatch information  715  need not be in the same representation  615  as found in media  600 , or as found in compiler system  500 . As illustrated, the direct check and dispatch information  715  is part of direct check and dispatch input  710 , which optionally includes representations  712  and  718  of the set of classes and interfaces, respectively. In addition to the direct check and dispatch information, runtime storage also includes a runtime context  750 , which is used in conjunction with the direct check and dispatch information  615 . The runtime context  750  may include any particular objects for which the direct check is performed, as well as any particular method calls on objects for which the direct dispatch is performed.  
         [0098]     Runtime processor  720  may execute the direct check and dispatch runtime software module  730  and provides direct check and dispatch information  715  to module  730  for the purpose of performing the direct check and dispatch method. It should be understood that the runtime software module may be implemented as a single program or a set of programs (e.g., a module to perform the direct check and another module to perform the direct dispatch). Runtime software module  730  may embody the step  300  of the method of  FIG. 8 .  
         [0099]     Also shown is transceiver  740  that allows runtime device  700  to communicate with compiler system  500  over wireless media  600 .  
         [0100]     With reference to  FIG. 27 , exemplary runtime storage  705  is illustrated. See  FIG. 7  for a logical view of some of the same elements. Direct check and dispatch output  710  includes a set of classes  712 , a set of interfaces  718 , and direct check and dispatch information  715 . The set of classes illustrated includes Cr class data  15 R and other class data  15 P (see  FIG. 7  for a logical view). The set of interfaces  718  includes I x    25 X interface data and  25 Y interface data. Direct check and dispatch information  715  includes CIC tables  716  and CID tables  717 , as well as interface and method ordinals  27 X,  27 Y and  28 W,  28 Z respectively. Only one CIC table CIC(Cr) and one CID table CID(Cr), both related to class Cr  15 R, are illustrated. CIC(Cr) table  716  has non-null entries at interface ordinal positions ord i (I x ) and ord i (I y ) corresponding to interface ordinals of interfaces I x    25 X and I y    25 Y respectively. CID(Cr) table  717  has non-null entries at method ordinal positions ord m (m w ) and ord m (m z ) corresponding to method ordinals of interface methods m w  and m z  of interfaces I y    25 Y and I x    25 X respectively. Also illustrated is runtime context  750  which includes Or object data  35 R (see  FIG. 7 ) and an Or method call  770 . The Or method call  770  is illustrated at the position of the program counter PC for the runtime context  750  as this condition could be used as a trigger to invoke the direct check and dispatch method of  FIG. 20  wherein at step  340  a runtime method call is provided. Also shown is virtual function table  760  which includes the addresses of the two interface methods of the example of  FIG. 7 , m z (Cr) and m w (Cr) each specified by interfaces  25 Y and  25 X respectively, and implemented by class data  15 P and  15 R respectively.  
         [0101]     A method of compacting sparse CID tables in accordance with the optional step  800  of  FIG. 17 , will be described next with reference to  FIG. 28 . After which, in order to better illustrate this method,  FIGS. 29 and 30  will be described.  FIG. 29  illustrates sparse tables.  FIG. 30  illustrates the same table information found in  FIG. 29  compacted by the method of  FIG. 28 .  
         [0102]     With reference to  FIG. 28 , at step  810  a Compact Table is allocated and all of its entries are set to null. The Compact Table can be allocated to accommodate as many entries as there are in all of the candidate sparse CID tables. For instance, if each of 3 candidate CID tables has 9 entries each corresponding to 9 ordinals ( 0  to  8 ), then the Compact Table can be allocated to have  27  (3×9) entries. The method will actually use less memory than was allocated, therefore step  890  is provided to recover unused memory, both in the Compact Table and in the CID tables, at the end of the method.  
         [0103]     At step  820 , each candidate sparse CID table is processed in turn through steps  830  to  870 .  
         [0104]     At step  830 , an offset value is set to zero. The offset value indicates how many entries of the Compact Table should be skipped in order to find the first entry of the sparse CID table being processed at step  820 .  
         [0105]     At step  840 , all entries of the candidate sparse CID table are compared to the corresponding entries in the Compact Table in order to determine if the candidate sparse CID table would fit at the current offset. For a given offset, correspondence between candidate sparse CID table entries and Compact Table entries is done by adding the ordinal number of the CID table entry to the offset of the Compact Table. A candidate sparse CID table fits at a given offset if and only if all non-null entries at ordinal position in the candidate sparse CID table find correspondence with null entries at position [offset+ordinal] in the Compact Table. If the candidate sparse table fits, then steps  860  and  870  ensue, or else step  850  ensues wherein the offset is incremented, and step  840  is performed again. Eventually, the offset will be sufficiently large so that step  840  determines that the candidate sparse table fits.  
         [0106]     At step  860 , the non-null entries in the candidate sparse CID table are copied to their corresponding position in the Compact Table.  
         [0107]     At step  870 , the address of the offset in the Compact Table is used as the new origin of the candidate sparse CID table, for example by setting the handle in memory which previously pointed to the address of the first entry in the candidate sparse CID table to point to the address of the offset entry in the Compact Table. Once step  870  is complete, the memory that was at the old candidate sparse CID table can be recovered or marked for recovery.  
         [0108]     At step  880 , the next candidate sparse CID table is processed through steps  830  to  870 , or having processed all sparse CID tables, the method continues at step  890 .  
         [0109]     At step  890 , memory that remains unused can be recovered. For instance, the memory of each candidate sparse CID table marked for recovery at step  870  can be recovered. Furthermore, all null entries at the end of the Compact Table can be recovered.  
         [0110]     With reference to  FIGS. 29 and 30 , the equivalence of the compact representation of  FIG. 30  with the sparse representation of  FIG. 29  will be described with reference to the steps of the method at  FIGS. 20-22 .  
         [0111]     With reference to  FIG. 29 , three sparse CID tables are shown:  920 X,  920 Y and  920 Z that collectively form the sparse table input  910  for the method of  FIG. 28 . A sparse CID table has non-null entries, and being sparse, null entries. Table  920 X has three non-null entries X 0 , X 4  and X 8  at ordinal positions  0 ,  4  and  8  respectively. Table  920 Y has two non-null entries Y 0  and Y 5  at ordinal positions  0  and  5  respectively. Table  920 Z has two non-null entries Z 2  and Z 4  at ordinal positions  2  and  4  respectively. Each CID table  920 X,  920 Y, and  920 Z has a handle  925 X,  925 Y and  925 Z respectively which points to the address of the first entry of the respective CID table. The sparse table input  910  resides in either storage or media  900 .  
         [0112]     With reference to  FIG. 30 , the same sparse CID table information is shown, i.e., every non-null entry of the sparse table input  910  of  FIG. 29  can be found in the compact tables output  930  of  FIG. 30 . Furthermore, so long as only non-null entries are accessed using the updated handles  925 X,  925 Z and  925 Y, then compact table  940  provides a compact representation of the sparse CID tables of  FIG. 29 .  
         [0113]     With reference back to  FIGS. 20-22 , step  353  of  FIG. 22  could equally well use the tables of  FIG. 29  or  FIG. 30  to provide non-null entry ordinal m (m m ). This is because the direct check step  334  of  FIG. 21  prevents the direct dispatch step  353  of  FIG. 22  from accessing non-null CID table entries by throwing an exception at step  336 .  
         [0114]     Having described in detail the preferred embodiments of the present invention, including the preferred methods of operation, it is to be understood that this operation could be carried out with different elements and steps. This preferred embodiment is presented only by way of example and is not meant to limit the scope of the present invention. As an illustration, the methods and systems disclosed herein are well suited for use in many wireless devices, such as personal digital assistants, mobile communication devices, cellular phones, and wireless two-way communication devices. Moreover, the methods and systems disclosed herein are useful in any device that uses an object-oriented computer system as well as can be implemented via compiler systems, computer-readable media, and runtime devices. The systems and methods may also have their information stored in data structures which are contained in memory as well as be transmitted via data signals embodied on carrier signals or other communication pathway media (e.g., fiber optics, infrared, etc.).