MFZE1

8 files changed, 152 insertions, 18 deletions

diff --git a/Zend/Makefile.am b/Zend/Makefile.am
index f30286a1cc..c8d6c39011 100644
--- a/Zend/Makefile.am
+++ b/Zend/Makefile.am
@@ -13,7 +13,7 @@ libZend_la_SOURCES=\
 	zend_opcode.c zend_operators.c zend_ptr_stack.c zend_stack.c \
 	zend_variables.c zend.c zend_API.c zend_extensions.c zend_hash.c \
 	zend_list.c zend_indent.c zend_builtin_functions.c zend_sprintf.c \
-	zend_ini.c zend_objects.c
+	zend_ini.c zend_qsort.c zend_objects.c
 
 libZend_la_LDFLAGS = @EXTRA_LIBS@
 
diff --git a/Zend/zend_hash.c b/Zend/zend_hash.c
index 5bb35d6e52..f51c277fbc 100644
--- a/Zend/zend_hash.c
+++ b/Zend/zend_hash.c
@@ -1088,7 +1088,7 @@ ZEND_API int zend_hash_get_current_data_ex(HashTable *ht, void **pData, HashPosi
 
 
 ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func,
-							compare_func_t compar, int renumber)
+							compare_func_t compar, int renumber TSRMLS_DC)
 {
 	Bucket **arTmp;
 	Bucket *p;
@@ -1111,7 +1111,7 @@ ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func,
 		i++;
 	}
 
-	(*sort_func)((void *) arTmp, i, sizeof(Bucket *), compar);
+	(*sort_func)((void *) arTmp, i, sizeof(Bucket *), compar TSRMLS_CC);
 
 	HANDLE_BLOCK_INTERRUPTIONS();
 	ht->pListHead = arTmp[0];
@@ -1134,7 +1134,7 @@ ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func,
 		i=0;
 		while (p != NULL) {
 			p->nKeyLength = 0;
-			p->h = i++;
+			;
 			p = p->pListNext;
 		}
 		ht->nNextFreeElement = i;
@@ -1212,7 +1212,7 @@ ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t co
 				}
 			}
 		}
-		result = compar(p1->pData, pData2);
+		result = compar(p1->pData, pData2 TSRMLS_CC);
 		if (result!=0) {
 			HASH_UNPROTECT_RECURSION(ht1); 
 			HASH_UNPROTECT_RECURSION(ht2); 
@@ -1230,7 +1230,7 @@ ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t co
 }
 
 
