초록 ▼

A search apparatus and method for establishing efficiently whether a particular number, eg a MAC address, is stored in a database, eg in a communications bridge. The search is conducted stepwise on the basis of portions of the number, until one or zero match is found in the database. In the event th

A search apparatus and method for establishing efficiently whether a particular number, eg a MAC address, is stored in a database, eg in a communications bridge. The search is conducted stepwise on the basis of portions of the number, until one or zero match is found in the database. In the event that one match is found, a final confirmation is made that the whole of the number located and the number searched for are the same. This provides an efficient way to search among a subset of possible very large numbers.

대표청구항 ▼

[ I claim:] [1.] A device arranged to establish if a particular one of all possible M-digit numbers is stored in a storage means, said storage means being capable of storing a subset of possible M-digit numbers, the device comprising:search table means comprising a main search table and a plurality

[ I claim:] [1.] A device arranged to establish if a particular one of all possible M-digit numbers is stored in a storage means, said storage means being capable of storing a subset of possible M-digit numbers, the device comprising:search table means comprising a main search table and a plurality of subsidiary search tables having entries stored therein each entry in the main or a subsidiary search table comprising one of (i) an address of one M-digit stored in said storage means, (ii) a pointer to a subsidiary search table from which a further entry should be recovered, and (iii) an end indication being neither a valid said address nor a valid said pointer;means arranged to recover one or more entries sequentially from said search table means beginning with said main search table on the basis of specified portions of said M-digit number until the recovered entry comprises either a said address being the address of the only M-digit number stored in said storage means which matches said specified M-digit number in the specified portion or portions so far used, or a said end indication indicating that there no such M-digit numbers stored in said storage means; andmeans arranged to confirm whether the one M-digit number identified in the former case is the same as said specified M-digit number.