A processor natively executes lookup instructions. The lookup instruction
is decoded to determine which general-purpose register (GPR) contains a
pointer to a lookup key in a buffer. A variable-length key is read from
the buffer and hashed to generate an index into a first-level cache and a
hashed tag. An address of a bucket of entries for the index is generated
and tags from these entries are read and compared to the hashed tag. When
an entry matches the hashed tag, a second-level entry is read. A stored
key from the second-level entry is compared to the input key to determine
a match. The addresses of the matching second-level and first-level
entries are written to GPR's specified by operands decoded from the
lookup instruction. When the key or entry data is long, the second-level
entry also contains a pointer to a key extension or data extension in a
third-level cache.