Method and apparatus for improving the performance of object-oriented queues
View Patent ↗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 reusable object-oriented queue entry objects, the method comprising:
inserting an object-oriented queue entry object into the queue in response to a queue user calling a queue insert method, wherein the inserting includes
adding to a queue list an indicia of a queue entry object to be inserted into the queue,
changing the status of the queue entry object to be inserted into the queue from available queue entry object to in-use queue entry object,
returning the queue entry object to be inserted into the queue to the queue user, wherein the queue entry object to be inserted into the queue has invalid data therein,
receiving an insertion notification from the queue user when the queue entry object to be inserted into the queue is a valid queue entry object having valid data entered therein by the queue user, and
marking in the queue list as complete the insertion of the valid queue entry object into the queue; and
removing an object-oriented queue entry object from the queue in response to a queue user calling a queue removal method, wherein the removing includes
un-marking in the queue list as complete a queue entry object to be removed from the queue,
removing from the queue list an indicia of the queue entry object to be removed from the queue,
returning the queue entry object to be removed from the queue to the queue user, wherein the queue entry object removed from the queue has valid data therein,
receiving a removal notification from the queue user when the queue entry object to be removed from the queue has had its valid data extracted by the queue user, and
changing the status of the queue entry object removed from the queue from in-use queue entry object to available queue entry object.
2. 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.
3. The method as recited in claim 2 , 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 inserting the queue entry object into the queue includes calling an INSERT_DONE method, and wherein marking the insertion of the valid queue entry object into the queue as complete is performed in response to calling the INSERT_DONE method.
5. The method as recited in claim 1 , wherein removing the queue entry object from the queue includes calling a REMOVE_DONE method, and wherein changing the status of the reusable queue entry object removed from the queue list from in-use queue entry object to available queue entry object is performed in response to calling the REMOVE_DONE method.
6. 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.
7. 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.
8. The method as recited in claim 1 , wherein the queue has a queue object associated therewith, and wherein at least one of the queue insert method, the queue removal method and the queue list is included in the queue object.
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 head 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 the tail end of the queue.
11. An apparatus for managing a queue of reusable 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 in response to a queue user calling a queue insert method, wherein inserting the object-oriented queue entry into the queue includes
adding to a queue list an indicia of a queue entry object to be inserted into the queue,
changing the status of the queue entry object to be inserted into the queue from available queue entry object to in-use queue entry object,
returning the queue entry object to be inserted into the queue to the queue user, wherein the queue entry object to be inserted into the queue has invalid data therein,
receiving an insertion notification from the queue user when the queue entry object to be inserted into the queue is a valid queue entry object having valid data entered therein by the queue user, and
marking in the queue list as complete the insertion of the valid queue entry object into the queue; and
wherein the queue management module is configured to remove an object-oriented queue entry object from the queue in response to a queue user calling a queue removal method, wherein removing the object-oriented queue entry from the queue includes
un-marking in the queue list as complete a queue entry object to be removed from the queue,
removing from the queue list an indicia of the queue entry object to be removed from the queue,
returning the queue entry object to be removed from the queue to the queue user, wherein the queue entry object removed from the queue has valid data therein,
receiving a removal notification from the queue user when the queue entry object to be removed from the queue has had its valid data extracted by the queue user, and
changing the status of the queue entry object removed from the queue from in-use queue entry object to available queue entry object.
12. 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, wherein the queue management module generates the plurality of queue entry objects by receiving 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 received reusable queue entry object.
13. A computer readable medium having instructions stored thereon that, when executed by a processor, carry out a method for managing a queue of reusable object-oriented queue entry objects, the instructions comprising:
instructions for inserting an object-oriented queue entry object into the queue in response to a queue user calling a queue insert method, wherein the inserting includes
instructions for adding to a queue list an indicia of a queue entry object to be inserted into the queue,
instructions for changing the status of the queue entry object to be inserted into the queue from available queue entry object to in-use queue entry object,
instructions for returning the queue entry object to be inserted into the queue to the queue user, wherein the queue entry object to be inserted into the queue has invalid data therein,
instructions for receiving an insertion notification from the queue user when the queue entry object to be inserted into the queue is a valid queue entry object having valid data entered therein by the queue user, and
instructions for marking in the queue list as complete the insertion of the valid queue entry object into the queue; and
instructions for removing an object-oriented queue entry object from the queue in response to a queue user calling a queue removal method, wherein the removing includes
instructions for un-marking in the queue list as complete a queue entry object to be removed from the queue,
instructions for removing from the queue list an indicia of the queue entry object to be removed from the queue,
instructions for returning the queue entry object to be removed from the queue to the queue user, wherein the queue entry object removed from the queue has valid data therein,
instructions for receiving a removal notification from the queue user when the queue entry object to be removed from the queue has had its valid data extracted by the queue user, and
instructions for changing the status of the queue entry object removed from the queue from in-use queue entry object to available queue entry object.
14. The computer readable medium as recited in claim 13 , 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.