andy_shev

square-sort-reversed.c

Oct 18th, 2021 (edited)
131
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3.  * Circular double linked list example.
  4.  * Includes:
  5.  *  - quick sort
  6.  *  - insertion sort
  7.  *  - reversed traversing
  8.  *
  9.  * Usage:
  10.  *  square-sort [sorting type] [reversed]
  11.  *
  12.  * Sorting type can be:
  13.  *  - 0 (default) for quick sort
  14.  *  - 1 for insertion sort
  15.  *
  16.  * Reversed defines the output of the sorted data.
  17.  */
  18. #include <err.h>
  19. #include <stdio.h>
  20. #include <stdlib.h>
  21. #include <time.h>
  22.  
  23. /* Double linked list implementation */
  24.  
  25. struct list_head {
  26.     struct list_head *prev;
  27.     struct list_head *next;
  28. };
  29.  
  30. #define LIST_HEAD(name) \
  31.     struct list_head name = { &(name), &(name) }
  32.  
  33. static void list_del(struct list_head *entry)
  34. {
  35.     struct list_head *prev = entry->prev;
  36.     struct list_head *next = entry->next;
  37.  
  38.     next->prev = prev;
  39.     prev->next = next;
  40. }
  41.  
  42. static void list_add(struct list_head *new, struct list_head *head)
  43. {
  44.     struct list_head *prev = head->prev;
  45.     struct list_head *next = head;
  46.  
  47.         next->prev = new;
  48.         new->next = next;
  49.         new->prev = prev;
  50.         prev->next = new;
  51. }
  52.  
  53. static int list_empty(const struct list_head *head)
  54. {
  55.         return head->next == head;
  56. }
  57.  
  58. static void list_splice(const struct list_head *list, struct list_head *prev, struct list_head *next)
  59. {
  60.     struct list_head *first = list->next;
  61.     struct list_head *last = list->prev;
  62.  
  63.     first->prev = prev;
  64.     prev->next = first;
  65.  
  66.     last->next = next;
  67.     next->prev = last;
  68. }
  69.  
  70. /* The member type of list_head MUST be first in a structure */
  71. #define list_entry(ptr, type, member)       ((type *)(ptr))
  72.  
  73. #define list_first_entry(ptr, type, member) list_entry((ptr)->next, type, member)
  74. #define list_last_entry(ptr, type, member)  list_entry((ptr)->prev, type, member)
  75.  
  76. #define list_next_entry(pos, member)        list_entry((pos)->member.next, typeof(*(pos)), member)
  77. #define list_prev_entry(pos, member)        list_entry((pos)->member.prev, typeof(*(pos)), member)
  78.  
  79. #define list_for_each_entry_safe(pos, n, head, member)          \
  80.     for (pos = list_first_entry(head, typeof(*pos), member),    \
  81.            n = list_next_entry(pos, member);            \
  82.          &pos->member != (head);                    \
  83.          pos = n, n = list_next_entry(n, member))
  84.  
  85. #define list_for_each_entry_safe_reversed(pos, n, head, member)     \
  86.     for (pos = list_last_entry(head, typeof(*pos), member),     \
  87.            n = list_prev_entry(pos, member);            \
  88.          &pos->member != (head);                    \
  89.          pos = n, n = list_prev_entry(n, member))
  90.  
  91. /*************************************/
  92.  
  93. struct bus {
  94.     struct list_head node;  /* MUST be first member */
  95.     int x1, y1, x2, y2;
  96. };
  97.  
  98. static int s(struct bus *b)
  99. {
  100.     return abs(b->x1 - b->x2) * abs(b->y1 - b->y2);
  101. }
  102.  
  103. static void dump(struct list_head *bs, int reversed)
  104. {
  105.     const char *fmt = "Square[%u]: %d,%d,%d,%d (%d)\n";
  106.     unsigned int i = 0;
  107.     struct bus *b, *_b;
  108.  
  109.     if (reversed) {
  110.         list_for_each_entry_safe_reversed(b, _b, bs, node)
  111.             printf(fmt, i++, b->x1, b->y1, b->x2, b->y2, s(b));
  112.     } else {
  113.         list_for_each_entry_safe(b, _b, bs, node)
  114.             printf(fmt, i++, b->x1, b->y1, b->x2, b->y2, s(b));
  115.     }
  116.     printf("\n");
  117. }
  118.  
  119. static void bsfree(struct list_head *bs)
  120. {
  121.     struct bus *b, *_b;
  122.  
  123.     list_for_each_entry_safe(b, _b, bs, node) {
  124.         list_del(&b->node);
  125.         free(b);
  126.     }
  127. }
  128.  
  129. static int prepare(struct list_head *bs)
  130. {
  131.     unsigned int num;
  132.     unsigned int i;
  133.     struct bus *b;
  134.  
  135.     srand(time(NULL));
  136.  
  137.     num = rand() % 8 + 3;
  138.  
  139.     for (i = 0; i < num; i++) {
  140.         b = malloc(sizeof(*b));
  141.         if (!b)
  142.             err(1, NULL);
  143.  
  144.         b->x1 = rand() % 12;
  145.         b->y1 = rand() % 12 - 5;
  146.         b->x2 = rand() % 12 - 7;
  147.         b->y2 = rand() % 12;
  148.  
  149.         list_add(&b->node, bs);
  150.     }
  151.  
  152.     return 0;
  153. }
  154.  
  155. /* Quicksort implementation for double-linked list */
  156. static void dlsort(struct list_head *bs)
  157. {
  158.     struct bus *b, *_b, *first;
  159.     LIST_HEAD(less);
  160.     LIST_HEAD(more);
  161.     int pivot;
  162.  
  163.     first = list_first_entry(bs, struct bus, node);
  164.     pivot = s(first);
  165.  
  166.     list_del(&first->node);
  167.     list_for_each_entry_safe(b, _b, bs, node) {
  168.         list_del(&b->node);
  169.         if (s(b) >= pivot)
  170.             list_add(&b->node, &more);
  171.         else
  172.             list_add(&b->node, &less);
  173.     }
  174.     list_add(&first->node, &less);
  175.  
  176.     if (!list_empty(&less)) {
  177.         if (less.next != less.prev)
  178.             dlsort(&less);
  179.         list_splice(&less, bs->prev, bs);
  180.     }
  181.  
  182.     if (!list_empty(&more)) {
  183.         if (more.next != more.prev)
  184.             dlsort(&more);
  185.         list_splice(&more, bs->prev, bs);
  186.     }
  187. }
  188.  
  189. static void inssort(struct list_head *bs)
  190. {
  191.     struct bus *b, *_b, *n, *_n;
  192.     LIST_HEAD(result);
  193.  
  194.     list_for_each_entry_safe(b, _b, bs, node) {
  195.         list_del(&b->node);
  196.  
  197.         list_for_each_entry_safe(n, _n, &result, node) {
  198.             if (s(n) > s(b))
  199.                 break;
  200.         }
  201.  
  202.         list_add(&b->node, &n->node);
  203.     }
  204.  
  205.     list_splice(&result, bs, bs);
  206. }
  207.  
  208. static void bssort(struct list_head *bs, int type)
  209. {
  210.     if (list_empty(bs))
  211.         return;
  212.  
  213.     switch (type) {
  214.         case 1:
  215.             printf("Using Insert Sort...\n");
  216.             inssort(bs);
  217.             break;
  218.         case 0:
  219.         default:
  220.             printf("Using Quick Sort...\n");
  221.             dlsort(bs);
  222.             break;
  223.     }
  224. }
  225.  
  226. int main(int argc, char *argv[])
  227. {
  228.     LIST_HEAD(bussit);
  229.     int reversed;
  230.     int type;
  231.     int ret;
  232.  
  233.     if (argc > 2)
  234.         reversed = atoi(argv[2]);
  235.     else
  236.         reversed = 0;
  237.  
  238.     if (argc > 1)
  239.         type = atoi(argv[1]);
  240.     else
  241.         type = 0;
  242.  
  243.     ret = prepare(&bussit);
  244.     if (ret)
  245.         return ret;
  246.  
  247.     dump(&bussit, 0);
  248.     bssort(&bussit, type);
  249.     dump(&bussit, reversed);
  250.  
  251.     bsfree(&bussit);
  252.     return 0;
  253. }
  254.  
RAW Paste Data