Techniques for efficient memory management that enable rapid longest prefix match lookups in memory. In general, the present invention is efficacious wherever maintenance of a good distribution of holes in a sorted list is required. This technique relies on a proactive hole management methodology to preserve a good distribution of holes in each memory region in such a way that one does not have to search for holes in order to insert or store a new entry into the list. In particular, all holes in a given region are kept in one or more contiguous sub-region. Keeping the holes contiguous requires a hole move every time there is a delete operation. The amortized cost of these operations is justified by the resulting simplification in later insert (store) and delete operations. For example, during an insert the new entry is placed at the end of the contiguous sub-region of used entries in the region. During a delete, when a hole is created in the middle of a contiguous sub-region of used entries, the last used entry is moved into the hole, thus keeping the holes contiguous. Such an organization of holes and movement of used entries within a region is permissible within the longest prefix match type of lookup table, because all entries within a region, by definition, have an IP prefix of equal length.
展开▼
