A method for updating table entries of a Ternary Content Addressable Memory (TCAM), comprising:
- creating a virtual TCAM list, of which respective first TCAM table entries are one-to-one corresponding to respective second TCAM table entries stored in a hardware TCAM;
- determining, in idle resources of the hardware TCAM, a storage position of a second TCAM table entry to be updated corresponding to a first TCAM table entry to be updated, according to a pre-specified precedence relationship between the storage positions of the first TCAM table entry to be updated and other first TCAM table entry in the virtual TCAM list;
- and
- performing an updating operation on the second TCAM table entry to be updated in the hardware TCAM, according to the determined storage position,
- wherein the step of creating the virtual TCAM list comprises:
- creating a link list as the virtual TCAM list;
- and
- arranging first TCAM table entries in the link list in a pre-specified order, and making them be one-to-one corresponding to the respective second TCAM table entries stored in the hardware TCAM;
- wherein each of the first TCAM table entries comprises a data content of a second TCAM table entry corresponding to the first TCAM table entry, a storage position of the second TCAM table entry corresponding to the first TCAM table entry in the hardware TCAM, minimum and maximum storage positions for the second TCAM table entry corresponding to the first TCAM table entry to be freely movable in the hardware TCAM, and a list of previous table entries to the first TCAM table entry, which is called as Prelist and a list of posterior table entries to the first TCAM table entry, which is called as Poslist,
- and wherein when the updating operation is to add a second TCAM table entry, determining, in the idle resources of the hardware TCAM, the storage position of the second TCAM table entry to be updated comprises:
- in the virtual TCAM list, determining a storage position of a first TCAM table entry before a first TCAM table entry to be added corresponding to a pre-specified second TCAM table entry to be added;
- inserting the first TCAM table entry to be added after the determined storage position, and recording the data content of the second TCAM table entry to be added in the first TCAM table entry to be added;
- determining other first TCAM table entries related to the first TCAM table entry to be added, according to the recorded data content and data content of other first TCAM table entries in the first TCAM list;
- determining all first TCAM table entries, which are arranged before the first TCAM table entry to be added and related thereto in the virtual TCAM list, as table entries in the Prelist thereof;
- determining all first TCAM table entries, which are arranged after the first TCAM table entry to be added and related thereto in the virtual TCAM list, as table entries in the Poslist thereof;
- incrementing a storage position in the hardware TCAM of a second TCAM table entry corresponding to a backmost first TCAM table entry in the Prelist by 1, and taking this storage position as the minimum storage position for the second TCAM table entry to be added to be freely movable in the hardware TCAM;
- decrementing a storage position in the hardware TCAM of a second TCAM table entry corresponding to a headmost first TCAM table entry in the Poslist by 1, and taking this storage position as the maximum storage position for the second TCAM table entry to be added to be freely movable in the hardware TCAM;
- determining a storage position of the second TCAM table entry to be added in the idle resources of the hardware TCAM, according to the minimum and maximum storage positions.