← Back to branch summary

~ubuntu-branches/ubuntu/trusty/nginx/trusty-proposed

« back to all changes in this revision

Viewing changes to src/core/ngx_queue.c

  • Committer: Package Import Robot
  • Author(s): Kartik Mistry
  • Date: 2013-04-25 12:51:45 UTC
  • mfrom: (1.3.28)
  • mto: (1.3.29) (15.1.2 experimental)
  • mto: This revision was merged to the branch mainline in revision 64.
  • Revision ID: package-import@ubuntu.com-20130425125145-ugl0wor6bq0u5eae
Tags: upstream-1.4.0
Import upstream version 1.4.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/core/ngx_queue.c
 
1
 
 
2
/*
 
3
 * Copyright (C) Igor Sysoev
 
4
 * Copyright (C) Nginx, Inc.
 
5
 */
 
6
 
 
7
 
 
8
#include <ngx_config.h>
 
9
#include <ngx_core.h>
 
10
 
 
11
 
 
12
/*
 
13
 * find the middle queue element if the queue has odd number of elements
 
14
 * or the first element of the queue's second part otherwise
 
15
 */
 
16
 
 
17
ngx_queue_t *
 
18
ngx_queue_middle(ngx_queue_t *queue)
 
19
{
 
20
    ngx_queue_t  *middle, *next;
 
21
 
 
22
    middle = ngx_queue_head(queue);
 
23
 
 
24
    if (middle == ngx_queue_last(queue)) {
 
25
        return middle;
 
26
    }
 
27
 
 
28
    next = ngx_queue_head(queue);
 
29
 
 
30
    for ( ;; ) {
 
31
        middle = ngx_queue_next(middle);
 
32
 
 
33
        next = ngx_queue_next(next);
 
34
 
 
35
        if (next == ngx_queue_last(queue)) {
 
36
            return middle;
 
37
        }
 
38
 
 
39
        next = ngx_queue_next(next);
 
40
 
 
41
        if (next == ngx_queue_last(queue)) {
 
42
            return middle;
 
43
        }
 
44
    }
 
45
}
 
46
 
 
47
 
 
48
/* the stable insertion sort */
 
49
 
 
50
void
 
51
ngx_queue_sort(ngx_queue_t *queue,
 
52
    ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
 
53
{
 
54
    ngx_queue_t  *q, *prev, *next;
 
55
 
 
56
    q = ngx_queue_head(queue);
 
57
 
 
58
    if (q == ngx_queue_last(queue)) {
 
59
        return;
 
60
    }
 
61
 
 
62
    for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) {
 
63
 
 
64
        prev = ngx_queue_prev(q);
 
65
        next = ngx_queue_next(q);
 
66
 
 
67
        ngx_queue_remove(q);
 
68
 
 
69
        do {
 
70
            if (cmp(prev, q) <= 0) {
 
71
                break;
 
72
            }
 
73
 
 
74
            prev = ngx_queue_prev(prev);
 
75
 
 
76
        } while (prev != ngx_queue_sentinel(queue));
 
77
 
 
78
        ngx_queue_insert_after(prev, q);
 
79
    }
 
80
}