5
\$\begingroup\$

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 a user can perform (1 = read, 2 = write, etc).

So given user role "3", you know you can perform action "1", "2" and "3".

The problem: Users in 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 gets used a LOT, so I have to create a solution that works quick and efficiently.

My solution: create an unbalanced search tree and navigate through it to get the correct security level for a set of permissions.

Overview: 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: enter image description here

Then given an array [ "6", "8", "10", "11" ], create a function that returns "3", or "-1" if no corresponding level was found. The search tree is cached, so creating it does not have to be very efficient. Searching it however should be quick. My code:

 Public class TreeSearcher
 {
private static Dictionary<string, SearchTree> documentSearchTrees = new Dictionary<string, SearchTree>();

/// <summary>
/// Create a search tree for a document type's different rights levels. 
/// </summary>
/// <param name="documentType">The documenttype</param>
/// <param name="documentRights">A tuple holding an int (rights level), and a string[] (the rights)</param>
public static void CreateSearchTree(string documentType, params Tuple<int, string[]>[] documentRights)
{
    if (string.IsNullOrEmpty(documentType))
        throw new ArgumentNullException(nameof(documentType), $"{nameof(documentType)} can not be null.");

    if (documentRights?.Length == 0)
        throw new ArgumentNullException(nameof(documentRights), $"{nameof(documentRights)} can not be null or empty.");

    // Only insert rights if they haven't been inserted before. 
    // Use the DeleteSearchTree(documentType) method to explicitly remove document rights. 
    if (documentSearchTrees.ContainsKey(documentType) == false)
    {
        SearchTree searchTree = new SearchTree();
        foreach (var rights in documentRights)
        {
            searchTree.AddNode(rights.Item1, rights.Item2);
        }

        documentSearchTrees.Add(documentType, searchTree);

    }
}

/// <summary>
/// Returns the level of a passed in array of user rights.
/// </summary>
/// <param name="documentType">The type of document to compare the user rights for.</param>
/// <param name="userRights">The rights of the user.</param>
/// <returns>The authorization level for the user, or -1 if none was found.</returns>
public static int GetAuthorizationLevel(string documentType, string[] userRights)
{
    Array.Sort(userRights);

    if (documentSearchTrees.TryGetValue(documentType, out var searchTree) == true)
    {
        return searchTree.GetAuthorizationLevel(userRights);
    }
    else
    {
        return -1;
    }
}

/// <summary>
/// Delete a document type's searchTree. 
/// </summary>
/// <param name="documentType"></param>
public static void DeleteSearchTree(string documentType)
{
    if (string.IsNullOrEmpty(documentType))
        throw new ArgumentNullException(nameof(documentType), $"{nameof(documentType)} can not be null.");

    documentSearchTrees.Remove(documentType);
}


/// <summary>
/// The entire search tree.
/// </summary>
private class SearchTree
{
    private Dictionary<string, TreeNode> Nodes = new Dictionary<string, TreeNode>();

    internal void AddNode(int authorizationLevel, string[] rights)
    {
        // We need the rights to be sorted, 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(authorizationLevel, rights.Skip(1).ToArray());
            Nodes.Add(rights[0].ToString(), nodeToAdd);
        }
        else
        {
            nodeToAdd.AddNode(authorizationLevel, rights.Skip(1).ToArray(), new TreeNode(authorizationLevel, rights.Skip(1).ToArray()));
        }
    }

    internal int GetAuthorizationLevel(string[] userRights)
    {
        int arrayStartPosition = 0;
        if (Nodes.TryGetValue(userRights[arrayStartPosition], out var treeNode) == true)
        {
            return treeNode.GetAuthorizationLevel(userRights, arrayStartPosition + 1);
        }
        else
        {
            return -1;
        }
    }
}

/// <summary>
/// A single node with all sub-nodes of the tree. 
/// </summary>
private class TreeNode
{
    private Dictionary<string, TreeNode> Nodes = new Dictionary<string, TreeNode>();
    internal int AuthorizationLevel { get; set; }

    internal TreeNode(int authorizationLevel, string[] rights)
    {
        if (rights.Length <= 0)
        {
            AuthorizationLevel = authorizationLevel;
            return;
        }

        if (Nodes.TryGetValue(rights[0].ToString(), out TreeNode existingNode) == false)
        {
            if (rights.Length == 1)
                AuthorizationLevel = authorizationLevel;

            existingNode = new TreeNode(authorizationLevel, rights.Skip(1).ToArray());
            Nodes.Add(rights[0].ToString(), existingNode);
        }
        else
        {
            existingNode.AddNode(authorizationLevel, rights, new TreeNode(authorizationLevel, rights.ToArray()));
        }
    }

    internal void AddNode(int authorizationLevel, string[] rights, TreeNode treeNode)
    {
        if (rights.Length <= 0)
        {
            return;
        }
        if (rights.Length == 1)
        {
            treeNode.AuthorizationLevel = authorizationLevel;
        }

        if (Nodes.TryGetValue(rights[0].ToString(), out TreeNode existingNode) == false)
        {
            Nodes.Add(rights[0].ToString(), treeNode);
        }
        else
        {
            existingNode.AddNode(authorizationLevel, rights.Skip(1).ToArray(), treeNode);
        }
    }

