Software management tree implementation for a network processor
First Claim
1. A method for performing a pattern range comparison for a variable length search key in a software managed tree by a computer processing device, comprising the acts of:
- reading an input key as a search string;
using the N most significant bits of the search key as an index into a table representing a plurality of root nodes of search trees wherein each non-empty entry contains a pointer to a next branch in the search tree or a leaf;
determining if the pointer in a non-empty table entry points to a leaf or a next branch of the corresponding search tree;
reading the next branch contents if the pointer does not point to the leaf of the corresponding search tree;
reading the leaf contents when the leaf of a corresponding search tree is reached and comparing a pair of patterns in the leaf with the search key to determine if the range defined by the pair of leaf patterns includes the search key; and
returning the contents of the leaf found to the requesting application if the leaf patterns include the search key.
1 Assignment
0 Petitions
Accused Products
Abstract
Novel data structures, methods and apparatus for a Software Managed Tree (SMT) which provides a mechanism to create tree structures that follow a search mechanism defined by a control point processor. The search mechanism does not require storage on the previous pointer and uses only a forward pointer along with a next bit or group of bits to test thereby reducing storage space for nodes. The search mechanism processes multiple filter rules for an application without requiring multiple searches and also allows various filter rules to be chained. Two patterns of the same length are stored in each leaf to define a range compare. A compare at the end operation is either a compare under range or a compare under mask. In a compare under range, the input key is checked to determine if it is in the range defined by the two patterns. In a compare under mask, the bits in the input key are compared with the bits in a first leaf pattern under a mask specified in a second leaf pattern.
-
Citations
48 Claims
-
1. A method for performing a pattern range comparison for a variable length search key in a software managed tree by a computer processing device, comprising the acts of:
-
reading an input key as a search string; using the N most significant bits of the search key as an index into a table representing a plurality of root nodes of search trees wherein each non-empty entry contains a pointer to a next branch in the search tree or a leaf; determining if the pointer in a non-empty table entry points to a leaf or a next branch of the corresponding search tree; reading the next branch contents if the pointer does not point to the leaf of the corresponding search tree; reading the leaf contents when the leaf of a corresponding search tree is reached and comparing a pair of patterns in the leaf with the search key to determine if the range defined by the pair of leaf patterns includes the search key; and returning the contents of the leaf found to the requesting application if the leaf patterns include the search key. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. A computer readable medium containing a plurality of data structures for performing a pattern range comparison for a variable length search key in a software managed tree, comprising:
-
a pattern or key that is to be searched; a direct table that stores a first address location for a search tree; a plurality of pattern search control blocks that each represent a branch in the search tree; a compare table that specifies at least one range compare associated with each entry; a programmable color key register to enable sharing a single table data structure among a plurality of independent search trees; and a plurality of leaves wherein each leaf stores a pair of patterns to compare with the search key. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25)
-
-
26. An apparatus fabricated on a semiconductor substrate for performing a pattern range comparison for a variable length search key in a software managed tree, comprising:
-
an embedded processor complex including a plurality of protocol processors and an internal control point processor that provide frame processing; a plurality of hardware accelerator co-processors accessible to each protocol processor and providing high speed pattern searching, data manipulation, and frame parsing; a plurality of programmable memory devices that store a plurality of data structures that represent at least one search tree, wherein the data structures include a direct table, a pattern search control block, a compare table and a leaf including a pair of patterns to compare with the search key; a programmable color key register to enable sharing a single table data structure among a plurality of independent search trees; and an control memory arbiter that controls the access of each protocol processor to the plurality of memory devices. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33, 34)
-
-
35. A computer readable medium containing a computer program product for performing a pattern range comparison for a variable length search key in a software managed tree, comprising:
-
program instructions that read an input key as a search string; program instructions that use the N most significant bits of the search key as an index into a table representing a plurality of root nodes of search trees wherein each non-empty entry contains a pointer to a next branch in the search tree or a leaf; program instructions that determine if the pointer in a non-empty table entry points to a leaf or a next branch of the corresponding search tree; program instructions that read the next branch contents if the pointer does not point to the leaf of the corresponding search tree; program instructions that read the leaf contents when the leaf of a corresponding search tree is reached and compare a pair of patterns in the leaf with the search key to determine if the range defined by the pair of leaf patterns includes the search key; and program instructions that return the contents of the leaf found to the requesting application if the leaf patterns include the search key. - View Dependent Claims (36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48)
-
Specification