Data structure supporting random delete and timer function

• US 7,792,873 B2
• Filed: 01/16/2008
• Issued: 09/07/2010
• Est. Priority Date: 09/03/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hwang, Dongming, Heddes, Marco, Davis, Gordon T.
• Primary Examiner(s): Lu; Kuen S
• Application Number:
  US12/015,198
• Publication Number:
  US 20080133467A1
• Time in Patent Office: 965 Days
• Field of Search: 707/101, 707/3
• US Class Current: 707/802
• CPC Class Codes: G06F 16/902 using more than one table in sequence, i.e. systems with three or more layers
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A procedure is used to provide data structures that handle large numbers of active data entries and a high rate of additions and deletions of active entries. The procedure utilizes one or more of the following modifications. Timers are removed from individual session table entries and are linked via pointers. Bilateral links are established between the session table and the timer structure. Aging/timer checks are applied to the timer control block (TCB). A chain of TCBs, optionally including an excess of blocks, may be used along with packing of multiple TCBs into a single memory location. This excess of blocks permits a terminated session to continue to occupy a TCB until the timer process progresses to that block location in the chain of blocks.

Claims

1. In a computer processor system for transferring an active file entry to and from a dynamic data structure in connection with networking tasks, comprising:

a) a data structure to handle the addition and the deletion of a large number of data entries;

b) at least one data entry associated with said data structure;

c) a timer control block for each data entry;

d) a bidirectional link pointer between each data entry and its corresponding timer control block; and

e) a tree structure consisting of a direct table (DT) and pattern search control blocks (PSCBs) to associate each data entry with a unique search key, said tree structure created by;

1) adding a new data entry to the data structure by;

a) removing an empty data entry from the data entry free queue;

b) removing an empty timer control block from the timer control block free queue; and

c) initializing the data entry and timer control block with application specific parameters and pointers to associate the data entry and timer control block, and

2) modifying the DT and PSCBs within the data structure to enable a search process to locate the added data entry.

2. The system according to claim 1 further including a search function to search the data structure to identify one of the data entries matching a search criteria.

3. The system according to claim 2 further comprising a timer function, wherein the timer function checks a timer value in the timer control block for each data entry.

4. The system according to claim 3 wherein each data entry represents a network session.

5. The system according to claim 4 further including sufficient timer control blocks to permit a terminated session to occupy a block until the timer function progresses to the block.

6. The system according to claim 2 wherein the data structure comprises a direct table and pattern search control blocks arranged in a tree structure that includes a unique search key for each data entry.

7. The system according to claim 6 wherein a plurality of timer control blocks are arranged in a fixed circular chain including a first section containing a free queue of timer control blocks and a second section containing timer control blocks assigned to active data entries.

8. The system according to claim 7 wherein the circular chain of timer control blocks is partitioned into multiple shorter loops, each of which includes its own timer support task.

9. The system according to claim 8 wherein a partition supports only timer control blocks initialized with the same timeout duration, and the order of timer control blocks within a partition are maintained in order of expected timer expiration.

10. The system according to claim 7 further including a timer restart that causes the timer control block to be recirculated, and further causes the data entry to be updated to be associated with a new timer control block.

11. The system according to claim 7 wherein a timer function is capable of detecting timer control blocks marked as idle and advancing a timer control block free queue tail pointer to effectively recirculate timer control blocks associated with terminated data entries for subsequent use with new data entries.

12. The system according to claim 11 wherein the timer function is able to detect timer control blocks with a timer value indicating the associated timer has expired.

13. The system according to claim 12 wherein the timer function, upon detection of an expired timer, is capable of advancing the timer control block free queue tail pointer to effectively recirculate timer control blocks associated with data entries for subsequent use with new data entries.

14. The system according to claim 13 wherein the timer is programmed to process timer control blocks marked as idle immediately but to delay processing of active timer control blocks to insure that active timer control blocks are processed at approximately the time their associated timer expiration value is equal to the current time maintained by the timer function.

15. A computer readable storage medium containing a program for transferring an active file entry to and from a dynamic data structure, comprising instructions to:

a) partition said active file into basic application data and a timer control block;

b) maintain an association between an active entry and its corresponding timer control clock using a bidirectional pointer;

c) include a free queue of timer control blocks in the same timer loop used for timer control blocks assigned to active sessions; and

d) construct a tree structure consisting of a direct table (DT) and pattern search control blocks (PSCBs) to associate each data entry with a unique search key, wherein the construction of the tree structure includes the additional process of;

1) adding a new data entry to the data structure by;

a) removing an empty data entry from the data entry free queue;

b) removing an empty timer control block from the timer control block free queue; and

c) initializing the data entry and timer control block with application specific parameters and pointers to associate the data entry and timer control block, and

2) modifying the DT and PSCBs within the data structure to enable a search process to locate the added data entry.

16. The computer readable storage medium according to claim 15 wherein the instructions direct an aging function to point to the next active session to test and control an insertion point for a new session and a deletion point for obsolete sessions.

17. The medium according to claim 16 wherein the instructions direct a timer restart action to re-circulate a timer control block and causes a new data entry to be updated to be associated with the recirculated timer control block.