| 摘要 |
Techniques for the efficient location of free entries for use in performing insert operations in a binary or ternary content addressable memory. As used in data communications and packet routing, such memories often rely on an organization that maintains entries of the same "length" within defined regions. The present invention keeps the free entries (holes) compacted into a contiguous subregion within each region, without requiring hole movement during deletes. These positive effects are accomplished by initially pre-filling the entire memory with a set of hole codes that each uniquely identify the holes in each region. A conventional memory write is then performed to load routing data into the memory. Typically, such routing information will not fill the entire memory, leaving unused entries (containing the region appropriate hole code) in each region. As entries need to be deleted, they are simply replaced by writing in the region-unique hole code. To insert an entry, the host processor searches for the desired region-unique hole and writes the data to its location. In instances where a region has no available holes, a mechanism is presented to move a hole from a nearby region.
|
