Array-Heap/Heap.xs

#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"

/* pre-5.10 compatibility */
#ifndef GV_NOTQUAL
# define GV_NOTQUAL 1
#endif
#ifndef gv_fetchpvs
# define gv_fetchpvs gv_fetchpv
#endif

/* pre-5.8 compatibility */
#ifndef PERL_MAGIC_tied
# define PERL_MAGIC_tied 'P'
#endif

#include "multicall.h"

/* workaround for buggy multicall API */
#ifndef cxinc
# define cxinc() Perl_cxinc (aTHX)
#endif

#define dCMP                    \
  dMULTICALL;                   \
  void *cmp_data;               \
  I32 gimme = G_SCALAR;

#define CMP_PUSH(sv)            \
  PUSH_MULTICALL (cmp_push_ (sv));\
  cmp_data = multicall_cop;

#define CMP_POP                 \
  POP_MULTICALL;

#define dCMP_CALL(data)         \
  OP *multicall_cop = (OP *)data;

static void *
cmp_push_ (SV *sv)
{
  HV *st;
  GV *gvp;
  CV *cv;

  cv = sv_2cv (sv, &st, &gvp, 0);

  if (!cv)
    croak ("%s: callback must be a CODE reference or another callable object", SvPV_nolen (sv));

  SAVESPTR (PL_firstgv ); PL_firstgv  = gv_fetchpv ("a", GV_ADD | GV_NOTQUAL, SVt_PV); SAVESPTR (GvSV (PL_firstgv ));
  SAVESPTR (PL_secondgv); PL_secondgv = gv_fetchpv ("b", GV_ADD | GV_NOTQUAL, SVt_PV); SAVESPTR (GvSV (PL_secondgv));

  return cv;
}

/*****************************************************************************/

static SV *
sv_first (SV *sv)
{
  if (SvROK (sv) && SvTYPE (SvRV (sv)) == SVt_PVAV)
    {
      AV *av = (AV *)SvRV (sv);

      sv = AvFILLp (av) < 0 || !AvARRAY (sv)[0]
           ? &PL_sv_undef : AvARRAY (av)[0];
    }

  return sv;
}

static void
set_idx (SV *sv, int idx)
{
  if (!SvROK (sv))
    return;

  sv = SvRV (sv);
  
  if (SvTYPE (sv) != SVt_PVAV)
    return;
  
  if (
     AvFILL ((AV *)sv) < 1
     || AvARRAY ((AV *)sv)[1] == 0
     || AvARRAY ((AV *)sv)[1] == &PL_sv_undef)
    av_store ((AV *)sv, 1, newSViv (idx));
  else
    {
      sv = AvARRAY ((AV *)sv)[1];

      if (SvTYPE (sv) == SVt_IV)
        SvIV_set (sv, idx);
      else
        sv_setiv (sv, idx);
    }
}

#define set_heap(idx,he)                \
  do {                                  \
    if (flags)                          \
      set_idx (he, idx);                \
    heap [idx] = he;                    \
  } while (0)

static int
cmp_nv (SV *a, SV *b, void *cmp_data)
{
  a = sv_first (a);
  b = sv_first (b);

  return SvNV (a) > SvNV (b);
}

static int
cmp_sv (SV *a, SV *b, void *cmp_data)
{
  a = sv_first (a);
  b = sv_first (b);

  return sv_cmp (a, b) > 0;
}

static int
cmp_custom (SV *a, SV *b, void *cmp_data)
{
  dCMP_CALL (cmp_data);

  GvSV (PL_firstgv ) = a;
  GvSV (PL_secondgv) = b;

  MULTICALL;

  if (SvTRUE (ERRSV))
    croak (NULL);

  {
    dSP;
    return TOPi > 0;
  }
}

/*****************************************************************************/

typedef int (*f_cmp)(SV *a, SV *b, void *cmp_data);

static AV *
array (SV *ref)
{
  if (SvROK (ref)
      && SvTYPE (SvRV (ref)) == SVt_PVAV
      && !SvTIED_mg (SvRV (ref), PERL_MAGIC_tied))
    return (AV *)SvRV (ref);

  croak ("argument 'heap' must be a (non-tied) array");
}

