list.c

   1 /* -*- Mode: C ; c-basic-offset: 2 -*- */
   2 /*****************************************************************************
   3  *
   4  *   list_sort() adapted from linux kernel.
   5  *
   6  *   This program is free software; you can redistribute it and/or modify
   7  *   it under the terms of the GNU General Public License as published by
   8  *   the Free Software Foundation; version 2 of the License
   9  *
  10  *   This program is distributed in the hope that it will be useful,
  11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *   GNU General Public License for more details.
  14  *
  15  *   You should have received a copy of the GNU General Public License
  16  *   along with this program; if not, write to the Free Software
  17  *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  *****************************************************************************/
  20
  21 #include <assert.h>
  22
  23 #include "list.h"
  24
  25 /* list sort from Mark J Roberts (mjr@znex.org) */
  26 void
  27 __list_sort(
  28   struct list_head *head,
  29   int member_offset,
  30   int (*cmp)(void * a, void * b))
  31 {
  32   struct list_head *p, *q, *e, *list, *tail, *oldhead;
  33   int insize, nmerges, psize, qsize, i;
  34
  35   list = head->next;
  36   list_del(head);
  37   insize = 1;
  38   for (;;) {
  39     p = oldhead = list;
  40     list = tail = NULL;
  41     nmerges = 0;
  42
  43     while (p) {
  44       nmerges++;
  45       q = p;
  46       psize = 0;
  47       for (i = 0; i < insize; i++) {
  48         psize++;
  49         q = q->next == oldhead ? NULL : q->next;
  50         if (!q)
  51           break;
  52       }
  53
  54       qsize = insize;
  55       while (psize > 0 || (qsize > 0 && q)) {
  56         if (!psize) {
  57           e = q;
  58           q = q->next;
  59           qsize--;
  60           if (q == oldhead)
  61             q = NULL;
  62         } else if (!qsize || !q) {
  63           e = p;
  64           p = p->next;
  65           psize--;
  66           if (p == oldhead)
  67             p = NULL;
  68         } else if (cmp((void *)p - member_offset, (void *)q - member_offset) <= 0) {
  69           e = p;
  70           p = p->next;
  71           psize--;
  72           if (p == oldhead)
  73             p = NULL;
  74         } else {
  75           e = q;
  76           q = q->next;
  77           qsize--;
  78           if (q == oldhead)
  79             q = NULL;
  80         }
  81         if (tail)
  82           tail->next = e;
  83         else
  84           list = e;
  85         e->prev = tail;
  86         tail = e;
  87       }
  88       p = q;
  89     }
  90
  91     tail->next = list;
  92     list->prev = tail;
  93
  94     if (nmerges <= 1)
  95       break;
  96
  97     insize *= 2;
  98   }
  99
 100   head->next = list;
 101   head->prev = list->prev;
 102   list->prev->next = head;
 103   list->prev = head;
 104 }
 105
 106 struct test_list_el {
 107   int value;
 108   struct list_head test_list_node;
 109 };
 110
 111 int test_list_sort_comparator(struct test_list_el * e1, struct test_list_el * e2)
 112 {
 113   return e1->value - e2->value;
 114 }
 115
 116 void test_list_sort(void)
 117 {
 118   struct list_head test_list;
 119   struct test_list_el *el, *next;
 120   struct test_list_el te1 = {.value = 1};
 121   struct test_list_el te2 = {.value = 2};
 122   struct test_list_el te3 = {.value = 3};
 123   struct test_list_el te4 = {.value = 4};
 124   struct test_list_el te5 = {.value = 5};
 125   struct test_list_el te6 = {.value = 6};
 126   struct test_list_el te7 = {.value = 7};
 127
 128   const int expected[] = {1, 2, 3, 4, 5, 6, 7};
 129   int i;
 130
 131   INIT_LIST_HEAD(&test_list);
 132   list_add_tail(&te2.test_list_node, &test_list);
 133   list_add_tail(&te6.test_list_node, &test_list);
 134   list_add_tail(&te4.test_list_node, &test_list);
 135   list_add_tail(&te5.test_list_node, &test_list);
 136   list_add_tail(&te7.test_list_node, &test_list);
 137   list_add_tail(&te1.test_list_node, &test_list);
 138   list_add_tail(&te3.test_list_node, &test_list);
 139
 140   list_sort(&test_list, struct test_list_el, test_list_node, test_list_sort_comparator);
 141
 142   i = 0;
 143   list_for_each_entry_safe(el, next, &test_list, test_list_node) {
 144     assert(el->value == expected[i]);
 145     i++;
 146   }
 147 }