Back to home page

Nginx displayed by LXR

Source navigation ]
Diff markup ]
Identifier search ]
general search ]
 
 
Version: nginx-1.13.12 ]​[ nginx-1.12.2 ]​

0001 
0002 /*
0003  * Copyright (C) Igor Sysoev
0004  * Copyright (C) Nginx, Inc.
0005  */
0006 
0007 
0008 #include <ngx_config.h>
0009 #include <ngx_core.h>
0010 
0011 
0012 /*
0013  * find the middle queue element if the queue has odd number of elements
0014  * or the first element of the queue's second part otherwise
0015  */
0016 
0017 ngx_queue_t *
0018 ngx_queue_middle(ngx_queue_t *queue)
0019 {
0020     ngx_queue_t  *middle, *next;
0021 
0022     middle = ngx_queue_head(queue);
0023 
0024     if (middle == ngx_queue_last(queue)) {
0025         return middle;
0026     }
0027 
0028     next = ngx_queue_head(queue);
0029 
0030     for ( ;; ) {
0031         middle = ngx_queue_next(middle);
0032 
0033         next = ngx_queue_next(next);
0034 
0035         if (next == ngx_queue_last(queue)) {
0036             return middle;
0037         }
0038 
0039         next = ngx_queue_next(next);
0040 
0041         if (next == ngx_queue_last(queue)) {
0042             return middle;
0043         }
0044     }
0045 }
0046 
0047 
0048 /* the stable insertion sort */
0049 
0050 void
0051 ngx_queue_sort(ngx_queue_t *queue,
0052     ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
0053 {
0054     ngx_queue_t  *q, *prev, *next;
0055 
0056     q = ngx_queue_head(queue);
0057 
0058     if (q == ngx_queue_last(queue)) {
0059         return;
0060     }
0061 
0062     for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) {
0063 
0064         prev = ngx_queue_prev(q);
0065         next = ngx_queue_next(q);
0066 
0067         ngx_queue_remove(q);
0068 
0069         do {
0070             if (cmp(prev, q) <= 0) {
0071                 break;
0072             }
0073 
0074             prev = ngx_queue_prev(prev);
0075 
0076         } while (prev != ngx_queue_sentinel(queue));
0077 
0078         ngx_queue_insert_after(prev, q);
0079     }
0080 }