#define gt(a,b) cmp ((a), (b), cmp_data)

/*****************************************************************************/

/* away from the root */
static void
downheap (AV *av, f_cmp cmp, void *cmp_data, int N, int k, int flags)
{
  SV **heap = AvARRAY (av);
  SV *he = heap [k];

  for (;;)
    {
      int c = (k << 1) + 1;

      if (c >= N)
        break;

      c += c + 1 < N && gt (heap [c], heap [c + 1])
           ? 1 : 0;

      if (!(gt (he, heap [c])))
        break;

      set_heap (k, heap [c]);

      k = c;
    }

  set_heap (k, he);
}

/* towards the root */
static void
upheap (AV *av, f_cmp cmp, void *cmp_data, int k, int flags)
{
  SV **heap = AvARRAY (av);
  SV *he = heap [k];

  while (k)
    {
      int p = (k - 1) >> 1;

      if (!(gt (heap [p], he)))
        break;

      set_heap (k, heap [p]);
      k = p;
    }

  set_heap (k, he);
}

/* move an element suitably so it is in a correct place */
static void
adjustheap (AV *av, f_cmp cmp, void *cmp_data, int N, int k, int flags)
{
  SV **heap = AvARRAY (av);

  if (k > 0 && !gt (heap [k], heap [(k - 1) >> 1]))
    upheap (av, cmp, cmp_data, k, flags);
  else
    downheap (av, cmp, cmp_data, N, k, flags);
}

/*****************************************************************************/

static void
make_heap (AV *av, f_cmp cmp, void *cmp_data, int flags)
{
  int i, len = AvFILLp (av);

  /* do not use floyds algorithm, as I expect the simpler and more cache-efficient */
  /* upheap is actually faster */
  for (i = 0; i <= len; ++i)
    upheap (av, cmp, cmp_data, i, flags);
}

static void
push_heap (AV *av, f_cmp cmp, void *cmp_data, SV **elems, int nelems, int flags)
{
  int i;

  av_extend (av, AvFILLp (av) + nelems);

  /* we do it in two steps, as the perl cmp function might copy the stack */
  for (i = 0; i < nelems; ++i)
    AvARRAY (av)[++AvFILLp (av)] = newSVsv (elems [i]);

  for (i = 0; i < nelems; ++i)
    upheap (av, cmp, cmp_data, AvFILLp (av) - i, flags);
}

static SV *
pop_heap (AV *av, f_cmp cmp, void *cmp_data, int flags)
{
  int len = AvFILLp (av);

  if (len < 0)
    return &PL_sv_undef;
  else if (len == 0)
    return av_pop (av);
  else
    {
      SV *top = av_pop (av);
      SV *result = AvARRAY (av)[0];
      AvARRAY (av)[0] = top;
      downheap (av, cmp, cmp_data, len, 0, flags);
      return result;
    }
}

static SV *
splice_heap (AV *av, f_cmp cmp, void *cmp_data, int idx, int flags)
{
  int len = AvFILLp (av);

  if (idx < 0 || idx > len)
    return &PL_sv_undef;
  else if (idx == len)
    return av_pop (av); /* the last element */
  else
    {
      SV *top = av_pop (av);
      SV *result = AvARRAY (av)[idx];
      AvARRAY (av)[idx] = top;
      adjustheap (av, cmp, cmp_data, len, idx, flags);
      return result;
    }
}

static void
adjust_heap (AV *av, f_cmp cmp, void *cmp_data, int idx, int flags)
{
  int len = AvFILLp (av);

  if (idx > len)
    croak ("Array::Heap::adjust_heap: index out of array bounds");

  adjustheap (av, cmp, cmp_data, len + 1, idx, flags);
}

MODULE = Array::Heap            PACKAGE = Array::Heap

void
make_heap (SV *heap)
        PROTOTYPE: \@
        ALIAS:
        make_heap_idx = 1
        CODE:
        make_heap (array (heap), cmp_nv, 0, ix);

