blob: de091eae6eb0b64695043e6557699ee4e6ffb1b7 [file] [log] [blame]
/*
* Copyright (C) Igor Sysoev
* Copyright (C) NGINX, Inc.
*/
#include <nxt_auto_config.h>
#include <nxt_types.h>
#include <nxt_clang.h>
#include <nxt_queue.h>
/*
* Find the middle queue element if the queue has odd number of elements,
* or the first element of the queue's second part otherwise.
*/
nxt_queue_link_t *
nxt_queue_middle(nxt_queue_t *queue)
{
nxt_queue_link_t *middle, *next;
middle = nxt_queue_first(queue);
if (middle == nxt_queue_last(queue)) {
return middle;
}
next = middle;
for ( ;; ) {
middle = nxt_queue_next(middle);
next = nxt_queue_next(next);
if (next == nxt_queue_last(queue)) {
return middle;
}
next = nxt_queue_next(next);
if (next == nxt_queue_last(queue)) {
return middle;
}
}
}
/*
* nxt_queue_sort() provides a stable sort because it uses the insertion
* sort algorithm. Its worst and average computational complexity is O^2.
*/
void
nxt_queue_sort(nxt_queue_t *queue,
nxt_int_t (*compare)(const void *data, const nxt_queue_link_t *,
const nxt_queue_link_t *), const void *data)
{
nxt_queue_link_t *link, *prev, *next;
link = nxt_queue_first(queue);
if (link == nxt_queue_last(queue)) {
return;
}
for (link = nxt_queue_next(link);
link != nxt_queue_tail(queue);
link = next)
{
prev = nxt_queue_prev(link);
next = nxt_queue_next(link);
nxt_queue_remove(link);
do {
if (compare(data, prev, link) <= 0) {
break;
}
prev = nxt_queue_prev(prev);
} while (prev != nxt_queue_head(queue));
nxt_queue_insert_after(prev, link);
}
}