Method and structure for deleting leaves in tree table structures

• US 7,490,101 B2
• Filed: 08/04/2006
• Issued: 02/10/2009
• Est. Priority Date: 06/03/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Randall, Grayson W., Rovner, Sonia K., Heddes, Marco, Davis, Gordon T., Basso, Claude, Calvignac, Jean L., Patel, Piyush C., Perrin, Steven R.
• Primary Examiner(s): Mofiz; Apu
• Assistant Examiner(s): CHEN, TE Y
• Application Number:
  US11/462,404
• Publication Number:
  US 20060271576A1
• Time in Patent Office: 921 Days
• Field of Search: 707/3, 707/6, 707100-102, 370/401, 370/475
• US Class Current: 1/1
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A technique is provided to delete a leaf from a Patricia tree having a direct table and a plurality of PSCB'"'"'s which decode portions of the pattern of a leaf in the tree without shutting down the functioning of the tree. A leaf having a pattern is identified as a leaf to be deleted. Using the pattern, the tree is walked to identify the location of the leaf to be deleted. The leaf to be deleted is identified and deleted, and any relevant PSCB modified, if necessary. The technique also is applicable to deleting a prefix of a prefix.

Claims

1. A method of deleting a leaf in a patricia tree leaf structure without interrupting the functioning of the patricia tree, comprising:

providing a patricia tree leaf having a plurality of leaf keys, each of the keys having a pattern x bits in length wherein x is a positive integer;

the patricia tree further comprising a plurality of pattern search control blocks, each of the pattern search control blocks configured to decode m bits and store 2m possible combinations of bits, wherein m is a positive integer;

each of the pattern search control blocks containing a prefix and either an end-of-trail leaf or a pointer to another of the pattern search control blocks;

placing each of the prefixes in a tree prefix table;

searching for a key in the patricia tree;

if the patricia tree searching does not find the key in the patricia tree, searching for the key in the prefix table and if the key is not found in the prefix table confirming that the key is deleted; and

if the patricia tree searching finds the key, deleting the key from one of the pattern search control blocks and collapsing the patricia tree by eliminating the left most pattern search control block from the patricia tree.

2. The method of claim 1, the prefix comprising an operational prefix and a history prefix, and wherein the searching comprises:

looking in the operational prefixes of the prefix table to find a longest prefix match;

storing a found longest prefix match in an operational prefix of the prefix table; and

if no longest prefix match is found, storing a prefix in a one of the history prefixes of the prefix table.

3. The method of claim 2, further comprising:

maintaining the table history prefixes to allow for updating of the operational table during insertions and deletions;

an end bit in each pattern search control block indicating whether the pattern search control block contains a leaf or another node; and

a mode bit in each pattern search control block indicating a size of a next pattern search control block.

4. The method of claim 3, further comprising:

if a prefix indicator is on, determining if a prefix of a prefix length has been received by reference to a corresponding history prefix in the prefix table;

if determined that a prefix length prefix has been received;

moving the received prefix to a pattern search control block entry and removing an operational prefix from the prefix table;

if no other shorter prefix exists, turning off the prefix indicator;

if the other shorter prefix exists, updating an operational prefix of the prefix table; and

if determined that a prefix length prefix has not been received, obtaining a next longest prefix and copying it into a pattern search control block entry with its address.

5. A method of deleting a leaf in a patricia tree leaf structure without interrupting the functioning of the patricia tree, comprising:

producing computer executable program code;

storing the code on a computer readable storage medium;

providing the program code to be deployed and executed on a computer system, the program code causing the computer system to;

provide a patricia tree leaf having a plurality of leaf keys, each of the keys having a pattern x bits in length wherein x is a positive integer, the patricia tree further comprising a plurality of pattern search control blocks, each of the pattern search control blocks configured to decode m bits and store 2m possible combinations of bits, wherein m is a positive integer, each of the pattern search control blocks containing a prefix and either an end-of-trail leaf or a pointer to another of the pattern search control blocks;

place each of the prefixes in a tree prefix table;

search for a key in the patricia tree;

if the patricia tree search does not find the key in the patricia tree, search for the key in the prefix table and if the key is not found in the prefix table, confirm that the key is deleted; and

if the patricia tree search finds the key, delete the key from a one of the pattern search control blocks and collapse the patricia tree by eliminating the left most block pattern search control block from the patricia tree.

6. The method of claim 5, the prefix comprising an operational prefix and a history prefix, the program code comprising instructions which, when executed on the computer system, causes the computer system to:

look in the operational prefixes of the prefix table to find a longest prefix match;

store a found longest prefix match in an operational prefix of the prefix table; and

if no longest prefix match is found, store a prefix in a one of the history prefixes of the prefix table.

7. The method of claim 6, the program code comprising instructions which, when executed on the computer system, causes the computer system to:

maintain the table history prefixes to allow for updating of the operational table during insertions and deletions, wherein an end bit in each pattern search control block indicates whether the pattern search control block contains a leaf or another node, and a mode bit in each pattern search control block indicates a size of a next pattern search control block.

8. The method of claim 7, the program code comprising instructions which, when executed on the computer system, causes the computer system to:

if a prefix indicator is on, determine if a prefix of a prefix length has been received by reference to a corresponding history prefix in the prefix table;

if determined that a prefix length prefix has been received;

move the received prefix to a pattern search control block entry and remove an operational prefix from the prefix table;

if no other shorter prefix exists, turn off the prefix indicator;

if the other shorter prefix exists, update an operational prefix of the prefix table; and

if determined that a prefix length prefix has not been received, obtain a next longest prefix and copy it into a pattern search control block entry with its address.