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.5 by root, Fri Apr 19 20:00:54 2013 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 (len < 0 || idx > len)
233 return &PL_sv_undef; 277 return &PL_sv_undef;
… …
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{
249 adjustheap (av, cmp, cmp_data, AvFILLp (av) + 1, idx); 293 adjustheap (av, cmp, cmp_data, AvFILLp (av) + 1, idx, flags);
250} 294}
251 295
252MODULE = Array::Heap PACKAGE = Array::Heap 296MODULE = Array::Heap PACKAGE = Array::Heap
253 297
254void 298void
255make_heap (SV *heap) 299make_heap (SV *heap)
256 PROTOTYPE: \@ 300 PROTOTYPE: \@
301 ALIAS:
302 make_heap_idx = 1
257 CODE: 303 CODE:
258 make_heap (array (heap), cmp_nv, 0); 304 make_heap (array (heap), cmp_nv, 0, ix);
259 305
260void 306void
261make_heap_lex (SV *heap) 307make_heap_lex (SV *heap)
262 PROTOTYPE: \@ 308 PROTOTYPE: \@
263 CODE: 309 CODE:
264 make_heap (array (heap), cmp_sv, 0); 310 make_heap (array (heap), cmp_sv, 0, 0);
265 311
266void 312void
267make_heap_cmp (SV *cmp, SV *heap) 313make_heap_cmp (SV *cmp, SV *heap)
268 PROTOTYPE: &\@ 314 PROTOTYPE: &\@
269 CODE: 315 CODE:
270{ 316{
271 dCMP; 317 dCMP;
272 CMP_PUSH (cmp); 318 CMP_PUSH (cmp);
273 make_heap (array (heap), cmp_custom, cmp_data); 319 make_heap (array (heap), cmp_custom, cmp_data, 0);
274 CMP_POP; 320 CMP_POP;
275} 321}
276 322
277void 323void
278push_heap (SV *heap, ...) 324push_heap (SV *heap, ...)
279 PROTOTYPE: \@@ 325 PROTOTYPE: \@@
326 ALIAS:
327 push_heap_idx = 1
280 CODE: 328 CODE:
281{
282 int i;
283 for (i = 1; i < items; i++)
284 push_heap (array (heap), cmp_nv, 0, ST(i)); 329 push_heap (array (heap), cmp_nv, 0, &(ST(1)), items - 1, ix);
285}
286 330
287void 331void
288push_heap_lex (SV *heap, ...) 332push_heap_lex (SV *heap, ...)
289 PROTOTYPE: \@@ 333 PROTOTYPE: \@@
290 CODE: 334 CODE:
291{
292 int i;
293 for (i = 1; i < items; i++)
294 push_heap (array (heap), cmp_sv, 0, ST(i)); 335 push_heap (array (heap), cmp_sv, 0, &(ST(1)), items - 1, 0);
295}
296 336
297void 337void
298push_heap_cmp (SV *cmp, SV *heap, ...) 338push_heap_cmp (SV *cmp, SV *heap, ...)
299 PROTOTYPE: &\@@ 339 PROTOTYPE: &\@@
300 CODE: 340 CODE:
301{ 341{
302 int i; 342 SV **st_2 = &(ST(2)); /* multicall.h uses PUSHSTACK */
303 dCMP; 343 dCMP;
304
305 CMP_PUSH (cmp); 344 CMP_PUSH (cmp);
306 for (i = 2; i < items; i++)
307 push_heap (array (heap), cmp_custom, cmp_data, ST(i)); 345 push_heap (array (heap), cmp_custom, cmp_data, st_2, items - 2, 0);
308 CMP_POP; 346 CMP_POP;
309} 347}
310 348
311SV * 349SV *
312pop_heap (SV *heap) 350pop_heap (SV *heap)
313 PROTOTYPE: \@ 351 PROTOTYPE: \@
352 ALIAS:
353 pop_heap_idx = 1
314 CODE: 354 CODE:
315 RETVAL = pop_heap (array (heap), cmp_nv, 0); 355 RETVAL = pop_heap (array (heap), cmp_nv, 0, ix);
316 OUTPUT: 356 OUTPUT:
317 RETVAL 357 RETVAL
318 358
319SV * 359SV *
320pop_heap_lex (SV *heap) 360pop_heap_lex (SV *heap)
321 PROTOTYPE: \@ 361 PROTOTYPE: \@
322 CODE: 362 CODE:
323 RETVAL = pop_heap (array (heap), cmp_sv, 0); 363 RETVAL = pop_heap (array (heap), cmp_sv, 0, 0);
324 OUTPUT: 364 OUTPUT:
325 RETVAL 365 RETVAL
326 366
327SV * 367SV *
328pop_heap_cmp (SV *cmp, SV *heap) 368pop_heap_cmp (SV *cmp, SV *heap)
329 PROTOTYPE: &\@ 369 PROTOTYPE: &\@
330 CODE: 370 CODE:
331{ 371{
332 dCMP; 372 dCMP;
333 CMP_PUSH (cmp); 373 CMP_PUSH (cmp);
334 RETVAL = pop_heap (array (heap), cmp_custom, cmp_data); 374 RETVAL = pop_heap (array (heap), cmp_custom, cmp_data, 0);
335 CMP_POP; 375 CMP_POP;
336} 376}
337 OUTPUT: 377 OUTPUT:
338 RETVAL 378 RETVAL
339 379
340SV * 380SV *
341splice_heap (SV *heap, int idx) 381splice_heap (SV *heap, int idx)
342 PROTOTYPE: \@$ 382 PROTOTYPE: \@$
383 ALIAS:
384 splice_heap_idx = 1
343 CODE: 385 CODE:
344 RETVAL = splice_heap (array (heap), cmp_nv, 0, idx); 386 RETVAL = splice_heap (array (heap), cmp_nv, 0, idx, ix);
345 OUTPUT: 387 OUTPUT:
346 RETVAL 388 RETVAL
347 389
348SV * 390SV *
349splice_heap_lex (SV *heap, int idx) 391splice_heap_lex (SV *heap, int idx)
350 PROTOTYPE: \@$ 392 PROTOTYPE: \@$
351 CODE: 393 CODE:
352 RETVAL = splice_heap (array (heap), cmp_sv, 0, idx); 394 RETVAL = splice_heap (array (heap), cmp_sv, 0, idx, 0);
353 OUTPUT: 395 OUTPUT:
354 RETVAL 396 RETVAL
355 397
356SV * 398SV *
357splice_heap_cmp (SV *cmp, SV *heap, int idx) 399splice_heap_cmp (SV *cmp, SV *heap, int idx)
358 PROTOTYPE: &\@$ 400 PROTOTYPE: &\@$
359 CODE: 401 CODE:
360{ 402{
361 dCMP; 403 dCMP;
362 CMP_PUSH (cmp); 404 CMP_PUSH (cmp);
363 RETVAL = splice_heap (array (heap), cmp_custom, cmp_data, idx); 405 RETVAL = splice_heap (array (heap), cmp_custom, cmp_data, idx, 0);
364 CMP_POP; 406 CMP_POP;
365} 407}
366 OUTPUT: 408 OUTPUT:
367 RETVAL 409 RETVAL
368 410
369void 411void
370adjust_heap (SV *heap, int idx) 412adjust_heap (SV *heap, int idx)
371 PROTOTYPE: \@$ 413 PROTOTYPE: \@$
414 ALIAS:
415 adjust_heap_idx = 1
372 CODE: 416 CODE:
373 adjust_heap (array (heap), cmp_nv, 0, idx); 417 adjust_heap (array (heap), cmp_nv, 0, idx, ix);
374 418
375void 419void
376adjust_heap_lex (SV *heap, int idx) 420adjust_heap_lex (SV *heap, int idx)
377 PROTOTYPE: \@$ 421 PROTOTYPE: \@$
378 CODE: 422 CODE:
379 adjust_heap (array (heap), cmp_sv, 0, idx); 423 adjust_heap (array (heap), cmp_sv, 0, idx, 0);
380 424
381void 425void
382adjust_heap_cmp (SV *cmp, SV *heap, int idx) 426adjust_heap_cmp (SV *cmp, SV *heap, int idx)
383 PROTOTYPE: &\@$ 427 PROTOTYPE: &\@$
384 CODE: 428 CODE:
385{ 429{
386 dCMP; 430 dCMP;
387 CMP_PUSH (cmp); 431 CMP_PUSH (cmp);
388 adjust_heap (array (heap), cmp_custom, cmp_data, idx); 432 adjust_heap (array (heap), cmp_custom, cmp_data, idx, 0);
389 CMP_POP; 433 CMP_POP;
390} 434}
391 435

Diff Legend

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