void
make_heap_lex (SV *heap)
        PROTOTYPE: \@
        CODE:
        make_heap (array (heap), cmp_sv, 0, 0);

void
make_heap_cmp (SV *cmp, SV *heap)
        PROTOTYPE: &\@
        CODE:
{
        dCMP;
        CMP_PUSH (cmp);
        make_heap (array (heap), cmp_custom, cmp_data, 0);
        CMP_POP;
}

void
push_heap (SV *heap, ...)
        PROTOTYPE: \@@
        ALIAS:
        push_heap_idx = 1
        CODE:
        push_heap (array (heap), cmp_nv, 0, &(ST(1)), items - 1, ix);

void
push_heap_lex (SV *heap, ...)
        PROTOTYPE: \@@
        CODE:
        push_heap (array (heap), cmp_sv, 0, &(ST(1)), items - 1, 0);

void
push_heap_cmp (SV *cmp, SV *heap, ...)
        PROTOTYPE: &\@@
        CODE:
{
        SV **st_2 = &(ST(2)); /* multicall.h uses PUSHSTACK */
        dCMP;
        CMP_PUSH (cmp);
        push_heap (array (heap), cmp_custom, cmp_data, st_2, items - 2, 0);
        CMP_POP;
}

SV *
pop_heap (SV *heap)
        PROTOTYPE: \@
        ALIAS:
        pop_heap_idx = 1
        CODE:
        RETVAL = pop_heap (array (heap), cmp_nv, 0, ix);
        OUTPUT:
        RETVAL

SV *
pop_heap_lex (SV *heap)
        PROTOTYPE: \@
        CODE:
        RETVAL = pop_heap (array (heap), cmp_sv, 0, 0);
        OUTPUT:
        RETVAL

SV *
pop_heap_cmp (SV *cmp, SV *heap)
        PROTOTYPE: &\@
        CODE:
{
        dCMP;
        CMP_PUSH (cmp);
        RETVAL = pop_heap (array (heap), cmp_custom, cmp_data, 0);
        CMP_POP;
}
        OUTPUT:
        RETVAL

SV *
splice_heap (SV *heap, int idx)
        PROTOTYPE: \@$
        ALIAS:
        splice_heap_idx = 1
        CODE:
        RETVAL = splice_heap (array (heap), cmp_nv, 0, idx, ix);
        OUTPUT:
        RETVAL

SV *
splice_heap_lex (SV *heap, int idx)
        PROTOTYPE: \@$
        CODE:
        RETVAL = splice_heap (array (heap), cmp_sv, 0, idx, 0);
        OUTPUT:
        RETVAL

SV *
splice_heap_cmp (SV *cmp, SV *heap, int idx)
        PROTOTYPE: &\@$
        CODE:
{
        dCMP;
        CMP_PUSH (cmp);
        RETVAL = splice_heap (array (heap), cmp_custom, cmp_data, idx, 0);
        CMP_POP;
}
        OUTPUT:
        RETVAL

void
adjust_heap (SV *heap, int idx)
        PROTOTYPE: \@$
        ALIAS:
        adjust_heap_idx = 1
        CODE:
        adjust_heap (array (heap), cmp_nv, 0, idx, ix);

void
adjust_heap_lex (SV *heap, int idx)
        PROTOTYPE: \@$
        CODE:
        adjust_heap (array (heap), cmp_sv, 0, idx, 0);

void
adjust_heap_cmp (SV *cmp, SV *heap, int idx)
        PROTOTYPE: &\@$
        CODE:
{
        dCMP;
        CMP_PUSH (cmp);
        adjust_heap (array (heap), cmp_custom, cmp_data, idx, 0);
        CMP_POP;
}

