Changeset 788ccb04 in mainline

Timestamp:

2005-09-11T13:38:48Z (19 years ago)

Author:

Sergey Bondari <bondari@…>

Branches:

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

Children:

272f4271

Parents:

ddd9486

Message:

More effective memory allocations with help of qsort wrapper method

File:

• src/lib/sort.c (modified) (2 diffs)

src/lib/sort.c

@@ -30 +30 @@
 #include <memstr.h>
 #include <sort.h>
+#include <panic.h>
 
+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)) {
-        if (n > 4) {
-                int i = 0, j = n - 1;
-                void * tmp = (void *) malloc(e_size);
-                void * pivot = (void *) malloc(e_size);
+        void * tmp = (void *) malloc(e_size);
+        void * pivot = (void *) malloc(e_size);
+        
+        if (!tmp || !pivot) {
+                panic("qsort(): Cannot allocate memory\n");
+        }
 
-                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;
-                        }
-                }
-
-                free(tmp);
-                free(pivot);
-
-                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);
-        }
+        _qsort(data, n, e_size, cmp, pivot, tmp);
+        
+        free(tmp);
+        free(pivot);
 }
 
@@ -83 +72 @@
 }
 
+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