METHOD AND STRUCTURE FOR DELETING LEAVES IN TREE TABLE STRUCTURES
First Claim
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 2m 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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
5 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 2m 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. - View Dependent Claims (2, 3)
- m”
-
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 2m 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.
-
Specification