LCOV - code coverage report
Current view: top level - lib/libc/minimal/source/stdlib - qsort.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 0 30 0.0 %
Date: 2022-08-18 11:36:24 Functions: 0 4 0.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 16 0.0 %

           Branch data     Line data    Source code
       1                 :            : /*
       2                 :            :  * Copyright (c) 2021 Friedt Professional Engineering Services, Inc
       3                 :            :  *
       4                 :            :  * SPDX-License-Identifier: Apache-2.0
       5                 :            :  */
       6                 :            : 
       7                 :            : #include <stddef.h>
       8                 :            : #include <stdint.h>
       9                 :            : #include <stdlib.h>
      10                 :            : #include <sys/types.h>
      11                 :            : #include <sys/util.h>
      12                 :            : 
      13                 :            : /*
      14                 :            :  * Normally parent is defined parent(k) = floor((k-1) / 2) but we can avoid a
      15                 :            :  * divide by noticing that floor((k-1) / 2) = ((k - 1) >> 1).
      16                 :            :  */
      17                 :            : 
      18                 :            : #define parent(k) (((k) - 1) >> 1)
      19                 :            : /*
      20                 :            :  * Normally left is defined left(k) = (2 * k + 1) but we can avoid a
      21                 :            :  * multiply by noticing that (2 * k + 1) = ((k << 1) + 1).
      22                 :            :  */
      23                 :            : 
      24                 :            : #define left(k) (((k) << 1) + 1)
      25                 :            : 
      26                 :            : /*
      27                 :            :  * Normally right is defined right(k) = (2 * k + 2) but we can avoid a
      28                 :            :  * multiply by noticing that right(k) = left(k) + 1
      29                 :            :  */
      30                 :            : #define right(k) (left(k) + 1)
      31                 :            : 
      32                 :            : #define A(k) ((uint8_t *)base + size * (k))
      33                 :            : 
      34                 :            : struct qsort_comp {
      35                 :            :         bool has3;
      36                 :            :         void *arg;
      37                 :            :         union {
      38                 :            :                 int (*comp2)(const void *a, const void *b);
      39                 :            :                 int (*comp3)(const void *a, const void *b, void *arg);
      40                 :            :         };
      41                 :            : };
      42                 :            : 
      43                 :          0 : static inline int compare(struct qsort_comp *cmp, void *a, void *b)
      44                 :            : {
      45         [ #  # ]:          0 :         if (cmp->has3) {
      46                 :          0 :                 return cmp->comp3(a, b, cmp->arg);
      47                 :            :         }
      48                 :            : 
      49                 :          0 :         return cmp->comp2(a, b);
      50                 :            : }
      51                 :            : 
      52                 :          0 : static void sift_down(void *base, int start, int end, size_t size, struct qsort_comp *cmp)
      53                 :            : {
      54                 :            :         int root;
      55                 :            :         int child;
      56                 :            :         int swap;
      57                 :            : 
      58         [ #  # ]:          0 :         for (swap = start, root = swap; left(root) < end; root = swap) {
      59                 :          0 :                 child = left(root);
      60                 :            : 
      61                 :            :                 /* if root < left */
      62         [ #  # ]:          0 :                 if (compare(cmp, A(swap), A(child)) < 0) {
      63                 :          0 :                         swap = child;
      64                 :            :                 }
      65                 :            : 
      66                 :            :                 /* right exists and min(A(root),A(left)) < A(right) */
      67   [ #  #  #  # ]:          0 :                 if (right(root) < end && compare(cmp, A(swap), A(right(root))) < 0) {
      68                 :          0 :                         swap = right(root);
      69                 :            :                 }
      70                 :            : 
      71         [ #  # ]:          0 :                 if (swap == root) {
      72                 :          0 :                         return;
      73                 :            :                 }
      74                 :            : 
      75                 :          0 :                 byteswp(A(root), A(swap), size);
      76                 :            :         }
      77                 :            : }
      78                 :            : 
      79                 :          0 : static void heapify(void *base, int nmemb, size_t size, struct qsort_comp *cmp)
      80                 :            : {
      81                 :            :         int start;
      82                 :            : 
      83         [ #  # ]:          0 :         for (start = parent(nmemb - 1); start >= 0; --start) {
      84                 :          0 :                 sift_down(base, start, nmemb, size, cmp);
      85                 :            :         }
      86                 :          0 : }
      87                 :            : 
      88                 :          0 : static void heap_sort(void *base, int nmemb, size_t size, struct qsort_comp *cmp)
      89                 :            : {
      90                 :            :         int end;
      91                 :            : 
      92                 :          0 :         heapify(base, nmemb, size, cmp);
      93                 :            : 
      94         [ #  # ]:          0 :         for (end = nmemb - 1; end > 0; --end) {
      95                 :          0 :                 byteswp(A(end), A(0), size);
      96                 :          0 :                 sift_down(base, 0, end, size, cmp);
      97                 :            :         }
      98                 :          0 : }
      99                 :            : 
     100                 :            : void qsort_r(void *base, size_t nmemb, size_t size,
     101                 :            :              int (*comp3)(const void *a, const void *b, void *arg), void *arg)
     102                 :            : {
     103                 :          0 :         struct qsort_comp cmp = {
     104                 :            :                 .has3 = true,
     105                 :            :                 .arg = arg,
     106                 :            :                 {
     107                 :            :                         .comp3 = comp3
     108                 :            :                 }
     109                 :            :         };
     110                 :            : 
     111                 :          0 :         heap_sort(base, nmemb, size, &cmp);
     112                 :          0 : }
     113                 :            : 
     114                 :            : void qsort(void *base, size_t nmemb, size_t size,
     115                 :            :            int (*comp2)(const void *a, const void *b))
     116                 :            : {
     117                 :          0 :         struct qsort_comp cmp = {
     118                 :            :                 .has3 = false,
     119                 :            :                 .arg = NULL,
     120                 :            :                 {
     121                 :            :                         .comp2 = comp2
     122                 :            :                 }
     123                 :            :         };
     124                 :            : 
     125                 :          0 :         heap_sort(base, nmemb, size, &cmp);
     126                 :          0 : }

Generated by: LCOV version 1.14