From e18a033b921d0d79fa8278f853548e6125b93e0c Mon Sep 17 00:00:00 2001
From: Konstantin Ananyev <konstantin.ananyev@intel.com>
Date: Tue, 31 Oct 2017 12:40:17 +0000
Subject: Integrate TLDK with NGINX

Created a clone of nginx (from https://github.com/nginx/nginx)
to demonstrate and benchmark TLDK library integrated with real
world application.
A new nginx module is created and and BSD socket-like API is implemented
on top of native TLDK API.
Note, that right now only minimalistic subset of socket-like API is provided:
- accept
- close
- readv
- recv
- writev
so only limited nginx functionality is available for a moment.

Change-Id: Ie1efe9349a0538da4348a48fb8306cbf636b5a92
Signed-off-by: Mohammad Abdul Awal <mohammad.abdul.awal@intel.com>
Signed-off-by: Reshma Pattan <reshma.pattan@intel.com>
Signed-off-by: Remy Horton <remy.horton@intel.com>
Signed-off-by: Konstantin Ananyev <konstantin.ananyev@intel.com>
---
 app/nginx/src/core/ngx_rbtree.c | 409 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 409 insertions(+)
 create mode 100644 app/nginx/src/core/ngx_rbtree.c

(limited to 'app/nginx/src/core/ngx_rbtree.c')

diff --git a/app/nginx/src/core/ngx_rbtree.c b/app/nginx/src/core/ngx_rbtree.c
new file mode 100644
index 0000000..969d549
--- /dev/null
+++ b/app/nginx/src/core/ngx_rbtree.c
@@ -0,0 +1,409 @@
+
+/*
+ * Copyright (C) Igor Sysoev
+ * Copyright (C) Nginx, Inc.
+ */
+
+
+#include <ngx_config.h>
+#include <ngx_core.h>
+
+
+/*
+ * The red-black tree code is based on the algorithm described in
+ * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
+ */
+
+
+static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,
+    ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
+static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,
+    ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
+
+
+void
+ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
+{
+    ngx_rbtree_node_t  **root, *temp, *sentinel;
+
+    /* a binary tree insert */
+
+    root = &tree->root;
+    sentinel = tree->sentinel;
+
+    if (*root == sentinel) {
+        node->parent = NULL;
+        node->left = sentinel;
+        node->right = sentinel;
+        ngx_rbt_black(node);
+        *root = node;
+
+        return;
+    }
+
+    tree->insert(*root, node, sentinel);
+
+    /* re-balance tree */
+
+    while (node != *root && ngx_rbt_is_red(node->parent)) {
+
+        if (node->parent == node->parent->parent->left) {
+            temp = node->parent->parent->right;
+
+            if (ngx_rbt_is_red(temp)) {
+                ngx_rbt_black(node->parent);
+                ngx_rbt_black(temp);
+                ngx_rbt_red(node->parent->parent);
+                node = node->parent->parent;
+
+            } else {
+                if (node == node->parent->right) {
+                    node = node->parent;
+                    ngx_rbtree_left_rotate(root, sentinel, node);
+                }
+
+                ngx_rbt_black(node->parent);
+                ngx_rbt_red(node->parent->parent);
+                ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
+            }
+
+        } else {
+            temp = node->parent->parent->left;
+
+            if (ngx_rbt_is_red(temp)) {
+                ngx_rbt_black(node->parent);
+                ngx_rbt_black(temp);
+                ngx_rbt_red(node->parent->parent);
+                node = node->parent->parent;
+
+            } else {
+                if (node == node->parent->left) {
+                    node = node->parent;
+                    ngx_rbtree_right_rotate(root, sentinel, node);
+                }
+
+                ngx_rbt_black(node->parent);
+                ngx_rbt_red(node->parent->parent);
+                ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
+            }
+        }
+    }
+
+    ngx_rbt_black(*root);
+}
+
+
+void
+ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
+    ngx_rbtree_node_t *sentinel)
+{
+    ngx_rbtree_node_t  **p;
+
+    for ( ;; ) {
+
+        p = (node->key < temp->key) ? &temp->left : &temp->right;
+
+        if (*p == sentinel) {
+            break;
+        }
+
+        temp = *p;
+    }
+
+    *p = node;
+    node->parent = temp;
+    node->left = sentinel;
+    node->right = sentinel;
+    ngx_rbt_red(node);
+}
+
+
+void
+ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
+    ngx_rbtree_node_t *sentinel)
+{
+    ngx_rbtree_node_t  **p;
+
+    for ( ;; ) {
+
+        /*
+         * Timer values
+         * 1) are spread in small range, usually several minutes,
+         * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
+         * The comparison takes into account that overflow.
+         */
+
+        /*  node->key < temp->key */
+
+        p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0)
+            ? &temp->left : &temp->right;
+
+        if (*p == sentinel) {
+            break;
+        }
+
+        temp = *p;
+    }
+
+    *p = node;
+    node->parent = temp;
+    node->left = sentinel;
+    node->right = sentinel;
+    ngx_rbt_red(node);
+}
+
+
+void
+ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
+{
+    ngx_uint_t           red;
+    ngx_rbtree_node_t  **root, *sentinel, *subst, *temp, *w;
+
+    /* a binary tree delete */
+
+    root = &tree->root;
+    sentinel = tree->sentinel;
+
+    if (node->left == sentinel) {
+        temp = node->right;
+        subst = node;
+
+    } else if (node->right == sentinel) {
+        temp = node->left;
+        subst = node;
+
+    } else {
+        subst = ngx_rbtree_min(node->right, sentinel);
+
+        if (subst->left != sentinel) {
+            temp = subst->left;
+        } else {
+            temp = subst->right;
+        }
+    }
+
+    if (subst == *root) {
+        *root = temp;
+        ngx_rbt_black(temp);
+
+        /* DEBUG stuff */
+        node->left = NULL;
+        node->right = NULL;
+        node->parent = NULL;
+        node->key = 0;
+
+        return;
+    }
+
+    red = ngx_rbt_is_red(subst);
+
+    if (subst == subst->parent->left) {
+        subst->parent->left = temp;
+
+    } else {
+        subst->parent->right = temp;
+    }
+
+    if (subst == node) {
+
+        temp->parent = subst->parent;
+
+    } else {
+
+        if (subst->parent == node) {
+            temp->parent = subst;
+
+        } else {
+            temp->parent = subst->parent;
+        }
+
+        subst->left = node->left;
+        subst->right = node->right;
+        subst->parent = node->parent;
+        ngx_rbt_copy_color(subst, node);
+
+        if (node == *root) {
+            *root = subst;
+
+        } else {
+            if (node == node->parent->left) {
+                node->parent->left = subst;
+            } else {
+                node->parent->right = subst;
+            }
+        }
+
+        if (subst->left != sentinel) {
+            subst->left->parent = subst;
+        }
+
+        if (subst->right != sentinel) {
+            subst->right->parent = subst;
+        }
+    }
+
+    /* DEBUG stuff */
+    node->left = NULL;
+    node->right = NULL;
+    node->parent = NULL;
+    node->key = 0;
+
+    if (red) {
+        return;
+    }
+
+    /* a delete fixup */
+
+    while (temp != *root && ngx_rbt_is_black(temp)) {
+
+        if (temp == temp->parent->left) {
+            w = temp->parent->right;
+
+            if (ngx_rbt_is_red(w)) {
+                ngx_rbt_black(w);
+                ngx_rbt_red(temp->parent);
+                ngx_rbtree_left_rotate(root, sentinel, temp->parent);
+                w = temp->parent->right;
+            }
+
+            if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
+                ngx_rbt_red(w);
+                temp = temp->parent;
+
+            } else {
+                if (ngx_rbt_is_black(w->right)) {
+                    ngx_rbt_black(w->left);
+                    ngx_rbt_red(w);
+                    ngx_rbtree_right_rotate(root, sentinel, w);
+                    w = temp->parent->right;
+                }
+
+                ngx_rbt_copy_color(w, temp->parent);
+                ngx_rbt_black(temp->parent);
+                ngx_rbt_black(w->right);
+                ngx_rbtree_left_rotate(root, sentinel, temp->parent);
+                temp = *root;
+            }
+
+        } else {
+            w = temp->parent->left;
+
+            if (ngx_rbt_is_red(w)) {
+                ngx_rbt_black(w);
+                ngx_rbt_red(temp->parent);
+                ngx_rbtree_right_rotate(root, sentinel, temp->parent);
+                w = temp->parent->left;
+            }
+
+            if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
+                ngx_rbt_red(w);
+                temp = temp->parent;
+
+            } else {
+                if (ngx_rbt_is_black(w->left)) {
+                    ngx_rbt_black(w->right);
+                    ngx_rbt_red(w);
+                    ngx_rbtree_left_rotate(root, sentinel, w);
+                    w = temp->parent->left;
+                }
+
+                ngx_rbt_copy_color(w, temp->parent);
+                ngx_rbt_black(temp->parent);
+                ngx_rbt_black(w->left);
+                ngx_rbtree_right_rotate(root, sentinel, temp->parent);
+                temp = *root;
+            }
+        }
+    }
+
+    ngx_rbt_black(temp);
+}
+
+
+static ngx_inline void
+ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
+    ngx_rbtree_node_t *node)
+{
+    ngx_rbtree_node_t  *temp;
+
+    temp = node->right;
+    node->right = temp->left;
+
+    if (temp->left != sentinel) {
+        temp->left->parent = node;
+    }
+
+    temp->parent = node->parent;
+
+    if (node == *root) {
+        *root = temp;
+
+    } else if (node == node->parent->left) {
+        node->parent->left = temp;
+
+    } else {
+        node->parent->right = temp;
+    }
+
+    temp->left = node;
+    node->parent = temp;
+}
+
+
+static ngx_inline void
+ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
+    ngx_rbtree_node_t *node)
+{
+    ngx_rbtree_node_t  *temp;
+
+    temp = node->left;
+    node->left = temp->right;
+
+    if (temp->right != sentinel) {
+        temp->right->parent = node;
+    }
+
+    temp->parent = node->parent;
+
+    if (node == *root) {
+        *root = temp;
+
+    } else if (node == node->parent->right) {
+        node->parent->right = temp;
+
+    } else {
+        node->parent->left = temp;
+    }
+
+    temp->right = node;
+    node->parent = temp;
+}
+
+
+ngx_rbtree_node_t *
+ngx_rbtree_next(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
+{
+    ngx_rbtree_node_t  *root, *sentinel, *parent;
+
+    sentinel = tree->sentinel;
+
+    if (node->right != sentinel) {
+        return ngx_rbtree_min(node->right, sentinel);
+    }
+
+    root = tree->root;
+
+    for ( ;; ) {
+        parent = node->parent;
+
+        if (node == root) {
+            return NULL;
+        }
+
+        if (node == parent->left) {
+            return parent;
+        }
+
+        node = parent;
+    }
+}
-- 
cgit 1.2.3-korg