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.3 by root, Sun Jul 26 04:50:02 2009 UTC vs.
Revision 1.9 by root, Wed Dec 7 12:06:35 2016 UTC

… …
8#endif 8#endif
9#ifndef gv_fetchpvs 9#ifndef gv_fetchpvs
10# define gv_fetchpvs gv_fetchpv 10# define gv_fetchpvs gv_fetchpv
11#endif 11#endif
12 12
13/* pre-5.8 compatibility */
14#ifndef PERL_MAGIC_tied
15# define PERL_MAGIC_tied 'P'
16#endif
17
13#include "multicall.h" 18#include "multicall.h"
14 19
15/* workaround for buggy multicall API */ 20/* workaround for buggy multicall API */
16#ifndef cxinc 21#ifndef cxinc
17# define cxinc() Perl_cxinc (aTHX) 22# define cxinc() Perl_cxinc (aTHX)
… …
42 cv = sv_2cv (sv, &st, &gvp, 0); 47 cv = sv_2cv (sv, &st, &gvp, 0);
43 48
44 if (!cv) 49 if (!cv)
45 croak ("%s: callback must be a CODE reference or another callable object", SvPV_nolen (sv)); 50 croak ("%s: callback must be a CODE reference or another callable object", SvPV_nolen (sv));
46 51
47 if (!PL_firstgv) PL_firstgv = gv_fetchpvs ("a", GV_ADD | GV_NOTQUAL, SVt_PV); 52 SAVESPTR (PL_firstgv ); PL_firstgv = gv_fetchpv ("a", GV_ADD | GV_NOTQUAL, SVt_PV); SAVESPTR (GvSV (PL_firstgv ));
48 if (!PL_secondgv) PL_secondgv = gv_fetchpvs ("b", GV_ADD | GV_NOTQUAL, SVt_PV); 53 SAVESPTR (PL_secondgv); PL_secondgv = gv_fetchpv ("b", GV_ADD | GV_NOTQUAL, SVt_PV); SAVESPTR (GvSV (PL_secondgv));
49
50 SAVESPTR (GvSV (PL_firstgv));
51 SAVESPTR (GvSV (PL_secondgv));
52 54
53 return cv; 55 return cv;
54} 56}
55 57
56/*****************************************************************************/ 58/*****************************************************************************/
… …
60{ 62{
61 if (SvROK (sv) && SvTYPE (SvRV (sv)) == SVt_PVAV) 63 if (SvROK (sv) && SvTYPE (SvRV (sv)) == SVt_PVAV)
62 { 64 {
63 AV *av = (AV *)SvRV (sv); 65 AV *av = (AV *)SvRV (sv);
64 66
65 sv = AvFILLp (av) < 0 ? &PL_sv_undef : AvARRAY (av)[0]; 67 sv = AvFILLp (av) < 0 || !AvARRAY (sv)[0]
68 ? &PL_sv_undef : AvARRAY (av)[0];
66 } 69 }
67 70
68 return sv; 71 return sv;
69} 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)
70 107
71static int 108static int
72cmp_nv (SV *a, SV *b, void *cmp_data) 109cmp_nv (SV *a, SV *b, void *cmp_data)
73{ 110{
74 a = sv_first (a); 111 a = sv_first (a);
… …
89static int 126static int
90cmp_custom (SV *a, SV *b, void *cmp_data) 127cmp_custom (SV *a, SV *b, void *cmp_data)
91{ 128{
92 dCMP_CALL (cmp_data); 129 dCMP_CALL (cmp_data);
93 130
94 GvSV (PL_firstgv) = a; 131 GvSV (PL_firstgv ) = a;
95 GvSV (PL_secondgv) = b; 132 GvSV (PL_secondgv) = b;
96 133
97 MULTICALL; 134 MULTICALL;
98 135
99 if (SvTRUE (ERRSV)) 136 if (SvTRUE (ERRSV))
… …
124 161
125/*****************************************************************************/ 162/*****************************************************************************/
126 163
127/* away from the root */ 164/* away from the root */
128static void 165static void
129downheap (AV *av, f_cmp cmp, void *cmp_data, int N, int k) 166downheap (AV *av, f_cmp cmp, void *cmp_data, int N, int k, int flags)
130{ 167{
131 SV **heap = AvARRAY (av); 168 SV **heap = AvARRAY (av);
132 SV *he = heap [k]; 169 SV *he = heap [k];
133 170
134 for (;;) 171 for (;;)
… …
142 ? 1 : 0; 179 ? 1 : 0;
143 180
144 if (!(gt (he, heap [c]))) 181 if (!(gt (he, heap [c])))
145 break; 182 break;
146 183
147 heap [k] = heap [c]; 184 set_heap (k, heap [c]);
148 185
149 k = c; 186 k = c;
150 } 187 }
151 188
152 heap [k] = he; 189 set_heap (k, he);
153} 190}
154 191
155/* towards the root */ 192/* towards the root */
156static void 193static void
157upheap (AV *av, f_cmp cmp, void *cmp_data, int k) 194upheap (AV *av, f_cmp cmp, void *cmp_data, int k, int flags)
158{ 195{
159 SV **heap = AvARRAY (av); 196 SV **heap = AvARRAY (av);
160 SV *he = heap [k]; 197 SV *he = heap [k];
161 198
162 while (k) 199 while (k)
… …
164 int p = (k - 1) >> 1; 201 int p = (k - 1) >> 1;
165 202
166 if (!(gt (heap [p], he))) 203 if (!(gt (heap [p], he)))
167 break; 204 break;
168 205
169 heap [k] = heap [p]; 206 set_heap (k, heap [p]);
170 k = p; 207 k = p;
171 } 208 }
172 209
173 heap [k] = he; 210 set_heap (k, he);
174} 211}
175 212
176/* move an element suitably so it is in a correct place */ 213/* move an element suitably so it is in a correct place */
177static void 214static void
178adjustheap (AV *av, f_cmp cmp, void *cmp_data, int N, int k) 215adjustheap (AV *av, f_cmp cmp, void *cmp_data, int N, int k, int flags)
179{ 216{
180 SV **heap = AvARRAY (av); 217 SV **heap = AvARRAY (av);
181 218
182 if (k > 0 && !gt (heap [k], heap [(k - 1) >> 1])) 219 if (k > 0 && !gt (heap [k], heap [(k - 1) >> 1]))
183 upheap (av, cmp, cmp_data, k); 220 upheap (av, cmp, cmp_data, k, flags);
184 else 221 else
185 downheap (av, cmp, cmp_data, N, k); 222 downheap (av, cmp, cmp_data, N, k, flags);
186} 223}
187 224
188/*****************************************************************************/ 225/*****************************************************************************/
189 226
190static void 227static void
191make_heap (AV *av, f_cmp cmp, void *cmp_data) 228make_heap (AV *av, f_cmp cmp, void *cmp_data, int flags)
192{ 229{
193 int i, len = AvFILLp (av); 230 int i, len = AvFILLp (av);
194 231
195 /* do not use floyds algorithm, as I expect the simpler and more cache-efficient */ 232 /* do not use floyds algorithm, as I expect the simpler and more cache-efficient */
196 /* upheap is actually faster */ 233 /* upheap is actually faster */
197 for (i = 0; i <= len; ++i) 234 for (i = 0; i <= len; ++i)
198 upheap (av, cmp, cmp_data, i); 235 upheap (av, cmp, cmp_data, i, flags);
199} 236}
200 237
201static void 238static void
202push_heap (AV *av, f_cmp cmp, void *cmp_data, SV *elem) 239push_heap (AV *av, f_cmp cmp, void *cmp_data, SV **elems, int nelems, int flags)
203{ 240{
204 av_push (av, newSVsv (elem)); 241 int i;
242
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)
205 upheap (av, cmp, cmp_data, AvFILLp (av)); 250 upheap (av, cmp, cmp_data, AvFILLp (av) - i, flags);
206} 251}
207 252
208static SV * 253static SV *
209pop_heap (AV *av, f_cmp cmp, void *cmp_data) 254pop_heap (AV *av, f_cmp cmp, void *cmp_data, int flags)
210{ 255{
211 int len = AvFILLp (av); 256 int len = AvFILLp (av);
212 257
213 if (len < 0) 258 if (len < 0)
214 return &PL_sv_undef; 259 return &PL_sv_undef;
… …
217 else 262 else
218 { 263 {
219 SV *top = av_pop (av); 264 SV *top = av_pop (av);
220 SV *result = AvARRAY (av)[0]; 265 SV *result = AvARRAY (av)[0];
221 AvARRAY (av)[0] = top; 266 AvARRAY (av)[0] = top;
222 downheap (av, cmp, cmp_data, len, 0); 267 downheap (av, cmp, cmp_data, len, 0, flags);
223 return result; 268 return result;
224 } 269 }
225} 270}
226 271
227static SV * 272static SV *
228splice_heap (AV *av, f_cmp cmp, void *cmp_data, int idx) 273splice_heap (AV *av, f_cmp cmp, void *cmp_data, int idx, int flags)
229{ 274{
230 int len = AvFILLp (av); 275 int len = AvFILLp (av);
231 276
232 if (len < 0 || idx > len) 277 if (idx < 0 || idx > len)
233 return &PL_sv_undef; 278 return &PL_sv_undef;
234 else if (len == 0 || idx == len) 279 else if (idx == len)
235 return av_pop (av); /* the only or last element */ 280 return av_pop (av); /* the last element */
236 else 281 else
237 { 282 {
238 SV *top = av_pop (av); 283 SV *top = av_pop (av);
239 SV *result = AvARRAY (av)[idx]; 284 SV *result = AvARRAY (av)[idx];
240 AvARRAY (av)[idx] = top; 285 AvARRAY (av)[idx] = top;
241 adjustheap (av, cmp, cmp_data, len, idx); 286 adjustheap (av, cmp, cmp_data, len, idx, flags);
242 return result; 287 return result;
243 } 288 }
244} 289}
245 290
246static void 291static void
247adjust_heap (AV *av, f_cmp cmp, void *cmp_data, int idx) 292adjust_heap (AV *av, f_cmp cmp, void *cmp_data, int idx, int flags)
248{ 293{
294 int len = AvFILLp (av);
295
296 if (idx > len)
297 croak ("Array::Heap::adjust_heap: index out of array bounds");
298
249 adjustheap (av, cmp, cmp_data, AvFILLp (av) + 1, idx); 299 adjustheap (av, cmp, cmp_data, len + 1, idx, flags);
250} 300}
251 301
252MODULE = Array::Heap PACKAGE = Array::Heap 302MODULE = Array::Heap PACKAGE = Array::Heap
253 303
254void 304void
255make_heap (SV *heap) 305make_heap (SV *heap)
256 PROTOTYPE: \@ 306 PROTOTYPE: \@
307 ALIAS:
308 make_heap_idx = 1
257 CODE: 309 CODE:
258 make_heap (array (heap), cmp_nv, 0); 310 make_heap (array (heap), cmp_nv, 0, ix);
259 311
260void 312void
261make_heap_lex (SV *heap) 313make_heap_lex (SV *heap)
262 PROTOTYPE: \@ 314 PROTOTYPE: \@
263 CODE: 315 CODE:
264 make_heap (array (heap), cmp_sv, 0); 316 make_heap (array (heap), cmp_sv, 0, 0);
265 317
266void 318void
267make_heap_cmp (SV *cmp, SV *heap) 319make_heap_cmp (SV *cmp, SV *heap)
268 PROTOTYPE: &\@ 320 PROTOTYPE: &\@
269 CODE: 321 CODE:
270{ 322{
271 dCMP; 323 dCMP;
272 CMP_PUSH (cmp); 324 CMP_PUSH (cmp);
273 make_heap (array (heap), cmp_custom, cmp_data); 325 make_heap (array (heap), cmp_custom, cmp_data, 0);
274 CMP_POP; 326 CMP_POP;
275} 327}
276 328
277void 329void
278push_heap (SV *heap, ...) 330push_heap (SV *heap, ...)
279 PROTOTYPE: \@@ 331 PROTOTYPE: \@@
332 ALIAS:
333 push_heap_idx = 1
280 CODE: 334 CODE:
281{
282 int i;
283 for (i = 1; i < items; i++)
284 push_heap (array (heap), cmp_nv, 0, ST(i)); 335 push_heap (array (heap), cmp_nv, 0, &(ST(1)), items - 1, ix);
285}
286 336
287void 337void
288push_heap_lex (SV *heap, ...) 338push_heap_lex (SV *heap, ...)
289 PROTOTYPE: \@@ 339 PROTOTYPE: \@@
290 CODE: 340 CODE:
291{
292 int i;
293 for (i = 1; i < items; i++)
294 push_heap (array (heap), cmp_sv, 0, ST(i)); 341 push_heap (array (heap), cmp_sv, 0, &(ST(1)), items - 1, 0);
295}
296 342
297void 343void
298push_heap_cmp (SV *cmp, SV *heap, ...) 344push_heap_cmp (SV *cmp, SV *heap, ...)
299 PROTOTYPE: &\@@ 345 PROTOTYPE: &\@@
300 CODE: 346 CODE:
301{ 347{
302 int i; 348 SV **st_2 = &(ST(2)); /* multicall.h uses PUSHSTACK */
303 dCMP; 349 dCMP;
304
305 CMP_PUSH (cmp); 350 CMP_PUSH (cmp);
306 for (i = 2; i < items; i++)
307 push_heap (array (heap), cmp_custom, cmp_data, ST(i)); 351 push_heap (array (heap), cmp_custom, cmp_data, st_2, items - 2, 0);
308 CMP_POP; 352 CMP_POP;
309} 353}
310 354
311SV * 355SV *
312pop_heap (SV *heap) 356pop_heap (SV *heap)
313 PROTOTYPE: \@ 357 PROTOTYPE: \@
358 ALIAS:
359 pop_heap_idx = 1
314 CODE: 360 CODE:
315 RETVAL = pop_heap (array (heap), cmp_nv, 0); 361 RETVAL = pop_heap (array (heap), cmp_nv, 0, ix);
316 OUTPUT: 362 OUTPUT:
317 RETVAL 363 RETVAL
318 364
319SV * 365SV *
320pop_heap_lex (SV *heap) 366pop_heap_lex (SV *heap)
321 PROTOTYPE: \@ 367 PROTOTYPE: \@
322 CODE: 368 CODE:
323 RETVAL = pop_heap (array (heap), cmp_sv, 0); 369 RETVAL = pop_heap (array (heap), cmp_sv, 0, 0);
324 OUTPUT: 370 OUTPUT:
325 RETVAL 371 RETVAL
326 372
327SV * 373SV *
328pop_heap_cmp (SV *cmp, SV *heap) 374pop_heap_cmp (SV *cmp, SV *heap)
329 PROTOTYPE: &\@ 375 PROTOTYPE: &\@
330 CODE: 376 CODE:
331{ 377{
332 dCMP; 378 dCMP;
333 CMP_PUSH (cmp); 379 CMP_PUSH (cmp);
334 RETVAL = pop_heap (array (heap), cmp_custom, cmp_data); 380 RETVAL = pop_heap (array (heap), cmp_custom, cmp_data, 0);
335 CMP_POP; 381 CMP_POP;
336} 382}
337 OUTPUT: 383 OUTPUT:
338 RETVAL 384 RETVAL
339 385
340SV * 386SV *
341splice_heap (SV *heap, int idx) 387splice_heap (SV *heap, int idx)
342 PROTOTYPE: \@$ 388 PROTOTYPE: \@$
389 ALIAS:
390 splice_heap_idx = 1
343 CODE: 391 CODE:
344 RETVAL = splice_heap (array (heap), cmp_nv, 0, idx); 392 RETVAL = splice_heap (array (heap), cmp_nv, 0, idx, ix);
345 OUTPUT: 393 OUTPUT:
346 RETVAL 394 RETVAL
347 395
348SV * 396SV *
349splice_heap_lex (SV *heap, int idx) 397splice_heap_lex (SV *heap, int idx)
350 PROTOTYPE: \@$ 398 PROTOTYPE: \@$
351 CODE: 399 CODE:
352 RETVAL = splice_heap (array (heap), cmp_sv, 0, idx); 400 RETVAL = splice_heap (array (heap), cmp_sv, 0, idx, 0);
353 OUTPUT: 401 OUTPUT:
354 RETVAL 402 RETVAL
355 403
356SV * 404SV *
357splice_heap_cmp (SV *cmp, SV *heap, int idx) 405splice_heap_cmp (SV *cmp, SV *heap, int idx)
358 PROTOTYPE: &\@$ 406 PROTOTYPE: &\@$
359 CODE: 407 CODE:
360{ 408{
361 dCMP; 409 dCMP;
362 CMP_PUSH (cmp); 410 CMP_PUSH (cmp);
363 RETVAL = splice_heap (array (heap), cmp_custom, cmp_data, idx); 411 RETVAL = splice_heap (array (heap), cmp_custom, cmp_data, idx, 0);
364 CMP_POP; 412 CMP_POP;
365} 413}
366 OUTPUT: 414 OUTPUT:
367 RETVAL 415 RETVAL
368 416
369void 417void
370adjust_heap (SV *heap, int idx) 418adjust_heap (SV *heap, int idx)
371 PROTOTYPE: \@$ 419 PROTOTYPE: \@$
420 ALIAS:
421 adjust_heap_idx = 1
372 CODE: 422 CODE:
373 adjust_heap (array (heap), cmp_nv, 0, idx); 423 adjust_heap (array (heap), cmp_nv, 0, idx, ix);
374 424
375void 425void
376adjust_heap_lex (SV *heap, int idx) 426adjust_heap_lex (SV *heap, int idx)
377 PROTOTYPE: \@$ 427 PROTOTYPE: \@$
378 CODE: 428 CODE:
379 adjust_heap (array (heap), cmp_sv, 0, idx); 429 adjust_heap (array (heap), cmp_sv, 0, idx, 0);
380 430
381void 431void
382adjust_heap_cmp (SV *cmp, SV *heap, int idx) 432adjust_heap_cmp (SV *cmp, SV *heap, int idx)
383 PROTOTYPE: &\@$ 433 PROTOTYPE: &\@$
384 CODE: 434 CODE:
385{ 435{
386 dCMP; 436 dCMP;
387 CMP_PUSH (cmp); 437 CMP_PUSH (cmp);
388 adjust_heap (array (heap), cmp_custom, cmp_data, idx); 438 adjust_heap (array (heap), cmp_custom, cmp_data, idx, 0);
389 CMP_POP; 439 CMP_POP;
390} 440}
391 441

Diff Legend

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