Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1996-04-30
2001-05-15
Banankhah, Majid A. (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C707S793000
Reexamination Certificate
active
06233621
ABSTRACT:
The present invention relates generally to object-oriented computer systems associating a unique identifier to an object, and particularly to a system and method for efficiently allocating hashcodes to objects in a system where most or all objects are hashable, but relatively few objects are in fact ever hashed.
BACKGROUND OF THE INVENTION
In object-oriented computer systems, system resources can be characterized in the form of an object. In some of these systems, the objects can be stored in arrays or tables and accessed through the use of keys. A key is a consistent value that identifies an object with respect to other objects and provides direct access to the object. Typically, hashcodes are utilized as keys.
Various approaches have been used to associate a hashcode with an object. In systems where the memory locations for objects are static, the memory location of the object is used as the hashcode. However, the use of the memory location as a hashcode cannot be applied to systems which relocate objects during a garbage collection process. Since the memory location of an object changes during the lifetime of an object, a hashcode that is dependent on a memory location could not provide a consistent value.
Another approach is to generate and store a hashcode with each object's data space. This approach is undesirable since it requires extra space in the object's data space which may never be utilized. While there may be a large number of objects which are hashable, most of them are not referenced by their hashcodes. As a result, this approach has the distinct disadvantage of requiring a large amount of memory.
It is an object of the present invention to provide a system and method for providing a hashcode for an object on an as-needed basis so as to avoid the allocation of memory space for hashcodes that are not referenced.
It is another object of the present invention to provide a system and method as described above that is computationally efficient and that imposes essentially no computational overhead for frequently hashed objects, and that uses storage resources that are proportional to the number of hashed objects.
It is another object of the present invention to provide a system and method as described above which provides a hashcode that identifies an object with respect to all the other objects, that is consistent for the duration of the object, and that is not based on the memory location of the object's data space.
It is another object of the present invention to provide a system and method as described above which provides a hashcode for an object in a concurrent processing environment.
SUMMARY OF THE INVENTION
In summary, the present invention is an object-oriented computer system having a memory that stores a plurality of objects and a plurality of procedures. An object can be represented as an object data structure, the first element of which is a methods pointer to a methods array. Each object is an instance of a class and has a data reference stored with its methods pointer to a class data structure associated with this class. The class data structure has a methods array of pointers to methods used by the class.
The system uses two global hashoode procedures for providing the hashcode of an object and a hashcode cleanup procedure for reclaiming storage used by one of the hashcode procedures. The system uses a first global hashing procedure to service the initial request for an object's hashcode. Initially, objects do not have associated hashcodes. The first global hashing procedure generates a relatively unique hashcode for the object and stores it as private data in a local object-specific hashing procedure. The local object-specific hashing procedure's function is to retrieve the hashcode from its private data. The local object-specific hashing procedure is generated for an individual object rather than for the object class. This is done in order to preserve the integrity of the object's data structure in a concurrent processing environment.
A hashcode cleanup procedure is invoked as part of a garbage collection method in order to reclaim storage used by the local object-specific hashing procedure. The hashcode cleanup procedure relocates the object's data space to an alternate memory location and stores the associated hashcode, if any, in the object's data structure. It then releases the memory space for the local object-specific hashing procedure. The system then uses a second global hashing procedure to retrieve the hashcode from the object's data structure.
In a preferred embodiment, each object that does not have a hashcode (i.e. has not had a request for the object's hashcode) has a methods pointer that references a set of procedures that includes the first global hashing procedure. Each object that has been allocated a local object-specific hashing procedure has a methods pointer that references a set of procedures that includes its local object-specific hashing procedure. Objects that have hashcodes stored in the object's data structure each have a methods pointer that references the second global hashing procedure.
Furthermore, the first global hashing procedure includes instructions for updating a specified object's methods pointer to point to a set of procedures that includes the local object-specific hashing procedure. The hashcode cleanup procedure includes instructions for updating a specified object's methods pointer to point to a set of procedures that includes the second global hashing procedure.
More specifically, in a preferred embodiment, the computer system includes a set of object classes, and each object class includes a primary virtual function table (VFT) that includes pointers referencing a set of methods associated with the object class as well as a pointer that references the first global hashing procedure. Each object that does not have a hashcode has a methods pointer that references the primary VFT for a corresponding object class.
For each object that has a local object-specific hashing procedure, the system stores a local virtual function table (VFT) that includes pointers referencing the set of methods associated with its object class as well as a pointer that references that object's local object hashing procedure. The first global hashing procedure includes instructions for updating a specified object's methods pointer to reference its local VFT.
For each object class, the system stores a secondary virtual function table (VFT) that includes pointers referencing the set of methods associated with its object class as well as a pointer that references the second global hashing procedure. The second global hashing procedure includes instructions for retrieving the hashcode from the object's data structure. The hashcode cleanup procedure includes instructions for updating an object's methods pointer to reference the secondary VFT.
REFERENCES:
patent: 4695949 (1987-09-01), Thatte et al.
patent: 4775932 (1988-10-01), Oxley et al.
patent: 4996663 (1991-02-01), Nemes
patent: 5287499 (1994-02-01), Nemes
patent: 5321834 (1994-06-01), Weiser et al.
patent: 5355483 (1994-10-01), Serlet
patent: 5485613 (1996-01-01), Engelstad et al.
patent: 5577246 (1996-11-01), Priddy et al.
patent: 5652883 (1997-07-01), Adcock
patent: 5692185 (1997-11-01), Nilsen et al.
patent: 5802590 (1998-09-01), Draves
Ekow Otoo, “Balanced Multidimensional extendible hash tree”, ACM digital library, 1986.*
Hirano et al, “Extendible hashing for concurrent insertions and retrievals”, IEEE electronic library, 1996.*
Kyoji kawagoe, “Modified dynamic hashing”, ACM digital library, 1985.*
Flat et al, “Nonoblivious hashing”, ACM digital library, 1992.*
Isabelle Puaut, “Distributed Garbage Collector for Active Objects”, OOPSLA, 1994.*
Kafura et al, “Concurrent and Distributed Garbage Collection of Active Objects”, IEEE Transactions on Parallel and Distributed Systems, vol. 6, No. 4, Apr. 1995.
Banankhah Majid A.
Caldwell P. G.
Pennie & Edmonds LLP
Sun Microsystems Inc.
LandOfFree
System and method for space efficient hashcode allocation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for space efficient hashcode allocation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for space efficient hashcode allocation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2557915