queue.c

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

#include "queue.h"

/* Notice: sometimes, Cppcheck would find the potential NULL pointer bugs,
 * but some of them cannot occur. You can suppress them by adding the
 * following line.
 *   cppcheck-suppress nullPointer
 */


/* Create an empty queue */
struct list_head *q_new()
{
    struct list_head *new_list =
        (struct list_head *) malloc(sizeof(struct list_head));
    if (!new_list)
        return NULL;
    INIT_LIST_HEAD(new_list);
    return new_list;
}

/* Free all storage used by queue */
void q_free(struct list_head *head)
{
    if (!head)
        return;
    element_t *cur, *n;
    list_for_each_entry_safe (cur, n, head, list)
        q_release_element(cur);
    free(head);
}

unsigned int str_len(char *s)
{
    unsigned int count = 0;
    while (*s != '\0') {
        if (s++ && !++count)
            return 0;
    }
    return count;
}

/* q_new_element - Create a new element
 * @s: pointer to the data
 *
 * Return: the created element
 * */
element_t *q_new_element(char *s)
{
    element_t *new = malloc(sizeof(element_t));
    if (!new)
        return NULL;
    new->value = strdup(s);
    if (!new->value) {
        free(new);
        return NULL;
    }
    return new;
}

bool q_insert(struct list_head *head,
              char *s,
              void (*add)(struct list_head *, struct list_head *))
{
    if (!head)
        return false;

    element_t *new = q_new_element(s);
    if (!new)
        return false;
    add(&new->list, head);
    return true;
}

/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
    return q_insert(head, s, list_add);
}

/* Insert an element at tail of queue */
bool q_insert_tail(struct list_head *head, char *s)
{
    return q_insert(head, s, list_add_tail);
}

/* Remove an element from node */
element_t *q_remove(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head)
        return NULL;
    element_t *ret = list_entry(head, element_t, list);
    if (!ret)
        return NULL;
    list_del(head);
    if (sp && bufsize - 1 > 0) {
        strncpy(sp, ret->value, bufsize - 1);
        *(sp + bufsize - 1) = '\0';
    }
    return ret;
}

/* 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;
    return q_remove(head->next, sp, bufsize);
}

/* 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;
    return q_remove(head->prev, sp, bufsize);
}

/* Return number of elements in queue */
int q_size(struct list_head *head)
{
    if (!head)
        return 0;
    int count = 0;
    struct list_head *cur;
    list_for_each (cur, head)
        count++;
    return count;
}

/* 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 || list_empty(head))
        return false;
    struct list_head *one = head->next, *two = head->next->next;
    while (one != head && two != head && two != head->next) {
        one = one->next;
        two = two->next->next;
    }
    list_del(one);
    q_release_element(list_entry(one, element_t, list));
    return true;
}

/* 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 || list_empty(head))
        return false;
    struct list_head *cur, *n;
    bool del = false;
    list_for_each_safe (cur, n, head) {
        element_t *cur_ele = list_entry(cur, element_t, list);
        element_t *next_ele = list_entry(n, element_t, list);
        if (n != head && strcmp(cur_ele->value, next_ele->value) == 0) {
            list_del(cur);
            q_release_element(cur_ele);
            del = true;
        } else if (del) {
            list_del(cur);
            q_release_element(cur_ele);
            del = false;
        }
    }
    return true;
}

/* Swap every two adjacent nodes */
void q_swap(struct list_head *head)
{
    // https://leetcode.com/problems/swap-nodes-in-pairs/
    q_reverseK(head, 2);
}

/* Reverse elements in queue */
void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head *cur, *n;
    list_for_each_safe (cur, n, head)
        list_move(cur, head);
}

/* 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 || list_empty(head))
        return;
    struct list_head *cur, *n;
    LIST_HEAD(tmp);
    int count = 0;
    list_for_each_safe (cur, n, head) {
        list_move(cur, &tmp);
        ++count;
        if (count == k) {
            count = 0;
            list_splice_init(&tmp, n->prev);
        }
    }
    if (!list_empty(&tmp)) {
        q_reverse(&tmp);
        list_splice_tail_init(&tmp, head);
    }
}

bool greater(const char *s1, const char *s2)
{
    return strcmp(s1, s2) > 0;
}

bool less(const char *s1, const char *s2)
{
    return strcmp(s1, s2) < 0;
}

void conquer(struct list_head *l1,
             struct list_head *l2,
             bool (*cmp)(const char *s1, const char *s2))
{
    struct list_head *list1 = l1->next;
    struct list_head *list2 = l2->next;
    struct list_head *list2_n = list2->next;
    while (list1 != l1 && !list_empty(l2)) {
        element_t *list1_entry = list_entry(list1, element_t, list);
        element_t *list2_entry = list_entry(list2, element_t, list);
        if (!cmp(list1_entry->value, list2_entry->value)) {
            list_move_tail(list2, list1);
            list2 = list2_n;
            list2_n = list2->next;
        } else {
            list1 = list1->next;
        }
    }
    list_splice_tail_init(list2->prev, list1);
}

/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *fast = head->next->next, *slow = head->next;
    while (fast != head && fast != head->prev) {
        fast = fast->next->next;
        slow = slow->next;
    }
    LIST_HEAD(tmp);
    list_cut_position(&tmp, head, slow);
    q_sort(&tmp, descend);
    q_sort(head, descend);
    conquer(head, &tmp, descend ? greater : less);
}

int q_remove_unorder_part(struct list_head *head,
                          bool (*cmp)(const char *s1, const char *s2))
{
    if (!head || list_empty(head))
        return 0;
    int ret = q_size(head);
    element_t *cur, *n;
    list_for_each_entry_safe (cur, n, head, list) {
        if (n != list_first_entry(head, element_t, list) &&
            cur != list_last_entry(head, element_t, list)) {
            while (n != list_first_entry(head, element_t, list) &&
                   cmp(cur->value, n->value)) {
                cur = q_remove(&cur->list, NULL, 0);
                q_release_element(cur);
                --ret;
                if (&n->list != head &&
                    n != list_first_entry(head, element_t, list))
                    cur = list_entry(n->list.prev, element_t, list);
            }
        }
    }
    return ret;
}

/* 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/
    return q_remove_unorder_part(head, greater);
}

/* 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/
    return q_remove_unorder_part(head, less);
}

/* 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 || list_empty(head))
        return 0;
    struct list_head *cur;
    struct list_head *q_head = list_first_entry(head, queue_contex_t, chain)->q;
    for (cur = (head)->next->next; cur != head; cur = cur->next) {
        conquer(q_head, list_entry(cur, queue_contex_t, chain)->q,
                descend ? greater : less);
    }
    return q_size(list_first_entry(head, queue_contex_t, chain)->q);
}