Created
March 21, 2017 01:12
-
-
Save llint/a58de34f6e445a58ba794be74324da7b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| using System; | |
| using System.Collections.Generic; | |
| namespace PortsManager | |
| { | |
| class PortsManager | |
| { | |
| int count = 0; | |
| readonly (int minPort, int maxPort) range; | |
| LinkedList<(int minPort, int maxPort)> ranges = new LinkedList<(int, int)>(); | |
| internal PortsManager(int minPort, int maxPort) | |
| { | |
| count = maxPort - minPort + 1; | |
| range = (minPort, maxPort); | |
| ranges.AddLast(range); | |
| } | |
| internal int Count { get => count; } | |
| internal bool IsPortAvailable(int port) | |
| { | |
| if (port < range.minPort || port > range.maxPort) | |
| { | |
| return false; | |
| } | |
| for (var node = ranges.First; node != null; node = node.Next) | |
| { | |
| var range = node.Value; | |
| if (port >= range.minPort && port <= range.maxPort) | |
| { | |
| return true; | |
| } | |
| } | |
| return false; | |
| } | |
| internal int? GetPort() | |
| { | |
| if (ranges.Count > 0) | |
| { | |
| var range = ranges.First.Value; | |
| int port = range.minPort++; | |
| ranges.RemoveFirst(); | |
| if (range.minPort <= range.maxPort) | |
| { | |
| ranges.AddFirst(range); | |
| } | |
| --count; | |
| return port; | |
| } | |
| return null; | |
| } | |
| internal void ReturnPort(int port) | |
| { | |
| if (port < range.minPort || port > range.maxPort) | |
| { | |
| return; | |
| } | |
| ++count; | |
| for (var node = ranges.First; node != null; node = node.Next) | |
| { | |
| var range = node.Value; | |
| if (port < range.minPort) | |
| { | |
| if (port == range.minPort - 1) | |
| { | |
| if (node.Previous != null && port == node.Previous.Value.maxPort + 1) | |
| { | |
| // the port bridges the gap between two adjacent ranges, merge them | |
| range.minPort = node.Previous.Value.minPort; | |
| ranges.Remove(node.Previous); | |
| } | |
| else | |
| { | |
| // just merge the port into the current range | |
| --range.minPort; | |
| } | |
| var next = node.Next; | |
| ranges.Remove(node); | |
| node = next != null ? ranges.AddBefore(next, range) : ranges.AddLast(range); | |
| return; | |
| } | |
| if (node.Previous != null) | |
| { | |
| if (port == node.Previous.Value.maxPort + 1) | |
| { | |
| // merge with the previous node, and done | |
| range.minPort = node.Previous.Value.minPort; | |
| range.maxPort = node.Previous.Value.maxPort + 1; | |
| ranges.Remove(node.Previous); | |
| ranges.AddBefore(node, range); | |
| return; | |
| } | |
| } | |
| // add a new range | |
| ranges.AddBefore(node, (port, port)); | |
| return; | |
| } | |
| else if (port <= range.maxPort) | |
| { | |
| --count; // NB: this is the only scenario where 'count' shouldn't be incremented | |
| return; | |
| } | |
| else if (node.Next == null) | |
| { | |
| if (port == range.maxPort + 1) | |
| { | |
| ++range.maxPort; | |
| ranges.RemoveLast(); | |
| ranges.AddLast(range); | |
| return; | |
| } | |
| } | |
| } | |
| // if control comes here, the port forms the last range | |
| ranges.AddLast((port, port)); | |
| } | |
| internal void VerifyIntegrity() | |
| { | |
| int count = 0; | |
| for (var node = ranges.First; node != null; node = node.Next) | |
| { | |
| var range = node.Value; | |
| System.Diagnostics.Debug.Assert(range.minPort <= range.maxPort); | |
| count += range.maxPort - range.minPort + 1; | |
| if (node.Previous != null) | |
| { | |
| System.Diagnostics.Debug.Assert(node.Previous.Value.maxPort < range.minPort - 1); | |
| } | |
| } | |
| System.Diagnostics.Debug.Assert(count == this.count); | |
| } | |
| } | |
| class Program | |
| { | |
| static void Main(string[] args) | |
| { | |
| PortsManager pm = new PortsManager(1, 100); | |
| Random rnd = new Random(); | |
| for (var c = 0; c < 100; ++c) | |
| { | |
| for (var i = 0; i < 50; ++i) | |
| { | |
| var port = pm.GetPort(); | |
| Console.WriteLine($"GetPort: {port}"); | |
| } | |
| pm.VerifyIntegrity(); | |
| Console.WriteLine($"Count: {pm.Count}"); | |
| for (var i = 0; i < 100; ++i) | |
| { | |
| var port = rnd.Next(1, 100); | |
| Console.WriteLine($"ReturnPort: {port}"); | |
| pm.ReturnPort(port); | |
| } | |
| pm.VerifyIntegrity(); | |
| Console.WriteLine($"Count: {pm.Count}"); | |
| } | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment