pytx/sort.c

   1 #include "list.h"
   2
   3 void sort(struct list_head *head, void *d, int (*cmp)(void *, const struct list_head *, const struct list_head *)) {
   4         LIST_HEAD(empty);
   5         struct list_head *unsorted_head, *sorted_head, *p, *q, *tmp;
   6         int psize, qsize, K, count;
   7
   8         if (list_empty(head))
   9                 return;
  10
  11         unsorted_head = head;
  12         sorted_head = &empty;
  13         K = 1;
  14         while (1) {
  15                 p = unsorted_head->next;
  16                 count = 0;
  17                 do {
  18                         q = p;
  19                         psize = 0;
  20                         while (psize < K) {
  21                                 if (q == unsorted_head)
  22                                         break;
  23                                 psize++;
  24                                 q = q->next;
  25                         }
  26                         qsize = K;
  27                         while (1) {
  28                                 struct list_head *e;
  29
  30                                 if (q == unsorted_head)
  31                                         qsize = 0;
  32                                 if (psize == 0 && qsize == 0)
  33                                         break;
  34                                 if (!psize || (qsize && cmp(d, p, q) > 0)) {
  35                                         e = q;
  36                                         q = q->next;
  37                                         qsize--;
  38                                 } else {
  39                                         e = p;
  40                                         p = p->next;
  41                                         psize--;
  42                                 }
  43                                 list_del(e);
  44                                 list_add_tail(e, sorted_head);
  45                         }
  46                         count++;
  47                         p = q;
  48                 } while (p != unsorted_head);
  49
  50                 if (count == 1) {
  51                         head->next = sorted_head->next;
  52                         head->prev = sorted_head->prev;
  53                         sorted_head->prev->next = head;
  54                         sorted_head->next->prev = head;
  55                         return;
  56                 }
  57                 tmp = unsorted_head;
  58                 unsorted_head = sorted_head;
  59                 sorted_head = tmp;
  60                 K *= 2;
  61         }
  62 }