queue.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "queue.h"

#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin__expect(!!(x), 0)

/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *head =
        (struct list_head *) malloc(sizeof(struct list_head));

    if (head)
        INIT_LIST_HEAD(head);

    return head;
}

/* Free all storage used by queue */
void q_free(struct list_head *head)
{
    if (!head)
        return;

    struct list_head *pos, *next;

    for (pos = head->next; pos != head;) {
        next = pos->next;
        element_t *ele = list_entry(pos, element_t, list);
        free(ele->value);
        free(ele);
        pos = next;
    }

    free(head);
}

inline element_t *__new_element(const char *s)
{
    element_t *ele = (element_t *) malloc(sizeof(element_t));
    if (!ele)
        return NULL;

    size_t len = strlen(s);

    ele->value = (char *) malloc((len + 1) * sizeof(char));
    if (!ele->value) {
        free(ele);
        return NULL;
    }

    strncpy(ele->value, s, len + 1);
    return ele;
}

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *ele = __new_element(s);
    if (!ele)
        return false;

    list_add(&ele->list, head);
    return true;
}

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;

    element_t *ele = __new_element(s);
    if (!ele)
        return false;

    list_add_tail(&ele->list, head);
    return true;
}

/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *ele = list_entry(head->next, element_t, list);
    list_del_init(&ele->list);

    if (sp) {
        strncpy(sp, ele->value, bufsize - 1);
        sp[bufsize - 1] = 0;
    }

    return ele;
}

/* Remove an element from tail of queue */
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    element_t *ele = list_entry(head->prev, element_t, list);
    list_del_init(&ele->list);

    if (sp) {
        strncpy(sp, ele->value, bufsize - 1);
        sp[bufsize - 1] = 0;
    }

    return ele;
}

/* Return number of elements in queue */
int q_size(struct list_head *head)
{
    if (!head)
        return 0;

    int size = 0;
    struct list_head *node;

    list_for_each(node, head)
        size++;
    return size;
}

/* Delete the middle node in queue */
bool q_delete_mid(struct list_head *head)
{
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
    if (!head || head->next == head)
        return false;

    struct list_head *slow = head->next, *fast = head;
    for (; fast->next != head && fast->next->next != head;) {
        slow = slow->next;
        fast = fast->next->next;
    }
    slow->prev->next = slow->next;
    slow->next->prev = slow->prev;

    element_t *ele = list_entry(slow, element_t, list);
    free(ele->value);
    free(ele);
    return true;
}

/* Delete nodes in the range [begin, end) */
void delete_range(struct list_head *begin, struct list_head *end)
{
    struct list_head *begin_prev = begin->prev, *curr = begin,
                     *next = begin->next;

    while (curr != end) {
        element_t *ele = list_entry(curr, element_t, list);
        free(ele->value);
        free(ele);
        curr = next;
        next = next->next;
    }
    begin_prev->next = end;
    end->prev = begin_prev;
}

/* Delete all nodes that have duplicate string */
bool q_delete_dup(struct list_head *head)
{
    // https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
    if (!head || head->next == head)
        return false;

    struct list_head *curr = head->next, *begin = head->next;
    const char *value = list_entry(curr, element_t, list)->value;

    for (; curr != head; curr = curr->next) {
        const char *tmp = list_entry(curr, element_t, list)->value;
        if (strcmp(value, tmp) != 0) {
            if (begin != curr->prev)
                delete_range(begin, curr);
            begin = curr;
            value = tmp;
        }
    }
    if (begin != curr->prev)
        delete_range(begin, curr);

    return true;
}

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    if (!head)
        return;

    struct list_head *p1 = head->next, *p2 = head->next->next;

    for (; p1 != head && p2 != head;) {
        p1->prev->next = p2;
        p2->next->prev = p1;
        p1->next = p2->next;
        p2->prev = p1->prev;
        p1->prev = p2;
        p2->next = p1;
        p1 = p1->next;
        p2 = p1->next;
    }
}

/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    struct list_head *prev = head, *cur = head->next, *next = head->next->next;

    for (;;) {
        cur->prev = next;
        cur->next = prev;
        if (cur == head)
            break;
        prev = cur;
        cur = next;
        next = next->next;
    }
}

