Method and structure for reducing search times

• US 20020165848A1
• Filed: 05/16/2001
• Published: 11/07/2002
• Est. Priority Date: 11/16/1998
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Insignia Solutions Plc (America's Suppliers, Inc.)
• Inventors: Darnell, Stephen, Sexton, Jeremy James, Rautenbach, Keith, Plummer, Wayne, Kramskoy, Jeremy Paul, Charnell, William Thomas, Dias, Blaise Abel Alec, Wynn, Michael John, Thomas, Stephen Paul, Guthrie, Philippa Joy
• Granted Patent: US 7,007,005 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 11/3612 by runtime analysis performance monitoring G06F11/3466
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: G06F 2209/481 Exception handling
• CPC Class Codes: G06F 8/4442 Reducing the number of cache misses; Data prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 8/445 Exploiting fine grain parallelism, i.e. parallelism at instruction level run-time instruction scheduling G06F9/3836
• CPC Class Codes: G06F 9/4484 Executing subprograms
• CPC Class Codes: G06F 9/449 Object-oriented method invocation or resolution
• CPC Class Codes: G06F 9/4491 Optimising based on receiver type
• CPC Class Codes: G06F 9/455 Emulation; Interpretation; Software simulation, e.g. virtualisation or emulation of application or operating system execution engines
• CPC Class Codes: G06F 9/45516 Runtime code conversion or optimisation
• CPC Class Codes: G06F 9/4812 by interrupt, e.g. masked
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A method and structure for reducing search times. The method includes examining the entries in a list in turn beginning with the entry pointed to by a start pointer and continuing until the particular entry is found. The start pointer is then reset to point at the particular entry that was found. The next search will therefore begin to search at the location where the last search ended. Such a strategy increases the likelihood of locating the particular entry faster. The list of entries includes next entry pointers that point to another entry in the list such that the next entry pointers together form a closed loop. If the entire list is searched and the particular entry is not found, the search is aborted.

Claims

7. A method of accessing a particular entry in a list of entries in a computer system, each of the entries including a next entry pointer that points to another entry in the list such that the next entry pointers together form a closed loop, the method comprising:

reading a start pointer of one of the entries;

examining the entries in the list in turn beginning with the entry pointed to by the start pointer and continuing until the particular entry is found;

if the particular entry is found then performing the following steps;

accessing the particular entity;

overwriting the start pointer so as to point to the particular entry; and

if the particular entry is not found and all of the entries in the list have been examined then performing the following step;

terminating examination of the entries.

1. A method of accessing a particular entry in a list of entries in a computer system, each of the entries including a next entry pointer that points to another entry in the list such that the next entry pointers together form a closed loop, the method comprising:

reading a start pointer of one of the entries;

examining the entries in the list in turn beginning with the entry pointed to by the start pointer and continuing until the particular entry is found;

accessing the particular entity; and

overwriting the start pointer so as to point to the particular entry.

2. A method as claimed in claim 1, further comprising terminating examination of the entries in the event that the particular entry is not found and all of the entries in the list have been examined.

3. A method as claimed in claim 1, wherein accessing the particular entry includes reading the entry.

4. A method as claimed in claim 1, wherein accessing the particular entry includes writing to the entry and the method further comprises imposing a mutex

5. A method as claimed in claim 1, wherein overwriting the start pointer does not require a mutex.

6. A method as claimed in claim 1, wherein the computer system is a multi-threaded environment and the overwriting step is performed atomically.

8. A method as claimed in claim 7, wherein accessing the particular entry includes reading the entry.

9. A method as claimed in claim 7, wherein accessing the particular entry includes writing to the entry and the method further comprises imposing a mutex

10. A method as claimed in claim 7, wherein overwriting the start pointer does not require a mutex.

11. A method as claimed in claim 7, wherein the computer system is a multi-threaded environment and the overwriting step is performed atomically.

12. A method of accessing a particular entry in a list of entries in a computer system, each of the entries including a next entry reference that refers to another entry in the list such that the next entry references together form a closed loop, the method comprising:

reading a start reference of one of the entries;

examining the entries in the list in turn beginning with the entry pointed to by the start reference and continuing until the particular entry is found;

accessing the particular entity; and

overwriting the start reference so as to point to the particular entry;

13. A method as claimed in claim 9, wherein accessing the particular entry includes writing to the entry and the method further comprises imposing a mutex.

14. A method as claimed in claim 9, wherein overwriting the start pointer does not require a mutex.

15. A method as claimed in claim 9, wherein the computer system is a multi-threaded environment and the overwriting step is performed atomically.

17. A storage structure as claimed in claim 16, wherein the entry other than the entry is a particular entry that was searched for and found.

18. A storage structure as claimed in claim 17, wherein the particular entry is searched for by examining the list of entries in turn beginning with an entry pointed to by the start pointer and continuing until the particular entry is found.

10-1. A method as claimed in claim 9, further comprising terminating examination of the entries in the event that the particular entry is not found and all of the entries in the list have been examined.

11-2. A method as claimed in claim 9, wherein the accessing and examining steps are omitted when the particular entry is not found.

12-3. A method as claimed in claim 9, wherein accessing the particular entry includes reading the entry.

16. A storage structure comprising

a list of entries, each entry having a next entry pointer and each next entry pointer pointing to another entry such that the next entry pointers together form a closed loop;

and

an overwritable start pointer that points to an entry in the list of entries, the start pointer capable of being overwritten to point to an entry other than the entry.