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 100 int sort_indices_int_inc(int **optr, int *ranks, const int num)
87 {
88 100 int *order;
89 100 int i;
90
91 /* Allocate list of sequential indices. */
92 100 order = (int *)g_malloc(num * sizeof(int));
93 /* Initialize list of sequential indices. */
94
2/2
✓ Branch 5 → 4 taken 38952 times.
✓ Branch 5 → 6 taken 100 times.
 39152 for(i = 0; i < num; i++)
95 38952 order[i] = i;
96
97 /* Sort the indecies into rank order. */
98 100 bubble_sort_int_inc_2(ranks, order, num);
99
100 /* Set output pointer to the resulting order of sorted indices. */
101 100 *optr = order;
102 /* Return normally. */
103 100 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 100 void bubble_sort_int_inc_2(int *ranks, int *items, const int len)
140 {
141 100 int done = 0;
142 100 int i, p, n, trank, titem;
143
144 /* Set counter to the length of the list being sorted. */
145 100 n = len;
146
147 /* While swaps in order continue to occur from the */
148 /* previous iteration... */
149
2/2
✓ Branch 8 → 9 taken 36128 times.
✓ Branch 8 → 10 taken 100 times.
 36228 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 14646396 times.
✓ Branch 6 → 7 taken 36128 times.
 14682524 for (i=1, p = 0; i<n; i++, p++){
155 /* If previous rank is < current rank ... */
156
2/2
✓ Branch 3 → 4 taken 5406421 times.
✓ Branch 3 → 5 taken 9239975 times.
 14646396 if(ranks[p] > ranks[i]){
157 /* Swap ranks. */
158 5406421 trank = ranks[i];
159 5406421 ranks[i] = ranks[p];
160 5406421 ranks[p] = trank;
161 /* Swap items. */
162 5406421 titem = items[i];
163 5406421 items[i] = items[p];
164 5406421 items[p] = titem;
165 /* Changes were made, so set done flag to FALSE. */
166 5406421 done = FALSE;
167 }
168 /* Otherwise, rank pair is in order, so continue. */
169 }
170 /* Decrement the ending index. */
171 36128 n--;
172 }
173 100 }
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 3659 void bubble_sort_double_inc_2(double *ranks, int *items, const int len)
191 {
192 3659 int done = 0;
193 3659 int i, p, n, titem;
194 3659 double trank;
195
196 /* Set counter to the length of the list being sorted. */
197 3659 n = len;
198
199 /* While swaps in order continue to occur from the */
200 /* previous iteration... */
201
2/2
✓ Branch 8 → 9 taken 12818 times.
✓ Branch 8 → 10 taken 3659 times.
 16477 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 32467 times.
✓ Branch 6 → 7 taken 12818 times.
 45285 for (i=1, p = 0; i<n; i++, p++){
207 /* If previous rank is < current rank ... */
208
2/2
✓ Branch 3 → 4 taken 17472 times.
✓ Branch 3 → 5 taken 14995 times.
 32467 if(ranks[p] > ranks[i]){
209 /* Swap ranks. */
210 17472 trank = ranks[i];
211 17472 ranks[i] = ranks[p];
212 17472 ranks[p] = trank;
213 /* Swap items. */
214 17472 titem = items[i];
215 17472 items[i] = items[p];
216 17472 items[p] = titem;
217 /* Changes were made, so set done flag to FALSE. */
218 17472 done = FALSE;
219 }
220 /* Otherwise, rank pair is in order, so continue. */
221 }
222 /* Decrement the ending index. */
223 12818 n--;
224 }
225 3659 }
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 48548 void bubble_sort_double_dec_2(double *ranks, int *items, const int len)
244 {
245 48548 int done = 0;
246 48548 int i, p, n, titem;
247 48548 double trank;
248
249 48548 n = len;
250
2/2
✓ Branch 8 → 9 taken 104937 times.
✓ Branch 8 → 10 taken 48548 times.
 153485 while(!done){
251 done = 1;
252
2/2
✓ Branch 6 → 3 taken 132938 times.
✓ Branch 6 → 7 taken 104937 times.
 237875 for (i=1, p = 0;i<n;i++, p++){
253 /* If previous rank is < current rank ... */
254
2/2
✓ Branch 3 → 4 taken 69908 times.
✓ Branch 3 → 5 taken 63030 times.
 132938 if(ranks[p] < ranks[i]){
255 /* Swap ranks */
256 69908 trank = ranks[i];
257 69908 ranks[i] = ranks[p];
258 69908 ranks[p] = trank;
259 /* Swap corresponding items */
260 69908 titem = items[i];
261 69908 items[i] = items[p];
262 69908 items[p] = titem;
263 69908 done = 0;
264 }
265 }
266 104937 n--;
267 }
268 48548 }
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 14716 void bubble_sort_int_inc(int *ranks, const int len)
282 {
283 14716 int done = 0;
284 14716 int i, p, n;
285 14716 int trank;
286
287 /* Set counter to the length of the list being sorted. */
288 14716 n = len;
289
290 /* While swaps in order continue to occur from the */
291 /* previous iteration... */
292
2/2
✓ Branch 8 → 9 taken 34736 times.
✓ Branch 8 → 10 taken 14716 times.
 49452 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 64990 times.
✓ Branch 6 → 7 taken 34736 times.
 99726 for (i=1, p = 0; i<n; i++, p++){
298 /* If previous rank is < current rank ... */
299
2/2
✓ Branch 3 → 4 taken 45625 times.
✓ Branch 3 → 5 taken 19365 times.
 64990 if(ranks[p] > ranks[i]){
300 /* Swap ranks. */
301 45625 trank = ranks[i];
302 45625 ranks[i] = ranks[p];
303 45625 ranks[p] = trank;
304 /* Changes were made, so set done flag to FALSE. */
305 45625 done = FALSE;
306 }
307 /* Otherwise, rank pair is in order, so continue. */
308 }
309 /* Decrement the ending index. */
310 34736 n--;
311 }
312 14716 }
313
314