METHOD AND STRUCTURE FOR DELETING LEAVES IN TREE TABLE STRUCTURES

• US 20060271576A1
• Filed: 08/04/2006
• Published: 11/30/2006
• 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 7,490,101 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

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 leaf structure having a pattern of x bits, wherein x is a positive integer, in length from a Patricia tree structure which is separate from said leaf structure and with pointers to the leaf structure without interrupting the functioning of the Patricia tree, and wherein said Patricia tree includes a direct table to decode y bits of the pattern, wherein y is a positive integer, and a series of Pattern Search Control Blocks (PSCB'"'"'s), each configured to decode “

m”

bits, wherein m is a positive integer, and store 2^m possible combinations of bits, and wherein said search of the leaf to be deleted is comprised of the steps of;

initially decoding the y bits and then decoding any relevant subsequent bits until the search pattern for the leaf to be deleted is identified, and then deleting the leaf to be deleted.

2. The method as defined in claim 1 wherein the decision where to delete a leaf is made in the direct table.

3. The method as defined in claim 1 wherein the decision where to delete a leaf is made in a PSCB.

4. The method as defined in claim 4 wherein an operational prefix of a prefix table and/or a history prefix of a prefix table are provided, and

wherein the decision where to delete the leaf is made in the operational prefix of the prefix table and/or history prefix of the prefix table.

5. An article of manufacture comprising a computer usable medium having a computer readable program embedded in said medium, wherein said computer readable program, when executed on a computer, causes the computer to:

delete a leaf from a leaf structure having a pattern of x bits, wherein x is a positive integer, in length from a Patricia tree structure which is separate from said leaf structure and with pointers to the leaf structure without interrupting the functioning of the Patricia tree, and wherein said Patricia tree includes a direct table to decode y bits of the pattern, wherein y is a positive integer, and a series of Pattern Search Control Blocks (PSCB'"'"'s), each configured to decode “

m”

bits, wherein m is a positive integer, and store 2^m possible combinations of bits, and wherein said search of the leaf to be deleted is comprised of the steps of;

initially decoding the y bits, skipping any bit pattern that is identical, and then decoding any relevant subsequent bits that are different until the search pattern for the leaf to be deleted is identified, and then deleting the leaf to be deleted.