nginx-0.0.1-2003-12-04-17:53:00 import
diff --git a/auto/sources b/auto/sources
index 14bb80d..fa2b2df 100644
--- a/auto/sources
+++ b/auto/sources
@@ -16,6 +16,7 @@
src/core/ngx_file.h \
src/core/ngx_crc.h \
src/core/ngx_regex.h \
+ src/core/ngx_rbtree.h \
src/core/ngx_times.h \
src/core/ngx_connection.h \
src/core/ngx_conf_file.h \
@@ -32,6 +33,7 @@
src/core/ngx_inet.c \
src/core/ngx_file.c \
src/core/ngx_regex.c \
+ src/core/ngx_rbtree.c \
src/core/ngx_times.c \
src/core/ngx_conf_file.c \
src/core/ngx_garbage_collector.c"
diff --git a/src/core/ngx_core.h b/src/core/ngx_core.h
index 5b76d86..97819b6 100644
--- a/src/core/ngx_core.h
+++ b/src/core/ngx_core.h
@@ -30,6 +30,7 @@
#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 0000000..2bc4650
--- /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 0000000..de6fef9
--- /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 e1706ba..12dc229 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 @@
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 b765dd8..6ff316d 100644
--- a/src/core/ngx_times.h
+++ b/src/core/ngx_times.h
@@ -14,10 +14,13 @@
#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_ */
diff --git a/src/event/modules/ngx_kqueue_module.c b/src/event/modules/ngx_kqueue_module.c
index 9371ece..393c4d1 100644
--- a/src/event/modules/ngx_kqueue_module.c
+++ b/src/event/modules/ngx_kqueue_module.c
@@ -360,8 +360,10 @@
ts.tv_nsec = (timer % 1000) * 1000000;
tp = &ts;
+#if 0
ngx_gettimeofday(&tv);
delta = tv.tv_sec * 1000 + tv.tv_usec / 1000;
+#endif
} else {
delta = 0;
@@ -384,28 +386,31 @@
ngx_gettimeofday(&tv);
+#if 1
+ delta = ngx_elapsed_msec;
+#endif
+ ngx_elapsed_msec = tv.tv_sec * 1000 + tv.tv_usec / 1000 - ngx_start_msec;
+
if (ngx_cached_time != tv.tv_sec) {
ngx_cached_time = tv.tv_sec;
ngx_time_update();
}
if (timer) {
- delta = tv.tv_sec * 1000 + tv.tv_usec / 1000 - delta;
-
-#if (NGX_DEBUG_EVENT)
- ngx_log_debug(log, "kevent timer: %d, delta: %d" _ timer _ (int) delta);
-#endif
+ delta = ngx_elapsed_msec - delta;
#if 0
+ delta = tv.tv_sec * 1000 + tv.tv_usec / 1000 - delta;
+
/*
* The expired timers must be handled before a processing of the events
* because the new timers can be added during a processing
*/
ngx_event_expire_timers((ngx_msec_t) delta);
-#endif
ngx_event_set_timer_delta((ngx_msec_t) delta);
+#endif
} else {
if (events == 0) {
@@ -413,11 +418,11 @@
"kevent() returned no events without timeout");
return NGX_ERROR;
}
+ }
#if (NGX_DEBUG_EVENT)
ngx_log_debug(log, "kevent timer: %d, delta: %d" _ timer _ (int) delta);
#endif
- }
if (err) {
ngx_log_error(NGX_LOG_ALERT, log, err, "kevent() failed");
@@ -510,9 +515,15 @@
}
}
+ if (timer && delta) {
+ ngx_event_expire_timers((ngx_msec_t) delta);
+ }
+
+#if 0
if (timer) {
ngx_event_expire_timers((ngx_msec_t) delta);
}
+#endif
return NGX_OK;
}
diff --git a/src/event/ngx_event.c b/src/event/ngx_event.c
index 71bf45d..8a0856d 100644
--- a/src/event/ngx_event.c
+++ b/src/event/ngx_event.c
@@ -200,21 +200,10 @@
/* required by iocp in "c->write->active = 1" */
c->write = wev;
-#if 0
- ngx_test_null(rev->log, ngx_palloc(cycle->pool, sizeof(ngx_log_t)),
- NGX_ERROR);
-
- ngx_memcpy(rev->log, c->log, sizeof(ngx_log_t));
-#endif
-
rev->log = c->log;
rev->data = c;
rev->index = NGX_INVALID_INDEX;
-#if 0
- rev->listening = 1;
-#endif
-
rev->available = 0;
#if (HAVE_DEFERRED_ACCEPT)
diff --git a/src/event/ngx_event.h b/src/event/ngx_event.h
index 8e4ce44..1454cdb 100644
--- a/src/event/ngx_event.h
+++ b/src/event/ngx_event.h
@@ -31,11 +31,14 @@
ngx_event_t *prev;
ngx_event_t *next;
+ ngx_rbtree_t rbtree;
+
+#if 0
ngx_event_t *timer_prev;
ngx_event_t *timer_next;
ngx_msec_t timer_delta;
- ngx_msec_t timer;
+#endif
ngx_log_t *log;
diff --git a/src/event/ngx_event_accept.c b/src/event/ngx_event_accept.c
index ea63724..bba5aa5 100644
--- a/src/event/ngx_event_accept.c
+++ b/src/event/ngx_event_accept.c
@@ -175,6 +175,9 @@
rev->index = NGX_INVALID_INDEX;
wev->index = NGX_INVALID_INDEX;
+ rev->rbtree.data = rev;
+ wev->rbtree.data = wev;
+
rev->data = c;
wev->data = c;
diff --git a/src/event/ngx_event_timer.c b/src/event/ngx_event_timer.c
index 8176ed1..296c748 100644
--- a/src/event/ngx_event_timer.c
+++ b/src/event/ngx_event_timer.c
@@ -4,6 +4,81 @@
#include <ngx_event.h>
+ngx_rbtree_t *ngx_event_timer_rbtree;
+
+
+int ngx_event_timer_init(ngx_cycle_t *cycle)
+{
+ ngx_event_timer_rbtree = &sentinel;
+ sentinel.left = &sentinel;
+ sentinel.right = &sentinel;
+ sentinel.parent = &sentinel;
+
+ return NGX_OK;
+}
+
+
+void ngx_event_timer_done(ngx_cycle_t *cycle)
+{
+}
+
+
+int ngx_event_find_timer(void)
+{
+ ngx_rbtree_t *node;
+
+ node = ngx_rbtree_min(ngx_event_timer_rbtree);
+
+ if (node == &sentinel) {
+ return 0;
+
+ } else {
+ return node->key * NGX_TIMER_RESOLUTION - ngx_elapsed_msec;
+ }
+}
+
+
+void ngx_event_expire_timers(ngx_msec_t timer)
+{
+ ngx_event_t *ev;
+ ngx_rbtree_t *node;
+
+ for ( ;; ) {
+ node = ngx_rbtree_min(ngx_event_timer_rbtree);
+
+ if (node == &sentinel) {
+ break;
+ }
+
+ if ((ngx_msec_t) node->key <=
+ (ngx_elapsed_msec + timer) / NGX_TIMER_RESOLUTION)
+ {
+ ev = (ngx_event_t *)
+ ((char *) node - offsetof(ngx_event_t, rbtree));
+
+ ngx_del_timer(ev);
+
+ if (ev->delayed) {
+ ev->delayed = 0;
+ if (ev->ready == 0) {
+ continue;
+ }
+
+ } else {
+ ev->timedout = 1;
+ }
+
+ ev->event_handler(ev);
+ continue;
+ }
+
+ break;
+ }
+}
+
+
+#if 0
+
/* TODO: in multithreaded enviroment all timer operations must be
protected by the single mutex */
@@ -275,3 +350,6 @@
}
#endif
}
+
+
+#endif
diff --git a/src/event/ngx_event_timer.h b/src/event/ngx_event_timer.h
index 911667d..ea8105e 100644
--- a/src/event/ngx_event_timer.h
+++ b/src/event/ngx_event_timer.h
@@ -7,14 +7,58 @@
#include <ngx_event.h>
+/*
+ * 1 msec - 49 days
+ * 10 msec - 1 years 4 months
+ * 50 msec - 6 years 10 months
+ * 100 msec - 13 years 8 months
+ */
+
+#define NGX_TIMER_RESOLUTION 50
+
+
+int ngx_event_timer_init(ngx_cycle_t *cycle);
+void ngx_event_timer_done(ngx_cycle_t *cycle);
+int ngx_event_find_timer(void);
+void ngx_event_expire_timers(ngx_msec_t timer);
+
+#if 0
int ngx_event_timer_init(ngx_cycle_t *cycle);
void ngx_event_timer_done(ngx_cycle_t *cycle);
void ngx_event_add_timer(ngx_event_t *ev, ngx_msec_t timer);
int ngx_event_find_timer(void);
void ngx_event_set_timer_delta(ngx_msec_t timer);
void ngx_event_expire_timers(ngx_msec_t timer);
+#endif
+extern ngx_rbtree_t *ngx_event_timer_rbtree;
+
+
+ngx_inline static void ngx_event_del_timer(ngx_event_t *ev)
+{
+ ngx_rbtree_delete(&ngx_event_timer_rbtree, &ev->rbtree);
+
+ ev->timer_set = 0;
+}
+
+
+ngx_inline static void ngx_event_add_timer(ngx_event_t *ev, ngx_msec_t timer)
+{
+ if (ev->timer_set) {
+ ngx_del_timer(ev);
+ }
+
+ ev->rbtree.key = (ngx_int_t)
+ (ngx_elapsed_msec + timer) / NGX_TIMER_RESOLUTION;
+
+ ngx_rbtree_insert(&ngx_event_timer_rbtree, &ev->rbtree);
+
+ ev->timer_set = 1;
+}
+
+
+#if 0
ngx_inline static void ngx_event_del_timer(ngx_event_t *ev)
{
@@ -45,5 +89,7 @@
ev->timer_set = 0;
}
+#endif
+
#endif /* _NGX_EVENT_TIMER_H_INCLUDED_ */
diff --git a/src/http/ngx_http_core_module.c b/src/http/ngx_http_core_module.c
index 3046ca8..547e028 100644
--- a/src/http/ngx_http_core_module.c
+++ b/src/http/ngx_http_core_module.c
@@ -514,13 +514,7 @@
}
if (clcf->handler) {
- /*
- * if the location already has content handler then skip
- * the translation phase
- */
-
r->content_handler = clcf->handler;
- r->phase++;
}
return NGX_OK;
