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

Diff Legend

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