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

Diff Legend

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