GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 73 / 0 / 73
Functions: 100.0% 5 / 0 / 5
Branches: 100.0% 26 / 0 / 26
libfprint/nbis/mindtct/sort.c
Line Branch Exec Source
1 /*******************************************************************************
2
3 License:
4 This software and/or related materials was developed at the National Institute
5 of Standards and Technology (NIST) by employees of the Federal Government
6 in the course of their official duties. Pursuant to title 17 Section 105
7 of the United States Code, this software is not subject to copyright
8 protection and is in the public domain.
9
10 This software and/or related materials have been determined to be not subject
11 to the EAR (see Part 734.3 of the EAR for exact details) because it is
12 a publicly available technology and software, and is freely distributed
13 to any interested party with no licensing requirements. Therefore, it is
14 permissible to distribute this software as a free download from the internet.
15
16 Disclaimer:
17 This software and/or related materials was developed to promote biometric
18 standards and biometric technology testing for the Federal Government
19 in accordance with the USA PATRIOT Act and the Enhanced Border Security
20 and Visa Entry Reform Act. Specific hardware and software products identified
21 in this software were used in order to perform the software development.
22 In no case does such identification imply recommendation or endorsement
23 by the National Institute of Standards and Technology, nor does it imply that
24 the products and equipment identified are necessarily the best available
25 for the purpose.
26
27 This software and/or related materials are provided "AS-IS" without warranty
28 of any kind including NO WARRANTY OF PERFORMANCE, MERCHANTABILITY,
29 NO WARRANTY OF NON-INFRINGEMENT OF ANY 3RD PARTY INTELLECTUAL PROPERTY
30 or FITNESS FOR A PARTICULAR PURPOSE or for any purpose whatsoever, for the
31 licensed product, however used. In no event shall NIST be liable for any
32 damages and/or costs, including but not limited to incidental or consequential
33 damages of any kind, including economic damage or injury to property and lost
34 profits, regardless of whether NIST shall be advised, have reason to know,
35 or in fact shall know of the possibility.
36
37 By using this software, you agree to bear all risk relating to quality,
38 use and performance of the software and/or related materials. You agree
39 to hold the Government harmless from any claim arising from your use
40 of the software.
41
42 *******************************************************************************/
43
44
45 /***********************************************************************
46 LIBRARY: LFS - NIST Latent Fingerprint System
47
48 FILE: SORT.C
49 AUTHOR: Michael D. Garris
50 DATE: 03/16/1999
51 UPDATED: 03/16/2005 by MDG
52
53 Contains sorting routines required by the NIST Latent Fingerprint
54 System (LFS).
55
56 ***********************************************************************
57 ROUTINES:
58 sort_indices_int_inc()
59 sort_indices_double_inc()
60 bubble_sort_int_inc_2()
61 bubble_sort_double_inc_2()
62 bubble_sort_double_dec_2()
63 bubble_sort_int_inc()
64 ***********************************************************************/
65
66 #include <stdio.h>
67 #include <lfs.h>
68
69 /*************************************************************************
70 **************************************************************************
71 #cat: sort_indices_int_inc - Takes a list of integers and returns a list of
72 #cat: indices referencing the integer list in increasing order.
73 #cat: The original list of integers is also returned in sorted
74 #cat: order.
75
76 Input:
77 ranks - list of integers to be sorted
78 num - number of integers in the list
79 Output:
80 optr - list of indices referencing the integer list in sorted order
81 ranks - list of integers in increasing order
82 Return Code:
83 Zero - successful completion
84 Negative - system error
85 **************************************************************************/
86 98 int sort_indices_int_inc(int **optr, int *ranks, const int num)
87 {
88 98 int *order;
89 98 int i;
90
91 /* Allocate list of sequential indices. */
92 98 order = (int *)g_malloc(num * sizeof(int));
93 /* Initialize list of sequential indices. */
94
2/2
✓ Branch 5 → 4 taken 37053 times.
✓ Branch 5 → 6 taken 98 times.
 37249 for(i = 0; i < num; i++)
95 37053 order[i] = i;
96
97 /* Sort the indecies into rank order. */
98 98 bubble_sort_int_inc_2(ranks, order, num);
99
100 /* Set output pointer to the resulting order of sorted indices. */
101 98 *optr = order;
102 /* Return normally. */
103 98 return(0);
104 }
105
106 /*************************************************************************
107 **************************************************************************
108 #cat: sort_indices_double_inc - Takes a list of doubles and returns a list of
109 #cat: indices referencing the double list in increasing order.
110 #cat: The original list of doubles is also returned in sorted
111 #cat: order.
112
113 Input:
114 ranks - list of doubles to be sorted
115 num - number of doubles in the list
116 Output:
117 optr - list of indices referencing the double list in sorted order
118 ranks - list of doubles in increasing order
119 Return Code:
120 Zero - successful completion
121 Negative - system error
122 **************************************************************************/
123
124 /*************************************************************************
125 **************************************************************************
126 #cat: bubble_sort_int_inc_2 - Takes a list of integer ranks and a corresponding
127 #cat: list of integer attributes, and sorts the ranks
128 #cat: into increasing order moving the attributes
129 #cat: correspondingly.
130
131 Input:
132 ranks - list of integers to be sort on
133 items - list of corresponding integer attributes
134 len - number of items in list
135 Output:
136 ranks - list of integers sorted in increasing order
137 items - list of attributes in corresponding sorted order
138 **************************************************************************/
139 98 void bubble_sort_int_inc_2(int *ranks, int *items, const int len)
140 {
141 98 int done = 0;
142 98 int i, p, n, trank, titem;
143
144 /* Set counter to the length of the list being sorted. */
145 98 n = len;
146
147 /* While swaps in order continue to occur from the */
148 /* previous iteration... */
149
2/2
✓ Branch 8 → 9 taken 34280 times.
✓ Branch 8 → 10 taken 98 times.
 34378 while(!done){
150 /* Reset the done flag to TRUE. */
151 done = TRUE;
152 /* Foreach rank in list up to current end index... */
153 /* ("p" points to current rank and "i" points to the next rank.) */
154
2/2
✓ Branch 6 → 3 taken 13057242 times.
✓ Branch 6 → 7 taken 34280 times.
 13091522 for (i=1, p = 0; i<n; i++, p++){
155 /* If previous rank is < current rank ... */
156
2/2
✓ Branch 3 → 4 taken 4714333 times.
✓ Branch 3 → 5 taken 8342909 times.
 13057242 if(ranks[p] > ranks[i]){
157 /* Swap ranks. */
158 4714333 trank = ranks[i];
159 4714333 ranks[i] = ranks[p];
160 4714333 ranks[p] = trank;
161 /* Swap items. */
162 4714333 titem = items[i];
163 4714333 items[i] = items[p];
164 4714333 items[p] = titem;
165 /* Changes were made, so set done flag to FALSE. */
166 4714333 done = FALSE;
167 }
168 /* Otherwise, rank pair is in order, so continue. */
169 }
170 /* Decrement the ending index. */
171 34280 n--;
172 }
173 98 }
174
175 /*************************************************************************
176 **************************************************************************
177 #cat: bubble_sort_double_inc_2 - Takes a list of double ranks and a
178 #cat: corresponding list of integer attributes, and sorts the
179 #cat: ranks into increasing order moving the attributes
180 #cat: correspondingly.
181
182 Input:
183 ranks - list of double to be sort on
184 items - list of corresponding integer attributes
185 len - number of items in list
186 Output:
187 ranks - list of doubles sorted in increasing order
188 items - list of attributes in corresponding sorted order
189 **************************************************************************/
190 3541 void bubble_sort_double_inc_2(double *ranks, int *items, const int len)
191 {
192 3541 int done = 0;
193 3541 int i, p, n, titem;
194 3541 double trank;
195
196 /* Set counter to the length of the list being sorted. */
197 3541 n = len;
198
199 /* While swaps in order continue to occur from the */
200 /* previous iteration... */
201
2/2
✓ Branch 8 → 9 taken 12382 times.
✓ Branch 8 → 10 taken 3541 times.
 15923 while(!done){
202 /* Reset the done flag to TRUE. */
203 done = TRUE;
204 /* Foreach rank in list up to current end index... */
205 /* ("p" points to current rank and "i" points to the next rank.) */
206
2/2
✓ Branch 6 → 3 taken 31401 times.
✓ Branch 6 → 7 taken 12382 times.
 43783 for (i=1, p = 0; i<n; i++, p++){
207 /* If previous rank is < current rank ... */
208
2/2
✓ Branch 3 → 4 taken 16880 times.
✓ Branch 3 → 5 taken 14521 times.
 31401 if(ranks[p] > ranks[i]){
209 /* Swap ranks. */
210 16880 trank = ranks[i];
211 16880 ranks[i] = ranks[p];
212 16880 ranks[p] = trank;
213 /* Swap items. */
214 16880 titem = items[i];
215 16880 items[i] = items[p];
216 16880 items[p] = titem;
217 /* Changes were made, so set done flag to FALSE. */
218 16880 done = FALSE;
219 }
220 /* Otherwise, rank pair is in order, so continue. */
221 }
222 /* Decrement the ending index. */
223 12382 n--;
224 }
225 3541 }
226
227 /***************************************************************************
228 **************************************************************************
229 #cat: bubble_sort_double_dec_2 - Conducts a simple bubble sort returning a list
230 #cat: of ranks in decreasing order and their associated items in sorted
231 #cat: order as well.
232
233 Input:
234 ranks - list of values to be sorted
235 items - list of items, each corresponding to a particular rank value
236 len - length of the lists to be sorted
237 Output:
238 ranks - list of values sorted in descending order
239 items - list of items in the corresponding sorted order of the ranks.
240 If these items are indices, upon return, they may be used as
241 indirect addresses reflecting the sorted order of the ranks.
242 ****************************************************************************/
243 46761 void bubble_sort_double_dec_2(double *ranks, int *items, const int len)
244 {
245 46761 int done = 0;
246 46761 int i, p, n, titem;
247 46761 double trank;
248
249 46761 n = len;
250
2/2
✓ Branch 8 → 9 taken 102087 times.
✓ Branch 8 → 10 taken 46761 times.
 148848 while(!done){
251 done = 1;
252
2/2
✓ Branch 6 → 3 taken 128431 times.
✓ Branch 6 → 7 taken 102087 times.
 230518 for (i=1, p = 0;i<n;i++, p++){
253 /* If previous rank is < current rank ... */
254
2/2
✓ Branch 3 → 4 taken 68701 times.
✓ Branch 3 → 5 taken 59730 times.
 128431 if(ranks[p] < ranks[i]){
255 /* Swap ranks */
256 68701 trank = ranks[i];
257 68701 ranks[i] = ranks[p];
258 68701 ranks[p] = trank;
259 /* Swap corresponding items */
260 68701 titem = items[i];
261 68701 items[i] = items[p];
262 68701 items[p] = titem;
263 68701 done = 0;
264 }
265 }
266 102087 n--;
267 }
268 46761 }
269
270 /*************************************************************************
271 **************************************************************************
272 #cat: bubble_sort_int_inc - Takes a list of integers and sorts them into
273 #cat: increasing order using a simple bubble sort.
274
275 Input:
276 ranks - list of integers to be sort on
277 len - number of items in list
278 Output:
279 ranks - list of integers sorted in increasing order
280 **************************************************************************/
281 13943 void bubble_sort_int_inc(int *ranks, const int len)
282 {
283 13943 int done = 0;
284 13943 int i, p, n;
285 13943 int trank;
286
287 /* Set counter to the length of the list being sorted. */
288 13943 n = len;
289
290 /* While swaps in order continue to occur from the */
291 /* previous iteration... */
292
2/2
✓ Branch 8 → 9 taken 32813 times.
✓ Branch 8 → 10 taken 13943 times.
 46756 while(!done){
293 /* Reset the done flag to TRUE. */
294 done = TRUE;
295 /* Foreach rank in list up to current end index... */
296 /* ("p" points to current rank and "i" points to the next rank.) */
297
2/2
✓ Branch 6 → 3 taken 60561 times.
✓ Branch 6 → 7 taken 32813 times.
 93374 for (i=1, p = 0; i<n; i++, p++){
298 /* If previous rank is < current rank ... */
299
2/2
✓ Branch 3 → 4 taken 42714 times.
✓ Branch 3 → 5 taken 17847 times.
 60561 if(ranks[p] > ranks[i]){
300 /* Swap ranks. */
301 42714 trank = ranks[i];
302 42714 ranks[i] = ranks[p];
303 42714 ranks[p] = trank;
304 /* Changes were made, so set done flag to FALSE. */
305 42714 done = FALSE;
306 }
307 /* Otherwise, rank pair is in order, so continue. */
308 }
309 /* Decrement the ending index. */
310 32813 n--;
311 }
312 13943 }
313
314