src/core/ngx_queue.c - nginx-1.7.10

Functions defined

Source code


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


  5. #include <ngx_config.h>
  6. #include <ngx_core.h>


  7. /*
  8. * find the middle queue element if the queue has odd number of elements
  9. * or the first element of the queue's second part otherwise
  10. */

  11. ngx_queue_t *
  12. ngx_queue_middle(ngx_queue_t *queue)
  13. {
  14.     ngx_queue_t  *middle, *next;

  15.     middle = ngx_queue_head(queue);

  16.     if (middle == ngx_queue_last(queue)) {
  17.         return middle;
  18.     }

  19.     next = ngx_queue_head(queue);

  20.     for ( ;; ) {
  21.         middle = ngx_queue_next(middle);

  22.         next = ngx_queue_next(next);

  23.         if (next == ngx_queue_last(queue)) {
  24.             return middle;
  25.         }

  26.         next = ngx_queue_next(next);

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


  32. /* the stable insertion sort */

  33. void
  34. ngx_queue_sort(ngx_queue_t *queue,
  35.     ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
  36. {
  37.     ngx_queue_t  *q, *prev, *next;

  38.     q = ngx_queue_head(queue);

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

  42.     for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) {

  43.         prev = ngx_queue_prev(q);
  44.         next = ngx_queue_next(q);

  45.         ngx_queue_remove(q);

  46.         do {
  47.             if (cmp(prev, q) <= 0) {
  48.                 break;
  49.             }

  50.             prev = ngx_queue_prev(prev);

  51.         } while (prev != ngx_queue_sentinel(queue));

  52.         ngx_queue_insert_after(prev, q);
  53.     }
  54. }