implement child lookup via hash table

7 files changed, 201 insertions, 104 deletions

diff --git a/src/client.c b/src/client.c
index 5930f48..b50e71d 100644
--- a/src/client.c
+++ b/src/client.c
@@ -116,14 +116,18 @@ void sigusr2_handler(int s, siginfo_t *info, void *vp)
     (void) s;
     (void) vp;
 
-    sig_printf("got SIGUSR2\n");
+    sig_printf("PID %d got SIGUSR2\n", getpid());
 
     /* we only listen to requests from our parent */
     if(info->si_pid != getppid())
+    {
+        sig_printf("Unknown PID sent SIGUSR2\n");
         return;
+    }
 
     unsigned char cmd;
     read(from_parent, &cmd, 1);
+    sig_printf("Got data from parent.\n");
     unsigned char buf[MSG_MAX + 1];
     switch(cmd)
     {
@@ -151,6 +155,7 @@ void sigusr2_handler(int s, siginfo_t *info, void *vp)
             out("Cannot go that way.\n");
     }
     case REQ_NOP:
+        sig_printf("NOP from parent.\n");
         break;
     default:
         sig_printf("WARNING: client process received unknown code %d\n", cmd);
diff --git a/src/hash.c b/src/hash.c
index 52a5b93..8e4888a 100644
--- a/src/hash.c
+++ b/src/hash.c
@@ -63,6 +63,49 @@ void hash_free(void *ptr)
     free(map);
 }
 
+void *hash_iterate(void *map, void **saveptr, void **keyptr)
+{
+    struct iterstate_t {
+        struct hash_map *map;
+        struct hash_node *node;
+        unsigned bucket;
+    };
+
+    struct iterstate_t *saved;
+
+    if(map)
+    {
+        *saveptr = malloc(sizeof(struct iterstate_t));
+        saved = *saveptr;
+
+        saved->map = map;
+        saved->bucket = 0;
+        saved->node = NULL;
+    }
+    else
+        saved = *saveptr;
+
+    for(;saved->bucket < saved->map->table_sz; ++(saved->bucket))
+    {
+        do {
+            if(!saved->node)
+                saved->node = saved->map->table[saved->bucket];
+            else
+                saved->node = saved->node->next;
+            if(saved->node)
+            {
+                if(keyptr)
+                    *keyptr = saved->node->key;
+                return (void*)saved->node->data;
+            }
+        } while(saved->node);
+    }
+
+    free(saved);
+
+    return NULL;
+}
+
 void *hash_insert(void *ptr, const void *key, const void *data)
 {
     struct hash_map *map = ptr;
@@ -119,3 +162,44 @@ void hash_insert_pairs(void *ptr, const struct hash_pair *pairs,
         iter += pairsize;
     }
 }
+
+bool hash_remove(void *ptr, void *key)
+{
+    struct hash_map *map = ptr;
+    unsigned hash = map->hash(key) % map->table_sz;
+
+    struct hash_node *iter = map->table[hash], *last = NULL;
+
+    while(iter)
+    {
+        if(map->compare(key, iter->key) == 0)
+        {
+            if(last)
+                last->next = iter->next;
+            else
+                map->table[hash] = iter->next;
+            free(iter);
+            return true;
+        }
+        last = iter;
+        iter = iter->next;
+    }
+
+    return false;
+}
+
+void *hash_getkeyptr(void *ptr, const void *key)
+{
+    struct hash_map *map = ptr;
+    unsigned hash = map->hash(key) % map->table_sz;
+
+    struct hash_node *iter = map->table[hash];
+
+    while(iter)
+    {
+        if(map->compare(key, iter->key) == 0)
+            return (void*)(iter->key);
+        iter = iter->next;
+    }
+    return NULL;
+}
diff --git a/src/hash.h b/src/hash.h
index ae86b26..23586f4 100644
--- a/src/hash.h
+++ b/src/hash.h
@@ -1,3 +1,4 @@
+#include <stdbool.h>
 #include <stddef.h>
 
 /* simple, generic chained hash map implementation */
@@ -17,6 +18,12 @@ void *hash_insert(void*, const void *key, const void *data);
 /* returns NULL if not found */
 void *hash_lookup(void*, const void *key);
 
