ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/Array-Heap/Heap.xs
(Generate patch)

Comparing Array-Heap/Heap.xs (file contents):
Revision 1.2 by root, Fri Jul 24 21:29:07 2009 UTC vs.
Revision 1.3 by root, Sun Jul 26 04:50:02 2009 UTC

1#include "EXTERN.h" 1#include "EXTERN.h"
2#include "perl.h" 2#include "perl.h"
3#include "XSUB.h" 3#include "XSUB.h"
4 4
5/* pre-5.10 compatibility */
6#ifndef GV_NOTQUAL
7# define GV_NOTQUAL 1
8#endif
9#ifndef gv_fetchpvs
10# define gv_fetchpvs gv_fetchpv
11#endif
12
13#include "multicall.h"
14
15/* workaround for buggy multicall API */
16#ifndef cxinc
17# define cxinc() Perl_cxinc (aTHX)
18#endif
19
20#define dCMP \
21 dMULTICALL; \
22 void *cmp_data; \
23 I32 gimme = G_SCALAR;
24
25#define CMP_PUSH(sv) \
26 PUSH_MULTICALL (cmp_push_ (sv));\
27 cmp_data = multicall_cop;
28
29#define CMP_POP \
30 POP_MULTICALL;
31
32#define dCMP_CALL(data) \
33 OP *multicall_cop = (OP *)data;
34
35static void *
36cmp_push_ (SV *sv)
37{
38 HV *st;
39 GV *gvp;
40 CV *cv;
41
42 cv = sv_2cv (sv, &st, &gvp, 0);
43
44 if (!cv)
45 croak ("%s: callback must be a CODE reference or another callable object", SvPV_nolen (sv));
46
47 if (!PL_firstgv) PL_firstgv = gv_fetchpvs ("a", GV_ADD | GV_NOTQUAL, SVt_PV);
48 if (!PL_secondgv) PL_secondgv = gv_fetchpvs ("b", GV_ADD | GV_NOTQUAL, SVt_PV);
49
50 SAVESPTR (GvSV (PL_firstgv));
51 SAVESPTR (GvSV (PL_secondgv));
52
53 return cv;
54}
55
56/*****************************************************************************/
57
58static SV *
59sv_first (SV *sv)
60{
61 if (SvROK (sv) && SvTYPE (SvRV (sv)) == SVt_PVAV)
62 {
63 AV *av = (AV *)SvRV (sv);
64
65 sv = AvFILLp (av) < 0 ? &PL_sv_undef : AvARRAY (av)[0];
66 }
67
68 return sv;
69}
70
5static int 71static int
6cmp_nv (SV *a, SV *b, SV *data) 72cmp_nv (SV *a, SV *b, void *cmp_data)
7{ 73{
8 if (SvROK (a) && SvTYPE (SvRV (a)) == SVt_PVAV) a = *av_fetch ((AV *)SvRV (a), 0, 1); 74 a = sv_first (a);
9 if (SvROK (b) && SvTYPE (SvRV (b)) == SVt_PVAV) b = *av_fetch ((AV *)SvRV (b), 0, 1); 75 b = sv_first (b);
10 76
11 return SvNV (a) > SvNV (b); 77 return SvNV (a) > SvNV (b);
12} 78}
13 79
14static int 80static int
15cmp_sv (SV *a, SV *b, SV *data) 81cmp_sv (SV *a, SV *b, void *cmp_data)
16{ 82{
17 if (SvROK (a) && SvTYPE (SvRV (a)) == SVt_PVAV) a = *av_fetch ((AV *)SvRV (a), 0, 1); 83 a = sv_first (a);
18 if (SvROK (b) && SvTYPE (SvRV (b)) == SVt_PVAV) b = *av_fetch ((AV *)SvRV (b), 0, 1); 84 b = sv_first (b);
19 85
20 return sv_cmp(a, b) > 0; 86 return sv_cmp (a, b) > 0;
21} 87}
22 88
23static int 89static int
24cmp_custom (SV *a, SV *b, SV *data) 90cmp_custom (SV *a, SV *b, void *cmp_data)
25{ 91{
26 SV *old_a, *old_b; 92 dCMP_CALL (cmp_data);
27 int ret;
28 dSP;
29
30 if (!PL_firstgv) PL_firstgv = gv_fetchpv ("a", 1, SVt_PV);
31 if (!PL_secondgv) PL_secondgv = gv_fetchpv ("b", 1, SVt_PV);
32
33 old_a = GvSV (PL_firstgv);
34 old_b = GvSV (PL_secondgv);
35 93
36 GvSV (PL_firstgv) = a; 94 GvSV (PL_firstgv) = a;
37 GvSV (PL_secondgv) = b; 95 GvSV (PL_secondgv) = b;
38 96
39 PUSHMARK (SP); 97 MULTICALL;
40 PUTBACK;
41 ret = call_sv (data, G_SCALAR | G_NOARGS | G_EVAL);
42 SPAGAIN;
43
44 GvSV (PL_firstgv) = old_a;
45 GvSV (PL_secondgv) = old_b;
46 98
47 if (SvTRUE (ERRSV)) 99 if (SvTRUE (ERRSV))
48 croak (NULL); 100 croak (NULL);
49 101
50 if (ret != 1) 102 {
51 croak ("sort function must return exactly one return value"); 103 dSP;
52
53 return POPi >= 0; 104 return TOPi > 0;
105 }
54} 106}
55 107
108/*****************************************************************************/
109
56typedef int (*f_cmp)(SV *, SV *, SV *); 110typedef int (*f_cmp)(SV *a, SV *b, void *cmp_data);
57 111
58static AV * 112static AV *
59array (SV *ref) 113array (SV *ref)
60{ 114{
115 if (SvROK (ref)
61 if (SvROK (ref) && SvTYPE (SvRV (ref)) == SVt_PVAV) 116 && SvTYPE (SvRV (ref)) == SVt_PVAV
117 && !SvTIED_mg (SvRV (ref), PERL_MAGIC_tied))
62 return (AV *)SvRV (ref); 118 return (AV *)SvRV (ref);
63 119
64 croak ("argument 'heap' must be an array"); 120 croak ("argument 'heap' must be a (non-tied) array");
65} 121}
66 122
67#define geta(i) (*av_fetch (av, (i), 1))
68#define gt(a,b) cmp ((a), (b), data) 123#define gt(a,b) cmp ((a), (b), cmp_data)
69#define seta(i,v) seta_helper (av_fetch (av, (i), 1), v)
70 124
71static void 125/*****************************************************************************/
72seta_helper (SV **i, SV *v)
73{
74 SvREFCNT_dec (*i);
75 *i = v;
76}
77 126
127/* away from the root */
78static void 128static void
79push_heap_aux (AV *av, f_cmp cmp, SV *data, int hole_index, int top, SV *value) 129downheap (AV *av, f_cmp cmp, void *cmp_data, int N, int k)
80{ 130{
81 int parent = (hole_index - 1) / 2; 131 SV **heap = AvARRAY (av);
132 SV *he = heap [k];
82 133
83 while (hole_index > top && gt (geta (parent), value)) 134 for (;;)
84 {
85 seta (hole_index, SvREFCNT_inc (geta (parent)));
86 hole_index = parent;
87 parent = (hole_index - 1) / 2;
88 } 135 {
136 int c = (k << 1) + 1;
89 137
90 seta (hole_index, value); 138 if (c >= N)
91} 139 break;
92 140
93static void 141 c += c + 1 < N && gt (heap [c], heap [c + 1])
94adjust_heap (AV *av, f_cmp cmp, SV *data, int hole_index, int len, SV *elem) 142 ? 1 : 0;
95{
96 int top = hole_index;
97 int second_child = 2 * (hole_index + 1);
98 143
99 while (second_child < len) 144 if (!(gt (he, heap [c])))
145 break;
146
147 heap [k] = heap [c];
148
149 k = c;
100 { 150 }
101 if (gt (geta (second_child), geta (second_child - 1)))
102 second_child--;
103 151
104 seta (hole_index, SvREFCNT_inc (geta (second_child))); 152 heap [k] = he;
105 hole_index = second_child; 153}
106 second_child = 2 * (second_child + 1); 154
155/* towards the root */
156static void
157upheap (AV *av, f_cmp cmp, void *cmp_data, int k)
158{
159 SV **heap = AvARRAY (av);
160 SV *he = heap [k];
161
162 while (k)
107 } 163 {
164 int p = (k - 1) >> 1;
108 165
109 if (second_child == len) 166 if (!(gt (heap [p], he)))
167 break;
168
169 heap [k] = heap [p];
170 k = p;
110 { 171 }
111 seta (hole_index, SvREFCNT_inc (geta (second_child - 1)));
112 hole_index = second_child - 1;
113 }
114 172
115 push_heap_aux (av, cmp, data, hole_index, top, elem); 173 heap [k] = he;
116} 174}
117 175
176/* move an element suitably so it is in a correct place */
118static void 177static void
178adjustheap (AV *av, f_cmp cmp, void *cmp_data, int N, int k)
179{
180 SV **heap = AvARRAY (av);
181
182 if (k > 0 && !gt (heap [k], heap [(k - 1) >> 1]))
183 upheap (av, cmp, cmp_data, k);
184 else
185 downheap (av, cmp, cmp_data, N, k);
186}
187
188/*****************************************************************************/
189
190static void
119make_heap (AV *av, f_cmp cmp, SV *data) 191make_heap (AV *av, f_cmp cmp, void *cmp_data)
120{ 192{
121 if (av_len (av) > 0) 193 int i, len = AvFILLp (av);
122 {
123 int len = av_len (av) + 1;
124 int parent = (len - 2) / 2;
125 194
126 do { 195 /* do not use floyds algorithm, as I expect the simpler and more cache-efficient */
127 adjust_heap (av, cmp, data, parent, len, SvREFCNT_inc (geta (parent))); 196 /* upheap is actually faster */
128 } while (parent--); 197 for (i = 0; i <= len; ++i)
129 } 198 upheap (av, cmp, cmp_data, i);
130} 199}
131 200
132static void 201static void
133push_heap (AV *av, f_cmp cmp, SV *data, SV *elem) 202push_heap (AV *av, f_cmp cmp, void *cmp_data, SV *elem)
134{ 203{
135 elem = newSVsv (elem);
136 av_push (av, elem); 204 av_push (av, newSVsv (elem));
137 push_heap_aux (av, cmp, data, av_len (av), 0, SvREFCNT_inc (elem)); 205 upheap (av, cmp, cmp_data, AvFILLp (av));
138} 206}
139 207
140static SV * 208static SV *
141pop_heap (AV *av, f_cmp cmp, SV *data) 209pop_heap (AV *av, f_cmp cmp, void *cmp_data)
142{ 210{
211 int len = AvFILLp (av);
212
143 if (av_len (av) < 0) 213 if (len < 0)
144 return &PL_sv_undef; 214 return &PL_sv_undef;
145 else if (av_len (av) == 0) 215 else if (len == 0)
146 return av_pop (av); 216 return av_pop (av);
147 else 217 else
148 { 218 {
149 SV *result = newSVsv (geta (0));
150 SV *top = av_pop (av); 219 SV *top = av_pop (av);
151 220 SV *result = AvARRAY (av)[0];
152 adjust_heap (av, cmp, data, 0, av_len (av) + 1, top); 221 AvARRAY (av)[0] = top;
153 222 downheap (av, cmp, cmp_data, len, 0);
154 return result; 223 return result;
155 } 224 }
156} 225}
157 226
227static SV *
228splice_heap (AV *av, f_cmp cmp, void *cmp_data, int idx)
229{
230 int len = AvFILLp (av);
231
232 if (len < 0 || idx > len)
233 return &PL_sv_undef;
234 else if (len == 0 || idx == len)
235 return av_pop (av); /* the only or last element */
236 else
237 {
238 SV *top = av_pop (av);
239 SV *result = AvARRAY (av)[idx];
240 AvARRAY (av)[idx] = top;
241 adjustheap (av, cmp, cmp_data, len, idx);
242 return result;
243 }
244}
245
246static void
247adjust_heap (AV *av, f_cmp cmp, void *cmp_data, int idx)
248{
249 adjustheap (av, cmp, cmp_data, AvFILLp (av) + 1, idx);
250}
251
158MODULE = Array::Heap PACKAGE = Array::Heap 252MODULE = Array::Heap PACKAGE = Array::Heap
159 253
160void 254void
161make_heap (heap) 255make_heap (SV *heap)
162 SV * heap
163 PROTOTYPE: \@ 256 PROTOTYPE: \@
164 CODE: 257 CODE:
165 make_heap (array (heap), cmp_nv, 0); 258 make_heap (array (heap), cmp_nv, 0);
166 259
167void 260void
168make_heap_lex (heap) 261make_heap_lex (SV *heap)
169 SV * heap
170 PROTOTYPE: \@ 262 PROTOTYPE: \@
171 CODE: 263 CODE:
172 make_heap (array (heap), cmp_sv, 0); 264 make_heap (array (heap), cmp_sv, 0);
173 265
174void 266void
175make_heap_cmp (cmp, heap) 267make_heap_cmp (SV *cmp, SV *heap)
176 SV * cmp
177 SV * heap
178 PROTOTYPE: &\@ 268 PROTOTYPE: &\@
179 CODE: 269 CODE:
270{
271 dCMP;
272 CMP_PUSH (cmp);
180 make_heap (array (heap), cmp_custom, cmp); 273 make_heap (array (heap), cmp_custom, cmp_data);
274 CMP_POP;
275}
181 276
182void 277void
183push_heap (heap, ...) 278push_heap (SV *heap, ...)
184 SV * heap
185 PROTOTYPE: \@@ 279 PROTOTYPE: \@@
186 CODE: 280 CODE:
281{
187 int i; 282 int i;
188 for (i = 1; i < items; i++) 283 for (i = 1; i < items; i++)
189 push_heap (array (heap), cmp_nv, 0, ST(i)); 284 push_heap (array (heap), cmp_nv, 0, ST(i));
285}
190 286
191void 287void
192push_heap_lex (heap, ...) 288push_heap_lex (SV *heap, ...)
193 SV * heap
194 PROTOTYPE: \@@ 289 PROTOTYPE: \@@
195 CODE: 290 CODE:
291{
196 int i; 292 int i;
197 for (i = 1; i < items; i++) 293 for (i = 1; i < items; i++)
198 push_heap (array (heap), cmp_sv, 0, ST(i)); 294 push_heap (array (heap), cmp_sv, 0, ST(i));
295}
199 296
200void 297void
201push_heap_cmp (cmp, heap, ...) 298push_heap_cmp (SV *cmp, SV *heap, ...)
202 SV * cmp
203 SV * heap
204 PROTOTYPE: &\@@ 299 PROTOTYPE: &\@@
205 CODE: 300 CODE:
301{
206 int i; 302 int i;
303 dCMP;
304
305 CMP_PUSH (cmp);
207 for (i = 2; i < items; i++) 306 for (i = 2; i < items; i++)
208 push_heap (array (heap), cmp_custom, cmp, ST(i)); 307 push_heap (array (heap), cmp_custom, cmp_data, ST(i));
308 CMP_POP;
309}
209 310
210SV * 311SV *
211pop_heap (heap) 312pop_heap (SV *heap)
212 SV * heap
213 PROTOTYPE: \@ 313 PROTOTYPE: \@
214 CODE: 314 CODE:
215 RETVAL = pop_heap (array (heap), cmp_nv, 0); 315 RETVAL = pop_heap (array (heap), cmp_nv, 0);
216 OUTPUT: 316 OUTPUT:
217 RETVAL 317 RETVAL
218 318
219SV * 319SV *
220pop_heap_lex (heap) 320pop_heap_lex (SV *heap)
221 SV * heap
222 PROTOTYPE: \@ 321 PROTOTYPE: \@
223 CODE: 322 CODE:
224 RETVAL = pop_heap (array (heap), cmp_sv, 0); 323 RETVAL = pop_heap (array (heap), cmp_sv, 0);
225 OUTPUT: 324 OUTPUT:
226 RETVAL 325 RETVAL
227 326
228SV * 327SV *
229pop_heap_cmp (cmp, heap) 328pop_heap_cmp (SV *cmp, SV *heap)
230 SV * cmp
231 SV * heap
232 PROTOTYPE: &\@ 329 PROTOTYPE: &\@
233 CODE: 330 CODE:
331{
332 dCMP;
333 CMP_PUSH (cmp);
234 RETVAL = pop_heap (array (heap), cmp_custom, cmp); 334 RETVAL = pop_heap (array (heap), cmp_custom, cmp_data);
335 CMP_POP;
336}
235 OUTPUT: 337 OUTPUT:
236 RETVAL 338 RETVAL
237 339
340SV *
341splice_heap (SV *heap, int idx)
342 PROTOTYPE: \@$
343 CODE:
344 RETVAL = splice_heap (array (heap), cmp_nv, 0, idx);
345 OUTPUT:
346 RETVAL
238 347
348SV *
349splice_heap_lex (SV *heap, int idx)
350 PROTOTYPE: \@$
351 CODE:
352 RETVAL = splice_heap (array (heap), cmp_sv, 0, idx);
353 OUTPUT:
354 RETVAL
355
356SV *
357splice_heap_cmp (SV *cmp, SV *heap, int idx)
358 PROTOTYPE: &\@$
359 CODE:
360{
361 dCMP;
362 CMP_PUSH (cmp);
363 RETVAL = splice_heap (array (heap), cmp_custom, cmp_data, idx);
364 CMP_POP;
365}
366 OUTPUT:
367 RETVAL
368
369void
370adjust_heap (SV *heap, int idx)
371 PROTOTYPE: \@$
372 CODE:
373 adjust_heap (array (heap), cmp_nv, 0, idx);
374
375void
376adjust_heap_lex (SV *heap, int idx)
377 PROTOTYPE: \@$
378 CODE:
379 adjust_heap (array (heap), cmp_sv, 0, idx);
380
381void
382adjust_heap_cmp (SV *cmp, SV *heap, int idx)
383 PROTOTYPE: &\@$
384 CODE:
385{
386 dCMP;
387 CMP_PUSH (cmp);
388 adjust_heap (array (heap), cmp_custom, cmp_data, idx);
389 CMP_POP;
390}
391

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines