Patent ID: 6889225

Claim:
A circuit to search an external memory containing search results based on a search value received from an external controller, comprising: a hash unit to generate a hash output based on the search value, wherein said hash unit is operationally connected to an input bus connecting the circuit to the external controller; a content addressable memory (CAM) unit to store a CAM database of instances of the search values known to cause hash collisions in said hash unit and to match the search value against said CAM database such that a CAM output is provided if a match exists, wherein said CAM unit is also operationally connected to said input bus; a logic unit to: receive any said CAM output provided, to create an address value based there on, and to provide said address value on an output bus connecting the circuit to the external memory, wherein said address value represents an address in the external memory; and otherwise receive said hash output, create one or more hash addresses based there on, receive a hash pointer value and create said address value based there on, and receive a hash hit signal and responsive there to provide said address value on said output bus; a search data storage to: store a plurality of said hash pointer values, wherein said hash pointer values represent instances of said hash addresses; store a plurality of search data values, wherein said search data values represent instances of the search values; receive a said hash address from said logic unit and based there on retrieve a said hash pointer value and provide it to said logic unit; and retrieve a said search data value based on said hash pointer value; and a comparator operationally connected to said input bus to receive the search value there from, to receive said search data value from said search data storage, to compare the search value and said search data value to determine whether a match exists and, if a said match exists, to provide said hash hit signal to said logic unit.