I have a system that stores resources. A resource contains a string that represents a user role, for example, "3".
With this user role "3", you can retrieve a list of permissions for the user role, for example [“1”, “2”, “3”]. This list represents actions that a user can perform (1 = read, 2 = write, etc.).
Then, given the user role "3", you know that you can perform the action "1", "2" and "3".
The problem: the users of my system do not directly store a security level number. They only store the actions they are allowed to perform. Given a set of allowed actions, I need to find the correct user role. This part of the code is used a lot, so I have to create a solution that works quickly and efficiently.
My solution: create an unbalanced search tree and navigate through it to get the right level of security for a set of permissions.
Summary: for three sets of permissions:
- [ “1”, “2”, “3”, “4” ] level 1
- [ “1”, “2”, “3”, “5” ] Level 2
- [“6”, “8”, “10”, “11” ] level 3
- [ “2”, “1” ] level 4
Create a tree that looks like this:
Then a matrix is given [ “6”, “8”, “10”, “11” ], create a function that returns "3", or "-1" if the corresponding level was not found. The search tree is cached, so creating it does not have to be very efficient. However, looking for it should be quick. My code:
Public class TreeSearcher
{
Static private dictionary documentSearchTrees = new dictionary();
///
/// Create a search tree for the different levels of rights of a document type.
///
/// The type of document (arbeidsrecht, cao, etc.)
/// A tuple that contains an int (rights level) and a string[] (rights)
public static empty CreateSearchTree (string documentType, params Tuple[] documentRights)
{
if (string.IsNullOrEmpty (documentType))
throw the new exception ArgumentNullException (nameof (documentType), $ "{nameof (documentType)} can not be null.");
if (documentRights? .Length == 0)
throw the new exception ArgumentNullException (nameof (documentRights), $ "{nameof (documentRights)} can not be null or empty.");
// Only insert rights if they have not been inserted before.
// Use the DeleteSearchTree (documentType) method to explicitly remove the rights from the document.
if (documentSearchTrees.ContainsKey (documentType) == false)
{
SearchTree searchTree = new SearchTree ();
foreach (rights of var in documentRights)
{
searchTree.AddNode (rights.Item1, rights.Item2);
}
documentSearchTrees.Add (documentType, searchTree);
}
}
///
/// Returns the level of a pass in the user rights matrix.
///
/// The type of document to compare user rights for.
/// The rights of the user.
/// The authorization level for the user, or -1 if none was found.
public static int GetAuthorizationLevel (string documentType, string[] user rights)
{
Array.Sort (userRights);
if (documentSearchTrees.TryGetValue (documentType, out var searchTree) == true)
{
returns searchTree.GetAuthorizationLevel (userRights);
}
plus
{
returns -1;
}
}
///
/// Delete the search tree of a document type.
///
///
public static void DeleteSearchTree (string documentType)
{
if (string.IsNullOrEmpty (documentType))
throw the new exception ArgumentNullException (nameof (documentType), $ "{nameof (documentType)} can not be null.");
documentSearchTrees.Remove (documentType);
}
///
/// The entire search tree.
///
private class SearchTree
{
Private dictionary Nodes = new dictionary();
Empty internal AddNode (int permissionLevel, string[] rights)
{
// We need the rights to be ordered, otherwise the tree will not work.
Array.Sort (rights);
// Add the nodes recursively.
if (Nodes.TryGetValue (rights[0].ToString (), out TreeNode nodeToAdd) == false)
{
nodeToAdd = new TreeNode (authorityLevel, rights.Skip (1) .ToArray ());
Nodes.Add (rights[0].ToString (), nodeToAdd);
}
plus
{
nodeToAdd.AddNode (authorityLevel, rights.Skip (1) .ToArray (), new TreeNode (authorityLevel, rights.Skip (1) .ToArray ()));
}
}
internal int GetAuthorizationLevel (string[] user rights)
{
int arrayStartPosition = 0;
if (Nodes.TryGetValue (userRights[arrayStartPosition], out var treeNode) == true)
{
returns treeNode.GetAuthorizationLevel (userRights, arrayStartPosition + 1);
}
plus
{
returns -1;
}
}
}
///
/// A single node with all the subnodes of the tree.
///
TreeNode private class
{
Private dictionary Nodes = new dictionary();
internal int AuthorizationLevel {obtain; set; }
Internal TreeNode (int permissionLevel, string[] rights)
{
if (rights.Length <= 0)
{
AuthorizationLevel = permissionLevel;
he came back;
}
if (Nodes.TryGetValue (rights[0].ToString (), out TreeNode existingNode) == false)
{
if (rights.Length == 1)
AuthorizationLevel = permissionLevel;
existingNode = new TreeNode (authorityLevel, rights.Skip (1) .ToArray ());
Nodes.Add (rights[0].ToString (), existingNode);
}
plus
{
existingNode.AddNode (permissionLevel, rights, new TreeNode (permissionLevel, rights.ToArray ()));
}
}
Empty internal AddNode (int permissionLevel, string[] rights, TreeNode treeNode)
{
if (rights.Length <= 0)
{
he came back;
}
if (rights.Length == 1)
{
treeNode.AuthorizationLevel = permissionLevel;
}
if (Nodes.TryGetValue (rights[0].ToString (), out TreeNode existingNode) == false)
{
Nodes.Add (rights[0].ToString (), treeNode);
}
plus
{
existingNode.AddNode (authorityLevel, rights.Skip (1) .ToArray (), treeNode);
}
}
internal int GetAuthorizationLevel (string[] userRights, int offset)
{
if (userRights.Length == offset)
back AuthorizationLevel;
if (Nodes.TryGetValue (userRights[offset], out var treeNode) == true)
{
returns treeNode.GetAuthorizationLevel (userRights, offset + 1);
}
plus
{
returns -1;
}
}
}
}
Adding permissions by resource type works like this:
var list = new List <Tuple>
{
new tuple(1, new chain[] {"1", "2", "3", "4"}),
new tuple(2, new chain[] {"1", "2", "3", "5"}),
new tuple(3, new chain[] {"6", "8", "10", "11"}),
new tuple(4, new chain[] {"1", "8", "11", "12"}),
new tuple(5, new chain[] {"one",}),
new tuple(6, new rope[] {"1", "2"}),
new tuple(7, new rope[] {"30", "28", "123"}),
};
CreateSearchTree ("aCoolResource", list.ToArray ());
Finding a user permission is like this:
var userRights1 = new string[] {"1", "2", "3", "5"};
var userRights2 = new string[] {"123", "30", "28"};
int userLevel1 = AuthorizationHelper.GetAuthorizationLevel ("aCoolResource", userRights1);
int userLevel2 = AuthorizationHelper.GetAuthorizationLevel ("aCoolResource", userRights2);
This works as planned. What I look for most are tips on how to improve performance.
