square-sort-reversed.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Circular double linked list example.
 * Includes:
 *  - quick sort
 *  - insertion sort
 *  - reversed traversing
 *
 * Usage:
 *  square-sort [sorting type] [reversed]
 *
 * Sorting type can be:
 *  - 0 (default) for quick sort
 *  - 1 for insertion sort
 *
 * Reversed defines the output of the sorted data.
 */
#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* Double linked list implementation */

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

#define LIST_HEAD(name) \
    struct list_head name = { &(name), &(name) }

static void list_del(struct list_head *entry)
{
    struct list_head *prev = entry->prev;
    struct list_head *next = entry->next;

    next->prev = prev;
    prev->next = next;
}

static void list_add(struct list_head *new, struct list_head *head)
{
    struct list_head *prev = head->prev;
    struct list_head *next = head;

        next->prev = new;
        new->next = next;
        new->prev = prev;
        prev->next = new;
}

static int list_empty(const struct list_head *head)
{
        return head->next == head;
}

static void list_splice(const struct list_head *list, struct list_head *prev, struct list_head *next)
{
    struct list_head *first = list->next;
    struct list_head *last = list->prev;

    first->prev = prev;
    prev->next = first;

    last->next = next;
    next->prev = last;
}

/* The member type of list_head MUST be first in a structure */
#define list_entry(ptr, type, member)       ((type *)(ptr))

#define list_first_entry(ptr, type, member) list_entry((ptr)->next, type, member)
#define list_last_entry(ptr, type, member)  list_entry((ptr)->prev, type, member)

#define list_next_entry(pos, member)        list_entry((pos)->member.next, typeof(*(pos)), member)
#define list_prev_entry(pos, member)        list_entry((pos)->member.prev, typeof(*(pos)), member)

#define list_for_each_entry_safe(pos, n, head, member)          \
    for (pos = list_first_entry(head, typeof(*pos), member),    \
           n = list_next_entry(pos, member);            \
         &pos->member != (head);                    \
         pos = n, n = list_next_entry(n, member))

#define list_for_each_entry_safe_reversed(pos, n, head, member)     \
    for (pos = list_last_entry(head, typeof(*pos), member),     \
           n = list_prev_entry(pos, member);            \
         &pos->member != (head);                    \
         pos = n, n = list_prev_entry(n, member))

/*************************************/

struct bus {
    struct list_head node;  /* MUST be first member */
    int x1, y1, x2, y2;
};

static int s(struct bus *b)
{
    return abs(b->x1 - b->x2) * abs(b->y1 - b->y2);
}

static void dump(struct list_head *bs, int reversed)
{
    const char *fmt = "Square[%u]: %d,%d,%d,%d (%d)\n";
    unsigned int i = 0;
    struct bus *b, *_b;

    if (reversed) {
        list_for_each_entry_safe_reversed(b, _b, bs, node)
            printf(fmt, i++, b->x1, b->y1, b->x2, b->y2, s(b));
    } else {
        list_for_each_entry_safe(b, _b, bs, node)
            printf(fmt, i++, b->x1, b->y1, b->x2, b->y2, s(b));
    }
    printf("\n");
}

static void bsfree(struct list_head *bs)
{
    struct bus *b, *_b;

    list_for_each_entry_safe(b, _b, bs, node) {
        list_del(&b->node);
        free(b);
    }
}

static int prepare(struct list_head *bs)
{
    unsigned int num;
    unsigned int i;
    struct bus *b;

    srand(time(NULL));

    num = rand() % 8 + 3;

    for (i = 0; i < num; i++) {
        b = malloc(sizeof(*b));
        if (!b)
            err(1, NULL);

        b->x1 = rand() % 12;
        b->y1 = rand() % 12 - 5;
        b->x2 = rand() % 12 - 7;
        b->y2 = rand() % 12;

        list_add(&b->node, bs);
    }

    return 0;
}

/* Quicksort implementation for double-linked list */
static void dlsort(struct list_head *bs)
{
    struct bus *b, *_b, *first;
    LIST_HEAD(less);
    LIST_HEAD(more);
    int pivot;

    first = list_first_entry(bs, struct bus, node);
    pivot = s(first);

    list_del(&first->node);
    list_for_each_entry_safe(b, _b, bs, node) {
        list_del(&b->node);
        if (s(b) >= pivot)
            list_add(&b->node, &more);
        else
            list_add(&b->node, &less);
    }
    list_add(&first->node, &less);

    if (!list_empty(&less)) {
        if (less.next != less.prev)
            dlsort(&less);
        list_splice(&less, bs->prev, bs);
    }

    if (!list_empty(&more)) {
        if (more.next != more.prev)
            dlsort(&more);
        list_splice(&more, bs->prev, bs);
    }
}

static void inssort(struct list_head *bs)
{
    struct bus *b, *_b, *n, *_n;
    LIST_HEAD(result);

    list_for_each_entry_safe(b, _b, bs, node) {
        list_del(&b->node);

        list_for_each_entry_safe(n, _n, &result, node) {
            if (s(n) > s(b))
                break;
        }

        list_add(&b->node, &n->node);
    }

    list_splice(&result, bs, bs);
}

static void bssort(struct list_head *bs, int type)
{
    if (list_empty(bs))
        return;

    switch (type) {
        case 1:
            printf("Using Insert Sort...\n");
            inssort(bs);
            break;
        case 0:
        default:
            printf("Using Quick Sort...\n");
            dlsort(bs);
            break;
    }
}

int main(int argc, char *argv[])
{
    LIST_HEAD(bussit);
    int reversed;
    int type;
    int ret;

    if (argc > 2)
        reversed = atoi(argv[2]);
    else
        reversed = 0;

    if (argc > 1)
        type = atoi(argv[1]);
    else
        type = 0;

    ret = prepare(&bussit);
    if (ret)
        return ret;

    dump(&bussit, 0);
    bssort(&bussit, type);
    dump(&bussit, reversed);

    bsfree(&bussit);
    return 0;
}