| 摘要 |
The invention provides a method and system for memory management, in which at least some individual nodes in a hybrid trie are striped across a set of pipelined memories. Memory management is performed for a hybrid trie including both branch-search nodes and leaf-search nodes and maintained in a sequence of pipelined memories. The method provides for insertion and removal of data elements within the hybrid trie and for storing at least some of the nodes in stripes across a sequence of the memories. Memory management is performed for the leaf-search nodes, by selecting stripes from the possible subsequences of those memories, that are suited to pipelined operations performed on the memories. In a preferred embodiment, an invariant condition is maintained for families of those stripes, in which exactly one cell block is labeled "sparse" and that cell block is used in techniques for allocation and de-allocation of entries.
|
