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

Diff Legend

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