OpenCoverage

heap.c

Absolute File Name:/home/opencoverage/opencoverage/guest-scripts/coreutils/src/gl/lib/heap.c
Source codeSwitch to Preprocessed file
LineSourceCount
1/* Barebones heap implementation supporting only insert and pop.-
2-
3 Copyright (C) 2010-2018 Free Software Foundation, Inc.-
4-
5 This program is free software: you can redistribute it and/or modify-
6 it under the terms of the GNU General Public License as published by-
7 the Free Software Foundation; either version 3 of the License, or-
8 (at your option) any later version.-
9-
10 This program is distributed in the hope that it will be useful,-
11 but WITHOUT ANY WARRANTY; without even the implied warranty of-
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the-
13 GNU General Public License for more details.-
14-
15 You should have received a copy of the GNU General Public License-
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */-
17-
18/* Full implementation: GDSL (http://gna.org/projects/gdsl/) by Nicolas-
19 Darnis <ndarnis@free.fr>. */-
20-
21#include <config.h>-
22-
23#include "heap.h"-
24#include "stdlib--.h"-
25#include "xalloc.h"-
26-
27static int heap_default_compare (void const *, void const *);-
28static size_t heapify_down (void **, size_t, size_t,-
29 int (*) (void const *, void const *));-
30static void heapify_up (void **, size_t,-
31 int (*) (void const *, void const *));-
32-
33struct heap-
34{-
35 void **array; /* array[0] is not used */-
36 size_t capacity; /* Array size */-
37 size_t count; /* Used as index to last element. Also is num of items. */-
38 int (*compare) (void const *, void const *);-
39};-
40-
41/* Allocate memory for the heap. */-
42-
43struct heap *-
44heap_alloc (int (*compare) (void const *, void const *), size_t n_reserve)-
45{-
46 struct heap *heap = xmalloc (sizeof *heap);-
47-
48 if (n_reserve == 0)
n_reserve == 0Description
TRUEnever evaluated
FALSEevaluated 2402 times by 1 test
Evaluated by:
  • sort
0-2402
49 n_reserve = 1;
never executed: n_reserve = 1;
0
50-
51 heap->array = xnmalloc (n_reserve, sizeof *(heap->array));-
52-
53 heap->array[0] = NULL;-
54 heap->capacity = n_reserve;-
55 heap->count = 0;-
56 heap->compare = compare ? compare : heap_default_compare;
compareDescription
TRUEevaluated 2402 times by 1 test
Evaluated by:
  • sort
FALSEnever evaluated
0-2402
57-
58 return heap;
executed 2402 times by 1 test: return heap;
Executed by:
  • sort
2402
59}-
60-
61-
62static int-
63heap_default_compare (void const *a, void const *b)-
64{-
65 return 0;
never executed: return 0;
0
66}-
67-
68-
69void-
70heap_free (struct heap *heap)-
71{-
72 free (heap->array);-
73 free (heap);-
74}
never executed: end of block
0
75-
76/* Insert element into heap. */-
77-
78int-
79heap_insert (struct heap *heap, void *item)-
80{-
81 if (heap->capacity - 1 <= heap->count)
heap->capacity...<= heap->countDescription
TRUEnever evaluated
FALSEevaluated 25192 times by 1 test
Evaluated by:
  • sort
0-25192
82 heap->array = x2nrealloc (heap->array, &heap->capacity,
never executed: heap->array = x2nrealloc (heap->array, &heap->capacity, sizeof *(heap->array));
0
83 sizeof *(heap->array));
never executed: heap->array = x2nrealloc (heap->array, &heap->capacity, sizeof *(heap->array));
0
84-
85 heap->array[++heap->count] = item;-
86 heapify_up (heap->array, heap->count, heap->compare);-
87-
88 return 0;
executed 25192 times by 1 test: return 0;
Executed by:
  • sort
25192
89}-
90-
91/* Pop top element off heap. */-
92-
93void *-
94heap_remove_top (struct heap *heap)-
95{-
96 void *top;-
97-
98 if (heap->count == 0)
heap->count == 0Description
TRUEnever evaluated
FALSEevaluated 22790 times by 1 test
Evaluated by:
  • sort
0-22790
99 return NULL;
never executed: return ((void *)0) ;
0
100-
101 top = heap->array[1];-
102 heap->array[1] = heap->array[heap->count--];-
103 heapify_down (heap->array, heap->count, 1, heap->compare);-
104-
105 return top;
executed 22790 times by 1 test: return top;
Executed by:
  • sort
22790
106}-
107-
108/* Move element down into appropriate position in heap. */-
109-
110static size_t-
111heapify_down (void **array, size_t count, size_t initial,-
112 int (*compare) (void const *, void const *))-
113{-
114 void *element = array[initial];-
115-
116 size_t parent = initial;-
117 while (parent <= count / 2)
parent <= count / 2Description
TRUEnever evaluated
FALSEevaluated 22790 times by 1 test
Evaluated by:
  • sort
0-22790
118 {-
119 size_t child = 2 * parent;-
120-
121 if (child < count && compare (array[child], array[child+1]) < 0)
child < countDescription
TRUEnever evaluated
FALSEnever evaluated
compare (array...[child+1]) < 0Description
TRUEnever evaluated
FALSEnever evaluated
0
122 child++;
never executed: child++;
0
123-
124 if (compare (array[child], element) <= 0)
compare (array... element) <= 0Description
TRUEnever evaluated
FALSEnever evaluated
0
125 break;
never executed: break;
0
126-
127 array[parent] = array[child];-
128 parent = child;-
129 }
never executed: end of block
0
130-
131 array[parent] = element;-
132 return parent;
executed 22790 times by 1 test: return parent;
Executed by:
  • sort
22790
133}-
134-
135/* Move element up into appropriate position in heap. */-
136-
137static void-
138heapify_up (void **array, size_t count,-
139 int (*compare) (void const *, void const *))-
140{-
141 size_t k = count;-
142 void *new_element = array[k];-
143-
144 while (k != 1 && compare (array[k/2], new_element) <= 0)
k != 1Description
TRUEnever evaluated
FALSEevaluated 25192 times by 1 test
Evaluated by:
  • sort
compare (array..._element) <= 0Description
TRUEnever evaluated
FALSEnever evaluated
0-25192
145 {-
146 array[k] = array[k/2];-
147 k /= 2;-
148 }
never executed: end of block
0
149-
150 array[k] = new_element;-
151}
executed 25192 times by 1 test: end of block
Executed by:
  • sort
25192
Source codeSwitch to Preprocessed file
Generated by Squish Coco 4.1.2