Data structure supporting random delete and aging/timer function

• US 20050050188A1
• Filed: 09/03/2003
• Published: 03/03/2005
• Est. Priority Date: 09/03/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Heddes, Marco, Davis, Gordon T., Hwang, Dongming
• Granted Patent: US 7,412,454 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• 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 system for managing dynamic data structures, comprising:

a) a data structure capable of containing multiple data entries;

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

c) a timer control block for each data entry; and

d) an association between each data entry and a corresponding timer control block.

2. The system according to claim 1 further including the capability of searching 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 an aging/timer value in each timer control block.

4. The system according to claim 2 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 association between each data entry and a corresponding timer control block utilizes bidirectional pointers.

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

8. The system according to claim 7 wherein the 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.

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

10. The system according to claim 9 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.

11. The system according to claim 8 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.

12. The system according to claim 8 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.

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

14. The system according to claim 13 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.

15. The system according to claim 14 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.

16. A method for managing dynamic data base structures comprising

a) separating the timer parameters from the main entries in the data base structure and placing said timer parameters into timer control blocks;

and

b) establishing an association between said timer control blocks and corresponding data entries in said data structure.

17. The method according to claim 16 including the additional step of including a free queue of timer control blocks in the same timer loop used for timer control blocks assigned to active sessions.

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

19. The method according to claim 16 wherein the association between the session entry and its timer control block is established by using bidirectional pointers.

20. The method according to claim 19 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.

21. The method according to claim 20 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.

22. The method according to claim 16 including construction of 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.

23. The method according to claim 22 including the additional process of 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;

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.

24. The method according to claim 16 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.

25. The method according to claim 24 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.

26. The method according to claim 25 wherein a partition only supports 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.

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

28. The method according to claim 24 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.

29. The method according to claim 28, wherein a timer function detects timer control blocks marked as idle and advances the 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.

30. The method according to claim 29 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.

31. A computer readable medium containing instructions for managing dynamic data structures to enable the structures to handle large numbers of active entries including the addition and deletion of active databases thereto and therefrom by partitioning an entry into basic application data and a timer control block.

32. The computer readable medium according to claim 31 further including instructions to maintain an association between a session entry and a timer control block using bidirectional pointers.

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

34. The medium according to claim 33 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.