sys/dev/drm/linux_list_sort.c

   1 /*      $NetBSD: linux_list_sort.c,v 1.2 2014/03/18 18:20:43 riastradh Exp $    */
   2
   3 /*-
   4  * Copyright (c) 2013 The NetBSD Foundation, Inc.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to The NetBSD Foundation
   8  * by Taylor R. Campbell.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29  * POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 #include <sys/cdefs.h>
  33 //__KERNEL_RCSID(0, "$NetBSD: linux_list_sort.c,v 1.2 2014/03/18 18:20:43 riastradh Exp $");
  34
  35 #include <sys/systm.h>
  36
  37 #include <machine/limits.h>
  38
  39 #include <linux/kernel.h>
  40 #include <linux/list.h>
  41 #include <linux/list_sort.h>
  42
  43 static struct list_head *
  44 list_sort_merge(struct list_head *, struct list_head *,
  45                 int (*)(void *, struct list_head *,
  46                 struct list_head *), void *);
  47 static void
  48 list_sort_merge_into(struct list_head *,
  49                      struct list_head *, struct list_head *,
  50                      int (*)(void *, struct list_head *,
  51                      struct list_head *), void *);
  52
  53 void
  54 list_sort(void *arg, struct list_head *list,
  55           int (*compare)(void *, struct list_head *, struct list_head *))
  56 {
  57         /*
  58          * Array of sorted sublists, counting in binary: accum[i]
  59          * is sorted, and either is NULL or has length 2^i.
  60          */
  61         struct list_head *accum[64];
  62
  63         /* Indices into accum.  */
  64         unsigned int logn, max_logn = 0;
  65
  66         /* The sorted list we're currently working on.  */
  67         struct list_head *sorted;
  68
  69         /* The remainder of the unsorted list.  */
  70         struct list_head *next;
  71
  72         /* Make sure we can't possibly have more than 2^64-element lists.  */
  73         CTASSERT((CHAR_BIT * sizeof(struct list_head *)) <= 64);
  74
  75         for (logn = 0; logn < ARRAY_SIZE(accum); logn++)
  76                 accum[logn] = NULL;
  77
  78         list_for_each_safe(sorted, next, list) {
  79                 /* Pick off a single element, always sorted.  */
  80                 sorted->next = NULL;
  81
  82                 /* Add one and propagate the carry.  */
  83                 for (logn = 0; accum[logn] != NULL; logn++) {
  84                         /*
  85                          * Merge, preferring previously accumulated
  86                          * elements to make the sort stable.
  87                          */
  88                         sorted = list_sort_merge(accum[logn], sorted, compare, arg);
  89                         accum[logn] = NULL;
  90                         KKASSERT((logn + 1) < ARRAY_SIZE(accum));
  91                 }
  92
  93                 /* Remember the highest index seen so far.  */
  94                 if (logn > max_logn)
  95                         max_logn = logn;
  96
  97                 /*
  98                  * logn = log_2(length(sorted)), and accum[logn]
  99                  * is now empty, so save the sorted sublist there.
 100                  */
 101                 accum[logn] = sorted;
 102         }
 103
 104         /*
 105          * Merge ~half of everything we have accumulated.
 106          */
 107         sorted = NULL;
 108         for (logn = 0; logn < max_logn; logn++)
 109                 sorted = list_sort_merge(accum[logn], sorted, compare, arg);
 110
 111         /*
 112          * Merge the last ~halves back into the list, and fix the back
 113          * pointers.
 114          */
 115         list_sort_merge_into(list, accum[max_logn], sorted, compare, arg);
 116 }
 117
 118 /*
 119  * Merge the NULL-terminated lists starting at nodes `a' and `b',
 120  * breaking ties by choosing nodes in `a' first, and returning
 121  * whichever node has the least element.
 122  */
 123 static struct list_head *
 124 list_sort_merge(struct list_head *a, struct list_head *b,
 125                 int (*compare)(void *, struct list_head *,
 126                 struct list_head *), void *arg)
 127 {
 128         struct list_head head, *tail = &head;
 129
 130         /*
 131          * Merge while elements in both remain.
 132          */
 133         while ((a != NULL) && (b != NULL)) {
 134                 struct list_head **const first = ((*compare)(arg, a, b) <= 0?
 135                     &a : &b);
 136
 137                 tail = tail->next = *first;
 138                 *first = (*first)->next;
 139         }
 140
 141         /*
 142          * Attach whatever remains.
 143          */
 144         tail->next = (a != NULL? a : b);
 145         return head.next;
 146 }
 147
 148 /*
 149  * Merge the NULL-terminated lists starting at nodes `a' and `b' into
 150  * the (uninitialized) list head `list', breaking ties by choosing
 151  * nodes in `a' first, and setting the `prev' pointers as we go.
 152  */
 153 static void
 154 list_sort_merge_into(struct list_head *list,
 155                      struct list_head *a, struct list_head *b,
 156                      int (*compare)(void *, struct list_head *,
 157                      struct list_head *), void *arg)
 158 {
 159         struct list_head *prev = list;
 160
 161         /*
 162          * Merge while elements in both remain.
 163          */
 164         while ((a != NULL) && (b != NULL)) {
 165                 struct list_head **const first = (
 166                         (*compare)(arg, a, b) <= 0 ? &a : &b);
 167
 168                 (*first)->prev = prev;
 169                 prev = prev->next = *first;
 170                 *first = (*first)->next;
 171         }
 172
 173         /*
 174          * Attach whichever of a and b remains, and fix up the prev
 175          * pointers all the way down the rest of the list.
 176          */
 177         struct list_head *tail = (a == NULL? b : a);
 178         while (tail != NULL) {
 179                 prev->next = tail;
 180                 tail->prev = prev;
 181                 prev = prev->next;
 182                 tail = tail->next;
 183         }
 184
 185         /*
 186          * Finally, finish the cycle.
 187          */
 188         prev->next = list;
 189         list->prev = prev;
 190 }