Patent ID: 6675163
Filing Date: 2004-01-06
Classification: H04L,Y10S

Abstract:
A method for determining a full match for a variable length search key by a computer processing device, comprising the acts of:reading an input key as a search string; hashing the input key using a hash function to generate a hashed key; using the N most significant bits of the hashed key as an index into a table representing a plurality of root nodes of search trees wherein each non-empty entry contains a pointer to a next branch in the search tree or a leaf; determining if the pointer in a non-empty table entry points to a leaf or a next branch of the corresponding search tree; reading the next branch contents if the pointer does not point to the leaf of the corresponding search tree; reading the leaf contents when the leaf of a corresponding search tree is reached and comparing a pattern in the leaf with the hashed key to determine if the leaf pattern matches the hashed key; and returning the contents of the leaf found to the requesting application if the leaf pattern matches the hashed key.