struct list_head *__q_reverseK_recurse(struct list_head *node, int k)
{
    struct list_head **p = &node;

    for (int i = 0; i < k; ++i) {
        if (!*p)
            return node;
        p = &(*p)->next;
    }

    struct list_head *p_head = __q_reverseK_recurse(*p, k);

    *p = NULL;

    struct list_head *prev = NULL, *curr = node, *next = node->next;
    curr->next = prev;
    while (next) {
        prev = curr;
        curr = next;
        next = next->next;
        curr->next = prev;
    }

    node->next = p_head;
    return curr;
}

void __q_reverseK_final(struct list_head *head)
{
    struct list_head *cur = head, *next = head->next;

    while (next) {
        next->prev = cur;
        cur = next;
        next = next->next;
    }
    cur->next = head;
    head->prev = cur;
}

/* Reverse the nodes of the list k at a time */
void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || head->next == head->prev || k == 1)
        return;

    head->prev->next = NULL;
    head->next = __q_reverseK_recurse(head->next, k);
    __q_reverseK_final(head);
}

/* Merge two lists that are sorted in the order that is compatible with
 * `descend`. Return the address of the leading node of the merged list.
 */
struct list_head *__merge(struct list_head *head1,
                          struct list_head *head2,
                          bool descend)
{
    if (!head1)
        return head2;
    if (!head2)
        return head1;

    struct list_head *head = NULL, **tail = &head;

    for (;;) {
        const char *value1 = list_entry(head1, element_t, list)->value,
                   *value2 = list_entry(head2, element_t, list)->value;

        if ((!descend && strcmp(value1, value2) <= 0) ||
            (descend && strcmp(value1, value2) >= 0)) {
            *tail = head1;
            tail = &head1->next;
            head1 = head1->next;
            if (!head1) {
                *tail = head2;
                break;
            }
        } else {
            *tail = head2;
            tail = &head2->next;
            head2 = head2->next;
            if (!head2) {
                *tail = head1;
                break;
            }
        }
    }
    return head;
}

void __q_sort_final(struct list_head *head)
{
    struct list_head *cur = head, *next = head->next;

    while (next) {
        next->prev = cur;
        cur = next;
        next = next->next;
    }
    cur->next = head;
    head->prev = cur;
}

/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
    if (!head)
        return;

    struct list_head *list = head->next, *pending = NULL;
    size_t count = 0; /* Count of pending */

    if (list == head->prev) /* Zero or one elements */
        return;

    /* Convert to a null-terminated singly-linked list. */
    head->prev->next = NULL;

    /*
     * Data structure invariants:
     * - All lists are singly linked and null-terminated; prev
     *   pointers are not maintained.
     * - pending is a prev-linked "list of lists" of sorted
     *   sublists awaiting further merging.
     * - Each of the sorted sublists is power-of-two in size.
     * - Sublists are sorted by size and age, smallest & newest at front.
     * - There are zero to two sublists of each size.
     * - A pair of pending sublists are merged as soon as the number
     *   of following pending elements equals their size (i.e.
     *   each time count reaches an odd multiple of that size).
     *   That ensures each later final merge will be at worst 2:1.
     * - Each round consists of:
     *   - Merging the two sublists selected by the highest bit
     *     which flips when count is incremented, and
     *   - Adding an element from the input as a size-1 sublist.
     */
    do {
        size_t bits;
        struct list_head **tail = &pending;

        /* Find the least-significant clear bit in count */
        for (bits = count; bits & 1; bits >>= 1)
            tail = &(*tail)->prev;
        /* Do the indicated merge */
        if (likely(bits)) {
            struct list_head *a = *tail, *b = a->prev;

            a = __merge(b, a, descend);
            /* Install the merged result in place of the inputs */
            a->prev = b->prev;
            *tail = a;
        }

        /* Move one element from input list to pending */
        list->prev = pending;
        pending = list;
        list = list->next;
        pending->next = NULL;
        count++;
    } while (list);

    /* End of input; merge together all the pending lists. */
    list = pending;
    pending = pending->prev;
    for (;;) {
        struct list_head *next = pending->prev;

        if (!next)
            break;
        list = __merge(pending, list, descend);
        pending = next;
    }
    head->next = __merge(pending, list, descend);

    __q_sort_final(head);
}

