Changeset 0a50f59 in mainline

Timestamp:

2005-09-15T21:19:40Z (19 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

6799505

Parents:

01e48c1

Message:

Remove _qsort() as its concept is fundamentally broken.

Move lib/the.c to proc/the.c.

Location:

src

Files:

• Makefile (modified) (2 diffs)
• lib/sort.c (modified) (4 diffs)
• proc/the.c (moved) (moved from src/lib/the.c )

src/Makefile

@@ -9 +9 @@
         proc/thread.c \
         proc/task.c \
+        proc/the.c \
         mm/heap.c \
         mm/frame.c \
@@ -17 +18 @@
         lib/list.c \
         lib/memstr.c \
-        lib/the.c \
         lib/sort.c \
         debug/print.c \

src/lib/sort.c

@@ -34 +34 @@
 #define EBUFSIZE        32
 
-static void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void * pivot, void * tmp);
-
-/*
- * Wrapper method for quicksort algorithm to decrease amount of allocations
- */
-void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
+void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b))
+{
         __u8 buf_tmp[EBUFSIZE];
         __u8 buf_pivot[EBUFSIZE];
@@ -54 +50 @@
         }
 
-        _qsort(data, n, e_size, cmp, pivot, tmp);
+        if (n > 4) {
+                int i = 0, j = n - 1;
+
+                memcpy(pivot, data, e_size);
+
+                while (1) {
+                        while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++;
+                        while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--;
+                        if (i<j) {
+                                memcpy(tmp, data + i * e_size, e_size);
+                                memcpy(data + i * e_size, data + j * e_size, e_size);
+                                memcpy(data + j * e_size, tmp, e_size);
+                        } else {
+                                break;
+                        }
+                }
+
+                qsort(data, j + 1, e_size, cmp);
+                qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp);
+        } else {
+                bubblesort(data, n, e_size, cmp);
+        }
+
         
         if (e_size > EBUFSIZE) {
@@ -63 +81 @@
 
 
-void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
+void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b))
+{
         __u8 buf_slot[EBUFSIZE];
         bool done = false;
@@ -94 +113 @@
 }
 
-static void _qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b), void * pivot, void * tmp) {
-        if (n > 4) {
-                int i = 0, j = n - 1;
-
-                memcpy(pivot, data, e_size);
-
-                while (1) {
-                        while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++;
-                        while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--;
-                        if (i<j) {
-                                memcpy(tmp, data + i * e_size, e_size);
-                                memcpy(data + i * e_size, data + j * e_size, e_size);
-                                memcpy(data + j * e_size, tmp, e_size);
-                        } else {
-                                break;
-                        }
-                }
-
-                qsort(data, j + 1, e_size, cmp);
-                qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp);
-        } else {
-                bubblesort(data, n, e_size, cmp);
-        }
-}
-
-
-
 /*
  * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b
  */
-int int_cmp(void * a, void * b) {
+int int_cmp(void * a, void * b)
+{
         return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0;
 }
 
-int __u8_cmp(void * a, void * b) {
+int __u8_cmp(void * a, void * b)
+{
         return (* (__u8 *) a > * (__u8 *)b) ? 1 : (*(__u8 *)a < * (__u8 *)b) ? -1 : 0;
 }
 
-int __u16_cmp(void * a, void * b) {
+int __u16_cmp(void * a, void * b)
+{
         return (* (__u16 *) a > * (__u16 *)b) ? 1 : (*(__u16 *)a < * (__u16 *)b) ? -1 : 0;
 }
 
-int __u32_cmp(void * a, void * b) {
+int __u32_cmp(void * a, void * b)
+{
         return (* (__u32 *) a > * (__u32 *)b) ? 1 : (*(__u32 *)a < * (__u32 *)b) ? -1 : 0;
 }
-