Changes in uspace/lib/c/generic/sort.c [c6c49de:549012c] in mainline

File:

• uspace/lib/c/generic/sort.c (modified) (8 diffs)

uspace/lib/c/generic/sort.c

@@ -36 +36 @@
  *
  * This files contains functions implementing several sorting
- * algorithms (e.g. quick sort and gnome sort).
+ * algorithms (e.g. quick sort and bubble sort).
  *
  */
@@ -44 +44 @@
 #include <malloc.h>
 
-/** Immediate buffer size.
+/** Bubble sort
  *
- * For small buffer sizes avoid doing malloc()
- * and use the stack.
- *
- */
-#define IBUF_SIZE  32
-
-/** Array accessor.
- *
- */
-#define INDEX(buf, i, elem_size)  ((buf) + (i) * (elem_size))
-
-/** Gnome sort
- *
- * Apply generic gnome sort algorithm on supplied data,
+ * Apply generic bubble sort algorithm on supplied data,
  * using pre-allocated buffer.
  *
@@ -71 +58 @@
  *
  */
-static void _gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp,
+static void _bsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp,
     void *arg, void *slot)
 {
-        size_t i = 0;
+        bool done = false;
+        void *tmp;
         
-        while (i < cnt) {
-                if ((i != 0) &&
-                    (cmp(INDEX(data, i, elem_size),
-                    INDEX(data, i - 1, elem_size), arg) == -1)) {
-                        memcpy(slot, INDEX(data, i, elem_size), elem_size);
-                        memcpy(INDEX(data, i, elem_size), INDEX(data, i - 1, elem_size),
-                            elem_size);
-                        memcpy(INDEX(data, i - 1, elem_size), slot, elem_size);
-                        i--;
-                } else
-                        i++;
+        while (!done) {
+                done = true;
+                
+                for (tmp = data; tmp < data + elem_size * (cnt - 1);
+                    tmp = tmp + elem_size) {
+                        if (cmp(tmp, tmp + elem_size, arg) == 1) {
+                                memcpy(slot, tmp, elem_size);
+                                memcpy(tmp, tmp + elem_size, elem_size);
+                                memcpy(tmp + elem_size, slot, elem_size);
+                                done = false;
+                        }
+                }
         }
 }
@@ -100 +89 @@
  * @param cmp       Comparator function.
  * @param arg       3rd argument passed to cmp.
- * @param slot      Pointer to scratch memory buffer
+ * @param tmp       Pointer to scratch memory buffer
  *                  elem_size bytes long.
  * @param pivot     Pointer to scratch memory buffer
@@ -107 +96 @@
  */
 static void _qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp,
-    void *arg, void *slot, void *pivot)
+    void *arg, void *tmp, void *pivot)
 {
         if (cnt > 4) {
@@ -116 +105 @@
                 
                 while (true) {
-                        while ((cmp(INDEX(data, i, elem_size), pivot, arg) < 0) && (i < cnt))
+                        while ((cmp(data + i * elem_size, pivot, arg) < 0) && (i < cnt))
                                 i++;
                         
-                        while ((cmp(INDEX(data, j, elem_size), pivot, arg) >= 0) && (j > 0))
+                        while ((cmp(data + j * elem_size, pivot, arg) >= 0) && (j > 0))
                                 j--;
                         
                         if (i < j) {
-                                memcpy(slot, INDEX(data, i, elem_size), elem_size);
-                                memcpy(INDEX(data, i, elem_size), INDEX(data, j, elem_size),
+                                memcpy(tmp, data + i * elem_size, elem_size);
+                                memcpy(data + i * elem_size, data + j * elem_size,
                                     elem_size);
-                                memcpy(INDEX(data, j, elem_size), slot, elem_size);
+                                memcpy(data + j * elem_size, tmp, elem_size);
                         } else
                                 break;
                 }
                 
-                _qsort(data, j + 1, elem_size, cmp, arg, slot, pivot);
-                _qsort(INDEX(data, j + 1, elem_size), cnt - j - 1, elem_size,
-                    cmp, arg, slot, pivot);
+                _qsort(data, j + 1, elem_size, cmp, arg, tmp, pivot);
+                _qsort(data + (j + 1) * elem_size, cnt - j - 1, elem_size,
+                    cmp, arg, tmp, pivot);
         } else
-                _gsort(data, cnt, elem_size, cmp, arg, slot);
+                _bsort(data, cnt, elem_size, cmp, arg, tmp);
 }
 
-/** Gnome sort wrapper
+/** Bubble sort wrapper
  *
  * This is only a wrapper that takes care of memory
  * allocations for storing the slot element for generic
- * gnome sort algorithm.
+ * bubble sort algorithm.
  *
  * @param data      Pointer to data to be sorted.
@@ -153 +142 @@
  *
  */
-bool gsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg)
+bool bsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg)
 {
-        uint8_t ibuf_slot[IBUF_SIZE];
-        void *slot;
+        void *slot = (void *) malloc(elem_size);
+        if (!slot)
+                return false;
         
-        if (elem_size > IBUF_SIZE) {
-                slot = (void *) malloc(elem_size);
-                if (!slot)
-                        return false;
-        } else
-                slot = (void *) ibuf_slot;
+        _bsort(data, cnt, elem_size, cmp, arg, slot);
         
-        _gsort(data, cnt, elem_size, cmp, arg, slot);
-        
-        if (elem_size > IBUF_SIZE)
-                free(slot);
+        free(slot);
         
         return true;
@@ -190 +172 @@
 bool qsort(void *data, size_t cnt, size_t elem_size, sort_cmp_t cmp, void *arg)
 {
-        uint8_t ibuf_slot[IBUF_SIZE];
-        uint8_t ibuf_pivot[IBUF_SIZE];
-        void *slot;
-        void *pivot;
+        void *tmp = (void *) malloc(elem_size);
+        if (!tmp)
+                return false;
         
-        if (elem_size > IBUF_SIZE) {
-                slot = (void *) malloc(elem_size);
-                if (!slot)
-                        return false;
-                
-                pivot = (void *) malloc(elem_size);
-                if (!pivot) {
-                        free(slot);
-                        return false;
-                }
-        } else {
-                slot = (void *) ibuf_slot;
-                pivot = (void *) ibuf_pivot;
+        void *pivot = (void *) malloc(elem_size);
+        if (!pivot) {
+                free(tmp);
+                return false;
         }
         
-        _qsort(data, cnt, elem_size, cmp, arg, slot, pivot);
+        _qsort(data, cnt, elem_size, cmp, arg, tmp, pivot);
         
-        if (elem_size > IBUF_SIZE) {
-                free(pivot);
-                free(slot);
-        }
+        free(pivot);
+        free(tmp);
         
         return true;