struct list_head *__q_ordering(struct list_head *node, int *size, bool ascend)
{
    if (!node->next) {
        ++(*size);
        return node;
    }

    node->next = __q_ordering(node->next, size, ascend);
    const char *val_1 = list_entry(node, element_t, list)->value,
               *val_2 = list_entry(node->next, element_t, list)->value;

    if ((ascend && strcmp(val_1, val_2) > 0) ||
        (!ascend && strcmp(val_1, val_2) < 0)) {
        struct list_head *next = node->next;
        element_t *ele = list_entry(node, element_t, list);
        free(ele->value);
        free(ele);
        return next;
    }

    ++(*size);
    return node;
}

void __q_ordering_final(struct list_head *head)
{
    struct list_head *cur = head, *next = head->next;

    while (next) {
        next->prev = cur;
        cur = next;
        next = next->next;
    }
    cur->next = head;
    head->prev = cur;
}

int __q_ordering_common(struct list_head *head, bool ascend)
{
    int size = 0;

    head->prev->next = NULL;
    head->next = __q_ordering(head->next, &size, ascend);
    __q_ordering_final(head);
    return size;
}

int __q_ascend(struct list_head *head)
{
    return __q_ordering_common(head, true);
}

int __q_descend(struct list_head *head)
{
    return __q_ordering_common(head, false);
}

/* Remove every node which has a node with a strictly less value anywhere to
 * the right side of it */
int q_ascend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || head->prev == head->next)
        return 0;
    return __q_ascend(head);
}

/* Remove every node which has a node with a strictly greater value anywhere to
 * the right side of it */
int q_descend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || head->prev == head->next)
        return 0;
    return __q_descend(head);
}

void __q_merge_chain_final(struct list_head *head)
{
    struct list_head *cur = head, *next = head->next;

    while (next) {
        next->prev = cur;
        cur = next;
        next = next->next;
    }
    cur->next = head;
    head->prev = cur;
}

void __q_merge_chain(struct list_head *chain1,
                     struct list_head *chain2,
                     bool descend)
{
    queue_contex_t *qctx1 = list_entry(chain1, queue_contex_t, chain),
                   *qctx2 = list_entry(chain2, queue_contex_t, chain);

    if (!qctx2->q)
        return;
    if (!qctx1->q) {
        qctx1->q = qctx2->q;
        qctx2->q = NULL;
        qctx1->size = qctx2->size;
        qctx2->size = 0;
        return;
    }

    qctx1->q->prev->next = NULL;
    qctx2->q->prev->next = NULL;

    qctx1->q->next = __merge(qctx1->q->next, qctx2->q->next, descend);
    qctx1->size = qctx1->size + qctx2->size;
    qctx2->q->next = qctx2->q;
    qctx2->q->prev = qctx2->q;
    qctx2->size = 0;
    __q_merge_chain_final(qctx1->q);
}

int __q_merge(struct list_head *begin, struct list_head *end, bool descend)
{
    if (begin == end)
        return list_entry(begin, queue_contex_t, chain)->size;

    struct list_head *slow = begin, *fast = begin;

    for (; fast != end && fast->next != end; fast = fast->next->next)
        slow = slow->next;

    int n1 = __q_merge(begin, slow, descend);
    int n2 = __q_merge(slow->next, end, descend);
    __q_merge_chain(begin, slow->next, descend);
    return n1 + n2;
}

/* Merge all the queues into one sorted queue, which is in ascending/descending
 * order */
int q_merge(struct list_head *head, bool descend)
{
    // https://leetcode.com/problems/merge-k-sorted-lists/
    if (!head || head->next == head)
        return 0;

    if (head->next == head->prev)
        return list_entry(head->next, queue_contex_t, chain)->size;

    return __q_merge(head->next, head->prev, descend);
}