Apparatus, system and method for updating a sorted list

• US 20040267772A1
• Filed: 06/30/2003
• Published: 12/30/2004
• Est. Priority Date: 06/30/2003
• Status: Active Grant

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Intel Corporation
• Inventors: Perloff, Ronals S.
• Granted Patent: US 7,197,498 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method, apparatus, and system for updating a sorted list.

Claims

1. A method of updating a sorted database, comprising:

identifying an item to be added to the database and a position in the sorted database in which the item to be added is to be added;

identifying an item to be deleted from the database and a position of the item to be deleted in the sorted database;

deleting the item to be deleted from the database;

iteratively redefining the position of each item in the sorted list by one position from the location of the deleted item to the position in which the item to be added is to be added; and

adding the item to be added to the sorted list in the last vacated position.

2. The method of claim 1, wherein the item to be added is retrieved from an add queue.

3. The method of claim 1, wherein the item to be deleted is retrieved from a delete queue.

4. The method of claim 1, wherein the database position in which the item to be added is to be added is a position in which a previous item in the sorted database immediately prior to the position has a numeric value less than the item to be added and a following item in the sorted database immediately following the position has a numeric value greater than the item to be added.

5. The method of claim 1, wherein the database position in which the item to be added is to be added is a position in which a previous item in the sorted database immediately prior to the position has an associated position value less than the item to be added and a following item in the sorted database immediately following the position has an associated position value greater than the item to be added.

6. The method of claim 1, wherein iteratively redefining the position includes redefining the position of each item from the location of the deleted item to the position in which the item to be added to a position immediately prior to its current position when the item from the add queue is to be located in a position prior to the deleted item.

7. The method of claim 1, wherein iteratively redefining the position includes redefining the position of each item from the location of the removed item to the position in which the item to be added to a position immediately following its current position when the item from the add queue is to be located in a position after the deleted item.

8. A method of updating a sorted database, comprising:

placing an identification of an item to be added to the database in an add queue;

placing an identification of an item to be deleted from the database in a delete queue;

selecting the item from the add queue and the item from the delete queue;

removing the identified item to be deleted from the database;

iteratively redefining the position of each item in the sorted list by one position from the location of the removed item to the position in which the item from the add queue is to be added; and

adding the item from the add queue to the sorted list in the last vacated position.

9. The method of claim 8, wherein the add queue contains identifications of more than one item to be added to the database.

10. The method of claim 9, wherein the item selected from the add queue is the item that has been in the add queue for the longest time.

11. The method of claim 8, wherein the delete queue contains identifications of more than one item to be deleted from the database.

12. The method of claim 11, wherein the item selected from the add queue is the item that has been in the add queue for the longest time.

13. The method of claim 8, wherein the identification of the item to be deleted from the database includes a number associated with the position of the item to be deleted.

14. The method of claim 8, further comprising removing the items selected from the add queue and the delete queue from those queues.

15. The method of claim 8, wherein the database position in which the item from the add queue is to be added is a position in which a previous item in the sorted database immediately prior to the position has a numeric value less than the item from the add queue and a following item in the sorted database immediately following the position has a numeric value greater than the item from the add queue.

16. The method of claim 8, wherein the database position in which the item from the add queue is to be added is a position in which a previous item in the sorted database immediately prior to the position has an associated position value less than the item from the add queue and a following item in the sorted database immediately following the position has an associated position value greater than the item from the add queue.

17. The method of claim 8, wherein iteratively redefining the position includes redefining the position of each item from the location of the removed item to the position in which the item from the add queue is to be added to a position immediately prior to its current position when the item from the add queue is to be located in a position prior to the deleted item.

18. The method of claim 8, wherein iteratively redefining the position includes redefining the position of each item from the location of the removed item to the position in which the item from the add queue is to be added to a position immediately following its current position when the item from the add queue is to be located in a position after the deleted item.

19. A device, comprising:

a sorted list;

an add queue to contain items to be added to the sorted list;

a delete queue to contain items to be deleted from the sorted list; and

a processor to contain instructions that, when executed, cause the processor to;

select an item from the delete queue and remove that item from the sorted list;

iteratively redefine a position of each item in the sorted list by one position from the location of the removed item to a position in which the item from the add queue is to be added; and

add the item from the add queue to the sorted list in the last vacated position.

20. The device of claim 19, wherein if no item exists in the add queue and an item does exist in the delete queue, then no item will be deleted from the sorted list and the iterative redefining will begin with the last item in the sorted list.

21. The device of claim 19, wherein the database position in which the item from the add queue is to be added is a position in which a previous item in the sorted database immediately prior to the position has an associated position value less than the item from the add queue and a following item in the sorted database immediately following the position has an associated position value greater than the item from the add queue.

22. A device, comprising:

a storage device containing;

a sorted list of items;

an add queue to contain items to be added to the sorted list; and

a delete queue to contain items to be deleted from the sorted list; and

a processor to contain instructions that, when executed, cause the processor to;

select an item from the delete queue and remove that item from the sorted list;

iteratively redefine a position of each item in the sorted list by one position from the location of the removed item to a position in which the item from the add queue is to be added; and

add the item from the add queue to the sorted list in the last vacated position.

23. The device of claim 22, wherein if no item exists in the add queue and an item does exist in the delete queue, then no item will be deleted from the sorted list and the iterative redefining will begin with the last item in the sorted list.

24. The device of claim 22, wherein the database position in which the item from the add queue is to be added is a position in which a previous item in the sorted database immediately prior to the position has an associated position value less than the item from the add queue and a following item in the sorted database immediately following the position has an associated position value greater than the item from the add queue.

25. A system, comprising:

a storage node coupled to the network, the storage node having;

a storage device to contain a sorted list;

memory to contain an add queue containing items to be added to the sorted list and a delete queue containing items to be deleted from the sorted list; and

a processor to contain instructions that, when executed, cause the processor to;

select an item from the delete queue and remove that item from the sorted list;

iteratively redefine a position of each item in the sorted list by one position from the location of the removed item to a position in which the item from the add queue is to be added; and

add the item from the add queue to the sorted list in the last vacated position;

a first node coupled to the network to place an item in the add queue; and

a second node coupled to the network to place an item in the delete queue.

26. The system of claim 25, wherein the first and second nodes include processors.

27. An article of manufacture, comprising:

a computer readable medium having stored thereon instructions which, when executed by a processor, cause the processor to;

place an identification of an item to be added to the database in an add queue;

place an identification of an item to be deleted from the database in a delete queue;

select the item from the add queue and the item from the delete queue;

remove the identified item to be deleted from the database;

iteratively redefine the position of each item in the sorted list by one position from the location of the removed item to the position in which the item from the add queue is to be added; and

add the item from the add queue to the sorted list in the last vacated position.

28. The article of manufacture of claim 27, wherein iteratively redefining the position includes redefining the position of each item from the location of the removed item to the position in which the item from the add queue is to be added to a position immediately prior to its current position when the item from the add queue is to be located in a position prior to the deleted item.