    internal int GetAuthorizationLevel(string[] userRights, int offset)
    {
        if (userRights.Length == offset)
            return AuthorizationLevel;

        if (Nodes.TryGetValue(userRights[offset], out var treeNode) == true)
        {
            return treeNode.GetAuthorizationLevel(userRights, offset + 1);
        }
        else
        {
            return -1;
        }
    }
}
}

Adding permissions per resource type works like this:

    var list = new List<Tuple<int, string[]>>
    {
        new Tuple<int, string[]>(1, new string[] { "1", "2", "3", "4" }),
        new Tuple<int, string[]>(2, new string[] { "1", "2", "3", "5" }),
        new Tuple<int, string[]>(3, new string[] { "6", "8", "10", "11" }),
        new Tuple<int, string[]>(4, new string[] { "1", "8", "11", "12" }),
        new Tuple<int, string[]>(5, new string[] { "1", }),
        new Tuple<int, string[]>(6, new string[] { "1", "2" }),
        new Tuple<int, string[]>(7, new string[] { "30", "28", "123" }),
    };

    CreateSearchTree("aCoolResource", list.ToArray());

Finding a user permission goes 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 intended. What I'm mostly looking for is tips on how to improve performance. However, all other tips are welcome as well. You can also download the source here:

https://gofile.io/?c=wwwNwv

NOTE: Because the trees store strings, they’re ordered as such. So 1, 2 and 10 is ordered as 1, 10 and 2. It works fine this way for me, but there may be edge cases I missed.

\$\endgroup\$
  • \$\begingroup\$ We could provide a better review if the entire class(s) was included. \$\endgroup\$ – pacmaninbw Jul 21 '19 at 16:20
  • \$\begingroup\$ @pacmaninbw I did one better and added some source code. Link is at the bottom of the post. \$\endgroup\$ – yesman Jul 21 '19 at 18:04
  • \$\begingroup\$ Roughly how many roles and actions per role do you need to handle? Also, can you use integers instead of strings for action IDs? \$\endgroup\$ – Pieter Witvoet Jul 22 '19 at 11:16
  • \$\begingroup\$ There are about 10 roles per search tree, with about 40 possible actions per role. All combinations of roles and actions are possible as far as I know, so role 1 can have just 1 action, while role 2 has 40 actions. \$\endgroup\$ – yesman Jul 22 '19 at 11:35
  • \$\begingroup\$ And are those action IDs always numeric, or do they have to be strings? \$\endgroup\$ – Pieter Witvoet Jul 22 '19 at 11:58
3
\$\begingroup\$

First of all, it's good to see the public interface being documented.

There are however some problems:

  • CreateSearchTree is broken. When registering level 1 with ["1", "2", "3"], it marks both the "2" and "3" node as level 1. And when registering level 2 with ["1", "2"], the "2" node is not updated to level 2. This causes various lookup failures, depending on the order in which rights were registered.
  • In some cases you're returning 0 instead of -1. That's because TreeNode.AuthorizationLevel's default value is 0, and you're not explicitly initializing it to -1.

Other things that could be improved:

  • In CreateSearchTree, you could use value tuples instead of the old Tuple class.
  • == false and == true are only necessary when you're working with nullable booleans, which is not the case here.
  • You don't need to call ToString() on a string.
  • Array.Sort modifies its input, which means that GetAuthorizationLevel is modifying the userRights array. That's an unexpected side-effect that could cause trouble elsewhere.
  • There's a fair bit of code duplication between SearchTree and TreeNode. You can simplify SearchTree by giving it a single root node to which it can delegate its calls.

Regarding performance, using integer action IDs instead of strings would make this quite a bit faster - even with integer parsing overhead.

But with the number of actions being limited to about 40, a dictionary with a ulong as key (with each bit indicating the presence of a specific action ID) would be even faster. If the IDs are all within the 0-63 range, then the key can be generated with one binary-or and bit-shift operation per action ID. Otherwise, you'll need a lookup table that maps action IDs to bit-masks (which would work for integer as well as string IDs). Even with this lookup table, it's still several times faster than the tree-based approach, mostly because you can skip the expensive input-sorting operation.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks, I can really use this advice. I'm trying to understand your comment on a lookup table though. For that, do you mean something like mapping all user actions to an enum with the [Flag] attribute, converting any set of user actions to an enum, and using the result ulong as a key for a <ulong, int> dictionary? \$\endgroup\$ – yesman Jul 22 '19 at 13:03
  • 1
    \$\begingroup\$ You don't need an enum for that: registering an action (during initialization) can be done like actionMasks[actionID] = 1ul << actionMasks.Count;. A [Flags] enum allows you to give descriptive names to these bit-masks, but that's not very useful in this case. \$\endgroup\$ – Pieter Witvoet Jul 22 '19 at 13:31
  • \$\begingroup\$ Ahhhhhh, excellent! Thanks. Sadly, I doubt my team will understand bitwise operators, so I have to do some explaining first, as I don't want to check in code that only I understand. \$\endgroup\$ – yesman Jul 22 '19 at 13:35
  • \$\begingroup\$ I also had to withdraw some bitwise operations once, because the team rather used an array of booleans. It's not a good feeling if you know you have a good solution that nobody understands :) \$\endgroup\$ – dfhwze Jul 22 '19 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.