Initial implementation of OVSDB.
[openvswitch] / lib / sort.c
1 /* Copyright (c) 2009 Nicira Networks
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 }