Method and apparatus for improving the performance of object-oriented queues

Abstract

A method for managing object-oriented queues by reusing queue entry objects instead of creating and destroying each queue entry object inserted into and removed from the queue. Inserting a queue entry object into the queue involves changing the status of the queue entry object from available to in-use, adding the queue entry object to a queue list, returning a reusable queue entry object to the queue user, receiving an insertion notification that the queue entry object data is valid, and marking the insertion of the queue entry object into the queue as complete. Removing a queue entry object from the queue involves un-marking the queue entry object in the queue as complete, removing the queue entry object from the queue list, returning the valid queue entry object to the queue user, receiving a removal notification that valid data has been extracted from the queue entry object, and changing the status of the reusable queue entry object removed from the queue list from in-use to available.

1 . A method for managing a queue of object-oriented queue entry objects, the method comprising:
 inserting an object-oriented queue entry object into the queue by reusing an existing queue entry object in the queue, wherein inserting the queue entry object in the queue includes
 changing the status of an existing available queue entry object from available queue entry object to in-use queue entry object, and 
 entering valid data into the existing queue entry object in such a way that the existing queue entry becomes a valid queue entry object; and 
   removing an object-oriented queue entry object from the queue while maintaining the allocation of the queue entry object, wherein removing the object-oriented queue entry object from the queue includes
 extracting valid data from an existing in-use queue entry object in such a way that the existing in-use queue entry object becomes an invalid queue entry object, and 
 changing the status of the existing in-use queue entry object from in-use queue entry object to available queue entry object. 
   
     
     
         2 . The method as recited in  claim 1 , wherein the queue has associated therewith a queue list configured to determine an availability status of a queue entry object, the completion of the insertion of a queue entry object into the queue, and the completion of the removal of a queue entry object from the queue. 
     
     
         3 . The method as recited in  claim 1 , further comprising generating a plurality of reusable queue entry objects for insertion into the queue and removal from the queue, wherein generating the plurality of reusable queue entry objects includes providing a reusable queue entry object of the type to be inserted into the queue and removed from the queue and making at least one copy of the provided reusable queue entry object. 
     
     
         4 . The method as recited in  claim 1 , wherein at least one of inserting the queue entry object in the queue includes providing an insertion notification when the existing queue entry object becomes a valid queue entry object, and removing the object-oriented queue entry object from the queue includes providing a removal notification when the existing in-use queue entry object becomes an invalid queue entry object. 
     
     
         5 . The method as recited in  claim 1 , wherein the queue entry object to be inserted into the queue has a plurality of data fields and wherein the queue user enters valid data into the queue entry object to be inserted into the queue by setting the values of at least one data field in the queue entry object to be inserted into the queue. 
     
     
         6 . The method as recited in  claim 1 , wherein the queue entry object to be removed from the queue has a plurality of data fields and wherein the queue user extracts valid data from the queue entry object to be removed from the queue by reading or copying the values of the data fields in the queue entry object to be removed from the queue. 
     
     
         7 . The method as recited in  claim 1 , wherein inserting an object-oriented queue entry object into the queue is in response to a queue user calling a queue insert method, and wherein removing an object-oriented queue entry object from the queue is in response to a queue user calling a queue removal method. 
     
     
         8 . The method as recited in  claim 1 , wherein the queue has a head end and a tail end, wherein queue entry objects are inserted into the queue at the tail end of the queue, and wherein queue entry objects are removed from the queue at the head end of the queue. 
     
     
         9 . The method as recited in  claim 1 , wherein the queue has a head end and a tail end, wherein queue entry objects are inserted into the queue at the tail end of the queue, and wherein queue entry objects are removed from the queue at the tail end of the queue. 
     
     
         10 . The method as recited in  claim 1 , wherein the queue has a head end and a tail end, wherein queue entry objects are inserted into the queue at the tail end of the queue, and wherein queue entry objects are removed from the queue at a specific position in the queue. 
     
     
         11 . An apparatus for managing a queue of object-oriented queue entry objects, comprising:
 a controller configured to receive queue entry object insertion instructional information and queue entry object removal instructional information from a queue user;   a memory element coupled to the controller for storing at least a portion of the instructional information received by the controller; and   a queue management module coupled to the controller,   wherein the queue management module is configured to insert an object-oriented queue entry object into the queue by reusing an existing queue entry object in the queue, wherein reusing an existing queue entry object in the queue includes
 changing the status of an existing available queue entry object from available queue entry object to in-use queue entry object, 
 entering valid data into the existing queue entry object in such a way that the existing queue entry becomes a valid queue entry object, and 
 providing an insertion notification when the existing queue entry object becomes a valid queue entry object; and 
   wherein the queue management module is configured to remove an object-oriented queue entry object from the queue while maintaining the allocation of the queue entry object, wherein removing the object-oriented queue entry object from the queue includes
 extracting valid data from an existing in-use queue entry object in such a way that the existing in-use queue entry object becomes an invalid queue entry object, 
 providing a removal notification when the existing in-use queue entry object becomes an invalid queue entry object, and 
 changing the status of the existing in-use queue entry object from in-use queue entry object to available queue entry object. 
   
     
     
         12 . The apparatus as recited in  claim 11 , wherein the queue has associated therewith a queue list configured to determine an availability status of a queue entry object, the completion of the insertion of a queue entry object into the queue, and the completion of the removal of a queue entry object from the queue. 
     
     
         13 . The apparatus as recited in  claim 11 , wherein the queue management module is configured to generate a plurality of reusable queue entry objects for insertion into the queue and removal from the queue. 
     
     
         14 . The apparatus as recited in  claim 13 , wherein the queue management module generating the plurality of reusable queue entry objects includes the queue management module providing a reusable queue entry object of the type to be inserted into the queue and removed from the queue and making at least one copy of the provided reusable queue entry object. 
     
     
         15 . The apparatus as recited in  claim 11 , wherein the queue entry object to be inserted into the queue has a plurality of data fields and wherein the queue management module is configured to enter valid data into the queue entry object to be inserted into the queue by setting the values of at least one data field in the queue entry object to be inserted into the queue. 
     
     
         16 . The apparatus as recited in  claim 11 , wherein the queue entry object to be removed from the queue has a plurality of data fields and wherein the queue management module is configured to extract valid data from the queue entry object to be removed from the queue by reading or copying the values of the data fields in the queue entry object to be removed from the queue. 
     
     
         17 . The apparatus as recited in  claim 11 , wherein the queue management module inserting an object-oriented queue entry object into the queue is in response to a queue user calling a queue insert method, and wherein the queue management module removing an object-oriented queue entry object from the queue is in response to a queue user calling a queue removal method. 
     
     
         18 . A computer readable medium having instructions stored thereon that, when executed by a processor, carry out a method for managing a queue of object-oriented queue entry objects, the instructions comprising:
 instructions for inserting an object-oriented queue entry object into the queue by reusing an existing queue entry object in the queue, wherein reusing an existing queue entry object in the queue includes
 instructions for changing the status of an existing available queue entry object from available queue entry object to in-use queue entry object, 
 instructions for entering valid data into the existing queue entry object in such a way that the existing queue entry becomes a valid queue entry object, and 
 instructions for providing an insertion notification when the existing queue entry object becomes a valid queue entry object; and 
   instructions for removing an object-oriented queue entry object from the queue while maintaining the allocation of the queue entry object, wherein removing the object-oriented queue entry object from the queue includes
 instructions for extracting valid data from an existing in-use queue entry object in such a way that the existing in-use queue entry object becomes an invalid queue entry object, 
 instructions for providing a removal notification when the existing in-use queue entry object becomes an invalid queue entry object, and 
 instructions for changing the status of the existing in-use queue entry object from in-use queue entry object to available queue entry object. 
   
     
     
         19 . The computer readable medium as recited in  claim 18 , further comprising instructions for generating a plurality of reusable queue entry objects for insertion into the queue and removal from the queue, wherein the generating instructions include instructions for providing a reusable queue entry object of the type to be inserted into the queue and removed from the queue and instructions for making at least one copy of the provided reusable queue entry object. 
     
     
         20 . The computer readable medium as recited in  claim 18 , wherein the queue entry object to be inserted into the queue has a plurality of data fields, further comprising instructions for entering valid data into the queue entry object to be inserted into the queue by setting the values of at least one data field in the queue entry object to be inserted into the queue, and further comprising instructions for extracting valid data from the queue entry object to be removed from the queue by reading or copying the values of the data fields in the queue entry object to be removed from the queue.