[ViewVC] Diff of: cvs/Array-Heap/Heap.xs

Comparing Array-Heap/Heap.xs (file contents):
Revision 1.1 by root, Wed Jul 1 08:31:34 2009 UTC vs.
Revision 1.8 by root, Tue Jul 14 23:28:10 2015 UTC

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

Diff Legend

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

Comparing Array-Heap/Heap.xs (file contents): Revision 1.1 by root, Wed Jul 1 08:31:34 2009 UTC vs. Revision 1.8 by root, Tue Jul 14 23:28:10 2015 UTC

Diff Legend

Comparing Array-Heap/Heap.xs (file contents):
Revision 1.1 by root, Wed Jul 1 08:31:34 2009 UTC vs.
Revision 1.8 by root, Tue Jul 14 23:28:10 2015 UTC