From 33c225c16407ea092dc610ad07ea65a0e2c359fa Mon Sep 17 00:00:00 2001 From: Pekka Riikonen Date: Tue, 22 May 2001 17:37:21 +0000 Subject: [PATCH] updates. --- CHANGES | 25 ++++ apps/silcd/command.c | 97 ++++++---------- apps/silcd/idlist.c | 41 ++++--- apps/silcd/idlist.h | 32 +++--- apps/silcd/packet_receive.c | 31 +++-- apps/silcd/packet_send.c | 26 +++-- apps/silcd/server.c | 215 ++++++++++++++++++----------------- lib/silccore/idcache.c | 7 +- lib/silcutil/silchashtable.c | 70 +++++++++++- lib/silcutil/silchashtable.h | 13 ++- prepare | 2 +- 11 files changed, 327 insertions(+), 232 deletions(-) diff --git a/CHANGES b/CHANGES index 90eff4f9..9289df41 100644 --- a/CHANGES +++ b/CHANGES @@ -1,3 +1,28 @@ +Tue May 22 17:27:16 EEST 2001 Pekka Riikonen + + * Added silc_hash_table_list, silc_hash_table_get and the + SilcHashTableList structure to provide an alternative way to + traverse the hash table. The affected files are + lib/silcutil/silchashtable.[ch]. + + * Changed the server's idlist routines to use the hash table + routines to optimize the code. + +Mon May 21 21:46:20 EEST 2001 Pekka Riikonen + + * Replaced the client entry's `channel' list and channel entry's + `user_list' list to hash tables for optimized lookup. Changed + the code to use the hash table interface around the code. + Affected file lib/silcd/idlist.[ch]. + + * Added `auto_rehash' boolean argument to the function + silc_hash_table_alloc to indicate whether the hash table should + auto-rehash when it thinks is appropriate time. It will + increase the hash table size if the there is twice as much + entries in the table than the size of the table, and will + decrease the size if there are twice as less entries than + the size of the table. + Mon May 21 09:51:11 EEST 2001 Pekka Riikonen * Fixed silc_xxx_get_supported to not crash at some circumstances. diff --git a/apps/silcd/command.c b/apps/silcd/command.c index 31283fd0..c47c1caa 100644 --- a/apps/silcd/command.c +++ b/apps/silcd/command.c @@ -1864,7 +1864,7 @@ silc_server_command_list_send_reply(SilcServerCommandContext cmd, memset(usercount, 0, sizeof(usercount)); } else { topic = entry->topic; - users = silc_list_count(entry->user_list); + users = silc_hash_table_count(entry->user_list); SILC_PUT32_MSB(users, usercount); } @@ -1915,7 +1915,7 @@ silc_server_command_list_send_reply(SilcServerCommandContext cmd, memset(usercount, 0, sizeof(usercount)); } else { topic = entry->topic; - users = silc_list_count(entry->user_list); + users = silc_hash_table_count(entry->user_list); SILC_PUT32_MSB(users, usercount); } @@ -2050,11 +2050,13 @@ SILC_SERVER_CMD_FUNC(topic) goto out; } - /* See whether has rights to change topic */ - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) - if (chl->client == client) - break; + /* See whether the client is on channel and has rights to change topic */ + if (!silc_hash_table_find(channel->user_list, client, NULL, + (void *)&chl)) { + silc_server_command_send_status_reply(cmd, SILC_COMMAND_TOPIC, + SILC_STATUS_ERR_NOT_ON_CHANNEL); + goto out; + } if (chl->mode == SILC_CHANNEL_UMODE_NONE) { if (channel->mode & SILC_CHANNEL_MODE_TOPIC) { @@ -2168,16 +2170,12 @@ SILC_SERVER_CMD_FUNC(invite) /* Check whether the channel is invite-only channel. If yes then the sender of this command must be at least channel operator. */ if (channel->mode & SILC_CHANNEL_MODE_INVITE) { - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) - if (chl->client == sender) { - if (chl->mode == SILC_CHANNEL_UMODE_NONE) { - silc_server_command_send_status_reply(cmd, SILC_COMMAND_INVITE, - SILC_STATUS_ERR_NO_CHANNEL_PRIV); - goto out; - } - break; - } + silc_hash_table_find(channel->user_list, sender, NULL, (void *)&chl); + if (chl->mode == SILC_CHANNEL_UMODE_NONE) { + silc_server_command_send_status_reply(cmd, SILC_COMMAND_INVITE, + SILC_STATUS_ERR_NO_CHANNEL_PRIV); + goto out; + } } /* Get destination client ID */ @@ -2800,7 +2798,7 @@ static void silc_server_command_join_channel(SilcServer server, /* Check user count limit if set. */ if (channel->mode & SILC_CHANNEL_MODE_ULIMIT) { - if (silc_list_count(channel->user_list) + 1 > + if (silc_hash_table_count(channel->user_list) + 1 > channel->user_limit) { silc_server_command_send_status_reply(cmd, SILC_COMMAND_JOIN, SILC_STATUS_ERR_CHANNEL_IS_FULL); @@ -2820,7 +2818,7 @@ static void silc_server_command_join_channel(SilcServer server, } /* Generate new channel key as protocol dictates */ - if ((!created && silc_list_count(channel->user_list) > 0) || + if ((!created && silc_hash_table_count(channel->user_list) > 0) || !channel->channel_key) silc_server_create_channel_key(server, channel, 0); @@ -2838,8 +2836,8 @@ static void silc_server_command_join_channel(SilcServer server, chl->mode = umode; chl->client = client; chl->channel = channel; - silc_list_add(channel->user_list, chl); - silc_list_add(client->channels, chl); + silc_hash_table_add(channel->user_list, client, chl); + silc_hash_table_add(client->channels, channel, chl); /* Get users on the channel */ silc_server_get_users_on_channel(server, channel, &user_list, &mode_list, @@ -3090,7 +3088,7 @@ SILC_SERVER_CMD_FUNC(join) /* If the channel does not have global users and is also empty it means the channel was created globally (by our router) and the client will be the channel founder and operator. */ - if (!channel->global_users && silc_list_count(channel->user_list) == 0) { + if (!channel->global_users && !silc_hash_table_count(channel->user_list)) { umode = (SILC_CHANNEL_UMODE_CHANOP | SILC_CHANNEL_UMODE_CHANFO); created = TRUE; /* Created globally by our router */ } @@ -3458,10 +3456,7 @@ SILC_SERVER_CMD_FUNC(cmode) } /* Get entry to the channel user list */ - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) - if (chl->client == client) - break; + silc_hash_table_find(channel->user_list, client, NULL, (void *)&chl); /* Check that client has rights to change any requested channel modes */ if (!silc_server_check_cmode_rights(channel, chl, mode_mask)) { @@ -3798,13 +3793,8 @@ SILC_SERVER_CMD_FUNC(cumode) } /* Check that client has rights to change other's rights */ - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) { - if (chl->client == client) { - sender_mask = chl->mode; - break; - } - } + silc_hash_table_find(channel->user_list, client, NULL, (void *)&chl); + sender_mask = chl->mode; /* Get the target client's channel mode mask */ tmp_mask = silc_argument_get_arg_type(cmd->args, 2, NULL); @@ -3854,10 +3844,8 @@ SILC_SERVER_CMD_FUNC(cumode) } /* Get entry to the channel user list */ - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) - if (chl->client == target_client) - break; + silc_hash_table_find(channel->user_list, target_client, NULL, + (void *)&chl); } /* @@ -4046,16 +4034,11 @@ SILC_SERVER_CMD_FUNC(kick) } /* Check that the kicker is channel operator or channel founder */ - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) { - if (chl->client == client) { - if (chl->mode == SILC_CHANNEL_UMODE_NONE) { - silc_server_command_send_status_reply(cmd, SILC_COMMAND_KICK, - SILC_STATUS_ERR_NO_CHANNEL_PRIV); - goto out; - } - break; - } + silc_hash_table_find(channel->user_list, client, NULL, (void *)&chl); + if (chl->mode == SILC_CHANNEL_UMODE_NONE) { + silc_server_command_send_status_reply(cmd, SILC_COMMAND_KICK, + SILC_STATUS_ERR_NO_CHANNEL_PRIV); + goto out; } /* Get target Client ID */ @@ -4082,16 +4065,11 @@ SILC_SERVER_CMD_FUNC(kick) /* Check that the target client is not channel founder. Channel founder cannot be kicked from the channel. */ - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) { - if (chl->client == target_client) { - if (chl->mode & SILC_CHANNEL_UMODE_CHANFO) { - silc_server_command_send_status_reply(cmd, SILC_COMMAND_KICK, - SILC_STATUS_ERR_NO_CHANNEL_FOPRIV); - goto out; - } - break; - } + silc_hash_table_find(channel->user_list, target_client, NULL, (void *)&chl); + if (chl->mode & SILC_CHANNEL_UMODE_CHANFO) { + silc_server_command_send_status_reply(cmd, SILC_COMMAND_KICK, + SILC_STATUS_ERR_NO_CHANNEL_FOPRIV); + goto out; } /* Check whether target client is on the channel */ @@ -4405,10 +4383,7 @@ SILC_SERVER_CMD_FUNC(ban) } /* Get entry to the channel user list */ - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) - if (chl->client == client) - break; + silc_hash_table_find(channel->user_list, client, NULL, (void *)&chl); /* The client must be at least channel operator. */ if (!(chl->mode & SILC_CHANNEL_UMODE_CHANOP)) { diff --git a/apps/silcd/idlist.c b/apps/silcd/idlist.c index a647c949..9cdbc223 100644 --- a/apps/silcd/idlist.c +++ b/apps/silcd/idlist.c @@ -307,11 +307,12 @@ silc_idlist_add_client(SilcIDList id_list, char *nickname, char *username, client->id = id; client->router = router; client->connection = connection; - silc_list_init(client->channels, struct SilcChannelClientEntryStruct, - client_list); + client->channels = silc_hash_table_alloc(3, silc_hash_ptr, NULL, + NULL, NULL, NULL, NULL, TRUE); if (!silc_idcache_add(id_list->clients, nickname, (void *)client->id, (void *)client, FALSE)) { + silc_hash_table_free(client->channels); silc_free(client); return NULL; } @@ -562,11 +563,13 @@ silc_idlist_add_channel(SilcIDList id_list, char *channel_name, int mode, return NULL; } - silc_list_init(channel->user_list, struct SilcChannelClientEntryStruct, - channel_list); + channel->user_list = silc_hash_table_alloc(3, silc_hash_ptr, NULL, NULL, + NULL, NULL, NULL, TRUE); if (!silc_idcache_add(id_list->channels, channel->channel_name, (void *)channel->id, (void *)channel, FALSE)) { + silc_hmac_free(channel->hmac); + silc_hash_table_free(channel->user_list); silc_free(channel); return NULL; } @@ -574,6 +577,20 @@ silc_idlist_add_channel(SilcIDList id_list, char *channel_name, int mode, return channel; } +/* Foreach callbcak to free all users from the channel when deleting a + channel entry. */ + +static void silc_idlist_del_channel_foreach(void *key, void *context, + void *user_context) +{ + SilcChannelClientEntry chl = (SilcChannelClientEntry)context; + + /* Remove the context from the client's channel hash table as that + table and channel's user_list hash table share this same context. */ + silc_hash_table_del_by_context(chl->client->channels, chl->channel, chl); + silc_free(chl); +} + /* Free channel entry. This free's everything. */ int silc_idlist_del_channel(SilcIDList id_list, SilcChannelEntry entry) @@ -581,8 +598,6 @@ int silc_idlist_del_channel(SilcIDList id_list, SilcChannelEntry entry) SILC_LOG_DEBUG(("Start")); if (entry) { - SilcChannelClientEntry chl; - /* Remove from cache */ if (entry->id) if (!silc_idcache_del_by_id(id_list->channels, (void *)entry->id)) @@ -608,14 +623,12 @@ int silc_idlist_del_channel(SilcIDList id_list, SilcChannelEntry entry) if (entry->rekey) silc_free(entry->rekey); - /* Free all data, free also any reference from the client's channel - list since they share the same memory. */ - silc_list_start(entry->user_list); - while ((chl = silc_list_get(entry->user_list)) != SILC_LIST_END) { - silc_list_del(chl->client->channels, chl); - silc_list_del(entry->user_list, chl); - silc_free(chl); - } + /* Free all client entrys from the users list. The silc_hash_table_free + will free all the entries so they are not freed at the foreach + callback. */ + silc_hash_table_foreach(entry->user_list, silc_idlist_del_channel_foreach, + NULL); + silc_hash_table_free(entry->user_list); memset(entry, 'F', sizeof(*entry)); silc_free(entry); diff --git a/apps/silcd/idlist.h b/apps/silcd/idlist.h index e070b1ca..f701514b 100644 --- a/apps/silcd/idlist.h +++ b/apps/silcd/idlist.h @@ -174,7 +174,7 @@ struct SilcServerEntryStruct { This entry used only by the SilcChannelEntry object and it holds information about current clients (ie. users) on channel. Following - short description of the fields: + short description of the fields: SilcClientEntry client @@ -190,21 +190,11 @@ struct SilcServerEntryStruct { SilcClientEntry we have this here for fast access to the channel when used by SilcClientEntry. - struct SilcChannelClientEntryStruct *client_list - struct SilcChannelClientEntryStruct *channel_list - - List member pointers. This structure is used by channel entry and - client entry thus we must have separate list member pointers for - them since we are using same entry for both lists (the entry is not - duplicated). SilcList requires this. - */ typedef struct SilcChannelClientEntryStruct { SilcClientEntry client; uint32 mode; SilcChannelEntry channel; - struct SilcChannelClientEntryStruct *client_list; - struct SilcChannelClientEntryStruct *channel_list; } *SilcChannelClientEntry; /* @@ -298,9 +288,11 @@ typedef struct SilcChannelClientEntryStruct { cell this client is coming from. This is used to route messages to this client. - SilcList channels + SilcHashTable channels; - List of channels this client has joined. + All the channels this client has joined. The context saved in the + hash table shares memory with the channel entrys `user_list' hash + table. void *connection @@ -327,8 +319,8 @@ struct SilcClientEntryStruct { /* Pointer to the router */ SilcServerEntry router; - /* List of channels client has joined to */ - SilcList channels; + /* All channels this client has joined */ + SilcHashTable channels; /* Connection data */ void *connection; @@ -400,6 +392,12 @@ struct SilcClientEntryStruct { if the method is SILC_AUTH_PASSWORD. If it is SILC_AUTH_PUBLIC_KEY then the `founder_passwd' is NULL. + SilcHashTable user_list + + All users joined on this channel. Note that the context saved to + this entry shares memory with the client entrys `channels' hash + table. + SilcServerEntry router This is a pointer to the server list. This is the router server @@ -448,8 +446,8 @@ struct SilcChannelEntryStruct { char *invite_list; char *ban_list; - /* List of users on channel */ - SilcList user_list; + /* All users on this channel */ + SilcHashTable user_list; /* Pointer to the router */ SilcServerEntry router; diff --git a/apps/silcd/packet_receive.c b/apps/silcd/packet_receive.c index 1b3303b4..9f175376 100644 --- a/apps/silcd/packet_receive.c +++ b/apps/silcd/packet_receive.c @@ -45,6 +45,7 @@ void silc_server_notify(SilcServer server, SilcServerEntry server_entry; SilcChannelClientEntry chl; SilcIDCacheEntry cache; + SilcHashTableList htl; uint32 mode; unsigned char *tmp; uint32 tmp_len; @@ -176,8 +177,8 @@ void silc_server_notify(SilcServer server, chl = silc_calloc(1, sizeof(*chl)); chl->client = client; chl->channel = channel; - silc_list_add(channel->user_list, chl); - silc_list_add(client->channels, chl); + silc_hash_table_add(channel->user_list, client, chl); + silc_hash_table_add(client->channels, channel, chl); silc_free(client_id); break; @@ -512,8 +513,8 @@ void silc_server_notify(SilcServer server, silc_free(client_id); /* Get entry to the channel user list */ - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) { + silc_hash_table_list(channel->user_list, &htl); + while (silc_hash_table_get(&htl, NULL, (void *)&chl)) { SilcChannelClientEntry chl2 = NULL; /* If the mode is channel founder and we already find a client @@ -1178,7 +1179,6 @@ void silc_server_channel_message(SilcServer server, SilcPacketContext *packet) { SilcChannelEntry channel = NULL; - SilcChannelClientEntry chl; SilcChannelID *id = NULL; void *sender = NULL; void *sender_entry = NULL; @@ -1204,23 +1204,20 @@ void silc_server_channel_message(SilcServer server, } } - /* See that this client is on the channel. If the message is coming - from router we won't do the check as the message is from client that - we don't know about. Also, if the original sender is not client - (as it can be server as well) we don't do the check. */ + /* See that this client is on the channel. If the original sender is + not client (as it can be server as well) we don't do the check. */ sender = silc_id_str2id(packet->src_id, packet->src_id_len, packet->src_id_type); if (!sender) goto out; if (packet->src_id_type == SILC_ID_CLIENT) { - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) { - if (chl->client && SILC_ID_CLIENT_COMPARE(chl->client->id, sender)) { - sender_entry = chl->client; - break; - } - } - if (chl == SILC_LIST_END) { + sender_entry = silc_idlist_find_client_by_id(server->local_list, + sender, NULL); + if (!sender_entry) + sender_entry = silc_idlist_find_client_by_id(server->global_list, + sender, NULL); + if (!sender_entry || !silc_server_client_on_channel(sender_entry, + channel)) { SILC_LOG_DEBUG(("Client not on channel")); goto out; } diff --git a/apps/silcd/packet_send.c b/apps/silcd/packet_send.c index c4d33dd8..46a77f18 100644 --- a/apps/silcd/packet_send.c +++ b/apps/silcd/packet_send.c @@ -418,6 +418,7 @@ void silc_server_packet_send_to_channel(SilcServer server, SilcClientEntry client = NULL; SilcServerEntry *routed = NULL; SilcChannelClientEntry chl; + SilcHashTableList htl; SilcIDListData idata; uint32 routed_count = 0; @@ -463,8 +464,8 @@ void silc_server_packet_send_to_channel(SilcServer server, } /* Send the message to clients on the channel's client list. */ - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) { + silc_hash_table_list(channel->user_list, &htl); + while (silc_hash_table_get(&htl, NULL, (void *)&chl)) { client = chl->client; /* If client has router set it is not locally connected client and @@ -604,6 +605,7 @@ void silc_server_packet_relay_to_channel(SilcServer server, SilcChannelClientEntry chl; uint32 routed_count = 0; SilcIDListData idata; + SilcHashTableList htl; SILC_LOG_DEBUG(("Relaying packet to channel")); @@ -654,8 +656,8 @@ void silc_server_packet_relay_to_channel(SilcServer server, } /* Send the message to clients on the channel's client list. */ - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) { + silc_hash_table_list(channel->user_list, &htl); + while (silc_hash_table_get(&htl, NULL, (void *)&chl)) { client = chl->client; if (client) { @@ -812,13 +814,14 @@ void silc_server_packet_send_local_channel(SilcServer server, int force_send) { SilcChannelClientEntry chl; + SilcHashTableList htl; SilcSocketConnection sock = NULL; SILC_LOG_DEBUG(("Start")); /* Send the message to clients on the channel's client list. */ - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) { + silc_hash_table_list(channel->user_list, &htl); + while (silc_hash_table_get(&htl, NULL, (void *)&chl)) { if (chl->client && !chl->client->router) { sock = (SilcSocketConnection)chl->client->connection; @@ -1318,6 +1321,7 @@ void silc_server_send_notify_on_channels(SilcServer server, uint32 sent_clients_count = 0; SilcServerEntry *routed = NULL; uint32 routed_count = 0; + SilcHashTableList htl, htl2; SilcChannelEntry channel; SilcChannelClientEntry chl, chl2; SilcIDListData idata; @@ -1329,7 +1333,7 @@ void silc_server_send_notify_on_channels(SilcServer server, SILC_LOG_DEBUG(("Start")); - if (!silc_list_count(client->channels)) + if (!silc_hash_table_count(client->channels)) return; va_start(ap, argc); @@ -1344,13 +1348,13 @@ void silc_server_send_notify_on_channels(SilcServer server, packetdata.src_id_len = silc_id_get_len(server->id, SILC_ID_SERVER); packetdata.src_id_type = SILC_ID_SERVER; - silc_list_start(client->channels); - while ((chl = silc_list_get(client->channels)) != SILC_LIST_END) { + silc_hash_table_list(client->channels, &htl); + while (silc_hash_table_get(&htl, NULL, (void *)&chl)) { channel = chl->channel; /* Send the message to all clients on the channel's client list. */ - silc_list_start(channel->user_list); - while ((chl2 = silc_list_get(channel->user_list)) != SILC_LIST_END) { + silc_hash_table_list(channel->user_list, &htl2); + while (silc_hash_table_get(&htl2, NULL, (void *)&chl2)) { c = chl2->client; if (sender && c == sender) diff --git a/apps/silcd/server.c b/apps/silcd/server.c index 2eae57b8..427bbdf3 100644 --- a/apps/silcd/server.c +++ b/apps/silcd/server.c @@ -2445,9 +2445,10 @@ int silc_server_remove_clients_by_server(SilcServer server, int silc_server_channel_has_global(SilcChannelEntry channel) { SilcChannelClientEntry chl; + SilcHashTableList htl; - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) { + silc_hash_table_list(channel->user_list, &htl); + while (silc_hash_table_get(&htl, NULL, (void *)&chl)) { if (chl->client->router) return TRUE; } @@ -2461,9 +2462,10 @@ int silc_server_channel_has_global(SilcChannelEntry channel) int silc_server_channel_has_local(SilcChannelEntry channel) { SilcChannelClientEntry chl; + SilcHashTableList htl; - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) { + silc_hash_table_list(channel->user_list, &htl); + while (silc_hash_table_get(&htl, NULL, (void *)&chl)) { if (!chl->client->router) return TRUE; } @@ -2484,6 +2486,7 @@ void silc_server_remove_from_channels(SilcServer server, { SilcChannelEntry channel; SilcChannelClientEntry chl; + SilcHashTableList htl; SilcBuffer clidp; SILC_LOG_DEBUG(("Start")); @@ -2495,16 +2498,16 @@ void silc_server_remove_from_channels(SilcServer server, /* Remove the client from all channels. The client is removed from the channels' user list. */ - silc_list_start(client->channels); - while ((chl = silc_list_get(client->channels)) != SILC_LIST_END) { + silc_hash_table_list(client->channels, &htl); + while (silc_hash_table_get(&htl, NULL, (void *)&chl)) { channel = chl->channel; /* Remove channel from client's channel list */ - silc_list_del(client->channels, chl); + silc_hash_table_del_by_context(client->channels, channel, chl); /* Remove channel if there is no users anymore */ if (server->server_type == SILC_ROUTER && - silc_list_count(channel->user_list) < 2) { + silc_hash_table_count(channel->user_list) < 2) { server->stat.my_channels--; if (channel->rekey) @@ -2513,13 +2516,15 @@ void silc_server_remove_from_channels(SilcServer server, if (channel->founder_key) { /* The founder auth data exists, do not remove the channel entry */ SilcChannelClientEntry chl2; + SilcHashTableList htl2; channel->id = NULL; - silc_list_start(channel->user_list); - while ((chl2 = silc_list_get(channel->user_list)) != SILC_LIST_END) { - silc_list_del(chl2->client->channels, chl2); - silc_list_del(channel->user_list, chl2); + silc_hash_table_list(channel->user_list, &htl2); + while (silc_hash_table_get(&htl2, NULL, (void *)&chl2)) { + silc_hash_table_del_by_context(chl2->client->channels, channel, chl); + silc_hash_table_del_by_context(channel->user_list, + chl2->client, chl); silc_free(chl2); } continue; @@ -2531,7 +2536,7 @@ void silc_server_remove_from_channels(SilcServer server, } /* Remove client from channel's client list */ - silc_list_del(channel->user_list, chl); + silc_hash_table_del_by_context(channel->user_list, chl->client, chl); silc_free(chl); server->stat.my_chanclients--; @@ -2560,13 +2565,15 @@ void silc_server_remove_from_channels(SilcServer server, if (channel->founder_key) { /* The founder auth data exists, do not remove the channel entry */ SilcChannelClientEntry chl2; + SilcHashTableList htl2; channel->id = NULL; - silc_list_start(channel->user_list); - while ((chl2 = silc_list_get(channel->user_list)) != SILC_LIST_END) { - silc_list_del(chl2->client->channels, chl2); - silc_list_del(channel->user_list, chl2); + silc_hash_table_list(channel->user_list, &htl2); + while (silc_hash_table_get(&htl2, NULL, (void *)&chl2)) { + silc_hash_table_del_by_context(chl2->client->channels, channel, chl); + silc_hash_table_del_by_context(channel->user_list, + chl2->client, chl); silc_free(chl2); } continue; @@ -2621,87 +2628,87 @@ int silc_server_remove_from_one_channel(SilcServer server, SILC_LOG_DEBUG(("Start")); - clidp = silc_id_payload_encode(client->id, SILC_ID_CLIENT); + /* Get the entry to the channel, if this client is not on the channel + then return Ok. */ + if (!silc_hash_table_find(client->channels, channel, NULL, (void *)&chl)) + return TRUE; /* Remove the client from the channel. The client is removed from the channel's user list. */ - silc_list_start(client->channels); - while ((chl = silc_list_get(client->channels)) != SILC_LIST_END) { - if (chl->channel != channel) - continue; - - ch = chl->channel; - - /* Remove channel from client's channel list */ - silc_list_del(client->channels, chl); - /* Remove channel if there is no users anymore */ - if (server->server_type == SILC_ROUTER && - silc_list_count(channel->user_list) < 2) { - if (channel->rekey) - silc_task_unregister_by_context(server->timeout_queue, channel->rekey); - if (!silc_idlist_del_channel(server->local_list, channel)) - silc_idlist_del_channel(server->global_list, channel); - silc_buffer_free(clidp); - server->stat.my_channels--; - return FALSE; - } - - /* Remove client from channel's client list */ - silc_list_del(channel->user_list, chl); - silc_free(chl); - server->stat.my_chanclients--; - - /* If there is no global users on the channel anymore mark the channel - as local channel. */ - if (server->server_type == SILC_SERVER && - !silc_server_channel_has_global(channel)) - channel->global_users = FALSE; - - /* If there is not at least one local user on the channel then we don't - need the channel entry anymore, we can remove it safely. */ - if (server->server_type == SILC_SERVER && - !silc_server_channel_has_local(channel)) { - /* Notify about leaving client if this channel has global users. */ - if (notify && channel->global_users) - silc_server_send_notify_to_channel(server, NULL, channel, FALSE, - SILC_NOTIFY_TYPE_LEAVE, 1, - clidp->data, clidp->len); - - silc_buffer_free(clidp); - - if (channel->rekey) - silc_task_unregister_by_context(server->timeout_queue, channel->rekey); - - if (channel->founder_key) { - /* The founder auth data exists, do not remove the channel entry */ - SilcChannelClientEntry chl2; + clidp = silc_id_payload_encode(client->id, SILC_ID_CLIENT); + ch = chl->channel; + + /* Remove channel from client's channel list */ + silc_hash_table_del_by_context(client->channels, chl->channel, chl); + + /* Remove channel if there is no users anymore */ + if (server->server_type == SILC_ROUTER && + silc_hash_table_count(channel->user_list) < 2) { + if (channel->rekey) + silc_task_unregister_by_context(server->timeout_queue, channel->rekey); + if (!silc_idlist_del_channel(server->local_list, channel)) + silc_idlist_del_channel(server->global_list, channel); + silc_buffer_free(clidp); + server->stat.my_channels--; + return FALSE; + } - channel->id = NULL; + /* Remove client from channel's client list */ + silc_hash_table_del_by_context(channel->user_list, chl->client, chl); + silc_free(chl); + server->stat.my_chanclients--; + + /* If there is no global users on the channel anymore mark the channel + as local channel. */ + if (server->server_type == SILC_SERVER && + !silc_server_channel_has_global(channel)) + channel->global_users = FALSE; + + /* If there is not at least one local user on the channel then we don't + need the channel entry anymore, we can remove it safely. */ + if (server->server_type == SILC_SERVER && + !silc_server_channel_has_local(channel)) { + /* Notify about leaving client if this channel has global users. */ + if (notify && channel->global_users) + silc_server_send_notify_to_channel(server, NULL, channel, FALSE, + SILC_NOTIFY_TYPE_LEAVE, 1, + clidp->data, clidp->len); + + silc_buffer_free(clidp); + + if (channel->rekey) + silc_task_unregister_by_context(server->timeout_queue, channel->rekey); - silc_list_start(channel->user_list); - while ((chl2 = silc_list_get(channel->user_list)) != SILC_LIST_END) { - silc_list_del(chl2->client->channels, chl2); - silc_list_del(channel->user_list, chl2); - silc_free(chl2); - } - return FALSE; + if (channel->founder_key) { + /* The founder auth data exists, do not remove the channel entry */ + SilcChannelClientEntry chl2; + SilcHashTableList htl2; + + channel->id = NULL; + + silc_hash_table_list(channel->user_list, &htl2); + while (silc_hash_table_get(&htl2, NULL, (void *)&chl2)) { + silc_hash_table_del_by_context(chl2->client->channels, channel, chl); + silc_hash_table_del_by_context(channel->user_list, + chl2->client, chl); + silc_free(chl2); } - - if (!silc_idlist_del_channel(server->local_list, channel)) - silc_idlist_del_channel(server->global_list, channel); - server->stat.my_channels--; return FALSE; } - /* Send notify to channel about client leaving the channel */ - if (notify) - silc_server_send_notify_to_channel(server, NULL, channel, FALSE, - SILC_NOTIFY_TYPE_LEAVE, 1, - clidp->data, clidp->len); - break; + if (!silc_idlist_del_channel(server->local_list, channel)) + silc_idlist_del_channel(server->global_list, channel); + server->stat.my_channels--; + return FALSE; } + /* Send notify to channel about client leaving the channel */ + if (notify) + silc_server_send_notify_to_channel(server, NULL, channel, FALSE, + SILC_NOTIFY_TYPE_LEAVE, 1, + clidp->data, clidp->len); + silc_buffer_free(clidp); return TRUE; } @@ -2714,15 +2721,11 @@ int silc_server_remove_from_one_channel(SilcServer server, int silc_server_client_on_channel(SilcClientEntry client, SilcChannelEntry channel) { - SilcChannelClientEntry chl; - if (!client || !channel) return FALSE; - silc_list_start(client->channels); - while ((chl = silc_list_get(client->channels)) != SILC_LIST_END) - if (chl->channel == channel) - return TRUE; + if (silc_hash_table_find(client->channels, channel, NULL, NULL)) + return TRUE; return FALSE; } @@ -3242,6 +3245,7 @@ void silc_server_announce_get_channel_users(SilcServer server, SilcBuffer *channel_users_modes) { SilcChannelClientEntry chl; + SilcHashTableList htl; SilcBuffer chidp, clidp; SilcBuffer tmp; int len; @@ -3251,8 +3255,8 @@ void silc_server_announce_get_channel_users(SilcServer server, /* Now find all users on the channel */ chidp = silc_id_payload_encode(channel->id, SILC_ID_CHANNEL); - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) { + silc_hash_table_list(channel->user_list, &htl); + while (silc_hash_table_get(&htl, NULL, (void *)&chl)) { clidp = silc_id_payload_encode(chl->client->id, SILC_ID_CLIENT); /* JOIN Notify */ @@ -3450,6 +3454,7 @@ void silc_server_get_users_on_channel(SilcServer server, uint32 *user_count) { SilcChannelClientEntry chl; + SilcHashTableList htl; SilcBuffer client_id_list; SilcBuffer client_mode_list; SilcBuffer idp; @@ -3457,14 +3462,15 @@ void silc_server_get_users_on_channel(SilcServer server, /* XXX rewrite - this does not support IPv6 based Client ID's. */ - client_id_list = silc_buffer_alloc((SILC_ID_CLIENT_LEN + 4) * - silc_list_count(channel->user_list)); - client_mode_list = silc_buffer_alloc(4 * - silc_list_count(channel->user_list)); + client_id_list = + silc_buffer_alloc((SILC_ID_CLIENT_LEN + 4) * + silc_hash_table_count(channel->user_list)); + client_mode_list = + silc_buffer_alloc(4 * silc_hash_table_count(channel->user_list)); silc_buffer_pull_tail(client_id_list, SILC_BUFFER_END(client_id_list)); silc_buffer_pull_tail(client_mode_list, SILC_BUFFER_END(client_mode_list)); - silc_list_start(channel->user_list); - while ((chl = silc_list_get(channel->user_list)) != SILC_LIST_END) { + silc_hash_table_list(channel->user_list, &htl); + while (silc_hash_table_get(&htl, NULL, (void *)&chl)) { /* Client ID */ idp = silc_id_payload_encode(chl->client->id, SILC_ID_CLIENT); silc_buffer_put(client_id_list, idp->data, idp->len); @@ -3561,8 +3567,8 @@ void silc_server_save_users_on_channel(SilcServer server, chl->client = client; chl->mode = mode; chl->channel = channel; - silc_list_add(channel->user_list, chl); - silc_list_add(client->channels, chl); + silc_hash_table_add(channel->user_list, chl->client, chl); + silc_hash_table_add(client->channels, chl->channel, chl); } } } @@ -3659,13 +3665,14 @@ SilcBuffer silc_server_get_client_channel_list(SilcServer server, SilcBuffer buffer = NULL; SilcChannelEntry channel; SilcChannelClientEntry chl; + SilcHashTableList htl; unsigned char *cid; uint32 id_len; uint16 name_len; int len; - silc_list_start(client->channels); - while ((chl = silc_list_get(client->channels)) != SILC_LIST_END) { + silc_hash_table_list(client->channels, &htl); + while (silc_hash_table_get(&htl, NULL, (void *)&chl)) { channel = chl->channel; if (channel->mode & SILC_CHANNEL_MODE_SECRET) diff --git a/lib/silccore/idcache.c b/lib/silccore/idcache.c index 7b8b1fa7..e5665f42 100644 --- a/lib/silccore/idcache.c +++ b/lib/silccore/idcache.c @@ -109,12 +109,13 @@ SilcIDCache silc_idcache_alloc(uint32 count, SilcIdType id_type, (void *)(uint32)id_type, silc_hash_id_compare, (void *)(uint32)id_type, - silc_idcache_destructor, NULL); + silc_idcache_destructor, NULL, + FALSE); cache->name_table = silc_hash_table_alloc(count, silc_hash_string, NULL, silc_hash_string_compare, NULL, - NULL, NULL); + NULL, NULL, FALSE); cache->context_table = silc_hash_table_alloc(count, silc_hash_ptr, NULL, - NULL, NULL, NULL, NULL); + NULL, NULL, NULL, NULL, FALSE); cache->destructor = destructor; cache->type = id_type; diff --git a/lib/silcutil/silchashtable.c b/lib/silcutil/silchashtable.c index fe75b10a..a5994cf4 100644 --- a/lib/silcutil/silchashtable.c +++ b/lib/silcutil/silchashtable.c @@ -42,11 +42,16 @@ #define SILC_HASH_TABLE_SIZE 3 /* Produce the index by hashing the key */ -#define SILC_HASH_TABLE_HASH \ - (ht->hash(key, ht->hash_user_context) % primesize[ht->table_size]) #define SILC_HASH_TABLE_HASH_F(f, c) \ ((f)(key, (c)) % primesize[ht->table_size]) +/* Check whether need to rehash */ +#define SILC_HASH_REHASH_INC \ + (ht->auto_rehash && (ht->entry_count / 2) > primesize[ht->table_size]) +#define SILC_HASH_REHASH_DEC \ + (ht->auto_rehash && (ht->entry_count * 2) < primesize[ht->table_size] && \ + ht->entry_count > primesize[SILC_HASH_TABLE_SIZE]) + /* One entry in the hash table. Includes the key and the associated context. The `next' pointer is non-NULL if two (or more) different keys hashed to same value. The pointer is the pointer to the next @@ -68,6 +73,7 @@ struct SilcHashTableStruct { void *hash_user_context; void *compare_user_context; void *destructor_user_context; + bool auto_rehash; }; /* Prime sizes for the hash table. The size of the table will always @@ -268,6 +274,9 @@ silc_hash_table_add_internal(SilcHashTable ht, void *key, void *context, (*entry)->context = context; ht->entry_count++; } + + if (SILC_HASH_REHASH_INC) + silc_hash_table_rehash(ht, 0); } /* Internal routine to replace old key with new one (if it exists) */ @@ -313,7 +322,8 @@ SilcHashTable silc_hash_table_alloc(uint32 table_size, SilcHashCompare compare, void *compare_user_context, SilcHashDestructor destructor, - void *destructor_user_context) + void *destructor_user_context, + bool auto_rehash) { SilcHashTable ht; uint32 size_index = SILC_HASH_TABLE_SIZE; @@ -333,6 +343,7 @@ SilcHashTable silc_hash_table_alloc(uint32 table_size, ht->hash_user_context = hash_user_context; ht->compare_user_context = compare_user_context; ht->destructor_user_context = destructor_user_context; + ht->auto_rehash = auto_rehash; return ht; } @@ -446,6 +457,9 @@ bool silc_hash_table_del(SilcHashTable ht, void *key) ht->entry_count--; + if (SILC_HASH_REHASH_DEC) + silc_hash_table_rehash(ht, 0); + return TRUE; } @@ -487,6 +501,9 @@ bool silc_hash_table_del_ext(SilcHashTable ht, void *key, ht->entry_count--; + if (SILC_HASH_REHASH_DEC) + silc_hash_table_rehash(ht, 0); + return TRUE; } @@ -525,6 +542,9 @@ bool silc_hash_table_del_by_context(SilcHashTable ht, void *key, ht->entry_count--; + if (SILC_HASH_REHASH_DEC) + silc_hash_table_rehash(ht, 0); + return TRUE; } @@ -569,6 +589,9 @@ bool silc_hash_table_del_by_context_ext(SilcHashTable ht, void *key, ht->entry_count--; + if (SILC_HASH_REHASH_DEC) + silc_hash_table_rehash(ht, 0); + return TRUE; } @@ -752,6 +775,7 @@ void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size, &size_index), sizeof(*ht->table)); ht->table_size = size_index; + ht->entry_count = 0; /* Rehash */ for (i = 0; i < primesize[table_size]; i++) { @@ -770,3 +794,43 @@ void silc_hash_table_rehash_ext(SilcHashTable ht, uint32 new_size, /* Remove old table */ silc_free(table); } + +/* Prepares the `htl' list structure sent as argument to be used in the + hash table traversing with the silc_hash_table_get. Usage: + SilcHashTableList htl; silc_hash_table_list(ht, &htl); */ + +void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl) +{ + htl->ht = ht; + htl->entry = NULL; + htl->index = 0; +} + +/* Returns always the next entry in the hash table into the `key' and + `context' and TRUE. If this returns FALSE then there are no anymore + any entrys. Usage: while (silc_hash_table_get(&htl, &key, &context)) */ + +bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context) +{ + SilcHashTableEntry entry = (SilcHashTableEntry)htl->entry; + + if (!htl->ht->entry_count) + return FALSE; + + while (!entry && htl->index < primesize[htl->ht->table_size]) { + entry = htl->ht->table[htl->index]; + htl->index++; + } + + if (!entry) + return FALSE; + + htl->entry = entry->next; + + if (key) + *key = entry->key; + if (context) + *context = entry->context; + + return TRUE; +} diff --git a/lib/silcutil/silchashtable.h b/lib/silcutil/silchashtable.h index 4bda91ab..4ad3db2d 100644 --- a/lib/silcutil/silchashtable.h +++ b/lib/silcutil/silchashtable.h @@ -23,6 +23,14 @@ /* Forward declarations */ typedef struct SilcHashTableStruct *SilcHashTable; +typedef struct SilcHashTableListStruct SilcHashTableList; + +/* List structure to traverse the hash table. */ +struct SilcHashTableListStruct { + SilcHashTable ht; + void *entry; + uint32 index; +}; /* A type for the hash function. This function is used to hash the provided key value `key' and return the index for the hash table. */ @@ -51,7 +59,8 @@ SilcHashTable silc_hash_table_alloc(uint32 table_size, SilcHashCompare compare, void *compare_user_context, SilcHashDestructor destructor, - void *destructor_user_context); + void *destructor_user_context, + bool auto_rehash); void silc_hash_table_free(SilcHashTable ht); uint32 silc_hash_table_size(SilcHashTable ht); uint32 silc_hash_table_count(SilcHashTable ht); @@ -67,6 +76,8 @@ void silc_hash_table_find_foreach(SilcHashTable ht, void *key, void silc_hash_table_foreach(SilcHashTable ht, SilcHashForeach foreach, void *user_context); void silc_hash_table_rehash(SilcHashTable ht, uint32 new_size); +void silc_hash_table_list(SilcHashTable ht, SilcHashTableList *htl); +bool silc_hash_table_get(SilcHashTableList *htl, void **key, void **context); /* Extended hash table interface (same as above but with specific diff --git a/prepare b/prepare index c3405b91..d9c2964a 100755 --- a/prepare +++ b/prepare @@ -25,7 +25,7 @@ # temporary files (including these prepare* scripts) are removed. # -SILC_VERSION=0.2.5 +SILC_VERSION=0.2.6 version=$1 if test "$version" = ""; then -- 2.24.0