Tree bitmap data structures and their use in performing lookup operations

One or more computer readable media for storing a data structure, the data structure comprising:

• a first segmented tree bitmap and a second segmented tree bitmap for identifying for each node of a plurality of nodes within a stride of a number of tree levels greater than one whether said each node is a prefix or vacant node, the plurality of nodes representing a plurality of tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of the plurality of tree levels in the stride, the lowest-level subset of the plurality of nodes including two or more nodes;
• a first child bitmap;
• a second child bitmap;
• a first result array;
• a second result array;
• a first segmented trie element including the first segmented tree bitmap, a pointer to the first child bitmap and a pointer to the first result array;
• a second segmented trie element including the second segmented tree bitmap, a pointer to the second child bitmap, and a pointer to the second result array;
• wherein the first child bitmap and the second child bitmaps identify which trie paths emanate and which trie paths do not emanate from the lowest-level subset of the plurality of nodes for the first segmented tree bitmap and the second segmented tree bitmap, respectively.

An apparatus for performing lookup operations, the apparatus comprising:

• one or more computer-readable media configured to store a data structure representing a plurality of prefixes partitioned into a plurality of strides of a number of tree levels greater than one;
• and
• one or more lookup engines for performing lookup operations on the data structure;
• wherein the data structure includes:
• a tree bitmap for identifying for each node of a plurality of nodes within a stride of a number of tree levels greater than one whether said each node is a prefix or vacant node, the plurality of nodes representing a plurality of tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of the plurality of tree levels in the stride, the lowest-level subset of the plurality of nodes including two or more nodes;
• a child bitmap for identifying which trie paths emanate and which trie paths do not emanate from the lowest-level subset of the plurality of nodes;
• a result array;
• and
• a trie element, the trie element including the child bitmap, a pointer to the tree bitmap, and a pointer to the result array.

An apparatus for performing lookup operations, the apparatus comprising:

• one or more computer-readable media configured to store a data structure representing a plurality of prefixes partitioned into a plurality of strides of a number of tree levels greater than one;
• and
• one or more lookup engines for performing lookup operations on the data structure;
• wherein the data structure includes:
• a first segmented tree bitmap and a second segmented tree bitmap for identifying for each node of a plurality of nodes within a stride of a number of tree levels greater than one whether said each node is a prefix or vacant node, the plurality of nodes representing a plurality of tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of the plurality of tree levels in the stride, the lowest-level subset of the plurality of nodes including two or more nodes;
• a first child bitmap;
• a second child bitmap;
• a first result array;
• a second result array;
• a first segmented trie element including the first segmented tree bitmap, a pointer to the first child bitmap and a pointer to the first result array;
• a second segmented trie element including the second segmented tree bitmap, a pointer to the second child bitmap, and a pointer to the second result array;
• wherein the first child bitmap and the second child bitmaps identify which trie paths emanate and which trie paths do not emanate from the lowest-level subset of the plurality of nodes for the first segmented tree bitmap and the second segmented tree bitmap, respectively.

An apparatus for performing lookup operations, the apparatus comprising:

• one or more computer-readable media configured to store a data structure representing a plurality of prefixes partitioned into a plurality of strides of a number of tree levels greater than one;
• and
• one or more lookup engines for performing lookup operations on the data structure;
• wherein the data structure includes:
• a tree bitmap for identifying for each node of a plurality of nodes within a stride of a number of tree levels greater than one whether said each node is a prefix or vacant node, the plurality of nodes representing a plurality of tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of the plurality of tree levels in the stride, the lowest-level subset of the plurality of nodes including two or more nodes;
• a child bitmap for identifying which trie paths emanate and which trie paths do not emanate from the lowest-level subset of the plurality of nodes;
• a trie element, the trie element including the child bitmap and a pointer to the tree bitmap;
• and
• a result array;
• and
• wherein the tree bitmap includes a pointer to the result array.

An apparatus for performing lookup operations, the apparatus comprising:

• one or more computer-readable media configured to store a data structure representing a plurality of prefixes partitioned into a plurality of strides of a number of tree levels greater than one;
• and
• one or more lookup engines for performing lookup operations on the data structure;
• wherein the data structure includes:
• a first trie element including:
• a tree bitmap for identifying for each node of a plurality of nodes within a stride of a number of tree levels greater than one whether said each node is a prefix or vacant node, the plurality of nodes representing a plurality of tree levels, a lowest-level subset of the plurality of nodes corresponding to a lowest level of the plurality of tree levels in the stride, the lowest-level subset of the plurality of nodes including two or more nodes;
• a child bitmap for identifying which trie paths emanate and which trie paths do not emanate from the lowest-level subset of the plurality of nodes;
• and
• a pointer for identifying a link to a next-level trie element.