Patent ID: 6467019
Filing Date: 2002-10-15
Classification: G06F

Abstract:
In a content addressable memory (CAM) that can receive an input query and provide a match indication between an input query and stored rules, the CAM including a plurality of storage locations that can each store a rule that includes maskable matching criteria, the storage locations having an order that can establish priority among multiple rules, a method of adding new rules to the CAM, comprising the steps of:determining if a new rule, having a predetermined priority with respect to the stored rules, overlaps any stored rule, wherein a new rule overlaps a stored rule if a query exists that matches the new rule and the stored rule; if a new rule overlaps a rule in a group of overlapping stored rules, determining a closest lower priority rule that is the rule in the overlapping group that has the closest lower priority with respect to the new rule priority, determining a closest higher priority rule that is the rule in the overlapping group that has the closest higher priority with respect to the new rule priority, if an empty location exists between the locations of the closest lower priority rule and the closest higher priority rule, writing the new rule into the empty location, and if no empty location exists between the location of the closest lower priority rule and the closest higher priority rule, selecting a new group of locations from all current empty locations and all locations of the overlapping group, the new group of locations including a location corresponding to each rule of the overlapping group and the new rule, and writing the group of overlapping rules and the new rule into the new group of locations in order of priority.