Fast method of determining duplicates on a linked list

• US 5,765,165 A
• Filed: 02/29/1996
• Issued: 06/09/1998
• Est. Priority Date: 02/29/1996
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Harper, James
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/609,080
• Time in Patent Office: 831 Days
• Field of Search: 395/611, 395/612, 395/613, 395/615, 707/104, 707/102, 707/100
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Methods and computer program products are disclosed for improving the performance of hardware and software in which checking for duplicates on a linked list is required. In one form, a linked list is checked in its entirety for the presence of duplicates. In another, an element to be added to the linked list is checked to determine whether a duplicate of that element exists on the linked list.

Claims

1. A computer implemented method for checking for duplicates on a linked list stored on a computer, comprising the step of:

checking said linked list for duplicates using a hash bit map containing information about the linked list.

2. A computer implemented method of claim 1 for detecting duplicates on a linked list, in which the step of checking said linked list for duplicates using a hash bit map containing information about the linked list comprises the steps of:

a. allocating a hash bit map for the linked list and setting all bits in the hash bit map to a first state;

b. sequentially checking each list element of the linked list for possible duplicates, beginning with a first list element, by hashing a list element identifier of a list element being checked to one bit location of said hash bit map;

c. when the bit at said one bit location is in a first state, setting the bit at said one bit location to a second state and checking the next list element; and

d. when the bit at said one bit location is in a second state, comparing the identifier of the list element being checked with the identifier of each preceding list element on the linked list to see if a duplicate exists.

3. The computer implemented method of claim 1 for detecting whether a list element to be added to a linked list is a duplicate of a list element on the linked list, in which the step of checking said linked list for duplicates using a hash bit map containing information about the linked list comprises the steps of:

a. hashing a list element identifier for the list element to be added to the linked list to one bit location of said hash bit map; and

b. checking said bit location to determine whether a possible duplicate exists.

4. A computer implemented process of claim 3, in which the step of hashing a list element identifier for the list element to be added to the linked list to one bit location of said hash bit map comprises the steps of:

a. allocating a hash bit map for the linked list and setting all bits in the hash bit map to a first state; and

b. hashing a list element identifier for each list element of the linked list to one bit location of said hash bit map and setting the bit at said one bit location to a second state;

and the step of checking said bit location to determine whether a possible duplicate exists, comprises the steps of;

c. hashing a list element identifier of a list element to be added to the linked list to one bit location of said hash bit map; and

d. when the bit at said one bit location is in a first state, adding the list element to the linked list; and

when the bit at said one bit location is in a second state, comparing the identifier of the list element to be added to the linked list with the identifier of each list element on the linked list to determine if a duplicate exists.

5. Apparatus for checking for duplicates in a linked list comprising:

a computer processor having a memory medium containing said linked list; and

a computer program for checking said linked list for duplicates using a hash bit map containing information about said linked list.

6. The apparatus of claim 5, in which the linked list is one of plural linked lists constituting an inode cache.

7. The apparatus of claim 6 in which the inode cache is part of a Unix file system.

8. The apparatus of claim 5 in which the processor is a processor on a network.

9. A computer system comprising:

at least one computer; and

a device configured for checking a linked list for duplicates using a hash bit map containing information about the linked list.

10. The computer system of claim 9 in which,

said device configured for checking a linked list for duplicates using a hash bit map containing information about the linked list further comprises:

a. a device configured for allocating a hash bit map for the linked list and setting all bits in the hash bit map to a first state;

b. a device configured for sequentially checking each element of the linked list for possible duplicates, beginning with a first element, by hashing an element identifier for each element of the linked list to one bit location of said hash bit map;

c. a device configured for, when the bit at said one bit location is in a first state, setting the bit at said one bit location to a second state and checking the next element of the linked list; and

d. a device configured for, when the bit at said one bit location is in a second state, comparing the identifier of the element being checked with the identifier of each preceding element on the linked list to see if a duplicate exists.

11. The computer system of claim 9 in which,

said device configured for checking a linked list for duplicates using a hash bit map containing information about the linked list further comprises:

a. a device configured for allocating a hash bit map for the linked list and setting all bits in the hash bit map to a first state;

b. a device configured for hashing an element identifier for each element of the linked list to one bit location of said hash bit map and setting a bit at said one bit location to a second state if it is not already in the second state;

c. a device configured for hashing an element identifier of an element to be added to the linked list to one bit location of said hash bit map;

d. a device configured for, when the bit at said one bit location is in a first state, adding the element to the linked list; and

e. a device configured for, when the bit at said one bit location is in a second state, comparing the identifier of the element to be added to the linked list with the identifier of each element on the linked list to determine if a duplicate exists.

12. A product comprising:

a computer readable memory medium;

at least one linked list stored on said medium; and

a hash table, stored on said medium and containing information about the contents of the linked list, which permits a fast search for duplicates on the linked list.

13. A computer program product comprising:

a computer readable memory medium; and

a computer program stored on said medium for causing a computer to check a linked list for duplicates using a hash bit map containing information about the linked list.

14. A computer program product of claim 13 in which the computer program stored on said medium for causing a computer to check a linked list for duplicates using a hash bit map containing information about the linked list is a program for causing a computer to detect duplicates on a linked list, by:

a. allocating a hash bit map for the linked list and setting all bits in the hash bit map to a first state;

b. sequentially checking each element of the linked list for possible duplicates, beginning with a first element by hashing an element identifier for each element of the linked list to one bit location of said hash bit map;

c. when the bit at said one bit location is in a first state, setting the bit at said one bit location to a second state and checking the next element; and

d. when the bit at said one bit location is in a second state, comparing the identifier of the element being checked with the identifier of each preceding element on the linked list to see if a duplicate exists.

15. A computer program product of claim 13 in which the a computer program stored on said medium for causing a computer to check a linked list for duplicates using a hash bit map containing information about the linked list is a program for detecting whether an element to be added to a linked list is a duplicate of an element on the linked list by:

a. allocating a hash bit map for the linked list and setting all bits in the hash bit map to a first state;

b. hashing an element identifier for each element of the linked list to one bit location of said hash bit map and setting the bit at said one bit location to a second state

c. hashing an element identifier of an element to be added to the linked list to one bit location of said hash bit map;

d. when the bit at said one bit location is in a first state, adding the element to the linked list; and

e. when the bit at said one bit location is in a second state, comparing the identifier of the element to be added to the linked list with the identifier of each element on the linked list to determine if a duplicate exists.

16. A computer implemented method of checking for duplicate modes in a Unix File system, comprising the steps of:

a. selecting a group of inodes maintained as a linked list; and

b. checking said group of inodes for the existence of duplicates using a hash bit map containing information about the group of inodes selected.

17. The method of claim 16, comprising the additional step of:

c. repeating steps a. and b. until all groups of inodes maintained as linked lists have been checked.

18. A computer implemented method of checking for duplicates on a linked list stored in a computer on a network, comprising the steps of:

a. sending a computer program which checks linked lists for duplicates, using a hash bit map containing information about the linked list, from one computer on the network to the computer where checking for duplicates is to occur; and

b. executing said computer program at the computer where checking for duplicates is to occur.

19. A method of checking for duplicates on a linked list stored in a computer on a network, comprising the steps of:

a. receiving a computer program, which checks a linked list for duplicates using a hash bit map containing information about the linked list, over the network; and

b. executing said computer program.