[10/10] mergesort: remove llist_mergesort()

Commit Message

René Scharfe July 16, 2022, 5:02 p.m. UTC

Now that all of its callers are gone, remove llist_mergesort().

Signed-off-by: René Scharfe <[e-mail]>
---
 Makefile    |  1 -
 mergesort.c | 76 -----------------------------------------------------
 mergesort.h | 13 ---------
 3 files changed, 90 deletions(-)
 delete mode 100644 mergesort.c

--
2.37.1

Patch

diff --git a/Makefile b/Makefile
index 04d0fd1fe6..d41705dc31 100644
--- a/Makefile
+++ b/Makefile
@@ -984,7 +984,6 @@  LIB_OBJS += merge-ort.o
 LIB_OBJS += merge-ort-wrappers.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += merge.o
-LIB_OBJS += mergesort.o
 LIB_OBJS += midx.o
 LIB_OBJS += name-hash.o
 LIB_OBJS += negotiator/default.o
diff --git a/mergesort.c b/mergesort.c
deleted file mode 100644
index 6bda3a1c0e..0000000000
--- a/mergesort.c
+++ /dev/null
@@ -1,76 +0,0 @@ 
-#include "cache.h"
-#include "mergesort.h"
-
-/* Combine two sorted lists.  Take from `list` on equality. */
-static void *llist_merge(void *list, void *other,
-			 void *(*get_next_fn)(const void *),
-			 void (*set_next_fn)(void *, void *),
-			 int (*compare_fn)(const void *, const void *))
-{
-	void *result = list, *tail;
-	int prefer_list = compare_fn(list, other) <= 0;
-
-	if (!prefer_list) {
-		result = other;
-		SWAP(list, other);
-	}
-	for (;;) {
-		do {
-			tail = list;
-			list = get_next_fn(list);
-			if (!list) {
-				set_next_fn(tail, other);
-				return result;
-			}
-		} while (compare_fn(list, other) < prefer_list);
-		set_next_fn(tail, other);
-		prefer_list ^= 1;
-		SWAP(list, other);
-	}
-}
-
-/*
- * Perform an iterative mergesort using an array of sublists.
- *
- * n is the number of items.
- * ranks[i] is undefined if n & 2^i == 0, and assumed empty.
- * ranks[i] contains a sublist of length 2^i otherwise.
- *
- * The number of bits in a void pointer limits the number of objects
- * that can be created, and thus the number of array elements necessary
- * to be able to sort any valid list.
- *
- * Adding an item to this array is like incrementing a binary number;
- * positional values for set bits correspond to sublist lengths.
- */
-void *llist_mergesort(void *list,
-		      void *(*get_next_fn)(const void *),
-		      void (*set_next_fn)(void *, void *),
-		      int (*compare_fn)(const void *, const void *))
-{
-	void *ranks[bitsizeof(void *)];
-	size_t n = 0;
-
-	if (!list)
-		return NULL;
-
-	for (;;) {
-		int i;
-		size_t m;
-		void *next = get_next_fn(list);
-		if (next)
-			set_next_fn(list, NULL);
-		for (i = 0, m = n;; i++, m >>= 1) {
-			if (m & 1)
-				list = llist_merge(ranks[i], list, get_next_fn,
-						   set_next_fn, compare_fn);
-			else if (next)
-				break;
-			else if (!m)
-				return list;
-		}
-		n++;
-		ranks[i] = list;
-		list = next;
-	}
-}
diff --git a/mergesort.h b/mergesort.h
index 7b44355283..7c36f08bd5 100644
--- a/mergesort.h
+++ b/mergesort.h
@@ -1,19 +1,6 @@ 
 #ifndef MERGESORT_H
 #define MERGESORT_H

-/*
- * Sort linked list in place.
- * - get_next_fn() returns the next element given an element of a linked list.
- * - set_next_fn() takes two elements A and B, and makes B the "next" element
- *   of A on the list.
- * - compare_fn() takes two elements A and B, and returns negative, 0, positive
- *   as the same sign as "subtracting" B from A.
- */
-void *llist_mergesort(void *list,
-		      void *(*get_next_fn)(const void *),
-		      void (*set_next_fn)(void *, void *),
-		      int (*compare_fn)(const void *, const void *));
-
 /* Combine two sorted lists.  Take from `list` on equality. */
 #define DEFINE_LIST_MERGE_INTERNAL(name, type)				\
 static type *name##__merge(type *list, type *other,			\