aboutsummaryrefslogtreecommitdiff
path: root/src/core
diff options
context:
space:
mode:
Diffstat (limited to 'src/core')
-rw-r--r--src/core/ngx_core.h1
-rw-r--r--src/core/ngx_rbtree.c296
-rw-r--r--src/core/ngx_rbtree.h36
-rw-r--r--src/core/ngx_times.c9
-rw-r--r--src/core/ngx_times.h11
5 files changed, 347 insertions, 6 deletions
diff --git a/src/core/ngx_core.h b/src/core/ngx_core.h
index 5b76d86c7..97819b6ff 100644
--- a/src/core/ngx_core.h
+++ b/src/core/ngx_core.h
@@ -30,6 +30,7 @@ typedef struct ngx_connection_s ngx_connection_t;
#include <ngx_files.h>
#include <ngx_crc.h>
#include <ngx_regex.h>
+#include <ngx_rbtree.h>
#include <ngx_times.h>
#include <ngx_inet.h>
#include <ngx_conf_file.h>
diff --git a/src/core/ngx_rbtree.c b/src/core/ngx_rbtree.c
new file mode 100644
index 000000000..2bc4650f0
--- /dev/null
+++ b/src/core/ngx_rbtree.c
@@ -0,0 +1,296 @@
+
+#include <ngx_config.h>
+#include <ngx_core.h>
+
+
+/*
+ * The code is based on the algorithm described in the "Introduction
+ * to Algorithms" by Cormen, Leiserson and Rivest.
+ */
+
+#define ngx_rbt_red(node) ((uintptr_t) (node)->data |= 1)
+#define ngx_rbt_black(node) ((uintptr_t) (node)->data &= ~1)
+#define ngx_rbt_is_red(node) ((uintptr_t) (node)->data & 1)
+#define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node))
+#define ngx_rbt_copy_color(n1, n2) \
+ ((uintptr_t) (n1)->data |= (uintptr_t) (n2)->data & 1)
+
+
+ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node);
+ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root,
+ ngx_rbtree_t *node);
+
+ngx_rbtree_t sentinel;
+
+
+void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node)
+{
+ ngx_rbtree_t *temp;
+
+ /* a binary tree insert */
+
+ if (*root == &sentinel) {
+ node->parent = &sentinel;
+ node->left = &sentinel;
+ node->right = &sentinel;
+ ngx_rbt_black(node);
+ *root = node;
+
+ return;
+ }
+
+ temp = *root;
+
+ for ( ;; ) {
+ if (node->key < temp->key) {
+ if (temp->left == &sentinel) {
+ temp->left = node;
+ break;
+ }
+
+ temp = temp->left;
+ continue;
+ }
+
+ if (temp->right == &sentinel) {
+ temp->right = node;
+ break;
+ }
+
+ temp = temp->right;
+ continue;
+ }
+
+ node->parent = temp;
+ node->left = &sentinel;
+ node->right = &sentinel;
+
+
+ /* re-balance tree */
+
+ ngx_rbt_red(node);
+
+ while (node->parent && 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, node);
+ }
+
+ ngx_rbt_black(node->parent);
+ ngx_rbt_red(node->parent->parent);
+ ngx_rbtree_right_rotate(root, 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, node);
+ }
+
+ ngx_rbt_black(node->parent);
+ ngx_rbt_red(node->parent->parent);
+ ngx_rbtree_left_rotate(root, node->parent->parent);
+ }
+ }
+
+ }
+
+ ngx_rbt_black(*root);
+}
+
+
+void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node)
+{
+ ngx_rbtree_t *subst, *temp, *w;
+
+ /* a binary tree delete */
+
+ if (node->left == &sentinel || node->right == &sentinel) {
+ subst = node;
+
+ } else {
+
+ /* find a node successor */
+
+ if (node->right == &sentinel) {
+ temp = node;
+ subst = node->parent;
+
+ while (subst != &sentinel && temp == subst->right) {
+ temp = subst;
+ subst = subst->parent;
+ }
+
+ } else {
+ subst = ngx_rbtree_min(node->right);
+ }
+ }
+
+ if (subst->left != &sentinel) {
+ temp = subst->left;
+ } else {
+ temp = subst->right;
+ }
+
+ temp->parent = subst->parent;
+
+ if (subst->parent == &sentinel) {
+ *root = temp;
+
+ } else if (subst == subst->parent->left) {
+ subst->parent->left = temp;
+
+ } else {
+ subst->parent->right = temp;
+ }
+
+ if (subst != node) {
+ node->key = subst->key;
+ node->data = subst->data;
+ }
+
+ if (ngx_rbt_is_red(subst)) {
+ return;
+ }
+
+ /* a delete fixup */
+
+ while (temp->parent != &sentinel && 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, 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, 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, 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, temp->parent);
+ w = temp->parent->left;
+ }
+
+ if (ngx_rbt_is_black(w->right) && ngx_rbt_is_black(w->left)) {
+ 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, 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, temp->parent);
+ temp = *root;
+ }
+ }
+ }
+
+ ngx_rbt_black(temp);
+}
+
+
+ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node)
+{
+ ngx_rbtree_t *temp;
+
+ temp = node->right;
+ node->right = temp->left;
+
+ if (temp->left != &sentinel) {
+ temp->left->parent = node;
+ }
+
+ temp->parent = node->parent;
+
+ if (node->parent == &sentinel) {
+ *root = temp;
+
+ } else if (node == node->parent->left) {
+ node->parent->left = temp;
+
+ } else {
+ node->parent->right = temp;
+ }
+
+ temp->left = node;
+ node->parent = temp;
+}
+
+
+ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, ngx_rbtree_t *node)
+{
+ ngx_rbtree_t *temp;
+
+ temp = node->left;
+ node->left = temp->right;
+
+ if (temp->right != &sentinel) {
+ temp->right->parent = node;
+ }
+
+ temp->parent = node->parent;
+
+ if (node->parent == &sentinel) {
+ *root = temp;
+
+ } else if (node == node->parent->right) {
+ node->parent->right = temp;
+
+ } else {
+ node->parent->left = temp;
+ }
+
+ temp->right = node;
+ node->parent = temp;
+}
diff --git a/src/core/ngx_rbtree.h b/src/core/ngx_rbtree.h
new file mode 100644
index 000000000..de6fef904
--- /dev/null
+++ b/src/core/ngx_rbtree.h
@@ -0,0 +1,36 @@
+#ifndef _NGX_RBTREE_H_INCLUDED_
+#define _NGX_RBTREE_H_INCLUDED_
+
+
+#include <ngx_config.h>
+#include <ngx_core.h>
+
+
+typedef struct ngx_rbtree_s ngx_rbtree_t;
+
+struct ngx_rbtree_s {
+ ngx_int_t key;
+ ngx_rbtree_t *left;
+ ngx_rbtree_t *right;
+ ngx_rbtree_t *parent;
+ void *data;
+};
+
+extern ngx_rbtree_t sentinel;
+
+
+void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *node);
+void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *node);
+
+
+ngx_inline static ngx_rbtree_t *ngx_rbtree_min(ngx_rbtree_t *root)
+{
+ while (root->left != &sentinel) {
+ root = root->left;
+ }
+
+ return root;
+}
+
+
+#endif /* _NGX_RBTREE_H_INCLUDED_ */
diff --git a/src/core/ngx_times.c b/src/core/ngx_times.c
index e1706baa2..12dc229c0 100644
--- a/src/core/ngx_times.c
+++ b/src/core/ngx_times.c
@@ -3,9 +3,11 @@
#include <ngx_core.h>
-time_t ngx_cached_time;
+time_t ngx_cached_time;
+ngx_epoch_msec_t ngx_elapsed_msec;
+ngx_epoch_msec_t ngx_start_msec;
-ngx_tm_t ngx_cached_gmtime;
+ngx_tm_t ngx_cached_gmtime;
static char cached_err_log_time[] = "1970/09/28 12:00:00";
ngx_str_t ngx_cached_err_log_time;
@@ -37,6 +39,9 @@ void ngx_time_init()
ngx_gettimeofday(&tv);
ngx_cached_time = tv.tv_sec;
+ ngx_start_msec = tv.tv_sec * 1000 + tv.tv_usec / 1000;
+ ngx_elapsed_msec = 0;
+
ngx_time_update();
}
diff --git a/src/core/ngx_times.h b/src/core/ngx_times.h
index b765dd8e0..6ff316d3f 100644
--- a/src/core/ngx_times.h
+++ b/src/core/ngx_times.h
@@ -14,10 +14,13 @@ void ngx_gmtime(time_t t, ngx_tm_t *tp);
#define ngx_time() ngx_cached_time
-extern time_t ngx_cached_time;
-extern ngx_str_t ngx_cached_err_log_time;
-extern ngx_str_t ngx_cached_http_time;
-extern ngx_str_t ngx_cached_http_log_time;
+extern time_t ngx_cached_time;
+extern ngx_epoch_msec_t ngx_elapsed_msec;
+extern ngx_epoch_msec_t ngx_start_msec;
+
+extern ngx_str_t ngx_cached_err_log_time;
+extern ngx_str_t ngx_cached_http_time;
+extern ngx_str_t ngx_cached_http_log_time;
#endif /* _NGX_TIMES_H_INCLUDED_ */
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-19 17:29:00 +0000