Deterministic lookup using hashed key in a multi-stride compressed trie structure

An apparatus comprising circuitry configured to:

• hash an input lookup key to generate a hashed key;
• divide the hashed key into a plurality of strides including a first stride and a second stride;
• use the first stride to locate a first entry in a first-level stride table;
• locate a second entry in a second-level stride table using a table pointer in the first entry and the second stride;
• locate entries in additional stride tables based on the strides in the hashed key;
• locate a first bucket table using a first final pointer in a final entry;
• read first discriminant bits from the input lookup key at bit-positions indicated by a first discriminant bit-position field in the final entry;
• locate a selected first entry in the first bucket table using the first discriminant bits as an index into the first bucket table;
• determine that a stored key in the selected first entry matches the input lookup key;
• and
• return a lookup result stored in or pointed to by the selected first entry.

A system comprising a processor and a memory communicatively coupled to the processor, the system configured to:

• hash an input lookup key to generate a hashed key;
• divide the hashed key into a plurality of strides including a first stride and a second stride;
• use the first stride to locate a first entry in a first-level stride table;
• locate a second entry in a second-level stride table using a table pointer in the first entry and the second stride;
• locate entries in additional stride tables based on the strides in the hashed key;
• locate a first bucket table using a first final pointer in a final entry;
• read first discriminant bits from the input lookup key at bit-positions indicated by a first discriminant bit-position field in the final entry;
• locate a selected first entry in the first bucket table using the first discriminant bits as an index into the first bucket table;
• determine that a stored key in the selected first entry matches the input lookup key;
• and
• return a lookup result stored in or pointed to by the selected first entry.

A computer readable storage memory comprising computer readable instructions, the computer readable storage memory storing thereon:

• instructions for hashing an input lookup key to generate a hashed key;
• instructions for dividing the hashed key into a plurality of strides including a first stride and a second stride;
• instructions for using the first stride to locate a first entry in a first-level stride table;
• instructions for locating a second entry in a second-level stride table using a table pointer in the first entry and the second stride;
• instructions for locating entries in additional stride tables based on the strides in the hashed key;
• instructions for locating a first bucket table using a first final pointer in a final entry;
• instructions for reading first discriminant bits from the input lookup key at bit-positions indicated by a first discriminant bit-position field in the final entry;
• instructions for locating a selected first entry in the first bucket table using the first discriminant bits as an index into the first bucket table;
• instructions for determining that a stored key in the selected first entry matches the input lookup key;
• and
• instructions for returning a lookup result stored in or pointed to by the selected first entry.