From fb917475ead420804c304dee9cacc34f1c3c9c0f Mon Sep 17 00:00:00 2001 From: Egor Date: Tue, 3 May 2022 10:49:56 +0300 Subject: [PATCH] use trie for seaching nicknames --- common.h | 3 + config.h | 1 + irc.c | 62 ++++++++++--------- net.c | 3 + trie.c | 182 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ trie.h | 33 ++++++++++ util.c | 7 +++ util.h | 1 + 8 files changed, 265 insertions(+), 27 deletions(-) create mode 100644 trie.c create mode 100644 trie.h diff --git a/common.h b/common.h index 499bffc..5038e7a 100644 --- a/common.h +++ b/common.h @@ -2,6 +2,7 @@ #define _common_h #include "NetSock/netsock.h" #include "config.h" +#include "trie.h" #define UMODE_INVISIBLE 1 #define UMODE_OPER 2 @@ -13,11 +14,13 @@ struct client_data { char type; char nick[32]; size_t nickLen; + char *key; // case-mapped nick char buf[2048]; size_t bufLen; size_t bufCap; char umode; }; +extern struct trie_node *client_map; extern struct client_data *clients[CLIENTS]; extern fd_set readfds; extern struct sockaddr_in serverAddrV4; diff --git a/config.h b/config.h index 913d250..36d19ae 100644 --- a/config.h +++ b/config.h @@ -3,3 +3,4 @@ #define CLIENTS 30 #define SUPPORT_IPV4 #define SUPPORT_IPV6 +#define MAX_NICKLEN 32 diff --git a/irc.c b/irc.c index 52cae31..20b8490 100644 --- a/irc.c +++ b/irc.c @@ -2,6 +2,8 @@ struct dynarr databuf; +struct trie_node *client_map = NULL; + const char *hostname = "irc.patchysicp.xyz"; int processPacket(struct client_data *client) { char *source = NULL; @@ -105,11 +107,13 @@ int processPacket(struct client_data *client) { // End GitHub Copilot send_log(client->FD, databuf.buf, databuf.len, 0); sendall_log(client->FD, databuf.buf, databuf.len, 0); - for(int i=0; inick[0]) { - copy_strf(&databuf, ":%s 353 %s = %s :%s\n", hostname, client->nick, args[0], clients[i]->nick); + struct trie_find *f; + if (trie_findfirst(&f, &client_map) == 1) + do { + struct client_data *cl = f->n->value; + copy_strf(&databuf, ":%s 353 %s = %s :%s\n", hostname, client->nick, args[0], cl->nick); send_log(client->FD, databuf.buf, databuf.len, 0); - } + } while(trie_findnext(&f) == 1); copy_strf(&databuf, ":%s 366 %s :End of /NAMES list\n", hostname, client->nick); send_log(client->FD, databuf.buf, databuf.len, 0); } else if(strcmp(command, "PRIVMSG") == 0) { @@ -195,11 +199,13 @@ int processPacket(struct client_data *client) { // TODO: actual channel support if (argc == 0) // FIXME: error message return 0; - for(int i=0; inick[0]) { - copy_strf(&databuf, ":%s 353 %s = %s :%s\n", hostname, client->nick, args[0], clients[i]->nick); + struct trie_find *f; + if (trie_findfirst(&f, &client_map) == 1) + do { + struct client_data *cl = f->n->value; + copy_strf(&databuf, ":%s 353 %s = %s :%s\n", hostname, client->nick, args[0], cl->nick); send_log(client->FD, databuf.buf, databuf.len, 0); - } + } while(trie_findnext(&f) == 1); copy_strf(&databuf, ":%s 366 %s :End of /NAMES list\n", hostname, client->nick); send_log(client->FD, databuf.buf, databuf.len, 0); } else if(strcmp(command, "USERHOST") == 0) { @@ -253,34 +259,36 @@ void sendMOTD(struct client_data *client) { } void setNick(struct client_data *client, char* nickname, size_t size) { - size_t i; // TODO: perform basic sanitization char *bruh = strchr(nickname, ' '); // FIXME: we should reject those tbh if (bruh) *bruh = 0; - // Start GitHub Copilot - // Check if the nickname is already taken - for(i=0;inick, nickname, size) == 0) { - // Nickname is already taken - copy_strf(&databuf, ":%s 443 * %s :Nickname is already in use\n", hostname, nickname); - send_log(client->FD, databuf.buf, databuf.len, 0); - return; - } + char *key = mystrdup(nickname); + if (!key) abort(); + stringlower(key); + + if (trie_get(&client_map, key)) { + // Nickname is already taken + copy_strf(&databuf, ":%s 443 * %s :Nickname is already in use\n", hostname, nickname); + send_log(client->FD, databuf.buf, databuf.len, 0); + free(key); + return; } - // End GitHub Copilot // Update nickname if(client->nickLen) { copy_strf(&databuf, ":%s NICK %s\n", client->nick, nickname); send_log(client->FD, databuf.buf, databuf.len, 0); sendall_log(client->FD, databuf.buf, databuf.len, 0); + trie_set(&client_map, client->key, NULL, NULL); } strncpy(client->nick, nickname, size); + if (trie_set(&client_map, client->key = key, client, 0) == -1) + abort(); + // Null term just incase client->nick[size-1] = 0; // Set length @@ -289,11 +297,11 @@ void setNick(struct client_data *client, char* nickname, size_t size) { } struct client_data *findClient(const char *nickname) { - for(int i=0; inick, nickname, 32) == 0) { - return clients[i]; - } - } - return NULL; + char key[MAX_NICKLEN]; + int len = strlen(nickname); + if (len >= MAX_NICKLEN) + return NULL; + memcpy(key, nickname, len+1); + stringlower(key); + return trie_get(&client_map, key); } diff --git a/net.c b/net.c index 90dd901..93e510a 100644 --- a/net.c +++ b/net.c @@ -69,6 +69,9 @@ void killConnection(struct client_data *cl, bool byChoice) { // End GitHub Copilot shutdown(cl->FD, SHUT_RDWR); closesocket(cl->FD); + if (cl->key) + trie_set(&client_map, cl->key, NULL, NULL); + free(cl->key); free(cl); } diff --git a/trie.c b/trie.c new file mode 100644 index 0000000..32d5ba8 --- /dev/null +++ b/trie.c @@ -0,0 +1,182 @@ +#include "trie.h" +#include +#include +#define trie_is_end(e, n) ((e) >= (n)->len) +#define trie_is_found(e, n, k) (!trie_is_end((e), (n)) && (n)->data[(e)]->key == (k)) +#define trie_node_size(cap) (sizeof(struct trie_node)+sizeof(struct trie_node*)*((cap)-1)) +#define trie_data_size(len) (sizeof(struct trie_node*)*(len)) +// finds the entry for a child node O(log s) +// note that there are three cases to handle: +// - past the end pointer (key doesn't exist, larger than any existing key) +// - ent with different key (key doesn't exist, it should be inserted before this one) +// - ent with matching key (key exists) +static int ent_find(struct trie_node *n, int key) +{ + int lo = 0; + int hi = n->len; + while (lo != hi) { + int mid = (lo+hi)/2; + if (n->data[mid]->key == key) + return mid; + if (n->data[mid]->key > key) + hi = mid; + else + lo = mid+1; + } + return lo; +} +// get value from trie O(n log s) +void *trie_get(struct trie_node **root, const char *key) +{ + struct trie_node *n = *root; + if (!n) + return NULL; + while (*key) { + int ent = ent_find(n, (unsigned char)*key); + if (!trie_is_found(ent, n, *key)) + return NULL; + n = n->data[ent]; + key++; + } + return n->value; +} +// set value in trie O(ns) +int trie_set(struct trie_node **root, const char *key, const void *value, void **oldvalue) +{ + int rv = 0; + if (oldvalue) + *oldvalue = NULL; + struct trie_node *n = *root; + if (!n) { // create root node + n = malloc(trie_node_size(1)); + if (!n) + return -1; + memset(n, 0, trie_node_size(0)); + n->cap = 1; + *root = n; + } + while (*key) { // walk the trie to find the leaf + int ent = ent_find(n, (unsigned char)*key); + if (!trie_is_found(ent, n, *key)) { // create missing node + if (!value) // ...unless we're deleting + return 0; + int cap = key[1] ? 1 : 0; // if it's a leaf, use capacity of 0 + struct trie_node *node = malloc(trie_node_size(cap)); + if (!node) { + rv = -1; + goto cleanup; + } + memset(node, 0, trie_node_size(0)); + node->key = *key; + node->cap = cap; + if (n->len == n->cap) { // reallocate the node + n->cap = n->cap*2 + 1; // 0 1 3 7 15 31 63 127 255 + // we have to update parent's pointer, but ent_find needs that pointer to be valid. + // so we have to locate it *before* reallocing. + struct trie_node **pent = n->parent ? &n->parent->data[ent_find(n->parent, n->key)] : root; + struct trie_node *nn = realloc(n, trie_node_size(n->cap)); + if (!nn) { + free(node); + rv = -1; + goto cleanup; + } + if (n != nn) { // update pointers + n = nn; + *pent = n; + for (int i = 0; i < n->len; i++) + n->data[i]->parent = n; + } + } + // insert the new node + node->parent = n; + memmove(&n->data[ent+1], &n->data[ent], trie_data_size(n->len++ - ent)); + n->data[ent] = node; + n = node; + } else { + n = n->data[ent]; + } + key++; + } + if (oldvalue) + *oldvalue = n->value; + n->value = (void *)value; // discard const + if (!value) { + while (!n->value && !n->len) { // free no longer used nodes +cleanup: + if (n->parent) { + struct trie_node *p = n->parent; + int ent = ent_find(p, n->key); + memmove(&p->data[ent], &p->data[ent+1], trie_data_size(--p->len - ent)); + free(n); + n = p; + } else { + free(n); + *root = NULL; + break; + } + } + } + return rv; +} +// free a trie +void trie_free(struct trie_node **root) { + struct trie_node *n = *root; + while (n) { + if (n->len) { + n = n->data[--n->len]; + } else { + struct trie_node *p = n->parent; + free(n); + n = p; + } + } +} +int trie_findnext(struct trie_find **pf) { + struct trie_find *f = *pf; + int ent = 0; // go to the first child node + for (;;) { + if (!trie_is_end(ent, f->n)) { + if (f->len == f->cap) { + f->cap *= 2; + void *nf = realloc(f, sizeof(struct trie_find)+f->cap); + if (!nf) { + *pf = NULL; + free(f); + return -1; + } + *pf = f = nf; + } + f->n = f->n->data[ent]; + f->key[f->len++] = f->n->key; + if (f->n->value) { // found a value + f->key[f->len] = '\0'; + return 1; + } + ent = 0; // no value, go to the first child + } else { // no more children, go to parent's next child + f->n = f->n->parent; + if (!f->n) { + *pf = NULL; + free(f); + return 0; + } + f->len--; + ent = ent_find(f->n, (unsigned char)f->key[f->len] + 1); + } + } +} +int trie_findfirst(struct trie_find **pf, struct trie_node **root) { + if (!*root) + return 0; + struct trie_find *f = *pf = malloc(sizeof(struct trie_find)+16); + if (!f) + return -1; + f->n = *root; + f->len = 0; + f->cap = 16; + if (f->n->value) { + f->key[f->len] = '\0'; + return 1; + } + return trie_findnext(pf); +} diff --git a/trie.h b/trie.h new file mode 100644 index 0000000..513f496 --- /dev/null +++ b/trie.h @@ -0,0 +1,33 @@ +#ifndef TRIE_H_ +#define TRIE_H_ +#include +#ifdef __cplusplus +extern "C" { +#endif +// all complexity is in terms of n = strlen(key) and s = size of the character set +struct trie_node { + unsigned char key; + unsigned char len; + unsigned char cap; + void *value; + struct trie_node *parent; + struct trie_node *data[1]; +}; +// get value from trie O(n log s) +void *trie_get(struct trie_node **root, const char *key); +// set value in trie O(ns) +int trie_set(struct trie_node **root, const char *key, const void *value, void **oldvalue); +// free a trie +void trie_free(struct trie_node **root); +struct trie_find { + struct trie_node *n; + size_t len; + size_t cap; + char key[1]; +}; +int trie_findfirst(struct trie_find **pf, struct trie_node **root); +int trie_findnext(struct trie_find **pf); +#ifdef __cplusplus +} +#endif +#endif diff --git a/util.c b/util.c index 0468b00..6166c8e 100644 --- a/util.c +++ b/util.c @@ -55,3 +55,10 @@ void stringlower(char *s) { s++; } } +char *mystrdup(const char *s) { + int len = strlen(s); + char *buf = malloc(len+1); + if (buf) + memcpy(buf, s, len+1); + return buf; +} diff --git a/util.h b/util.h index ab11d47..340ee17 100644 --- a/util.h +++ b/util.h @@ -11,3 +11,4 @@ void append_strf(struct dynarr *d, const char *s, ...); #define copy_strf(d, ...) append_strf(((d)->len=0, (d)), __VA_ARGS__) void stringupper(char *s); void stringlower(char *s); +char *mystrdup(const char *s); -- 2.56.0