-ZEND_API int zend_hash_minmax(HashTable *ht, int (*compar) (const void *, const void *), int flag, void **pData)
+ZEND_API int zend_hash_minmax(HashTable *ht, compare_func_t compar, int flag, void **pData TSRMLS_DC)
 {
 	Bucket *p, *res;
 
@@ -1244,11 +1244,11 @@ ZEND_API int zend_hash_minmax(HashTable *ht, int (*compar) (const void *, const
 	res = p = ht->pListHead;
 	while ((p = p->pListNext)) {
 		if (flag) {
-			if (compar(&res, &p) < 0) { /* max */
+			if (compar(&res, &p TSRMLS_CC) < 0) { /* max */
 				res = p;
 			}
 		} else {
-			if (compar(&res, &p) > 0) { /* min */
+			if (compar(&res, &p TSRMLS_CC) > 0) { /* min */
 				res = p;
 			}
 		}
diff --git a/Zend/zend_hash.h b/Zend/zend_hash.h
index 62bcab1f9f..b5d22211e4 100644
--- a/Zend/zend_hash.h
+++ b/Zend/zend_hash.h
@@ -34,8 +34,8 @@
 #define HASH_DEL_INDEX 1
 
 typedef ulong (*hash_func_t)(char *arKey, uint nKeyLength);
-typedef int  (*compare_func_t)(const void *, const void *);
-typedef void (*sort_func_t)(void *, size_t, register size_t, compare_func_t);
+typedef int  (*compare_func_t)(const void *, const void * TSRMLS_DC);
+typedef void (*sort_func_t)(void *, size_t, register size_t, compare_func_t TSRMLS_DC);
 typedef void (*dtor_func_t)(void *pDest);
 typedef void (*copy_ctor_func_t)(void *pElement);
 
@@ -179,9 +179,9 @@ ZEND_API void zend_hash_internal_pointer_end_ex(HashTable *ht, HashPosition *pos
 ZEND_API void zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size);
 ZEND_API void zend_hash_merge(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, void *tmp, uint size, int overwrite);
 ZEND_API void zend_hash_merge_ex(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, uint size, zend_bool (*pReplaceOrig)(void *orig, void *p_new));
-ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func, compare_func_t compare_func, int renumber);
+ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func, compare_func_t compare_func, int renumber TSRMLS_DC);
 ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered TSRMLS_DC);
-ZEND_API int zend_hash_minmax(HashTable *ht, int (*compar)(const void *, const void *), int flag, void **pData);
+ZEND_API int zend_hash_minmax(HashTable *ht, compare_func_t compar, int flag, void **pData TSRMLS_DC);
 
 ZEND_API int zend_hash_num_elements(HashTable *ht);
 
diff --git a/Zend/zend_ini.c b/Zend/zend_ini.c
index e5986273a3..6a87189e20 100644
--- a/Zend/zend_ini.c
+++ b/Zend/zend_ini.c
@@ -20,6 +20,7 @@
 #include <stdlib.h>
 
 #include "zend.h"
+#include "zend_qsort.h"
 #include "zend_API.h"
 #include "zend_ini.h"
 #include "zend_alloc.h"
@@ -97,7 +98,7 @@ ZEND_API int zend_copy_ini_directives(TSRMLS_D)
 }
 
 
-static int ini_key_compare(const void *a, const void *b)
+static int ini_key_compare(const void *a, const void *b TSRMLS_DC)
 {
 	Bucket *f;
 	Bucket *s;
@@ -119,7 +120,7 @@ static int ini_key_compare(const void *a, const void *b)
 
 ZEND_API void zend_ini_sort_entries(TSRMLS_D)
 {
-	zend_hash_sort(&EG(ini_directives), qsort, ini_key_compare, 0);
+	zend_hash_sort(&EG(ini_directives), zend_qsort, ini_key_compare, 0 TSRMLS_CC);
 }
 
 /*
diff --git a/Zend/zend_llist.c b/Zend/zend_llist.c
index 9eb1f109b1..5ed13f0077 100644
--- a/Zend/zend_llist.c
+++ b/Zend/zend_llist.c
@@ -20,6 +20,7 @@
 
 #include "zend.h"
 #include "zend_llist.h"
+#include "zend_qsort.h"
 
 ZEND_API void zend_llist_init(zend_llist *l, size_t size, llist_dtor_func_t dtor, unsigned char persistent)
 {
@@ -187,7 +188,7 @@ ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func TSRMLS_DC)
 	}
 }
 
-ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func)
+ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func TSRMLS_DC)
 {
 	size_t i;
 
@@ -206,7 +207,7 @@ ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func)
 		*ptr++ = element;
 	}
 
-	qsort(elements, l->count, sizeof(zend_llist_element *), (int (*)(const void *, const void *)) comp_func);
+	zend_qsort(elements, l->count, sizeof(zend_llist_element *), (compare_func_t) comp_func TSRMLS_CC);
 
 	l->head = elements[0];
 	elements[0]->prev = NULL;
diff --git a/Zend/zend_llist.h b/Zend/zend_llist.h
index 1f2e07f151..3d702abbae 100644
--- a/Zend/zend_llist.h
+++ b/Zend/zend_llist.h
@@ -30,7 +30,7 @@ typedef struct _zend_llist_element {
 } zend_llist_element;
 
 typedef void (*llist_dtor_func_t)(void *);
-typedef int (*llist_compare_func_t)(const zend_llist_element *, const zend_llist_element *);
+typedef int (*llist_compare_func_t)(const zend_llist_element *, const zend_llist_element * TSRMLS_DC);
 typedef void (*llist_apply_with_args_func_t)(void *data, int num_args, va_list args TSRMLS_DC);
 typedef void (*llist_apply_with_arg_func_t)(void *data, void *arg TSRMLS_DC);
 typedef void (*llist_apply_func_t)(void * TSRMLS_DC);
@@ -61,7 +61,7 @@ ZEND_API void zend_llist_apply_with_del(zend_llist *l, int (*func)(void *data));
 ZEND_API void zend_llist_apply_with_argument(zend_llist *l, llist_apply_with_arg_func_t func, void *arg TSRMLS_DC);
 ZEND_API void zend_llist_apply_with_arguments(zend_llist *l, llist_apply_with_args_func_t func TSRMLS_DC, int num_args, ...);
 ZEND_API int zend_llist_count(zend_llist *l);
-ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func);
+ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func TSRMLS_DC);
 
 /* traversal */
 ZEND_API void *zend_llist_get_first_ex(zend_llist *l, zend_llist_position *pos);
diff --git a/Zend/zend_qsort.c b/Zend/zend_qsort.c
new file mode 100644
index 0000000000..63056584cb
--- /dev/null
+++ b/Zend/zend_qsort.c
@@ -0,0 +1,106 @@
+/*
+   +----------------------------------------------------------------------+
+   | Zend Engine                                                          |
+   +----------------------------------------------------------------------+
+   | Copyright (c) 1998-2001 Zend Technologies Ltd. (http://www.zend.com) |
+   +----------------------------------------------------------------------+
+   | This source file is subject to version 0.92 of the Zend license,     |
+   | that is bundled with this package in the file LICENSE, and is        | 
+   | available at through the world-wide-web at                           |
+   | http://www.zend.com/license/0_92.txt.                                |
+   | If you did not receive a copy of the Zend license and are unable to  |
+   | obtain it through the world-wide-web, please send a note to          |
+   | license@zend.com so we can mail you a copy immediately.              |
+   +----------------------------------------------------------------------+
+   | Authors: Sterling Hughes <sterling@php.net>                          |
+   +----------------------------------------------------------------------+
+*/
+
+#include "zend.h"
+
+#include <limits.h>
+
+#define QSORT_STACK_SIZE (sizeof(size_t) * CHAR_BIT)
+
+static void _zend_qsort_swap(void *a, void *b, size_t siz)
+{
+	register size_t i;
+	register int    t_i;
+	register char   t_c;
+	
+	for (i = sizeof(int); i <= siz; i += sizeof(int)) {
+		t_i = *(int *) a;
+		*((int *) a)++ = *(int *) b;
+		*((int *) b)++ = t_i;
+	}
+
+	for (i = i - sizeof(int) + 1; i <= siz; ++i) {
+		t_c = *(char *) a;
+		*((char *) a)++ = *(char *) b;
+		*((char *) b)++ = t_c;
+	}
+}
+
+ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC)
+{
+	void           *begin_stack[QSORT_STACK_SIZE];
+	void           *end_stack[QSORT_STACK_SIZE];
+	register char  *begin;
+	register char  *end;
+	register char  *seg1;
+	register char  *seg2;
+	register char  *seg2p;
+	register int    loop;
+	uint            offset;
+
+	begin_stack[0] = (char *) base;
+	end_stack[0]   = (char *) base + ((nmemb - 1) * siz);
+
+	for (loop = 0; loop >= 0; --loop) {
+		begin = begin_stack[loop];
+		end   = end_stack[loop];
+
+		while (begin < end) {
+			offset = (end - begin) >> 1;
+			_zend_qsort_swap(begin, begin + (offset - (offset % siz)), siz);
+
+			seg1 = begin + siz;
+			seg2 = end;
+
+			while (1) {
+				for (; seg1 < seg2 && compare(begin, seg1 TSRMLS_CC) > 0;
+				     seg1 += siz);
+
+				for (; seg2 >= seg1 && compare(seg2, begin TSRMLS_CC) > 0;
+				     seg2 -= siz);
+				
+				if (seg1 >= seg2)
+					break;
+				
+				_zend_qsort_swap(seg1, seg2, siz);
+
+				seg1 += siz;
+				seg2 -= siz;
+			}
+
+			_zend_qsort_swap(begin, seg2, siz);
+
+			seg2p = seg2;
+			
+			if ((seg2p - begin) <= (end - seg2p)) {
+				if ((seg2p + siz) < end) {
+					begin_stack[loop] = seg2p + siz;
+					end_stack[loop++] = end;
+				}
+				end = seg2p - siz;
+			}
+			else {
+				if ((seg2p - siz) > begin) {
+					begin_stack[loop] = begin;
+					end_stack[loop++] = seg2p - siz;
+				}
+				begin = seg2p + siz;
+			}
+		}
+	}
+}
diff --git a/Zend/zend_qsort.h b/Zend/zend_qsort.h
new file mode 100644
index 0000000000..3ee3c3db30
--- /dev/null
+++ b/Zend/zend_qsort.h
@@ -0,0 +1,26 @@
+/*
+   +----------------------------------------------------------------------+
+   | Zend Engine                                                          |
+   +----------------------------------------------------------------------+
+   | Copyright (c) 1998-2001 Zend Technologies Ltd. (http://www.zend.com) |
+   +----------------------------------------------------------------------+
+   | This source file is subject to version 0.92 of the Zend license,     |
+   | that is bundled with this package in the file LICENSE, and is        | 
+   | available at through the world-wide-web at                           |
+   | http://www.zend.com/license/0_92.txt.                                |
+   | If you did not receive a copy of the Zend license and are unable to  |
+   | obtain it through the world-wide-web, please send a note to          |
+   | license@zend.com so we can mail you a copy immediately.              |
+   +----------------------------------------------------------------------+
+   | Authors: Sterling Hughes <sterling@php.net>                          |
+   +----------------------------------------------------------------------+
+*/
+
+#ifndef ZEND_QSORT_H
+#define ZEND_QSORT_H
+
+BEGIN_EXTERN_C()
+ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC);
+END_EXTERN_C()
+
+#endif       /* ZEND_QSORT_H */