Patent ID: 7725450
Filing Date: 2010-05-25
Classification: G06F

Abstract:
1. An integrated circuit device, comprising: a search engine having a pipelined arrangement of a plurality of search and tree maintenance sub-engines, wherein the search engine is configured to: (i) perform search operations on multi-way trees of search prefixes, (ii) concurrently perform update operations on the multi-way trees as they are being searched, and (iii) perform an update operation on a first multi-way tree by generating a modified copy of a first branch of the first multi-way tree, wherein the modified copy comprises a plurality of temporary node pointers associated with copies of nodes of the first branch of the first multi-way tree, wherein the plurality of temporary node pointers are generated by extracting the plurality of temporary node pointers from a free list within the search engine, and wherein the modified copy of the first branch does not comprise all nodes of the first multi-way tree.