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.4 by root, Sun Jul 26 05:25:18 2009 UTC vs.
Revision 1.5 by root, Fri Apr 19 20:00:54 2013 UTC

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

Diff Legend

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