Content addressable memory (CAM) engine

A memory controller comprising an integrated circuit including a means for storing a plurality of data records in a memory structure, wherein each data record has a key and a related association, the means for storing comprising:

• means for configuring a content addressable memory table in a random access memory device, wherein the content addressable memory table comprises storage for the plurality of keys and associations, and the configuring comprises partitioning the content addressable memory table into a plurality of table records, each having a table key;
• means for initializing the content addressable memory table, wherein the initializing comprises:
• storing a first initialization value in the table key of the first table record;
• and
• storing a second initialization value in the table keys of all subsequent table records;
• means for adding a plurality of data records to the content addressable memory table such that the data records are maintained in order according to hash values of the keys of the data records, wherein the adding comprises:
• calculating a hash value by applying a hash algorithm to the key of the data record to be stored;
• and
• if the table key at the location in the content addressable memory table which corresponds to the hash value contains the second initialization value, writing the data record into that location;
• otherwise:
• calculating a re-hash value by applying a hash algorithm to the key of the stored record at the location in the content addressable memory table which corresponds to the hash value;
• comparing the re-hash value with the hash value;
• and
• if the re-hash value is greater than the hash value,
• pushing down any stored records between the next sequential table record with the second initialization value in its table key and the stored record with a table key which would hash to a value greater than the hash value, wherein said pushing down continues until said next sequential table record with the second initialization value in the table key is overwritten, and
• writing the data record into the table record at the location opened by pushing down the stored records,
• otherwise:
• reading the next sequential table record;
• repeating the calculating a re-hash value, comparing the rehash value, and pushing down the stored records until the re-hash value is less than or equal to the hash;
• and
• writing the data record into the table record at the location opened by pushing down the stored records.

A method of storing a plurality of data records in a memory structure, wherein each data record has a key, the method comprising:

• configuring a table in a random access memory device, wherein the table comprises storage for the plurality of keys, and wherein the configuring comprises partitioning the table into a plurality of table records each having a table key;
• storing an initialization value in the table keys of a plurality of table records;
• adding a plurality of data records to the table such that the data records are maintained in order according to hash values of the keys, the adding comprising:
• calculating a hash value by applying a hash algorithm to the key of the data record to be stored;
• and
• writing the data record into that location if the table key at the location in a content addressable memory table which corresponds to the hash value contains the initialization value.