nginx/src/core/ngx_queue.c

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