Data structure supporting random delete and timer function

• US 7,412,454 B2
• Filed: 09/03/2003
• Issued: 08/12/2008
• Est. Priority Date: 09/03/2003
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Heddes, Marco, Davis, Gordon T., Hwang, Dongming
• Primary Examiner(s): Lu; Kuen S
• Application Number:
  US10/654,139
• Publication Number:
  US 20050050188A1
• Time in Patent Office: 1,805 Days
• Field of Search: 707/101, 707/3, 707/10
• US Class Current: 1/1
• 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. A method in computer processing for transferring an active file entry to or from a dynamic data base-structure comprising performing the steps of:

a) separating a timer parameter from the file entry in the data base structure and placing said timer parameter into a timer control block;

b) establishing a bidirectional association between said timer control blocks and a corresponding data entry in said dynamic data structure;

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

d) constructing 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 constructing 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.

2. The method according to claim 1 wherein the timer loop is partitioned into multiple shorter loops, and each of the shorter loops is provided with its own timer support task.

3. The method according to claim 1 wherein a session entry uses a single pointer to identify its timer control block and the timer control block uses a pointer to identify the session entry.

4. The method according to claim 3 wherein a timer restart action causes the timer control block to be recirculated and causes the session entry to be updated to point to a new timer control block.

5. The method according to claim 1 having the additional step of including a fixed circular chain of timer control blocks wherein a first section of the circular chain contains a free queue of timer control blocks while a second section in the same timer control block circular chain contains timer control blocks assigned to active data entries.

6. The method according to claim 5 wherein the circular chain of timer control blocks is partitioned into multiple shorter loops and each of the shorter loops is provided with its own timer support task.

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

8. The method according to claim 1 wherein a timer restart action causes a timer control block to be recirculated and causes a data entry to be updated to be associated with a new timer control block.

9. The method according to claim 5 wherein termination of the use of a data entry will cause the data entry to be returned to a free queue and will cause the associated timer control block to be marked as idle.

10. The method according to claim 9, wherein a timer function detects the timer control blocks marked as idle and advances the timer control block free queue tail pointer to effectively recirculate the timer control blocks associated with terminated data entries for subsequent use with new data entries.

11. The method according to claim 10 wherein the timer function immediately processes timer control blocks marked as idle but delays 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.