Patent ID: 7149749
Filing Date: 2006-12-12
Classification: G06F,Y10S

Abstract:
1. A method of inserting a leaf in a leaf structure having a pattern of x bits, wherein x is a positive integer, in length to 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 wherein a search of the leaf to be inserted is comprised of the steps of: first walking the Patricia tree a first time by decoding the y bits, skipping any bit pattern that is identical, and then decoding any subsequent relevant bits that are different in successive PSCB's to determine the place of insertion of the leaf to be inserted; if the leaf to be inserted already exists in the table, then updating any information in the existing leaf from the leaf being inserted; if the leaf being inserted does not already exist in the tree, then determining what modification, if any, is needed of any PSCB, and walking the tree a second time and inserting the leaf to be inserted at the determined place of insertion, and making any modifications to any relevant PSCB that has been determined is required.