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

Diff Legend

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