Werner Zeh has uploaded this change for review.

View Change

lib: 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.

Change-Id: I2c5e0b5685a907243b58ebe6682078272d316bf6
Signed-off-by: Werner Zeh <werner.zeh@siemens.com>
---
A src/include/sort.h
M src/lib/Makefile.inc
A src/lib/sort.c
3 files changed, 83 insertions(+), 0 deletions(-)

git pull ssh://review.coreboot.org:29418/coreboot refs/changes/44/31544/1

diff --git a/src/include/sort.h b/src/include/sort.h
new file mode 100644
index 0000000..0117d66
--- /dev/null
+++ b/src/include/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 SORT_H_
+#define 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 /* SORT_H_ */
diff --git a/src/lib/Makefile.inc b/src/lib/Makefile.inc
index fa1ff8b..33f68d2 100644
--- a/src/lib/Makefile.inc
+++ b/src/lib/Makefile.inc
@@ -150,6 +150,7 @@
 ramstage-$(CONFIG_FLATTENED_DEVICE_TREE) += device_tree.c
 ramstage-$(CONFIG_PAYLOAD_FIT_SUPPORT) += fit.c
 ramstage-$(CONFIG_PAYLOAD_FIT_SUPPORT) += fit_payload.c
+ramstage-y += sort.c
 
 romstage-y += cbmem_common.c
 romstage-y += imd_cbmem.c
diff --git a/src/lib/sort.c b/src/lib/sort.c
new file mode 100644
index 0000000..48802c1
--- /dev/null
+++ b/src/lib/sort.c
@@ -0,0 +1,55 @@
+/*
+ * 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 <sort.h>
+
+static void swap(int *v1, int *v2)
+{
+	int tmp = *v1;
+
+	*v1 = *v2;
+	*v2 = tmp;
+}
+
+static int is_bigger(int v1, int v2)
+{
+	return v1 > v2 ? 1 : 0;
+}
+/* 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 len = num_entries, idx, i;
+
+	do {
+		idx = 1;
+		for (i = 0; i < (len - 1); ++i) {
+			switch (order) {
+			case NUM_ASCENDING:
+				if (is_bigger(v[i], v[i + 1]))
+					swap(&v[i], &v[i + 1]);
+				break;
+			case NUM_DESCENDING:
+				if (is_bigger(v[i + 1], v[i]))
+					swap(&v[i], &v[i + 1]);
+				break;
+			default:
+				return;
+			}
+			idx = i + 1;
+		}
+		len = idx;
+	} while (len > 1);
+}

To view, visit change 31544. To unsubscribe, or for help writing mail filters, visit settings.