add qsort implementation.

git-svn-id: https://rt-thread.googlecode.com/svn/trunk@1036 bbd45198-f89e-11dd-88c7-29a3b14d5316

3 files changed, 51 insertions, 0 deletions

diff --git a/components/libc/minilibc/qsort.c b/components/libc/minilibc/qsort.c
new file mode 100644
index 0000000000..6240057132
--- /dev/null
+++ b/components/libc/minilibc/qsort.c
@@ -0,0 +1,46 @@
+#include <sys/cdefs.h>

+#include <sys/types.h>

+

+#include <stdlib.h>

+

+static void exch(char* base,size_t size,size_t a,size_t b) {

+  char* x=base+a*size;

+  char* y=base+b*size;

+  while (size) {

+    char z=*x;

+    *x=*y;

+    *y=z;

+    --size; ++x; ++y;

+  }

+}

+

+/* Quicksort with 3-way partitioning, ala Sedgewick */

+/* Blame him for the scary variable names */

+/* http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf */

+static void quicksort(char* base,size_t size,ssize_t l,ssize_t r,

+		      int (*compar)(const void*,const void*)) {

+  ssize_t i=l-1, j=r, p=l-1, q=r, k;

+  char* v=base+r*size;

+  if (r<=l) return;

+  for (;;) {

+    while (++i != r && compar(base+i*size,v)<0) ;

+    while (compar(v,base+(--j)*size)<0) if (j == l) break;

+    if (i >= j) break;

+    exch(base,size,i,j);

+    if (compar(base+i*size,v)==0) exch(base,size,++p,i);

+    if (compar(v,base+j*size)==0) exch(base,size,j,--q);

+  }

+  exch(base,size,i,r); j = i-1; ++i;

+  for (k=l; k<p; k++, j--) exch(base,size,k,j);

+  for (k=r-1; k>q; k--, i++) exch(base,size,i,k);

+  quicksort(base,size,l,j,compar);

+  quicksort(base,size,i,r,compar);

+}

+

+void qsort(void* base,size_t nmemb,size_t size,int (*compar)(const void*,const void*)) {

+  /* check for integer overflows */

+  if (nmemb >= (((size_t)-1)>>1) ||

+      size >= (((size_t)-1)>>1)) return;

+  if (nmemb>1)

+    quicksort(base,size,0,nmemb-1,compar);

+}

diff --git a/components/libc/minilibc/stdlib.h b/components/libc/minilibc/stdlib.h
index 93c9b19b5c..e91a176089 100644
--- a/components/libc/minilibc/stdlib.h
+++ b/components/libc/minilibc/stdlib.h
@@ -15,6 +15,8 @@
 #ifndef __STDLIB_H__

 #define __STDLIB_H__

 

+#include <sys/types.h>

+

 #if !defined (RT_USING_NEWLIB) && defined (RT_USING_MINILIBC)

 int atoi(const char *nptr);

 #endif

@@ -28,4 +30,6 @@ int rand(void);
 int rand_r(unsigned int *seed);

 void srand(unsigned int seed);

 

+void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));

+

 #endif

diff --git a/components/libc/minilibc/sys/types.h b/components/libc/minilibc/sys/types.h
index fa0a236636..a2dbee5256 100644
--- a/components/libc/minilibc/sys/types.h
+++ b/components/libc/minilibc/sys/types.h
@@ -5,6 +5,7 @@
 
 typedef long    	off_t;
 typedef rt_size_t 	size_t;
+typedef signed long ssize_t;		/* Used for a count of bytes or an error indication. */
 
 typedef rt_uint8_t 	u_char;
 typedef rt_uint16_t u_short;