Subversion Repositories HelenOS

Rev

Rev 333 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. #include <mm/heap.h>
  2. #include <memstr.h>
  3. #include <sort.h>
  4.  
  5.  
  6. void qsort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
  7.  
  8.     if (n > 4) {
  9.         int i = 0, j = n - 1;
  10.         void * tmp = (void *) malloc(e_size);
  11.         void * pivot = (void *) malloc(e_size);
  12.  
  13.         memcpy(pivot, data, e_size);
  14.  
  15.         while (1) {
  16.             while ((cmp(data + i * e_size, pivot) < 0) && i < n) i++;
  17.             while ((cmp(data + j * e_size, pivot) >=0) && j > 0) j--;
  18.  
  19.             if (i<j) {
  20.                 memcpy(tmp, data + i * e_size, e_size);
  21.                 memcpy(data + i * e_size, data + j * e_size, e_size);
  22.                 memcpy(data + j * e_size, tmp, e_size);
  23.             } else {
  24.                 break;
  25.             }
  26.         }
  27.  
  28.         free(tmp);
  29.         free(pivot);
  30.  
  31.         qsort(data, j + 1, e_size, cmp);
  32.         qsort(data + (j + 1) * e_size, n - j - 1, e_size, cmp);
  33.  
  34.     } else {
  35.         bubblesort(data, n, e_size, cmp);
  36.     }
  37.  
  38.  
  39. }
  40.  
  41.  
  42. void bubblesort(void * data, count_t n, size_t e_size, int (* cmp) (void * a, void * b)) {
  43.     bool done = false;
  44.     void * p;
  45.     void * slot = (void *) malloc(e_size);
  46.  
  47.     while (!done) {
  48.         done = true;
  49.         for (p = data; p < data + e_size * (n - 1); p = p + e_size) {
  50.             if (cmp(p, p + e_size) == 1) {
  51.                 memcpy(slot, p, e_size);
  52.                 memcpy(p, p + e_size, e_size);
  53.                 memcpy(p + e_size, slot, e_size);
  54.                 done = false;
  55.             }
  56.         }
  57.  
  58.     }
  59.  
  60.     free(slot);
  61. }
  62.  
  63. /*
  64.  * Comparator returns 1 if a > b, 0 if a == b, -1 if a < b
  65.  */
  66. int int_cmp(void * a, void * b) {
  67.     return (* (int *) a > * (int*)b) ? 1 : (*(int *)a < * (int *)b) ? -1 : 0;
  68. }
  69.  
  70. int __u8_cmp(void * a, void * b) {
  71.     return (* (__u8 *) a > * (__u8 *)b) ? 1 : (*(__u8 *)a < * (__u8 *)b) ? -1 : 0;
  72. }
  73.  
  74. int __u16_cmp(void * a, void * b) {
  75.     return (* (__u16 *) a > * (__u16 *)b) ? 1 : (*(__u16 *)a < * (__u16 *)b) ? -1 : 0;
  76. }
  77.  
  78. int __u32_cmp(void * a, void * b) {
  79.     return (* (__u32 *) a > * (__u32 *)b) ? 1 : (*(__u32 *)a < * (__u32 *)b) ? -1 : 0;
  80. }
  81.  
  82.