Granted Patent B1

US 8,762,362 · App. 13/278,701 · Granted Jun 24, 2014

Abstract

Claims (67)

1. A method for updating a data structure, comprising:

providing a data structure, wherein the data structure comprises a hierarchically arranged set of nodes and branches, and each node has two or less branches;

retrieving a first data entry in the data structure via a first node in response to a first data access request;

modifying the data structure to generate a first intermediate data structure that keeps the first node and creates a duplicate of the first node, wherein the first intermediate data structure comprises the first node and the duplicate of the first node;

retrieving a second data entry in the data structure via the duplicate of the first node in response to a second data access request;

retrieving a third data entry in the data structure via a second node in response to a third data access request; and

modifying the first intermediate data structure to generate a second intermediate data structure that creates a duplicate of the second node and removes the first node by replacing the first node with the duplicate of the second node.

2. The method of claim 1 further comprises:

retrieving a fourth data entry in the data structure via the duplicate of the second node in response to a fourth data access request.

3. The method of claim 2 further comprises:

modifying the second intermediate data structure to generate an updated data structure, wherein the updated data structure removes the second node and balances the data structure with respect to the duplicate of the second node; and

storing the updated data structure in a memory.

4. The method of claim 1 , wherein modifying the data structure comprises:

traversing up the data structure from a leaf node that exceeded a predetermined allowable accesses; and

examining each node to determine the first node to be duplicated.

5. The method of claim 2 , wherein modifying the first intermediate data structure comprises:

identifying a second node to replace the first node.

6. The method of claim 5 , wherein the second node has a next higher value compared to value of the first node of the data structure if a number of levels to the right of the first node is more than a number of levels to the left of the first node.

7. The method of claim 5 , wherein the second node has a next lower value compared to value of the first node of the data structure if a number of levels to the left of the first node is more than a number of levels to the right of the first node.

8. A computer program product for updating a data structure, comprising a non-transitory medium storing computer programs for execution by one or more computer systems, comprising:

code for providing a data structure, wherein the data structure comprises a hierarchically arranged set of nodes and branches, and each node has two or less branches;

code for retrieving a first data entry in the data structure via a first node in response to a first data access request;

code for modifying the data structure to generate a first intermediate data structure that keeps the first node and creates a duplicate of the first node, wherein the first intermediate data structure comprises the first node and the duplicate of the first node;

code for retrieving a second data entry in the data structure via the duplicate of the first node in response to a second data access request;

code for retrieving a third data entry in the data structure via a second node in response to a third data access request; and

code for modifying the first intermediate data structure to generate a second intermediate data structure that creates a duplicate of the second node and removes the first node by replacing the first node with the duplicate of the second node.

9. The computer program product of claim 8 further comprises:

code for retrieving a fourth data entry in the data structure via the duplicate of the second node in response to a fourth data access request.

10. The computer program product of claim 9 further comprises:

code for modifying the second intermediate data structure to generate an updated data structure, wherein the updated data structure removes the second node and balances the data structure with respect to the duplicate of the second node; and

code for storing the updated data structure in a memory.

11. The computer program product of claim 8 , wherein modifying the data structure comprises:

code for traversing up the data structure from a leaf node that exceeded a predetermined allowable accesses; and

code for examining each node to determine the first node to be duplicated.

12. The computer program product of claim 9 , wherein modifying the first intermediate data structure comprises:

code for identifying a second node to replace the first node.

13. The computer program product of claim 12 , wherein the second node has a next higher value compared to value of the first node of the data structure if a number of levels to the right of the first node is more than a number of levels to the left of the first node.

14. The computer program product of claim 12 , wherein the second node has a next lower value compared to value of the first node of the data structure if a number of levels to the left of the first node is more than a number of levels to the right of the first node.

15. A system for updating a data structure, comprising:

a memory for storing the data structure, wherein the data structure comprises a hierarchically arranged set of nodes and branches, and each node has two or less branches;

a graphical-user-interface for viewing representations of the data structure on a display;

a search engine includes at least a processor and control logic, wherein the processor and control logic further comprises

logic for retrieving a first data entry in the data structure via a first node in response to a first data access request;

logic for modifying the data structure to generate a first intermediate data structure that keeps the first node and creates a duplicate of the first node, wherein the first intermediate data structure comprise the first node and the duplicate of the first node;

logic for retrieving a second data entry in the data structure via the duplicate of the first node in response to a second data access request;

logic for retrieving a third data entry in the data structure via a second node in response to a third data access request; and

logic for modifying the first intermediate data structure to generate a second intermediate data structure that creates a duplicate of the second node and removes the first node by replacing the first node with the duplicate of the second node.

16. The system of claim 15 further comprises:

logic for retrieving a fourth data entry in the data structure via the duplicate of the second node in response to a fourth data access request.

17. The system of claim 16 further comprises:

logic for modifying the second intermediate data structure to generate an updated data structure, wherein the updated data structure removes the second node and balances the data structure with respect to the duplicate of the second node; and

logic for storing the updated data structure in a memory.

18. The system of claim 15 , wherein modifying the data structure comprises:

logic for traversing up the data structure from a leaf node that exceeded a predetermined allowable accesses; and

logic for examining each node to determine the first node to be duplicated.

19. The system of claim 16 , wherein modifying the first intermediate data structure comprises:

logic for identifying a second node to replace the first node.

20. The system of claim 19 , wherein the second node has a next higher value compared to value of the first node of the data structure if a number of levels to the right of the first node is more than a number of levels to the left of the first node.

21. The system of claim 19 , wherein the second node has a next lower value compared to value of the first node of the data structure if a number of levels to the left of the first node is more than a number of levels to the right of the first node.

22. The system of claim 15 further comprises:

one or more parsers coupled to a parser RAM, wherein the one or more parsers are configured to read an incoming data stream and compares contents of the incoming data stream with contents in a location of the parser RAM;

one or more access control list (ACL) search engines coupled to an ACL RAM, wherein the one or more ACL search engines are configured to perform searches with ACL search strings; and

one or more search engines coupled to an exact match RAM, wherein the one or more search engines are configured to maintain the data structure.

23. The system of claim 22 further comprises:

an exchange module coupled to the exact match RAM and an external memory, wherein the exchange module is configured to control entries of the data structure between the exact match RAM and the external memory;

one or more hash functions configured to generate hash values of data entries in the data structure; and

a bloom filter coupled to the one or more hash functions, wherein the bloom filter is configured to determine whether a data entry exists in the data structure.

Assignments (6)