]>
git.proxmox.com Git - mirror_ovs.git/blob - lib/sort.c
1 /* Copyright (c) 2009 Nicira, Inc.
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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
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
),
32 for (j
= p
; j
< x
; j
++) {
33 if (compare(j
, x
, aux
) <= 0) {
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
),
53 i
= random_range(r
- p
) + p
;
58 q
= partition(p
, r
, compare
, swap
, aux
);
59 quicksort(p
, q
, compare
, swap
, aux
);
60 quicksort(q
, r
, compare
, swap
, aux
);
65 int (*compare
)(size_t a
, size_t b
, void *aux
),
66 void (*swap
)(size_t a
, size_t b
, void *aux
),
69 quicksort(0, count
, compare
, swap
, aux
);