third_party/cairo/src/cairo-tor22-scan-converter.c
static struct edge *
sort_edges (struct edge *list,
	    unsigned int level,
	    struct edge **head_out)
{
    struct edge *head_other, *remaining;
    unsigned int i;

    head_other = list->next;

    if (head_other == NULL) {
	*head_out = list;
	return NULL;
    }

    remaining = head_other->next;
    if (list->x.quo <= head_other->x.quo) {
	*head_out = list;
	head_other->next = NULL;
    } else {
	*head_out = head_other;
	head_other->prev = list->prev;
	head_other->next = list;
	list->prev = head_other;
	list->next = NULL;
    }

    for (i = 0; i < level && remaining; i++) {
	remaining = sort_edges (remaining, i, &head_other);
	*head_out = merge_sorted_edges (*head_out, head_other);
    }

    return remaining;
}
/*
 * Sort (part of) a list.
 * Input:
 *  - list: The list to be sorted; list cannot be NULL.
 *  - limit: Recursion limit.
 * Output:
 *  - head_out: The head of the sorted list containing the first 2^(level+1) elements of the
 *              input list; if the input list has fewer elements, head_out be a sorted list
 *              containing all the elements of the input list.
 * Returns the head of the list of unprocessed elements (NULL if the sorted list contains
 * all the elements of the input list).
 *
 * Implementation notes:
 * Special case single element list, unroll/inline the sorting of the first two elements.
 * Some tail recursion is used since we iterate on the bottom-up solution of the problem
 * (we start with a small sorted list and keep merging other lists of the same size to it).
 */
Sort (part of) a list.
Input:
- list: The list to be sorted; list cannot be NULL.
- limit: Recursion limit.
Output:
- head_out: The head of the sorted list containing the first 2^(level+1) elements of the
input list; if the input list has fewer elements, head_out be a sorted list
containing all the elements of the input list.
Returns the head of the list of unprocessed elements (NULL if the sorted list contains
all the elements of the input list).

Implementation notes:
Special case single element list, unroll/inline the sorting of the first two elements.
Some tail recursion is used since we iterate on the bottom-up solution of the problem
(we start with a small sorted list and keep merging other lists of the same size to it).
Sort ( part of ) a list . Input : - list : The list to be sorted ; list cannot be NULL . - limit : Recursion limit . Output : - head_out : The head of the sorted list containing the first 2^ ( level + 1 ) elements of the input list ; if the input list has fewer elements head_out be a sorted list containing all the elements of the input list . Returns the head of the list of unprocessed elements ( NULL if the sorted list contains all the elements of the input list ) . Implementation notes : Special case single element list unroll / inline the sorting of the first two elements . Some tail recursion is used since we iterate on the bottom - up solution of the problem ( we start with a small sorted list and keep merging other lists of the same size to it ) .
static struct edge *
sort_edges (struct edge *list,
	    unsigned int level,
	    struct edge **head_out)
{
    struct edge *head_other, *remaining;
    unsigned int i;
    head_other = list->next;
    if (head_other == NULL) {
	*head_out = list;
	return NULL;
    }
    remaining = head_other->next;
    if (list->x.quo <= head_other->x.quo) {
	*head_out = list;
	head_other->next = NULL;
    } else {
	*head_out = head_other;
	head_other->prev = list->prev;
	head_other->next = list;
	list->prev = head_other;
	list->next = NULL;
    }
    for (i = 0; i < level && remaining; i++) {
	remaining = sort_edges (remaining, i, &head_other);
	*head_out = merge_sorted_edges (*head_out, head_other);
    }
    return remaining;
}
static struct edge * sort_edges ( struct edge * list , unsigned int level , struct edge * * head_out ) { struct edge * head_other , * remaining ; unsigned int i ; head_other = list -> next ; if ( head_other == NULL ) { * head_out = list ; return NULL ; } remaining = head_other -> next ; if ( list -> x . quo <= head_other -> x . quo ) { * head_out = list ; head_other -> next = NULL ; } else { * head_out = head_other ; head_other -> prev = list -> prev ; head_other -> next = list ; list -> prev = head_other ; list -> next = NULL ; } for ( i = 0 ; i < level && remaining ; i ++ ) { remaining = sort_edges ( remaining , i , & head_other ) ; * head_out = merge_sorted_edges ( * head_out , head_other ) ; } return remaining ; }
Sort (part of) a list.
Sort ( part of ) a list .