Search algorithm implementation for a network processor

摘要

A method of performing a search based upon a search criterion using a tree is proposed. In use an input is read as a search key and the most significant bits are used as an index to a search table representing a plurality of search nodes. Each non empty entry in the search table will contain a pointer to the next branch of the tree. The search table may use a hash function to generate an index key. A determination is then made if the pointer points to a leaf or branch of the tree. If the pointer is to a branch the procedure is repeated until a leaf object is identified and returned to the calling application. In no entry is found that matches the search a no match is returned. The search criterion may be a longest prefix match in which instance the method is executed to find the position of the distinguishing bit.