new ngx_queue functions
diff --git a/auto/sources b/auto/sources
index ed78c71..62fb047 100644
--- a/auto/sources
+++ b/auto/sources
@@ -44,6 +44,7 @@
src/core/ngx_list.c \
src/core/ngx_hash.c \
src/core/ngx_buf.c \
+ src/core/ngx_queue.c \
src/core/ngx_output_chain.c \
src/core/ngx_string.c \
src/core/ngx_parse.c \
diff --git a/src/core/ngx_queue.c b/src/core/ngx_queue.c
new file mode 100644
index 0000000..a49b5c6
--- /dev/null
+++ b/src/core/ngx_queue.c
@@ -0,0 +1,79 @@
+
+/*
+ * Copyright (C) Igor Sysoev
+ */
+
+
+#include <ngx_config.h>
+#include <ngx_core.h>
+
+
+/*
+ * find the middle queue element if the queue has odd number of elements
+ * or the first element of the queue's second part otherwise
+ */
+
+ngx_queue_t *
+ngx_queue_middle(ngx_queue_t *queue)
+{
+ ngx_queue_t *middle, *next;
+
+ middle = ngx_queue_head(queue);
+
+ if (middle == ngx_queue_last(queue)) {
+ return middle;
+ }
+
+ next = ngx_queue_head(queue);
+
+ for ( ;; ) {
+ middle = ngx_queue_next(middle);
+
+ next = ngx_queue_next(next);
+
+ if (next == ngx_queue_last(queue)) {
+ return middle;
+ }
+
+ next = ngx_queue_next(next);
+
+ if (next == ngx_queue_last(queue)) {
+ return middle;
+ }
+ }
+}
+
+
+/* the stable insertion sort */
+
+void
+ngx_queue_sort(ngx_queue_t *queue,
+ ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
+{
+ ngx_queue_t *q, *prev, *next;
+
+ q = ngx_queue_head(queue);
+
+ if (q == ngx_queue_last(queue)) {
+ return;
+ }
+
+ for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) {
+
+ prev = ngx_queue_prev(q);
+ next = ngx_queue_next(q);
+
+ ngx_queue_remove(q);
+
+ do {
+ if (cmp(prev, q) <= 0) {
+ break;
+ }
+
+ prev = ngx_queue_prev(prev);
+
+ } while (prev != ngx_queue_sentinel(queue));
+
+ ngx_queue_insert_after(prev, q);
+ }
+}
diff --git a/src/core/ngx_queue.h b/src/core/ngx_queue.h
index 1407d85..9a1763d 100644
--- a/src/core/ngx_queue.h
+++ b/src/core/ngx_queue.h
@@ -36,6 +36,16 @@
(h)->next = x
+#define ngx_queue_insert_after ngx_queue_insert_head
+
+
+#define ngx_queue_insert_tail(h, x) \
+ (x)->prev = (h)->prev; \
+ (x)->prev->next = x; \
+ (x)->next = h; \
+ (h)->prev = x
+
+
#define ngx_queue_head(h) \
(h)->next
@@ -44,6 +54,18 @@
(h)->prev
+#define ngx_queue_sentinel(h) \
+ (h)
+
+
+#define ngx_queue_next(q) \
+ (q)->next
+
+
+#define ngx_queue_prev(q) \
+ (q)->prev
+
+
#if (NGX_DEBUG)
#define ngx_queue_remove(x) \
@@ -61,8 +83,29 @@
#endif
+#define ngx_queue_split(h, q, n) \
+ (n)->prev = (h)->prev; \
+ (n)->prev->next = n; \
+ (n)->next = q; \
+ (h)->prev = (q)->prev; \
+ (h)->prev->next = h; \
+ (q)->prev = n;
+
+
+#define ngx_queue_add(h, n) \
+ (h)->prev->next = (n)->next; \
+ (n)->next->prev = (h)->prev; \
+ (h)->prev = (n)->prev; \
+ (h)->prev->next = h;
+
+
#define ngx_queue_data(q, type, link) \
(type *) ((u_char *) q - offsetof(type, link))
+ngx_queue_t *ngx_queue_middle(ngx_queue_t *queue);
+void ngx_queue_sort(ngx_queue_t *queue,
+ ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *));
+
+
#endif /* _NGX_QUEUE_H_INCLUDED_ */