+bool hash_remove(void *ptr, void *key);
+
+/* use like you would strtok_r */
+/* allocates a buffer that's freed once all elements are processed */
+void *hash_iterate(void *map, void **saved, void **keyptr);
+
 struct hash_pair {
     void *key;
     unsigned char value[0];
@@ -25,6 +32,9 @@ struct hash_pair {
 /* insert n key->pair members of size pairsize */
 void hash_insert_pairs(void*, const struct hash_pair*, size_t pairsize, size_t n);
 
+/* gets the original pointer used to store the tuple */
+void *hash_getkeyptr(void*, const void *key);
+
 #define SIMP_HASH(TYPE, NAME)       \
     unsigned NAME (const void *key) \
     {                               \
diff --git a/src/netcosm.h b/src/netcosm.h
index 94fa42f..c9c4a0f 100644
--- a/src/netcosm.h
+++ b/src/netcosm.h
@@ -116,9 +116,6 @@ struct child_data {
     char *user;
 
     struct in_addr addr;
-
-    /* a linked list works well for this because no random-access is needed */
-    struct child_data *next;
 };
 
 /* the data we get from a world module */
diff --git a/src/room.c b/src/room.c
index fb8d138..18fd37e 100644
--- a/src/room.c
+++ b/src/room.c
@@ -125,11 +125,17 @@ bool world_load(const char *fname, const struct roomdata_t *data, size_t data_sz
     if(magic != WORLD_MAGIC)
         return false;
     read(fd, &world_sz, sizeof(world_sz));
+
     if(world)
+        /* possible memory leak here as strings allocated inside of world
+           aren't freed. avoided by loading only one world per instance */
         free(world);
+
     if(world_sz != data_sz)
         return false;
+
     world = calloc(world_sz, sizeof(struct room_t));
+
     for(unsigned i = 0; i < world_sz; ++i)
     {
         world[i].id = read_roomid(fd);
diff --git a/src/server.c b/src/server.c
index 3476f38..2ea5d1d 100644
--- a/src/server.c
+++ b/src/server.c
@@ -35,7 +35,7 @@ void __attribute__((noreturn)) error(const char *fmt, ...)
 
 /* assume int is atomic */
 volatile int num_clients = 0;
-struct child_data *child_data;
+void *child_map = NULL;
 
 static void sigchld_handler(int s, siginfo_t *info, void *vp)
 {
@@ -50,20 +50,9 @@ static void sigchld_handler(int s, siginfo_t *info, void *vp)
     pid_t pid;
     while((pid = waitpid(-1, NULL, WNOHANG)) > 0)
     {
-        struct child_data *iter = child_data, *last = NULL;
-        while(iter)
-        {
-            if(iter->pid == pid)
-            {
-                if(!last)
-                    child_data = iter->next;
-                else
-                    last->next = iter->next;
-                free(iter);
-                break;
-            }
-            iter = iter->next;
-        }
+        void *key = hash_getkeyptr(child_map, &pid);
+        hash_remove(child_map, &pid);
+        free(key);
     }
 
     errno = saved_errno;
@@ -107,7 +96,9 @@ static void req_pass_msg(unsigned char *data, size_t datalen,
     }
 
     write(child->outpipe[1], data, datalen);
-    kill(child->pid, SIGUSR2);
+
+    if(sender->pid != child->pid)
+        kill(child->pid, SIGUSR2);
 }
 
 static void req_send_clientinfo(unsigned char *data, size_t datalen,
@@ -127,12 +118,17 @@ static void req_send_clientinfo(unsigned char *data, size_t datalen,
     };
 
     if(child->user)
-        len = snprintf(buf, sizeof(buf), "Client %s PID %d [%s] USER %s\n",
+        len = snprintf(buf, sizeof(buf), "Client %s PID %d [%s] USER %s",
                        inet_ntoa(child->addr), child->pid, state[child->state], child->user);
     else
-        len = snprintf(buf, sizeof(buf), "Client %s PID %d [%s]\n",
+        len = snprintf(buf, sizeof(buf), "Client %s PID %d [%s]",
                        inet_ntoa(child->addr), child->pid, state[child->state]);
 
+    if(sender->pid == child->pid)
+        strncat(buf, " [YOU]\n", sizeof(buf));
+    else
+        strncat(buf, "\n", sizeof(buf));
+
     write(sender->outpipe[1], buf, len);
 }
 
@@ -317,80 +313,67 @@ static void sigusr1_handler(int s, siginfo_t *info, void *vp)
     unsigned char cmd, data[MSG_MAX + 1];
     const struct child_request *req = NULL;
     size_t datalen = 0;
-    struct child_data *sender = NULL;
+    struct child_data *sender = hash_lookup(child_map, &sender_pid);
 
-    /* we have to iterate over the linked list twice */
-    /* first to get the data, second to send it to the rest of the children */
+    if(!sender)
+    {
+        printf("WARNING: got SIGUSR1 from unknown PID, ignoring.\n");
+        return;
+    }
 
-    struct child_data *iter = child_data;
+    read(sender->readpipe[0], &cmd, 1);
+    req = hash_lookup(request_map, &cmd);
+    if(!req)
+    {
+        sig_printf("Unknown request.\n");
+        return;
+    }
 
-    while(iter)
+    sig_printf("Got command %d\n", cmd);
+    if(req->havedata)
     {
-        if(!req)
-        {
-            if(iter->pid == sender_pid)
-            {
-                sender = iter;
-                read(iter->readpipe[0], &cmd, 1);
-                req = hash_lookup(request_map, &cmd);
-                if(!req)
-                {
-                    sig_printf("Unknown request.\n");
-                    return;
-                }
-
-                sig_printf("Got command %d\n", cmd);
-                if(req->havedata)
-                {
-                    datalen = read(iter->readpipe[0], data, sizeof(data));
-                }
-
-                write(sender->outpipe[1], &req->cmd_to_send, 1);
-
-                switch(req->which)
-                {
-                case CHILD_SENDER:
-                case CHILD_ALL:
-                    req->handle_child(data, datalen, sender, iter);
-                    if(req->which == CHILD_SENDER)
-                        goto finish;
-                    break;
-                case CHILD_NONE:
-                    goto finish;
-                default:
-                    break;
-                }
-            }
-        }
-        else
-        {
-            switch(req->which)
-            {
-            case CHILD_ALL:
-            case CHILD_ALL_BUT_SENDER:
-                req->handle_child(data, datalen, sender, iter);
-                break;
-            default:
-                break;
-            }
-        }
-        iter = iter->next;
+        datalen = read(sender->readpipe[0], data, sizeof(data));
     }
 
-    /* iterate over the rest of the children, if needed */
-    if(req && req->which != CHILD_SENDER)
+    write(sender->outpipe[1], &req->cmd_to_send, 1);
+
+    switch(req->which)
     {
-        iter = child_data;
-        while(iter)
-        {
-            if(iter->pid == sender_pid)
-                break;
+    case CHILD_SENDER:
+    case CHILD_ALL:
+        req->handle_child(data, datalen, sender, sender);
+        if(req->which == CHILD_SENDER)
+            goto finish;
+        break;
+    case CHILD_NONE:
+        goto finish;
+    default:
+        break;
+    }
 
-            req->handle_child(data, datalen, sender, iter);
+    struct child_data *child = NULL;
+    void *ptr = child_map, *save;
 
-            iter = iter->next;
+    do {
+        pid_t *key;
+        child = hash_iterate(ptr, &save, (void**)&key);
+        ptr = NULL;
+        if(!child)
+            break;
+        sig_printf("Iterating over PID %d\n", *key);
+        if(child->pid == sender->pid)
+            continue;
+
+        switch(req->which)
+        {
+        case CHILD_ALL:
+        case CHILD_ALL_BUT_SENDER:
+            req->handle_child(data, datalen, sender, child);
+            break;
+        default:
+            break;
         }
-    }
+    } while(1);
 
 finish:
 
@@ -402,9 +385,6 @@ finish:
     else
         sig_printf("WARN: unknown child sent request.\n");
 
-    if(!req)
-        sig_printf("WARN: unknown request, request ignored\n");
-
     sig_printf("finished handling client request\n");
 }
 
@@ -487,6 +467,9 @@ static int server_bind(void)
     return sock;
 }
 
+static SIMP_HASH(pid_t, pid_hash);
+static SIMP_EQUAL(pid_t, pid_equal);
+
 int main(int argc, char *argv[])
 {
     if(argc != 2)
@@ -508,7 +491,8 @@ int main(int argc, char *argv[])
 
     reqmap_init();
 
-    child_data = NULL;
+    /* this is set very low to make iteration faster */
+    child_map = hash_init(8, pid_hash, pid_equal);
 
     printf("Listening on port %d\n", port);
 
@@ -558,16 +542,18 @@ int main(int argc, char *argv[])
             close(outpipe[0]);
             close(new_sock);
 
-            /* add the child to the child list */
-            struct child_data *old = child_data;
-            child_data = malloc(sizeof(struct child_data));
-            memcpy(child_data->outpipe, outpipe, sizeof(outpipe));
-            memcpy(child_data->readpipe, readpipe, sizeof(readpipe));
-            child_data->addr = client.sin_addr;
-            child_data->next = old;
-            child_data->pid = pid;
-            child_data->state = STATE_INIT;
-            child_data->user = NULL;
+            /* add the child to the child map */
+            struct child_data *new = calloc(1, sizeof(struct child_data));
+            memcpy(new->outpipe, outpipe, sizeof(outpipe));
+            memcpy(new->readpipe, readpipe, sizeof(readpipe));
+            new->addr = client.sin_addr;
+            new->pid = pid;
+            new->state = STATE_INIT;
+            new->user = NULL;
+
+            pid_t *pidbuf = malloc(sizeof(pid_t));
+            *pidbuf = pid;
+            hash_insert(child_map, pidbuf, new);
         }
     }
 }
diff --git a/src/test.c b/src/test.c
index 23a7530..95129e5 100644
--- a/src/test.c
+++ b/src/test.c
@@ -1,10 +1,19 @@
 #include "hash.h"
 #include <string.h>
+#include <stdio.h>
 
 int main()
 {
-    struct hash_map *map = hash_init(10, hash_djb, strcmp);
-    hash_insert(map, "a", 42);
-    hash_insert(map, "b", 32);
-    printf("weird. %d\n", hash_lookup(map, "a"));
+    void *map = hash_init(10000, hash_djb, compare_strings);
+    hash_insert(map, "a",1);
+    hash_insert(map, "b",2);
+    void *ptr = map;
+    void *data = NULL;
+    void *save;
+    do {
+        char *key;
+        data = hash_iterate(ptr, &save, &key);
+        ptr = NULL;
+        printf("%d %s\n", data, key);
+    } while(data);
 }