aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--TODO.txt1
-rw-r--r--hashtable.c149
-rw-r--r--hashtable.h15
-rw-r--r--main.c53
4 files changed, 190 insertions, 28 deletions
diff --git a/TODO.txt b/TODO.txt
index cd20675..1f09bca 100644
--- a/TODO.txt
+++ b/TODO.txt
@@ -5,4 +5,3 @@
- A session is marked inactive 2 minutes after the latest activity on that session. Make the number "2" configurable and not a hard-coded constant.
- Use poll(2), not select(2)
- Fix OOM dos vector
-- Sub-linear hash table of conn_data's in main.c
diff --git a/hashtable.c b/hashtable.c
new file mode 100644
index 0000000..ea0f0fc
--- /dev/null
+++ b/hashtable.c
@@ -0,0 +1,149 @@
+#include <limits.h>
+#include "hashtable.h"
+#include "global.h"
+
+
+// Generated by starting with 5, then repeatedly taking the smallest prime at
+// least double the previous number.
+// This array must end well before UINT64_MAX, so that the occupancy percentage
+// computation does not overflow.
+static const size_t doubling_primes[] = {
+ 5, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853, 25717, 51437,
+ 102877, 205759, 411527, 823117, 1646237, 3292489, 6584983, 13169977,
+ 26339969, 52679969, 105359939, 210719881, 421439783, 842879579
+};
+#define NUM_DOUBLING_PRIMES ((size_t)(sizeof(doubling_primes) / sizeof(doubling_primes[0])))
+
+
+struct keyvalue {
+ unsigned int key;
+ void *value;
+};
+
+struct bucket {
+ int cap, len;
+ struct keyvalue *pairs;
+};
+
+struct hashtable {
+ // modulus == doubling_primes[modulus_index]
+ size_t modulus_index, modulus;
+ size_t num_values;
+ struct bucket *table;
+};
+
+static void ht_nullify(struct hashtable *ht) {
+ for (size_t i = 0; i < ht->modulus; i++) {
+ free(ht->table[i].pairs); // noop if values == NULL
+ }
+ free(ht->table);
+}
+
+static void ht_grow(struct hashtable *ht) {
+ static bool nested_grow = false;
+
+ // See the ht_insert() call below
+ if (nested_grow) {
+ die("Unexpected nested ht_grow() in ht_insert()");
+ }
+
+ if (ht->modulus_index == NUM_DOUBLING_PRIMES - 1) {
+ // TODO: fail more gracefully
+ die("Hashtable full, cannot insert");
+ }
+
+ struct hashtable newht;
+ newht.modulus_index = ht->modulus_index + 1;
+ newht.modulus = doubling_primes[newht.modulus_index];
+ newht.num_values = 0;
+ newht.table = calloc(newht.modulus, struct bucket);
+
+ debug("ht: growing from %zu to %zu", ht->modulus, newht.modulus);
+
+ for (size_t i = 0; i < ht->modulus; i++) {
+ const struct bucket *bucket = &ht->table[i];
+ for (int j = 0; j < bucket->len; j++) {
+ const struct keyvalue *pair = &bucket->pairs[j];
+ // A priori, this could recursively call ht_grow() on the new
+ // table. However, this is in practice impossible, because growing
+ // occurs at 60% occupancy, and we only just surpassed that with
+ // the old size -- and we just doubled the size. Therefore,
+ // recursively arriving here in ht_grow() should be impossible.
+ // This is dynamically checked using the nested_grow static
+ // boolean.
+ ht_insert(&newht, pair->key, pair->value);
+ }
+ }
+
+ ht_nullify(ht);
+ *ht = newht;
+}
+
+struct hashtable* ht_alloc() {
+ struct hashtable *ht = malloc(1, struct hashtable);
+ ht->modulus_index = 0;
+ ht->modulus = doubling_primes[ht->modulus_index];
+ ht->num_values = 0;
+ ht->table = calloc(ht->modulus, struct bucket);
+ return ht;
+}
+
+void ht_free(struct hashtable *ht) {
+ ht_nullify(ht);
+ free(ht);
+}
+
+void ht_insert(struct hashtable *ht, unsigned int key, void *value) {
+ struct bucket *bucket = &ht->table[key % ht->modulus];
+
+ debug("ht: insert num_values=%zu key=%u bucket: cap=%d len=%d", ht->num_values, key, bucket->cap, bucket->len);
+
+ if (bucket->cap == 0) {
+ bucket->cap = 1;
+ bucket->pairs = malloc(bucket->cap, struct keyvalue);
+ } else if (bucket->len == bucket->cap) {
+ if (bucket->cap > INT_MAX / 2) {
+ die("Hashtable has degraded so far it's not funny anymore");
+ }
+ bucket->cap *= 2;
+ bucket->pairs = realloc(bucket->pairs, bucket->cap, struct keyvalue);
+ }
+
+ bucket->pairs[bucket->len].key = key;
+ bucket->pairs[bucket->len].value = value;
+ bucket->len++;
+ ht->num_values++;
+
+ // Reallocate at >60% occupation (counting colliding keys double).
+ // Note that this does not overflow since the last entry in doubling_primes
+ // is only on the order of 10^9.
+ if (5 * ht->num_values > 3 * ht->modulus) {
+ ht_grow(ht);
+ }
+}
+
+void* ht_find(const struct hashtable *ht, unsigned int key) {
+ struct bucket *bucket = &ht->table[key % ht->modulus];
+ for (int i = 0; i < bucket->len; i++) {
+ if (bucket->pairs[i].key == key) {
+ return bucket->pairs[i].value;
+ }
+ }
+ return NULL;
+}
+
+void ht_delete(struct hashtable *ht, unsigned int key) {
+ struct bucket *bucket = &ht->table[key % ht->modulus];
+ for (int i = 0; i < bucket->len; i++) {
+ if (bucket->pairs[i].key == key) {
+ debug("ht: delete key=%u bucket: cap=%d len=%d i=%d", key, bucket->cap, bucket->len, i);
+ if (i < bucket->len - 1) {
+ bucket->pairs[i] = bucket->pairs[bucket->len - 1];
+ }
+ bucket->len--;
+ ht->num_values--;
+ return;
+ }
+ }
+ debug("ht: delete key=%u not found", key);
+}
diff --git a/hashtable.h b/hashtable.h
new file mode 100644
index 0000000..b85c2e0
--- /dev/null
+++ b/hashtable.h
@@ -0,0 +1,15 @@
+#pragma once
+
+
+struct hashtable;
+
+struct hashtable* ht_alloc();
+void ht_free(struct hashtable *ht);
+
+void ht_insert(struct hashtable *ht, unsigned int key, void *value);
+
+// Returns NULL if key is not present in the table.
+void* ht_find(const struct hashtable *ht, unsigned int key);
+
+// Does nothing if the key is not present in the table.
+void ht_delete(struct hashtable *ht, unsigned int key);
diff --git a/main.c b/main.c
index 03bf7b0..b925cd1 100644
--- a/main.c
+++ b/main.c
@@ -19,6 +19,7 @@
#include "plugin.h"
#include "runloop.h"
#include "user_data.h"
+#include "hashtable.h"
#define PORT (29536) // python: int("msg",36)
@@ -39,39 +40,35 @@ static int create_server_socket(void){
return sock;
}
-struct hash_item{
- struct conn_data cd;
- struct hash_item *next;
-};
+static struct hashtable *conn_hash = NULL;
-#define CONN_HASH_SIZE (16)
-static struct hash_item *conn_hash[CONN_HASH_SIZE];
+static void conn_hash_init(void) {
+ conn_hash = ht_alloc();
+}
+
+static void add_conn_data(int fd, struct conn_data *item) {
+ ht_insert(conn_hash, fd, item);
+}
static struct conn_data* find_conn_data(int fd){
- struct hash_item *item=conn_hash[fd%CONN_HASH_SIZE];
- while(item&&item->cd.fd!=fd)item=item->next;
+ struct conn_data *item = (struct conn_data*)ht_find(conn_hash, fd);
assert(item);
- return &item->cd;
+ return item;
}
static void delete_conn_data(int fd){
debug("Deleting conn_data for fd=%d",fd);
- struct hash_item *item=conn_hash[fd%CONN_HASH_SIZE];
- assert(item);
- struct hash_item *parent=NULL;
- while(item&&item->cd.fd!=fd){
- parent=item;
- item=item->next;
- }
- assert(item);
- if(item->cd.userid!=-1){
- userdata_unregister(item->cd.userid,fd);
- broadcast_online_change(item->cd.userid);
+
+ struct conn_data *item = find_conn_data(fd);
+
+ if (item->userid != -1) {
+ userdata_unregister(item->userid, fd);
+ broadcast_online_change(item->userid);
}
- conn_data_nullify(&item->cd);
- if(parent)parent->next=item->next;
- else conn_hash[fd%CONN_HASH_SIZE]=item->next;
+ conn_data_nullify(item);
free(item);
+
+ ht_delete(conn_hash, fd);
}
static bool client_socket_callback(int fd){
@@ -116,10 +113,10 @@ static bool server_socket_callback(int fd){
if(sock<0)die_perror("accept");
runloop_add_fd(sock,client_socket_callback,true);
- struct hash_item *item=malloc(1,struct hash_item);
- conn_data_init(&item->cd,sock);
- item->next=conn_hash[sock%CONN_HASH_SIZE];
- conn_hash[sock%CONN_HASH_SIZE]=item;
+ struct conn_data *item = malloc(1, struct conn_data);
+ conn_data_init(item, sock);
+ add_conn_data(sock, item);
+
debug("Added conn_data for fd=%d",sock);
return false;
}
@@ -167,6 +164,8 @@ int main(int argc,char **argv){
signal(SIGPIPE,signal_handler);
+ conn_hash_init();
+
plugin_init();
for(int i=1;i<argc;i++){
plugin_register(argv[i]);
generated by cgit v1.2.3-70-g09d2 (git 2.51.0) at 2025-10-31 19:15:10 +0100