RANGE CONTENT-ADDRESSABLE MEMORY

摘要

Method and apparatus for arranging and storing in a memory associative key data set of associative elements and a corresponding associated data set of associated elements, wherein each associative element corresponds to a range of consecutive values, such that an associated element may be extracted from the memory as valid data if an associative key belongs to its associative element, the range being represented by its lower and upper extreme values. A memory device(s) is provided for storing the associative key data set and the associated data set that comprises first and second storage areas, so that to each storage location in the first storage area there is a corresponding storage location in the second storage area. The associative elements of the key association data set and their corresponding associated data set are arranged in an order determined by priority precedence, such that associative elements having higher priority are placed before associative elements having lower priority. A unique index is assigned for each associative element for representing its ordered location. At least one of the extreme values of each associative element is stored in the first storage area in a location that corresponds to the priority of the associative element. Each value of the associated data set is stored in a location in the second storage area that corresponds to the location of the associative element to which it is associated. Associated data values are extracted from the memory upon conducting a key search on the associative key data. Upon receiving an input key, one or more associative elements that may contain the input key are sought, and if no such associative element(s) is found, a mismatch signal is output to indicate that the associated data that is output is invalid. If the input key is contained in one or more associative element(s), the associated data that corresponds to the associative element having the highest priority that contains the input key and a match signal indicating that the associated data that is being output is valid, are output.