STRUCTURE FOR DELETING LEAVES IN TREE TABLE STRUCTURES

• US 20090125535A1
• Filed: 01/08/2009
• Published: 05/14/2009
• Est. Priority Date: 06/03/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Heddes, Marco, Davis, Gordon T., Basso, Claude, Calvignac, Jean L., Patel, Piyush C., Perrin, Steven R., Randall, Grayson W., Rovner, Sonia K.
• Granted Patent: US 8,135,752 B2
• Time in Patent Office: Days
• 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

Techniques and articles of manufacture are provided comprising computer readable programs that, when executed on the computer, cause the computer 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. An article of manufacture comprising a computer usable medium having a computer readable program embedded in said medium, wherein the computer readable program, when executed on a computer, causes the computer to delete a leaf in a patricia tree leaf structure without interrupting the functioning of the patricia tree by:

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;

searching for the key in the prefix table if the patricia tree searching does not find the key in the patricia tree;

confirming that the key is deleted if the key is not found in the prefix table; and

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 if the patricia tree searching finds the key.

2. The article of manufacture of claim 1, wherein the prefix comprises an operational prefix and a history prefix, and wherein the computer readable program, when executed on the computer, causes the computer to search by:

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

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

3. The article of manufacture of claim 2, wherein the computer readable program, when executed on the computer, causes the computer to:

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

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

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

4. The article of manufacture of claim 3, wherein the computer readable program, when executed on the computer, causes the computer to:

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

move the received prefix to a pattern search control block entry and remove an operational prefix from the prefix table if determined that the first prefix length prefix has been received;

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

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

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