* src/sort.frag.h: Add copyright notice and some explanation.

(increment): Remove null check.
(combine_digits): Add 'list' argument to seed the summation.
(do_sort): Use the empty or singleton tail as the seed, rather
than calling 'increment'.

svn path=/trunk/mono/; revision=64372

4 files changed, 82 insertions, 20 deletions

diff --git a/eglib/ChangeLog b/eglib/ChangeLog
index 9c3ffab1329..d258f6d401c 100644
--- a/eglib/ChangeLog
+++ b/eglib/ChangeLog
@@ -1,3 +1,11 @@
+2006-08-26  Raja R Harinath  <rharinath@novell.com>
+
+	* src/sort.frag.h: Add copyright notice and some explanation.
+	(increment): Remove null check.
+	(combine_digits): Add 'list' argument to seed the summation.
+	(do_sort): Use the empty or singleton tail as the seed, rather
+	than calling 'increment'.
+
 2006-08-25  Raja R Harinath  <rharinath@novell.com>
 
 	* TODO: Remove 'List' entries.
diff --git a/eglib/src/glist.c b/eglib/src/glist.c
index be4e213ca9b..6f679276ac6 100644
--- a/eglib/src/glist.c
+++ b/eglib/src/glist.c
@@ -1,8 +1,9 @@
 /*
  * glist.c: Doubly-linked list implementation
  *
- * Author:
+ * Authors:
  *   Duncan Mak (duncan@novell.com)
+ *   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
diff --git a/eglib/src/gslist.c b/eglib/src/gslist.c
index da8bb3a87a3..22fbcc85eaa 100644
--- a/eglib/src/gslist.c
+++ b/eglib/src/gslist.c
@@ -1,8 +1,9 @@
 /*
  * gslist.c: Singly-linked list implementation
  *
- * Author:
+ * Authors:
  *   Duncan Mak (duncan@novell.com)
+ *   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
diff --git a/eglib/src/sort.frag.h b/eglib/src/sort.frag.h
index 3e9e2dde1dd..72b0e6b3c4f 100644
--- a/eglib/src/sort.frag.h
+++ b/eglib/src/sort.frag.h
@@ -1,6 +1,54 @@
-/* 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 'digit' for the list type.  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.
+ */
+
+/*
+ * 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))
+ */
+
+#define FLOOR_LOG2(x) (((x)>=2) + ((x)>=4) + ((x)>=8) + ((x)>=16) + ((x)>=32) + ((x)>=64) + ((x)>=128))
+#define N_DIGITS ((sizeof (size_t) * 8) - FLOOR_LOG2(sizeof (digit)))
 
 static inline digit
 add_digits (digit first, digit second, GCompareFunc func)
@@ -23,38 +71,43 @@ 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 max_pos, GCompareFunc func)
 {
 	int i;
-	digit list = digits [0];
-	for (i = 1; i <= max_digit; ++i)
+	for (i = 0; i <= max_pos; ++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 max_pos, GCompareFunc func)
 {
 	int i;
-
-	if (!list)
-		return max_digit;
-
 	for (i = 0; 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 ;-) */
+		if (i == N_DIGITS-1) /* Will _never_ happen: so we can just devolve into quadratic ;-) */
 			break;
 	}
 	digits [i] = list;
-	return i > max_digit ? i : max_digit;
+	return i > max_pos ? i : max_pos;
 }
 
+/*
+ * 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 */
+	int max_pos = 0;
+	digit digits [N_DIGITS]; /* ~ 128 bytes on 32bit, ~ 512 bytes on 64bit */
 	memset (digits, 0, sizeof digits);
 
 	while (list && list->next) {
@@ -68,14 +121,13 @@ do_sort (digit list, GCompareFunc func)
 		}
 		next->next = NULL;
 
-		max_digit = increment (digits, list, max_digit, func);
+		max_pos = increment (digits, list, max_pos, func);
 
 		list = tail;
 	}
 
-	max_digit = increment (digits, list, max_digit, func);
-
-	return combine_digits (digits, max_digit, func);
+	return combine_digits (digits, list, max_pos, func);
 }
 
 #undef N_DIGITS
+#undef LOG2_FLOOR