Method for selecting unique identifiers within a range

• US 6,363,372 B1
• Filed: 04/22/1998
• Issued: 03/26/2002
• Est. Priority Date: 04/22/1998
• Status: Expired due to Term

• Current Assignee: Zenith Electronics Corporation (LG Corporation)
• Original Assignee: Zenith Electronics Corporation (LG Corporation)
• Inventors: Lichterman, Kevin
• Primary Examiner(s): Alam, Hosain T.
• Application Number:
  US09/064,302
• Time in Patent Office: 1,434 Days
• Field of Search: 707/1-7, 707/100-102, 707/200, 711/202, 711/206, 711/209, 379/210-213, 704/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method for selecting a next available identifier. A plurality of unique identifiers are assigned, preferably in blocks, to each of a plurality of banks. Within each of the banks, when empty, there is one available minimum value identifier and one available maximum value identifier. A number of resident identifiers are counted in each of the banks and at least one bank having a lowest counted number is identified. Within the first available bank, a highest value of all resident identifiers is determined. In the first available bank, the highest value is compared to a maximum value. If the highest value is less than the maximum value, then the next available identifier is equal to a sum of the highest value plus an incremental value. When a check bank counter is set at a value or when the next available unique identifier is a value outside of a range of the corresponding bank, the next available bank is selected and an iteration process begins in the next available bank.

Claims

1. A method for selecting a next available identifier, the method comprising the steps of:

breaking an acceptable range of integer values that a plurality of unique identifiers may take into a number of banks;

assigning the unique identifiers to each of the banks so that within each of the banks when empty there is a minimum value identifier and a maximum value identifier;

counting a number of resident identifiers in each of the banks and setting a plurality of counted numbers that each correspond to a different one of the banks;

identifying a first available bank of the banks having a lowest counted number of the counted numbers;

determining a highest value of the resident identifiers in the first available bank;

comparing the highest value in the first available bank to a maximum value of the available maximum value identifier in the first available bank; and

when the highest value is less than the maximum value, assigning the next available identifier and a last highest value in the first available bank equal to a sum of the highest value plus an incremental value.

2. A method according to claim 1 further comprising the steps of:

when the highest value in the first available bank is greater than or equal to the maximum value in the first available bank identifying a second available bank of the banks having a lowest counted number of the counted numbers.

3. A method according to claim 2 further comprising the steps of:

determining a highest value of the unique identifiers in the second available bank;

comparing the highest value in the second available bank to a maximum value of the available maximum value identifier in the second available bank; and

when the highest value in the second available bank is less than the maximum value, assigning the next available identifier and the last highest value in the second available bank equal to a sum of the highest value in the second available bank plus the incremental value.

4. A method according to claim 3 further comprising the steps of:

when the highest value in the second available bank is greater than or equal to the maximum value in the second available bank, performing a linear search of the second available bank to determine the next available identifier.

5. In a method according to claim 4 wherein linearly searching the second available bank comprises the steps of:

searching from a lower boundary identifier of the unique identifiers having a lowest value of the unique identifiers in the second available bank to an upper boundary of the unique identifiers having a highest value of the unique identifiers in the second available bank for the next available identifier in the second available bank by detecting more than the incremental value between one of the identifiers in the second available bank and a next consecutive one of the identifiers in the second available bank.

6. In a method according to claim 5 wherein the next available identifier is equal to a sum of a lower value of the one of the identifiers plus the incremental value.

7. In a method according to claim 6 wherein an error signal is generated when a difference in value between each consecutive pair of the identifiers in the second available bank is greater than the incremental value.

8. In a method according to claim 5 wherein the incremental value is equal to unity.

9. In a method according to claim 5 wherein the resident identifiers in the second available bank are sorted in ascending order.

10. In a method according to claim 2 wherein a flag is set when the second available bank is identified.

11. In a method according to claim 1 wherein the unique identifiers are sequentially incremented.

12. In a method according to claim 1 wherein the identifiers are numbers.

13. In a method according to claim 12 wherein the incremental value is equal to unity.

14. In a method according to claim 1 wherein two of the lowest counted numbers exist.

15. In a method according to claim 1 wherein corresponding to each of the banks is a stored value representing the number of the resident identifiers in each of the banks and the stored value is updated when the number of the resident identifiers changes.

16. In a method according to claim 1 wherein the lowest counted number has a least absolute value of the counted numbers.

17. In a method according to claim 1 wherein each of the resident identifiers corresponds to and identifies a program stored in a corresponding bank of the banks.

18. In a method according to claim 1 wherein a next available bark of the banks is selected when the highest value in the first available bank is greater than the maximum value in the first available bank.