一种三态内容可寻址存储器TCAM的寻址方法及装置

摘要

一种三态内容可寻址存储器TCAM的寻址方法及装置，首先，将三态可寻址存储器TCAM空间中的块通过空闲块链进行连接；然后，当数据库申请块时，将所述空闲块链中的至少一部分块与所述数据库绑定。本发明实施例将TCAM空间中的块通过空闲链连接，并动态的分配相应的数据库，能够最大化的利用TCAM空间，节省了功耗，并且根据位置树也能方便快捷的找到TCAM中的块。

主权项

一种三态内容可寻址存储器TCAM的寻址方法，其特征在于，包括：将三态可寻址存储器TCAM空间中的块通过空闲块链进行连接；当数据库申请块时，将所述空闲块链中的至少一部分块与所述数据库绑定；根据所述与数据库绑定的块中的表项尺寸将所述与数据库绑定的块增加到未满的在用块树中，将所述与数据库绑定的块的地址信息增加到相应的位置树中，所述在用块树用于表示正在使用的块的信息，所述位置树用于表示在用块树中所述块的地址信息；根据在用块树中所述块中的表项尺寸对位置树中的节点进行着色，具体包括：将在用块树中所述块中的表项尺寸小于等于预定值M1对应位置树中的节点着色A1、将在用块树中所述块中的表项尺寸大于预定值M1且小于等于预定值M2对应位置树中的节点着色A2以及将在用块树中所述块中的表项尺寸大于预定值M2且小于等于预定值M对应位置树中的节点着色A3，其中预定值M1小于预定值M2且都小于预定值M，所述预定值M为块的大小，所述A1、A2和A3为不同的颜色，用于区别在用块树中所述块中的表项尺寸；所述数据库申请块，但空闲块链上没有块时，将一个着色A1的节点对应块中的表项搬移到其它着色A1的节点对应块中，或将一个着色A1的节点对应块中的表项搬移到一个或多个着色A3的节点对应块中，使存在空闲块；或者，所述数据库申请块，但空闲块链上没有块时，将一个着色A2的节点对应块中的表项搬移到一个或多个着色A2的节点对应块中，或将一个着色A2的节点对应块中的表项搬移到多个着色A3的节点对应块中，使存在空闲块；或者，当在用块树中所述块中的表项被删除时，将一个着色A1的节点对应块中的表项搬移到一个着色A2的节点对应块中，以减少碎片。