summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorWerner Zeh <werner.zeh@siemens.com>2019-02-19 13:34:12 +0100
committerPatrick Georgi <pgeorgi@google.com>2019-02-26 11:14:41 +0000
commitbd660e23382a74b399fa25ca01b9a9cd9c7683e9 (patch)
tree7caf9845c770b379dba2cab680c214bf38f9bbea /src
parent38b6ccfed9d0a9ff0605f2def02033cc9523ee94 (diff)
downloadcoreboot-bd660e23382a74b399fa25ca01b9a9cd9c7683e9.tar.xz
commonlib: Add Bubble sort algorithm
Add an implementation for Bubble sort. For now, only integers can be sorted in an ascending or descending order. It can be later simply extended to cover other datasets like strings if needed. The reasons for choosing bubble sort are: * it is a simple algorithm * bubble sort is stable, i.e. it does not exchange entries which are not needed to be sorted as they are already in order Change-Id: I2c5e0b5685a907243b58ebe6682078272d316bf6 Signed-off-by: Werner Zeh <werner.zeh@siemens.com> Reviewed-on: https://review.coreboot.org/c/31544 Tested-by: build bot (Jenkins) <no-reply@coreboot.org> Reviewed-by: Julius Werner <jwerner@chromium.org>
Diffstat (limited to 'src')
-rw-r--r--src/commonlib/Makefile.inc2
-rw-r--r--src/commonlib/include/commonlib/helpers.h5
-rw-r--r--src/commonlib/include/commonlib/sort.h27
-rw-r--r--src/commonlib/sort.c49
4 files changed, 83 insertions, 0 deletions
diff --git a/src/commonlib/Makefile.inc b/src/commonlib/Makefile.inc
index 4d89c48e5a..b6e8913cd1 100644
--- a/src/commonlib/Makefile.inc
+++ b/src/commonlib/Makefile.inc
@@ -36,3 +36,5 @@ verstage-y += lz4_wrapper.c
romstage-y += lz4_wrapper.c
ramstage-y += lz4_wrapper.c
postcar-y += lz4_wrapper.c
+
+ramstage-y += sort.c
diff --git a/src/commonlib/include/commonlib/helpers.h b/src/commonlib/include/commonlib/helpers.h
index 03f430635d..adc43ca98b 100644
--- a/src/commonlib/include/commonlib/helpers.h
+++ b/src/commonlib/include/commonlib/helpers.h
@@ -38,6 +38,11 @@
#define ABS(a) (((a) < 0) ? (-(a)) : (a))
#define IS_POWER_OF_2(x) (((x) & ((x) - 1)) == 0)
#define DIV_ROUND_UP(x, y) (((x) + (y) - 1) / (y))
+#define SWAP(a, b) do { \
+ typeof(a) tmp = a; \
+ a = (typeof(a)) b; \
+ b = (typeof(b)) tmp; \
+ } while (0)
/*
* Divide positive or negative dividend by positive divisor and round
* to closest integer. Result is undefined for negative divisors and
diff --git a/src/commonlib/include/commonlib/sort.h b/src/commonlib/include/commonlib/sort.h
new file mode 100644
index 0000000000..3d94d25d40
--- /dev/null
+++ b/src/commonlib/include/commonlib/sort.h
@@ -0,0 +1,27 @@
+/*
+ * This file is part of the coreboot project.
+ *
+ * Copyright (C) 2019 Siemens AG
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; version 2 of the License.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ */
+#ifndef _COMMONLIB_SORT_H_
+#define _COMMONLIB_SORT_H_
+
+#include <stddef.h>
+
+typedef enum {
+ NUM_ASCENDING,
+ NUM_DESCENDING
+} sort_order_t;
+
+void bubblesort(int *v, size_t num_entries, sort_order_t order);
+
+#endif /* _COMMONLIB_SORT_H_ */
diff --git a/src/commonlib/sort.c b/src/commonlib/sort.c
new file mode 100644
index 0000000000..40999397c8
--- /dev/null
+++ b/src/commonlib/sort.c
@@ -0,0 +1,49 @@
+/*
+ * This file is part of the coreboot project.
+ *
+ * Copyright (C) 2019 Siemens AG
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; version 2 of the License.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ */
+
+#include <commonlib/helpers.h>
+#include <commonlib/sort.h>
+
+/* Implement a simple Bubble sort algorithm. Reduce the needed number of
+ iterations by taking care of already sorted entries in the list. */
+void bubblesort(int *v, size_t num_entries, sort_order_t order)
+{
+ size_t i, j;
+ int swapped;
+
+ for (j = 0; j < num_entries - 1; j++) {
+ swapped = 0;
+ for (i = 0; i < num_entries - j - 1; i++) {
+ switch (order) {
+ case NUM_ASCENDING:
+ if (v[i] > v[i + 1]) {
+ SWAP(v[i], v[i + 1]);
+ swapped = 1;
+ }
+ break;
+ case NUM_DESCENDING:
+ if (v[i] < v[i + 1]) {
+ SWAP(v[i], v[i + 1]);
+ swapped = 1;
+ }
+ break;
+ default:
+ return;
+ }
+ }
+ if (!swapped)
+ break;
+ }
+}