Patent ID: 6473846
Filing Date: 2002-10-29
Classification: G06F,G11C,Y10S

Abstract:
A method of storing a plurality of data records in a memory structure, wherein each data record has a key and a related association, the method comprising: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 wherein the configuring comprises partitioning the content addressable memory table into a plurality of table records each having a table key; initializing the content addressable memory table, the initializing comprising: 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; 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, the adding comprising: 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.