kern/lib/sort.c

   1 /* Copyright (c) 2015 Google Inc
   2  * Davide Libenzi <dlibenzi@google.com>
   3  * See LICENSE for details.
   4  */
   5
   6 #include <stdio.h>
   7
   8 static void mem_swap(void *a, void *b, size_t size)
   9 {
  10         for (; size > 0; size--, a++, b++) {
  11                 char tmp = *(char*) a;
  12
  13                 *(char *) a = *(char *) b;
  14                 *(char *) b = tmp;
  15         }
  16 }
  17
  18 void sort(void *base, size_t count, size_t size,
  19           int (*cmp)(const void *, const void *))
  20 {
  21         ssize_t n = count * size, c;
  22
  23         /* Standard heapsort algorithm. First loop creates a heap, and the
  24          * second one progressively pop the top of the heap, and does re-heap
  25          * operations so that we maintain the heap properties.
  26          */
  27         for (ssize_t i = (count / 2 - 1) * size; i >= 0; i -= size) {
  28                 for (ssize_t r = i; r * 2 + size < n; r = c) {
  29                         c = r * 2 + size;
  30                         if (c < n - size && cmp(base + c, base + c + size) < 0)
  31                                 c += size;
  32                         if (cmp(base + r, base + c) >= 0)
  33                                 break;
  34                         mem_swap(base + r, base + c, size);
  35                 }
  36         }
  37
  38         for (ssize_t i = n - size; i > 0; i -= size) {
  39                 mem_swap(base, base + i, size);
  40                 for (ssize_t r = 0; r * 2 + size < i; r = c) {
  41                         c = r * 2 + size;
  42                         if (c < i - size && cmp(base + c, base + c + size) < 0)
  43                                 c += size;
  44                         if (cmp(base + r, base + c) >= 0)
  45                                 break;
  46                         mem_swap(base + r, base + c, size);
  47                 }
  48         }
  49 }