-/* A "counting" merge sort that avoids recursion */
+/*
+ * sort.frag.h: Common implementation of linked-list sorting
+ *
+ * Author:
+ * Raja R Harinath (rharinath@novell.com)
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+ * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+ * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+ * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ *
+ * (C) 2006 Novell, Inc.
+ */
-#define N_DIGITS (sizeof (size_t) * 8)
+/*
+ * This code requires a typedef named 'list_node' for the list node. It
+ * is assumed that the list type is the type of a pointer to a list
+ * node, and that the node has a field named 'next' that implements to
+ * the linked list. No additional invariant is maintained (e.g. the
+ * 'prev' pointer of a doubly-linked list node is _not_ updated). Any
+ * invariant would require a post-processing pass to fix matters if
+ * necessary.
+ *
+ * Note: We refer to a list fragment as a "digit" because the code for
+ * maintaining the invariants of the core data structure parallels the
+ * code for incrementing the binary representation of a number.
+ */
+typedef list_node *digit;
+
+/*
+ * The maximum possible depth of the merge tree
+ * = ceiling (log2 (maximum number of list nodes))
+ * = ceiling (log2 (maximum possible memory size/size of each list node))
+ * = number of bits in 'size_t' - floor (log2 (sizeof digit))
+ * Also, each "digit" is at least 2 nodes long: we can reduce the depth by 1
+ */
+
+#define FLOOR_LOG2(x) (((x)>=2) + ((x)>=4) + ((x)>=8) + ((x)>=16) + ((x)>=32) + ((x)>=64) + ((x)>=128))
+#define MAX_DIGITS ((sizeof (size_t) * 8) - FLOOR_LOG2(sizeof (list_node)) - 1)
static inline digit
add_digits (digit first, digit second, GCompareFunc func)
}
static inline digit
-combine_digits (digit *digits, int max_digit, GCompareFunc func)
+combine_digits (digit *digits, digit list, int n_digits, GCompareFunc func)
{
int i;
- digit list = digits [0];
- for (i = 1; i <= max_digit; ++i)
+ for (i = 0; i < n_digits; ++i)
list = add_digits (digits [i], list, func);
return list;
}
+/*
+ * Given: length(list) == k
+ * Invariant: digit[i] == NULL || length(digit[i]) == k * 2**i
+ */
static inline int
-increment (digit *digits, digit list, int max_digit, GCompareFunc func)
+increment (digit *digits, digit list, int n_digits, GCompareFunc func)
{
int i;
-
- if (!list)
- return max_digit;
-
- for (i = 0; digits [i]; i++) {
+ for (i = 0; i < n_digits && digits [i]; i++) {
list = add_digits (digits [i], list, func);
digits [i] = NULL;
- if (i == N_DIGITS-1) /* Should _never_ happen, but if it does, we just devolve into quadratic ;-) */
- break;
}
+ if (i == MAX_DIGITS) /* Will _never_ happen: so we can just devolve into quadratic ;-) */
+ --i;
+
+ if (i == n_digits)
+ ++n_digits;
digits [i] = list;
- return i > max_digit ? i : max_digit;
+ return n_digits;
}
+/*
+ * A mergesort that avoids recursion. The 'digits' array essentially
+ * captures the recursion stack. The actual merge tree is built in a
+ * bottom-up manner. It's "counting", since we "increment" a set of
+ * "digit"s.
+ */
static inline digit
do_sort (digit list, GCompareFunc func)
{
- int max_digit = 0;
- digit digits [N_DIGITS]; /* 128 bytes on 32bit, 512 bytes on 64bit */
- memset (digits, 0, sizeof digits);
+ int n_digits = 0;
+ digit digits [MAX_DIGITS]; /* ~ 128 bytes on 32bit, ~ 512 bytes on 64bit */
while (list && list->next) {
digit next = list->next;
}
next->next = NULL;
- max_digit = increment (digits, list, max_digit, func);
+ n_digits = increment (digits, list, n_digits, func);
list = tail;
}
- max_digit = increment (digits, list, max_digit, func);
-
- return combine_digits (digits, max_digit, func);
+ return combine_digits (digits, list, n_digits, func);
}
-#undef N_DIGITS
+#undef MAX_DIGITS
+#undef FLOOR_LOG2
projects / mono.git / blobdiff