summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRené Scharfe <l.s.r@web.de>2022-07-16 17:02:38 (GMT)
committerJunio C Hamano <gitster@pobox.com>2022-07-17 22:20:39 (GMT)
commit0f1eb7d6e976c64c0016d4355200660ce2fdf1ec (patch)
tree6af1dad6c23abda33f8f7329b495d64c807dfefe
parent9b9f5f6217a5178e348dc2e18bc6af7158b97c36 (diff)
downloadgit-0f1eb7d6e976c64c0016d4355200660ce2fdf1ec.zip
git-0f1eb7d6e976c64c0016d4355200660ce2fdf1ec.tar.gz
git-0f1eb7d6e976c64c0016d4355200660ce2fdf1ec.tar.bz2
mergesort: remove llist_mergesort()
Now that all of its callers are gone, remove llist_mergesort(). Signed-off-by: René Scharfe <l.s.r@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
-rw-r--r--Makefile1
-rw-r--r--mergesort.c76
-rw-r--r--mergesort.h13
3 files changed, 0 insertions, 90 deletions
diff --git a/Makefile b/Makefile
index f8bccfa..6b2aa3b 100644
--- a/Makefile
+++ b/Makefile
@@ -973,7 +973,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 6bda3a1..0000000
--- 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 7b44355..7c36f08 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, \