diff options
author | Igor Sysoev <igor@sysoev.ru> | 2008-05-24 18:10:01 +0400 |
---|---|---|
committer | Igor Sysoev <igor@sysoev.ru> | 2008-05-24 18:10:01 +0400 |
commit | 5cdc511fcd825c522340742f005302d3d7d87771 (patch) | |
tree | 28cb076ef03d3debbccd1019518ed60aca42281d /src | |
parent | 89e0aad840cddfb8031a0d97ed8254a85aa943c5 (diff) |
new ngx_queue functions
Diffstat (limited to 'src')
-rw-r--r-- | src/core/ngx_queue.c | 79 | ||||
-rw-r--r-- | src/core/ngx_queue.h | 43 |
2 files changed, 122 insertions, 0 deletions
diff --git a/src/core/ngx_queue.c b/src/core/ngx_queue.c new file mode 100644 index 000000000..a49b5c663 --- /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 1407d85a6..9a1763d7b 100644 --- a/src/core/ngx_queue.h +++ b/src/core/ngx_queue.h @@ -36,6 +36,16 @@ struct ngx_queue_s { (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 @@ struct ngx_queue_s { (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 @@ struct ngx_queue_s { #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_ */ |