_zend_qsort_swap() is broken, it only works when siz is sizeof(int) or
sizeof(char). The following patch fixes it:
+++ Zend/zend_qsort.c Wed Jan 16 22:46:11 2002
@@ -32,23 +32,24 @@
int t_i;
char t_c;
- for (i = sizeof(int); i <= siz; i += sizeof(int)) {
- tmp_a_int = (int *) a;
- tmp_b_int = (int *) b;
+ tmp_a_int = (int *) a;
+ tmp_b_int = (int *) b;
+ for (i = sizeof(int); i <= siz; i += sizeof(int)) {
t_i = *tmp_a_int;
-
- *tmp_a_int++ = *(int *) b;
+ *tmp_a_int++ = *tmp_b_int;
*tmp_b_int++ = t_i;
}
- for (i = i - sizeof(int) + 1; i <= siz; ++i) {
- tmp_a_char = (char *) a;
- tmp_b_char = (char *) b;
+ if (i - sizeof(int) == siz)
+ return;
- t_c = *tmp_a_char;
+ tmp_a_char = (char *) a;
+ tmp_b_char = (char *) b;
- *tmp_a_char++ = *(char *) b;
+ for (i = i - sizeof(int) + 1; i <= siz; ++i) {
+ t_c = *tmp_a_char;
+ *tmp_a_char++ = *tmp_b_char;
*tmp_b_char++ = t_c;
}
}
Another thing which I don't like, is that it doesn't preserve the order
of "equal" values. This is a problem for array_unique(), see bug #14805.
The reason is that instead of storing the pivot separately by copying
the middle value, the first and middle values are exchanged in order to
store the pivot in the first value (I know, that's not quite clear, but
if you look at the code and understand quicksort, you know what I mean).
Can we please fix this? I can submit a patch if you like. Another slight
improvement is to compare the pivot candidate (middle) with first and
last, and sort those. This gives better performance in some cases, and
it isn't really a penalty since these comparisons then can be skipped
in the following loops by setting seg1 = begin + siz and seg2 = end - siz.
With these changes I think the performance would be about as good as now.
The big penalty is memory allocation for the pivot I guess, but it is
done only once for the entire sort, so I think it is okay.
Stig
--
PHP Development Mailing List <http://www.php.net/>
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
To contact the list administrators, e-mail: [EMAIL PROTECTED]
