Patent ID: 7644085
Filing Date: 2010-01-05
Classification: G06F,H04L

Abstract:
1. A method of generating a representation of an access control list, the method comprising the steps of: determining a plurality of rules of the access control list, each of at least a subset of the rules having a plurality of fields and a corresponding action; and processing the rules to generate a multi-level tree representation of the access control list, each of one or more of the levels of the tree representation being associated with a corresponding one of the fields; wherein the determining and processing steps are implemented in a processor and at least a portion of the multi-level tree representation is stored under control of the processor in memory circuitry associated with the processor; wherein at least one level of the tree representation comprises a plurality of nodes, with two or more of the nodes of that level having a common subtree, the tree representation including only a single copy of that subtree, the subtree comprising at least one node that is not a leaf node of the tree representation; the tree representation being characterizable as a directed graph in which each of the two nodes having the common subtree points to the single copy of the common subtree; wherein for at least a given level of the tree representation that corresponds to a field of a rule of the access control list, a master list of nodes is maintained, at least a given such node comprising information characterizing one or more field values associated with that node, one or more subtree pointers for that node, and a reference count indicating how many ancestor nodes are pointing to that node; wherein the tree representation is generated by sequentially processing the rules of the access control list, the processing for a given rule comprising applying values of fields of the given rule to one or more existing nodes of the tree representation, and wherein when a particular value of a field of the given rule is applied to a given node, a copy is made of the node, the field value is applied to the copied node, and the resultant updated node is added to the master list of the corresponding level; and wherein the updated node is compared with other nodes of the master list and if a duplicate node is found, the copied node is deleted and a pointer to the duplicate node is provided to an ancestor node that points to the given node, a subtree pointer of the ancestor node is updated to the duplicate node pointer, a reference count of the duplicate node now pointed to by the ancestor node is incremented and a reference count of the given node previously pointed to by the ancestor node is decremented.