OpenCoverage

heap.c

Absolute File Name:/home/opencoverage/opencoverage/guest-scripts/coreutils/src/gl/lib/heap.c
Switch to Source codePreprocessed file
LineSourceCount
1-
2-
3static int heap_default_compare (void const *, void const *);-
4static size_t heapify_down (void **, size_t, size_t,-
5 int (*) (void const *, void const *));-
6static void heapify_up (void **, size_t,-
7 int (*) (void const *, void const *));-
8-
9struct heap-
10{-
11 void **array;-
12 size_t capacity;-
13 size_t count;-
14 int (*compare) (void const *, void const *);-
15};-
16-
17-
18-
19struct heap *-
20heap_alloc (int (*compare) (void const *, void const *), size_t n_reserve)-
21{-
22 struct heap *heap = xmalloc (sizeof *heap);-
23-
24 if (n_reserve == 0
n_reserve == 0Description
TRUEnever evaluated
FALSEevaluated 2402 times by 1 test
Evaluated by:
  • sort
)		0-2402
25 n_reserve = 1;
never executed: n_reserve = 1;
0
26-
27 heap->array = xnmalloc (n_reserve, sizeof *(heap->array));-
28-
29 heap->array[0] = -
30 ((void *)0)-
31 ;-
32 heap->capacity = n_reserve;-
33 heap->count = 0;-
34 heap->compare = compare
compareDescription
TRUEevaluated 2402 times by 1 test
Evaluated by:
  • sort
FALSEnever evaluated
 ? compare : heap_default_compare;		0-2402
35-
36 return
executed 2402 times by 1 test: return heap;
Executed by:
  • sort
 heap;
executed 2402 times by 1 test: return heap;
Executed by:
  • sort
2402
37}-
38-
39-
40static int-
41heap_default_compare (void const *a, void const *b)-
42{-
43 return
never executed: return 0;
 0;
never executed: return 0;
0
44}-
45-
46-
47void-
48heap_free (struct heap *heap)-
49{-
50 free (heap->array);-
51 free (heap);-
52}
never executed: end of block
0
53-
54-
55-
56int-
57heap_insert (struct heap *heap, void *item)-
58{-
59 if (heap->capacity - 1 <= heap->count
heap->capacity...<= heap->countDescription
TRUEnever evaluated
FALSEevaluated 25192 times by 1 test
Evaluated by:
  • sort
)		0-25192
60 heap->array = x2nrealloc (heap->array, &heap->capacity,
never executed: heap->array = x2nrealloc (heap->array, &heap->capacity, sizeof *(heap->array));
0
61 sizeof *(heap->array));
never executed: heap->array = x2nrealloc (heap->array, &heap->capacity, sizeof *(heap->array));
0
62-
63 heap->array[++heap->count] = item;-
64 heapify_up (heap->array, heap->count, heap->compare);-
65-
66 return
executed 25192 times by 1 test: return 0;
Executed by:
  • sort
 0;
executed 25192 times by 1 test: return 0;
Executed by:
  • sort
25192
67}-
68-
69-
70-
71void *-
72heap_remove_top (struct heap *heap)-
73{-
74 void *top;-
75-
76 if (heap->count == 0
heap->count == 0Description
TRUEnever evaluated
FALSEevaluated 22790 times by 1 test
Evaluated by:
  • sort
)		0-22790
77 return
never executed: return ((void *)0) ;
never executed: return ((void *)0) ;
0
78 ((void *)0)
never executed: return ((void *)0) ;
0
79 ;
never executed: return ((void *)0) ;
0
80-
81 top = heap->array[1];-
82 heap->array[1] = heap->array[heap->count--];-
83 heapify_down (heap->array, heap->count, 1, heap->compare);-
84-
85 return
executed 22790 times by 1 test: return top;
Executed by:
  • sort
 top;
executed 22790 times by 1 test: return top;
Executed by:
  • sort
22790
86}-
87-
88-
89-
90static size_t-
91heapify_down (void **array, size_t count, size_t initial,-
92 int (*compare) (void const *, void const *))-
93{-
94 void *element = array[initial];-
95-
96 size_t parent = initial;-
97 while (parent <= count / 2
parent <= count / 2Description
TRUEnever evaluated
FALSEevaluated 22790 times by 1 test
Evaluated by:
  • sort
)		0-22790
98 {-
99 size_t child = 2 * parent;-
100-
101 if (child < count
child < countDescription
TRUEnever evaluated
FALSEnever evaluated
 && compare (array[child], array[child+1]) < 0
compare (array...[child+1]) < 0Description
TRUEnever evaluated
FALSEnever evaluated
)		0
102 child++;
never executed: child++;
0
103-
104 if (compare (array[child], element) <= 0
compare (array... element) <= 0Description
TRUEnever evaluated
FALSEnever evaluated
)		0
105 break;
never executed: break;
0
106-
107 array[parent] = array[child];-
108 parent = child;-
109 }
never executed: end of block
0
110-
111 array[parent] = element;-
112 return
executed 22790 times by 1 test: return parent;
Executed by:
  • sort
 parent;
executed 22790 times by 1 test: return parent;
Executed by:
  • sort
22790
113}-
114-
115-
116-
117static void-
118heapify_up (void **array, size_t count,-
119 int (*compare) (void const *, void const *))-
120{-
121 size_t k = count;-
122 void *new_element = array[k];-
123-
124 while (k != 1
k != 1Description
TRUEnever evaluated
FALSEevaluated 25192 times by 1 test
Evaluated by:
  • sort
 && compare (array[k/2], new_element) <= 0
compare (array..._element) <= 0Description
TRUEnever evaluated
FALSEnever evaluated
)		0-25192
125 {-
126 array[k] = array[k/2];-
127 k /= 2;-
128 }
never executed: end of block
0
129-
130 array[k] = new_element;-
131}
executed 25192 times by 1 test: end of block
Executed by:
  • sort
25192
Switch to Source codePreprocessed file
Generated by Squish Coco 4.1.2