diff options
author | Ben Pfaff <blp@nicira.com> | 2009-11-04 15:11:44 -0800 |
---|---|---|
committer | Ben Pfaff <blp@nicira.com> | 2009-11-04 17:12:10 -0800 |
commit | f85f8ebbfac946c19b3c6eb0f4170f579d0a4d25 (patch) | |
tree | 2111aee77751f2143773907f81c6adb9101afb6c /lib/sort.c | |
parent | f212909325be9bc7e296e1a32e2fc89694a0049f (diff) |
Initial implementation of OVSDB.
Diffstat (limited to 'lib/sort.c')
-rw-r--r-- | lib/sort.c | 70 |
1 files changed, 70 insertions, 0 deletions
diff --git a/lib/sort.c b/lib/sort.c new file mode 100644 index 00000000..017b0a9a --- /dev/null +++ b/lib/sort.c @@ -0,0 +1,70 @@ +/* Copyright (c) 2009 Nicira Networks + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <config.h> + +#include "sort.h" + +#include "random.h" + +static size_t +partition(size_t p, size_t r, + int (*compare)(size_t a, size_t b, void *aux), + void (*swap)(size_t a, size_t b, void *aux), + void *aux) +{ + size_t x = r - 1; + size_t i, j; + + i = p; + for (j = p; j < x; j++) { + if (compare(j, x, aux) <= 0) { + swap(i++, j, aux); + } + } + swap(i, x, aux); + return i; +} + +static void +quicksort(size_t p, size_t r, + int (*compare)(size_t a, size_t b, void *aux), + void (*swap)(size_t a, size_t b, void *aux), + void *aux) +{ + size_t i, q; + + if (r - p < 2) { + return; + } + + i = random_range(r - p) + p; + if (r - 1 != i) { + swap(r - 1, i, aux); + } + + q = partition(p, r, compare, swap, aux); + quicksort(p, q, compare, swap, aux); + quicksort(q, r, compare, swap, aux); +} + +void +sort(size_t count, + int (*compare)(size_t a, size_t b, void *aux), + void (*swap)(size_t a, size_t b, void *aux), + void *aux) +{ + quicksort(0, count, compare, swap, aux); +} |