Return to ngx_queue.c CVS log | Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / nginx / src / core |
1.1 ! misho 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: }