"Fossies" - the Fresh Open Source Software Archive 
Member "tin-2.6.2/src/heapsort.c" (9 Dec 2022, 6252 Bytes) of package /linux/misc/tin-2.6.2.tar.xz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "heapsort.c" see the
Fossies "Dox" file reference documentation and the last
Fossies "Diffs" side-by-side code changes report:
2.4.3_vs_2.4.4.
1 /*-
2 * Copyright (c) 1991, 1993
3 * The Regents of the University of California. All rights reserved.
4 *
5 * This code is derived from software contributed to Berkeley by
6 * Ronnie Kon at Mindcraft Inc., Kevin Lew and Elmer Yglesias.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 4. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 */
32
33 #if 0
34 # include <sys/cdefs.h>
35 # include <errno.h>
36 # include <stddef.h>
37 # include <stdlib.h>
38 #else
39 # ifndef TIN_H
40 # include "tin.h"
41 # endif /* !TIN_H */
42 #endif /* 0 */
43
44 #if defined(USE_HEAPSORT) && !defined(HAVE_HEAPSORT)
45 /*
46 * Swap two areas of size number of bytes. Although qsort(3) permits random
47 * blocks of memory to be sorted, sorting pointers is almost certainly the
48 * common case (and, were it not, could easily be made so). Regardless, it
49 * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer
50 * arithmetic gets lost in the time required for comparison function calls.
51 */
52 #define SWAP(a, b, count, size, tmp) { \
53 count = size; \
54 do { \
55 tmp = *a; \
56 *a++ = *b; \
57 *b++ = tmp; \
58 } while (--count); \
59 }
60
61 /* Copy one block of size size to another. */
62 #define COPY(a, b, count, size, tmp1, tmp2) { \
63 count = size; \
64 tmp1 = a; \
65 tmp2 = b; \
66 do { \
67 *tmp1++ = *tmp2++; \
68 } while (--count); \
69 }
70
71 /*
72 * Build the list into a heap, where a heap is defined such that for
73 * the records K1 ... KN, Kj/2 >= Kj for 1 <= j/2 <= j <= N.
74 *
75 * There two cases. If j == nmemb, select largest of Ki and Kj. If
76 * j < nmemb, select largest of Ki, Kj and Kj+1.
77 */
78 #define CREATE(initval, nmemb, par_i, child_i, par, child, size, count, tmp) { \
79 for (par_i = initval; (child_i = par_i * 2) <= nmemb; \
80 par_i = child_i) { \
81 child = abase + child_i * size; \
82 if (child_i < nmemb && compar(child, child + size) < 0) { \
83 child += size; \
84 ++child_i; \
85 } \
86 par = abase + par_i * size; \
87 if (compar(child, par) <= 0) \
88 break; \
89 SWAP(par, child, count, size, tmp); \
90 } \
91 }
92
93 /*
94 * Select the top of the heap and 'heapify'. Since by far the most expensive
95 * action is the call to the compar function, a considerable optimization
96 * in the average case can be achieved due to the fact that k, the displaced
97 * element, is usually quite small, so it would be preferable to first
98 * heapify, always maintaining the invariant that the larger child is copied
99 * over its parent's record.
100 *
101 * Then, starting from the *bottom* of the heap, finding k's correct place,
102 * again maintaining the invariant. As a result of the invariant no element
103 * is 'lost' when k is assigned its correct place in the heap.
104 *
105 * The time savings from this optimization are on the order of 15-20% for the
106 * average case. See Knuth, Vol. 3, page 158, problem 18.
107 *
108 * XXX Don't break the #define SELECT line, below. Reiser cpp gets upset.
109 */
110 #define SELECT(par_i, child_i, nmemb, par, child, size, k, count, tmp1, tmp2) { \
111 for (par_i = 1; (child_i = par_i * 2) <= nmemb; par_i = child_i) { \
112 child = abase + child_i * size; \
113 if (child_i < nmemb && compar(child, child + size) < 0) { \
114 child += size; \
115 ++child_i; \
116 } \
117 par = abase + par_i * size; \
118 COPY(par, child, count, size, tmp1, tmp2); \
119 } \
120 for (;;) { \
121 child_i = par_i; \
122 par_i = child_i / 2; \
123 child = abase + child_i * size; \
124 par = abase + par_i * size; \
125 if (child_i == 1 || compar(k, par) < 0) { \
126 COPY(child, k, count, size, tmp1, tmp2); \
127 break; \
128 } \
129 COPY(child, par, count, size, tmp1, tmp2); \
130 } \
131 }
132
133 /*
134 * Heapsort -- Knuth, Vol. 3, page 145. Runs in O (N lg N), both average
135 * and worst. While heapsort is faster than the worst case of quicksort,
136 * the BSD quicksort does median selection so that the chance of finding
137 * a data set that will trigger the worst case is nonexistent. Heapsort's
138 * only advantage over quicksort is that it requires little additional memory.
139 */
140 int
141 heapsort(
142 void *vbase,
143 size_t nmemb,
144 size_t size,
145 t_compfunc compar)
146 {
147 char tmp, *tmp1, *tmp2, *abase, *k, *p, *t;
148 size_t cnt, i, j, l;
149
150 if (nmemb <= 1)
151 return (0);
152
153 if (!size) {
154 errno = EINVAL;
155 return (-1);
156 }
157
158 #if !defined(TIN_H)
159 if ((k = malloc(size)) == NULL)
160 return (-1);
161 #else
162 k = my_malloc(size);
163 #endif /* !TIN_H */
164
165 /*
166 * Items are numbered from 1 to nmemb, so offset from size bytes
167 * below the starting address.
168 */
169 abase = (char *)vbase - size;
170
171 for (l = nmemb / 2 + 1; --l;)
172 CREATE(l, nmemb, i, j, t, p, size, cnt, tmp);
173
174 /*
175 * For each element of the heap, save the largest element into its
176 * final slot, save the displaced element (k), then recreate the
177 * heap.
178 */
179 while (nmemb > 1) {
180 COPY(k, abase + nmemb * size, cnt, size, tmp1, tmp2);
181 COPY(abase + nmemb * size, abase + size, cnt, size, tmp1, tmp2);
182 --nmemb;
183 SELECT(i, j, nmemb, t, p, size, k, cnt, tmp1, tmp2);
184 }
185 free(k);
186 return (0);
187 }
188 #endif /* USE_HEAPSORT && !HAVE_HEAPSORT */