Hi, Imagine a server with many connections. Maybe hundreds, maybe thousands. Now if a client sends something, I want to know from which client it came. Now here's the problem, how to find out fast? I could use a simple loop that searched through a list:

function findUser( userCode : integer );
...
    for i:=0 to clients.Count-1 do
       if clients.userCode = userCode then begin
           < found him>
           break;
       end;

However, if many clients are sending stuff more times a second, wouldn't I kill the server with looping through that list all the time? It would be nice if the userCode is an index to an array, so there's no need to search at all. But since the user list could be pretty dynamic, that wouldn't really work I think. Another way I could think of, is using a sorted list. Each time when a client logs in/out, I need to resort the list. But besides that, finding the client could be faster. Do you guys have better/faster solutions? Greetings, Rick

Rather than a linear search for a user, why not use some form of hash table or an STL map (which is... dun dun dun... a hashed structure I believe)

Instead of O(n) time you're cutting it down to O(1) for the find. Just a thought.

Sounds good. Is client ID required or any unique attribute?

Kuphryn

That code looks like Delphi/Pascal. If so, what does your actual server code look like? There is usually a way to identify the user right in there, rather than doing it separately.

Arrays might be the ideal way. Server keeps the (connection, userID) pairs, and this list is updated whenever a connection is established or lost. If you cannot do that, then hashmap is the next best way, as pointed out.

In general, in computer science, whenever you find yourself thinking "oh, I have this KEY, and I want to find that DATA associtated with that KEY," you want to use a hash table. After the linked list and the vector, it's the third most commonly used data container. If you haven't yet learned it, I suggest doing some googling right now.

An STL map is ordered, so it's typically implemented as an AVL tree or Red-Black tree; O(lg N) searching. There is the extended STL class hash_map, which is O(1) searching. You can also create your own open addressing based hash table with chaining pretty easily.

If you are using TCP, then the socket that you get the message on is the appropriate client ID. If you are using UDP, then the pair of remote IP address and remote IP port is the appropriate ID. Data in the actual packet is more easily forged.

Quote:

Original post by hplus0603 In general, in computer science, whenever you find yourself thinking "oh, I have this KEY, and I want to find that DATA associtated with that KEY," you want to use a hash table. After the linked list and the vector, it's the third most commonly used data container. If you haven't yet learned it, I suggest doing some googling right now.

Hashtable is of course the ideal implementation, my point was just that certain socket APIs provide callback mechanisms, which allow you to associate some tag object or identifier with socket, which is provided on callback.

Delphi in particular has an arbitrary integer property ("tag", i believe) on many objects, which is intended just callback purpose. This way, when reading from the socket, you can just query this value directly, and there's no need for additional mapping. Since many delphi socket implementations are based on visual components, they should have this property as well (depends on library of course).

Depending on application, it might be necessary to still manage addition and removal of sockets (or assume that total number of connection attempts will not exceed 2^32)