Mercurial > hg > nginx-quic
diff src/core/ngx_queue.c @ 2026:72db8932f782
new ngx_queue functions
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Sat, 24 May 2008 14:10:01 +0000 |
parents | |
children | d620f497c50f |
line wrap: on
line diff
new file mode 100644 --- /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); + } +}