lib/sort.c

   1 /* Copyright (c) 2009 Nicira, Inc.
   2  *
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15
  16 #include <config.h>
  17
  18 #include "sort.h"
  19
  20 #include "random.h"
  21
  22 static size_t
  23 partition(size_t p, size_t r,
  24           int (*compare)(size_t a, size_t b, void *aux),
  25           void (*swap)(size_t a, size_t b, void *aux),
  26           void *aux)
  27 {
  28     size_t x = r - 1;
  29     size_t i, j;
  30
  31     i = p;
  32     for (j = p; j < x; j++) {
  33         if (compare(j, x, aux) <= 0) {
  34             swap(i++, j, aux);
  35         }
  36     }
  37     swap(i, x, aux);
  38     return i;
  39 }
  40
  41 static void
  42 quicksort(size_t p, size_t r,
  43           int (*compare)(size_t a, size_t b, void *aux),
  44           void (*swap)(size_t a, size_t b, void *aux),
  45           void *aux)
  46 {
  47     size_t i, q;
  48
  49     if (r - p < 2) {
  50         return;
  51     }
  52
  53     i = random_range(r - p) + p;
  54     if (r - 1 != i) {
  55         swap(r - 1, i, aux);
  56     }
  57
  58     q = partition(p, r, compare, swap, aux);
  59     quicksort(p, q, compare, swap, aux);
  60     quicksort(q, r, compare, swap, aux);
  61 }
  62
  63 void
  64 sort(size_t count,
  65      int (*compare)(size_t a, size_t b, void *aux),
  66      void (*swap)(size_t a, size_t b, void *aux),
  67      void *aux)
  68 {
  69     quicksort(0, count, compare, swap, aux);
  70 }