What is the fastest collection in c# to implement a prioritizing queue?
- by Nathan Smith
I need to implement a queue for messages on a game server so it needs to as fast as possible.
The queue will have a maxiumem size.
I need to prioritize messages once the queue is full by working backwards and removing a lower priority message (if one exists) before adding the new message.
The appliation is asynchronous so access to the queue needs to be locked.
I'm currently implementing it using a LinkedList as the underlying storage but have concerns that searching and removing nodes will keep it locked for too long.
Heres the basic code I have at the moment:
public class ActionQueue
{
private LinkedList<ClientAction> _actions = new LinkedList<ClientAction>();
private int _maxSize;
/// <summary>
/// Initializes a new instance of the ActionQueue class.
/// </summary>
public ActionQueue(int maxSize)
{
_maxSize = maxSize;
}
public int Count
{
get { return _actions.Count; }
}
public void Enqueue(ClientAction action)
{
lock (_actions)
{
if (Count < _maxSize)
_actions.AddLast(action);
else
{
LinkedListNode<ClientAction> node = _actions.Last;
while (node != null)
{
if (node.Value.Priority < action.Priority)
{
_actions.Remove(node);
_actions.AddLast(action);
break;
}
}
}
}
}
public ClientAction Dequeue()
{
ClientAction action = null;
lock (_actions)
{
action = _actions.First.Value;
_actions.RemoveFirst();
}
return action;
}
}