File Coverage

HeapPQ.c

Criterion	Covered	Total	%
statement	1450	1707	84.9
branch	615	1024	60.0
condition			n/a
subroutine			n/a
pod			n/a
total	2065	2731	75.6

line	stmt	bran	code
1			/*
2			* heap.c - Ultra-fast binary heap (priority queue)
3			*
4			* Three API levels for different speed/convenience tradeoffs:
5			*
6			* 1. RAW ARRAY API (fastest - matches Array::Heap speed)
7			* push_heap_min(\@array, $val)
8			* pop_heap_min(\@array)
9			* make_heap_min(\@array) # O(n) Floyd's heapify
10			*
11			* 2. NUMERIC HEAP (very fast - stores NV directly, no SV overhead)
12			* my $h = heap::new_nv('min');
13			* $h->push(3.14); # No SV allocation
14			* $h->pop; # Returns NV directly
15			*
16			* 3. OO HEAP (convenient - stores any Perl values)
17			* my $h = heap::new('min');
18			* $h->push($anything);
19			*
20			* Optimizations:
21			* - Custom ops bypass method dispatch
22			* - Inlined comparison for min/max heaps
23			* - Floyd's O(n) heapify for bulk operations
24			* - Zero-copy returns where possible
25			*/
26
27			#include "EXTERN.h"
28			#include "perl.h"
29			#include "XSUB.h"
30			#include "heap_compat.h"
31
32			/* ============================================
33			Heap type enum
34			============================================ */
35			typedef enum {
36			HEAP_MIN = 0,
37			HEAP_MAX = 1
38			} HeapType;
39
40			/* ============================================
41			Standard Heap structure (stores SV*)
42			============================================ */
43			typedef struct Heap_s Heap;
44			typedef void (heap_sift_fn)(pTHX_ Heap, IV);
45
46			struct Heap_s {
47			SV **data;
48			NV *priorities;
49			IV size;
50			IV capacity;
51			HeapType type;
52			SV *comparator;
53			heap_sift_fn sift_up;
54			heap_sift_fn sift_down;
55			};
56
57			/* ============================================
58			Numeric Heap structure (stores NV directly)
59			============================================ */
60			typedef struct {
61			NV *data;
62			IV size;
63			IV capacity;
64			HeapType type;
65			} NumericHeap;
66
67			/* ============================================
68			Custom op declarations
69			============================================ */
70			static XOP heap_func_push_xop;
71			static XOP heap_func_pop_xop;
72			static XOP heap_func_peek_xop;
73			static XOP heap_func_size_xop;
74
75			/* Raw array ops */
76			static XOP push_heap_min_xop;
77			static XOP pop_heap_min_xop;
78			static XOP push_heap_max_xop;
79			static XOP pop_heap_max_xop;
80			static XOP make_heap_min_xop;
81			static XOP make_heap_max_xop;
82
83			/* Numeric heap ops */
84			static XOP nv_push_xop;
85			static XOP nv_pop_xop;
86			static XOP nv_peek_xop;
87			static XOP nv_size_xop;
88			static XOP nv_peek_n_xop;
89
90			/* peek_n ops */
91			static XOP heap_func_peek_n_xop;
92
93			/* is_empty/clear/type ops */
94			static XOP heap_func_is_empty_xop;
95			static XOP heap_func_clear_xop;
96			static XOP heap_func_type_xop;
97			static XOP nv_is_empty_xop;
98			static XOP nv_clear_xop;
99
100			/* search/delete ops */
101			static XOP heap_func_search_xop;
102			static XOP heap_func_delete_xop;
103			static XOP nv_search_xop;
104			static XOP nv_delete_xop;
105
106			/* ============================================
107			Magic vtables
108			============================================ */
109			static int heap_free(pTHX_ SV sv, MAGIC mg);
110			static int numeric_heap_free(pTHX_ SV sv, MAGIC mg);
111
112			static MGVTBL heap_vtbl = {
113			NULL, NULL, NULL, NULL,
114			heap_free,
115			NULL, NULL, NULL
116			};
117
118			static MGVTBL numeric_heap_vtbl = {
119			NULL, NULL, NULL, NULL,
120			numeric_heap_free,
121			NULL, NULL, NULL
122			};
123
124			/* ============================================
125			Unified heap lookup (single magic walk)
126			============================================ */
127			typedef enum { MAGIC_NONE, MAGIC_HEAP, MAGIC_NUMERIC } HeapMagicType;
128
129			typedef struct {
130			HeapMagicType type;
131			union {
132			Heap *heap;
133			NumericHeap *nheap;
134			} ptr;
135			} HeapLookup;
136
137	22101		PERL_STATIC_INLINE HeapLookup find_heap(pTHX_ SV *obj) {
138			HeapLookup result;
139			MAGIC *mg;
140	22101		result.type = MAGIC_NONE;
141	22101		result.ptr.heap = NULL;
142	22101	50	if (!SvROK(obj)) return result;
143	22101		mg = mg_find(SvRV(obj), PERL_MAGIC_ext);
144	22101	50	while (mg) {
145	22101	100	if (mg->mg_virtual == &heap_vtbl) {
146	22093		result.type = MAGIC_HEAP;
147	22093		result.ptr.heap = (Heap*)mg->mg_ptr;
148	22093		return result;
149			}
150	8	50	if (mg->mg_virtual == &numeric_heap_vtbl) {
151	8		result.type = MAGIC_NUMERIC;
152	8		result.ptr.nheap = (NumericHeap*)mg->mg_ptr;
153	8		return result;
154			}
155	0		mg = mg->mg_moremagic;
156			}
157	0		return result;
158			}
159
160			/* ============================================
161			Get structures from blessed SV
162			============================================ */
163			/* Fast path: OO methods always receive a valid blessed ref.
164			Our magic is always the first PERL_MAGIC_ext on the SV. */
165			#define HEAP_FAST(sv) ((Heap*)mg_find(SvRV(sv), PERL_MAGIC_ext)->mg_ptr)
166			#define NV_HEAP_FAST(sv) ((NumericHeap*)mg_find(SvRV(sv), PERL_MAGIC_ext)->mg_ptr)
167
168			#define GET_HEAP_MAGIC(obj) mg_find(SvRV(obj), PERL_MAGIC_ext)
169
170	7		PERL_STATIC_INLINE Heap* get_heap(pTHX_ SV *obj) {
171			MAGIC *mg;
172	7	50	if (!SvROK(obj)) croak("Not a reference");
173	7		mg = mg_find(SvRV(obj), PERL_MAGIC_ext);
174	7	50	while (mg) {
175	7	50	if (mg->mg_virtual == &heap_vtbl) {
176	7		return (Heap*)mg->mg_ptr;
177			}
178	0		mg = mg->mg_moremagic;
179			}
180	0		croak("Not a heap object");
181			return NULL;
182			}
183
184			PERL_STATIC_INLINE NumericHeap* get_numeric_heap(pTHX_ SV *obj) {
185			MAGIC *mg;
186			if (!SvROK(obj)) croak("Not a reference");
187			mg = mg_find(SvRV(obj), PERL_MAGIC_ext);
188			while (mg) {
189			if (mg->mg_virtual == &numeric_heap_vtbl) {
190			return (NumericHeap*)mg->mg_ptr;
191			}
192			mg = mg->mg_moremagic;
193			}
194			croak("Not a numeric heap object");
195			return NULL;
196			}
197
198			/* ============================================
199			PART 1: RAW ARRAY API (fastest)
200			Operates directly on Perl arrays
201			============================================ */
202
203			/* Sift up for raw array - min heap */
204	4409		static void raw_sift_up_min(pTHX_ AV *av, IV idx) {
205	4409		SV **arr = AvARRAY(av);
206	4409		SV *val = arr[idx];
207	4409		NV val_nv = SvNV(val);
208
209	4414	100	while (idx > 0) {
210	3809		IV parent = (idx - 1) >> 1;
211	3809		NV parent_nv = SvNV(arr[parent]);
212	3809	100	if (val_nv < parent_nv) {
213	5		arr[idx] = arr[parent];
214	5		idx = parent;
215			} else {
216	3804		break;
217			}
218			}
219	4409		arr[idx] = val;
220	4409		}
221
222			/* Sift up for raw array - max heap */
223	409		static void raw_sift_up_max(pTHX_ AV *av, IV idx) {
224	409		SV **arr = AvARRAY(av);
225	409		SV *val = arr[idx];
226	409		NV val_nv = SvNV(val);
227
228	415	100	while (idx > 0) {
229	10		IV parent = (idx - 1) >> 1;
230	10		NV parent_nv = SvNV(arr[parent]);
231	10	100	if (val_nv > parent_nv) {
232	6		arr[idx] = arr[parent];
233	6		idx = parent;
234			} else {
235	4		break;
236			}
237			}
238	409		arr[idx] = val;
239	409		}
240
241			/* Sift down for raw array - min heap */
242	6542		static void raw_sift_down_min(pTHX_ AV *av, IV idx, IV size) {
243	6542		SV **arr = AvARRAY(av);
244	6542		SV *val = arr[idx];
245	6542		NV val_nv = SvNV(val);
246	6542		IV half = size >> 1;
247
248	24825	100	while (idx < half) {
249	18849		IV left = (idx << 1) + 1;
250	18849		IV right = left + 1;
251	18849		IV best = left;
252	18849		NV best_nv = SvNV(arr[left]);
253
254	18849	100	if (right < size) {
255	18425		NV right_nv = SvNV(arr[right]);
256	18425	100	if (right_nv < best_nv) {
257	8265		best = right;
258	8265		best_nv = right_nv;
259			}
260			}
261
262	18849	100	if (best_nv < val_nv) {
263	18283		arr[idx] = arr[best];
264	18283		idx = best;
265			} else {
266	566		break;
267			}
268			}
269	6542		arr[idx] = val;
270	6542		}
271
272			/* Sift down for raw array - max heap */
273	1215		static void raw_sift_down_max(pTHX_ AV *av, IV idx, IV size) {
274	1215		SV **arr = AvARRAY(av);
275	1215		SV *val = arr[idx];
276	1215		NV val_nv = SvNV(val);
277	1215		IV half = size >> 1;
278
279	2427	100	while (idx < half) {
280	1617		IV left = (idx << 1) + 1;
281	1617		IV right = left + 1;
282	1617		IV best = left;
283	1617		NV best_nv = SvNV(arr[left]);
284
285	1617	100	if (right < size) {
286	1613		NV right_nv = SvNV(arr[right]);
287	1613	100	if (right_nv > best_nv) {
288	804		best = right;
289	804		best_nv = right_nv;
290			}
291			}
292
293	1617	100	if (best_nv > val_nv) {
294	1212		arr[idx] = arr[best];
295	1212		idx = best;
296			} else {
297	405		break;
298			}
299			}
300	1215		arr[idx] = val;
301	1215		}
302
303			/* push_heap_min(\@array, $value) */
304	0		XS_EXTERNAL(XS_push_heap_min) {
305	0		dXSARGS;
306			AV *av;
307			SV *val;
308			IV size;
309
310	0	0	if (items != 2) croak("Usage: push_heap_min(\\@array, $value)");
311	0	0	if (!SvROK(ST(0)) \|\| SvTYPE(SvRV(ST(0))) != SVt_PVAV) {
		0
312	0		croak("First argument must be an array reference");
313			}
314
315	0		av = (AV*)SvRV(ST(0));
316	0		val = newSVsv(ST(1));
317
318	0		av_push(av, val);
319	0		size = av_len(av) + 1;
320	0		raw_sift_up_min(aTHX_ av, size - 1);
321
322	0		XSRETURN_EMPTY;
323			}
324
325			/* push_heap_max(\@array, $value) */
326	0		XS_EXTERNAL(XS_push_heap_max) {
327	0		dXSARGS;
328			AV *av;
329			SV *val;
330			IV size;
331
332	0	0	if (items != 2) croak("Usage: push_heap_max(\\@array, $value)");
333	0	0	if (!SvROK(ST(0)) \|\| SvTYPE(SvRV(ST(0))) != SVt_PVAV) {
		0
334	0		croak("First argument must be an array reference");
335			}
336
337	0		av = (AV*)SvRV(ST(0));
338	0		val = newSVsv(ST(1));
339
340	0		av_push(av, val);
341	0		size = av_len(av) + 1;
342	0		raw_sift_up_max(aTHX_ av, size - 1);
343
344	0		XSRETURN_EMPTY;
345			}
346
347			/* pop_heap_min(\@array) */
348	0		XS_EXTERNAL(XS_pop_heap_min) {
349	0		dXSARGS;
350			AV *av;
351			IV size;
352			SV *result;
353			SV **arr;
354
355	0	0	if (items != 1) croak("Usage: pop_heap_min(\\@array)");
356	0	0	if (!SvROK(ST(0)) \|\| SvTYPE(SvRV(ST(0))) != SVt_PVAV) {
		0
357	0		croak("First argument must be an array reference");
358			}
359
360	0		av = (AV*)SvRV(ST(0));
361	0		size = av_len(av) + 1;
362
363	0	0	if (size == 0) XSRETURN_UNDEF;
364
365	0		arr = AvARRAY(av);
366	0		result = arr[0];
367
368	0	0	if (size > 1) {
369	0		arr[0] = arr[size - 1];
370	0		AvFILLp(av) = size - 2;
371	0		raw_sift_down_min(aTHX_ av, 0, size - 1);
372			} else {
373	0		AvFILLp(av) = -1;
374			}
375
376	0		ST(0) = sv_2mortal(result);
377	0		XSRETURN(1);
378			}
379
380			/* pop_heap_max(\@array) */
381	0		XS_EXTERNAL(XS_pop_heap_max) {
382	0		dXSARGS;
383			AV *av;
384			IV size;
385			SV *result;
386			SV **arr;
387
388	0	0	if (items != 1) croak("Usage: pop_heap_max(\\@array)");
389	0	0	if (!SvROK(ST(0)) \|\| SvTYPE(SvRV(ST(0))) != SVt_PVAV) {
		0
390	0		croak("First argument must be an array reference");
391			}
392
393	0		av = (AV*)SvRV(ST(0));
394	0		size = av_len(av) + 1;
395
396	0	0	if (size == 0) XSRETURN_UNDEF;
397
398	0		arr = AvARRAY(av);
399	0		result = arr[0];
400
401	0	0	if (size > 1) {
402	0		arr[0] = arr[size - 1];
403	0		AvFILLp(av) = size - 2;
404	0		raw_sift_down_max(aTHX_ av, 0, size - 1);
405			} else {
406	0		AvFILLp(av) = -1;
407			}
408
409	0		ST(0) = sv_2mortal(result);
410	0		XSRETURN(1);
411			}
412
413			/* make_heap_min(\@array) - Floyd's O(n) heapify */
414	0		XS_EXTERNAL(XS_make_heap_min) {
415	0		dXSARGS;
416			AV *av;
417			IV size, i;
418
419	0	0	if (items != 1) croak("Usage: make_heap_min(\\@array)");
420	0	0	if (!SvROK(ST(0)) \|\| SvTYPE(SvRV(ST(0))) != SVt_PVAV) {
		0
421	0		croak("First argument must be an array reference");
422			}
423
424	0		av = (AV*)SvRV(ST(0));
425	0		size = av_len(av) + 1;
426
427			/* Floyd's algorithm: sift down from middle to root */
428	0	0	for (i = (size >> 1) - 1; i >= 0; i--) {
429	0		raw_sift_down_min(aTHX_ av, i, size);
430			}
431
432	0		XSRETURN_EMPTY;
433			}
434
435			/* make_heap_max(\@array) - Floyd's O(n) heapify */
436	0		XS_EXTERNAL(XS_make_heap_max) {
437	0		dXSARGS;
438			AV *av;
439			IV size, i;
440
441	0	0	if (items != 1) croak("Usage: make_heap_max(\\@array)");
442	0	0	if (!SvROK(ST(0)) \|\| SvTYPE(SvRV(ST(0))) != SVt_PVAV) {
		0
443	0		croak("First argument must be an array reference");
444			}
445
446	0		av = (AV*)SvRV(ST(0));
447	0		size = av_len(av) + 1;
448
449	0	0	for (i = (size >> 1) - 1; i >= 0; i--) {
450	0		raw_sift_down_max(aTHX_ av, i, size);
451			}
452
453	0		XSRETURN_EMPTY;
454			}
455
456			/* ============================================
457			Raw array custom ops
458			============================================ */
459
460			/* pp_push_heap_min: BINOP(\@array, $value) */
461	4410		static OP* pp_push_heap_min(pTHX) {
462	4410		dSP;
463	4410		SV *val_sv = TOPs;
464	4410		SV *aref = TOPm1s;
465			AV *av;
466			SV *val;
467			IV size;
468
469	4410	100	if (!SvROK(aref) \|\| SvTYPE(SvRV(aref)) != SVt_PVAV)
		50
470	1		croak("First argument must be an array reference");
471
472	4409		av = (AV*)SvRV(aref);
473	4409		val = newSVsv(val_sv);
474	4409		av_push(av, val);
475	4409		size = av_len(av) + 1;
476	4409		raw_sift_up_min(aTHX_ av, size - 1);
477
478	4409		SP--;
479	4409		SETs(&PL_sv_undef);
480	4409		RETURN;
481			}
482
483			/* pp_push_heap_max: BINOP(\@array, $value) */
484	410		static OP* pp_push_heap_max(pTHX) {
485	410		dSP;
486	410		SV *val_sv = TOPs;
487	410		SV *aref = TOPm1s;
488			AV *av;
489			SV *val;
490			IV size;
491
492	410	50	if (!SvROK(aref) \|\| SvTYPE(SvRV(aref)) != SVt_PVAV)
		100
493	1		croak("First argument must be an array reference");
494
495	409		av = (AV*)SvRV(aref);
496	409		val = newSVsv(val_sv);
497	409		av_push(av, val);
498	409		size = av_len(av) + 1;
499	409		raw_sift_up_max(aTHX_ av, size - 1);
500
501	409		SP--;
502	409		SETs(&PL_sv_undef);
503	409		RETURN;
504			}
505
506			/* pp_pop_heap_min: UNOP(\@array) */
507	5436		static OP* pp_pop_heap_min(pTHX) {
508	5436		dSP;
509	5436		SV *aref = TOPs;
510			AV *av;
511			IV size;
512			SV *result;
513			SV **arr;
514
515	5436	100	if (!SvROK(aref) \|\| SvTYPE(SvRV(aref)) != SVt_PVAV)
		50
516	1		croak("First argument must be an array reference");
517
518	5435		av = (AV*)SvRV(aref);
519	5435		size = av_len(av) + 1;
520
521	5435	100	if (size == 0) {
522	2		SETs(&PL_sv_undef);
523	2		RETURN;
524			}
525
526	5433		arr = AvARRAY(av);
527	5433		result = arr[0];
528
529	5433	100	if (size > 1) {
530	4824		arr[0] = arr[size - 1];
531	4824		AvFILLp(av) = size - 2;
532	4824		raw_sift_down_min(aTHX_ av, 0, size - 1);
533			} else {
534	609		AvFILLp(av) = -1;
535			}
536
537	5433		SETs(sv_2mortal(result));
538	5433		RETURN;
539			}
540
541			/* pp_pop_heap_max: UNOP(\@array) */
542	412		static OP* pp_pop_heap_max(pTHX) {
543	412		dSP;
544	412		SV *aref = TOPs;
545			AV *av;
546			IV size;
547			SV *result;
548			SV **arr;
549
550	412	100	if (!SvROK(aref) \|\| SvTYPE(SvRV(aref)) != SVt_PVAV)
		50
551	1		croak("First argument must be an array reference");
552
553	411		av = (AV*)SvRV(aref);
554	411		size = av_len(av) + 1;
555
556	411	100	if (size == 0) {
557	1		SETs(&PL_sv_undef);
558	1		RETURN;
559			}
560
561	410		arr = AvARRAY(av);
562	410		result = arr[0];
563
564	410	100	if (size > 1) {
565	8		arr[0] = arr[size - 1];
566	8		AvFILLp(av) = size - 2;
567	8		raw_sift_down_max(aTHX_ av, 0, size - 1);
568			} else {
569	402		AvFILLp(av) = -1;
570			}
571
572	410		SETs(sv_2mortal(result));
573	410		RETURN;
574			}
575
576			/* pp_make_heap_min: UNOP(\@array) */
577	414		static OP* pp_make_heap_min(pTHX) {
578	414		dSP;
579	414		SV *aref = TOPs;
580			AV *av;
581			IV size, i;
582
583	414	100	if (!SvROK(aref) \|\| SvTYPE(SvRV(aref)) != SVt_PVAV)
		50
584	1		croak("First argument must be an array reference");
585
586	413		av = (AV*)SvRV(aref);
587	413		size = av_len(av) + 1;
588
589	2131	100	for (i = (size >> 1) - 1; i >= 0; i--) {
590	1718		raw_sift_down_min(aTHX_ av, i, size);
591			}
592
593	413		SETs(&PL_sv_undef);
594	413		RETURN;
595			}
596
597			/* pp_make_heap_max: UNOP(\@array) */
598	406		static OP* pp_make_heap_max(pTHX) {
599	406		dSP;
600	406		SV *aref = TOPs;
601			AV *av;
602			IV size, i;
603
604	406	50	if (!SvROK(aref) \|\| SvTYPE(SvRV(aref)) != SVt_PVAV)
		100
605	1		croak("First argument must be an array reference");
606
607	405		av = (AV*)SvRV(aref);
608	405		size = av_len(av) + 1;
609
610	1612	100	for (i = (size >> 1) - 1; i >= 0; i--) {
611	1207		raw_sift_down_max(aTHX_ av, i, size);
612			}
613
614	405		SETs(&PL_sv_undef);
615	405		RETURN;
616			}
617
618			/* ============================================
619			PART 2: NUMERIC HEAP (stores NV directly)
620			============================================ */
621
622	5483		PERL_STATIC_INLINE void nv_ensure_capacity(NumericHeap *h, IV needed) {
623	5483	100	if (needed > h->capacity) {
624	15	50	IV new_cap = h->capacity ? h->capacity * 2 : 16;
625	20	100	while (new_cap < needed) new_cap *= 2;
626	15	50	Renew(h->data, new_cap, NV);
627	15		h->capacity = new_cap;
628			}
629	5483		}
630
631			/* Sift up for NV min-heap */
632	4252		static void nv_sift_up_min(NumericHeap *h, IV idx) {
633	4252		NV *data = h->data;
634	4252		NV val = data[idx];
635
636	5611	100	while (idx > 0) {
637	4297		IV parent = (idx - 1) >> 1;
638	4297	100	if (val < data[parent]) {
639	1359		data[idx] = data[parent];
640	1359		idx = parent;
641			} else {
642	2938		break;
643			}
644			}
645	4252		data[idx] = val;
646	4252		}
647
648			/* Sift up for NV max-heap */
649	2047		static void nv_sift_up_max(NumericHeap *h, IV idx) {
650	2047		NV *data = h->data;
651	2047		NV val = data[idx];
652
653	4510	100	while (idx > 0) {
654	3470		IV parent = (idx - 1) >> 1;
655	3470	100	if (val > data[parent]) {
656	2463		data[idx] = data[parent];
657	2463		idx = parent;
658			} else {
659	1007		break;
660			}
661			}
662	2047		data[idx] = val;
663	2047		}
664
665			/* Sift down for NV min-heap */
666	1662		static void nv_sift_down_min(NumericHeap *h, IV idx) {
667	1662		NV *data = h->data;
668	1662		IV size = h->size;
669	1662		NV val = data[idx];
670	1662		IV half = size >> 1;
671
672	9964	100	while (idx < half) {
673	8687		IV left = (idx << 1) + 1;
674	8687		IV right = left + 1;
675	8687		IV best = left;
676	8687		NV best_nv = data[left];
677
678	8687	100	if (right < size && data[right] < best_nv) {
		100
679	4188		best = right;
680	4188		best_nv = data[right];
681			}
682
683	8687	100	if (best_nv < val) {
684	8302		data[idx] = data[best];
685	8302		idx = best;
686			} else {
687	385		break;
688			}
689			}
690	1662		data[idx] = val;
691	1662		}
692
693			/* Sift down for NV max-heap */
694	1819		static void nv_sift_down_max(NumericHeap *h, IV idx) {
695	1819		NV *data = h->data;
696	1819		IV size = h->size;
697	1819		NV val = data[idx];
698	1819		IV half = size >> 1;
699
700	9570	100	while (idx < half) {
701	8318		IV left = (idx << 1) + 1;
702	8318		IV right = left + 1;
703	8318		IV best = left;
704	8318		NV best_nv = data[left];
705
706	8318	100	if (right < size && data[right] > best_nv) {
		100
707	3714		best = right;
708	3714		best_nv = data[right];
709			}
710
711	8318	100	if (best_nv > val) {
712	7751		data[idx] = data[best];
713	7751		idx = best;
714			} else {
715	567		break;
716			}
717			}
718	1819		data[idx] = val;
719	1819		}
720
721	271		static int numeric_heap_free(pTHX_ SV sv, MAGIC mg) {
722	271		NumericHeap h = (NumericHeap)mg->mg_ptr;
723			PERL_UNUSED_ARG(sv);
724	271	50	if (h->data) Safefree(h->data);
725	271		Safefree(h);
726	271		return 0;
727			}
728
729			/* heap::new_nv($type) - create numeric heap */
730	271		XS_EXTERNAL(XS_heap_new_nv) {
731	271		dXSARGS;
732			NumericHeap *h;
733			SV obj_sv, rv;
734			HV *stash;
735	271		HeapType type = HEAP_MIN;
736	271		int arg_offset = 0;
737
738	271	100	if (items >= 1 && SvPOK(ST(0))) {
		50
739			STRLEN len;
740	270		const char *str = SvPV(ST(0), len);
741	270	50	if (len == 8 && strEQ(str, "Heap::PQ")) {
		0
742	0		arg_offset = 1;
743	270	50	} else if (len == 3 && (strEQ(str, "min") \|\| strEQ(str, "max"))) {
		100
		50
744	270		arg_offset = 0;
745			} else {
746	0		arg_offset = 1;
747			}
748			}
749
750	271	100	if (items > arg_offset) {
751			STRLEN len;
752	270		const char *type_str = SvPV(ST(arg_offset), len);
753	270	50	if (len == 3 && strEQ(type_str, "max")) {
		100
754	210		type = HEAP_MAX;
755			}
756			}
757
758	271		Newxz(h, 1, NumericHeap);
759	271		h->type = type;
760	271		h->size = 0;
761	271		h->capacity = 16;
762	271		Newx(h->data, 16, NV);
763
764	271		obj_sv = newSV(0);
765	271		sv_magicext(obj_sv, NULL, PERL_MAGIC_ext, &numeric_heap_vtbl, (char*)h, 0);
766
767	271		rv = newRV_noinc(obj_sv);
768	271		stash = gv_stashpvn("Heap::PQ::nv", 12, GV_ADD);
769	271		sv_bless(rv, stash);
770
771	271		ST(0) = sv_2mortal(rv);
772	271		XSRETURN(1);
773			}
774
775			/* $nv_heap->push($value) */
776	5268		XS_EXTERNAL(XS_nv_push) {
777	5268		dXSARGS;
778			NumericHeap *h;
779			NV val;
780
781	5268	50	if (items != 2) croak("Usage: $heap->push($value)");
782
783	5268		h = NV_HEAP_FAST(ST(0));
784	5268		val = SvNV(ST(1));
785
786	5268		nv_ensure_capacity(h, h->size + 1);
787	5268		h->data[h->size] = val;
788	5268		h->size++;
789
790	5268	100	if (h->type == HEAP_MIN) {
791	4224		nv_sift_up_min(h, h->size - 1);
792			} else {
793	1044		nv_sift_up_max(h, h->size - 1);
794			}
795
796	5268		ST(0) = ST(0);
797	5268		XSRETURN(1);
798			}
799
800			/* $nv_heap->push_all(@values) - with Floyd's heapify */
801	206		XS_EXTERNAL(XS_nv_push_all) {
802	206		dXSARGS;
803			NumericHeap *h;
804			int i;
805			IV start_size;
806
807	206	50	if (items < 1) croak("Usage: $heap->push_all(@values)");
808
809	206		h = NV_HEAP_FAST(ST(0));
810	206		start_size = h->size;
811
812	206		nv_ensure_capacity(h, h->size + items - 1);
813
814			/* Add all values first */
815	2228	100	for (i = 1; i < items; i++) {
816	2022		h->data[h->size++] = SvNV(ST(i));
817			}
818
819			/* Floyd's heapify on the new portion if significant */
820	206	100	if (items - 1 > 10) {
821			/* Full Floyd's heapify */
822			IV j;
823	501	100	for (j = (h->size >> 1) - 1; j >= 0; j--) {
824	500	50	if (h->type == HEAP_MIN) {
825	500		nv_sift_down_min(h, j);
826			} else {
827	0		nv_sift_down_max(h, j);
828			}
829			}
830			} else {
831			/* Just sift up each new element */
832	1227	100	for (i = start_size; i < h->size; i++) {
833	1022	100	if (h->type == HEAP_MIN) {
834	22		nv_sift_up_min(h, i);
835			} else {
836	1000		nv_sift_up_max(h, i);
837			}
838			}
839			}
840
841	206		ST(0) = ST(0);
842	206		XSRETURN(1);
843			}
844
845			/* $nv_heap->pop() */
846	4174		XS_EXTERNAL(XS_nv_pop) {
847	4174		dXSARGS;
848			NumericHeap *h;
849			NV result;
850
851	4174	50	if (items != 1) croak("Usage: $heap->pop()");
852
853	4174		h = NV_HEAP_FAST(ST(0));
854
855	4174	100	if (h->size == 0) XSRETURN_UNDEF;
856
857	4169		result = h->data[0];
858	4169		h->size--;
859
860	4169	100	if (h->size > 0) {
861	2937		h->data[0] = h->data[h->size];
862	2937	100	if (h->type == HEAP_MIN) {
863	1127		nv_sift_down_min(h, 0);
864			} else {
865	1810		nv_sift_down_max(h, 0);
866			}
867			}
868
869	4169		ST(0) = sv_2mortal(newSVnv(result));
870	4169		XSRETURN(1);
871			}
872
873			/* $nv_heap->peek() */
874	1016		XS_EXTERNAL(XS_nv_peek) {
875	1016		dXSARGS;
876			NumericHeap *h;
877
878	1016	50	if (items != 1) croak("Usage: $heap->peek()");
879
880	1016		h = NV_HEAP_FAST(ST(0));
881
882	1016	100	if (h->size == 0) XSRETURN_UNDEF;
883
884	1014		ST(0) = sv_2mortal(newSVnv(h->data[0]));
885	1014		XSRETURN(1);
886			}
887
888			/* $nv_heap->size() */
889	1025		XS_EXTERNAL(XS_nv_size) {
890	1025		dXSARGS;
891			NumericHeap *h;
892
893	1025	50	if (items != 1) croak("Usage: $heap->size()");
894
895	1025		h = NV_HEAP_FAST(ST(0));
896	1025		XSRETURN_IV(h->size);
897			}
898
899			/* $nv_heap->is_empty() */
900	3295		XS_EXTERNAL(XS_nv_is_empty) {
901	3295		dXSARGS;
902			NumericHeap *h;
903
904	3295	50	if (items != 1) croak("Usage: $heap->is_empty()");
905
906	3295		h = NV_HEAP_FAST(ST(0));
907
908	3295	100	if (h->size == 0) XSRETURN_YES;
909	3075		XSRETURN_NO;
910			}
911
912			/* $nv_heap->clear() */
913	203		XS_EXTERNAL(XS_nv_clear) {
914	203		dXSARGS;
915			NumericHeap *h;
916
917	203	50	if (items != 1) croak("Usage: $heap->clear()");
918
919	203		h = NV_HEAP_FAST(ST(0));
920	203		h->size = 0;
921
922	203		XSRETURN_EMPTY;
923			}
924
925			/* $nv_heap->peek_n($n) - return top N elements in sorted order without removing */
926	6		XS_EXTERNAL(XS_nv_peek_n) {
927	6		dXSARGS;
928			NumericHeap *h;
929			IV n, i, count;
930			NV *saved;
931
932	6	50	if (items != 2) croak("Usage: $heap->peek_n($n)");
933
934	6		h = NV_HEAP_FAST(ST(0));
935	6		n = SvIV(ST(1));
936
937	6	50	if (n <= 0 \|\| h->size == 0) XSRETURN_EMPTY;
		100
938	5	100	if (n > h->size) n = h->size;
939
940			/* Save the original state */
941	5	50	Newx(saved, h->size, NV);
942	5	50	Copy(h->data, saved, h->size, NV);
943	5		IV saved_size = h->size;
944
945			/* Pop n elements */
946	5	50	EXTEND(SP, n);
		50
947	24	100	for (i = 0; i < n; i++) {
948	19		NV val = h->data[0];
949	19		h->size--;
950	19	100	if (h->size > 0) {
951	18		h->data[0] = h->data[h->size];
952	18	100	if (h->type == HEAP_MIN)
953	16		nv_sift_down_min(h, 0);
954			else
955	2		nv_sift_down_max(h, 0);
956			}
957	19		ST(i) = sv_2mortal(newSVnv(val));
958			}
959	5		count = n;
960
961			/* Restore original state */
962	5	50	Copy(saved, h->data, saved_size, NV);
963	5		h->size = saved_size;
964	5		Safefree(saved);
965
966	5		XSRETURN(count);
967			}
968
969			/* $nv_heap->search(sub { ... }) - find NV elements matching condition */
970	4		XS_EXTERNAL(XS_nv_search) {
971	4		dXSARGS;
972			NumericHeap *h;
973	4		IV i, found = 0;
974			SV *callback;
975			NV *results;
976
977	4	50	if (items != 2) croak("Usage: $heap->search(sub { ... })");
978
979	4		h = NV_HEAP_FAST(ST(0));
980	4		callback = ST(1);
981
982	4	50	if (!SvROK(callback) \|\| SvTYPE(SvRV(callback)) != SVt_PVCV)
		100
983	1		croak("search requires a code reference");
984
985	3	100	if (h->size == 0) XSRETURN_EMPTY;
986
987	2	50	Newx(results, h->size, NV);
988
989	10	100	for (i = 0; i < h->size; i++) {
990	8		dSP;
991	8		SV *elem = sv_2mortal(newSVnv(h->data[i]));
992			IV result;
993			int count;
994
995	8		ENTER; SAVETMPS;
996	8		SAVE_DEFSV;
997	8		DEFSV_set(elem);
998
999	8	50	PUSHMARK(SP);
1000	8	50	XPUSHs(elem);
1001	8		PUTBACK;
1002
1003	8		count = call_sv(callback, G_SCALAR);
1004	8		SPAGAIN;
1005	8	50	result = count > 0 ? SvTRUE(TOPs) : 0;
1006	8	50	if (count > 0) POPs;
1007	8		PUTBACK;
1008	8	50	FREETMPS; LEAVE;
1009
1010	8	100	if (result) {
1011	2		results[found++] = h->data[i];
1012			}
1013			}
1014
1015	2	50	EXTEND(SP, found);
		50
1016	4	100	for (i = 0; i < found; i++) {
1017	2		ST(i) = sv_2mortal(newSVnv(results[i]));
1018			}
1019	2		Safefree(results);
1020	2		XSRETURN(found);
1021			}
1022
1023			/* $nv_heap->delete(sub { ... }) - remove matching NV elements, returns count */
1024	5		XS_EXTERNAL(XS_nv_delete) {
1025	5		dXSARGS;
1026			NumericHeap *h;
1027	5		IV i, write_pos = 0, deleted = 0;
1028			SV *callback;
1029
1030	5	50	if (items != 2) croak("Usage: $heap->delete(sub { ... })");
1031
1032	5		h = NV_HEAP_FAST(ST(0));
1033	5		callback = ST(1);
1034
1035	5	50	if (!SvROK(callback) \|\| SvTYPE(SvRV(callback)) != SVt_PVCV)
		100
1036	1		croak("delete requires a code reference");
1037
1038	28	100	for (i = 0; i < h->size; i++) {
1039	24		dSP;
1040	24		SV *elem = sv_2mortal(newSVnv(h->data[i]));
1041			IV result;
1042			int count;
1043
1044	24		ENTER; SAVETMPS;
1045	24		SAVE_DEFSV;
1046	24		DEFSV_set(elem);
1047
1048	24	50	PUSHMARK(SP);
1049	24	50	XPUSHs(elem);
1050	24		PUTBACK;
1051
1052	24		count = call_sv(callback, G_SCALAR);
1053	24		SPAGAIN;
1054	24	50	result = count > 0 ? SvTRUE(TOPs) : 0;
1055	24	50	if (count > 0) POPs;
1056	24		PUTBACK;
1057	24	50	FREETMPS; LEAVE;
1058
1059	24	100	if (result) {
1060	12		deleted++;
1061			} else {
1062	12	100	if (write_pos != i) {
1063	3		h->data[write_pos] = h->data[i];
1064			}
1065	12		write_pos++;
1066			}
1067			}
1068
1069	4		h->size = write_pos;
1070
1071			/* Rebuild heap with Floyd's heapify */
1072	4	50	if (deleted > 0 && h->size > 1) {
		100
1073			IV j;
1074	8	100	for (j = (h->size >> 1) - 1; j >= 0; j--) {
1075	5	100	if (h->type == HEAP_MIN)
1076	3		nv_sift_down_min(h, j);
1077			else
1078	2		nv_sift_down_max(h, j);
1079			}
1080			}
1081
1082	4		XSRETURN_IV(deleted);
1083			}
1084
1085			/* ============================================
1086			PART 3: STANDARD HEAP (original OO API)
1087			============================================ */
1088
1089	5777		PERL_STATIC_INLINE void heap_ensure_capacity(Heap *h, IV needed) {
1090	5777	100	if (needed > h->capacity) {
1091	14	50	IV new_cap = h->capacity ? h->capacity * 2 : 16;
1092	14	50	while (new_cap < needed) new_cap *= 2;
1093	14	50	Renew(h->data, new_cap, SV*);
1094	14	50	Renew(h->priorities, new_cap, NV);
1095	14		h->capacity = new_cap;
1096			}
1097	5777		}
1098
1099			/* Sift functions for standard heap */
1100	4555		static void heap_sift_up_min(pTHX_ Heap *h, IV idx) {
1101	4555		SV **data = h->data;
1102	4555		NV *prio = h->priorities;
1103	4555		SV *val = data[idx];
1104	4555		NV val_nv = prio[idx];
1105			PERL_UNUSED_CONTEXT;
1106
1107	5939	100	while (idx > 0) {
1108	2758		IV parent = (idx - 1) >> 1;
1109	2758	100	if (val_nv < prio[parent]) {
1110	1384		data[idx] = data[parent];
1111	1384		prio[idx] = prio[parent];
1112	1384		idx = parent;
1113			} else {
1114	1374		break;
1115			}
1116			}
1117	4555		data[idx] = val;
1118	4555		prio[idx] = val_nv;
1119	4555		}
1120
1121	49		static void heap_sift_up_max(pTHX_ Heap *h, IV idx) {
1122	49		SV **data = h->data;
1123	49		NV *prio = h->priorities;
1124	49		SV *val = data[idx];
1125	49		NV val_nv = prio[idx];
1126			PERL_UNUSED_CONTEXT;
1127
1128	70	100	while (idx > 0) {
1129	49		IV parent = (idx - 1) >> 1;
1130	49	100	if (val_nv > prio[parent]) {
1131	21		data[idx] = data[parent];
1132	21		prio[idx] = prio[parent];
1133	21		idx = parent;
1134			} else {
1135	28		break;
1136			}
1137			}
1138	49		data[idx] = val;
1139	49		prio[idx] = val_nv;
1140	49		}
1141
1142	1295		static void heap_sift_down_min(pTHX_ Heap *h, IV idx) {
1143	1295		SV **data = h->data;
1144	1295		NV *prio = h->priorities;
1145	1295		IV size = h->size;
1146	1295		SV *val = data[idx];
1147	1295		NV val_nv = prio[idx];
1148	1295		IV half = size >> 1;
1149			PERL_UNUSED_CONTEXT;
1150
1151	9180	100	while (idx < half) {
1152	8124		IV left = (idx << 1) + 1;
1153	8124		IV right = left + 1;
1154	8124		IV best = left;
1155	8124		NV best_nv = prio[left];
1156
1157	8124	100	if (right < size) {
1158	8027		NV right_nv = prio[right];
1159	8027	100	if (right_nv < best_nv) {
1160	3917		best = right;
1161	3917		best_nv = right_nv;
1162			}
1163			}
1164
1165	8124	100	if (best_nv < val_nv) {
1166	7885		data[idx] = data[best];
1167	7885		prio[idx] = prio[best];
1168	7885		idx = best;
1169			} else {
1170	239		break;
1171			}
1172			}
1173	1295		data[idx] = val;
1174	1295		prio[idx] = val_nv;
1175	1295		}
1176
1177	28		static void heap_sift_down_max(pTHX_ Heap *h, IV idx) {
1178	28		SV **data = h->data;
1179	28		NV *prio = h->priorities;
1180	28		IV size = h->size;
1181	28		SV *val = data[idx];
1182	28		NV val_nv = prio[idx];
1183	28		IV half = size >> 1;
1184			PERL_UNUSED_CONTEXT;
1185
1186	45	100	while (idx < half) {
1187	24		IV left = (idx << 1) + 1;
1188	24		IV right = left + 1;
1189	24		IV best = left;
1190	24		NV best_nv = prio[left];
1191
1192	24	100	if (right < size) {
1193	15		NV right_nv = prio[right];
1194	15	100	if (right_nv > best_nv) {
1195	8		best = right;
1196	8		best_nv = right_nv;
1197			}
1198			}
1199
1200	24	100	if (best_nv > val_nv) {
1201	17		data[idx] = data[best];
1202	17		prio[idx] = prio[best];
1203	17		idx = best;
1204			} else {
1205	7		break;
1206			}
1207			}
1208	28		data[idx] = val;
1209	28		prio[idx] = val_nv;
1210	28		}
1211
1212			/* Custom comparator sift operations */
1213	4656		static bool heap_compare_custom(pTHX_ Heap h, SV a, SV *b) {
1214	4656		dSP;
1215			IV result;
1216			int count;
1217
1218	4656		ENTER; SAVETMPS;
1219	4656	50	PUSHMARK(SP);
1220	4656	50	XPUSHs(a);
1221	4656	50	XPUSHs(b);
1222	4656		PUTBACK;
1223
1224	4656		count = call_sv(h->comparator, G_SCALAR);
1225
1226	4656		SPAGAIN;
1227	4656	50	if (count != 1) croak("Comparator must return exactly one value");
1228	4656		result = POPi;
1229	4656		PUTBACK;
1230	4656	50	FREETMPS; LEAVE;
1231
1232	4656	100	return h->type == HEAP_MIN ? result < 0 : result > 0;
1233			}
1234
1235	1190		static void heap_sift_up_custom(pTHX_ Heap *h, IV idx) {
1236	1315	100	while (idx > 0) {
1237	1162		IV parent = (idx - 1) >> 1;
1238	1162	100	if (heap_compare_custom(aTHX_ h, h->data[idx], h->data[parent])) {
1239	125		SV *tmp = h->data[idx];
1240	125		h->data[idx] = h->data[parent];
1241	125		h->data[parent] = tmp;
1242	125		idx = parent;
1243			} else {
1244	1037		break;
1245			}
1246			}
1247	1190		}
1248
1249	1049		static void heap_sift_down_custom(pTHX_ Heap *h, IV idx) {
1250	1628		while (1) {
1251	2677		IV left = (idx << 1) + 1;
1252	2677		IV right = left + 1;
1253	2677		IV best = idx;
1254
1255	2677	100	if (left < h->size && heap_compare_custom(aTHX_ h, h->data[left], h->data[best])) {
		100
1256	1606		best = left;
1257			}
1258	2677	100	if (right < h->size && heap_compare_custom(aTHX_ h, h->data[right], h->data[best])) {
		100
1259	494		best = right;
1260			}
1261
1262	2677	100	if (best != idx) {
1263	1628		SV *tmp = h->data[idx];
1264	1628		h->data[idx] = h->data[best];
1265	1628		h->data[best] = tmp;
1266	1628		idx = best;
1267			} else {
1268	1049		break;
1269			}
1270			}
1271	1049		}
1272
1273	260		static int heap_free(pTHX_ SV sv, MAGIC mg) {
1274	260		Heap h = (Heap)mg->mg_ptr;
1275			PERL_UNUSED_ARG(sv);
1276
1277	260	50	if (!PL_dirty) {
1278			IV i;
1279	508	100	for (i = 0; i < h->size; i++) {
1280	248	50	if (h->data[i]) SvREFCNT_dec(h->data[i]);
1281			}
1282	260	100	if (h->comparator) SvREFCNT_dec(h->comparator);
1283			}
1284	260	50	if (h->data) Safefree(h->data);
1285	260	50	if (h->priorities) Safefree(h->priorities);
1286	260		Safefree(h);
1287	260		return 0;
1288			}
1289
1290			/* Function-style custom ops */
1291
1292			/* Dedicated NV heap custom ops - no find_heap, no SV allocation */
1293	9		static OP* pp_nv_push(pTHX) {
1294	9		dSP;
1295	9		NV val = SvNV(TOPs);
1296	9		SV *heap_sv = TOPm1s;
1297	9		NumericHeap *nh = NV_HEAP_FAST(heap_sv);
1298
1299	9		nv_ensure_capacity(nh, nh->size + 1);
1300	9		nh->data[nh->size] = val;
1301	9		nh->size++;
1302	9	100	if (nh->type == HEAP_MIN) {
1303	6		nv_sift_up_min(nh, nh->size - 1);
1304			} else {
1305	3		nv_sift_up_max(nh, nh->size - 1);
1306			}
1307	9		SP--;
1308	9		SETs(heap_sv);
1309	9		RETURN;
1310			}
1311
1312	11		static OP* pp_nv_pop(pTHX) {
1313	11		dSP;
1314	11		dTARGET;
1315	11		NumericHeap *nh = NV_HEAP_FAST(TOPs);
1316
1317	11	100	if (nh->size == 0) {
1318	1		SETs(&PL_sv_undef);
1319	1		RETURN;
1320			}
1321	10		NV result = nh->data[0];
1322	10		nh->size--;
1323	10	100	if (nh->size > 0) {
1324	8		nh->data[0] = nh->data[nh->size];
1325	8	100	if (nh->type == HEAP_MIN) {
1326	6		nv_sift_down_min(nh, 0);
1327			} else {
1328	2		nv_sift_down_max(nh, 0);
1329			}
1330			}
1331	10	50	SETn(result);
1332	10		RETURN;
1333			}
1334
1335	6		static OP* pp_nv_peek(pTHX) {
1336	6		dSP;
1337	6		dTARGET;
1338	6		NumericHeap *nh = NV_HEAP_FAST(TOPs);
1339
1340	6	100	if (nh->size == 0) {
1341	1		SETs(&PL_sv_undef);
1342	1		RETURN;
1343			}
1344	5	50	SETn(nh->data[0]);
1345	5		RETURN;
1346			}
1347
1348	5		static OP* pp_nv_size(pTHX) {
1349	5		dSP;
1350	5		dTARGET;
1351	5		NumericHeap *nh = NV_HEAP_FAST(TOPs);
1352	5	50	SETi(nh->size);
1353	5		RETURN;
1354			}
1355
1356	0		static OP* pp_nv_is_empty(pTHX) {
1357	0		dSP;
1358	0		NumericHeap *nh = NV_HEAP_FAST(TOPs);
1359	0	0	if (nh->size == 0) { SETs(&PL_sv_yes); }
1360	0		else { SETs(&PL_sv_no); }
1361	0		RETURN;
1362			}
1363
1364	0		static OP* pp_nv_clear(pTHX) {
1365	0		dSP;
1366	0		NumericHeap *nh = NV_HEAP_FAST(TOPs);
1367	0		nh->size = 0;
1368	0		SETs(&PL_sv_undef);
1369	0		RETURN;
1370			}
1371
1372	3		static OP* pp_nv_peek_n(pTHX) {
1373	3		dSP;
1374	3		IV n = SvIV(TOPs);
1375	3		NumericHeap *nh = NV_HEAP_FAST(TOPm1s);
1376			IV i;
1377
1378	3		SP -= 2;
1379
1380	3	50	if (n <= 0 \|\| nh->size == 0) RETURN;
		50
1381	3	50	if (n > nh->size) n = nh->size;
1382
1383			{
1384			NV *saved;
1385	3		IV saved_size = nh->size;
1386	3	50	Newx(saved, saved_size, NV);
1387	3	50	Copy(nh->data, saved, saved_size, NV);
1388
1389	3	50	EXTEND(SP, n);
		50
1390	11	100	for (i = 0; i < n; i++) {
1391	8		NV val = nh->data[0];
1392	8		nh->size--;
1393	8	50	if (nh->size > 0) {
1394	8		nh->data[0] = nh->data[nh->size];
1395	8	100	if (nh->type == HEAP_MIN) nv_sift_down_min(nh, 0);
1396	2		else nv_sift_down_max(nh, 0);
1397			}
1398	8		PUSHs(sv_2mortal(newSVnv(val)));
1399			}
1400
1401	3	50	Copy(saved, nh->data, saved_size, NV);
1402	3		nh->size = saved_size;
1403	3		Safefree(saved);
1404			}
1405	3		RETURN;
1406			}
1407
1408	4		static OP* pp_heap_func_peek_n(pTHX) {
1409	4		dSP;
1410	4		IV n = SvIV(TOPs);
1411	4		SV *heap_sv = TOPm1s;
1412	4		HeapLookup lookup = find_heap(aTHX_ heap_sv);
1413			IV i;
1414
1415	4		SP -= 2;
1416
1417	4	100	if (lookup.type == MAGIC_NUMERIC) {
1418	1		NumericHeap *nh = lookup.ptr.nheap;
1419	1	50	if (n <= 0 \|\| nh->size == 0) RETURN;
		50
1420	1	50	if (n > nh->size) n = nh->size;
1421
1422			{
1423			NV *saved;
1424	1		IV saved_size = nh->size;
1425	1	50	Newx(saved, saved_size, NV);
1426	1	50	Copy(nh->data, saved, saved_size, NV);
1427
1428	1	50	EXTEND(SP, n);
		50
1429	3	100	for (i = 0; i < n; i++) {
1430	2		NV val = nh->data[0];
1431	2		nh->size--;
1432	2	50	if (nh->size > 0) {
1433	2		nh->data[0] = nh->data[nh->size];
1434	2	50	if (nh->type == HEAP_MIN) nv_sift_down_min(nh, 0);
1435	0		else nv_sift_down_max(nh, 0);
1436			}
1437	2		PUSHs(sv_2mortal(newSVnv(val)));
1438			}
1439
1440	1	50	Copy(saved, nh->data, saved_size, NV);
1441	1		nh->size = saved_size;
1442	1		Safefree(saved);
1443			}
1444	1		RETURN;
1445			}
1446
1447	3	50	if (lookup.type == MAGIC_HEAP) {
1448	3		Heap *h = lookup.ptr.heap;
1449	3	50	if (n <= 0 \|\| h->size == 0) RETURN;
		100
1450	2	50	if (n > h->size) n = h->size;
1451
1452			{
1453			SV **saved_data;
1454			NV *saved_pri;
1455	2		IV saved_size = h->size;
1456	2	50	Newx(saved_data, saved_size, SV*);
1457	2	50	Newx(saved_pri, saved_size, NV);
1458	2	50	Copy(h->data, saved_data, saved_size, SV*);
1459	2	50	Copy(h->priorities, saved_pri, saved_size, NV);
1460
1461	2	50	EXTEND(SP, n);
		50
1462	7	100	for (i = 0; i < n; i++) {
1463	5		PUSHs(h->data[0]);
1464	5		h->size--;
1465	5	50	if (h->size > 0) {
1466	5		h->data[0] = h->data[h->size];
1467	5		h->priorities[0] = h->priorities[h->size];
1468	5		h->sift_down(aTHX_ h, 0);
1469			}
1470			}
1471
1472	2	50	Copy(saved_data, h->data, saved_size, SV*);
1473	2	50	Copy(saved_pri, h->priorities, saved_size, NV);
1474	2		h->size = saved_size;
1475	2		Safefree(saved_data);
1476	2		Safefree(saved_pri);
1477			}
1478	2		RETURN;
1479			}
1480
1481	0		croak("Not a heap object");
1482			RETURN;
1483			}
1484
1485			/* Dedicated NV search custom op */
1486	1		static OP* pp_nv_search(pTHX) {
1487	1		dSP;
1488	1		SV *callback = TOPs;
1489	1		SV *heap_sv = TOPm1s;
1490	1		NumericHeap *nh = NV_HEAP_FAST(heap_sv);
1491	1		IV i, found = 0;
1492			NV *results;
1493
1494	1		SP -= 2;
1495
1496	1	50	if (!SvROK(callback) \|\| SvTYPE(SvRV(callback)) != SVt_PVCV)
		50
1497	0		croak("search requires a code reference");
1498
1499	1	50	if (nh->size == 0) RETURN;
1500
1501	1	50	Newx(results, nh->size, NV);
1502
1503	6	100	for (i = 0; i < nh->size; i++) {
1504	5		dSP;
1505	5		SV *elem = sv_2mortal(newSVnv(nh->data[i]));
1506			IV result;
1507			int count;
1508
1509	5		ENTER; SAVETMPS;
1510	5		SAVE_DEFSV;
1511	5		DEFSV_set(elem);
1512
1513	5	50	PUSHMARK(SP);
1514	5	50	XPUSHs(elem);
1515	5		PUTBACK;
1516
1517	5		count = call_sv(callback, G_SCALAR);
1518	5		SPAGAIN;
1519	5	50	result = count > 0 ? SvTRUE(TOPs) : 0;
1520	5	50	if (count > 0) POPs;
1521	5		PUTBACK;
1522	5	50	FREETMPS; LEAVE;
1523
1524	5	100	if (result) {
1525	3		results[found++] = nh->data[i];
1526			}
1527			}
1528
1529	1	50	EXTEND(SP, found);
		50
1530	4	100	for (i = 0; i < found; i++) {
1531	3		PUSHs(sv_2mortal(newSVnv(results[i])));
1532			}
1533	1		Safefree(results);
1534	1		RETURN;
1535			}
1536
1537			/* Dedicated NV delete custom op */
1538	1		static OP* pp_nv_delete(pTHX) {
1539	1		dSP;
1540	1		SV *callback = TOPs;
1541	1		SV *heap_sv = TOPm1s;
1542	1		NumericHeap *nh = NV_HEAP_FAST(heap_sv);
1543	1		IV i, write_pos = 0, deleted = 0;
1544	1		dTARGET;
1545
1546	1		SP -= 2;
1547
1548	1	50	if (!SvROK(callback) \|\| SvTYPE(SvRV(callback)) != SVt_PVCV)
		50
1549	0		croak("delete requires a code reference");
1550
1551	6	100	for (i = 0; i < nh->size; i++) {
1552	5		dSP;
1553	5		SV *elem = sv_2mortal(newSVnv(nh->data[i]));
1554			IV result;
1555			int count;
1556
1557	5		ENTER; SAVETMPS;
1558	5		SAVE_DEFSV;
1559	5		DEFSV_set(elem);
1560
1561	5	50	PUSHMARK(SP);
1562	5	50	XPUSHs(elem);
1563	5		PUTBACK;
1564
1565	5		count = call_sv(callback, G_SCALAR);
1566	5		SPAGAIN;
1567	5	50	result = count > 0 ? SvTRUE(TOPs) : 0;
1568	5	50	if (count > 0) POPs;
1569	5		PUTBACK;
1570	5	50	FREETMPS; LEAVE;
1571
1572	5	100	if (result) {
1573	2		deleted++;
1574			} else {
1575	3	100	if (write_pos != i) {
1576	1		nh->data[write_pos] = nh->data[i];
1577			}
1578	3		write_pos++;
1579			}
1580			}
1581
1582	1		nh->size = write_pos;
1583
1584	1	50	if (deleted > 0 && nh->size > 1) {
		50
1585			IV j;
1586	2	100	for (j = (nh->size >> 1) - 1; j >= 0; j--) {
1587	1	50	if (nh->type == HEAP_MIN)
1588	0		nv_sift_down_min(nh, j);
1589			else
1590	1		nv_sift_down_max(nh, j);
1591			}
1592			}
1593
1594	1	50	SETi(deleted);
1595	1		RETURN;
1596			}
1597
1598			/* Generic search custom op - dispatches to both heap types */
1599	3		static OP* pp_heap_func_search(pTHX) {
1600	3		dSP;
1601	3		SV *callback = TOPs;
1602	3		SV *heap_sv = TOPm1s;
1603	3		HeapLookup lookup = find_heap(aTHX_ heap_sv);
1604	3		IV i, found = 0;
1605
1606	3		SP -= 2;
1607
1608	3	50	if (!SvROK(callback) \|\| SvTYPE(SvRV(callback)) != SVt_PVCV)
		50
1609	0		croak("search requires a code reference");
1610
1611	3	100	if (lookup.type == MAGIC_NUMERIC) {
1612	1		NumericHeap *nh = lookup.ptr.nheap;
1613			NV *results;
1614
1615	1	50	if (nh->size == 0) RETURN;
1616
1617	1	50	Newx(results, nh->size, NV);
1618
1619	6	100	for (i = 0; i < nh->size; i++) {
1620	5		dSP;
1621	5		SV *elem = sv_2mortal(newSVnv(nh->data[i]));
1622			IV result;
1623			int count;
1624
1625	5		ENTER; SAVETMPS;
1626	5		SAVE_DEFSV;
1627	5		DEFSV_set(elem);
1628
1629	5	50	PUSHMARK(SP);
1630	5	50	XPUSHs(elem);
1631	5		PUTBACK;
1632
1633	5		count = call_sv(callback, G_SCALAR);
1634	5		SPAGAIN;
1635	5	50	result = count > 0 ? SvTRUE(TOPs) : 0;
1636	5	50	if (count > 0) POPs;
1637	5		PUTBACK;
1638	5	50	FREETMPS; LEAVE;
1639
1640	5	100	if (result) {
1641	2		results[found++] = nh->data[i];
1642			}
1643			}
1644
1645	1	50	EXTEND(SP, found);
		50
1646	3	100	for (i = 0; i < found; i++) {
1647	2		PUSHs(sv_2mortal(newSVnv(results[i])));
1648			}
1649	1		Safefree(results);
1650	1		RETURN;
1651			}
1652
1653	2	50	if (lookup.type == MAGIC_HEAP) {
1654	2		Heap *h = lookup.ptr.heap;
1655			SV **results;
1656
1657	2	100	if (h->size == 0) RETURN;
1658
1659	1	50	Newx(results, h->size, SV*);
1660
1661	9	100	for (i = 0; i < h->size; i++) {
1662	8		dSP;
1663			IV result;
1664			int count;
1665
1666	8		ENTER; SAVETMPS;
1667	8		SAVE_DEFSV;
1668	8		DEFSV_set(h->data[i]);
1669
1670	8	50	PUSHMARK(SP);
1671	8	50	XPUSHs(h->data[i]);
1672	8		PUTBACK;
1673
1674	8		count = call_sv(callback, G_SCALAR);
1675	8		SPAGAIN;
1676	8	50	result = count > 0 ? SvTRUE(TOPs) : 0;
1677	8	50	if (count > 0) POPs;
1678	8		PUTBACK;
1679	8	50	FREETMPS; LEAVE;
1680
1681	8	100	if (result) {
1682	3		results[found++] = h->data[i];
1683			}
1684			}
1685
1686	1	50	EXTEND(SP, found);
		50
1687	4	100	for (i = 0; i < found; i++) {
1688	3		PUSHs(results[i]);
1689			}
1690	1		Safefree(results);
1691	1		RETURN;
1692			}
1693
1694	0		croak("Not a heap object");
1695			RETURN;
1696			}
1697
1698			/* Generic delete custom op - dispatches to both heap types */
1699	3		static OP* pp_heap_func_delete(pTHX) {
1700	3		dSP;
1701	3		SV *callback = TOPs;
1702	3		SV *heap_sv = TOPm1s;
1703	3		HeapLookup lookup = find_heap(aTHX_ heap_sv);
1704	3		IV i, write_pos = 0, deleted = 0;
1705	3		dTARGET;
1706
1707	3		SP -= 2;
1708
1709	3	50	if (!SvROK(callback) \|\| SvTYPE(SvRV(callback)) != SVt_PVCV)
		50
1710	0		croak("delete requires a code reference");
1711
1712	3	100	if (lookup.type == MAGIC_NUMERIC) {
1713	1		NumericHeap *nh = lookup.ptr.nheap;
1714
1715	9	100	for (i = 0; i < nh->size; i++) {
1716	8		dSP;
1717	8		SV *elem = sv_2mortal(newSVnv(nh->data[i]));
1718			IV result;
1719			int count;
1720
1721	8		ENTER; SAVETMPS;
1722	8		SAVE_DEFSV;
1723	8		DEFSV_set(elem);
1724
1725	8	50	PUSHMARK(SP);
1726	8	50	XPUSHs(elem);
1727	8		PUTBACK;
1728
1729	8		count = call_sv(callback, G_SCALAR);
1730	8		SPAGAIN;
1731	8	50	result = count > 0 ? SvTRUE(TOPs) : 0;
1732	8	50	if (count > 0) POPs;
1733	8		PUTBACK;
1734	8	50	FREETMPS; LEAVE;
1735
1736	8	100	if (result) {
1737	3		deleted++;
1738			} else {
1739	5	100	if (write_pos != i) {
1740	2		nh->data[write_pos] = nh->data[i];
1741			}
1742	5		write_pos++;
1743			}
1744			}
1745
1746	1		nh->size = write_pos;
1747
1748	1	50	if (deleted > 0 && nh->size > 1) {
		50
1749			IV j;
1750	3	100	for (j = (nh->size >> 1) - 1; j >= 0; j--) {
1751	2	50	if (nh->type == HEAP_MIN)
1752	2		nv_sift_down_min(nh, j);
1753			else
1754	0		nv_sift_down_max(nh, j);
1755			}
1756			}
1757
1758	1	50	PUSHi(deleted);
1759	1		RETURN;
1760			}
1761
1762	2	50	if (lookup.type == MAGIC_HEAP) {
1763	2		Heap *h = lookup.ptr.heap;
1764
1765	10	100	for (i = 0; i < h->size; i++) {
1766	8		dSP;
1767			IV result;
1768			int count;
1769
1770	8		ENTER; SAVETMPS;
1771	8		SAVE_DEFSV;
1772	8		DEFSV_set(h->data[i]);
1773
1774	8	50	PUSHMARK(SP);
1775	8	50	XPUSHs(h->data[i]);
1776	8		PUTBACK;
1777
1778	8		count = call_sv(callback, G_SCALAR);
1779	8		SPAGAIN;
1780	8	50	result = count > 0 ? SvTRUE(TOPs) : 0;
1781	8	50	if (count > 0) POPs;
1782	8		PUTBACK;
1783	8	50	FREETMPS; LEAVE;
1784
1785	8	100	if (result) {
1786	3		SvREFCNT_dec(h->data[i]);
1787	3		deleted++;
1788			} else {
1789	5	100	if (write_pos != i) {
1790	2		h->data[write_pos] = h->data[i];
1791	2		h->priorities[write_pos] = h->priorities[i];
1792			}
1793	5		write_pos++;
1794			}
1795			}
1796
1797	2		h->size = write_pos;
1798
1799	2	100	if (deleted > 0 && h->size > 1) {
		50
1800			IV j;
1801	3	100	for (j = (h->size >> 1) - 1; j >= 0; j--) {
1802	2		h->sift_down(aTHX_ h, j);
1803			}
1804			}
1805
1806	2	50	PUSHi(deleted);
1807	2		RETURN;
1808			}
1809
1810	0		croak("Not a heap object");
1811			RETURN;
1812			}
1813
1814	1030		static OP* pp_heap_func_push(pTHX) {
1815	1030		dSP;
1816	1030		SV *val_sv = TOPs;
1817	1030		SV *heap_sv = TOPm1s;
1818	1030		HeapLookup lookup = find_heap(aTHX_ heap_sv);
1819
1820	1030	50	if (lookup.type == MAGIC_NUMERIC) {
1821	0		NumericHeap *nh = lookup.ptr.nheap;
1822	0		NV val = SvNV(val_sv);
1823	0		nv_ensure_capacity(nh, nh->size + 1);
1824	0		nh->data[nh->size] = val;
1825	0		nh->size++;
1826	0	0	if (nh->type == HEAP_MIN) {
1827	0		nv_sift_up_min(nh, nh->size - 1);
1828			} else {
1829	0		nv_sift_up_max(nh, nh->size - 1);
1830			}
1831	0		SP--;
1832	0		SETs(heap_sv);
1833	0		RETURN;
1834			}
1835
1836	1030	50	if (lookup.type == MAGIC_HEAP) {
1837	1030		Heap *h = lookup.ptr.heap;
1838			SV *value;
1839
1840	1030		heap_ensure_capacity(h, h->size + 1);
1841	1030	100	if (h->comparator) {
1842	3		value = newSVsv(val_sv);
1843	3		h->data[h->size] = value;
1844			} else {
1845	1027		NV prio = SvNV(val_sv);
1846	1027		value = newSVsv(val_sv);
1847	1027		h->data[h->size] = value;
1848	1027		h->priorities[h->size] = prio;
1849			}
1850	1030		h->size++;
1851	1030		h->sift_up(aTHX_ h, h->size - 1);
1852
1853	1030		SP--;
1854	1030		SETs(heap_sv);
1855	1030		RETURN;
1856			}
1857
1858	0		croak("Not a heap object");
1859			RETURN;
1860			}
1861
1862	1010		static OP* pp_heap_func_pop(pTHX) {
1863	1010		dSP;
1864	1010		SV *heap_sv = TOPs;
1865	1010		HeapLookup lookup = find_heap(aTHX_ heap_sv);
1866
1867	1010	50	if (lookup.type == MAGIC_NUMERIC) {
1868	0		NumericHeap *nh = lookup.ptr.nheap;
1869	0	0	if (nh->size == 0) {
1870	0		SETs(&PL_sv_undef);
1871	0		RETURN;
1872			}
1873	0		NV result = nh->data[0];
1874	0		nh->size--;
1875	0	0	if (nh->size > 0) {
1876	0		nh->data[0] = nh->data[nh->size];
1877	0	0	if (nh->type == HEAP_MIN) {
1878	0		nv_sift_down_min(nh, 0);
1879			} else {
1880	0		nv_sift_down_max(nh, 0);
1881			}
1882			}
1883	0		SETs(sv_2mortal(newSVnv(result)));
1884	0		RETURN;
1885			}
1886
1887	1010	50	if (lookup.type == MAGIC_HEAP) {
1888	1010		Heap *h = lookup.ptr.heap;
1889	1010	100	if (h->size == 0) {
1890	1		SETs(&PL_sv_undef);
1891	1		RETURN;
1892			}
1893	1009		SV *result = sv_2mortal(h->data[0]);
1894	1009		h->size--;
1895	1009	100	if (h->size > 0) {
1896	7		h->data[0] = h->data[h->size];
1897	7		h->priorities[0] = h->priorities[h->size];
1898	7		h->sift_down(aTHX_ h, 0);
1899			}
1900	1009		SETs(result);
1901	1009		RETURN;
1902			}
1903
1904	0		croak("Not a heap object");
1905			RETURN;
1906			}
1907
1908	1005		static OP* pp_heap_func_peek(pTHX) {
1909	1005		dSP;
1910	1005		SV *heap_sv = TOPs;
1911	1005		HeapLookup lookup = find_heap(aTHX_ heap_sv);
1912
1913	1005	50	if (lookup.type == MAGIC_NUMERIC) {
1914	0		NumericHeap *nh = lookup.ptr.nheap;
1915	0	0	SETs(nh->size > 0 ? sv_2mortal(newSVnv(nh->data[0])) : &PL_sv_undef);
1916	0		RETURN;
1917			}
1918
1919	1005	50	if (lookup.type == MAGIC_HEAP) {
1920	1005		Heap *h = lookup.ptr.heap;
1921	1005	100	SETs(h->size > 0 ? h->data[0] : &PL_sv_undef);
1922	1005		RETURN;
1923			}
1924
1925	0		croak("Not a heap object");
1926			RETURN;
1927			}
1928
1929	1008		static OP* pp_heap_func_size(pTHX) {
1930	1008		dSP;
1931	1008		SV *heap_sv = TOPs;
1932	1008		HeapLookup lookup = find_heap(aTHX_ heap_sv);
1933
1934	1008	50	if (lookup.type == MAGIC_NUMERIC) {
1935	0		SETs(sv_2mortal(newSViv(lookup.ptr.nheap->size)));
1936	0		RETURN;
1937			}
1938
1939	1008	50	if (lookup.type == MAGIC_HEAP) {
1940	1008		SETs(sv_2mortal(newSViv(lookup.ptr.heap->size)));
1941	1008		RETURN;
1942			}
1943
1944	0		croak("Not a heap object");
1945			RETURN;
1946			}
1947
1948	7		static OP* pp_heap_func_is_empty(pTHX) {
1949	7		dSP;
1950	7		SV *heap_sv = TOPs;
1951	7		HeapLookup lookup = find_heap(aTHX_ heap_sv);
1952
1953	7	100	if (lookup.type == MAGIC_NUMERIC) {
1954	3	100	if (lookup.ptr.nheap->size == 0) { SETs(&PL_sv_yes); }
1955	1		else { SETs(&PL_sv_no); }
1956	3		RETURN;
1957			}
1958
1959	4	50	if (lookup.type == MAGIC_HEAP) {
1960	4	100	if (lookup.ptr.heap->size == 0) { SETs(&PL_sv_yes); }
1961	1		else { SETs(&PL_sv_no); }
1962	4		RETURN;
1963			}
1964
1965	0		croak("Not a heap object");
1966			RETURN;
1967			}
1968
1969	2		static OP* pp_heap_func_clear(pTHX) {
1970	2		dSP;
1971	2		SV *heap_sv = TOPs;
1972	2		HeapLookup lookup = find_heap(aTHX_ heap_sv);
1973
1974	2	100	if (lookup.type == MAGIC_NUMERIC) {
1975	1		lookup.ptr.nheap->size = 0;
1976	1		SETs(&PL_sv_undef);
1977	1		RETURN;
1978			}
1979
1980	1	50	if (lookup.type == MAGIC_HEAP) {
1981	1		Heap *h = lookup.ptr.heap;
1982			IV i;
1983	6	100	for (i = 0; i < h->size; i++) {
1984	5	50	if (h->data[i]) SvREFCNT_dec(h->data[i]);
1985			}
1986	1		h->size = 0;
1987	1		SETs(&PL_sv_undef);
1988	1		RETURN;
1989			}
1990
1991	0		croak("Not a heap object");
1992			RETURN;
1993			}
1994
1995	3		static OP* pp_heap_func_type(pTHX) {
1996	3		dSP;
1997	3		SV *heap_sv = TOPs;
1998	3		HeapLookup lookup = find_heap(aTHX_ heap_sv);
1999
2000	3	100	if (lookup.type == MAGIC_NUMERIC) {
2001	1	50	if (lookup.ptr.nheap->type == HEAP_MIN)
2002	0		SETs(sv_2mortal(newSVpvn("min", 3)));
2003			else
2004	1		SETs(sv_2mortal(newSVpvn("max", 3)));
2005	1		RETURN;
2006			}
2007
2008	2	50	if (lookup.type == MAGIC_HEAP) {
2009	2	100	if (lookup.ptr.heap->type == HEAP_MIN)
2010	1		SETs(sv_2mortal(newSVpvn("min", 3)));
2011			else
2012	1		SETs(sv_2mortal(newSVpvn("max", 3)));
2013	2		RETURN;
2014			}
2015
2016	0		croak("Not a heap object");
2017			RETURN;
2018			}
2019
2020			/* Call checkers for function-style calls (Heap::PQ::push($h,$v) and imported heap_push($h,$v)) */
2021			typedef OP* (*heap_ppfunc)(pTHX);
2022
2023	101		static OP* heap_call_checker_1arg(pTHX_ OP entersubop, GV namegv, SV *ckobj) {
2024	101		heap_ppfunc ppfunc = (heap_ppfunc)SvIVX(ckobj);
2025			OP pushop, cvop, *heapop;
2026			OP *newop;
2027
2028			PERL_UNUSED_ARG(namegv);
2029
2030	101		pushop = cUNOPx(entersubop)->op_first;
2031	101	50	if (!OpHAS_SIBLING(pushop)) pushop = cUNOPx(pushop)->op_first;
2032
2033	101	50	heapop = OpSIBLING(pushop);
2034	101	50	if (!heapop) return entersubop;
2035
2036	101	50	cvop = OpSIBLING(heapop);
2037	101	50	if (!cvop) return entersubop;
2038	101	50	if (OpSIBLING(heapop) != cvop) return entersubop;
		50
2039
2040	101		OpMORESIB_set(pushop, cvop);
2041	101		OpLASTSIB_set(heapop, NULL);
2042
2043	101		newop = newUNOP(OP_CUSTOM, 0, heapop);
2044	101		newop->op_ppaddr = ppfunc;
2045	101		newop->op_targ = pad_alloc(OP_CUSTOM, SVs_PADTMP);
2046
2047	101		op_free(entersubop);
2048	101		return newop;
2049			}
2050
2051	66		static OP* heap_call_checker_2arg(pTHX_ OP entersubop, GV namegv, SV *ckobj) {
2052	66		heap_ppfunc ppfunc = (heap_ppfunc)SvIVX(ckobj);
2053			OP pushop, cvop, heapop, valop;
2054			OP *newop;
2055
2056			PERL_UNUSED_ARG(namegv);
2057
2058	66		pushop = cUNOPx(entersubop)->op_first;
2059	66	50	if (!OpHAS_SIBLING(pushop)) pushop = cUNOPx(pushop)->op_first;
2060
2061	66	50	heapop = OpSIBLING(pushop);
2062	66	50	if (!heapop) return entersubop;
2063
2064	66	50	valop = OpSIBLING(heapop);
2065	66	50	if (!valop) return entersubop;
2066
2067	66	50	cvop = OpSIBLING(valop);
2068	66	50	if (!cvop) return entersubop;
2069	66	50	if (OpSIBLING(valop) != cvop) return entersubop;
		50
2070
2071	66		OpMORESIB_set(pushop, cvop);
2072	66		OpLASTSIB_set(valop, NULL);
2073	66		OpLASTSIB_set(heapop, NULL);
2074
2075	66		newop = newBINOP(OP_CUSTOM, 0, heapop, valop);
2076	66		newop->op_ppaddr = ppfunc;
2077	66		newop->op_targ = pad_alloc(OP_CUSTOM, SVs_PADTMP);
2078
2079	66		op_free(entersubop);
2080	66		return newop;
2081			}
2082
2083			/* XS Functions */
2084	260		XS_EXTERNAL(XS_heap_new) {
2085	260		dXSARGS;
2086			Heap *h;
2087			SV obj_sv, rv;
2088			HV *stash;
2089	260		HeapType type = HEAP_MIN;
2090	260		SV *comparator = NULL;
2091	260		int arg_offset = 0;
2092
2093	260	100	if (items >= 1 && SvPOK(ST(0))) {
		50
2094			STRLEN len;
2095	243		const char *str = SvPV(ST(0), len);
2096	243	50	if (len == 8 && strEQ(str, "Heap::PQ")) {
		0
2097	0		arg_offset = 1;
2098	243	50	} else if (len == 3 && (strEQ(str, "min") \|\| strEQ(str, "max"))) {
		100
		50
2099	243		arg_offset = 0;
2100			} else {
2101	0		arg_offset = 1;
2102			}
2103			}
2104
2105	260	100	if (items > arg_offset) {
2106			STRLEN len;
2107	243		const char *type_str = SvPV(ST(arg_offset), len);
2108	243	50	if (len == 3 && strEQ(type_str, "max")) {
		100
2109	14		type = HEAP_MAX;
2110	229	50	} else if (len == 3 && strEQ(type_str, "min")) {
		50
2111	229		type = HEAP_MIN;
2112			} else {
2113	0		croak("heap type must be 'min' or 'max'");
2114			}
2115			}
2116
2117	260	100	if (items > arg_offset + 1) {
2118	130		SV *cmp_arg = ST(arg_offset + 1);
2119	130	50	if (SvROK(cmp_arg) && SvTYPE(SvRV(cmp_arg)) == SVt_PVCV) {
		50
2120	130		comparator = newSVsv(cmp_arg);
2121	0	0	} else if (SvOK(cmp_arg)) {
2122	0		croak("Comparator must be a code reference");
2123			}
2124			}
2125
2126	260		Newxz(h, 1, Heap);
2127	260		h->type = type;
2128	260		h->size = 0;
2129	260		h->capacity = 16;
2130	260		Newx(h->data, 16, SV*);
2131	260		Newx(h->priorities, 16, NV);
2132	260		h->comparator = comparator;
2133
2134	260	100	if (comparator) {
2135	130		h->sift_up = heap_sift_up_custom;
2136	130		h->sift_down = heap_sift_down_custom;
2137	130	100	} else if (type == HEAP_MIN) {
2138	118		h->sift_up = heap_sift_up_min;
2139	118		h->sift_down = heap_sift_down_min;
2140			} else {
2141	12		h->sift_up = heap_sift_up_max;
2142	12		h->sift_down = heap_sift_down_max;
2143			}
2144
2145	260		obj_sv = newSV(0);
2146	260		sv_magicext(obj_sv, NULL, PERL_MAGIC_ext, &heap_vtbl, (char*)h, 0);
2147
2148	260		rv = newRV_noinc(obj_sv);
2149	260		stash = gv_stashpvn("Heap::PQ", 8, GV_ADD);
2150	260		sv_bless(rv, stash);
2151
2152	260		ST(0) = sv_2mortal(rv);
2153	260		XSRETURN(1);
2154			}
2155
2156	4740		XS_EXTERNAL(XS_heap_push) {
2157	4740		dXSARGS;
2158			HeapLookup hl;
2159
2160	4740	50	if (items != 2) croak("Usage: $heap->push($value)");
2161
2162	4740		hl = find_heap(aTHX_ ST(0));
2163
2164	4740	50	if (hl.type == MAGIC_NUMERIC) {
2165	0		NumericHeap *nh = hl.ptr.nheap;
2166	0		NV val = SvNV(ST(1));
2167	0		nv_ensure_capacity(nh, nh->size + 1);
2168	0		nh->data[nh->size] = val;
2169	0		nh->size++;
2170	0	0	if (nh->type == HEAP_MIN)
2171	0		nv_sift_up_min(nh, nh->size - 1);
2172			else
2173	0		nv_sift_up_max(nh, nh->size - 1);
2174	0		ST(0) = ST(0);
2175	0		XSRETURN(1);
2176			}
2177
2178			{
2179	4740		Heap *h = hl.ptr.heap;
2180	4740		SV *val_sv = ST(1);
2181			SV *value;
2182
2183	4740		heap_ensure_capacity(h, h->size + 1);
2184	4740	100	if (h->comparator) {
2185	1184		value = newSVsv(val_sv);
2186	1184		h->data[h->size] = value;
2187			} else {
2188	3556		NV prio = SvNV(val_sv);
2189	3556		value = newSVsv(val_sv);
2190	3556		h->data[h->size] = value;
2191	3556		h->priorities[h->size] = prio;
2192			}
2193	4740		h->size++;
2194	4740		h->sift_up(aTHX_ h, h->size - 1);
2195
2196	4740		ST(0) = ST(0);
2197	4740		XSRETURN(1);
2198			}
2199			}
2200
2201	7		XS_EXTERNAL(XS_heap_push_all) {
2202	7		dXSARGS;
2203			Heap *h;
2204			int i;
2205			IV start_size;
2206
2207	7	50	if (items < 1) croak("Usage: $heap->push_all(@values)");
2208
2209	7		h = get_heap(aTHX_ ST(0));
2210	7		start_size = h->size;
2211
2212	7		heap_ensure_capacity(h, h->size + items - 1);
2213
2214			/* Add all values first */
2215	31	100	for (i = 1; i < items; i++) {
2216	24		NV prio = SvNV(ST(i));
2217	24		SV *val = newSVsv(ST(i));
2218	24		h->data[h->size] = val;
2219	24	100	if (!h->comparator) h->priorities[h->size] = prio;
2220	24		h->size++;
2221			}
2222
2223			/* Floyd's heapify if adding many elements */
2224	7	50	if (items - 1 > 10) {
2225			IV j;
2226	0	0	for (j = (h->size >> 1) - 1; j >= 0; j--) {
2227	0		h->sift_down(aTHX_ h, j);
2228			}
2229			} else {
2230	31	100	for (i = start_size; i < h->size; i++) {
2231	24		h->sift_up(aTHX_ h, i);
2232			}
2233			}
2234
2235	7		ST(0) = ST(0);
2236	7		XSRETURN(1);
2237			}
2238
2239	4594		XS_EXTERNAL(XS_heap_pop) {
2240	4594		dXSARGS;
2241			HeapLookup hl;
2242
2243	4594	50	if (items != 1) croak("Usage: $heap->pop()");
2244
2245	4594		hl = find_heap(aTHX_ ST(0));
2246
2247	4594	50	if (hl.type == MAGIC_NUMERIC) {
2248	0		NumericHeap *nh = hl.ptr.nheap;
2249			NV result;
2250	0	0	if (nh->size == 0) XSRETURN_UNDEF;
2251	0		result = nh->data[0];
2252	0		nh->size--;
2253	0	0	if (nh->size > 0) {
2254	0		nh->data[0] = nh->data[nh->size];
2255	0	0	if (nh->type == HEAP_MIN)
2256	0		nv_sift_down_min(nh, 0);
2257			else
2258	0		nv_sift_down_max(nh, 0);
2259			}
2260	0		ST(0) = sv_2mortal(newSVnv(result));
2261	0		XSRETURN(1);
2262			}
2263
2264			{
2265	4594		Heap *h = hl.ptr.heap;
2266			SV *result;
2267
2268	4594	100	if (h->size == 0) XSRETURN_UNDEF;
2269
2270	4486		result = sv_2mortal(h->data[0]);
2271
2272	4486		h->size--;
2273	4486	100	if (h->size > 0) {
2274	2321		h->data[0] = h->data[h->size];
2275	2321		h->priorities[0] = h->priorities[h->size];
2276	2321		h->sift_down(aTHX_ h, 0);
2277			}
2278
2279	4486		ST(0) = result;
2280	4486		XSRETURN(1);
2281			}
2282			}
2283
2284	2042		XS_EXTERNAL(XS_heap_peek) {
2285	2042		dXSARGS;
2286			HeapLookup hl;
2287
2288	2042	50	if (items != 1) croak("Usage: $heap->peek()");
2289
2290	2042		hl = find_heap(aTHX_ ST(0));
2291
2292	2042	50	if (hl.type == MAGIC_NUMERIC) {
2293	0		NumericHeap *nh = hl.ptr.nheap;
2294	0	0	if (nh->size == 0) XSRETURN_UNDEF;
2295	0		ST(0) = sv_2mortal(newSVnv(nh->data[0]));
2296	0		XSRETURN(1);
2297			}
2298
2299			{
2300	2042		Heap *h = hl.ptr.heap;
2301	2042	100	if (h->size == 0) XSRETURN_UNDEF;
2302	2040		ST(0) = h->data[0];
2303	2040		XSRETURN(1);
2304			}
2305			}
2306
2307	2064		XS_EXTERNAL(XS_heap_size) {
2308	2064		dXSARGS;
2309			HeapLookup hl;
2310
2311	2064	50	if (items != 1) croak("Usage: $heap->size()");
2312
2313	2064		hl = find_heap(aTHX_ ST(0));
2314
2315	2064	50	if (hl.type == MAGIC_NUMERIC)
2316	0		XSRETURN_IV(hl.ptr.nheap->size);
2317
2318	2064		XSRETURN_IV(hl.ptr.heap->size);
2319			}
2320
2321	4344		XS_EXTERNAL(XS_heap_is_empty) {
2322	4344		dXSARGS;
2323			HeapLookup lookup;
2324
2325	4344	50	if (items != 1) croak("Usage: $heap->is_empty()");
2326
2327	4344		lookup = find_heap(aTHX_ ST(0));
2328
2329	4344	50	if (lookup.type == MAGIC_NUMERIC) {
2330	0	0	if (lookup.ptr.nheap->size == 0) XSRETURN_YES;
2331	0		XSRETURN_NO;
2332			}
2333	4344	50	if (lookup.type == MAGIC_HEAP) {
2334	4344	100	if (lookup.ptr.heap->size == 0) XSRETURN_YES;
2335	2213		XSRETURN_NO;
2336			}
2337	0		croak("Not a heap object");
2338			}
2339
2340	203		XS_EXTERNAL(XS_heap_clear) {
2341	203		dXSARGS;
2342			HeapLookup lookup;
2343
2344	203	50	if (items != 1) croak("Usage: $heap->clear()");
2345
2346	203		lookup = find_heap(aTHX_ ST(0));
2347
2348	203	50	if (lookup.type == MAGIC_NUMERIC) {
2349	0		lookup.ptr.nheap->size = 0;
2350	0		XSRETURN_EMPTY;
2351			}
2352	203	50	if (lookup.type == MAGIC_HEAP) {
2353	203		Heap *h = lookup.ptr.heap;
2354			IV i;
2355	228	100	for (i = 0; i < h->size; i++) {
2356	25	50	if (h->data[i]) SvREFCNT_dec(h->data[i]);
2357			}
2358	203		h->size = 0;
2359	203		XSRETURN_EMPTY;
2360			}
2361	0		croak("Not a heap object");
2362			}
2363
2364	4		XS_EXTERNAL(XS_heap_type) {
2365	4		dXSARGS;
2366			HeapLookup lookup;
2367			HeapType type;
2368
2369	4	50	if (items != 1) croak("Usage: $heap->type()");
2370
2371	4		lookup = find_heap(aTHX_ ST(0));
2372
2373	4	50	if (lookup.type == MAGIC_NUMERIC) {
2374	0		type = lookup.ptr.nheap->type;
2375	4	50	} else if (lookup.type == MAGIC_HEAP) {
2376	4		type = lookup.ptr.heap->type;
2377			} else {
2378	0		croak("Not a heap object");
2379			}
2380
2381	4	100	if (type == HEAP_MIN) {
2382	2		ST(0) = sv_2mortal(newSVpvn("min", 3));
2383			} else {
2384	2		ST(0) = sv_2mortal(newSVpvn("max", 3));
2385			}
2386	4		XSRETURN(1);
2387			}
2388
2389			/* $heap->peek_n($n) - return top N elements in sorted order without removing */
2390	13		XS_EXTERNAL(XS_heap_peek_n) {
2391	13		dXSARGS;
2392			HeapLookup hl;
2393			IV n, i, count;
2394
2395	13	50	if (items != 2) croak("Usage: $heap->peek_n($n)");
2396
2397	13		hl = find_heap(aTHX_ ST(0));
2398	13		n = SvIV(ST(1));
2399
2400	13	50	if (hl.type == MAGIC_NUMERIC) {
2401	0		NumericHeap *nh = hl.ptr.nheap;
2402			NV *saved;
2403			IV saved_size;
2404
2405	0	0	if (n <= 0 \|\| nh->size == 0) XSRETURN_EMPTY;
		0
2406	0	0	if (n > nh->size) n = nh->size;
2407
2408	0	0	Newx(saved, nh->size, NV);
2409	0	0	Copy(nh->data, saved, nh->size, NV);
2410	0		saved_size = nh->size;
2411
2412	0	0	EXTEND(SP, n);
		0
2413	0	0	for (i = 0; i < n; i++) {
2414	0		NV val = nh->data[0];
2415	0		nh->size--;
2416	0	0	if (nh->size > 0) {
2417	0		nh->data[0] = nh->data[nh->size];
2418	0	0	if (nh->type == HEAP_MIN)
2419	0		nv_sift_down_min(nh, 0);
2420			else
2421	0		nv_sift_down_max(nh, 0);
2422			}
2423	0		ST(i) = sv_2mortal(newSVnv(val));
2424			}
2425	0		count = n;
2426
2427	0	0	Copy(saved, nh->data, saved_size, NV);
2428	0		nh->size = saved_size;
2429	0		Safefree(saved);
2430	0		XSRETURN(count);
2431			}
2432
2433			{
2434	13		Heap *h = hl.ptr.heap;
2435			SV **saved_data;
2436			NV *saved_pri;
2437			IV saved_size;
2438
2439	13	100	if (n <= 0 \|\| h->size == 0) XSRETURN_EMPTY;
		100
2440	10	100	if (n > h->size) n = h->size;
2441
2442	10	50	Newx(saved_data, h->size, SV*);
2443	10	50	Newx(saved_pri, h->size, NV);
2444	10	50	Copy(h->data, saved_data, h->size, SV*);
2445	10	50	Copy(h->priorities, saved_pri, h->size, NV);
2446	10		saved_size = h->size;
2447
2448	10	50	EXTEND(SP, n);
		50
2449	38	100	for (i = 0; i < n; i++) {
2450	28		ST(i) = h->data[0];
2451	28		h->size--;
2452	28	100	if (h->size > 0) {
2453	26		h->data[0] = h->data[h->size];
2454	26		h->priorities[0] = h->priorities[h->size];
2455	26		h->sift_down(aTHX_ h, 0);
2456			}
2457			}
2458	10		count = n;
2459
2460	10	50	Copy(saved_data, h->data, saved_size, SV*);
2461	10	50	Copy(saved_pri, h->priorities, saved_size, NV);
2462	10		h->size = saved_size;
2463	10		Safefree(saved_data);
2464	10		Safefree(saved_pri);
2465	10		XSRETURN(count);
2466			}
2467			}
2468
2469			/* $heap->search(sub { ... }) - find elements matching condition */
2470	12		XS_EXTERNAL(XS_heap_search) {
2471	12		dXSARGS;
2472			HeapLookup hl;
2473	12		IV i, found = 0;
2474			SV *callback;
2475
2476	12	50	if (items != 2) croak("Usage: $heap->search(sub { ... })");
2477
2478	12		hl = find_heap(aTHX_ ST(0));
2479	12		callback = ST(1);
2480
2481	12	100	if (!SvROK(callback) \|\| SvTYPE(SvRV(callback)) != SVt_PVCV)
		50
2482	2		croak("search requires a code reference");
2483
2484	10	50	if (hl.type == MAGIC_NUMERIC) {
2485	0		NumericHeap *nh = hl.ptr.nheap;
2486			NV *results;
2487
2488	0	0	if (nh->size == 0) XSRETURN_EMPTY;
2489
2490	0	0	Newx(results, nh->size, NV);
2491
2492	0	0	for (i = 0; i < nh->size; i++) {
2493	0		dSP;
2494	0		SV *elem = sv_2mortal(newSVnv(nh->data[i]));
2495			IV result;
2496			int count;
2497
2498	0		ENTER; SAVETMPS;
2499	0		SAVE_DEFSV;
2500	0		DEFSV_set(elem);
2501
2502	0	0	PUSHMARK(SP);
2503	0	0	XPUSHs(elem);
2504	0		PUTBACK;
2505
2506	0		count = call_sv(callback, G_SCALAR);
2507	0		SPAGAIN;
2508	0	0	result = count > 0 ? SvTRUE(TOPs) : 0;
2509	0	0	if (count > 0) POPs;
2510	0		PUTBACK;
2511	0	0	FREETMPS; LEAVE;
2512
2513	0	0	if (result) {
2514	0		results[found++] = nh->data[i];
2515			}
2516			}
2517
2518	0	0	EXTEND(SP, found);
		0
2519	0	0	for (i = 0; i < found; i++) {
2520	0		ST(i) = sv_2mortal(newSVnv(results[i]));
2521			}
2522	0		Safefree(results);
2523	0		XSRETURN(found);
2524			}
2525
2526			{
2527	10		Heap *h = hl.ptr.heap;
2528			SV **results;
2529
2530	10	100	if (h->size == 0) XSRETURN_EMPTY;
2531
2532	9	50	Newx(results, h->size, SV*);
2533
2534	48	100	for (i = 0; i < h->size; i++) {
2535	39		dSP;
2536			IV result;
2537			int count;
2538
2539	39		ENTER; SAVETMPS;
2540	39		SAVE_DEFSV;
2541	39		DEFSV_set(h->data[i]);
2542
2543	39	50	PUSHMARK(SP);
2544	39	50	XPUSHs(h->data[i]);
2545	39		PUTBACK;
2546
2547	39		count = call_sv(callback, G_SCALAR);
2548	39		SPAGAIN;
2549	39	50	result = count > 0 ? SvTRUE(TOPs) : 0;
2550	39	50	if (count > 0) POPs;
2551	39		PUTBACK;
2552	39	50	FREETMPS; LEAVE;
2553
2554	39	100	if (result) {
2555	18		results[found++] = h->data[i];
2556			}
2557			}
2558
2559	9	50	EXTEND(SP, found);
		50
2560	27	100	for (i = 0; i < found; i++) {
2561	18		ST(i) = results[i];
2562			}
2563	9		Safefree(results);
2564	9		XSRETURN(found);
2565			}
2566			}
2567
2568			/* $heap->delete(sub { ... }) - remove matching elements, returns count */
2569	10		XS_EXTERNAL(XS_heap_delete) {
2570	10		dXSARGS;
2571			HeapLookup hl;
2572	10		IV i, write_pos = 0, deleted = 0;
2573			SV *callback;
2574
2575	10	50	if (items != 2) croak("Usage: $heap->delete(sub { ... })");
2576
2577	10		hl = find_heap(aTHX_ ST(0));
2578	10		callback = ST(1);
2579
2580	10	100	if (!SvROK(callback) \|\| SvTYPE(SvRV(callback)) != SVt_PVCV)
		50
2581	1		croak("delete requires a code reference");
2582
2583	9	50	if (hl.type == MAGIC_NUMERIC) {
2584	0		NumericHeap *nh = hl.ptr.nheap;
2585
2586	0	0	for (i = 0; i < nh->size; i++) {
2587	0		dSP;
2588	0		SV *elem = sv_2mortal(newSVnv(nh->data[i]));
2589			IV result;
2590			int count;
2591
2592	0		ENTER; SAVETMPS;
2593	0		SAVE_DEFSV;
2594	0		DEFSV_set(elem);
2595
2596	0	0	PUSHMARK(SP);
2597	0	0	XPUSHs(elem);
2598	0		PUTBACK;
2599
2600	0		count = call_sv(callback, G_SCALAR);
2601	0		SPAGAIN;
2602	0	0	result = count > 0 ? SvTRUE(TOPs) : 0;
2603	0	0	if (count > 0) POPs;
2604	0		PUTBACK;
2605	0	0	FREETMPS; LEAVE;
2606
2607	0	0	if (result) {
2608	0		deleted++;
2609			} else {
2610	0	0	if (write_pos != i) {
2611	0		nh->data[write_pos] = nh->data[i];
2612			}
2613	0		write_pos++;
2614			}
2615			}
2616
2617	0		nh->size = write_pos;
2618
2619	0	0	if (deleted > 0 && nh->size > 1) {
		0
2620			IV j;
2621	0	0	for (j = (nh->size >> 1) - 1; j >= 0; j--) {
2622	0	0	if (nh->type == HEAP_MIN)
2623	0		nv_sift_down_min(nh, j);
2624			else
2625	0		nv_sift_down_max(nh, j);
2626			}
2627			}
2628
2629	0		XSRETURN_IV(deleted);
2630			}
2631
2632			{
2633	9		Heap *h = hl.ptr.heap;
2634
2635	55	100	for (i = 0; i < h->size; i++) {
2636	46		dSP;
2637			IV result;
2638			int count;
2639
2640	46		ENTER; SAVETMPS;
2641	46		SAVE_DEFSV;
2642	46		DEFSV_set(h->data[i]);
2643
2644	46	50	PUSHMARK(SP);
2645	46	50	XPUSHs(h->data[i]);
2646	46		PUTBACK;
2647
2648	46		count = call_sv(callback, G_SCALAR);
2649	46		SPAGAIN;
2650	46	50	result = count > 0 ? SvTRUE(TOPs) : 0;
2651	46	50	if (count > 0) POPs;
2652	46		PUTBACK;
2653	46	50	FREETMPS; LEAVE;
2654
2655	46	100	if (result) {
2656	18		SvREFCNT_dec(h->data[i]);
2657	18		deleted++;
2658			} else {
2659	28	100	if (write_pos != i) {
2660	15		h->data[write_pos] = h->data[i];
2661	15		h->priorities[write_pos] = h->priorities[i];
2662			}
2663	28		write_pos++;
2664			}
2665			}
2666
2667	9		h->size = write_pos;
2668
2669	9	100	if (deleted > 0 && h->size > 1) {
		100
2670			IV j;
2671	17	100	for (j = (h->size >> 1) - 1; j >= 0; j--) {
2672	11		h->sift_down(aTHX_ h, j);
2673			}
2674			}
2675
2676	9		XSRETURN_IV(deleted);
2677			}
2678			}
2679
2680			/* Import functions */
2681	28		static void install_heap_func_1arg(pTHX_ const char pkg, const char name,
2682			XSUBADDR_t xsub, heap_ppfunc ppfunc) {
2683			char full_name[256];
2684			CV *cv;
2685			SV *ckobj;
2686
2687	28		snprintf(full_name, sizeof(full_name), "%s::%s", pkg, name);
2688	28		cv = newXS(full_name, xsub, __FILE__);
2689	28		ckobj = newSViv(PTR2IV(ppfunc));
2690	28		cv_set_call_checker(cv, heap_call_checker_1arg, ckobj);
2691	28		}
2692
2693	18		static void install_heap_func_2arg(pTHX_ const char pkg, const char name,
2694			XSUBADDR_t xsub, heap_ppfunc ppfunc) {
2695			char full_name[256];
2696			CV *cv;
2697			SV *ckobj;
2698
2699	18		snprintf(full_name, sizeof(full_name), "%s::%s", pkg, name);
2700	18		cv = newXS(full_name, xsub, __FILE__);
2701	18		ckobj = newSViv(PTR2IV(ppfunc));
2702	18		cv_set_call_checker(cv, heap_call_checker_2arg, ckobj);
2703	18		}
2704
2705	21		XS_EXTERNAL(XS_heap_import) {
2706	21		dXSARGS;
2707			const char *pkg;
2708			int i;
2709	21		bool want_import = FALSE;
2710	21		bool want_raw = FALSE;
2711
2712	21	50	pkg = CopSTASHPV(PL_curcop);
		50
		50
		50
		0
		50
		50
2713
2714	26	100	for (i = 1; i < items; i++) {
2715			STRLEN len;
2716	5		const char *arg = SvPV(ST(i), len);
2717	5	100	if (len == 6 && strEQ(arg, "import")) {
		50
2718	4		want_import = TRUE;
2719	1	50	} else if (len == 3 && strEQ(arg, "raw")) {
		50
2720	1		want_raw = TRUE;
2721			}
2722			}
2723
2724	21	100	if (want_import) {
2725	4		install_heap_func_2arg(aTHX_ pkg, "heap_push", XS_heap_push, pp_heap_func_push);
2726	4		install_heap_func_1arg(aTHX_ pkg, "heap_pop", XS_heap_pop, pp_heap_func_pop);
2727	4		install_heap_func_1arg(aTHX_ pkg, "heap_peek", XS_heap_peek, pp_heap_func_peek);
2728	4		install_heap_func_1arg(aTHX_ pkg, "heap_size", XS_heap_size, pp_heap_func_size);
2729	4		install_heap_func_2arg(aTHX_ pkg, "heap_peek_n", XS_heap_peek_n, pp_heap_func_peek_n);
2730	4		install_heap_func_2arg(aTHX_ pkg, "heap_search", XS_heap_search, pp_heap_func_search);
2731	4		install_heap_func_2arg(aTHX_ pkg, "heap_delete", XS_heap_delete, pp_heap_func_delete);
2732	4		install_heap_func_1arg(aTHX_ pkg, "heap_is_empty", XS_heap_is_empty, pp_heap_func_is_empty);
2733	4		install_heap_func_1arg(aTHX_ pkg, "heap_clear", XS_heap_clear, pp_heap_func_clear);
2734	4		install_heap_func_1arg(aTHX_ pkg, "heap_type", XS_heap_type, pp_heap_func_type);
2735			}
2736
2737	21	100	if (want_raw) {
2738			/* Install raw array functions with custom ops */
2739	1		install_heap_func_2arg(aTHX_ pkg, "push_heap_min", XS_push_heap_min, pp_push_heap_min);
2740	1		install_heap_func_1arg(aTHX_ pkg, "pop_heap_min", XS_pop_heap_min, pp_pop_heap_min);
2741	1		install_heap_func_2arg(aTHX_ pkg, "push_heap_max", XS_push_heap_max, pp_push_heap_max);
2742	1		install_heap_func_1arg(aTHX_ pkg, "pop_heap_max", XS_pop_heap_max, pp_pop_heap_max);
2743	1		install_heap_func_1arg(aTHX_ pkg, "make_heap_min", XS_make_heap_min, pp_make_heap_min);
2744	1		install_heap_func_1arg(aTHX_ pkg, "make_heap_max", XS_make_heap_max, pp_make_heap_max);
2745			}
2746
2747	21		XSRETURN_EMPTY;
2748			}
2749
2750			/* ============================================
2751			Boot function
2752			============================================ */
2753
2754	19		XS_EXTERNAL(boot_Heap__PQ) {
2755	19		dXSBOOTARGSXSAPIVERCHK;
2756			PERL_UNUSED_VAR(items);
2757
2758			/* Register custom ops */
2759	19		XopENTRY_set(&heap_func_push_xop, xop_name, "heap_func_push");
2760	19		XopENTRY_set(&heap_func_push_xop, xop_desc, "heap function push");
2761	19		Perl_custom_op_register(aTHX_ pp_heap_func_push, &heap_func_push_xop);
2762
2763	19		XopENTRY_set(&heap_func_pop_xop, xop_name, "heap_func_pop");
2764	19		XopENTRY_set(&heap_func_pop_xop, xop_desc, "heap function pop");
2765	19		Perl_custom_op_register(aTHX_ pp_heap_func_pop, &heap_func_pop_xop);
2766
2767	19		XopENTRY_set(&heap_func_peek_xop, xop_name, "heap_func_peek");
2768	19		XopENTRY_set(&heap_func_peek_xop, xop_desc, "heap function peek");
2769	19		Perl_custom_op_register(aTHX_ pp_heap_func_peek, &heap_func_peek_xop);
2770
2771	19		XopENTRY_set(&heap_func_size_xop, xop_name, "heap_func_size");
2772	19		XopENTRY_set(&heap_func_size_xop, xop_desc, "heap function size");
2773	19		Perl_custom_op_register(aTHX_ pp_heap_func_size, &heap_func_size_xop);
2774
2775			/* Dedicated NV heap custom ops */
2776	19		XopENTRY_set(&nv_push_xop, xop_name, "nv_push");
2777	19		XopENTRY_set(&nv_push_xop, xop_desc, "nv heap push");
2778	19		Perl_custom_op_register(aTHX_ pp_nv_push, &nv_push_xop);
2779
2780			/* Raw array custom ops */
2781	19		XopENTRY_set(&push_heap_min_xop, xop_name, "push_heap_min");
2782	19		XopENTRY_set(&push_heap_min_xop, xop_desc, "raw array push min");
2783	19		Perl_custom_op_register(aTHX_ pp_push_heap_min, &push_heap_min_xop);
2784
2785	19		XopENTRY_set(&push_heap_max_xop, xop_name, "push_heap_max");
2786	19		XopENTRY_set(&push_heap_max_xop, xop_desc, "raw array push max");
2787	19		Perl_custom_op_register(aTHX_ pp_push_heap_max, &push_heap_max_xop);
2788
2789	19		XopENTRY_set(&pop_heap_min_xop, xop_name, "pop_heap_min");
2790	19		XopENTRY_set(&pop_heap_min_xop, xop_desc, "raw array pop min");
2791	19		Perl_custom_op_register(aTHX_ pp_pop_heap_min, &pop_heap_min_xop);
2792
2793	19		XopENTRY_set(&pop_heap_max_xop, xop_name, "pop_heap_max");
2794	19		XopENTRY_set(&pop_heap_max_xop, xop_desc, "raw array pop max");
2795	19		Perl_custom_op_register(aTHX_ pp_pop_heap_max, &pop_heap_max_xop);
2796
2797	19		XopENTRY_set(&make_heap_min_xop, xop_name, "make_heap_min");
2798	19		XopENTRY_set(&make_heap_min_xop, xop_desc, "raw array make min");
2799	19		Perl_custom_op_register(aTHX_ pp_make_heap_min, &make_heap_min_xop);
2800
2801	19		XopENTRY_set(&make_heap_max_xop, xop_name, "make_heap_max");
2802	19		XopENTRY_set(&make_heap_max_xop, xop_desc, "raw array make max");
2803	19		Perl_custom_op_register(aTHX_ pp_make_heap_max, &make_heap_max_xop);
2804
2805	19		XopENTRY_set(&nv_pop_xop, xop_name, "nv_pop");
2806	19		XopENTRY_set(&nv_pop_xop, xop_desc, "nv heap pop");
2807	19		Perl_custom_op_register(aTHX_ pp_nv_pop, &nv_pop_xop);
2808
2809	19		XopENTRY_set(&nv_peek_xop, xop_name, "nv_peek");
2810	19		XopENTRY_set(&nv_peek_xop, xop_desc, "nv heap peek");
2811	19		Perl_custom_op_register(aTHX_ pp_nv_peek, &nv_peek_xop);
2812
2813	19		XopENTRY_set(&nv_size_xop, xop_name, "nv_size");
2814	19		XopENTRY_set(&nv_size_xop, xop_desc, "nv heap size");
2815	19		Perl_custom_op_register(aTHX_ pp_nv_size, &nv_size_xop);
2816
2817	19		XopENTRY_set(&nv_peek_n_xop, xop_name, "nv_peek_n");
2818	19		XopENTRY_set(&nv_peek_n_xop, xop_desc, "nv heap peek_n");
2819	19		Perl_custom_op_register(aTHX_ pp_nv_peek_n, &nv_peek_n_xop);
2820
2821	19		XopENTRY_set(&heap_func_peek_n_xop, xop_name, "heap_func_peek_n");
2822	19		XopENTRY_set(&heap_func_peek_n_xop, xop_desc, "heap function peek_n");
2823	19		Perl_custom_op_register(aTHX_ pp_heap_func_peek_n, &heap_func_peek_n_xop);
2824
2825	19		XopENTRY_set(&heap_func_search_xop, xop_name, "heap_func_search");
2826	19		XopENTRY_set(&heap_func_search_xop, xop_desc, "heap function search");
2827	19		Perl_custom_op_register(aTHX_ pp_heap_func_search, &heap_func_search_xop);
2828
2829	19		XopENTRY_set(&heap_func_delete_xop, xop_name, "heap_func_delete");
2830	19		XopENTRY_set(&heap_func_delete_xop, xop_desc, "heap function delete");
2831	19		Perl_custom_op_register(aTHX_ pp_heap_func_delete, &heap_func_delete_xop);
2832
2833	19		XopENTRY_set(&nv_search_xop, xop_name, "nv_search");
2834	19		XopENTRY_set(&nv_search_xop, xop_desc, "nv heap search");
2835	19		Perl_custom_op_register(aTHX_ pp_nv_search, &nv_search_xop);
2836
2837	19		XopENTRY_set(&nv_delete_xop, xop_name, "nv_delete");
2838	19		XopENTRY_set(&nv_delete_xop, xop_desc, "nv heap delete");
2839	19		Perl_custom_op_register(aTHX_ pp_nv_delete, &nv_delete_xop);
2840
2841	19		XopENTRY_set(&heap_func_is_empty_xop, xop_name, "heap_func_is_empty");
2842	19		XopENTRY_set(&heap_func_is_empty_xop, xop_desc, "heap function is_empty");
2843	19		Perl_custom_op_register(aTHX_ pp_heap_func_is_empty, &heap_func_is_empty_xop);
2844
2845	19		XopENTRY_set(&heap_func_clear_xop, xop_name, "heap_func_clear");
2846	19		XopENTRY_set(&heap_func_clear_xop, xop_desc, "heap function clear");
2847	19		Perl_custom_op_register(aTHX_ pp_heap_func_clear, &heap_func_clear_xop);
2848
2849	19		XopENTRY_set(&heap_func_type_xop, xop_name, "heap_func_type");
2850	19		XopENTRY_set(&heap_func_type_xop, xop_desc, "heap function type");
2851	19		Perl_custom_op_register(aTHX_ pp_heap_func_type, &heap_func_type_xop);
2852
2853	19		XopENTRY_set(&nv_is_empty_xop, xop_name, "nv_is_empty");
2854	19		XopENTRY_set(&nv_is_empty_xop, xop_desc, "nv heap is_empty");
2855	19		Perl_custom_op_register(aTHX_ pp_nv_is_empty, &nv_is_empty_xop);
2856
2857	19		XopENTRY_set(&nv_clear_xop, xop_name, "nv_clear");
2858	19		XopENTRY_set(&nv_clear_xop, xop_desc, "nv heap clear");
2859	19		Perl_custom_op_register(aTHX_ pp_nv_clear, &nv_clear_xop);
2860
2861			/* Register XS subs with call checkers */
2862			{
2863			CV *cv;
2864			SV *ckobj;
2865
2866			/* Standard heap */
2867	19		newXS("Heap::PQ::new", XS_heap_new, __FILE__);
2868
2869	19		cv = newXS("Heap::PQ::push", XS_heap_push, __FILE__);
2870	19		ckobj = newSViv(PTR2IV(pp_heap_func_push));
2871	19		cv_set_call_checker(cv, heap_call_checker_2arg, ckobj);
2872
2873	19		newXS("Heap::PQ::push_all", XS_heap_push_all, __FILE__);
2874
2875	19		cv = newXS("Heap::PQ::pop", XS_heap_pop, __FILE__);
2876	19		ckobj = newSViv(PTR2IV(pp_heap_func_pop));
2877	19		cv_set_call_checker(cv, heap_call_checker_1arg, ckobj);
2878
2879	19		cv = newXS("Heap::PQ::peek", XS_heap_peek, __FILE__);
2880	19		ckobj = newSViv(PTR2IV(pp_heap_func_peek));
2881	19		cv_set_call_checker(cv, heap_call_checker_1arg, ckobj);
2882
2883	19		cv = newXS("Heap::PQ::size", XS_heap_size, __FILE__);
2884	19		ckobj = newSViv(PTR2IV(pp_heap_func_size));
2885	19		cv_set_call_checker(cv, heap_call_checker_1arg, ckobj);
2886
2887	19		cv = newXS("Heap::PQ::is_empty", XS_heap_is_empty, __FILE__);
2888	19		ckobj = newSViv(PTR2IV(pp_heap_func_is_empty));
2889	19		cv_set_call_checker(cv, heap_call_checker_1arg, ckobj);
2890
2891	19		cv = newXS("Heap::PQ::clear", XS_heap_clear, __FILE__);
2892	19		ckobj = newSViv(PTR2IV(pp_heap_func_clear));
2893	19		cv_set_call_checker(cv, heap_call_checker_1arg, ckobj);
2894
2895	19		cv = newXS("Heap::PQ::type", XS_heap_type, __FILE__);
2896	19		ckobj = newSViv(PTR2IV(pp_heap_func_type));
2897	19		cv_set_call_checker(cv, heap_call_checker_1arg, ckobj);
2898
2899	19		cv = newXS("Heap::PQ::peek_n", XS_heap_peek_n, __FILE__);
2900	19		ckobj = newSViv(PTR2IV(pp_heap_func_peek_n));
2901	19		cv_set_call_checker(cv, heap_call_checker_2arg, ckobj);
2902
2903	19		cv = newXS("Heap::PQ::search", XS_heap_search, __FILE__);
2904	19		ckobj = newSViv(PTR2IV(pp_heap_func_search));
2905	19		cv_set_call_checker(cv, heap_call_checker_2arg, ckobj);
2906
2907	19		cv = newXS("Heap::PQ::delete", XS_heap_delete, __FILE__);
2908	19		ckobj = newSViv(PTR2IV(pp_heap_func_delete));
2909	19		cv_set_call_checker(cv, heap_call_checker_2arg, ckobj);
2910
2911	19		newXS("Heap::PQ::import", XS_heap_import, __FILE__);
2912
2913			/* Numeric heap */
2914	19		newXS("Heap::PQ::new_nv", XS_heap_new_nv, __FILE__);
2915
2916	19		cv = newXS("Heap::PQ::nv::push", XS_nv_push, __FILE__);
2917	19		ckobj = newSViv(PTR2IV(pp_nv_push));
2918	19		cv_set_call_checker(cv, heap_call_checker_2arg, ckobj);
2919
2920	19		newXS("Heap::PQ::nv::push_all", XS_nv_push_all, __FILE__);
2921
2922	19		cv = newXS("Heap::PQ::nv::pop", XS_nv_pop, __FILE__);
2923	19		ckobj = newSViv(PTR2IV(pp_nv_pop));
2924	19		cv_set_call_checker(cv, heap_call_checker_1arg, ckobj);
2925
2926	19		cv = newXS("Heap::PQ::nv::peek", XS_nv_peek, __FILE__);
2927	19		ckobj = newSViv(PTR2IV(pp_nv_peek));
2928	19		cv_set_call_checker(cv, heap_call_checker_1arg, ckobj);
2929
2930	19		cv = newXS("Heap::PQ::nv::size", XS_nv_size, __FILE__);
2931	19		ckobj = newSViv(PTR2IV(pp_nv_size));
2932	19		cv_set_call_checker(cv, heap_call_checker_1arg, ckobj);
2933
2934	19		cv = newXS("Heap::PQ::nv::is_empty", XS_nv_is_empty, __FILE__);
2935	19		ckobj = newSViv(PTR2IV(pp_nv_is_empty));
2936	19		cv_set_call_checker(cv, heap_call_checker_1arg, ckobj);
2937
2938	19		cv = newXS("Heap::PQ::nv::clear", XS_nv_clear, __FILE__);
2939	19		ckobj = newSViv(PTR2IV(pp_nv_clear));
2940	19		cv_set_call_checker(cv, heap_call_checker_1arg, ckobj);
2941
2942	19		cv = newXS("Heap::PQ::nv::peek_n", XS_nv_peek_n, __FILE__);
2943	19		ckobj = newSViv(PTR2IV(pp_nv_peek_n));
2944	19		cv_set_call_checker(cv, heap_call_checker_2arg, ckobj);
2945
2946	19		cv = newXS("Heap::PQ::nv::search", XS_nv_search, __FILE__);
2947	19		ckobj = newSViv(PTR2IV(pp_nv_search));
2948	19		cv_set_call_checker(cv, heap_call_checker_2arg, ckobj);
2949
2950	19		cv = newXS("Heap::PQ::nv::delete", XS_nv_delete, __FILE__);
2951	19		ckobj = newSViv(PTR2IV(pp_nv_delete));
2952	19		cv_set_call_checker(cv, heap_call_checker_2arg, ckobj);
2953
2954			/* Raw array functions */
2955	19		cv = newXS("Heap::PQ::push_heap_min", XS_push_heap_min, __FILE__);
2956	19		ckobj = newSViv(PTR2IV(pp_push_heap_min));
2957	19		cv_set_call_checker(cv, heap_call_checker_2arg, ckobj);
2958
2959	19		cv = newXS("Heap::PQ::pop_heap_min", XS_pop_heap_min, __FILE__);
2960	19		ckobj = newSViv(PTR2IV(pp_pop_heap_min));
2961	19		cv_set_call_checker(cv, heap_call_checker_1arg, ckobj);
2962
2963	19		cv = newXS("Heap::PQ::push_heap_max", XS_push_heap_max, __FILE__);
2964	19		ckobj = newSViv(PTR2IV(pp_push_heap_max));
2965	19		cv_set_call_checker(cv, heap_call_checker_2arg, ckobj);
2966
2967	19		cv = newXS("Heap::PQ::pop_heap_max", XS_pop_heap_max, __FILE__);
2968	19		ckobj = newSViv(PTR2IV(pp_pop_heap_max));
2969	19		cv_set_call_checker(cv, heap_call_checker_1arg, ckobj);
2970
2971	19		cv = newXS("Heap::PQ::make_heap_min", XS_make_heap_min, __FILE__);
2972	19		ckobj = newSViv(PTR2IV(pp_make_heap_min));
2973	19		cv_set_call_checker(cv, heap_call_checker_1arg, ckobj);
2974
2975	19		cv = newXS("Heap::PQ::make_heap_max", XS_make_heap_max, __FILE__);
2976	19		ckobj = newSViv(PTR2IV(pp_make_heap_max));
2977	19		cv_set_call_checker(cv, heap_call_checker_1arg, ckobj);
2978			}
2979
2980			#if PERL_VERSION_GE(5,22,0)
2981	19		Perl_xs_boot_epilog(aTHX_ ax);
2982			#else
2983			XSRETURN_YES;
2984			#endif
2985	19		}