mergesort: add macros for typed sort of linked lists

[thirdparty/git.git] / mergesort.h

diff --git a/mergesort.h b/mergesort.h
index 644cff1f9640f4f3a146d7217a8deab34282ff53..7b4435528305dd88095775b8bab9f6308accc712 100644 (file)
--- a/mergesort.h
+++ b/mergesort.h
@@ -14,4 +14,105 @@ void *llist_mergesort(void *list,
                      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,                    \
+                          int (*compare_fn)(const type *, const type *))\
+{                                                                      \
+       type *result = list, *tail;                                     \
+       int prefer_list = compare_fn(list, other) <= 0;                 \
+                                                                       \
+       if (!prefer_list) {                                             \
+               result = other;                                         \
+               SWAP(list, other);                                      \
+       }                                                               \
+       for (;;) {                                                      \
+               do {                                                    \
+                       tail = list;                                    \
+                       list = name##__get_next(list);                  \
+                       if (!list) {                                    \
+                               name##__set_next(tail, other);          \
+                               return result;                          \
+                       }                                               \
+               } while (compare_fn(list, other) < prefer_list);        \
+               name##__set_next(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.
+ */
+#define DEFINE_LIST_SORT_INTERNAL(scope, name, type)                   \
+scope void name(type **listp,                                          \
+               int (*compare_fn)(const type *, const type *))          \
+{                                                                      \
+       type *list = *listp;                                            \
+       type *ranks[bitsizeof(type *)];                                 \
+       size_t n = 0;                                                   \
+                                                                       \
+       if (!list)                                                      \
+               return;                                                 \
+                                                                       \
+       for (;;) {                                                      \
+               int i;                                                  \
+               size_t m;                                               \
+               type *next = name##__get_next(list);                    \
+               if (next)                                               \
+                       name##__set_next(list, NULL);                   \
+               for (i = 0, m = n;; i++, m >>= 1) {                     \
+                       if (m & 1) {                                    \
+                               list = name##__merge(ranks[i], list,    \
+                                                   compare_fn);        \
+                       } else if (next) {                              \
+                               break;                                  \
+                       } else if (!m) {                                \
+                               *listp = list;                          \
+                               return;                                 \
+                       }                                               \
+               }                                                       \
+               n++;                                                    \
+               ranks[i] = list;                                        \
+               list = next;                                            \
+       }                                                               \
+}
+
+#define DECLARE_LIST_SORT(scope, name, type)                   \
+scope void name(type **listp,                                  \
+               int (*compare_fn)(const type *, const type *))
+
+#define DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, \
+                              on_get_next, on_set_next)        \
+                                                               \
+static inline type *name##__get_next(const type *elem)         \
+{                                                              \
+       on_get_next;                                            \
+       return elem->next_member;                               \
+}                                                              \
+                                                               \
+static inline void name##__set_next(type *elem, type *next)    \
+{                                                              \
+       on_set_next;                                            \
+       elem->next_member = next;                               \
+}                                                              \
+                                                               \
+DEFINE_LIST_MERGE_INTERNAL(name, type)                         \
+DEFINE_LIST_SORT_INTERNAL(scope, name, type)                   \
+DECLARE_LIST_SORT(scope, name, type)
+
+#define DEFINE_LIST_SORT(scope, name, type, next_member) \
+DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, (void)0, (void)0)
+
 #endif