Initial implementation of OVSDB.

[openvswitch] / lib / sort.c

diff --git a/lib/sort.c b/lib/sort.c
new file mode 100644 (file)
index 0000000..017b0a9
--- /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);
+}