Performance and memory bandwidth utilization for tree searches using tree fragmentation

Claim 3

The method of claim 1 , wherein the hash table comprises a one-to-one hash table.

Claim 4

The method of claim 1 , wherein each of the plurality of leaf nodes are substantially equal in size.

Claim 5

The method of claim 1 , further comprising employing the data structure to perform a prefix search.

Claim 6

The method of claim 4 , further comprising forwarding an Internet protocol packet through employment of the prefix search.

Claim 7

The method of claim 1 , wherein a separate table is accessed when the tree fragment associated with the hash key has zero or one entries.

Claim 8

The method of claim 1 , wherein the step of assigning a leaf node tree fragment further comprises assigning Internet protocol routing information to a leaf node of the sub-tree fragment.

Claim 9

The method of claim 1 , further comprising a step of locating a leaf node within the tree fragment as a function of an associated memory address of the leaf node.

Claim 10

The method of claim 1 , wherein the step of storing the tree fragment comprises substantially one loading sequence.

Claim 11

The method of claim 1 , wherein the fragment header comprises a base address pointer, an indicia of the size of a decision node, and a bit mask indicating occupied leaf nodes.

Claim 12

The method of claim 1 , wherein the tree fragments comprise Patricia tree fragments.

Claim 13

A computer program product for initializing a data structure comprising a tree structure that employs a single hash table and a plurality of tree fragments, the computer program product having a computer-readable medium with a computer program embodied thereon, the computer program comprising: computer code for creating the single hash table; computer code for creating the plurality tree fragments comprising a plurality of decision nodes and a plurality of leaf nodes of the tree structure, wherein each of the plurality of tree fragments is substantially the same size and comprises a header; computer code for storing the plurality of tree fragments such that: the plurality of decision nodes are stored in a contiguous block of memory in a relative position based on the position of the decision node in the tree structure, including blank positions; wherein storing the tree fragment is a function of a local storage size, wherein the local storage size is selected from the group consisting of a memory burst access size, a bus transfer size and a cache line size; and the plurality of leaf nodes are stored in a contiguous block of memory based on he position of the leaf node in the tree structure, concatenating leaf nodes to eliminate blank positions; computer code for hashing at least one table entry corresponding to each tree fragment, thereby creating at least one hash key and at least one hash table entry; and computer code for assigning the tree fragment to at least one hash table entry.

Claim 14

A computer program product for initializing a data structure comprising a tree structure that employs a single hash table and a plurality of tree fragments, the computer program product having a computer-readable medium with a computer program embodied thereon, the computer program comprising: computer code for creating the single hash table; computer code for creating the plurality tree fragments comprising a plurality of decision nodes and a plurality of leaf nodes of the tree structure, wherein each of the plurality of tree fragments is substantially the same size and comprises a header; computer code for storing the plurality of tree fragments such that: the plurality of decision nodes are stored in a contiguous block of memory in a relative position based on the position of the decision node in the tree structure, including blank positions; wherein storing the tree fragment is a function of a local storage size, wherein the local storage size is selected from the group consisting of a memory burst access size, a bus transfer size and a cache line size; and the plurality of leaf nodes are stored in a contiguous block of memory based on he position of the leaf node in the tree structure, concatenating leaf nodes to eliminate blank positions; computer code for hashing at least one table entry corresponding to each tree fragment, thereby creating at least one hash key and at least one hash table entry; and computer code for assigning the tree fragment to at least one hash table entry.

Claim 15

The computer program product of claim 12 , wherein the fragment header comprises a base address pointer, an indicia of the size of a decision node, and a bit mask indicating occupied leaf nodes.

Claim 16

The computer program product of claim 12 , wherein the tree fragments comprise Patricia tree fragments.

Claim 17

A processor for initializing a data structure comprising a tree structure that employs a single hash table and a plurality of tree fragments, the processor including a computer program comprising: computer program code for creating the single hash table; computer program code for creating the plurality of tree fragments comprising a plurality of decision nodes and a plurality of leaf nodes of the tree structure, wherein each of the plurality of tree fragments is substantially the same size and comprises a header; computer program code for storing the plurality of tree fragments such that: the plurality of decision nodes are stored in a contiguous block of memory in a relative position based on the position of the decision node in the tree structure, including blank positions; wherein storing the tree fragment is a function of a local storage size, wherein the local storage size is selected from the group consisting of a memory burst access size, a bus transfer size and a cache line size; and the plurality of leaf nodes are stored in a contiguous block of memory based on the position of the leaf node in the tree structure, concatenating leaf nodes to eliminate blank positions; computer program code for hashing at least one table entry corresponding to each tree fragment, thereby creating at least one hash key and at least one hash table entry; and computer program code for assigning the tree fragment to at least one hash table entry.

Claim 18

A processor for initializing a data structure comprising a tree structure that employs a single hash table and a plurality of tree fragments, the processor including a computer program comprising: computer program code for creating the single hash table; computer program code for creating the plurality of tree fragments comprising a plurality of decision nodes and a plurality of leaf nodes of the tree structure, wherein each of the plurality of tree fragments is substantially the same size and comprises a header; computer program code for storing the plurality of tree fragments such that: the plurality of decision nodes are stored in a contiguous block of memory in a relative position based on the position of the decision node in the tree structure, including blank positions; wherein storing the tree fragment is a function of a local storage size, wherein the local storage size is selected from the group consisting of a memory burst access size, a bus transfer size and a cache line size; and the plurality of leaf nodes are stored in a contiguous block of memory based on the position of the leaf node in the tree structure, concatenating leaf nodes to eliminate blank positions; computer program code for hashing at least one table entry corresponding to each tree fragment, thereby creating at least one hash key and at least one hash table entry; and computer program code for assigning the tree fragment to at least one hash table entry.

Claim 19

The processor of claim 15 , wherein the fragment header comprises a base address pointer, an indicia of the size of a decision node, and a bit mask indicating occupied leaf nodes.

Claim 20

The processor of claim 15 , wherein the tree fragments comprise Patricia tree fragments.