1 files changed, 156 insertions, 0 deletions
diff --git a/web/server/h2o/connlist.c b/web/server/h2o/connlist.c
new file mode 100644
index 00000000..272e65ca
--- /dev/null
+++ b/web/server/h2o/connlist.c
@@ -0,0 +1,156 @@
+#include "connlist.h"
+
+conn_list_t conn_list = { NULL, NULL, 0, 0, PTHREAD_MUTEX_INITIALIZER };
+
+static h2o_stream_conn_t **conn_list_get_null_element_unsafe(conn_list_t *list)
+{
+    struct conn_list_leaf *leaf = list->head;
+    while (leaf != NULL) {
+        for (int i = 0; i < CONN_LIST_MEMPOOL_SIZE; i++) {
+            if (leaf->conn[i] == NULL)
+                return &leaf->conn[i];
+        }
+        leaf = leaf->next;
+    }
+    return NULL;
+}
+
+void conn_list_insert(conn_list_t *list, h2o_stream_conn_t *conn)
+{
+    pthread_mutex_lock(&list->lock);
+
+    // in case the allocated capacity is not used up
+    // we can reuse the null element
+    if (list->capacity != list->size) {
+        h2o_stream_conn_t **null_element = conn_list_get_null_element_unsafe(list);
+        if (unlikely(null_element == NULL)) {
+            pthread_mutex_unlock(&list->lock);
+            error_report("conn_list_insert: capacity != size but no null element found");
+            return;
+        }
+        *null_element = conn;
+        list->size++;
+        pthread_mutex_unlock(&list->lock);
+        return;
+    }
+
+    // if not, we need to allocate a new leaf
+    struct conn_list_leaf *old_tail = list->tail;
+    list->tail = callocz(1, sizeof(struct conn_list_leaf));
+    if (unlikely(old_tail == NULL))
+        list->head = list->tail;
+    else
+        old_tail->next = list->tail;
+    
+    list->tail->conn[0] = conn;
+    list->size++;
+    list->capacity += CONN_LIST_MEMPOOL_SIZE;
+
+    pthread_mutex_unlock(&list->lock);
+}
+
+typedef struct {
+    conn_list_t *list;
+    struct conn_list_leaf *leaf;
+    int idx;
+} conn_list_iter_t;
+
+static inline void conn_list_iter_create_unsafe(conn_list_iter_t *iter, conn_list_t *list)
+{
+    iter->list = list;
+    iter->leaf = list->head;
+    iter->idx = 0;
+}
+
+static inline int conn_list_iter_next_unsafe(conn_list_iter_t *iter, h2o_stream_conn_t **conn)
+{
+    if (unlikely(iter->idx == iter->list->capacity))
+        return 0;
+
+    if (iter->idx && iter->idx % CONN_LIST_MEMPOOL_SIZE == 0) {
+        iter->leaf = iter->leaf->next;
+    }
+
+    *conn = iter->leaf->conn[iter->idx++ % CONN_LIST_MEMPOOL_SIZE];
+    return 1;
+}
+
+void conn_list_iter_all(conn_list_t *list, void (*cb)(h2o_stream_conn_t *conn))
+{
+    pthread_mutex_lock(&list->lock);
+    conn_list_iter_t iter;
+    conn_list_iter_create_unsafe(&iter, list);
+    h2o_stream_conn_t *conn;
+    while (conn_list_iter_next_unsafe(&iter, &conn)) {
+        if (conn == NULL)
+            continue;
+        cb(conn);
+    }
+    pthread_mutex_unlock(&list->lock);
+}
+
+static void conn_list_garbage_collect_unsafe(conn_list_t *list)
+{
+    if (list->capacity - list->size > CONN_LIST_MEMPOOL_SIZE) {
+        struct conn_list_leaf *new_tail = list->head;
+        while (new_tail->next != list->tail)
+            new_tail = new_tail->next;
+
+        // check if the tail leaf is empty and move the data if not
+        for (int i = 0; i < CONN_LIST_MEMPOOL_SIZE; i++) {
+            if (list->tail->conn[i] != NULL) {
+                h2o_stream_conn_t **null_element = conn_list_get_null_element_unsafe(list);
+                if (unlikely(null_element == NULL)) {
+                    error_report("conn_list_garbage_collect_unsafe: list->capacity - list->size > CONN_LIST_MEMPOOL_SIZE but no null element found?");
+                    return;
+                }
+                *null_element = list->tail->conn[i];
+                list->tail->conn[i] = NULL;
+            }
+        }
+
+        freez(list->tail);
+        new_tail->next = NULL;
+        list->tail = new_tail;
+        list->capacity -= CONN_LIST_MEMPOOL_SIZE;
+    }
+}
+
+static inline int conn_list_iter_remove(conn_list_iter_t *iter, h2o_stream_conn_t *conn)
+{
+    if (unlikely(iter->idx == iter->list->capacity))
+        return -1;
+
+    if (iter->idx && iter->idx % CONN_LIST_MEMPOOL_SIZE == 0) {
+        iter->leaf = iter->leaf->next;
+    }
+
+    if(conn == iter->leaf->conn[iter->idx % CONN_LIST_MEMPOOL_SIZE]) {
+        iter->leaf->conn[iter->idx % CONN_LIST_MEMPOOL_SIZE] = NULL;
+
+        iter->idx++;
+        return 1;
+    }
+
+    iter->idx++;
+    return 0;
+}
+
+int conn_list_remove_conn(conn_list_t *list, h2o_stream_conn_t *conn)
+{
+    pthread_mutex_lock(&list->lock);
+    conn_list_iter_t iter;
+    conn_list_iter_create_unsafe(&iter, list);
+    int rc;
+    while (!(rc = conn_list_iter_remove(&iter, conn)));
+    if (rc == -1) {
+        pthread_mutex_unlock(&list->lock);
+        error_report("conn_list_remove_conn: conn not found");
+        return 0;
+    }
+    list->size--;
+    conn_list_garbage_collect_unsafe(list);
+    pthread_mutex_unlock(&list->lock);
+    return 1;
+}
+