Revision:	1.9
Committed:	Wed Dec 7 12:06:35 2016 UTC (7 years, 5 months ago) by root
Branch:	MAIN
CVS Tags:	rel-3_22, HEAD
Changes since 1.8:	+6 -2 lines
Log Message:	3.22
#	User	Rev	Content
1	root	1.1	#include "EXTERN.h"
2			#include "perl.h"
3			#include "XSUB.h"
4
5	root	1.3	/* pre-5.10 compatibility */
6			#ifndef GV_NOTQUAL
7			# define GV_NOTQUAL 1
8			#endif
9			#ifndef gv_fetchpvs
10			# define gv_fetchpvs gv_fetchpv
11			#endif
12
13	root	1.4	/* pre-5.8 compatibility */
14			#ifndef PERL_MAGIC_tied
15			# define PERL_MAGIC_tied 'P'
16			#endif
17
18	root	1.3	#include "multicall.h"
19
20			/* workaround for buggy multicall API */
21			#ifndef cxinc
22			# define cxinc() Perl_cxinc (aTHX)
23			#endif
24
25			#define dCMP \
26			dMULTICALL; \
27			void *cmp_data; \
28			I32 gimme = G_SCALAR;
29
30			#define CMP_PUSH(sv) \
31			PUSH_MULTICALL (cmp_push_ (sv));\
32			cmp_data = multicall_cop;
33
34			#define CMP_POP \
35			POP_MULTICALL;
36
37			#define dCMP_CALL(data) \
38			OP multicall_cop = (OP )data;
39
40			static void *
41			cmp_push_ (SV *sv)
42			{
43			HV *st;
44			GV *gvp;
45			CV *cv;
46
47			cv = sv_2cv (sv, &st, &gvp, 0);
48
49			if (!cv)
50			croak ("%s: callback must be a CODE reference or another callable object", SvPV_nolen (sv));
51
52	root	1.8	SAVESPTR (PL_firstgv ); PL_firstgv = gv_fetchpv ("a", GV_ADD \| GV_NOTQUAL, SVt_PV); SAVESPTR (GvSV (PL_firstgv ));
53			SAVESPTR (PL_secondgv); PL_secondgv = gv_fetchpv ("b", GV_ADD \| GV_NOTQUAL, SVt_PV); SAVESPTR (GvSV (PL_secondgv));
54	root	1.3
55			return cv;
56			}
57
58			/*****************************************************************************/
59
60			static SV *
61			sv_first (SV *sv)
62			{
63			if (SvROK (sv) && SvTYPE (SvRV (sv)) == SVt_PVAV)
64			{
65			AV av = (AV )SvRV (sv);
66
67	root	1.9	sv = AvFILLp (av) < 0 \|\| !AvARRAY (sv)[0]
68			? &PL_sv_undef : AvARRAY (av)[0];
69	root	1.3	}
70
71			return sv;
72			}
73
74	root	1.5	static void
75			set_idx (SV *sv, int idx)
76			{
77			if (!SvROK (sv))
78			return;
79
80			sv = SvRV (sv);
81
82			if (SvTYPE (sv) != SVt_PVAV)
83			return;
84
85	root	1.9	if (
86			AvFILL ((AV *)sv) < 1
87			\|\| AvARRAY ((AV *)sv)[1] == 0
88			\|\| AvARRAY ((AV *)sv)[1] == &PL_sv_undef)
89	root	1.5	av_store ((AV *)sv, 1, newSViv (idx));
90			else
91			{
92			sv = AvARRAY ((AV *)sv)[1];
93
94			if (SvTYPE (sv) == SVt_IV)
95			SvIV_set (sv, idx);
96			else
97			sv_setiv (sv, idx);
98			}
99			}
100
101			#define set_heap(idx,he) \
102			do { \
103			if (flags) \
104			set_idx (he, idx); \
105			heap [idx] = he; \
106			} while (0)
107
108	root	1.1	static int
109	root	1.3	cmp_nv (SV a, SV b, void *cmp_data)
110	root	1.1	{
111	root	1.3	a = sv_first (a);
112			b = sv_first (b);
113	root	1.1
114			return SvNV (a) > SvNV (b);
115			}
116
117			static int
118	root	1.3	cmp_sv (SV a, SV b, void *cmp_data)
119	root	1.1	{
120	root	1.3	a = sv_first (a);
121			b = sv_first (b);
122	root	1.1
123	root	1.3	return sv_cmp (a, b) > 0;
124	root	1.1	}
125
126			static int
127	root	1.3	cmp_custom (SV a, SV b, void *cmp_data)
128	root	1.1	{
129	root	1.3	dCMP_CALL (cmp_data);
130	root	1.1
131	root	1.8	GvSV (PL_firstgv ) = a;
132	root	1.1	GvSV (PL_secondgv) = b;
133
134	root	1.3	MULTICALL;
135	root	1.1
136			if (SvTRUE (ERRSV))
137			croak (NULL);
138
139	root	1.3	{
140			dSP;
141			return TOPi > 0;
142			}
143			}
144	root	1.1
145	root	1.3	/*****************************************************************************/
146	root	1.1
147	root	1.3	typedef int (f_cmp)(SV a, SV b, void cmp_data);
148	root	1.1
149			static AV *
150			array (SV *ref)
151			{
152	root	1.3	if (SvROK (ref)
153			&& SvTYPE (SvRV (ref)) == SVt_PVAV
154			&& !SvTIED_mg (SvRV (ref), PERL_MAGIC_tied))
155	root	1.1	return (AV *)SvRV (ref);
156
157	root	1.3	croak ("argument 'heap' must be a (non-tied) array");
158	root	1.1	}
159
160	root	1.3	#define gt(a,b) cmp ((a), (b), cmp_data)
161	root	1.1
162	root	1.3	/*****************************************************************************/
163	root	1.1
164	root	1.3	/* away from the root */
165	root	1.1	static void
166	root	1.5	downheap (AV av, f_cmp cmp, void cmp_data, int N, int k, int flags)
167	root	1.1	{
168	root	1.3	SV **heap = AvARRAY (av);
169			SV *he = heap [k];
170	root	1.1
171	root	1.3	for (;;)
172	root	1.1	{
173	root	1.3	int c = (k << 1) + 1;
174
175			if (c >= N)
176			break;
177
178			c += c + 1 < N && gt (heap [c], heap [c + 1])
179			? 1 : 0;
180
181			if (!(gt (he, heap [c])))
182			break;
183
184	root	1.5	set_heap (k, heap [c]);
185	root	1.3
186			k = c;
187	root	1.1	}
188
189	root	1.5	set_heap (k, he);
190	root	1.1	}
191
192	root	1.3	/* towards the root */
193	root	1.1	static void
194	root	1.5	upheap (AV av, f_cmp cmp, void cmp_data, int k, int flags)
195	root	1.1	{
196	root	1.3	SV **heap = AvARRAY (av);
197			SV *he = heap [k];
198	root	1.1
199	root	1.3	while (k)
200	root	1.1	{
201	root	1.3	int p = (k - 1) >> 1;
202	root	1.1
203	root	1.3	if (!(gt (heap [p], he)))
204			break;
205
206	root	1.5	set_heap (k, heap [p]);
207	root	1.3	k = p;
208	root	1.1	}
209
210	root	1.5	set_heap (k, he);
211	root	1.3	}
212
213			/* move an element suitably so it is in a correct place */
214			static void
215	root	1.5	adjustheap (AV av, f_cmp cmp, void cmp_data, int N, int k, int flags)
216	root	1.3	{
217			SV **heap = AvARRAY (av);
218	root	1.1
219	root	1.3	if (k > 0 && !gt (heap [k], heap [(k - 1) >> 1]))
220	root	1.5	upheap (av, cmp, cmp_data, k, flags);
221	root	1.3	else
222	root	1.5	downheap (av, cmp, cmp_data, N, k, flags);
223	root	1.1	}
224
225	root	1.3	/*****************************************************************************/
226
227	root	1.1	static void
228	root	1.5	make_heap (AV av, f_cmp cmp, void cmp_data, int flags)
229	root	1.1	{
230	root	1.3	int i, len = AvFILLp (av);
231	root	1.1
232	root	1.3	/* do not use floyds algorithm, as I expect the simpler and more cache-efficient */
233			/* upheap is actually faster */
234			for (i = 0; i <= len; ++i)
235	root	1.5	upheap (av, cmp, cmp_data, i, flags);
236	root	1.1	}
237
238			static void
239	root	1.5	push_heap (AV av, f_cmp cmp, void cmp_data, SV **elems, int nelems, int flags)
240	root	1.1	{
241	root	1.4	int i;
242
243			av_extend (av, AvFILLp (av) + nelems);
244
245			/* we do it in two steps, as the perl cmp function might copy the stack */
246			for (i = 0; i < nelems; ++i)
247			AvARRAY (av)[++AvFILLp (av)] = newSVsv (elems [i]);
248
249			for (i = 0; i < nelems; ++i)
250	root	1.5	upheap (av, cmp, cmp_data, AvFILLp (av) - i, flags);
251	root	1.1	}
252
253			static SV *
254	root	1.5	pop_heap (AV av, f_cmp cmp, void cmp_data, int flags)
255	root	1.1	{
256	root	1.3	int len = AvFILLp (av);
257
258			if (len < 0)
259	root	1.1	return &PL_sv_undef;
260	root	1.3	else if (len == 0)
261	root	1.1	return av_pop (av);
262			else
263			{
264			SV *top = av_pop (av);
265	root	1.3	SV *result = AvARRAY (av)[0];
266			AvARRAY (av)[0] = top;
267	root	1.5	downheap (av, cmp, cmp_data, len, 0, flags);
268	root	1.3	return result;
269			}
270			}
271	root	1.1
272	root	1.3	static SV *
273	root	1.5	splice_heap (AV av, f_cmp cmp, void cmp_data, int idx, int flags)
274	root	1.3	{
275			int len = AvFILLp (av);
276	root	1.1
277	root	1.6	if (idx < 0 \|\| idx > len)
278	root	1.3	return &PL_sv_undef;
279	root	1.6	else if (idx == len)
280			return av_pop (av); /* the last element */
281	root	1.3	else
282			{
283			SV *top = av_pop (av);
284			SV *result = AvARRAY (av)[idx];
285			AvARRAY (av)[idx] = top;
286	root	1.5	adjustheap (av, cmp, cmp_data, len, idx, flags);
287	root	1.1	return result;
288			}
289			}
290
291	root	1.3	static void
292	root	1.5	adjust_heap (AV av, f_cmp cmp, void cmp_data, int idx, int flags)
293	root	1.3	{
294	root	1.7	int len = AvFILLp (av);
295
296			if (idx > len)
297			croak ("Array::Heap::adjust_heap: index out of array bounds");
298
299			adjustheap (av, cmp, cmp_data, len + 1, idx, flags);
300	root	1.3	}
301
302	root	1.1	MODULE = Array::Heap PACKAGE = Array::Heap
303
304			void
305	root	1.3	make_heap (SV *heap)
306	root	1.1	PROTOTYPE: \@
307	root	1.5	ALIAS:
308			make_heap_idx = 1
309	root	1.1	CODE:
310	root	1.5	make_heap (array (heap), cmp_nv, 0, ix);
311	root	1.1
312			void
313	root	1.3	make_heap_lex (SV *heap)
314	root	1.1	PROTOTYPE: \@
315			CODE:
316	root	1.5	make_heap (array (heap), cmp_sv, 0, 0);
317	root	1.1
318			void
319	root	1.3	make_heap_cmp (SV cmp, SV heap)
320	root	1.1	PROTOTYPE: &\@
321			CODE:
322	root	1.3	{
323			dCMP;
324			CMP_PUSH (cmp);
325	root	1.5	make_heap (array (heap), cmp_custom, cmp_data, 0);
326	root	1.3	CMP_POP;
327			}
328	root	1.1
329			void
330	root	1.3	push_heap (SV *heap, ...)
331	root	1.1	PROTOTYPE: \@@
332	root	1.5	ALIAS:
333			push_heap_idx = 1
334	root	1.1	CODE:
335	root	1.5	push_heap (array (heap), cmp_nv, 0, &(ST(1)), items - 1, ix);
336	root	1.1
337			void
338	root	1.3	push_heap_lex (SV *heap, ...)
339	root	1.1	PROTOTYPE: \@@
340			CODE:
341	root	1.5	push_heap (array (heap), cmp_sv, 0, &(ST(1)), items - 1, 0);
342	root	1.1
343			void
344	root	1.3	push_heap_cmp (SV cmp, SV heap, ...)
345	root	1.1	PROTOTYPE: &\@@
346			CODE:
347	root	1.3	{
348	root	1.4	SV *st_2 = &(ST(2)); / multicall.h uses PUSHSTACK */
349	root	1.3	dCMP;
350			CMP_PUSH (cmp);
351	root	1.5	push_heap (array (heap), cmp_custom, cmp_data, st_2, items - 2, 0);
352	root	1.3	CMP_POP;
353			}
354	root	1.1
355			SV *
356	root	1.3	pop_heap (SV *heap)
357	root	1.1	PROTOTYPE: \@
358	root	1.5	ALIAS:
359			pop_heap_idx = 1
360	root	1.1	CODE:
361	root	1.5	RETVAL = pop_heap (array (heap), cmp_nv, 0, ix);
362	root	1.1	OUTPUT:
363			RETVAL
364
365			SV *
366	root	1.3	pop_heap_lex (SV *heap)
367	root	1.1	PROTOTYPE: \@
368			CODE:
369	root	1.5	RETVAL = pop_heap (array (heap), cmp_sv, 0, 0);
370	root	1.1	OUTPUT:
371			RETVAL
372
373			SV *
374	root	1.3	pop_heap_cmp (SV cmp, SV heap)
375	root	1.1	PROTOTYPE: &\@
376			CODE:
377	root	1.3	{
378			dCMP;
379			CMP_PUSH (cmp);
380	root	1.5	RETVAL = pop_heap (array (heap), cmp_custom, cmp_data, 0);
381	root	1.3	CMP_POP;
382			}
383			OUTPUT:
384			RETVAL
385
386			SV *
387			splice_heap (SV *heap, int idx)
388			PROTOTYPE: \@$
389	root	1.5	ALIAS:
390			splice_heap_idx = 1
391	root	1.3	CODE:
392	root	1.5	RETVAL = splice_heap (array (heap), cmp_nv, 0, idx, ix);
393	root	1.3	OUTPUT:
394			RETVAL
395
396			SV *
397			splice_heap_lex (SV *heap, int idx)
398			PROTOTYPE: \@$
399			CODE:
400	root	1.5	RETVAL = splice_heap (array (heap), cmp_sv, 0, idx, 0);
401	root	1.3	OUTPUT:
402			RETVAL
403
404			SV *
405			splice_heap_cmp (SV cmp, SV heap, int idx)
406			PROTOTYPE: &\@$
407			CODE:
408			{
409			dCMP;
410			CMP_PUSH (cmp);
411	root	1.5	RETVAL = splice_heap (array (heap), cmp_custom, cmp_data, idx, 0);
412	root	1.3	CMP_POP;
413			}
414	root	1.1	OUTPUT:
415			RETVAL
416
417	root	1.3	void
418			adjust_heap (SV *heap, int idx)
419			PROTOTYPE: \@$
420	root	1.5	ALIAS:
421			adjust_heap_idx = 1
422	root	1.3	CODE:
423	root	1.5	adjust_heap (array (heap), cmp_nv, 0, idx, ix);
424	root	1.3
425			void
426			adjust_heap_lex (SV *heap, int idx)
427			PROTOTYPE: \@$
428			CODE:
429	root	1.5	adjust_heap (array (heap), cmp_sv, 0, idx, 0);
430	root	1.3
431			void
432			adjust_heap_cmp (SV cmp, SV heap, int idx)
433			PROTOTYPE: &\@$
434			CODE:
435			{
436			dCMP;
437			CMP_PUSH (cmp);
438	root	1.5	adjust_heap (array (heap), cmp_custom, cmp_data, idx, 0);
439	root	1.3	CMP_POP;
440			}
441	root	1.1