One Level Up Top Level

src/core/ngx_queue.c - nginx source code

Functions defined

Source code


  2. /*
  3. * Copyright (C) Igor Sysoev
  4. * Copyright (C) Nginx, Inc.
  5. */


  8. #include <ngx_config.h>
  9. #include <ngx_core.h>


  12. static void ngx_queue_merge(ngx_queue_t *queue, ngx_queue_t *tail,
  13.     ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *));


  16. /*
  17. * find the middle queue element if the queue has odd number of elements
  18. * or the first element of the queue's second part otherwise
  19. */

  21. ngx_queue_t *
  22. ‌ngx_queue_middle(ngx_queue_t *queue)
  23. {
  24.     ngx_queue_t  *middle, *next;

  26.     middle = ngx_queue_head(queue);

  28.     if (middle == ngx_queue_last(queue)) {
  29.         return middle;
  30.     }

  32.     next = ngx_queue_head(queue);

  34.     for ( ;; ) {
  35.         middle = ngx_queue_next(middle);

  37.         next = ngx_queue_next(next);

  39.         if (next == ngx_queue_last(queue)) {
  40.             return middle;
  41.         }

  43.         next = ngx_queue_next(next);

  45.         if (next == ngx_queue_last(queue)) {
  46.             return middle;
  47.         }
  48.     }
  49. }


  52. /* the stable merge sort */

  54. void
  55. ‌ngx_queue_sort(ngx_queue_t *queue,
  56.     ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
  57. {
  58.     ngx_queue_t  *q, tail;

  60.     q = ngx_queue_head(queue);

  62.     if (q == ngx_queue_last(queue)) {
  63.         return;
  64.     }

  66.     q = ngx_queue_middle(queue);

  68.     ngx_queue_split(queue, q, &tail);

  70.     ngx_queue_sort(queue, cmp);
  71.     ngx_queue_sort(&tail, cmp);

  73.     ngx_queue_merge(queue, &tail, cmp);
  74. }


  77. static void
  78. ‌ngx_queue_merge(ngx_queue_t *queue, ngx_queue_t *tail,
  79.     ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
  80. {
  81.     ngx_queue_t  *q1, *q2;

  83.     q1 = ngx_queue_head(queue);
  84.     q2 = ngx_queue_head(tail);

  86.     for ( ;; ) {
  87.         if (q1 == ngx_queue_sentinel(queue)) {
  88.             ngx_queue_add(queue, tail);
  89.             break;
  90.         }

  92.         if (q2 == ngx_queue_sentinel(tail)) {
  93.             break;
  94.         }

  96.         if (cmp(q1, q2) <= 0) {
  97.             q1 = ngx_queue_next(q1);
  98.             continue;
  99.         }

  101.         ngx_queue_remove(q2);
  102.         ngx_queue_insert_before(q1, q2);

  104.         q2 = ngx_queue_head(tail);
  105.     }
  106. }

One Level Up Top Level