International Business Machines Corporation

Grayson Warren Randall

Gordon Taylor Davis

Claude Basso

Marco C Heddes

Piyush Chunilal Patel

Sonia Kiang Rovner

Jean Louis Calvignac

Steven Richard Perrin

Colin Beaton Verrilli

Clark Debs Jeffries

Palmer W Agnew

Richard Joseph Sheftic

Anne S Kellerman

Robert M Friedman

David P Spencer

Matthew William Kilpatrick Brown

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 leaf keys and 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, by placing each of the prefixes in a tree prefix table; searching for a key in the tree; searching for the key in the prefix table if the tree searching does not find the key in the tree; confirming that the key is deleted if the key is not found in the prefix table; 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.

Deleting leaves in tree table structures

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.

Method and structure for deleting leaves in tree table structures

A technique is provided to either insert or delete a leaf in 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 either a leaf to be inserted or deleted. Using the pattern, the tree is walked once to identify the location of the leaf to be deleted or the location where the leaf is to be inserted. If it is a delete operation, the leaf to be deleted is identified and deleted, and any relevant PSCB modified, if necessary. If it is an insert operation, the tree is walked a second time to insert the leaf and reform or create any PSCB in the chain that needs to be reformed or created. The technique also is applicable to inserting or deleting a prefix of a prefix.

Method of inserting and deleting leaves in tree table structures

A method, system and computer program product for eliminating memory corruption when performing multi-threaded tree operations. A network processor may receive a command to perform a tree operation on a tree on one or more of multiple threads. Upon performing the requested tree operation, the network processor may lock one or more resources during a portion of the execution of the requested tree operation using one or more semaphores. A semaphore may refer to a flag used to indicate whether to 'lock' or make available the resource associated with the semaphore. Locking may refer to preventing the resource from being available to other threads. Hence, by locking one or more resources during a portion of the tree operation, memory corruption may be eliminated in a multiple thread system while preventing these resources from being used by other threads for a minimal amount of time.

Eliminating memory corruption when performing tree functions on multiple threads

A tree structure and method to organize routing information for processing messages within a network, each message being associated with a search key of 'n' bits. The processing determines where to send the message next. The structure has a direct table (DT) of 2entries for decoding the first 'x' bits of the search key, and one or more pattern search control blocks (PSCB's), each having 2entries for decoding subsequent groups of &#x201c;m&#x201d; bits. Each PSCB entry and DT entry includes a pointer to data associated with a specific route, if at this point a specific routing table entry is a potential match to the search key or a pointer to a subsequent PSCB if the end of a search trail is not identified. Each PSCB entry DT entry also indicates that the search has been resolved to the end of the search trail.

Multi-bit Patricia trees

A method and system for finding a longest prefix match for a key in a computer network is disclosed. The method and system include providing a main engine and providing an auxiliary engine. The main engine is for storing a first plurality of addresses and for searching the first plurality of addresses for the longest prefix match for the key. None of the first plurality of addresses is a prefix for another address of the first plurality of addresses. The auxiliary engine is for storing and searching a second plurality of addresses. A first address of the second plurality of addresses is capable of including the prefix for a second address of the first plurality of addresses or for a third address for the second plurality of addresses. None of the first plurality of addresses is the prefix for any of the second plurality of addresses. Each of the second plurality of addresses is distinct from each of the first plurality of addresses.

Method and system for performing a longest prefix match search

Method, system and computer program product for updating pre-existing region-dependent software within multiple regions via a common software update without affecting the region-dependent nature of the software. The technique includes extracting region information from pre-existing region-dependent software on a user system; loading the non-functional software update onto the user system, the non-functional update being a common software update for the multiple regions; and merging the region information extracted from the pre-existing region-dependent software with the non-functional software update loaded onto the user system to produce a functional, updated region-dependent software on the user system. In one example, the user system comprises a digital video disc (DVD) PC system, and the distribution network is the internet. An activation module accompanies the common software update and accomplishes the extracting, loading and merging steps.

Method, system and computer program product for updating

The disclosure describes a system to permit communication between two dissimilar networks that involves an interface system. More particularly, it is an interface system to permit communication between a MAP network that is utilizing common application service elements (CASE) and a network of non-MAP computer equipment. The interface system that is described establishes a connection between the two networks which involves a process of decoding data from one network into predetermined component parts, and then encoding the component parts into data for transfer to computer equipment in the other network, and then, releasing the connection when the data transfer is completed, in accordance with the State Table of FIG. 3 of the drawings.

Map case network virtual connection interface system

A method of transforming a first editable form of a document prepared by a batch text processing system into a second and incompatible editable form for use in another batch or an interactive text processing system through the use of a transform mechanism is described. A significant step of this method requires the identification of a limited number of key state variables, whose values reflect information concerning source document controls that have been read in a sequence thereof. The next step requires a definition of control compatibility, which source document controls are compatible with other source controls that set the state variables to their current values in that sequence. After control compatibility has been determined, it will be necessary to define the output items that need to be written for the target document as part of the transformation of any possible input sequence. In the next step, with respect to the output items thus defined, an ordering or hierarchy of these items is established so that they will be uniformly handled in the transformation. Then, for each possible output item, determine a set of rules which will govern when and if that output item gets written to the target document based on the value of the key variables in response to a particular set of input items that have been read from the source document. The output item is written if any one or more of the rules is satisfied. Text, when encountered, is defined as always ending a sequence and thereby initiating a write, if appropriate, to the target document of the transformation of the preceding sequence of controls.

Growing community of inventors

Cary, NC, United States of America

Grayson Warren Randall