1/*
2   +----------------------------------------------------------------------+
3   | PHP Version 7                                                        |
4   +----------------------------------------------------------------------+
5   | Copyright (c) 1997-2016 The PHP Group                                |
6   +----------------------------------------------------------------------+
7   | This source file is subject to version 3.01 of the PHP license,      |
8   | that is bundled with this package in the file LICENSE, and is        |
9   | available through the world-wide-web at the following url:           |
10   | http://www.php.net/license/3_01.txt                                  |
11   | If you did not receive a copy of the PHP license and are unable to   |
12   | obtain it through the world-wide-web, please send a note to          |
13   | license@php.net so we can mail you a copy immediately.               |
14   +----------------------------------------------------------------------+
15   | Authors: Andi Gutmans <andi@zend.com>                                |
16   |          Zeev Suraski <zeev@zend.com>                                |
17   |          Rasmus Lerdorf <rasmus@php.net>                             |
18   |          Andrei Zmievski <andrei@php.net>                            |
19   |          Stig Venaas <venaas@php.net>                                |
20   |          Jason Greene <jason@php.net>                                |
21   +----------------------------------------------------------------------+
22*/
23
24/* $Id$ */
25
26#include "php.h"
27#include "php_ini.h"
28#include <stdarg.h>
29#include <stdlib.h>
30#include <math.h>
31#include <time.h>
32#include <stdio.h>
33#if HAVE_STRING_H
34#include <string.h>
35#else
36#include <strings.h>
37#endif
38#ifdef PHP_WIN32
39#include "win32/unistd.h"
40#endif
41#include "zend_globals.h"
42#include "zend_interfaces.h"
43#include "php_globals.h"
44#include "php_array.h"
45#include "basic_functions.h"
46#include "php_string.h"
47#include "php_rand.h"
48#include "zend_smart_str.h"
49#include "ext/spl/spl_array.h"
50
51/* {{{ defines */
52#define EXTR_OVERWRITE			0
53#define EXTR_SKIP				1
54#define EXTR_PREFIX_SAME		2
55#define	EXTR_PREFIX_ALL			3
56#define	EXTR_PREFIX_INVALID		4
57#define	EXTR_PREFIX_IF_EXISTS	5
58#define	EXTR_IF_EXISTS			6
59
60#define EXTR_REFS				0x100
61
62#define CASE_LOWER				0
63#define CASE_UPPER				1
64
65#define DIFF_NORMAL			1
66#define DIFF_KEY			2
67#define DIFF_ASSOC			6
68#define DIFF_COMP_DATA_NONE    -1
69#define DIFF_COMP_DATA_INTERNAL 0
70#define DIFF_COMP_DATA_USER     1
71#define DIFF_COMP_KEY_INTERNAL  0
72#define DIFF_COMP_KEY_USER      1
73
74#define INTERSECT_NORMAL		1
75#define INTERSECT_KEY			2
76#define INTERSECT_ASSOC			6
77#define INTERSECT_COMP_DATA_NONE    -1
78#define INTERSECT_COMP_DATA_INTERNAL 0
79#define INTERSECT_COMP_DATA_USER     1
80#define INTERSECT_COMP_KEY_INTERNAL  0
81#define INTERSECT_COMP_KEY_USER      1
82/* }}} */
83
84ZEND_DECLARE_MODULE_GLOBALS(array)
85
86/* {{{ php_array_init_globals
87*/
88static void php_array_init_globals(zend_array_globals *array_globals)
89{
90	memset(array_globals, 0, sizeof(zend_array_globals));
91}
92/* }}} */
93
94PHP_MINIT_FUNCTION(array) /* {{{ */
95{
96	ZEND_INIT_MODULE_GLOBALS(array, php_array_init_globals, NULL);
97
98	REGISTER_LONG_CONSTANT("EXTR_OVERWRITE", EXTR_OVERWRITE, CONST_CS | CONST_PERSISTENT);
99	REGISTER_LONG_CONSTANT("EXTR_SKIP", EXTR_SKIP, CONST_CS | CONST_PERSISTENT);
100	REGISTER_LONG_CONSTANT("EXTR_PREFIX_SAME", EXTR_PREFIX_SAME, CONST_CS | CONST_PERSISTENT);
101	REGISTER_LONG_CONSTANT("EXTR_PREFIX_ALL", EXTR_PREFIX_ALL, CONST_CS | CONST_PERSISTENT);
102	REGISTER_LONG_CONSTANT("EXTR_PREFIX_INVALID", EXTR_PREFIX_INVALID, CONST_CS | CONST_PERSISTENT);
103	REGISTER_LONG_CONSTANT("EXTR_PREFIX_IF_EXISTS", EXTR_PREFIX_IF_EXISTS, CONST_CS | CONST_PERSISTENT);
104	REGISTER_LONG_CONSTANT("EXTR_IF_EXISTS", EXTR_IF_EXISTS, CONST_CS | CONST_PERSISTENT);
105	REGISTER_LONG_CONSTANT("EXTR_REFS", EXTR_REFS, CONST_CS | CONST_PERSISTENT);
106
107	REGISTER_LONG_CONSTANT("SORT_ASC", PHP_SORT_ASC, CONST_CS | CONST_PERSISTENT);
108	REGISTER_LONG_CONSTANT("SORT_DESC", PHP_SORT_DESC, CONST_CS | CONST_PERSISTENT);
109
110	REGISTER_LONG_CONSTANT("SORT_REGULAR", PHP_SORT_REGULAR, CONST_CS | CONST_PERSISTENT);
111	REGISTER_LONG_CONSTANT("SORT_NUMERIC", PHP_SORT_NUMERIC, CONST_CS | CONST_PERSISTENT);
112	REGISTER_LONG_CONSTANT("SORT_STRING", PHP_SORT_STRING, CONST_CS | CONST_PERSISTENT);
113	REGISTER_LONG_CONSTANT("SORT_LOCALE_STRING", PHP_SORT_LOCALE_STRING, CONST_CS | CONST_PERSISTENT);
114	REGISTER_LONG_CONSTANT("SORT_NATURAL", PHP_SORT_NATURAL, CONST_CS | CONST_PERSISTENT);
115	REGISTER_LONG_CONSTANT("SORT_FLAG_CASE", PHP_SORT_FLAG_CASE, CONST_CS | CONST_PERSISTENT);
116
117	REGISTER_LONG_CONSTANT("CASE_LOWER", CASE_LOWER, CONST_CS | CONST_PERSISTENT);
118	REGISTER_LONG_CONSTANT("CASE_UPPER", CASE_UPPER, CONST_CS | CONST_PERSISTENT);
119
120	REGISTER_LONG_CONSTANT("COUNT_NORMAL", COUNT_NORMAL, CONST_CS | CONST_PERSISTENT);
121	REGISTER_LONG_CONSTANT("COUNT_RECURSIVE", COUNT_RECURSIVE, CONST_CS | CONST_PERSISTENT);
122
123	REGISTER_LONG_CONSTANT("ARRAY_FILTER_USE_BOTH", ARRAY_FILTER_USE_BOTH, CONST_CS | CONST_PERSISTENT);
124	REGISTER_LONG_CONSTANT("ARRAY_FILTER_USE_KEY", ARRAY_FILTER_USE_KEY, CONST_CS | CONST_PERSISTENT);
125
126	return SUCCESS;
127}
128/* }}} */
129
130PHP_MSHUTDOWN_FUNCTION(array) /* {{{ */
131{
132#ifdef ZTS
133	ts_free_id(array_globals_id);
134#endif
135
136	return SUCCESS;
137}
138/* }}} */
139
140static int php_array_key_compare(const void *a, const void *b) /* {{{ */
141{
142	Bucket *f = (Bucket *) a;
143	Bucket *s = (Bucket *) b;
144	zend_uchar t;
145	zend_long l1, l2;
146	double d;
147
148	if (f->key == NULL) {
149		if (s->key == NULL) {
150			return (zend_long)f->h > (zend_long)s->h ? 1 : -1;
151		} else {
152			l1 = (zend_long)f->h;
153			t = is_numeric_string(s->key->val, s->key->len, &l2, &d, 1);
154			if (t == IS_LONG) {
155				/* pass */
156			} else if (t == IS_DOUBLE) {
157				return ZEND_NORMALIZE_BOOL((double)l1 - d);
158			} else {
159				l2 = 0;
160			}
161		}
162	} else {
163		if (s->key) {
164			return zendi_smart_strcmp(f->key, s->key);
165		} else {
166			l2 = (zend_long)s->h;
167			t = is_numeric_string(f->key->val, f->key->len, &l1, &d, 1);
168			if (t == IS_LONG) {
169				/* pass */
170			} else if (t == IS_DOUBLE) {
171				return ZEND_NORMALIZE_BOOL(d - (double)l2);
172			} else {
173				l1 = 0;
174			}
175		}
176	}
177	return l1 > l2 ? 1 : (l1 < l2 ? -1 : 0);
178}
179/* }}} */
180
181static int php_array_reverse_key_compare(const void *a, const void *b) /* {{{ */
182{
183	return php_array_key_compare(b, a);
184}
185/* }}} */
186
187static int php_array_key_compare_numeric(const void *a, const void *b) /* {{{ */
188{
189	Bucket *f = (Bucket *) a;
190	Bucket *s = (Bucket *) b;
191
192	if (f->key == NULL && s->key == NULL) {
193		return (zend_long)f->h > (zend_long)s->h ? 1 : -1;
194	} else {
195		double d1, d2;
196		if (f->key) {
197			d1 = zend_strtod(f->key->val, NULL);
198		} else {
199			d1 = (double)(zend_long)f->h;
200		}
201		if (s->key) {
202			d2 = zend_strtod(s->key->val, NULL);
203		} else {
204			d2 = (double)(zend_long)s->h;
205		}
206		return ZEND_NORMALIZE_BOOL(d1 - d2);
207	}
208}
209/* }}} */
210
211static int php_array_reverse_key_compare_numeric(const void *a, const void *b) /* {{{ */
212{
213	return php_array_key_compare_numeric(b, a);
214}
215/* }}} */
216
217static int php_array_key_compare_string_case(const void *a, const void *b) /* {{{ */
218{
219	Bucket *f = (Bucket *) a;
220	Bucket *s = (Bucket *) b;
221	char *s1, *s2;
222	size_t l1, l2;
223	char buf1[MAX_LENGTH_OF_LONG + 1];
224	char buf2[MAX_LENGTH_OF_LONG + 1];
225
226	if (f->key) {
227		s1 = f->key->val;
228		l1 = f->key->len;
229	} else {
230		s1 = zend_print_long_to_buf(buf1 + sizeof(buf1) - 1, f->h);
231		l1 = buf1 + sizeof(buf1) - 1 - s1;
232	}
233	if (s->key) {
234		s2 = s->key->val;
235		l2 = s->key->len;
236	} else {
237		s2 = zend_print_long_to_buf(buf2 + sizeof(buf2) - 1, s->h);
238		l2 = buf2 + sizeof(buf2) - 1 - s1;
239	}
240	return zend_binary_strcasecmp_l(s1, l1, s2, l2);
241}
242/* }}} */
243
244static int php_array_reverse_key_compare_string_case(const void *a, const void *b) /* {{{ */
245{
246	return php_array_key_compare_string_case(b, a);
247}
248/* }}} */
249
250static int php_array_key_compare_string(const void *a, const void *b) /* {{{ */
251{
252	Bucket *f = (Bucket *) a;
253	Bucket *s = (Bucket *) b;
254	char *s1, *s2;
255	size_t l1, l2;
256	char buf1[MAX_LENGTH_OF_LONG + 1];
257	char buf2[MAX_LENGTH_OF_LONG + 1];
258
259	if (f->key) {
260		s1 = f->key->val;
261		l1 = f->key->len;
262	} else {
263		s1 = zend_print_long_to_buf(buf1 + sizeof(buf1) - 1, f->h);
264		l1 = buf1 + sizeof(buf1) - 1 - s1;
265	}
266	if (s->key) {
267		s2 = s->key->val;
268		l2 = s->key->len;
269	} else {
270		s2 = zend_print_long_to_buf(buf2 + sizeof(buf2) - 1, s->h);
271		l2 = buf2 + sizeof(buf2) - 1 - s2;
272	}
273	return zend_binary_strcmp(s1, l1, s2, l2);
274}
275/* }}} */
276
277static int php_array_reverse_key_compare_string(const void *a, const void *b) /* {{{ */
278{
279	return php_array_key_compare_string(b, a);
280}
281/* }}} */
282
283static int php_array_key_compare_string_natural_general(const void *a, const void *b, int fold_case) /* {{{ */
284{
285	Bucket *f = (Bucket *) a;
286	Bucket *s = (Bucket *) b;
287	char *s1, *s2;
288	size_t l1, l2;
289	char buf1[MAX_LENGTH_OF_LONG + 1];
290	char buf2[MAX_LENGTH_OF_LONG + 1];
291
292	if (f->key) {
293		s1 = f->key->val;
294		l1 = f->key->len;
295	} else {
296		s1 = zend_print_long_to_buf(buf1 + sizeof(buf1) - 1, f->h);
297		l1 = buf1 + sizeof(buf1) - 1 - s1;
298	}
299	if (s->key) {
300		s2 = s->key->val;
301		l2 = s->key->len;
302	} else {
303		s2 = zend_print_long_to_buf(buf2 + sizeof(buf2) - 1, s->h);
304		l2 = buf2 + sizeof(buf2) - 1 - s1;
305	}
306	return strnatcmp_ex(s1, l1, s2, l2, fold_case);
307}
308/* }}} */
309
310static int php_array_key_compare_string_natural_case(const void *a, const void *b) /* {{{ */
311{
312	return php_array_key_compare_string_natural_general(a, b, 1);
313}
314/* }}} */
315
316static int php_array_reverse_key_compare_string_natural_case(const void *a, const void *b) /* {{{ */
317{
318	return php_array_key_compare_string_natural_general(b, a, 1);
319}
320/* }}} */
321
322static int php_array_key_compare_string_natural(const void *a, const void *b) /* {{{ */
323{
324	return php_array_key_compare_string_natural_general(a, b, 0);
325}
326/* }}} */
327
328static int php_array_reverse_key_compare_string_natural(const void *a, const void *b) /* {{{ */
329{
330	return php_array_key_compare_string_natural_general(b, a, 0);
331}
332/* }}} */
333
334#if HAVE_STRCOLL
335static int php_array_key_compare_string_locale(const void *a, const void *b) /* {{{ */
336{
337	Bucket *f = (Bucket *) a;
338	Bucket *s = (Bucket *) b;
339	char *s1, *s2;
340	char buf1[MAX_LENGTH_OF_LONG + 1];
341	char buf2[MAX_LENGTH_OF_LONG + 1];
342
343	if (f->key) {
344		s1 = f->key->val;
345	} else {
346		s1 = zend_print_long_to_buf(buf1 + sizeof(buf1) - 1, f->h);
347	}
348	if (s->key) {
349		s2 = s->key->val;
350	} else {
351		s2 = zend_print_long_to_buf(buf2 + sizeof(buf2) - 1, s->h);
352	}
353	return strcoll(s1, s2);
354}
355/* }}} */
356
357static int php_array_reverse_key_compare_string_locale(const void *a, const void *b) /* {{{ */
358{
359	return php_array_key_compare_string_locale(b, a);
360}
361/* }}} */
362#endif
363
364/* Numbers are always smaller than strings int this function as it
365 * anyway doesn't make much sense to compare two different data types.
366 * This keeps it consistent and simple.
367 *
368 * This is not correct any more, depends on what compare_func is set to.
369 */
370static int php_array_data_compare(const void *a, const void *b) /* {{{ */
371{
372	Bucket *f;
373	Bucket *s;
374	zval result;
375	zval *first;
376	zval *second;
377
378	f = (Bucket *) a;
379	s = (Bucket *) b;
380
381	first = &f->val;
382	second = &s->val;
383
384	if (UNEXPECTED(Z_TYPE_P(first) == IS_INDIRECT)) {
385		first = Z_INDIRECT_P(first);
386	}
387	if (UNEXPECTED(Z_TYPE_P(second) == IS_INDIRECT)) {
388		second = Z_INDIRECT_P(second);
389	}
390	if (compare_function(&result, first, second) == FAILURE) {
391		return 0;
392	}
393
394	ZEND_ASSERT(Z_TYPE(result) == IS_LONG);
395	return Z_LVAL(result);
396}
397/* }}} */
398
399static int php_array_reverse_data_compare(const void *a, const void *b) /* {{{ */
400{
401	return php_array_data_compare(a, b) * -1;
402}
403/* }}} */
404
405static int php_array_data_compare_numeric(const void *a, const void *b) /* {{{ */
406{
407	Bucket *f;
408	Bucket *s;
409	zval *first;
410	zval *second;
411
412	f = (Bucket *) a;
413	s = (Bucket *) b;
414
415	first = &f->val;
416	second = &s->val;
417
418	if (UNEXPECTED(Z_TYPE_P(first) == IS_INDIRECT)) {
419		first = Z_INDIRECT_P(first);
420	}
421	if (UNEXPECTED(Z_TYPE_P(second) == IS_INDIRECT)) {
422		second = Z_INDIRECT_P(second);
423	}
424
425	return numeric_compare_function(first, second);
426}
427/* }}} */
428
429static int php_array_reverse_data_compare_numeric(const void *a, const void *b) /* {{{ */
430{
431	return php_array_data_compare_numeric(b, a);
432}
433/* }}} */
434
435static int php_array_data_compare_string_case(const void *a, const void *b) /* {{{ */
436{
437	Bucket *f;
438	Bucket *s;
439	zval *first;
440	zval *second;
441
442	f = (Bucket *) a;
443	s = (Bucket *) b;
444
445	first = &f->val;
446	second = &s->val;
447
448	if (UNEXPECTED(Z_TYPE_P(first) == IS_INDIRECT)) {
449		first = Z_INDIRECT_P(first);
450	}
451	if (UNEXPECTED(Z_TYPE_P(second) == IS_INDIRECT)) {
452		second = Z_INDIRECT_P(second);
453	}
454
455	return string_case_compare_function(first, second);
456}
457/* }}} */
458
459static int php_array_reverse_data_compare_string_case(const void *a, const void *b) /* {{{ */
460{
461	return php_array_data_compare_string_case(b, a);
462}
463/* }}} */
464
465static int php_array_data_compare_string(const void *a, const void *b) /* {{{ */
466{
467	Bucket *f;
468	Bucket *s;
469	zval *first;
470	zval *second;
471
472	f = (Bucket *) a;
473	s = (Bucket *) b;
474
475	first = &f->val;
476	second = &s->val;
477
478	if (UNEXPECTED(Z_TYPE_P(first) == IS_INDIRECT)) {
479		first = Z_INDIRECT_P(first);
480	}
481	if (UNEXPECTED(Z_TYPE_P(second) == IS_INDIRECT)) {
482		second = Z_INDIRECT_P(second);
483	}
484
485	return string_compare_function(first, second);
486}
487/* }}} */
488
489static int php_array_reverse_data_compare_string(const void *a, const void *b) /* {{{ */
490{
491	return php_array_data_compare_string(b, a);
492}
493/* }}} */
494
495static int php_array_natural_general_compare(const void *a, const void *b, int fold_case) /* {{{ */
496{
497	Bucket *f = (Bucket *) a;
498	Bucket *s = (Bucket *) b;
499	zend_string *str1 = zval_get_string(&f->val);
500	zend_string *str2 = zval_get_string(&s->val);
501
502	int result = strnatcmp_ex(ZSTR_VAL(str1), ZSTR_LEN(str1), ZSTR_VAL(str2), ZSTR_LEN(str2), fold_case);
503
504	zend_string_release(str1);
505	zend_string_release(str2);
506	return result;
507}
508/* }}} */
509
510static int php_array_natural_compare(const void *a, const void *b) /* {{{ */
511{
512	return php_array_natural_general_compare(a, b, 0);
513}
514/* }}} */
515
516static int php_array_reverse_natural_compare(const void *a, const void *b) /* {{{ */
517{
518	return php_array_natural_general_compare(b, a, 0);
519}
520/* }}} */
521
522static int php_array_natural_case_compare(const void *a, const void *b) /* {{{ */
523{
524	return php_array_natural_general_compare(a, b, 1);
525}
526/* }}} */
527
528static int php_array_reverse_natural_case_compare(const void *a, const void *b) /* {{{ */
529{
530	return php_array_natural_general_compare(b, a, 1);
531}
532/* }}} */
533
534#if HAVE_STRCOLL
535static int php_array_data_compare_string_locale(const void *a, const void *b) /* {{{ */
536{
537	Bucket *f;
538	Bucket *s;
539	zval *first;
540	zval *second;
541
542	f = (Bucket *) a;
543	s = (Bucket *) b;
544
545	first = &f->val;
546	second = &s->val;
547
548	if (UNEXPECTED(Z_TYPE_P(first) == IS_INDIRECT)) {
549		first = Z_INDIRECT_P(first);
550	}
551	if (UNEXPECTED(Z_TYPE_P(second) == IS_INDIRECT)) {
552		second = Z_INDIRECT_P(second);
553	}
554
555	return string_locale_compare_function(first, second);
556}
557/* }}} */
558
559static int php_array_reverse_data_compare_string_locale(const void *a, const void *b) /* {{{ */
560{
561	return php_array_data_compare_string_locale(b, a);
562}
563/* }}} */
564#endif
565
566static compare_func_t php_get_key_compare_func(zend_long sort_type, int reverse) /* {{{ */
567{
568	switch (sort_type & ~PHP_SORT_FLAG_CASE) {
569		case PHP_SORT_NUMERIC:
570			if (reverse) {
571				return php_array_reverse_key_compare_numeric;
572			} else {
573				return php_array_key_compare_numeric;
574			}
575			break;
576
577		case PHP_SORT_STRING:
578			if (sort_type & PHP_SORT_FLAG_CASE) {
579				if (reverse) {
580					return php_array_reverse_key_compare_string_case;
581				} else {
582					return php_array_key_compare_string_case;
583				}
584			} else {
585				if (reverse) {
586					return php_array_reverse_key_compare_string;
587				} else {
588					return php_array_key_compare_string;
589				}
590			}
591			break;
592
593		case PHP_SORT_NATURAL:
594			if (sort_type & PHP_SORT_FLAG_CASE) {
595				if (reverse) {
596					return php_array_reverse_key_compare_string_natural_case;
597				} else {
598					return php_array_key_compare_string_natural_case;
599				}
600			} else {
601				if (reverse) {
602					return php_array_reverse_key_compare_string_natural;
603				} else {
604					return php_array_key_compare_string_natural;
605				}
606			}
607			break;
608
609#if HAVE_STRCOLL
610		case PHP_SORT_LOCALE_STRING:
611			if (reverse) {
612				return php_array_reverse_key_compare_string_locale;
613			} else {
614				return php_array_key_compare_string_locale;
615			}
616			break;
617#endif
618
619		case PHP_SORT_REGULAR:
620		default:
621			if (reverse) {
622				return php_array_reverse_key_compare;
623			} else {
624				return php_array_key_compare;
625			}
626			break;
627	}
628	return NULL;
629}
630/* }}} */
631
632static compare_func_t php_get_data_compare_func(zend_long sort_type, int reverse) /* {{{ */
633{
634	switch (sort_type & ~PHP_SORT_FLAG_CASE) {
635		case PHP_SORT_NUMERIC:
636			if (reverse) {
637				return php_array_reverse_data_compare_numeric;
638			} else {
639				return php_array_data_compare_numeric;
640			}
641			break;
642
643		case PHP_SORT_STRING:
644			if (sort_type & PHP_SORT_FLAG_CASE) {
645				if (reverse) {
646					return php_array_reverse_data_compare_string_case;
647				} else {
648					return php_array_data_compare_string_case;
649				}
650			} else {
651				if (reverse) {
652					return php_array_reverse_data_compare_string;
653				} else {
654					return php_array_data_compare_string;
655				}
656			}
657			break;
658
659		case PHP_SORT_NATURAL:
660			if (sort_type & PHP_SORT_FLAG_CASE) {
661				if (reverse) {
662					return php_array_reverse_natural_case_compare;
663				} else {
664					return php_array_natural_case_compare;
665				}
666			} else {
667				if (reverse) {
668					return php_array_reverse_natural_compare;
669				} else {
670					return php_array_natural_compare;
671				}
672			}
673			break;
674
675#if HAVE_STRCOLL
676		case PHP_SORT_LOCALE_STRING:
677			if (reverse) {
678				return php_array_reverse_data_compare_string_locale;
679			} else {
680				return php_array_data_compare_string_locale;
681			}
682			break;
683#endif
684
685		case PHP_SORT_REGULAR:
686		default:
687			if (reverse) {
688				return php_array_reverse_data_compare;
689			} else {
690				return php_array_data_compare;
691			}
692			break;
693	}
694	return NULL;
695}
696/* }}} */
697
698/* {{{ proto bool krsort(array &array_arg [, int sort_flags])
699   Sort an array by key value in reverse order */
700PHP_FUNCTION(krsort)
701{
702	zval *array;
703	zend_long sort_type = PHP_SORT_REGULAR;
704	compare_func_t cmp;
705
706#ifndef FAST_ZPP
707	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a/|l", &array, &sort_type) == FAILURE) {
708		RETURN_FALSE;
709	}
710#else
711	ZEND_PARSE_PARAMETERS_START(1, 2)
712		Z_PARAM_ARRAY_EX(array, 0, 1)
713		Z_PARAM_OPTIONAL
714		Z_PARAM_LONG(sort_type)
715	ZEND_PARSE_PARAMETERS_END_EX(RETURN_FALSE);
716#endif
717
718	cmp = php_get_key_compare_func(sort_type, 1);
719
720	if (zend_hash_sort(Z_ARRVAL_P(array), cmp, 0) == FAILURE) {
721		RETURN_FALSE;
722	}
723	RETURN_TRUE;
724}
725/* }}} */
726
727/* {{{ proto bool ksort(array &array_arg [, int sort_flags])
728   Sort an array by key */
729PHP_FUNCTION(ksort)
730{
731	zval *array;
732	zend_long sort_type = PHP_SORT_REGULAR;
733	compare_func_t cmp;
734
735#ifndef FAST_ZPP
736	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a/|l", &array, &sort_type) == FAILURE) {
737		RETURN_FALSE;
738	}
739#else
740	ZEND_PARSE_PARAMETERS_START(1, 2)
741		Z_PARAM_ARRAY_EX(array, 0, 1)
742		Z_PARAM_OPTIONAL
743		Z_PARAM_LONG(sort_type)
744	ZEND_PARSE_PARAMETERS_END_EX(RETURN_FALSE);
745#endif
746
747	cmp = php_get_key_compare_func(sort_type, 0);
748
749	if (zend_hash_sort(Z_ARRVAL_P(array), cmp, 0) == FAILURE) {
750		RETURN_FALSE;
751	}
752	RETURN_TRUE;
753}
754/* }}} */
755
756PHPAPI zend_long php_count_recursive(zval *array, zend_long mode) /* {{{ */
757{
758	zend_long cnt = 0;
759	zval *element;
760
761	if (Z_TYPE_P(array) == IS_ARRAY) {
762		if (Z_ARRVAL_P(array)->u.v.nApplyCount > 1) {
763			php_error_docref(NULL, E_WARNING, "recursion detected");
764			return 0;
765		}
766
767		cnt = zend_array_count(Z_ARRVAL_P(array));
768		if (mode == COUNT_RECURSIVE) {
769		    if (ZEND_HASH_APPLY_PROTECTION(Z_ARRVAL_P(array))) {
770				Z_ARRVAL_P(array)->u.v.nApplyCount++;
771			}
772			ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(array), element) {
773				ZVAL_DEREF(element);
774				cnt += php_count_recursive(element, COUNT_RECURSIVE);
775			} ZEND_HASH_FOREACH_END();
776		    if (ZEND_HASH_APPLY_PROTECTION(Z_ARRVAL_P(array))) {
777				Z_ARRVAL_P(array)->u.v.nApplyCount--;
778			}
779		}
780	}
781
782	return cnt;
783}
784/* }}} */
785
786/* {{{ proto int count(mixed var [, int mode])
787   Count the number of elements in a variable (usually an array) */
788PHP_FUNCTION(count)
789{
790	zval *array;
791	zend_long mode = COUNT_NORMAL;
792	zend_long cnt;
793	zval *element;
794
795#ifndef FAST_ZPP
796	if (zend_parse_parameters(ZEND_NUM_ARGS(), "z|l", &array, &mode) == FAILURE) {
797		return;
798	}
799#else
800	ZEND_PARSE_PARAMETERS_START(1, 2)
801		Z_PARAM_ZVAL(array)
802		Z_PARAM_OPTIONAL
803		Z_PARAM_LONG(mode)
804	ZEND_PARSE_PARAMETERS_END();
805#endif
806
807	switch (Z_TYPE_P(array)) {
808		case IS_NULL:
809			RETURN_LONG(0);
810			break;
811		case IS_ARRAY:
812			cnt = zend_array_count(Z_ARRVAL_P(array));
813			if (mode == COUNT_RECURSIVE) {
814				ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(array), element) {
815					ZVAL_DEREF(element);
816					cnt += php_count_recursive(element, COUNT_RECURSIVE);
817				} ZEND_HASH_FOREACH_END();
818			}
819			RETURN_LONG(cnt);
820			break;
821		case IS_OBJECT: {
822			zval retval;
823			/* first, we check if the handler is defined */
824			if (Z_OBJ_HT_P(array)->count_elements) {
825				RETVAL_LONG(1);
826				if (SUCCESS == Z_OBJ_HT(*array)->count_elements(array, &Z_LVAL_P(return_value))) {
827					return;
828				}
829			}
830			/* if not and the object implements Countable we call its count() method */
831			if (instanceof_function(Z_OBJCE_P(array), spl_ce_Countable)) {
832				zend_call_method_with_0_params(array, NULL, NULL, "count", &retval);
833				if (Z_TYPE(retval) != IS_UNDEF) {
834					RETVAL_LONG(zval_get_long(&retval));
835					zval_ptr_dtor(&retval);
836				}
837				return;
838			}
839		}
840		default:
841			RETURN_LONG(1);
842			break;
843	}
844}
845/* }}} */
846
847static void php_natsort(INTERNAL_FUNCTION_PARAMETERS, int fold_case) /* {{{ */
848{
849	zval *array;
850
851	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a/", &array) == FAILURE) {
852		return;
853	}
854
855	if (fold_case) {
856		if (zend_hash_sort(Z_ARRVAL_P(array), php_array_natural_case_compare, 0) == FAILURE) {
857			return;
858		}
859	} else {
860		if (zend_hash_sort(Z_ARRVAL_P(array), php_array_natural_compare, 0) == FAILURE) {
861			return;
862		}
863	}
864
865	RETURN_TRUE;
866}
867/* }}} */
868
869/* {{{ proto void natsort(array &array_arg)
870   Sort an array using natural sort */
871PHP_FUNCTION(natsort)
872{
873	php_natsort(INTERNAL_FUNCTION_PARAM_PASSTHRU, 0);
874}
875/* }}} */
876
877/* {{{ proto void natcasesort(array &array_arg)
878   Sort an array using case-insensitive natural sort */
879PHP_FUNCTION(natcasesort)
880{
881	php_natsort(INTERNAL_FUNCTION_PARAM_PASSTHRU, 1);
882}
883/* }}} */
884
885/* {{{ proto bool asort(array &array_arg [, int sort_flags])
886   Sort an array and maintain index association */
887PHP_FUNCTION(asort)
888{
889	zval *array;
890	zend_long sort_type = PHP_SORT_REGULAR;
891	compare_func_t cmp;
892
893	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a/|l", &array, &sort_type) == FAILURE) {
894		RETURN_FALSE;
895	}
896
897	cmp = php_get_data_compare_func(sort_type, 0);
898
899	if (zend_hash_sort(Z_ARRVAL_P(array), cmp, 0) == FAILURE) {
900		RETURN_FALSE;
901	}
902	RETURN_TRUE;
903}
904/* }}} */
905
906/* {{{ proto bool arsort(array &array_arg [, int sort_flags])
907   Sort an array in reverse order and maintain index association */
908PHP_FUNCTION(arsort)
909{
910	zval *array;
911	zend_long sort_type = PHP_SORT_REGULAR;
912	compare_func_t cmp;
913
914	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a/|l", &array, &sort_type) == FAILURE) {
915		RETURN_FALSE;
916	}
917
918	cmp = php_get_data_compare_func(sort_type, 1);
919
920	if (zend_hash_sort(Z_ARRVAL_P(array), cmp, 0) == FAILURE) {
921		RETURN_FALSE;
922	}
923	RETURN_TRUE;
924}
925/* }}} */
926
927/* {{{ proto bool sort(array &array_arg [, int sort_flags])
928   Sort an array */
929PHP_FUNCTION(sort)
930{
931	zval *array;
932	zend_long sort_type = PHP_SORT_REGULAR;
933	compare_func_t cmp;
934
935	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a/|l", &array, &sort_type) == FAILURE) {
936		RETURN_FALSE;
937	}
938
939	cmp = php_get_data_compare_func(sort_type, 0);
940
941	if (zend_hash_sort(Z_ARRVAL_P(array), cmp, 1) == FAILURE) {
942		RETURN_FALSE;
943	}
944	RETURN_TRUE;
945}
946/* }}} */
947
948/* {{{ proto bool rsort(array &array_arg [, int sort_flags])
949   Sort an array in reverse order */
950PHP_FUNCTION(rsort)
951{
952	zval *array;
953	zend_long sort_type = PHP_SORT_REGULAR;
954	compare_func_t cmp;
955
956	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a/|l", &array, &sort_type) == FAILURE) {
957		RETURN_FALSE;
958	}
959
960	cmp = php_get_data_compare_func(sort_type, 1);
961
962	if (zend_hash_sort(Z_ARRVAL_P(array), cmp, 1) == FAILURE) {
963		RETURN_FALSE;
964	}
965	RETURN_TRUE;
966}
967/* }}} */
968
969static int php_array_user_compare(const void *a, const void *b) /* {{{ */
970{
971	Bucket *f;
972	Bucket *s;
973	zval args[2];
974	zval retval;
975
976	f = (Bucket *) a;
977	s = (Bucket *) b;
978
979	ZVAL_COPY(&args[0], &f->val);
980	ZVAL_COPY(&args[1], &s->val);
981
982	BG(user_compare_fci).param_count = 2;
983	BG(user_compare_fci).params = args;
984	BG(user_compare_fci).retval = &retval;
985	BG(user_compare_fci).no_separation = 0;
986	if (zend_call_function(&BG(user_compare_fci), &BG(user_compare_fci_cache)) == SUCCESS && Z_TYPE(retval) != IS_UNDEF) {
987		zend_long ret = zval_get_long(&retval);
988		zval_ptr_dtor(&retval);
989		zval_ptr_dtor(&args[1]);
990		zval_ptr_dtor(&args[0]);
991		return ret < 0 ? -1 : ret > 0 ? 1 : 0;
992	} else {
993		zval_ptr_dtor(&args[1]);
994		zval_ptr_dtor(&args[0]);
995		return 0;
996	}
997}
998/* }}} */
999
1000/* check if comparison function is valid */
1001#define PHP_ARRAY_CMP_FUNC_CHECK(func_name)	\
1002	if (!zend_is_callable(*func_name, 0, NULL)) {	\
1003		php_error_docref(NULL, E_WARNING, "Invalid comparison function");	\
1004		BG(user_compare_fci) = old_user_compare_fci; \
1005		BG(user_compare_fci_cache) = old_user_compare_fci_cache; \
1006		RETURN_FALSE;	\
1007	}	\
1008
1009	/* Clear FCI cache otherwise : for example the same or other array with
1010	 * (partly) the same key values has been sorted with uasort() or
1011	 * other sorting function the comparison is cached, however the name
1012	 * of the function for comparison is not respected. see bug #28739 AND #33295
1013	 *
1014	 * Following defines will assist in backup / restore values. */
1015
1016#define PHP_ARRAY_CMP_FUNC_VARS \
1017	zend_fcall_info old_user_compare_fci; \
1018	zend_fcall_info_cache old_user_compare_fci_cache \
1019
1020#define PHP_ARRAY_CMP_FUNC_BACKUP() \
1021	old_user_compare_fci = BG(user_compare_fci); \
1022	old_user_compare_fci_cache = BG(user_compare_fci_cache); \
1023	BG(user_compare_fci_cache) = empty_fcall_info_cache; \
1024
1025#define PHP_ARRAY_CMP_FUNC_RESTORE() \
1026	BG(user_compare_fci) = old_user_compare_fci; \
1027	BG(user_compare_fci_cache) = old_user_compare_fci_cache; \
1028
1029static void php_usort(INTERNAL_FUNCTION_PARAMETERS, compare_func_t compare_func, zend_bool renumber) /* {{{ */
1030{
1031	zval *array;
1032	zend_refcounted *arr;
1033	zend_bool retval;
1034	PHP_ARRAY_CMP_FUNC_VARS;
1035
1036	PHP_ARRAY_CMP_FUNC_BACKUP();
1037
1038	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a/f", &array, &BG(user_compare_fci), &BG(user_compare_fci_cache)) == FAILURE) {
1039		PHP_ARRAY_CMP_FUNC_RESTORE();
1040		return;
1041	}
1042
1043	/* Increase reference counter, so the attempts to modify the array in user
1044	 * comparison function will create a copy of array and won't affect the
1045	 * original array. The fact of modification is detected by comparing the
1046	 * zend_array pointer. The result of sorting in such case is undefined and
1047	 * the function returns FALSE.
1048	 */
1049	Z_ADDREF_P(array);
1050	arr = Z_COUNTED_P(array);
1051
1052	retval = zend_hash_sort(Z_ARRVAL_P(array), compare_func, renumber) != FAILURE;
1053
1054	if (arr != Z_COUNTED_P(array)) {
1055		php_error_docref(NULL, E_WARNING, "Array was modified by the user comparison function");
1056		if (--GC_REFCOUNT(arr) <= 0) {
1057			_zval_dtor_func(arr ZEND_FILE_LINE_CC);
1058		}
1059		retval = 0;
1060	} else {
1061		Z_DELREF_P(array);
1062	}
1063
1064	PHP_ARRAY_CMP_FUNC_RESTORE();
1065	RETURN_BOOL(retval);
1066}
1067/* }}} */
1068
1069/* {{{ proto bool usort(array array_arg, string cmp_function)
1070   Sort an array by values using a user-defined comparison function */
1071PHP_FUNCTION(usort)
1072{
1073	php_usort(INTERNAL_FUNCTION_PARAM_PASSTHRU, php_array_user_compare, 1);
1074}
1075/* }}} */
1076
1077/* {{{ proto bool uasort(array array_arg, string cmp_function)
1078   Sort an array with a user-defined comparison function and maintain index association */
1079PHP_FUNCTION(uasort)
1080{
1081	php_usort(INTERNAL_FUNCTION_PARAM_PASSTHRU, php_array_user_compare, 0);
1082}
1083/* }}} */
1084
1085static int php_array_user_key_compare(const void *a, const void *b) /* {{{ */
1086{
1087	Bucket *f;
1088	Bucket *s;
1089	zval args[2];
1090	zval retval;
1091	zend_long result;
1092
1093	ZVAL_NULL(&args[0]);
1094	ZVAL_NULL(&args[1]);
1095
1096	f = (Bucket *) a;
1097	s = (Bucket *) b;
1098
1099	if (f->key == NULL) {
1100		ZVAL_LONG(&args[0], f->h);
1101	} else {
1102		ZVAL_STR_COPY(&args[0], f->key);
1103	}
1104	if (s->key == NULL) {
1105		ZVAL_LONG(&args[1], s->h);
1106	} else {
1107		ZVAL_STR_COPY(&args[1], s->key);
1108	}
1109
1110	BG(user_compare_fci).param_count = 2;
1111	BG(user_compare_fci).params = args;
1112	BG(user_compare_fci).retval = &retval;
1113	BG(user_compare_fci).no_separation = 0;
1114	if (zend_call_function(&BG(user_compare_fci), &BG(user_compare_fci_cache)) == SUCCESS && Z_TYPE(retval) != IS_UNDEF) {
1115		result = zval_get_long(&retval);
1116		zval_ptr_dtor(&retval);
1117	} else {
1118		result = 0;
1119	}
1120
1121	zval_ptr_dtor(&args[0]);
1122	zval_ptr_dtor(&args[1]);
1123
1124	return result < 0 ? -1 : result > 0 ? 1 : 0;
1125}
1126/* }}} */
1127
1128/* {{{ proto bool uksort(array array_arg, string cmp_function)
1129   Sort an array by keys using a user-defined comparison function */
1130PHP_FUNCTION(uksort)
1131{
1132	php_usort(INTERNAL_FUNCTION_PARAM_PASSTHRU, php_array_user_key_compare, 0);
1133}
1134/* }}} */
1135
1136/* {{{ proto mixed end(array array_arg)
1137   Advances array argument's internal pointer to the last element and return it */
1138PHP_FUNCTION(end)
1139{
1140	HashTable *array;
1141	zval *entry;
1142
1143#ifndef FAST_ZPP
1144	if (zend_parse_parameters(ZEND_NUM_ARGS(), "H/", &array) == FAILURE) {
1145		return;
1146	}
1147#else
1148	ZEND_PARSE_PARAMETERS_START(1, 1)
1149		Z_PARAM_ARRAY_OR_OBJECT_HT_EX(array, 0, 1)
1150	ZEND_PARSE_PARAMETERS_END();
1151#endif
1152
1153	zend_hash_internal_pointer_end(array);
1154
1155	if (USED_RET()) {
1156		if ((entry = zend_hash_get_current_data(array)) == NULL) {
1157			RETURN_FALSE;
1158		}
1159
1160		if (Z_TYPE_P(entry) == IS_INDIRECT) {
1161			entry = Z_INDIRECT_P(entry);
1162		}
1163
1164		ZVAL_DEREF(entry);
1165		ZVAL_COPY(return_value, entry);
1166	}
1167}
1168/* }}} */
1169
1170/* {{{ proto mixed prev(array array_arg)
1171   Move array argument's internal pointer to the previous element and return it */
1172PHP_FUNCTION(prev)
1173{
1174	HashTable *array;
1175	zval *entry;
1176
1177#ifndef FAST_ZPP
1178	if (zend_parse_parameters(ZEND_NUM_ARGS(), "H/", &array) == FAILURE) {
1179		return;
1180	}
1181#else
1182	ZEND_PARSE_PARAMETERS_START(1, 1)
1183		Z_PARAM_ARRAY_OR_OBJECT_HT_EX(array, 0, 1)
1184	ZEND_PARSE_PARAMETERS_END();
1185#endif
1186
1187	zend_hash_move_backwards(array);
1188
1189	if (USED_RET()) {
1190		if ((entry = zend_hash_get_current_data(array)) == NULL) {
1191			RETURN_FALSE;
1192		}
1193
1194		if (Z_TYPE_P(entry) == IS_INDIRECT) {
1195			entry = Z_INDIRECT_P(entry);
1196		}
1197
1198		ZVAL_DEREF(entry);
1199		ZVAL_COPY(return_value, entry);
1200	}
1201}
1202/* }}} */
1203
1204/* {{{ proto mixed next(array array_arg)
1205   Move array argument's internal pointer to the next element and return it */
1206PHP_FUNCTION(next)
1207{
1208	HashTable *array;
1209	zval *entry;
1210
1211#ifndef FAST_ZPP
1212	if (zend_parse_parameters(ZEND_NUM_ARGS(), "H/", &array) == FAILURE) {
1213		return;
1214	}
1215#else
1216	ZEND_PARSE_PARAMETERS_START(1, 1)
1217		Z_PARAM_ARRAY_OR_OBJECT_HT_EX(array, 0, 1)
1218	ZEND_PARSE_PARAMETERS_END();
1219#endif
1220
1221	zend_hash_move_forward(array);
1222
1223	if (USED_RET()) {
1224		if ((entry = zend_hash_get_current_data(array)) == NULL) {
1225			RETURN_FALSE;
1226		}
1227
1228		if (Z_TYPE_P(entry) == IS_INDIRECT) {
1229			entry = Z_INDIRECT_P(entry);
1230		}
1231
1232		ZVAL_DEREF(entry);
1233		ZVAL_COPY(return_value, entry);
1234	}
1235}
1236/* }}} */
1237
1238/* {{{ proto mixed reset(array array_arg)
1239   Set array argument's internal pointer to the first element and return it */
1240PHP_FUNCTION(reset)
1241{
1242	HashTable *array;
1243	zval *entry;
1244
1245#ifndef FAST_ZPP
1246	if (zend_parse_parameters(ZEND_NUM_ARGS(), "H/", &array) == FAILURE) {
1247		return;
1248	}
1249#else
1250	ZEND_PARSE_PARAMETERS_START(1, 1)
1251		Z_PARAM_ARRAY_OR_OBJECT_HT_EX(array, 0, 1)
1252	ZEND_PARSE_PARAMETERS_END();
1253#endif
1254
1255	zend_hash_internal_pointer_reset(array);
1256
1257	if (USED_RET()) {
1258		if ((entry = zend_hash_get_current_data(array)) == NULL) {
1259			RETURN_FALSE;
1260		}
1261
1262		if (Z_TYPE_P(entry) == IS_INDIRECT) {
1263			entry = Z_INDIRECT_P(entry);
1264		}
1265
1266		ZVAL_DEREF(entry);
1267		ZVAL_COPY(return_value, entry);
1268	}
1269}
1270/* }}} */
1271
1272/* {{{ proto mixed current(array array_arg)
1273   Return the element currently pointed to by the internal array pointer */
1274PHP_FUNCTION(current)
1275{
1276	HashTable *array;
1277	zval *entry;
1278
1279#ifndef FAST_ZPP
1280	if (zend_parse_parameters(ZEND_NUM_ARGS(), "H", &array) == FAILURE) {
1281		return;
1282	}
1283#else
1284	ZEND_PARSE_PARAMETERS_START(1, 1)
1285		Z_PARAM_ARRAY_OR_OBJECT_HT(array)
1286	ZEND_PARSE_PARAMETERS_END();
1287#endif
1288
1289	if ((entry = zend_hash_get_current_data(array)) == NULL) {
1290		RETURN_FALSE;
1291	}
1292
1293	if (Z_TYPE_P(entry) == IS_INDIRECT) {
1294		entry = Z_INDIRECT_P(entry);
1295	}
1296
1297	ZVAL_DEREF(entry);
1298	ZVAL_COPY(return_value, entry);
1299}
1300/* }}} */
1301
1302/* {{{ proto mixed key(array array_arg)
1303   Return the key of the element currently pointed to by the internal array pointer */
1304PHP_FUNCTION(key)
1305{
1306	HashTable *array;
1307
1308#ifndef FAST_ZPP
1309	if (zend_parse_parameters(ZEND_NUM_ARGS(), "H", &array) == FAILURE) {
1310		return;
1311	}
1312#else
1313	ZEND_PARSE_PARAMETERS_START(1, 1)
1314		Z_PARAM_ARRAY_OR_OBJECT_HT(array)
1315	ZEND_PARSE_PARAMETERS_END();
1316#endif
1317
1318	zend_hash_get_current_key_zval(array, return_value);
1319}
1320/* }}} */
1321
1322/* {{{ proto mixed min(mixed arg1 [, mixed arg2 [, mixed ...]])
1323   Return the lowest value in an array or a series of arguments */
1324PHP_FUNCTION(min)
1325{
1326	int argc;
1327	zval *args = NULL;
1328
1329	if (zend_parse_parameters(ZEND_NUM_ARGS(), "+", &args, &argc) == FAILURE) {
1330		return;
1331	}
1332
1333	/* mixed min ( array $values ) */
1334	if (argc == 1) {
1335		zval *result;
1336
1337		if (Z_TYPE(args[0]) != IS_ARRAY) {
1338			php_error_docref(NULL, E_WARNING, "When only one parameter is given, it must be an array");
1339			RETVAL_NULL();
1340		} else {
1341			if ((result = zend_hash_minmax(Z_ARRVAL(args[0]), php_array_data_compare, 0)) != NULL) {
1342				ZVAL_DEREF(result);
1343				ZVAL_COPY(return_value, result);
1344			} else {
1345				php_error_docref(NULL, E_WARNING, "Array must contain at least one element");
1346				RETVAL_FALSE;
1347			}
1348		}
1349	} else {
1350		/* mixed min ( mixed $value1 , mixed $value2 [, mixed $value3... ] ) */
1351		zval *min, result;
1352		int i;
1353
1354		min = &args[0];
1355
1356		for (i = 1; i < argc; i++) {
1357			is_smaller_function(&result, &args[i], min);
1358			if (Z_TYPE(result) == IS_TRUE) {
1359				min = &args[i];
1360			}
1361		}
1362
1363		ZVAL_DEREF(min);
1364		ZVAL_COPY(return_value, min);
1365	}
1366}
1367/* }}} */
1368
1369/* {{{ proto mixed max(mixed arg1 [, mixed arg2 [, mixed ...]])
1370   Return the highest value in an array or a series of arguments */
1371PHP_FUNCTION(max)
1372{
1373	zval *args = NULL;
1374	int argc;
1375
1376	if (zend_parse_parameters(ZEND_NUM_ARGS(), "+", &args, &argc) == FAILURE) {
1377		return;
1378	}
1379
1380	/* mixed max ( array $values ) */
1381	if (argc == 1) {
1382		zval *result;
1383
1384		if (Z_TYPE(args[0]) != IS_ARRAY) {
1385			php_error_docref(NULL, E_WARNING, "When only one parameter is given, it must be an array");
1386			RETVAL_NULL();
1387		} else {
1388			if ((result = zend_hash_minmax(Z_ARRVAL(args[0]), php_array_data_compare, 1)) != NULL) {
1389				ZVAL_DEREF(result);
1390				ZVAL_COPY(return_value, result);
1391			} else {
1392				php_error_docref(NULL, E_WARNING, "Array must contain at least one element");
1393				RETVAL_FALSE;
1394			}
1395		}
1396	} else {
1397		/* mixed max ( mixed $value1 , mixed $value2 [, mixed $value3... ] ) */
1398		zval *max, result;
1399		int i;
1400
1401		max = &args[0];
1402
1403		for (i = 1; i < argc; i++) {
1404			is_smaller_or_equal_function(&result, &args[i], max);
1405			if (Z_TYPE(result) == IS_FALSE) {
1406				max = &args[i];
1407			}
1408		}
1409
1410		ZVAL_DEREF(max);
1411		ZVAL_COPY(return_value, max);
1412	}
1413}
1414/* }}} */
1415
1416static int php_array_walk(HashTable *target_hash, zval *userdata, int recursive) /* {{{ */
1417{
1418	zval args[3],		/* Arguments to userland function */
1419		 retval,		/* Return value - unused */
1420		 *zv;
1421
1422	/* Set up known arguments */
1423	ZVAL_UNDEF(&args[1]);
1424	if (userdata) {
1425		ZVAL_COPY(&args[2], userdata);
1426	}
1427
1428	BG(array_walk_fci).retval = &retval;
1429	BG(array_walk_fci).param_count = userdata ? 3 : 2;
1430	BG(array_walk_fci).params = args;
1431	BG(array_walk_fci).no_separation = 0;
1432
1433	/* Iterate through hash */
1434	zend_hash_internal_pointer_reset(target_hash);
1435	while (!EG(exception) && (zv = zend_hash_get_current_data(target_hash)) != NULL) {
1436		if (Z_TYPE_P(zv) == IS_INDIRECT) {
1437			zv = Z_INDIRECT_P(zv);
1438			if (Z_TYPE_P(zv) == IS_UNDEF) {
1439				zend_hash_move_forward(target_hash);
1440				continue;
1441			}
1442		}
1443		if (recursive &&
1444		    (Z_TYPE_P(zv) == IS_ARRAY ||
1445		     (Z_ISREF_P(zv) && Z_TYPE_P(Z_REFVAL_P(zv)) == IS_ARRAY))) {
1446			HashTable *thash;
1447			zend_fcall_info orig_array_walk_fci;
1448			zend_fcall_info_cache orig_array_walk_fci_cache;
1449
1450			ZVAL_DEREF(zv);
1451			SEPARATE_ARRAY(zv);
1452			thash = Z_ARRVAL_P(zv);
1453			if (thash->u.v.nApplyCount > 1) {
1454				php_error_docref(NULL, E_WARNING, "recursion detected");
1455				if (userdata) {
1456					zval_ptr_dtor(&args[2]);
1457				}
1458				return 0;
1459			}
1460
1461			/* backup the fcall info and cache */
1462			orig_array_walk_fci = BG(array_walk_fci);
1463			orig_array_walk_fci_cache = BG(array_walk_fci_cache);
1464
1465			thash->u.v.nApplyCount++;
1466			php_array_walk(thash, userdata, recursive);
1467			thash->u.v.nApplyCount--;
1468
1469			/* restore the fcall info and cache */
1470			BG(array_walk_fci) = orig_array_walk_fci;
1471			BG(array_walk_fci_cache) = orig_array_walk_fci_cache;
1472		} else {
1473			int was_ref = Z_ISREF_P(zv);
1474
1475			ZVAL_COPY(&args[0], zv);
1476
1477			/* Allocate space for key */
1478			zend_hash_get_current_key_zval(target_hash, &args[1]);
1479
1480			/* Call the userland function */
1481			if (zend_call_function(&BG(array_walk_fci), &BG(array_walk_fci_cache)) == SUCCESS) {
1482				if (!was_ref && Z_ISREF(args[0])) {
1483					/* copy reference back */
1484					zval garbage;
1485
1486					ZVAL_COPY_VALUE(&garbage, zv);
1487					ZVAL_COPY_VALUE(zv, &args[0]);
1488					zval_ptr_dtor(&garbage);
1489				} else {
1490					zval_ptr_dtor(&args[0]);
1491				}
1492				zval_ptr_dtor(&retval);
1493			} else {
1494				zval_ptr_dtor(&args[0]);
1495				if (Z_TYPE(args[1]) != IS_UNDEF) {
1496					zval_ptr_dtor(&args[1]);
1497					ZVAL_UNDEF(&args[1]);
1498				}
1499				break;
1500			}
1501		}
1502
1503		if (Z_TYPE(args[1]) != IS_UNDEF) {
1504			zval_ptr_dtor(&args[1]);
1505			ZVAL_UNDEF(&args[1]);
1506		}
1507		zend_hash_move_forward(target_hash);
1508	}
1509
1510	if (userdata) {
1511		zval_ptr_dtor(&args[2]);
1512	}
1513	return 0;
1514}
1515/* }}} */
1516
1517/* {{{ proto bool array_walk(array input, string funcname [, mixed userdata])
1518   Apply a user function to every member of an array */
1519PHP_FUNCTION(array_walk)
1520{
1521	HashTable *array;
1522	zval *userdata = NULL;
1523	zend_fcall_info orig_array_walk_fci;
1524	zend_fcall_info_cache orig_array_walk_fci_cache;
1525
1526	orig_array_walk_fci = BG(array_walk_fci);
1527	orig_array_walk_fci_cache = BG(array_walk_fci_cache);
1528
1529#ifndef FAST_ZPP
1530	if (zend_parse_parameters(ZEND_NUM_ARGS(), "H/f|z/", &array, &BG(array_walk_fci), &BG(array_walk_fci_cache), &userdata) == FAILURE) {
1531		BG(array_walk_fci) = orig_array_walk_fci;
1532		BG(array_walk_fci_cache) = orig_array_walk_fci_cache;
1533		return;
1534	}
1535#else
1536	ZEND_PARSE_PARAMETERS_START(2, 3)
1537		Z_PARAM_ARRAY_OR_OBJECT_HT_EX(array, 0, 1)
1538		Z_PARAM_FUNC(BG(array_walk_fci), BG(array_walk_fci_cache))
1539		Z_PARAM_OPTIONAL
1540		Z_PARAM_ZVAL_EX(userdata, 0, 1)
1541	ZEND_PARSE_PARAMETERS_END_EX(
1542		BG(array_walk_fci) = orig_array_walk_fci;
1543		BG(array_walk_fci_cache) = orig_array_walk_fci_cache;
1544		return
1545	);
1546#endif
1547
1548	php_array_walk(array, userdata, 0);
1549	BG(array_walk_fci) = orig_array_walk_fci;
1550	BG(array_walk_fci_cache) = orig_array_walk_fci_cache;
1551	RETURN_TRUE;
1552}
1553/* }}} */
1554
1555/* {{{ proto bool array_walk_recursive(array input, string funcname [, mixed userdata])
1556   Apply a user function recursively to every member of an array */
1557PHP_FUNCTION(array_walk_recursive)
1558{
1559	HashTable *array;
1560	zval *userdata = NULL;
1561	zend_fcall_info orig_array_walk_fci;
1562	zend_fcall_info_cache orig_array_walk_fci_cache;
1563
1564	orig_array_walk_fci = BG(array_walk_fci);
1565	orig_array_walk_fci_cache = BG(array_walk_fci_cache);
1566
1567	if (zend_parse_parameters(ZEND_NUM_ARGS(), "H/f|z/", &array, &BG(array_walk_fci), &BG(array_walk_fci_cache), &userdata) == FAILURE) {
1568		BG(array_walk_fci) = orig_array_walk_fci;
1569		BG(array_walk_fci_cache) = orig_array_walk_fci_cache;
1570		return;
1571	}
1572
1573	php_array_walk(array, userdata, 1);
1574	BG(array_walk_fci) = orig_array_walk_fci;
1575	BG(array_walk_fci_cache) = orig_array_walk_fci_cache;
1576	RETURN_TRUE;
1577}
1578/* }}} */
1579
1580/* void php_search_array(INTERNAL_FUNCTION_PARAMETERS, int behavior)
1581 * 0 = return boolean
1582 * 1 = return key
1583 */
1584static inline void php_search_array(INTERNAL_FUNCTION_PARAMETERS, int behavior) /* {{{ */
1585{
1586	zval *value,				/* value to check for */
1587		 *array,				/* array to check in */
1588		 *entry;				/* pointer to array entry */
1589	zend_ulong num_idx;
1590	zend_string *str_idx;
1591	zend_bool strict = 0;		/* strict comparison or not */
1592
1593#ifndef FAST_ZPP
1594	if (zend_parse_parameters(ZEND_NUM_ARGS(), "za|b", &value, &array, &strict) == FAILURE) {
1595		return;
1596	}
1597#else
1598	ZEND_PARSE_PARAMETERS_START(2, 3)
1599		Z_PARAM_ZVAL(value)
1600		Z_PARAM_ARRAY(array)
1601		Z_PARAM_OPTIONAL
1602		Z_PARAM_BOOL(strict)
1603	ZEND_PARSE_PARAMETERS_END();
1604#endif
1605
1606	if (strict) {
1607		ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {
1608			ZVAL_DEREF(entry);
1609			if (fast_is_identical_function(value, entry)) {
1610				if (behavior == 0) {
1611					RETURN_TRUE;
1612				} else {
1613					if (str_idx) {
1614						RETVAL_STR_COPY(str_idx);
1615					} else {
1616						RETVAL_LONG(num_idx);
1617					}
1618					return;
1619				}
1620			}
1621		} ZEND_HASH_FOREACH_END();
1622	} else {
1623		ZVAL_DEREF(value);
1624		if (Z_TYPE_P(value) == IS_LONG) {
1625			ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {
1626				if (fast_equal_check_long(value, entry)) {
1627					if (behavior == 0) {
1628						RETURN_TRUE;
1629					} else {
1630						if (str_idx) {
1631							RETVAL_STR_COPY(str_idx);
1632						} else {
1633							RETVAL_LONG(num_idx);
1634						}
1635						return;
1636					}
1637				}
1638			} ZEND_HASH_FOREACH_END();
1639		} else if (Z_TYPE_P(value) == IS_STRING) {
1640			ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {
1641				if (fast_equal_check_string(value, entry)) {
1642					if (behavior == 0) {
1643						RETURN_TRUE;
1644					} else {
1645						if (str_idx) {
1646							RETVAL_STR_COPY(str_idx);
1647						} else {
1648							RETVAL_LONG(num_idx);
1649						}
1650						return;
1651					}
1652				}
1653			} ZEND_HASH_FOREACH_END();
1654		} else {
1655			ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {
1656				if (fast_equal_check_function(value, entry)) {
1657					if (behavior == 0) {
1658						RETURN_TRUE;
1659					} else {
1660						if (str_idx) {
1661							RETVAL_STR_COPY(str_idx);
1662						} else {
1663							RETVAL_LONG(num_idx);
1664						}
1665						return;
1666					}
1667				}
1668			} ZEND_HASH_FOREACH_END();
1669 		}
1670	}
1671
1672	RETURN_FALSE;
1673}
1674/* }}} */
1675
1676/* {{{ proto bool in_array(mixed needle, array haystack [, bool strict])
1677   Checks if the given value exists in the array */
1678PHP_FUNCTION(in_array)
1679{
1680	php_search_array(INTERNAL_FUNCTION_PARAM_PASSTHRU, 0);
1681}
1682/* }}} */
1683
1684/* {{{ proto mixed array_search(mixed needle, array haystack [, bool strict])
1685   Searches the array for a given value and returns the corresponding key if successful */
1686PHP_FUNCTION(array_search)
1687{
1688	php_search_array(INTERNAL_FUNCTION_PARAM_PASSTHRU, 1);
1689}
1690/* }}} */
1691
1692static zend_always_inline int php_valid_var_name(char *var_name, size_t var_name_len) /* {{{ */
1693{
1694#if 1
1695	/* first 256 bits for first character, and second 256 bits for the next */
1696	static const uint32_t charset[16] = {
1697	     /*  31      0   63     32   95     64   127    96 */
1698			0x00000000, 0x00000000, 0x87fffffe, 0x07fffffe,
1699			0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff,
1700	     /*  31      0   63     32   95     64   127    96 */
1701			0x00000000, 0x03ff0000, 0x87fffffe, 0x07fffffe,
1702			0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff
1703		};
1704#endif
1705	size_t i;
1706	uint32_t ch;
1707
1708	if (UNEXPECTED(!var_name_len)) {
1709		return 0;
1710	}
1711
1712	/* These are allowed as first char: [a-zA-Z_\x7f-\xff] */
1713	ch = (uint32_t)((unsigned char *)var_name)[0];
1714#if 1
1715	if (UNEXPECTED(!(charset[ch >> 5] & (1 << (ch & 0x1f))))) {
1716#else
1717	if (var_name[0] != '_' &&
1718		(ch < 65  /* A    */ || /* Z    */ ch > 90)  &&
1719		(ch < 97  /* a    */ || /* z    */ ch > 122) &&
1720		(ch < 127 /* 0x7f */ || /* 0xff */ ch > 255)
1721	) {
1722#endif
1723		return 0;
1724	}
1725
1726	/* And these as the rest: [a-zA-Z0-9_\x7f-\xff] */
1727	if (var_name_len > 1) {
1728		i = 1;
1729		do {
1730			ch = (uint32_t)((unsigned char *)var_name)[i];
1731#if 1
1732			if (UNEXPECTED(!(charset[8 + (ch >> 5)] & (1 << (ch & 0x1f))))) {
1733#else
1734			if (var_name[i] != '_' &&
1735				(ch < 48  /* 0    */ || /* 9    */ ch > 57)  &&
1736				(ch < 65  /* A    */ || /* Z    */ ch > 90)  &&
1737				(ch < 97  /* a    */ || /* z    */ ch > 122) &&
1738				(ch < 127 /* 0x7f */ || /* 0xff */ ch > 255)
1739			) {
1740#endif
1741				return 0;
1742			}
1743		} while (++i < var_name_len);
1744	}
1745	return 1;
1746}
1747/* }}} */
1748
1749PHPAPI int php_prefix_varname(zval *result, zval *prefix, char *var_name, size_t var_name_len, zend_bool add_underscore) /* {{{ */
1750{
1751	ZVAL_NEW_STR(result, zend_string_alloc(Z_STRLEN_P(prefix) + (add_underscore ? 1 : 0) + var_name_len, 0));
1752	memcpy(Z_STRVAL_P(result), Z_STRVAL_P(prefix), Z_STRLEN_P(prefix));
1753
1754	if (add_underscore) {
1755		Z_STRVAL_P(result)[Z_STRLEN_P(prefix)] = '_';
1756	}
1757
1758	memcpy(Z_STRVAL_P(result) + Z_STRLEN_P(prefix) + (add_underscore ? 1 : 0), var_name, var_name_len + 1);
1759
1760	return SUCCESS;
1761}
1762/* }}} */
1763
1764/* {{{ proto int extract(array var_array [, int extract_type [, string prefix]])
1765   Imports variables into symbol table from an array */
1766PHP_FUNCTION(extract)
1767{
1768	zval *var_array, *prefix = NULL;
1769	zend_long extract_type = EXTR_OVERWRITE;
1770	zval *entry;
1771	zend_string *var_name;
1772	zend_ulong num_key;
1773	int var_exists, count = 0;
1774	int extract_refs = 0;
1775	zend_array *symbol_table;
1776
1777#ifndef FAST_ZPP
1778	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a|lz/", &var_array, &extract_type, &prefix) == FAILURE) {
1779		return;
1780	}
1781#else
1782	ZEND_PARSE_PARAMETERS_START(1, 3)
1783		Z_PARAM_ARRAY(var_array)
1784		Z_PARAM_OPTIONAL
1785		Z_PARAM_LONG(extract_type)
1786		Z_PARAM_ZVAL_EX(prefix, 0, 1)
1787	ZEND_PARSE_PARAMETERS_END();
1788#endif
1789
1790	extract_refs = (extract_type & EXTR_REFS);
1791	if (extract_refs) {
1792		SEPARATE_ZVAL(var_array);
1793	}
1794	extract_type &= 0xff;
1795
1796	if (extract_type < EXTR_OVERWRITE || extract_type > EXTR_IF_EXISTS) {
1797		php_error_docref(NULL, E_WARNING, "Invalid extract type");
1798		return;
1799	}
1800
1801	if (extract_type > EXTR_SKIP && extract_type <= EXTR_PREFIX_IF_EXISTS && ZEND_NUM_ARGS() < 3) {
1802		php_error_docref(NULL, E_WARNING, "specified extract type requires the prefix parameter");
1803		return;
1804	}
1805
1806	if (prefix) {
1807		convert_to_string(prefix);
1808		if (Z_STRLEN_P(prefix) && !php_valid_var_name(Z_STRVAL_P(prefix), Z_STRLEN_P(prefix))) {
1809			php_error_docref(NULL, E_WARNING, "prefix is not a valid identifier");
1810			return;
1811		}
1812	}
1813
1814	symbol_table = zend_rebuild_symbol_table();
1815#if 0
1816	if (!symbol_table) {
1817		php_error_docref(NULL, E_WARNING, "failed to build symbol table");
1818		return;
1819	}
1820#endif
1821
1822	ZEND_HASH_FOREACH_KEY_VAL_IND(Z_ARRVAL_P(var_array), num_key, var_name, entry) {
1823		zval final_name;
1824
1825		ZVAL_NULL(&final_name);
1826		var_exists = 0;
1827
1828		if (var_name) {
1829			var_exists = zend_hash_exists_ind(symbol_table, var_name);
1830		} else if (extract_type == EXTR_PREFIX_ALL || extract_type == EXTR_PREFIX_INVALID) {
1831			zend_string *str = zend_long_to_str(num_key);
1832			php_prefix_varname(&final_name, prefix, ZSTR_VAL(str), ZSTR_LEN(str), 1);
1833			zend_string_release(str);
1834		} else {
1835			continue;
1836		}
1837
1838		switch (extract_type) {
1839			case EXTR_IF_EXISTS:
1840				if (!var_exists) break;
1841				/* break omitted intentionally */
1842
1843			case EXTR_OVERWRITE:
1844				/* GLOBALS protection */
1845				if (var_exists && ZSTR_LEN(var_name) == sizeof("GLOBALS")-1 && !strcmp(ZSTR_VAL(var_name), "GLOBALS")) {
1846					break;
1847				}
1848				if (var_exists && ZSTR_LEN(var_name) == sizeof("this")-1  && !strcmp(ZSTR_VAL(var_name), "this") && EG(scope) && ZSTR_LEN(EG(scope)->name) != 0) {
1849					break;
1850				}
1851				ZVAL_STR_COPY(&final_name, var_name);
1852				break;
1853
1854			case EXTR_PREFIX_IF_EXISTS:
1855				if (var_exists) {
1856					php_prefix_varname(&final_name, prefix, ZSTR_VAL(var_name), ZSTR_LEN(var_name), 1);
1857				}
1858				break;
1859
1860			case EXTR_PREFIX_SAME:
1861				if (!var_exists && ZSTR_LEN(var_name) != 0) {
1862					ZVAL_STR_COPY(&final_name, var_name);
1863				}
1864				/* break omitted intentionally */
1865
1866			case EXTR_PREFIX_ALL:
1867				if (Z_TYPE(final_name) == IS_NULL && ZSTR_LEN(var_name) != 0) {
1868					php_prefix_varname(&final_name, prefix, ZSTR_VAL(var_name), ZSTR_LEN(var_name), 1);
1869				}
1870				break;
1871
1872			case EXTR_PREFIX_INVALID:
1873				if (Z_TYPE(final_name) == IS_NULL) {
1874					if (!php_valid_var_name(ZSTR_VAL(var_name), ZSTR_LEN(var_name))) {
1875						php_prefix_varname(&final_name, prefix, ZSTR_VAL(var_name), ZSTR_LEN(var_name), 1);
1876					} else {
1877						ZVAL_STR_COPY(&final_name, var_name);
1878					}
1879				}
1880				break;
1881
1882			default:
1883				if (!var_exists) {
1884					ZVAL_STR_COPY(&final_name, var_name);
1885				}
1886				break;
1887		}
1888
1889		if (Z_TYPE(final_name) == IS_STRING && php_valid_var_name(Z_STRVAL(final_name), Z_STRLEN(final_name))) {
1890			zval *orig_var;
1891			if (extract_refs) {
1892
1893				ZVAL_MAKE_REF(entry);
1894				Z_ADDREF_P(entry);
1895
1896				if ((orig_var = zend_hash_find(symbol_table, Z_STR(final_name))) != NULL) {
1897					if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
1898						orig_var = Z_INDIRECT_P(orig_var);
1899					}
1900					zval_ptr_dtor(orig_var);
1901					ZVAL_COPY_VALUE(orig_var, entry);
1902				} else {
1903					zend_hash_update(symbol_table, Z_STR(final_name), entry);
1904				}
1905			} else {
1906				ZVAL_DEREF(entry);
1907				if (Z_REFCOUNTED_P(entry)) Z_ADDREF_P(entry);
1908				if ((orig_var = zend_hash_find(symbol_table, Z_STR(final_name))) != NULL) {
1909					if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
1910						orig_var = Z_INDIRECT_P(orig_var);
1911					}
1912					ZVAL_DEREF(orig_var);
1913					zval_ptr_dtor(orig_var);
1914					ZVAL_COPY_VALUE(orig_var, entry);
1915				} else {
1916					zend_hash_update(symbol_table, Z_STR(final_name), entry);
1917				}
1918			}
1919			count++;
1920		}
1921		zval_dtor(&final_name);
1922	} ZEND_HASH_FOREACH_END();
1923
1924	RETURN_LONG(count);
1925}
1926/* }}} */
1927
1928static void php_compact_var(HashTable *eg_active_symbol_table, zval *return_value, zval *entry) /* {{{ */
1929{
1930	zval *value_ptr, data;
1931
1932	ZVAL_DEREF(entry);
1933	if (Z_TYPE_P(entry) == IS_STRING) {
1934		if ((value_ptr = zend_hash_find_ind(eg_active_symbol_table, Z_STR_P(entry))) != NULL) {
1935			ZVAL_COPY(&data, value_ptr);
1936			zend_hash_update(Z_ARRVAL_P(return_value), Z_STR_P(entry), &data);
1937		}
1938	} else if (Z_TYPE_P(entry) == IS_ARRAY) {
1939		if ((Z_ARRVAL_P(entry)->u.v.nApplyCount > 1)) {
1940			php_error_docref(NULL, E_WARNING, "recursion detected");
1941			return;
1942		}
1943
1944	    if (ZEND_HASH_APPLY_PROTECTION(Z_ARRVAL_P(entry))) {
1945			Z_ARRVAL_P(entry)->u.v.nApplyCount++;
1946		}
1947		ZEND_HASH_FOREACH_VAL_IND(Z_ARRVAL_P(entry), value_ptr) {
1948			php_compact_var(eg_active_symbol_table, return_value, value_ptr);
1949		} ZEND_HASH_FOREACH_END();
1950	    if (ZEND_HASH_APPLY_PROTECTION(Z_ARRVAL_P(entry))) {
1951			Z_ARRVAL_P(entry)->u.v.nApplyCount--;
1952		}
1953	}
1954}
1955/* }}} */
1956
1957/* {{{ proto array compact(mixed var_names [, mixed ...])
1958   Creates a hash containing variables and their values */
1959PHP_FUNCTION(compact)
1960{
1961	zval *args = NULL;	/* function arguments array */
1962	uint32_t num_args, i;
1963	zend_array *symbol_table;
1964
1965	if (zend_parse_parameters(ZEND_NUM_ARGS(), "+", &args, &num_args) == FAILURE) {
1966		return;
1967	}
1968
1969	symbol_table = zend_rebuild_symbol_table();
1970
1971	if (UNEXPECTED(symbol_table == NULL)) {
1972		return;
1973	}
1974
1975	/* compact() is probably most used with a single array of var_names
1976	   or multiple string names, rather than a combination of both.
1977	   So quickly guess a minimum result size based on that */
1978	if (ZEND_NUM_ARGS() == 1 && Z_TYPE(args[0]) == IS_ARRAY) {
1979		array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL(args[0])));
1980	} else {
1981		array_init_size(return_value, ZEND_NUM_ARGS());
1982	}
1983
1984	for (i=0; i<ZEND_NUM_ARGS(); i++) {
1985		php_compact_var(symbol_table, return_value, &args[i]);
1986	}
1987}
1988/* }}} */
1989
1990/* {{{ proto array array_fill(int start_key, int num, mixed val)
1991   Create an array containing num elements starting with index start_key each initialized to val */
1992PHP_FUNCTION(array_fill)
1993{
1994	zval *val;
1995	zend_long start_key, num;
1996
1997	if (zend_parse_parameters(ZEND_NUM_ARGS(), "llz", &start_key, &num, &val) == FAILURE) {
1998		return;
1999	}
2000
2001	if (num < 0) {
2002		php_error_docref(NULL, E_WARNING, "Number of elements can't be negative");
2003		RETURN_FALSE;
2004	}
2005
2006	/* allocate an array for return */
2007	array_init_size(return_value, (uint32_t)num);
2008
2009	if (num == 0) {
2010		return;
2011	}
2012
2013	num--;
2014	zend_hash_index_update(Z_ARRVAL_P(return_value), start_key, val);
2015	Z_TRY_ADDREF_P(val);
2016
2017	while (num--) {
2018		if (zend_hash_next_index_insert(Z_ARRVAL_P(return_value), val) != NULL) {
2019			Z_TRY_ADDREF_P(val);
2020		} else {
2021			zval_dtor(return_value);
2022			php_error_docref(NULL, E_WARNING, "Cannot add element to the array as the next element is already occupied");
2023			RETURN_FALSE;
2024		}
2025	}
2026}
2027/* }}} */
2028
2029/* {{{ proto array array_fill_keys(array keys, mixed val)
2030   Create an array using the elements of the first parameter as keys each initialized to val */
2031PHP_FUNCTION(array_fill_keys)
2032{
2033	zval *keys, *val, *entry;
2034
2035	if (zend_parse_parameters(ZEND_NUM_ARGS(), "az", &keys, &val) == FAILURE) {
2036		return;
2037	}
2038
2039	/* Initialize return array */
2040	array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(keys)));
2041
2042	ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(keys), entry) {
2043		ZVAL_DEREF(entry);
2044		Z_TRY_ADDREF_P(val);
2045		if (Z_TYPE_P(entry) == IS_LONG) {
2046			zend_hash_index_update(Z_ARRVAL_P(return_value), Z_LVAL_P(entry), val);
2047		} else {
2048			zend_string *key = zval_get_string(entry);
2049			zend_symtable_update(Z_ARRVAL_P(return_value), key, val);
2050			zend_string_release(key);
2051		}
2052	} ZEND_HASH_FOREACH_END();
2053}
2054/* }}} */
2055
2056#define RANGE_CHECK_DOUBLE_INIT_ARRAY(start, end) do { \
2057		double __calc_size = ((start - end) / step) + 1; \
2058		if (__calc_size >= (double)HT_MAX_SIZE) { \
2059			php_error_docref(NULL, E_WARNING, "The supplied range exceeds the maximum array size: start=%0.0f end=%0.0f", end, start); \
2060			RETURN_FALSE; \
2061		} \
2062		size = (uint32_t)__calc_size; \
2063		array_init_size(return_value, size); \
2064		zend_hash_real_init(Z_ARRVAL_P(return_value), 1); \
2065	} while (0)
2066
2067#define RANGE_CHECK_LONG_INIT_ARRAY(start, end) do { \
2068		zend_ulong __calc_size = (start - end) / lstep; \
2069		if (__calc_size >= HT_MAX_SIZE - 1) { \
2070			php_error_docref(NULL, E_WARNING, "The supplied range exceeds the maximum array size: start=%pd end=%pd", end, start); \
2071			RETURN_FALSE; \
2072		} \
2073		size = (uint32_t)(__calc_size + 1); \
2074		array_init_size(return_value, size); \
2075		zend_hash_real_init(Z_ARRVAL_P(return_value), 1); \
2076	} while (0)
2077
2078/* {{{ proto array range(mixed low, mixed high[, int step])
2079   Create an array containing the range of integers or characters from low to high (inclusive) */
2080PHP_FUNCTION(range)
2081{
2082	zval *zlow, *zhigh, *zstep = NULL, tmp;
2083	int err = 0, is_step_double = 0;
2084	double step = 1.0;
2085
2086	if (zend_parse_parameters(ZEND_NUM_ARGS(), "zz|z", &zlow, &zhigh, &zstep) == FAILURE) {
2087		RETURN_FALSE;
2088	}
2089
2090	if (zstep) {
2091		if (Z_TYPE_P(zstep) == IS_DOUBLE ||
2092			(Z_TYPE_P(zstep) == IS_STRING && is_numeric_string(Z_STRVAL_P(zstep), Z_STRLEN_P(zstep), NULL, NULL, 0) == IS_DOUBLE)
2093		) {
2094			is_step_double = 1;
2095		}
2096
2097		step = zval_get_double(zstep);
2098
2099		/* We only want positive step values. */
2100		if (step < 0.0) {
2101			step *= -1;
2102		}
2103	}
2104
2105	/* If the range is given as strings, generate an array of characters. */
2106	if (Z_TYPE_P(zlow) == IS_STRING && Z_TYPE_P(zhigh) == IS_STRING && Z_STRLEN_P(zlow) >= 1 && Z_STRLEN_P(zhigh) >= 1) {
2107		int type1, type2;
2108		unsigned char low, high;
2109		zend_long lstep = (zend_long) step;
2110
2111		type1 = is_numeric_string(Z_STRVAL_P(zlow), Z_STRLEN_P(zlow), NULL, NULL, 0);
2112		type2 = is_numeric_string(Z_STRVAL_P(zhigh), Z_STRLEN_P(zhigh), NULL, NULL, 0);
2113
2114		if (type1 == IS_DOUBLE || type2 == IS_DOUBLE || is_step_double) {
2115			goto double_str;
2116		} else if (type1 == IS_LONG || type2 == IS_LONG) {
2117			goto long_str;
2118		}
2119
2120		low = (unsigned char)Z_STRVAL_P(zlow)[0];
2121		high = (unsigned char)Z_STRVAL_P(zhigh)[0];
2122
2123		if (low > high) {		/* Negative Steps */
2124			if (lstep <= 0) {
2125				err = 1;
2126				goto err;
2127			}
2128			/* Initialize the return_value as an array. */
2129			array_init_size(return_value, (uint32_t)(((low - high) / lstep) + 1));
2130			zend_hash_real_init(Z_ARRVAL_P(return_value), 1);
2131			ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(return_value)) {
2132				for (; low >= high; low -= (unsigned int)lstep) {
2133					if (CG(one_char_string)[low]) {
2134						ZVAL_INTERNED_STR(&tmp, CG(one_char_string)[low]);
2135					} else {
2136						ZVAL_STRINGL(&tmp, (char*)&low, 1);
2137					}
2138					ZEND_HASH_FILL_ADD(&tmp);
2139					if (((signed int)low - lstep) < 0) {
2140						break;
2141					}
2142				}
2143			} ZEND_HASH_FILL_END();
2144		} else if (high > low) {	/* Positive Steps */
2145			if (lstep <= 0) {
2146				err = 1;
2147				goto err;
2148			}
2149			array_init_size(return_value, (uint32_t)(((high - low) / lstep) + 1));
2150			zend_hash_real_init(Z_ARRVAL_P(return_value), 1);
2151			ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(return_value)) {
2152				for (; low <= high; low += (unsigned int)lstep) {
2153					if (CG(one_char_string)[low]) {
2154						ZVAL_INTERNED_STR(&tmp, CG(one_char_string)[low]);
2155					} else {
2156						ZVAL_STRINGL(&tmp, (char*)&low, 1);
2157					}
2158					ZEND_HASH_FILL_ADD(&tmp);
2159					if (((signed int)low + lstep) > 255) {
2160						break;
2161					}
2162				}
2163			} ZEND_HASH_FILL_END();
2164		} else {
2165			array_init(return_value);
2166			if (CG(one_char_string)[low]) {
2167				ZVAL_INTERNED_STR(&tmp, CG(one_char_string)[low]);
2168			} else {
2169				ZVAL_STRINGL(&tmp, (char*)&low, 1);
2170			}
2171			zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &tmp);
2172		}
2173	} else if (Z_TYPE_P(zlow) == IS_DOUBLE || Z_TYPE_P(zhigh) == IS_DOUBLE || is_step_double) {
2174		double low, high;
2175		uint32_t i, size;
2176double_str:
2177		low = zval_get_double(zlow);
2178		high = zval_get_double(zhigh);
2179
2180		if (zend_isinf(high) || zend_isinf(low)) {
2181			php_error_docref(NULL, E_WARNING, "Invalid range supplied: start=%0.0f end=%0.0f", low, high);
2182			RETURN_FALSE;
2183		}
2184
2185		Z_TYPE_INFO(tmp) = IS_DOUBLE;
2186		if (low > high) { 		/* Negative steps */
2187			if (low - high < step || step <= 0) {
2188				err = 1;
2189				goto err;
2190			}
2191
2192			RANGE_CHECK_DOUBLE_INIT_ARRAY(low, high);
2193
2194			ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(return_value)) {
2195				for (i = 0; i < size; ++i) {
2196					Z_DVAL(tmp) = low - (i * step);
2197					ZEND_HASH_FILL_ADD(&tmp);
2198				}
2199			} ZEND_HASH_FILL_END();
2200		} else if (high > low) { 	/* Positive steps */
2201			if (high - low < step || step <= 0) {
2202				err = 1;
2203				goto err;
2204			}
2205
2206			RANGE_CHECK_DOUBLE_INIT_ARRAY(high, low);
2207
2208			ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(return_value)) {
2209				for (i = 0; i < size; ++i) {
2210					Z_DVAL(tmp) = low + (i * step);
2211					ZEND_HASH_FILL_ADD(&tmp);
2212				}
2213			} ZEND_HASH_FILL_END();
2214		} else {
2215			array_init(return_value);
2216			Z_DVAL(tmp) = low;
2217			zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &tmp);
2218		}
2219	} else {
2220		zend_long low, high;
2221		/* lstep is a ulong so that comparisons to it don't overflow, i.e. low - high < lstep */
2222		zend_ulong lstep;
2223		uint32_t i, size;
2224long_str:
2225		low = zval_get_long(zlow);
2226		high = zval_get_long(zhigh);
2227
2228		if (step <= 0) {
2229			err = 1;
2230			goto err;
2231		}
2232
2233		lstep = step;
2234
2235		Z_TYPE_INFO(tmp) = IS_LONG;
2236		if (low > high) { 		/* Negative steps */
2237			if (low - high < lstep) {
2238				err = 1;
2239				goto err;
2240			}
2241
2242			RANGE_CHECK_LONG_INIT_ARRAY(low, high);
2243
2244			ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(return_value)) {
2245				for (i = 0; i < size; ++i) {
2246					Z_LVAL(tmp) = low - (i * lstep);
2247					ZEND_HASH_FILL_ADD(&tmp);
2248				}
2249			} ZEND_HASH_FILL_END();
2250		} else if (high > low) { 	/* Positive steps */
2251			if (high - low < lstep) {
2252				err = 1;
2253				goto err;
2254			}
2255
2256			RANGE_CHECK_LONG_INIT_ARRAY(high, low);
2257
2258			ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(return_value)) {
2259				for (i = 0; i < size; ++i) {
2260					Z_LVAL(tmp) = low + (i * lstep);
2261					ZEND_HASH_FILL_ADD(&tmp);
2262				}
2263			} ZEND_HASH_FILL_END();
2264		} else {
2265			array_init(return_value);
2266			Z_LVAL(tmp) = low;
2267			zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &tmp);
2268		}
2269	}
2270err:
2271	if (err) {
2272		php_error_docref(NULL, E_WARNING, "step exceeds the specified range");
2273		RETURN_FALSE;
2274	}
2275}
2276/* }}} */
2277
2278#undef RANGE_CHECK_DOUBLE_INIT_ARRAY
2279#undef RANGE_CHECK_LONG_INIT_ARRAY
2280
2281static void php_array_data_shuffle(zval *array) /* {{{ */
2282{
2283	uint32_t idx, j, n_elems;
2284	Bucket *p, temp;
2285	HashTable *hash;
2286	zend_long rnd_idx;
2287	uint32_t n_left;
2288
2289	n_elems = zend_hash_num_elements(Z_ARRVAL_P(array));
2290
2291	if (n_elems < 1) {
2292		return;
2293	}
2294
2295	hash = Z_ARRVAL_P(array);
2296	n_left = n_elems;
2297
2298	if (EXPECTED(hash->u.v.nIteratorsCount == 0)) {
2299		if (hash->nNumUsed != hash->nNumOfElements) {
2300			for (j = 0, idx = 0; idx < hash->nNumUsed; idx++) {
2301				p = hash->arData + idx;
2302				if (Z_TYPE(p->val) == IS_UNDEF) continue;
2303				if (j != idx) {
2304					hash->arData[j] = *p;
2305				}
2306				j++;
2307			}
2308		}
2309		while (--n_left) {
2310			rnd_idx = php_rand();
2311			RAND_RANGE(rnd_idx, 0, n_left, PHP_RAND_MAX);
2312			if (rnd_idx != n_left) {
2313				temp = hash->arData[n_left];
2314				hash->arData[n_left] = hash->arData[rnd_idx];
2315				hash->arData[rnd_idx] = temp;
2316			}
2317		}
2318	} else {
2319		uint32_t iter_pos = zend_hash_iterators_lower_pos(hash, 0);
2320
2321		if (hash->nNumUsed != hash->nNumOfElements) {
2322			for (j = 0, idx = 0; idx < hash->nNumUsed; idx++) {
2323				p = hash->arData + idx;
2324				if (Z_TYPE(p->val) == IS_UNDEF) continue;
2325				if (j != idx) {
2326					hash->arData[j] = *p;
2327					if (idx == iter_pos) {
2328						zend_hash_iterators_update(hash, idx, j);
2329						iter_pos = zend_hash_iterators_lower_pos(hash, iter_pos + 1);
2330					}
2331				}
2332				j++;
2333			}
2334		}
2335		while (--n_left) {
2336			rnd_idx = php_rand();
2337			RAND_RANGE(rnd_idx, 0, n_left, PHP_RAND_MAX);
2338			if (rnd_idx != n_left) {
2339				temp = hash->arData[n_left];
2340				hash->arData[n_left] = hash->arData[rnd_idx];
2341				hash->arData[rnd_idx] = temp;
2342				zend_hash_iterators_update(hash, (uint32_t)rnd_idx, n_left);
2343			}
2344		}
2345	}
2346	HANDLE_BLOCK_INTERRUPTIONS();
2347	hash->nNumUsed = n_elems;
2348	hash->nInternalPointer = 0;
2349
2350	for (j = 0; j < n_elems; j++) {
2351		p = hash->arData + j;
2352		if (p->key) {
2353			zend_string_release(p->key);
2354		}
2355		p->h = j;
2356		p->key = NULL;
2357	}
2358	hash->nNextFreeElement = n_elems;
2359	if (!(hash->u.flags & HASH_FLAG_PACKED)) {
2360		zend_hash_to_packed(hash);
2361	}
2362	HANDLE_UNBLOCK_INTERRUPTIONS();
2363}
2364/* }}} */
2365
2366/* {{{ proto bool shuffle(array array_arg)
2367   Randomly shuffle the contents of an array */
2368PHP_FUNCTION(shuffle)
2369{
2370	zval *array;
2371
2372	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a/", &array) == FAILURE) {
2373		RETURN_FALSE;
2374	}
2375
2376	php_array_data_shuffle(array);
2377
2378	RETURN_TRUE;
2379}
2380/* }}} */
2381
2382static void php_splice(HashTable *in_hash, int offset, int length, HashTable *replace, HashTable *removed) /* {{{ */
2383{
2384	HashTable 	 out_hash;			/* Output hashtable */
2385	int			 num_in,			/* Number of entries in the input hashtable */
2386				 pos;				/* Current position in the hashtable */
2387	uint         idx;
2388	Bucket		*p;					/* Pointer to hash bucket */
2389	zval		*entry;				/* Hash entry */
2390	uint32_t    iter_pos = zend_hash_iterators_lower_pos(in_hash, 0);
2391
2392	/* Get number of entries in the input hash */
2393	num_in = zend_hash_num_elements(in_hash);
2394
2395	/* Clamp the offset.. */
2396	if (offset > num_in) {
2397		offset = num_in;
2398	} else if (offset < 0 && (offset = (num_in + offset)) < 0) {
2399		offset = 0;
2400	}
2401
2402	/* ..and the length */
2403	if (length < 0) {
2404		length = num_in - offset + length;
2405	} else if (((unsigned)offset + (unsigned)length) > (unsigned)num_in) {
2406		length = num_in - offset;
2407	}
2408
2409	/* Create and initialize output hash */
2410	zend_hash_init(&out_hash, (length > 0 ? num_in - length : 0) + (replace ? zend_hash_num_elements(replace) : 0), NULL, ZVAL_PTR_DTOR, 0);
2411
2412	/* Start at the beginning of the input hash and copy entries to output hash until offset is reached */
2413	for (pos = 0, idx = 0; pos < offset && idx < in_hash->nNumUsed; idx++) {
2414		p = in_hash->arData + idx;
2415		if (Z_TYPE(p->val) == IS_UNDEF) continue;
2416		/* Get entry and increase reference count */
2417		entry = &p->val;
2418
2419		/* Update output hash depending on key type */
2420		if (p->key == NULL) {
2421			zend_hash_next_index_insert_new(&out_hash, entry);
2422		} else {
2423			zend_hash_add_new(&out_hash, p->key, entry);
2424		}
2425		if (idx == iter_pos) {
2426			if (idx != pos) {
2427				zend_hash_iterators_update(in_hash, idx, pos);
2428			}
2429			iter_pos = zend_hash_iterators_lower_pos(in_hash, iter_pos + 1);
2430		}
2431		pos++;
2432	}
2433
2434	/* If hash for removed entries exists, go until offset+length and copy the entries to it */
2435	if (removed != NULL) {
2436		for ( ; pos < offset + length && idx < in_hash->nNumUsed; idx++) {
2437			p = in_hash->arData + idx;
2438			if (Z_TYPE(p->val) == IS_UNDEF) continue;
2439			pos++;
2440			entry = &p->val;
2441			if (Z_REFCOUNTED_P(entry)) {
2442				Z_ADDREF_P(entry);
2443			}
2444			if (p->key == NULL) {
2445				zend_hash_next_index_insert_new(removed, entry);
2446				zend_hash_index_del(in_hash, p->h);
2447			} else {
2448				zend_hash_add_new(removed, p->key, entry);
2449				if (in_hash == &EG(symbol_table)) {
2450					zend_delete_global_variable(p->key);
2451				} else {
2452					zend_hash_del(in_hash, p->key);
2453				}
2454			}
2455		}
2456	} else { /* otherwise just skip those entries */
2457		int pos2 = pos;
2458
2459		for ( ; pos2 < offset + length && idx < in_hash->nNumUsed; idx++) {
2460			p = in_hash->arData + idx;
2461			if (Z_TYPE(p->val) == IS_UNDEF) continue;
2462			pos2++;
2463			if (p->key == NULL) {
2464				zend_hash_index_del(in_hash, p->h);
2465			} else {
2466				if (in_hash == &EG(symbol_table)) {
2467					zend_delete_global_variable(p->key);
2468				} else {
2469					zend_hash_del(in_hash, p->key);
2470				}
2471			}
2472		}
2473	}
2474	iter_pos = zend_hash_iterators_lower_pos(in_hash, iter_pos);
2475
2476	/* If there are entries to insert.. */
2477	if (replace) {
2478		ZEND_HASH_FOREACH_VAL_IND(replace, entry) {
2479			if (Z_REFCOUNTED_P(entry)) Z_ADDREF_P(entry);
2480			zend_hash_next_index_insert_new(&out_hash, entry);
2481			pos++;
2482		} ZEND_HASH_FOREACH_END();
2483	}
2484
2485	/* Copy the remaining input hash entries to the output hash */
2486	for ( ; idx < in_hash->nNumUsed ; idx++) {
2487		p = in_hash->arData + idx;
2488		if (Z_TYPE(p->val) == IS_UNDEF) continue;
2489		entry = &p->val;
2490		if (p->key == NULL) {
2491			zend_hash_next_index_insert_new(&out_hash, entry);
2492		} else {
2493			zend_hash_add_new(&out_hash, p->key, entry);
2494		}
2495		if (idx == iter_pos) {
2496			if (idx != pos) {
2497				zend_hash_iterators_update(in_hash, idx, pos);
2498			}
2499			iter_pos = zend_hash_iterators_lower_pos(in_hash, iter_pos + 1);
2500		}
2501		pos++;
2502	}
2503
2504	/* replace HashTable data */
2505	in_hash->u.v.nIteratorsCount = 0;
2506	in_hash->pDestructor = NULL;
2507	zend_hash_destroy(in_hash);
2508
2509	in_hash->u.v.flags         = out_hash.u.v.flags;
2510	in_hash->nTableSize        = out_hash.nTableSize;
2511	in_hash->nTableMask        = out_hash.nTableMask;
2512	in_hash->nNumUsed          = out_hash.nNumUsed;
2513	in_hash->nNumOfElements    = out_hash.nNumOfElements;
2514	in_hash->nNextFreeElement  = out_hash.nNextFreeElement;
2515	in_hash->arData            = out_hash.arData;
2516	in_hash->pDestructor       = out_hash.pDestructor;
2517
2518	zend_hash_internal_pointer_reset(in_hash);
2519}
2520/* }}} */
2521
2522/* {{{ proto int array_push(array stack, mixed var [, mixed ...])
2523   Pushes elements onto the end of the array */
2524PHP_FUNCTION(array_push)
2525{
2526	zval   *args,		/* Function arguments array */
2527		   *stack,		/* Input array */
2528		    new_var;	/* Variable to be pushed */
2529	int i,				/* Loop counter */
2530		argc;			/* Number of function arguments */
2531
2532
2533	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a/+", &stack, &args, &argc) == FAILURE) {
2534		return;
2535	}
2536
2537	/* For each subsequent argument, make it a reference, increase refcount, and add it to the end of the array */
2538	for (i = 0; i < argc; i++) {
2539		ZVAL_COPY(&new_var, &args[i]);
2540
2541		if (zend_hash_next_index_insert(Z_ARRVAL_P(stack), &new_var) == NULL) {
2542			if (Z_REFCOUNTED(new_var)) Z_DELREF(new_var);
2543			php_error_docref(NULL, E_WARNING, "Cannot add element to the array as the next element is already occupied");
2544			RETURN_FALSE;
2545		}
2546	}
2547
2548	/* Clean up and return the number of values in the stack */
2549	RETVAL_LONG(zend_hash_num_elements(Z_ARRVAL_P(stack)));
2550}
2551/* }}} */
2552
2553/* {{{ proto mixed array_pop(array stack)
2554   Pops an element off the end of the array */
2555PHP_FUNCTION(array_pop)
2556{
2557	zval *stack,	/* Input stack */
2558		 *val;		/* Value to be popped */
2559	uint32_t idx;
2560	Bucket *p;
2561
2562#ifndef FAST_ZPP
2563	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a/", &stack) == FAILURE) {
2564		return;
2565	}
2566#else
2567	ZEND_PARSE_PARAMETERS_START(1, 1)
2568		Z_PARAM_ARRAY_EX(stack, 0, 1)
2569	ZEND_PARSE_PARAMETERS_END();
2570#endif
2571
2572	if (zend_hash_num_elements(Z_ARRVAL_P(stack)) == 0) {
2573		return;
2574	}
2575
2576	/* Get the last value and copy it into the return value */
2577	idx = Z_ARRVAL_P(stack)->nNumUsed;
2578	while (1) {
2579		if (idx == 0) {
2580			return;
2581		}
2582		idx--;
2583		p = Z_ARRVAL_P(stack)->arData + idx;
2584		val = &p->val;
2585		if (Z_TYPE_P(val) == IS_INDIRECT) {
2586			val = Z_INDIRECT_P(val);
2587		}
2588		if (Z_TYPE_P(val) != IS_UNDEF) {
2589			break;
2590		}
2591	}
2592	ZVAL_DEREF(val);
2593	ZVAL_COPY(return_value, val);
2594
2595	if (!p->key && Z_ARRVAL_P(stack)->nNextFreeElement > 0 && p->h >= (zend_ulong)(Z_ARRVAL_P(stack)->nNextFreeElement - 1)) {
2596		Z_ARRVAL_P(stack)->nNextFreeElement = Z_ARRVAL_P(stack)->nNextFreeElement - 1;
2597	}
2598
2599	/* Delete the last value */
2600	if (p->key) {
2601		if (Z_ARRVAL_P(stack) == &EG(symbol_table)) {
2602			zend_delete_global_variable(p->key);
2603		} else {
2604			zend_hash_del(Z_ARRVAL_P(stack), p->key);
2605		}
2606	} else {
2607		zend_hash_index_del(Z_ARRVAL_P(stack), p->h);
2608	}
2609
2610	zend_hash_internal_pointer_reset(Z_ARRVAL_P(stack));
2611}
2612/* }}} */
2613
2614/* {{{ proto mixed array_shift(array stack)
2615   Pops an element off the beginning of the array */
2616PHP_FUNCTION(array_shift)
2617{
2618	zval *stack,	/* Input stack */
2619		 *val;		/* Value to be popped */
2620	uint32_t idx;
2621	Bucket *p;
2622
2623#ifndef FAST_ZPP
2624	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a/", &stack) == FAILURE) {
2625		return;
2626	}
2627#else
2628	ZEND_PARSE_PARAMETERS_START(1, 1)
2629		Z_PARAM_ARRAY_EX(stack, 0, 1)
2630	ZEND_PARSE_PARAMETERS_END();
2631#endif
2632
2633	if (zend_hash_num_elements(Z_ARRVAL_P(stack)) == 0) {
2634		return;
2635	}
2636
2637	/* Get the first value and copy it into the return value */
2638	idx = 0;
2639	while (1) {
2640		if (idx == Z_ARRVAL_P(stack)->nNumUsed) {
2641			return;
2642		}
2643		p = Z_ARRVAL_P(stack)->arData + idx;
2644		val = &p->val;
2645		if (Z_TYPE_P(val) == IS_INDIRECT) {
2646			val = Z_INDIRECT_P(val);
2647		}
2648		if (Z_TYPE_P(val) != IS_UNDEF) {
2649			break;
2650		}
2651		idx++;
2652	}
2653	ZVAL_DEREF(val);
2654	ZVAL_COPY(return_value, val);
2655
2656	/* Delete the first value */
2657	if (p->key) {
2658		if (Z_ARRVAL_P(stack) == &EG(symbol_table)) {
2659			zend_delete_global_variable(p->key);
2660		} else {
2661			zend_hash_del(Z_ARRVAL_P(stack), p->key);
2662		}
2663	} else {
2664		zend_hash_index_del(Z_ARRVAL_P(stack), p->h);
2665	}
2666
2667	/* re-index like it did before */
2668	if (Z_ARRVAL_P(stack)->u.flags & HASH_FLAG_PACKED) {
2669		uint32_t k = 0;
2670
2671		if (EXPECTED(Z_ARRVAL_P(stack)->u.v.nIteratorsCount == 0)) {
2672			for (idx = 0; idx < Z_ARRVAL_P(stack)->nNumUsed; idx++) {
2673				p = Z_ARRVAL_P(stack)->arData + idx;
2674				if (Z_TYPE(p->val) == IS_UNDEF) continue;
2675				if (idx != k) {
2676					Bucket *q = Z_ARRVAL_P(stack)->arData + k;
2677					q->h = k;
2678					q->key = NULL;
2679					ZVAL_COPY_VALUE(&q->val, &p->val);
2680					ZVAL_UNDEF(&p->val);
2681				}
2682				k++;
2683			}
2684		} else {
2685			uint32_t iter_pos = zend_hash_iterators_lower_pos(Z_ARRVAL_P(stack), 0);
2686
2687			for (idx = 0; idx < Z_ARRVAL_P(stack)->nNumUsed; idx++) {
2688				p = Z_ARRVAL_P(stack)->arData + idx;
2689				if (Z_TYPE(p->val) == IS_UNDEF) continue;
2690				if (idx != k) {
2691					Bucket *q = Z_ARRVAL_P(stack)->arData + k;
2692					q->h = k;
2693					q->key = NULL;
2694					ZVAL_COPY_VALUE(&q->val, &p->val);
2695					ZVAL_UNDEF(&p->val);
2696					if (idx == iter_pos) {
2697						zend_hash_iterators_update(Z_ARRVAL_P(stack), idx, k);
2698						iter_pos = zend_hash_iterators_lower_pos(Z_ARRVAL_P(stack), iter_pos + 1);
2699					}
2700				}
2701				k++;
2702			}
2703		}
2704		Z_ARRVAL_P(stack)->nNumUsed = k;
2705		Z_ARRVAL_P(stack)->nNextFreeElement = k;
2706	} else {
2707		uint32_t k = 0;
2708		int should_rehash = 0;
2709
2710		for (idx = 0; idx < Z_ARRVAL_P(stack)->nNumUsed; idx++) {
2711			p = Z_ARRVAL_P(stack)->arData + idx;
2712			if (Z_TYPE(p->val) == IS_UNDEF) continue;
2713			if (p->key == NULL) {
2714				if (p->h != k) {
2715					p->h = k++;
2716					should_rehash = 1;
2717				} else {
2718					k++;
2719				}
2720			}
2721		}
2722		Z_ARRVAL_P(stack)->nNextFreeElement = k;
2723		if (should_rehash) {
2724			zend_hash_rehash(Z_ARRVAL_P(stack));
2725		}
2726	}
2727
2728	zend_hash_internal_pointer_reset(Z_ARRVAL_P(stack));
2729}
2730/* }}} */
2731
2732/* {{{ proto int array_unshift(array stack, mixed var [, mixed ...])
2733   Pushes elements onto the beginning of the array */
2734PHP_FUNCTION(array_unshift)
2735{
2736	zval   *args,			/* Function arguments array */
2737		   *stack;			/* Input stack */
2738	HashTable new_hash;		/* New hashtable for the stack */
2739	int argc;				/* Number of function arguments */
2740	int i;
2741	zend_string *key;
2742	zval *value;
2743
2744	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a/+", &stack, &args, &argc) == FAILURE) {
2745		return;
2746	}
2747
2748	zend_hash_init(&new_hash, zend_hash_num_elements(Z_ARRVAL_P(stack)) + argc, NULL, ZVAL_PTR_DTOR, 0);
2749	for (i = 0; i < argc; i++) {
2750		if (Z_REFCOUNTED(args[i])) {
2751			Z_ADDREF(args[i]);
2752		}
2753		zend_hash_next_index_insert_new(&new_hash, &args[i]);
2754	}
2755	if (EXPECTED(Z_ARRVAL_P(stack)->u.v.nIteratorsCount == 0)) {
2756		ZEND_HASH_FOREACH_STR_KEY_VAL(Z_ARRVAL_P(stack), key, value) {
2757			if (key) {
2758				zend_hash_add_new(&new_hash, key, value);
2759			} else {
2760				zend_hash_next_index_insert_new(&new_hash, value);
2761			}
2762		} ZEND_HASH_FOREACH_END();
2763	} else {
2764		uint32_t old_idx;
2765		uint32_t new_idx = i;
2766		uint32_t iter_pos = zend_hash_iterators_lower_pos(Z_ARRVAL_P(stack), 0);
2767
2768		ZEND_HASH_FOREACH_STR_KEY_VAL(Z_ARRVAL_P(stack), key, value) {
2769			if (key) {
2770				zend_hash_add_new(&new_hash, key, value);
2771			} else {
2772				zend_hash_next_index_insert_new(&new_hash, value);
2773			}
2774			old_idx = (Bucket*)value - Z_ARRVAL_P(stack)->arData;
2775			if (old_idx == iter_pos) {
2776				zend_hash_iterators_update(Z_ARRVAL_P(stack), old_idx, new_idx);
2777				iter_pos = zend_hash_iterators_lower_pos(Z_ARRVAL_P(stack), iter_pos + 1);
2778			}
2779			new_idx++;
2780		} ZEND_HASH_FOREACH_END();
2781	}
2782
2783	/* replace HashTable data */
2784	Z_ARRVAL_P(stack)->u.v.nIteratorsCount = 0;
2785	Z_ARRVAL_P(stack)->pDestructor = NULL;
2786	zend_hash_destroy(Z_ARRVAL_P(stack));
2787
2788	Z_ARRVAL_P(stack)->u.v.flags         = new_hash.u.v.flags;
2789	Z_ARRVAL_P(stack)->nTableSize        = new_hash.nTableSize;
2790	Z_ARRVAL_P(stack)->nTableMask        = new_hash.nTableMask;
2791	Z_ARRVAL_P(stack)->nNumUsed          = new_hash.nNumUsed;
2792	Z_ARRVAL_P(stack)->nNumOfElements    = new_hash.nNumOfElements;
2793	Z_ARRVAL_P(stack)->nNextFreeElement  = new_hash.nNextFreeElement;
2794	Z_ARRVAL_P(stack)->arData            = new_hash.arData;
2795	Z_ARRVAL_P(stack)->pDestructor       = new_hash.pDestructor;
2796
2797	zend_hash_internal_pointer_reset(Z_ARRVAL_P(stack));
2798
2799	/* Clean up and return the number of elements in the stack */
2800	RETVAL_LONG(zend_hash_num_elements(Z_ARRVAL_P(stack)));
2801}
2802/* }}} */
2803
2804/* {{{ proto array array_splice(array input, int offset [, int length [, array replacement]])
2805   Removes the elements designated by offset and length and replace them with supplied array */
2806PHP_FUNCTION(array_splice)
2807{
2808	zval *array,				/* Input array */
2809		 *repl_array = NULL;	/* Replacement array */
2810	HashTable  *rem_hash = NULL;
2811	zend_long offset,
2812			length = 0;
2813	int		num_in;				/* Number of elements in the input array */
2814
2815	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a/l|lz/", &array, &offset, &length, &repl_array) == FAILURE) {
2816		return;
2817	}
2818
2819	num_in = zend_hash_num_elements(Z_ARRVAL_P(array));
2820
2821	if (ZEND_NUM_ARGS() < 3) {
2822		length = num_in;
2823	}
2824
2825	if (ZEND_NUM_ARGS() == 4) {
2826		/* Make sure the last argument, if passed, is an array */
2827		convert_to_array_ex(repl_array);
2828	}
2829
2830	/* Don't create the array of removed elements if it's not going
2831	 * to be used; e.g. only removing and/or replacing elements */
2832	if (USED_RET()) {
2833		zend_long size = length;
2834
2835		/* Clamp the offset.. */
2836		if (offset > num_in) {
2837			offset = num_in;
2838		} else if (offset < 0 && (offset = (num_in + offset)) < 0) {
2839			offset = 0;
2840		}
2841
2842		/* ..and the length */
2843		if (length < 0) {
2844			size = num_in - offset + length;
2845		} else if (((zend_ulong) offset + (zend_ulong) length) > (uint32_t) num_in) {
2846			size = num_in - offset;
2847		}
2848
2849		/* Initialize return value */
2850		array_init_size(return_value, size > 0 ? (uint32_t)size : 0);
2851		rem_hash = Z_ARRVAL_P(return_value);
2852	}
2853
2854	/* Perform splice */
2855	php_splice(Z_ARRVAL_P(array), (int)offset, (int)length, repl_array ? Z_ARRVAL_P(repl_array) : NULL, rem_hash);
2856}
2857/* }}} */
2858
2859/* {{{ proto array array_slice(array input, int offset [, int length [, bool preserve_keys]])
2860   Returns elements specified by offset and length */
2861PHP_FUNCTION(array_slice)
2862{
2863	zval	 *input,		/* Input array */
2864			 *z_length = NULL, /* How many elements to get */
2865			 *entry;		/* An array entry */
2866	zend_long	 offset,		/* Offset to get elements from */
2867			 length = 0;
2868	zend_bool preserve_keys = 0; /* Whether to preserve keys while copying to the new array or not */
2869	int		 num_in,		/* Number of elements in the input array */
2870			 pos;			/* Current position in the array */
2871	zend_string *string_key;
2872	zend_ulong num_key;
2873
2874#ifndef FAST_ZPP
2875	if (zend_parse_parameters(ZEND_NUM_ARGS(), "al|zb", &input, &offset, &z_length, &preserve_keys) == FAILURE) {
2876		return;
2877	}
2878#else
2879	ZEND_PARSE_PARAMETERS_START(2, 4)
2880		Z_PARAM_ARRAY(input)
2881		Z_PARAM_LONG(offset)
2882		Z_PARAM_OPTIONAL
2883		Z_PARAM_ZVAL(z_length)
2884		Z_PARAM_BOOL(preserve_keys)
2885	ZEND_PARSE_PARAMETERS_END();
2886#endif
2887
2888	/* Get number of entries in the input hash */
2889	num_in = zend_hash_num_elements(Z_ARRVAL_P(input));
2890
2891	/* We want all entries from offset to the end if length is not passed or is null */
2892	if (ZEND_NUM_ARGS() < 3 || Z_TYPE_P(z_length) == IS_NULL) {
2893		length = num_in;
2894	} else {
2895		length = zval_get_long(z_length);
2896	}
2897
2898	/* Clamp the offset.. */
2899	if (offset > num_in) {
2900		array_init(return_value);
2901		return;
2902	} else if (offset < 0 && (offset = (num_in + offset)) < 0) {
2903		offset = 0;
2904	}
2905
2906	/* ..and the length */
2907	if (length < 0) {
2908		length = num_in - offset + length;
2909	} else if (((zend_ulong) offset + (zend_ulong) length) > (unsigned) num_in) {
2910		length = num_in - offset;
2911	}
2912
2913	if (length <= 0) {
2914		array_init(return_value);
2915		return;
2916	}
2917
2918	/* Initialize returned array */
2919	array_init_size(return_value, (uint32_t)length);
2920
2921	/* Start at the beginning and go until we hit offset */
2922	pos = 0;
2923	if (!preserve_keys && (Z_ARRVAL_P(input)->u.flags & HASH_FLAG_PACKED)) {
2924		zend_hash_real_init(Z_ARRVAL_P(return_value), 1);
2925		ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(return_value)) {
2926			ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(input), entry) {
2927				pos++;
2928				if (pos <= offset) {
2929					continue;
2930				}
2931				if (pos > offset + length) {
2932					break;
2933				}
2934				ZEND_HASH_FILL_ADD(entry);
2935				zval_add_ref(entry);
2936			} ZEND_HASH_FOREACH_END();
2937		} ZEND_HASH_FILL_END();
2938	} else {
2939		ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(input), num_key, string_key, entry) {
2940			pos++;
2941			if (pos <= offset) {
2942				continue;
2943			}
2944			if (pos > offset + length) {
2945				break;
2946			}
2947
2948			if (string_key) {
2949				entry = zend_hash_add_new(Z_ARRVAL_P(return_value), string_key, entry);
2950			} else {
2951				if (preserve_keys) {
2952					entry = zend_hash_index_add_new(Z_ARRVAL_P(return_value), num_key, entry);
2953				} else {
2954					entry = zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), entry);
2955				}
2956			}
2957			zval_add_ref(entry);
2958		} ZEND_HASH_FOREACH_END();
2959	}
2960}
2961/* }}} */
2962
2963PHPAPI int php_array_merge_recursive(HashTable *dest, HashTable *src) /* {{{ */
2964{
2965	zval *src_entry, *dest_entry;
2966	zend_string *string_key;
2967
2968	ZEND_HASH_FOREACH_STR_KEY_VAL(src, string_key, src_entry) {
2969		if (string_key) {
2970			if ((dest_entry = zend_hash_find(dest, string_key)) != NULL) {
2971				zval *src_zval = src_entry;
2972				zval *dest_zval = dest_entry;
2973				HashTable *thash;
2974				zval tmp;
2975				int ret;
2976
2977				ZVAL_DEREF(src_zval);
2978				ZVAL_DEREF(dest_zval);
2979				thash = Z_TYPE_P(dest_zval) == IS_ARRAY ? Z_ARRVAL_P(dest_zval) : NULL;
2980				if ((thash && thash->u.v.nApplyCount > 1) || (src_entry == dest_entry && Z_ISREF_P(dest_entry) && (Z_REFCOUNT_P(dest_entry) % 2))) {
2981					php_error_docref(NULL, E_WARNING, "recursion detected");
2982					return 0;
2983				}
2984
2985				if (Z_ISREF_P(dest_entry)) {
2986					if (Z_REFCOUNT_P(dest_entry) == 1) {
2987						ZVAL_UNREF(dest_entry);
2988					} else {
2989						Z_DELREF_P(dest_entry);
2990						ZVAL_DUP(dest_entry, dest_zval);
2991					}
2992					dest_zval = dest_entry;
2993				} else {
2994					SEPARATE_ZVAL(dest_zval);
2995				}
2996				if (Z_TYPE_P(dest_zval) == IS_NULL) {
2997					convert_to_array_ex(dest_zval);
2998					add_next_index_null(dest_zval);
2999				} else if (Z_TYPE_P(dest_zval) == IS_ARRAY) {
3000					if (UNEXPECTED(Z_ARRVAL_P(dest_zval)->nNextFreeElement > Z_ARRVAL_P(dest_zval)->nNumUsed)) {
3001						Z_ARRVAL_P(dest_zval)->nNextFreeElement = Z_ARRVAL_P(dest_zval)->nNumUsed;
3002					}
3003				} else {
3004					convert_to_array_ex(dest_zval);
3005				}
3006				ZVAL_UNDEF(&tmp);
3007				if (Z_TYPE_P(src_zval) == IS_OBJECT) {
3008					ZVAL_COPY(&tmp, src_zval);
3009					convert_to_array(&tmp);
3010					src_zval = &tmp;
3011				}
3012				if (Z_TYPE_P(src_zval) == IS_ARRAY) {
3013					if (thash && ZEND_HASH_APPLY_PROTECTION(thash)) {
3014						thash->u.v.nApplyCount++;
3015					}
3016					ret = php_array_merge_recursive(Z_ARRVAL_P(dest_zval), Z_ARRVAL_P(src_zval));
3017					if (thash && ZEND_HASH_APPLY_PROTECTION(thash)) {
3018						thash->u.v.nApplyCount--;
3019					}
3020					if (!ret) {
3021						return 0;
3022					}
3023				} else {
3024					if (Z_REFCOUNTED_P(src_entry)) {
3025						Z_ADDREF_P(src_entry);
3026					}
3027					zend_hash_next_index_insert(Z_ARRVAL_P(dest_zval), src_zval);
3028				}
3029				zval_ptr_dtor(&tmp);
3030			} else {
3031				if (Z_REFCOUNTED_P(src_entry)) {
3032					Z_ADDREF_P(src_entry);
3033				}
3034				zend_hash_add_new(dest, string_key, src_entry);
3035			}
3036		} else {
3037			if (Z_REFCOUNTED_P(src_entry)) {
3038				Z_ADDREF_P(src_entry);
3039			}
3040			zend_hash_next_index_insert_new(dest, src_entry);
3041		}
3042	} ZEND_HASH_FOREACH_END();
3043	return 1;
3044}
3045/* }}} */
3046
3047PHPAPI int php_array_merge(HashTable *dest, HashTable *src) /* {{{ */
3048{
3049	zval *src_entry;
3050	zend_string *string_key;
3051
3052	ZEND_HASH_FOREACH_STR_KEY_VAL(src, string_key, src_entry) {
3053		if (string_key) {
3054			if (Z_REFCOUNTED_P(src_entry)) {
3055				Z_ADDREF_P(src_entry);
3056			}
3057			zend_hash_update(dest, string_key, src_entry);
3058		} else {
3059			if (Z_REFCOUNTED_P(src_entry)) {
3060				Z_ADDREF_P(src_entry);
3061			}
3062			zend_hash_next_index_insert_new(dest, src_entry);
3063		}
3064	} ZEND_HASH_FOREACH_END();
3065	return 1;
3066}
3067/* }}} */
3068
3069PHPAPI int php_array_replace_recursive(HashTable *dest, HashTable *src) /* {{{ */
3070{
3071	zval *src_entry, *dest_entry, *src_zval, *dest_zval;
3072	zend_string *string_key;
3073	zend_ulong num_key;
3074	int ret;
3075
3076	ZEND_HASH_FOREACH_KEY_VAL(src, num_key, string_key, src_entry) {
3077		src_zval = src_entry;
3078		ZVAL_DEREF(src_zval);
3079		if (string_key) {
3080			if (Z_TYPE_P(src_zval) != IS_ARRAY ||
3081				(dest_entry = zend_hash_find(dest, string_key)) == NULL ||
3082				(Z_TYPE_P(dest_entry) != IS_ARRAY &&
3083				 (!Z_ISREF_P(dest_entry) || Z_TYPE_P(Z_REFVAL_P(dest_entry)) != IS_ARRAY))) {
3084
3085				if (Z_REFCOUNTED_P(src_entry)) {
3086					Z_ADDREF_P(src_entry);
3087				}
3088				zend_hash_update(dest, string_key, src_entry);
3089
3090				continue;
3091			}
3092		} else {
3093			if (Z_TYPE_P(src_zval) != IS_ARRAY ||
3094				(dest_entry = zend_hash_index_find(dest, num_key)) == NULL ||
3095				(Z_TYPE_P(dest_entry) != IS_ARRAY &&
3096				 (!Z_ISREF_P(dest_entry) || Z_TYPE_P(Z_REFVAL_P(dest_entry)) != IS_ARRAY))) {
3097
3098				if (Z_REFCOUNTED_P(src_entry)) {
3099					Z_ADDREF_P(src_entry);
3100				}
3101				zend_hash_index_update(dest, num_key, src_entry);
3102
3103				continue;
3104			}
3105		}
3106
3107		dest_zval = dest_entry;
3108		ZVAL_DEREF(dest_zval);
3109		if (Z_ARRVAL_P(dest_zval)->u.v.nApplyCount > 1 ||
3110		    Z_ARRVAL_P(src_zval)->u.v.nApplyCount > 1 ||
3111		    (Z_ISREF_P(src_entry) && Z_ISREF_P(dest_entry) && Z_REF_P(src_entry) == Z_REF_P(dest_entry) && (Z_REFCOUNT_P(dest_entry) % 2))) {
3112			php_error_docref(NULL, E_WARNING, "recursion detected");
3113			return 0;
3114		}
3115		SEPARATE_ZVAL(dest_zval);
3116
3117		if (ZEND_HASH_APPLY_PROTECTION(Z_ARRVAL_P(dest_zval))) {
3118			Z_ARRVAL_P(dest_zval)->u.v.nApplyCount++;
3119		}
3120		if (ZEND_HASH_APPLY_PROTECTION(Z_ARRVAL_P(src_zval))) {
3121			Z_ARRVAL_P(src_zval)->u.v.nApplyCount++;
3122		}
3123
3124		ret = php_array_replace_recursive(Z_ARRVAL_P(dest_zval), Z_ARRVAL_P(src_zval));
3125
3126		if (ZEND_HASH_APPLY_PROTECTION(Z_ARRVAL_P(dest_zval))) {
3127			Z_ARRVAL_P(dest_zval)->u.v.nApplyCount--;
3128		}
3129		if (ZEND_HASH_APPLY_PROTECTION(Z_ARRVAL_P(src_zval))) {
3130			Z_ARRVAL_P(src_zval)->u.v.nApplyCount--;
3131		}
3132
3133		if (!ret) {
3134			return 0;
3135		}
3136	} ZEND_HASH_FOREACH_END();
3137
3138	return 1;
3139}
3140/* }}} */
3141
3142static inline void php_array_merge_or_replace_wrapper(INTERNAL_FUNCTION_PARAMETERS, int recursive, int replace) /* {{{ */
3143{
3144	zval *args = NULL;
3145	zval *arg;
3146	int argc, i, init_size = 0;
3147
3148#ifndef FAST_ZPP
3149	if (zend_parse_parameters(ZEND_NUM_ARGS(), "+", &args, &argc) == FAILURE) {
3150		return;
3151	}
3152#else
3153	ZEND_PARSE_PARAMETERS_START(1, -1)
3154		Z_PARAM_VARIADIC('+', args, argc)
3155	ZEND_PARSE_PARAMETERS_END();
3156#endif
3157
3158	for (i = 0; i < argc; i++) {
3159		zval *arg = args + i;
3160
3161		ZVAL_DEREF(arg);
3162		if (Z_TYPE_P(arg) != IS_ARRAY) {
3163			php_error_docref(NULL, E_WARNING, "Argument #%d is not an array", i + 1);
3164			RETURN_NULL();
3165		} else {
3166			int num = zend_hash_num_elements(Z_ARRVAL_P(arg));
3167
3168			if (num > init_size) {
3169				init_size = num;
3170			}
3171		}
3172	}
3173
3174	array_init_size(return_value, init_size);
3175
3176	if (replace) {
3177		zend_string *string_key;
3178		zval *src_entry;
3179		zend_ulong idx;
3180		HashTable *src, *dest;
3181
3182		/* copy first array */
3183		arg = args;
3184		ZVAL_DEREF(arg);
3185		src  = Z_ARRVAL_P(arg);
3186		dest = Z_ARRVAL_P(return_value);
3187		ZEND_HASH_FOREACH_KEY_VAL(src, idx, string_key, src_entry) {
3188			if (string_key) {
3189				if (Z_REFCOUNTED_P(src_entry)) {
3190					Z_ADDREF_P(src_entry);
3191				}
3192				zend_hash_add_new(dest, string_key, src_entry);
3193			} else {
3194				if (Z_REFCOUNTED_P(src_entry)) {
3195					Z_ADDREF_P(src_entry);
3196				}
3197				zend_hash_index_add_new(dest, idx, src_entry);
3198			}
3199		} ZEND_HASH_FOREACH_END();
3200
3201		if (recursive) {
3202			for (i = 1; i < argc; i++) {
3203				arg = args + i;
3204				ZVAL_DEREF(arg);
3205				php_array_replace_recursive(Z_ARRVAL_P(return_value), Z_ARRVAL_P(arg));
3206			}
3207		} else {
3208			for (i = 1; i < argc; i++) {
3209				arg = args + i;
3210				ZVAL_DEREF(arg);
3211				zend_hash_merge(Z_ARRVAL_P(return_value), Z_ARRVAL_P(arg), zval_add_ref, 1);
3212			}
3213		}
3214	} else {
3215		zend_string *string_key;
3216		zval *src_entry;
3217		HashTable *src, *dest;
3218
3219		/* copy first array */
3220		arg = args;
3221		ZVAL_DEREF(arg);
3222		src  = Z_ARRVAL_P(arg);
3223		dest = Z_ARRVAL_P(return_value);
3224		ZEND_HASH_FOREACH_STR_KEY_VAL(src, string_key, src_entry) {
3225			if (string_key) {
3226				if (Z_REFCOUNTED_P(src_entry)) {
3227					Z_ADDREF_P(src_entry);
3228				}
3229				zend_hash_add_new(dest, string_key, src_entry);
3230			} else {
3231				if (Z_REFCOUNTED_P(src_entry)) {
3232					Z_ADDREF_P(src_entry);
3233				}
3234				zend_hash_next_index_insert_new(dest, src_entry);
3235			}
3236		} ZEND_HASH_FOREACH_END();
3237
3238		if (recursive) {
3239			for (i = 1; i < argc; i++) {
3240				arg = args + i;
3241				ZVAL_DEREF(arg);
3242				php_array_merge_recursive(Z_ARRVAL_P(return_value), Z_ARRVAL_P(arg));
3243			}
3244		} else {
3245			for (i = 1; i < argc; i++) {
3246				arg = args + i;
3247				ZVAL_DEREF(arg);
3248				php_array_merge(Z_ARRVAL_P(return_value), Z_ARRVAL_P(arg));
3249			}
3250		}
3251	}
3252}
3253/* }}} */
3254
3255/* {{{ proto array array_merge(array arr1, array arr2 [, array ...])
3256   Merges elements from passed arrays into one array */
3257PHP_FUNCTION(array_merge)
3258{
3259	php_array_merge_or_replace_wrapper(INTERNAL_FUNCTION_PARAM_PASSTHRU, 0, 0);
3260}
3261/* }}} */
3262
3263/* {{{ proto array array_merge_recursive(array arr1, array arr2 [, array ...])
3264   Recursively merges elements from passed arrays into one array */
3265PHP_FUNCTION(array_merge_recursive)
3266{
3267	php_array_merge_or_replace_wrapper(INTERNAL_FUNCTION_PARAM_PASSTHRU, 1, 0);
3268}
3269/* }}} */
3270
3271/* {{{ proto array array_replace(array arr1, array arr2 [, array ...])
3272   Replaces elements from passed arrays into one array */
3273PHP_FUNCTION(array_replace)
3274{
3275	php_array_merge_or_replace_wrapper(INTERNAL_FUNCTION_PARAM_PASSTHRU, 0, 1);
3276}
3277/* }}} */
3278
3279/* {{{ proto array array_replace_recursive(array arr1, array arr2 [, array ...])
3280   Recursively replaces elements from passed arrays into one array */
3281PHP_FUNCTION(array_replace_recursive)
3282{
3283	php_array_merge_or_replace_wrapper(INTERNAL_FUNCTION_PARAM_PASSTHRU, 1, 1);
3284}
3285/* }}} */
3286
3287/* {{{ proto array array_keys(array input [, mixed search_value[, bool strict]])
3288   Return just the keys from the input array, optionally only for the specified search_value */
3289PHP_FUNCTION(array_keys)
3290{
3291	zval *input,				/* Input array */
3292	     *search_value = NULL,	/* Value to search for */
3293	     *entry,				/* An entry in the input array */
3294	       new_val;				/* New value */
3295	zend_bool strict = 0;		/* do strict comparison */
3296	zend_ulong num_idx;
3297	zend_string *str_idx;
3298
3299#ifndef FAST_ZPP
3300	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a|zb", &input, &search_value, &strict) == FAILURE) {
3301		return;
3302	}
3303#else
3304	ZEND_PARSE_PARAMETERS_START(1, 3)
3305		Z_PARAM_ARRAY(input)
3306		Z_PARAM_OPTIONAL
3307		Z_PARAM_ZVAL(search_value)
3308		Z_PARAM_BOOL(strict)
3309	ZEND_PARSE_PARAMETERS_END();
3310#endif
3311
3312	/* Initialize return array */
3313	if (search_value != NULL) {
3314		array_init(return_value);
3315
3316		if (strict) {
3317			ZEND_HASH_FOREACH_KEY_VAL_IND(Z_ARRVAL_P(input), num_idx, str_idx, entry) {
3318				ZVAL_DEREF(entry);
3319				if (fast_is_identical_function(search_value, entry)) {
3320					if (str_idx) {
3321						ZVAL_STR_COPY(&new_val, str_idx);
3322					} else {
3323						ZVAL_LONG(&new_val, num_idx);
3324					}
3325					zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &new_val);
3326				}
3327			} ZEND_HASH_FOREACH_END();
3328		} else {
3329			ZEND_HASH_FOREACH_KEY_VAL_IND(Z_ARRVAL_P(input), num_idx, str_idx, entry) {
3330				if (fast_equal_check_function(search_value, entry)) {
3331					if (str_idx) {
3332						ZVAL_STR_COPY(&new_val, str_idx);
3333					} else {
3334						ZVAL_LONG(&new_val, num_idx);
3335					}
3336					zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &new_val);
3337				}
3338			} ZEND_HASH_FOREACH_END();
3339		}
3340	} else {
3341		array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(input)));
3342		if (!zend_hash_num_elements(Z_ARRVAL_P(input))) {
3343			return;
3344		}
3345		zend_hash_real_init(Z_ARRVAL_P(return_value), 1);
3346		ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(return_value)) {
3347			/* Go through input array and add keys to the return array */
3348			ZEND_HASH_FOREACH_KEY_VAL_IND(Z_ARRVAL_P(input), num_idx, str_idx, entry) {
3349				if (str_idx) {
3350					ZVAL_STR_COPY(&new_val, str_idx);
3351				} else {
3352					ZVAL_LONG(&new_val, num_idx);
3353				}
3354				ZEND_HASH_FILL_ADD(&new_val);
3355			} ZEND_HASH_FOREACH_END();
3356		} ZEND_HASH_FILL_END();
3357	}
3358}
3359/* }}} */
3360
3361/* {{{ proto array array_values(array input)
3362   Return just the values from the input array */
3363PHP_FUNCTION(array_values)
3364{
3365	zval	 *input,		/* Input array */
3366			 *entry;		/* An entry in the input array */
3367
3368#ifndef FAST_ZPP
3369	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a", &input) == FAILURE) {
3370		return;
3371	}
3372#else
3373	ZEND_PARSE_PARAMETERS_START(1, 1)
3374		Z_PARAM_ARRAY(input)
3375	ZEND_PARSE_PARAMETERS_END();
3376#endif
3377
3378	/* Initialize return array */
3379	array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(input)));
3380
3381	if (!zend_hash_num_elements(Z_ARRVAL_P(input))) {
3382		return;
3383	}
3384
3385	zend_hash_real_init(Z_ARRVAL_P(return_value), 1);
3386
3387	/* Go through input array and add values to the return array */
3388	ZEND_HASH_FILL_PACKED(Z_ARRVAL_P(return_value)) {
3389		ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(input), entry) {
3390			if (UNEXPECTED(Z_ISREF_P(entry) && Z_REFCOUNT_P(entry) == 1)) {
3391				entry = Z_REFVAL_P(entry);
3392			}
3393			Z_TRY_ADDREF_P(entry);
3394			ZEND_HASH_FILL_ADD(entry);
3395		} ZEND_HASH_FOREACH_END();
3396	} ZEND_HASH_FILL_END();
3397}
3398/* }}} */
3399
3400/* {{{ proto array array_count_values(array input)
3401   Return the value as key and the frequency of that value in input as value */
3402PHP_FUNCTION(array_count_values)
3403{
3404	zval	*input,		/* Input array */
3405			*entry,		/* An entry in the input array */
3406			*tmp;
3407	HashTable *myht;
3408
3409	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a", &input) == FAILURE) {
3410		return;
3411	}
3412
3413	/* Initialize return array */
3414	array_init(return_value);
3415
3416	/* Go through input array and add values to the return array */
3417	myht = Z_ARRVAL_P(input);
3418	ZEND_HASH_FOREACH_VAL(myht, entry) {
3419		ZVAL_DEREF(entry);
3420		if (Z_TYPE_P(entry) == IS_LONG) {
3421			if ((tmp = zend_hash_index_find(Z_ARRVAL_P(return_value), Z_LVAL_P(entry))) == NULL) {
3422				zval data;
3423				ZVAL_LONG(&data, 1);
3424				zend_hash_index_update(Z_ARRVAL_P(return_value), Z_LVAL_P(entry), &data);
3425			} else {
3426				Z_LVAL_P(tmp)++;
3427			}
3428		} else if (Z_TYPE_P(entry) == IS_STRING) {
3429			if ((tmp = zend_symtable_find(Z_ARRVAL_P(return_value), Z_STR_P(entry))) == NULL) {
3430				zval data;
3431				ZVAL_LONG(&data, 1);
3432				zend_symtable_update(Z_ARRVAL_P(return_value), Z_STR_P(entry), &data);
3433			} else {
3434				Z_LVAL_P(tmp)++;
3435			}
3436		} else {
3437			php_error_docref(NULL, E_WARNING, "Can only count STRING and INTEGER values!");
3438		}
3439	} ZEND_HASH_FOREACH_END();
3440}
3441/* }}} */
3442
3443/* {{{ array_column_param_helper
3444 * Specialized conversion rules for array_column() function
3445 */
3446static inline
3447zend_bool array_column_param_helper(zval *param,
3448                                    const char *name) {
3449	switch (Z_TYPE_P(param)) {
3450		case IS_DOUBLE:
3451			convert_to_long_ex(param);
3452			/* fallthrough */
3453		case IS_LONG:
3454			return 1;
3455
3456		case IS_OBJECT:
3457			convert_to_string_ex(param);
3458			/* fallthrough */
3459		case IS_STRING:
3460			return 1;
3461
3462		default:
3463			php_error_docref(NULL, E_WARNING, "The %s key should be either a string or an integer", name);
3464			return 0;
3465	}
3466}
3467/* }}} */
3468
3469static inline zval *array_column_fetch_prop(zval *data, zval *name, zval *rv)
3470{
3471	zval *prop = NULL;
3472
3473	if (Z_TYPE_P(data) == IS_OBJECT) {
3474		zend_string *key = zval_get_string(name);
3475
3476		if (!Z_OBJ_HANDLER_P(data, has_property) || Z_OBJ_HANDLER_P(data, has_property)(data, name, 1, NULL)) {
3477			prop = zend_read_property(Z_OBJCE_P(data), data, ZSTR_VAL(key), ZSTR_LEN(key), 1, rv);
3478		}
3479		zend_string_release(key);
3480	} else if (Z_TYPE_P(data) == IS_ARRAY) {
3481		if (Z_TYPE_P(name) == IS_STRING) {
3482			prop = zend_hash_find(Z_ARRVAL_P(data), Z_STR_P(name));
3483		} else if (Z_TYPE_P(name) == IS_LONG) {
3484			prop = zend_hash_index_find(Z_ARRVAL_P(data), Z_LVAL_P(name));
3485		}
3486	}
3487
3488	return prop;
3489}
3490
3491/* {{{ proto array array_column(array input, mixed column_key[, mixed index_key])
3492   Return the values from a single column in the input array, identified by the
3493   value_key and optionally indexed by the index_key */
3494PHP_FUNCTION(array_column)
3495{
3496	zval *zcolumn = NULL, *zkey = NULL, *data;
3497	HashTable *arr_hash;
3498	zval *zcolval = NULL, *zkeyval = NULL, rvc, rvk;
3499
3500	if (zend_parse_parameters(ZEND_NUM_ARGS(), "hz!|z!", &arr_hash, &zcolumn, &zkey) == FAILURE) {
3501		return;
3502	}
3503
3504	if ((zcolumn && !array_column_param_helper(zcolumn, "column")) ||
3505	    (zkey && !array_column_param_helper(zkey, "index"))) {
3506		RETURN_FALSE;
3507	}
3508
3509	array_init(return_value);
3510	ZEND_HASH_FOREACH_VAL(arr_hash, data) {
3511		ZVAL_DEREF(data);
3512
3513		if (!zcolumn) {
3514			zcolval = data;
3515		} else if ((zcolval = array_column_fetch_prop(data, zcolumn, &rvc)) == NULL) {
3516			continue;
3517		}
3518
3519		/* Failure will leave zkeyval alone which will land us on the final else block below
3520		 * which is to append the value as next_index
3521		 */
3522		if (zkey) {
3523			zkeyval = array_column_fetch_prop(data, zkey, &rvk);
3524		}
3525
3526		Z_TRY_ADDREF_P(zcolval);
3527		if (zkeyval && Z_TYPE_P(zkeyval) == IS_STRING) {
3528			zend_symtable_update(Z_ARRVAL_P(return_value), Z_STR_P(zkeyval), zcolval);
3529		} else if (zkeyval && Z_TYPE_P(zkeyval) == IS_LONG) {
3530			add_index_zval(return_value, Z_LVAL_P(zkeyval), zcolval);
3531		} else if (zkeyval && Z_TYPE_P(zkeyval) == IS_OBJECT) {
3532			zend_string *key = zval_get_string(zkeyval);
3533			zend_symtable_update(Z_ARRVAL_P(return_value), key, zcolval);
3534			zend_string_release(key);
3535		} else {
3536			add_next_index_zval(return_value, zcolval);
3537		}
3538		if (zcolval == &rvc) {
3539			zval_ptr_dtor(&rvc);
3540		}
3541		if (zkeyval == &rvk) {
3542			zval_ptr_dtor(&rvk);
3543		}
3544	} ZEND_HASH_FOREACH_END();
3545}
3546/* }}} */
3547
3548/* {{{ proto array array_reverse(array input [, bool preserve keys])
3549   Return input as a new array with the order of the entries reversed */
3550PHP_FUNCTION(array_reverse)
3551{
3552	zval	 *input,				/* Input array */
3553			 *entry;				/* An entry in the input array */
3554	zend_string *string_key;
3555	zend_ulong	  num_key;
3556	zend_bool preserve_keys = 0;	/* whether to preserve keys */
3557
3558	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a|b", &input, &preserve_keys) == FAILURE) {
3559		return;
3560	}
3561
3562	/* Initialize return array */
3563	array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(input)));
3564
3565	ZEND_HASH_REVERSE_FOREACH_KEY_VAL(Z_ARRVAL_P(input), num_key, string_key, entry) {
3566		if (string_key) {
3567			entry = zend_hash_add_new(Z_ARRVAL_P(return_value), string_key, entry);
3568		} else {
3569			if (preserve_keys) {
3570				entry = zend_hash_index_add_new(Z_ARRVAL_P(return_value), num_key, entry);
3571			} else {
3572				entry = zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), entry);
3573			}
3574		}
3575
3576		zval_add_ref(entry);
3577	} ZEND_HASH_FOREACH_END();
3578}
3579/* }}} */
3580
3581/* {{{ proto array array_pad(array input, int pad_size, mixed pad_value)
3582   Returns a copy of input array padded with pad_value to size pad_size */
3583PHP_FUNCTION(array_pad)
3584{
3585	zval  *input;		/* Input array */
3586	zval  *pad_value;	/* Padding value obviously */
3587	zend_long pad_size;		/* Size to pad to */
3588	zend_long pad_size_abs;	/* Absolute value of pad_size */
3589	zend_long input_size;		/* Size of the input array */
3590	zend_long num_pads;		/* How many pads do we need */
3591	zend_long i;
3592	zend_string *key;
3593	zval *value;
3594
3595	if (zend_parse_parameters(ZEND_NUM_ARGS(), "alz", &input, &pad_size, &pad_value) == FAILURE) {
3596		return;
3597	}
3598
3599	/* Do some initial calculations */
3600	input_size = zend_hash_num_elements(Z_ARRVAL_P(input));
3601	pad_size_abs = ZEND_ABS(pad_size);
3602	if (pad_size_abs < 0 || pad_size_abs - input_size > Z_L(1048576)) {
3603		php_error_docref(NULL, E_WARNING, "You may only pad up to 1048576 elements at a time");
3604		RETURN_FALSE;
3605	}
3606
3607	if (input_size >= pad_size_abs) {
3608		/* Copy the original array */
3609		ZVAL_COPY(return_value, input);
3610		return;
3611	}
3612
3613	num_pads = pad_size_abs - input_size;
3614	array_init_size(return_value, pad_size_abs);
3615	if (Z_REFCOUNTED_P(pad_value)) {
3616		GC_REFCOUNT(Z_COUNTED_P(pad_value)) += num_pads;
3617	}
3618
3619	if (pad_size < 0) {
3620		for (i = 0; i < num_pads; i++) {
3621			zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), pad_value);
3622		}
3623	}
3624
3625	ZEND_HASH_FOREACH_STR_KEY_VAL_IND(Z_ARRVAL_P(input), key, value) {
3626		if (Z_REFCOUNTED_P(value)) {
3627			Z_ADDREF_P(value);
3628		}
3629		if (key) {
3630			zend_hash_add_new(Z_ARRVAL_P(return_value), key, value);
3631		} else {
3632			zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), value);
3633		}
3634	} ZEND_HASH_FOREACH_END();
3635
3636	if (pad_size > 0) {
3637		for (i = 0; i < num_pads; i++) {
3638			zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), pad_value);
3639		}
3640	}
3641}
3642/* }}} */
3643
3644/* {{{ proto array array_flip(array input)
3645   Return array with key <-> value flipped */
3646PHP_FUNCTION(array_flip)
3647{
3648	zval *array, *entry, data;
3649	zend_ulong num_idx;
3650	zend_string *str_idx;
3651
3652	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a", &array) == FAILURE) {
3653		return;
3654	}
3655
3656	array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(array)));
3657
3658	ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {
3659		ZVAL_DEREF(entry);
3660		if (Z_TYPE_P(entry) == IS_LONG) {
3661			if (str_idx) {
3662				ZVAL_STR_COPY(&data, str_idx);
3663			} else {
3664				ZVAL_LONG(&data, num_idx);
3665			}
3666			zend_hash_index_update(Z_ARRVAL_P(return_value), Z_LVAL_P(entry), &data);
3667		} else if (Z_TYPE_P(entry) == IS_STRING) {
3668			if (str_idx) {
3669				ZVAL_STR_COPY(&data, str_idx);
3670			} else {
3671				ZVAL_LONG(&data, num_idx);
3672			}
3673			zend_symtable_update(Z_ARRVAL_P(return_value), Z_STR_P(entry), &data);
3674		} else {
3675			php_error_docref(NULL, E_WARNING, "Can only flip STRING and INTEGER values!");
3676		}
3677	} ZEND_HASH_FOREACH_END();
3678}
3679/* }}} */
3680
3681/* {{{ proto array array_change_key_case(array input [, int case=CASE_LOWER])
3682   Retuns an array with all string keys lowercased [or uppercased] */
3683PHP_FUNCTION(array_change_key_case)
3684{
3685	zval *array, *entry;
3686	zend_string *string_key;
3687	zend_string *new_key;
3688	zend_ulong num_key;
3689	zend_long change_to_upper=0;
3690
3691	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a|l", &array, &change_to_upper) == FAILURE) {
3692		return;
3693	}
3694
3695	array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(array)));
3696
3697	ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_key, string_key, entry) {
3698		if (!string_key) {
3699			entry = zend_hash_index_update(Z_ARRVAL_P(return_value), num_key, entry);
3700		} else {
3701			if (change_to_upper) {
3702				new_key = php_string_toupper(string_key);
3703			} else {
3704				new_key = php_string_tolower(string_key);
3705			}
3706			entry = zend_hash_update(Z_ARRVAL_P(return_value), new_key, entry);
3707			zend_string_release(new_key);
3708		}
3709
3710		zval_add_ref(entry);
3711	} ZEND_HASH_FOREACH_END();
3712}
3713/* }}} */
3714
3715struct bucketindex {
3716	Bucket b;
3717	unsigned int i;
3718};
3719
3720static void array_bucketindex_swap(void *p, void *q) /* {{{ */
3721{
3722	struct bucketindex *f = (struct bucketindex *)p;
3723	struct bucketindex *g = (struct bucketindex *)q;
3724	struct bucketindex t;
3725	t = *f;
3726	*f = *g;
3727	*g = t;
3728}
3729/* }}} */
3730
3731/* {{{ proto array array_unique(array input [, int sort_flags])
3732   Removes duplicate values from array */
3733PHP_FUNCTION(array_unique)
3734{
3735	zval *array;
3736	uint idx;
3737	Bucket *p;
3738	struct bucketindex *arTmp, *cmpdata, *lastkept;
3739	unsigned int i;
3740	zend_long sort_type = PHP_SORT_STRING;
3741	compare_func_t cmp;
3742
3743	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a|l", &array, &sort_type) == FAILURE) {
3744		return;
3745	}
3746
3747	cmp = php_get_data_compare_func(sort_type, 0);
3748
3749
3750	if (Z_ARRVAL_P(array)->nNumOfElements <= 1) {	/* nothing to do */
3751		ZVAL_COPY(return_value, array);
3752		return;
3753	}
3754
3755	RETVAL_ARR(zend_array_dup(Z_ARRVAL_P(array)));
3756
3757	/* create and sort array with pointers to the target_hash buckets */
3758	arTmp = (struct bucketindex *) pemalloc((Z_ARRVAL_P(array)->nNumOfElements + 1) * sizeof(struct bucketindex), Z_ARRVAL_P(array)->u.flags & HASH_FLAG_PERSISTENT);
3759	if (!arTmp) {
3760		zval_dtor(return_value);
3761		RETURN_FALSE;
3762	}
3763	for (i = 0, idx = 0; idx < Z_ARRVAL_P(array)->nNumUsed; idx++) {
3764		p = Z_ARRVAL_P(array)->arData + idx;
3765		if (Z_TYPE(p->val) == IS_UNDEF) continue;
3766		if (Z_TYPE(p->val) == IS_INDIRECT && Z_TYPE_P(Z_INDIRECT(p->val)) == IS_UNDEF) continue;
3767		arTmp[i].b = *p;
3768		arTmp[i].i = i;
3769		i++;
3770	}
3771	ZVAL_UNDEF(&arTmp[i].b.val);
3772	zend_sort((void *) arTmp, i, sizeof(struct bucketindex),
3773			cmp, (swap_func_t)array_bucketindex_swap);
3774	/* go through the sorted array and delete duplicates from the copy */
3775	lastkept = arTmp;
3776	for (cmpdata = arTmp + 1; Z_TYPE(cmpdata->b.val) != IS_UNDEF; cmpdata++) {
3777		if (cmp(lastkept, cmpdata)) {
3778			lastkept = cmpdata;
3779		} else {
3780			if (lastkept->i > cmpdata->i) {
3781				p = &lastkept->b;
3782				lastkept = cmpdata;
3783			} else {
3784				p = &cmpdata->b;
3785			}
3786			if (p->key == NULL) {
3787				zend_hash_index_del(Z_ARRVAL_P(return_value), p->h);
3788			} else {
3789				if (Z_ARRVAL_P(return_value) == &EG(symbol_table)) {
3790					zend_delete_global_variable(p->key);
3791				} else {
3792					zend_hash_del(Z_ARRVAL_P(return_value), p->key);
3793				}
3794			}
3795		}
3796	}
3797	pefree(arTmp, Z_ARRVAL_P(array)->u.flags & HASH_FLAG_PERSISTENT);
3798}
3799/* }}} */
3800
3801static int zval_compare(zval *first, zval *second) /* {{{ */
3802{
3803	return string_compare_function(first, second);
3804}
3805/* }}} */
3806
3807static int zval_user_compare(zval *a, zval *b) /* {{{ */
3808{
3809	zval args[2];
3810	zval retval;
3811
3812	ZVAL_COPY_VALUE(&args[0], a);
3813	ZVAL_COPY_VALUE(&args[1], b);
3814
3815	BG(user_compare_fci).param_count = 2;
3816	BG(user_compare_fci).params = args;
3817	BG(user_compare_fci).retval = &retval;
3818	BG(user_compare_fci).no_separation = 0;
3819
3820	if (zend_call_function(&BG(user_compare_fci), &BG(user_compare_fci_cache)) == SUCCESS && Z_TYPE(retval) != IS_UNDEF) {
3821		zend_long ret = zval_get_long(&retval);
3822		zval_ptr_dtor(&retval);
3823		return ret < 0 ? -1 : ret > 0 ? 1 : 0;;
3824	} else {
3825		return 0;
3826	}
3827}
3828/* }}} */
3829
3830static void php_array_intersect_key(INTERNAL_FUNCTION_PARAMETERS, int data_compare_type) /* {{{ */
3831{
3832    uint idx;
3833	Bucket *p;
3834	int argc, i;
3835	zval *args;
3836	int (*intersect_data_compare_func)(zval *, zval *) = NULL;
3837	zend_bool ok;
3838	zval *val, *data;
3839	int req_args;
3840	char *param_spec;
3841
3842	/* Get the argument count */
3843	argc = ZEND_NUM_ARGS();
3844	if (data_compare_type == INTERSECT_COMP_DATA_USER) {
3845		/* INTERSECT_COMP_DATA_USER - array_uintersect_assoc() */
3846		req_args = 3;
3847		param_spec = "+f";
3848		intersect_data_compare_func = zval_user_compare;
3849	} else {
3850		/* 	INTERSECT_COMP_DATA_NONE - array_intersect_key()
3851			INTERSECT_COMP_DATA_INTERNAL - array_intersect_assoc() */
3852		req_args = 2;
3853		param_spec = "+";
3854
3855		if (data_compare_type == INTERSECT_COMP_DATA_INTERNAL) {
3856			intersect_data_compare_func = zval_compare;
3857		}
3858	}
3859
3860	if (argc < req_args) {
3861		php_error_docref(NULL, E_WARNING, "at least %d parameters are required, %d given", req_args, argc);
3862		return;
3863	}
3864
3865	if (zend_parse_parameters(ZEND_NUM_ARGS(), param_spec, &args, &argc, &BG(user_compare_fci), &BG(user_compare_fci_cache)) == FAILURE) {
3866		return;
3867	}
3868
3869	for (i = 0; i < argc; i++) {
3870		if (Z_TYPE(args[i]) != IS_ARRAY) {
3871			php_error_docref(NULL, E_WARNING, "Argument #%d is not an array", i + 1);
3872			RETURN_NULL();
3873		}
3874	}
3875
3876	array_init(return_value);
3877
3878	for (idx = 0; idx < Z_ARRVAL(args[0])->nNumUsed; idx++) {
3879		p = Z_ARRVAL(args[0])->arData + idx;
3880		val = &p->val;
3881		if (Z_TYPE_P(val) == IS_UNDEF) continue;
3882		if (UNEXPECTED(Z_TYPE_P(val) == IS_INDIRECT)) {
3883			val = Z_INDIRECT_P(val);
3884			if (Z_TYPE_P(val) == IS_UNDEF) continue;
3885		}
3886		if (Z_ISREF_P(val) && Z_REFCOUNT_P(val) == 1) {
3887			ZVAL_UNREF(val);
3888		}
3889		if (p->key == NULL) {
3890			ok = 1;
3891			for (i = 1; i < argc; i++) {
3892				if ((data = zend_hash_index_find(Z_ARRVAL(args[i]), p->h)) == NULL ||
3893					(intersect_data_compare_func &&
3894					intersect_data_compare_func(val, data) != 0)
3895				) {
3896					ok = 0;
3897					break;
3898				}
3899			}
3900			if (ok) {
3901				if (Z_REFCOUNTED_P(val)) {
3902					Z_ADDREF_P(val);
3903				}
3904				zend_hash_index_update(Z_ARRVAL_P(return_value), p->h, val);
3905			}
3906		} else {
3907			ok = 1;
3908			for (i = 1; i < argc; i++) {
3909				if ((data = zend_hash_find_ind(Z_ARRVAL(args[i]), p->key)) == NULL ||
3910					(intersect_data_compare_func &&
3911					intersect_data_compare_func(val, data) != 0)
3912				) {
3913					ok = 0;
3914					break;
3915				}
3916			}
3917			if (ok) {
3918				if (Z_REFCOUNTED_P(val)) {
3919					Z_ADDREF_P(val);
3920				}
3921				zend_hash_update(Z_ARRVAL_P(return_value), p->key, val);
3922			}
3923		}
3924	}
3925}
3926/* }}} */
3927
3928static void php_array_intersect(INTERNAL_FUNCTION_PARAMETERS, int behavior, int data_compare_type, int key_compare_type) /* {{{ */
3929{
3930	zval *args = NULL;
3931	HashTable *hash;
3932	int arr_argc, i, c = 0;
3933	uint idx;
3934	Bucket **lists, *list, **ptrs, *p;
3935	uint32_t req_args;
3936	char *param_spec;
3937	zend_fcall_info fci1, fci2;
3938	zend_fcall_info_cache fci1_cache = empty_fcall_info_cache, fci2_cache = empty_fcall_info_cache;
3939	zend_fcall_info *fci_key = NULL, *fci_data;
3940	zend_fcall_info_cache *fci_key_cache = NULL, *fci_data_cache;
3941	PHP_ARRAY_CMP_FUNC_VARS;
3942
3943	int (*intersect_key_compare_func)(const void *, const void *);
3944	int (*intersect_data_compare_func)(const void *, const void *);
3945
3946	if (behavior == INTERSECT_NORMAL) {
3947		intersect_key_compare_func = php_array_key_compare_string;
3948
3949		if (data_compare_type == INTERSECT_COMP_DATA_INTERNAL) {
3950			/* array_intersect() */
3951			req_args = 2;
3952			param_spec = "+";
3953			intersect_data_compare_func = php_array_data_compare_string;
3954		} else if (data_compare_type == INTERSECT_COMP_DATA_USER) {
3955			/* array_uintersect() */
3956			req_args = 3;
3957			param_spec = "+f";
3958			intersect_data_compare_func = php_array_user_compare;
3959		} else {
3960			php_error_docref(NULL, E_WARNING, "data_compare_type is %d. This should never happen. Please report as a bug", data_compare_type);
3961			return;
3962		}
3963
3964		if (ZEND_NUM_ARGS() < req_args) {
3965			php_error_docref(NULL, E_WARNING, "at least %d parameters are required, %d given", req_args, ZEND_NUM_ARGS());
3966			return;
3967		}
3968
3969		if (zend_parse_parameters(ZEND_NUM_ARGS(), param_spec, &args, &arr_argc, &fci1, &fci1_cache) == FAILURE) {
3970			return;
3971		}
3972		fci_data = &fci1;
3973		fci_data_cache = &fci1_cache;
3974
3975	} else if (behavior & INTERSECT_ASSOC) { /* triggered also when INTERSECT_KEY */
3976		/* INTERSECT_KEY is subset of INTERSECT_ASSOC. When having the former
3977		 * no comparison of the data is done (part of INTERSECT_ASSOC) */
3978		intersect_key_compare_func = php_array_key_compare_string;
3979
3980		if (data_compare_type == INTERSECT_COMP_DATA_INTERNAL && key_compare_type == INTERSECT_COMP_KEY_INTERNAL) {
3981			/* array_intersect_assoc() or array_intersect_key() */
3982			req_args = 2;
3983			param_spec = "+";
3984			intersect_key_compare_func = php_array_key_compare_string;
3985			intersect_data_compare_func = php_array_data_compare_string;
3986		} else if (data_compare_type == INTERSECT_COMP_DATA_USER && key_compare_type == INTERSECT_COMP_KEY_INTERNAL) {
3987			/* array_uintersect_assoc() */
3988			req_args = 3;
3989			param_spec = "+f";
3990			intersect_key_compare_func = php_array_key_compare_string;
3991			intersect_data_compare_func = php_array_user_compare;
3992			fci_data = &fci1;
3993			fci_data_cache = &fci1_cache;
3994		} else if (data_compare_type == INTERSECT_COMP_DATA_INTERNAL && key_compare_type == INTERSECT_COMP_KEY_USER) {
3995			/* array_intersect_uassoc() or array_intersect_ukey() */
3996			req_args = 3;
3997			param_spec = "+f";
3998			intersect_key_compare_func = php_array_user_key_compare;
3999			intersect_data_compare_func = php_array_data_compare_string;
4000			fci_key = &fci1;
4001			fci_key_cache = &fci1_cache;
4002		} else if (data_compare_type == INTERSECT_COMP_DATA_USER && key_compare_type == INTERSECT_COMP_KEY_USER) {
4003			/* array_uintersect_uassoc() */
4004			req_args = 4;
4005			param_spec = "+ff";
4006			intersect_key_compare_func = php_array_user_key_compare;
4007			intersect_data_compare_func = php_array_user_compare;
4008			fci_data = &fci1;
4009			fci_data_cache = &fci1_cache;
4010			fci_key = &fci2;
4011			fci_key_cache = &fci2_cache;
4012		} else {
4013			php_error_docref(NULL, E_WARNING, "data_compare_type is %d. key_compare_type is %d. This should never happen. Please report as a bug", data_compare_type, key_compare_type);
4014			return;
4015		}
4016
4017		if (ZEND_NUM_ARGS() < req_args) {
4018			php_error_docref(NULL, E_WARNING, "at least %d parameters are required, %d given", req_args, ZEND_NUM_ARGS());
4019			return;
4020		}
4021
4022		if (zend_parse_parameters(ZEND_NUM_ARGS(), param_spec, &args, &arr_argc, &fci1, &fci1_cache, &fci2, &fci2_cache) == FAILURE) {
4023			return;
4024		}
4025
4026	} else {
4027		php_error_docref(NULL, E_WARNING, "behavior is %d. This should never happen. Please report as a bug", behavior);
4028		return;
4029	}
4030
4031	PHP_ARRAY_CMP_FUNC_BACKUP();
4032
4033	/* for each argument, create and sort list with pointers to the hash buckets */
4034	lists = (Bucket **)safe_emalloc(arr_argc, sizeof(Bucket *), 0);
4035	ptrs = (Bucket **)safe_emalloc(arr_argc, sizeof(Bucket *), 0);
4036
4037	if (behavior == INTERSECT_NORMAL && data_compare_type == INTERSECT_COMP_DATA_USER) {
4038		BG(user_compare_fci) = *fci_data;
4039		BG(user_compare_fci_cache) = *fci_data_cache;
4040	} else if (behavior & INTERSECT_ASSOC && key_compare_type == INTERSECT_COMP_KEY_USER) {
4041		BG(user_compare_fci) = *fci_key;
4042		BG(user_compare_fci_cache) = *fci_key_cache;
4043	}
4044
4045	for (i = 0; i < arr_argc; i++) {
4046		if (Z_TYPE(args[i]) != IS_ARRAY) {
4047			php_error_docref(NULL, E_WARNING, "Argument #%d is not an array", i + 1);
4048			arr_argc = i; /* only free up to i - 1 */
4049			goto out;
4050		}
4051		hash = Z_ARRVAL(args[i]);
4052		list = (Bucket *) pemalloc((hash->nNumOfElements + 1) * sizeof(Bucket), hash->u.flags & HASH_FLAG_PERSISTENT);
4053		if (!list) {
4054			PHP_ARRAY_CMP_FUNC_RESTORE();
4055
4056			efree(ptrs);
4057			efree(lists);
4058			RETURN_FALSE;
4059		}
4060		lists[i] = list;
4061		ptrs[i] = list;
4062		for (idx = 0; idx < hash->nNumUsed; idx++) {
4063			p = hash->arData + idx;
4064			if (Z_TYPE(p->val) == IS_UNDEF) continue;
4065			*list++ = *p;
4066		}
4067		ZVAL_UNDEF(&list->val);
4068		if (hash->nNumOfElements > 1) {
4069			if (behavior == INTERSECT_NORMAL) {
4070				zend_sort((void *) lists[i], hash->nNumOfElements,
4071						sizeof(Bucket), intersect_data_compare_func, (swap_func_t)zend_hash_bucket_swap);
4072			} else if (behavior & INTERSECT_ASSOC) { /* triggered also when INTERSECT_KEY */
4073				zend_sort((void *) lists[i], hash->nNumOfElements,
4074						sizeof(Bucket), intersect_key_compare_func, (swap_func_t)zend_hash_bucket_swap);
4075			}
4076		}
4077	}
4078
4079	/* copy the argument array */
4080	RETVAL_ARR(zend_array_dup(Z_ARRVAL(args[0])));
4081
4082	/* go through the lists and look for common values */
4083	while (Z_TYPE(ptrs[0]->val) != IS_UNDEF) {
4084		if ((behavior & INTERSECT_ASSOC) /* triggered also when INTERSECT_KEY */
4085			&& key_compare_type == INTERSECT_COMP_KEY_USER) {
4086			BG(user_compare_fci) = *fci_key;
4087			BG(user_compare_fci_cache) = *fci_key_cache;
4088		}
4089
4090		for (i = 1; i < arr_argc; i++) {
4091			if (behavior & INTERSECT_NORMAL) {
4092				while (Z_TYPE(ptrs[i]->val) != IS_UNDEF && (0 < (c = intersect_data_compare_func(ptrs[0], ptrs[i])))) {
4093					ptrs[i]++;
4094				}
4095			} else if (behavior & INTERSECT_ASSOC) { /* triggered also when INTERSECT_KEY */
4096				while (Z_TYPE(ptrs[i]->val) != IS_UNDEF && (0 < (c = intersect_key_compare_func(ptrs[0], ptrs[i])))) {
4097					ptrs[i]++;
4098				}
4099				if ((!c && Z_TYPE(ptrs[i]->val) != IS_UNDEF) && (behavior == INTERSECT_ASSOC)) { /* only when INTERSECT_ASSOC */
4100					/* this means that ptrs[i] is not NULL so we can compare
4101					 * and "c==0" is from last operation
4102					 * in this branch of code we enter only when INTERSECT_ASSOC
4103					 * since when we have INTERSECT_KEY compare of data is not wanted. */
4104					if (data_compare_type == INTERSECT_COMP_DATA_USER) {
4105						BG(user_compare_fci) = *fci_data;
4106						BG(user_compare_fci_cache) = *fci_data_cache;
4107					}
4108					if (intersect_data_compare_func(ptrs[0], ptrs[i]) != 0) {
4109						c = 1;
4110						if (key_compare_type == INTERSECT_COMP_KEY_USER) {
4111							BG(user_compare_fci) = *fci_key;
4112							BG(user_compare_fci_cache) = *fci_key_cache;
4113							/* When KEY_USER, the last parameter is always the callback */
4114						}
4115						/* we are going to the break */
4116					} else {
4117						/* continue looping */
4118					}
4119				}
4120			}
4121			if (Z_TYPE(ptrs[i]->val) == IS_UNDEF) {
4122				/* delete any values corresponding to remains of ptrs[0] */
4123				/* and exit because they do not present in at least one of */
4124				/* the other arguments */
4125				for (;;) {
4126					p = ptrs[0]++;
4127					if (Z_TYPE(p->val) == IS_UNDEF) {
4128						goto out;
4129					}
4130					if (p->key == NULL) {
4131						zend_hash_index_del(Z_ARRVAL_P(return_value), p->h);
4132					} else {
4133						zend_hash_del(Z_ARRVAL_P(return_value), p->key);
4134					}
4135				}
4136			}
4137			if (c) /* here we get if not all are equal */
4138				break;
4139			ptrs[i]++;
4140		}
4141		if (c) {
4142			/* Value of ptrs[0] not in all arguments, delete all entries */
4143			/* with value < value of ptrs[i] */
4144			for (;;) {
4145				p = ptrs[0];
4146				if (p->key == NULL) {
4147					zend_hash_index_del(Z_ARRVAL_P(return_value), p->h);
4148				} else {
4149					zend_hash_del(Z_ARRVAL_P(return_value), p->key);
4150				}
4151				if (Z_TYPE((++ptrs[0])->val) == IS_UNDEF) {
4152					goto out;
4153				}
4154				if (behavior == INTERSECT_NORMAL) {
4155					if (0 <= intersect_data_compare_func(ptrs[0], ptrs[i])) {
4156						break;
4157					}
4158				} else if (behavior & INTERSECT_ASSOC) { /* triggered also when INTERSECT_KEY */
4159					/* no need of looping because indexes are unique */
4160					break;
4161				}
4162			}
4163		} else {
4164			/* ptrs[0] is present in all the arguments */
4165			/* Skip all entries with same value as ptrs[0] */
4166			for (;;) {
4167				if (Z_TYPE((++ptrs[0])->val) == IS_UNDEF) {
4168					goto out;
4169				}
4170				if (behavior == INTERSECT_NORMAL) {
4171					if (intersect_data_compare_func(ptrs[0] - 1, ptrs[0])) {
4172						break;
4173					}
4174				} else if (behavior & INTERSECT_ASSOC) { /* triggered also when INTERSECT_KEY */
4175					/* no need of looping because indexes are unique */
4176					break;
4177				}
4178			}
4179		}
4180	}
4181out:
4182	for (i = 0; i < arr_argc; i++) {
4183		hash = Z_ARRVAL(args[i]);
4184		pefree(lists[i], hash->u.flags & HASH_FLAG_PERSISTENT);
4185	}
4186
4187	PHP_ARRAY_CMP_FUNC_RESTORE();
4188
4189	efree(ptrs);
4190	efree(lists);
4191}
4192/* }}} */
4193
4194/* {{{ proto array array_intersect_key(array arr1, array arr2 [, array ...])
4195   Returns the entries of arr1 that have keys which are present in all the other arguments. Kind of equivalent to array_diff(array_keys($arr1), array_keys($arr2)[,array_keys(...)]). Equivalent of array_intersect_assoc() but does not do compare of the data. */
4196PHP_FUNCTION(array_intersect_key)
4197{
4198	php_array_intersect_key(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_COMP_DATA_NONE);
4199}
4200/* }}} */
4201
4202/* {{{ proto array array_intersect_ukey(array arr1, array arr2 [, array ...], callback key_compare_func)
4203   Returns the entries of arr1 that have keys which are present in all the other arguments. Kind of equivalent to array_diff(array_keys($arr1), array_keys($arr2)[,array_keys(...)]). The comparison of the keys is performed by a user supplied function. Equivalent of array_intersect_uassoc() but does not do compare of the data. */
4204PHP_FUNCTION(array_intersect_ukey)
4205{
4206	php_array_intersect(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_KEY, INTERSECT_COMP_DATA_INTERNAL, INTERSECT_COMP_KEY_USER);
4207}
4208/* }}} */
4209
4210/* {{{ proto array array_intersect(array arr1, array arr2 [, array ...])
4211   Returns the entries of arr1 that have values which are present in all the other arguments */
4212PHP_FUNCTION(array_intersect)
4213{
4214	php_array_intersect(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_NORMAL, INTERSECT_COMP_DATA_INTERNAL, INTERSECT_COMP_KEY_INTERNAL);
4215}
4216/* }}} */
4217
4218/* {{{ proto array array_uintersect(array arr1, array arr2 [, array ...], callback data_compare_func)
4219   Returns the entries of arr1 that have values which are present in all the other arguments. Data is compared by using a user-supplied callback. */
4220PHP_FUNCTION(array_uintersect)
4221{
4222	php_array_intersect(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_NORMAL, INTERSECT_COMP_DATA_USER, INTERSECT_COMP_KEY_INTERNAL);
4223}
4224/* }}} */
4225
4226/* {{{ proto array array_intersect_assoc(array arr1, array arr2 [, array ...])
4227   Returns the entries of arr1 that have values which are present in all the other arguments. Keys are used to do more restrictive check */
4228PHP_FUNCTION(array_intersect_assoc)
4229{
4230	php_array_intersect_key(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_COMP_DATA_INTERNAL);
4231}
4232/* }}} */
4233
4234/* {{{ proto array array_intersect_uassoc(array arr1, array arr2 [, array ...], callback key_compare_func) U
4235   Returns the entries of arr1 that have values which are present in all the other arguments. Keys are used to do more restrictive check and they are compared by using a user-supplied callback. */
4236PHP_FUNCTION(array_intersect_uassoc)
4237{
4238	php_array_intersect(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_ASSOC, INTERSECT_COMP_DATA_INTERNAL, INTERSECT_COMP_KEY_USER);
4239}
4240/* }}} */
4241
4242/* {{{ proto array array_uintersect_assoc(array arr1, array arr2 [, array ...], callback data_compare_func) U
4243   Returns the entries of arr1 that have values which are present in all the other arguments. Keys are used to do more restrictive check. Data is compared by using a user-supplied callback. */
4244PHP_FUNCTION(array_uintersect_assoc)
4245{
4246	php_array_intersect_key(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_COMP_DATA_USER);
4247}
4248/* }}} */
4249
4250/* {{{ proto array array_uintersect_uassoc(array arr1, array arr2 [, array ...], callback data_compare_func, callback key_compare_func)
4251   Returns the entries of arr1 that have values which are present in all the other arguments. Keys are used to do more restrictive check. Both data and keys are compared by using user-supplied callbacks. */
4252PHP_FUNCTION(array_uintersect_uassoc)
4253{
4254	php_array_intersect(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_ASSOC, INTERSECT_COMP_DATA_USER, INTERSECT_COMP_KEY_USER);
4255}
4256/* }}} */
4257
4258static void php_array_diff_key(INTERNAL_FUNCTION_PARAMETERS, int data_compare_type) /* {{{ */
4259{
4260    uint idx;
4261	Bucket *p;
4262	int argc, i;
4263	zval *args;
4264	int (*diff_data_compare_func)(zval *, zval *) = NULL;
4265	zend_bool ok;
4266	zval *val, *data;
4267
4268	/* Get the argument count */
4269	argc = ZEND_NUM_ARGS();
4270	if (data_compare_type == DIFF_COMP_DATA_USER) {
4271		if (argc < 3) {
4272			php_error_docref(NULL, E_WARNING, "at least 3 parameters are required, %d given", ZEND_NUM_ARGS());
4273			return;
4274		}
4275		if (zend_parse_parameters(ZEND_NUM_ARGS(), "+f", &args, &argc, &BG(user_compare_fci), &BG(user_compare_fci_cache)) == FAILURE) {
4276			return;
4277		}
4278		diff_data_compare_func = zval_user_compare;
4279	} else {
4280		if (argc < 2) {
4281			php_error_docref(NULL, E_WARNING, "at least 2 parameters are required, %d given", ZEND_NUM_ARGS());
4282			return;
4283		}
4284		if (zend_parse_parameters(ZEND_NUM_ARGS(), "+", &args, &argc) == FAILURE) {
4285			return;
4286		}
4287		if (data_compare_type == DIFF_COMP_DATA_INTERNAL) {
4288			diff_data_compare_func = zval_compare;
4289		}
4290	}
4291
4292	for (i = 0; i < argc; i++) {
4293		if (Z_TYPE(args[i]) != IS_ARRAY) {
4294			php_error_docref(NULL, E_WARNING, "Argument #%d is not an array", i + 1);
4295			RETURN_NULL();
4296		}
4297	}
4298
4299	array_init(return_value);
4300
4301	for (idx = 0; idx < Z_ARRVAL(args[0])->nNumUsed; idx++) {
4302		p = Z_ARRVAL(args[0])->arData + idx;
4303		val = &p->val;
4304		if (Z_TYPE_P(val) == IS_UNDEF) continue;
4305		if (UNEXPECTED(Z_TYPE_P(val) == IS_INDIRECT)) {
4306			val = Z_INDIRECT_P(val);
4307			if (Z_TYPE_P(val) == IS_UNDEF) continue;
4308		}
4309		if (Z_ISREF_P(val) && Z_REFCOUNT_P(val) == 1) {
4310			ZVAL_UNREF(val);
4311		}
4312		if (p->key == NULL) {
4313			ok = 1;
4314			for (i = 1; i < argc; i++) {
4315				if ((data = zend_hash_index_find(Z_ARRVAL(args[i]), p->h)) != NULL &&
4316					(!diff_data_compare_func ||
4317					diff_data_compare_func(val, data) == 0)
4318				) {
4319					ok = 0;
4320					break;
4321				}
4322			}
4323			if (ok) {
4324				if (Z_REFCOUNTED_P(val)) {
4325					Z_ADDREF_P(val);
4326				}
4327				zend_hash_index_update(Z_ARRVAL_P(return_value), p->h, val);
4328			}
4329		} else {
4330			ok = 1;
4331			for (i = 1; i < argc; i++) {
4332				if ((data = zend_hash_find_ind(Z_ARRVAL(args[i]), p->key)) != NULL &&
4333					(!diff_data_compare_func ||
4334					diff_data_compare_func(val, data) == 0)
4335				) {
4336					ok = 0;
4337					break;
4338				}
4339			}
4340			if (ok) {
4341				if (Z_REFCOUNTED_P(val)) {
4342					Z_ADDREF_P(val);
4343				}
4344				zend_hash_update(Z_ARRVAL_P(return_value), p->key, val);
4345			}
4346		}
4347	}
4348}
4349/* }}} */
4350
4351static void php_array_diff(INTERNAL_FUNCTION_PARAMETERS, int behavior, int data_compare_type, int key_compare_type) /* {{{ */
4352{
4353	zval *args = NULL;
4354	HashTable *hash;
4355	int arr_argc, i, c;
4356	uint idx;
4357	Bucket **lists, *list, **ptrs, *p;
4358	uint32_t req_args;
4359	char *param_spec;
4360	zend_fcall_info fci1, fci2;
4361	zend_fcall_info_cache fci1_cache = empty_fcall_info_cache, fci2_cache = empty_fcall_info_cache;
4362	zend_fcall_info *fci_key = NULL, *fci_data;
4363	zend_fcall_info_cache *fci_key_cache = NULL, *fci_data_cache;
4364	PHP_ARRAY_CMP_FUNC_VARS;
4365
4366	int (*diff_key_compare_func)(const void *, const void *);
4367	int (*diff_data_compare_func)(const void *, const void *);
4368
4369	if (behavior == DIFF_NORMAL) {
4370		diff_key_compare_func = php_array_key_compare_string;
4371
4372		if (data_compare_type == DIFF_COMP_DATA_INTERNAL) {
4373			/* array_diff */
4374			req_args = 2;
4375			param_spec = "+";
4376			diff_data_compare_func = php_array_data_compare_string;
4377		} else if (data_compare_type == DIFF_COMP_DATA_USER) {
4378			/* array_udiff */
4379			req_args = 3;
4380			param_spec = "+f";
4381			diff_data_compare_func = php_array_user_compare;
4382		} else {
4383			php_error_docref(NULL, E_WARNING, "data_compare_type is %d. This should never happen. Please report as a bug", data_compare_type);
4384			return;
4385		}
4386
4387		if (ZEND_NUM_ARGS() < req_args) {
4388			php_error_docref(NULL, E_WARNING, "at least %d parameters are required, %d given", req_args, ZEND_NUM_ARGS());
4389			return;
4390		}
4391
4392		if (zend_parse_parameters(ZEND_NUM_ARGS(), param_spec, &args, &arr_argc, &fci1, &fci1_cache) == FAILURE) {
4393			return;
4394		}
4395		fci_data = &fci1;
4396		fci_data_cache = &fci1_cache;
4397
4398	} else if (behavior & DIFF_ASSOC) { /* triggered also if DIFF_KEY */
4399		/* DIFF_KEY is subset of DIFF_ASSOC. When having the former
4400		 * no comparison of the data is done (part of DIFF_ASSOC) */
4401
4402		if (data_compare_type == DIFF_COMP_DATA_INTERNAL && key_compare_type == DIFF_COMP_KEY_INTERNAL) {
4403			/* array_diff_assoc() or array_diff_key() */
4404			req_args = 2;
4405			param_spec = "+";
4406			diff_key_compare_func = php_array_key_compare_string;
4407			diff_data_compare_func = php_array_data_compare_string;
4408		} else if (data_compare_type == DIFF_COMP_DATA_USER && key_compare_type == DIFF_COMP_KEY_INTERNAL) {
4409			/* array_udiff_assoc() */
4410			req_args = 3;
4411			param_spec = "+f";
4412			diff_key_compare_func = php_array_key_compare_string;
4413			diff_data_compare_func = php_array_user_compare;
4414			fci_data = &fci1;
4415			fci_data_cache = &fci1_cache;
4416		} else if (data_compare_type == DIFF_COMP_DATA_INTERNAL && key_compare_type == DIFF_COMP_KEY_USER) {
4417			/* array_diff_uassoc() or array_diff_ukey() */
4418			req_args = 3;
4419			param_spec = "+f";
4420			diff_key_compare_func = php_array_user_key_compare;
4421			diff_data_compare_func = php_array_data_compare_string;
4422			fci_key = &fci1;
4423			fci_key_cache = &fci1_cache;
4424		} else if (data_compare_type == DIFF_COMP_DATA_USER && key_compare_type == DIFF_COMP_KEY_USER) {
4425			/* array_udiff_uassoc() */
4426			req_args = 4;
4427			param_spec = "+ff";
4428			diff_key_compare_func = php_array_user_key_compare;
4429			diff_data_compare_func = php_array_user_compare;
4430			fci_data = &fci1;
4431			fci_data_cache = &fci1_cache;
4432			fci_key = &fci2;
4433			fci_key_cache = &fci2_cache;
4434		} else {
4435			php_error_docref(NULL, E_WARNING, "data_compare_type is %d. key_compare_type is %d. This should never happen. Please report as a bug", data_compare_type, key_compare_type);
4436			return;
4437		}
4438
4439		if (ZEND_NUM_ARGS() < req_args) {
4440			php_error_docref(NULL, E_WARNING, "at least %d parameters are required, %d given", req_args, ZEND_NUM_ARGS());
4441			return;
4442		}
4443
4444		if (zend_parse_parameters(ZEND_NUM_ARGS(), param_spec, &args, &arr_argc, &fci1, &fci1_cache, &fci2, &fci2_cache) == FAILURE) {
4445			return;
4446		}
4447
4448	} else {
4449		php_error_docref(NULL, E_WARNING, "behavior is %d. This should never happen. Please report as a bug", behavior);
4450		return;
4451	}
4452
4453	PHP_ARRAY_CMP_FUNC_BACKUP();
4454
4455	/* for each argument, create and sort list with pointers to the hash buckets */
4456	lists = (Bucket **)safe_emalloc(arr_argc, sizeof(Bucket *), 0);
4457	ptrs = (Bucket **)safe_emalloc(arr_argc, sizeof(Bucket *), 0);
4458
4459	if (behavior == DIFF_NORMAL && data_compare_type == DIFF_COMP_DATA_USER) {
4460		BG(user_compare_fci) = *fci_data;
4461		BG(user_compare_fci_cache) = *fci_data_cache;
4462	} else if (behavior & DIFF_ASSOC && key_compare_type == DIFF_COMP_KEY_USER) {
4463		BG(user_compare_fci) = *fci_key;
4464		BG(user_compare_fci_cache) = *fci_key_cache;
4465	}
4466
4467	for (i = 0; i < arr_argc; i++) {
4468		if (Z_TYPE(args[i]) != IS_ARRAY) {
4469			php_error_docref(NULL, E_WARNING, "Argument #%d is not an array", i + 1);
4470			arr_argc = i; /* only free up to i - 1 */
4471			goto out;
4472		}
4473		hash = Z_ARRVAL(args[i]);
4474		list = (Bucket *) pemalloc((hash->nNumOfElements + 1) * sizeof(Bucket), hash->u.flags & HASH_FLAG_PERSISTENT);
4475		if (!list) {
4476			PHP_ARRAY_CMP_FUNC_RESTORE();
4477
4478			efree(ptrs);
4479			efree(lists);
4480			RETURN_FALSE;
4481		}
4482		lists[i] = list;
4483		ptrs[i] = list;
4484		for (idx = 0; idx < hash->nNumUsed; idx++) {
4485			p = hash->arData + idx;
4486			if (Z_TYPE(p->val) == IS_UNDEF) continue;
4487			*list++ = *p;
4488		}
4489		ZVAL_UNDEF(&list->val);
4490		if (hash->nNumOfElements > 1) {
4491			if (behavior == DIFF_NORMAL) {
4492				zend_sort((void *) lists[i], hash->nNumOfElements,
4493						sizeof(Bucket), diff_data_compare_func, (swap_func_t)zend_hash_bucket_swap);
4494			} else if (behavior & DIFF_ASSOC) { /* triggered also when DIFF_KEY */
4495				zend_sort((void *) lists[i], hash->nNumOfElements,
4496						sizeof(Bucket), diff_key_compare_func, (swap_func_t)zend_hash_bucket_swap);
4497			}
4498		}
4499	}
4500
4501	/* copy the argument array */
4502	RETVAL_ARR(zend_array_dup(Z_ARRVAL(args[0])));
4503
4504	/* go through the lists and look for values of ptr[0] that are not in the others */
4505	while (Z_TYPE(ptrs[0]->val) != IS_UNDEF) {
4506		if ((behavior & DIFF_ASSOC) /* triggered also when DIFF_KEY */
4507			&&
4508			key_compare_type == DIFF_COMP_KEY_USER
4509		) {
4510			BG(user_compare_fci) = *fci_key;
4511			BG(user_compare_fci_cache) = *fci_key_cache;
4512		}
4513		c = 1;
4514		for (i = 1; i < arr_argc; i++) {
4515			Bucket *ptr = ptrs[i];
4516			if (behavior == DIFF_NORMAL) {
4517				while (Z_TYPE(ptrs[i]->val) != IS_UNDEF && (0 < (c = diff_data_compare_func(ptrs[0], ptrs[i])))) {
4518					ptrs[i]++;
4519				}
4520			} else if (behavior & DIFF_ASSOC) { /* triggered also when DIFF_KEY */
4521				while (Z_TYPE(ptr->val) != IS_UNDEF && (0 != (c = diff_key_compare_func(ptrs[0], ptr)))) {
4522					ptr++;
4523				}
4524			}
4525			if (!c) {
4526				if (behavior == DIFF_NORMAL) {
4527					if (Z_TYPE(ptrs[i]->val) != IS_UNDEF) {
4528						ptrs[i]++;
4529					}
4530					break;
4531				} else if (behavior == DIFF_ASSOC) {  /* only when DIFF_ASSOC */
4532					/* In this branch is execute only when DIFF_ASSOC. If behavior == DIFF_KEY
4533					 * data comparison is not needed - skipped. */
4534					if (Z_TYPE(ptr->val) != IS_UNDEF) {
4535						if (data_compare_type == DIFF_COMP_DATA_USER) {
4536							BG(user_compare_fci) = *fci_data;
4537							BG(user_compare_fci_cache) = *fci_data_cache;
4538						}
4539						if (diff_data_compare_func(ptrs[0], ptr) != 0) {
4540							/* the data is not the same */
4541							c = -1;
4542							if (key_compare_type == DIFF_COMP_KEY_USER) {
4543								BG(user_compare_fci) = *fci_key;
4544								BG(user_compare_fci_cache) = *fci_key_cache;
4545							}
4546						} else {
4547							break;
4548							/* we have found the element in other arrays thus we don't want it
4549							 * in the return_value -> delete from there */
4550						}
4551					}
4552				} else if (behavior == DIFF_KEY) { /* only when DIFF_KEY */
4553					/* the behavior here differs from INTERSECT_KEY in php_intersect
4554					 * since in the "diff" case we have to remove the entry from
4555					 * return_value while when doing intersection the entry must not
4556					 * be deleted. */
4557					break; /* remove the key */
4558				}
4559			}
4560		}
4561		if (!c) {
4562			/* ptrs[0] in one of the other arguments */
4563			/* delete all entries with value as ptrs[0] */
4564			for (;;) {
4565				p = ptrs[0];
4566				if (p->key == NULL) {
4567					zend_hash_index_del(Z_ARRVAL_P(return_value), p->h);
4568				} else {
4569					zend_hash_del(Z_ARRVAL_P(return_value), p->key);
4570				}
4571				if (Z_TYPE((++ptrs[0])->val) == IS_UNDEF) {
4572					goto out;
4573				}
4574				if (behavior == DIFF_NORMAL) {
4575					if (diff_data_compare_func(ptrs[0] - 1, ptrs[0])) {
4576						break;
4577					}
4578				} else if (behavior & DIFF_ASSOC) { /* triggered also when DIFF_KEY */
4579					/* in this case no array_key_compare is needed */
4580					break;
4581				}
4582			}
4583		} else {
4584			/* ptrs[0] in none of the other arguments */
4585			/* skip all entries with value as ptrs[0] */
4586			for (;;) {
4587				if (Z_TYPE((++ptrs[0])->val) == IS_UNDEF) {
4588					goto out;
4589				}
4590				if (behavior == DIFF_NORMAL) {
4591					if (diff_data_compare_func(ptrs[0] - 1, ptrs[0])) {
4592						break;
4593					}
4594				} else if (behavior & DIFF_ASSOC) { /* triggered also when DIFF_KEY */
4595					/* in this case no array_key_compare is needed */
4596					break;
4597				}
4598			}
4599		}
4600	}
4601out:
4602	for (i = 0; i < arr_argc; i++) {
4603		hash = Z_ARRVAL(args[i]);
4604		pefree(lists[i], hash->u.flags & HASH_FLAG_PERSISTENT);
4605	}
4606
4607	PHP_ARRAY_CMP_FUNC_RESTORE();
4608
4609	efree(ptrs);
4610	efree(lists);
4611}
4612/* }}} */
4613
4614/* {{{ proto array array_diff_key(array arr1, array arr2 [, array ...])
4615   Returns the entries of arr1 that have keys which are not present in any of the others arguments. This function is like array_diff() but works on the keys instead of the values. The associativity is preserved. */
4616PHP_FUNCTION(array_diff_key)
4617{
4618	php_array_diff_key(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_COMP_DATA_NONE);
4619}
4620/* }}} */
4621
4622/* {{{ proto array array_diff_ukey(array arr1, array arr2 [, array ...], callback key_comp_func)
4623   Returns the entries of arr1 that have keys which are not present in any of the others arguments. User supplied function is used for comparing the keys. This function is like array_udiff() but works on the keys instead of the values. The associativity is preserved. */
4624PHP_FUNCTION(array_diff_ukey)
4625{
4626	php_array_diff(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_KEY, DIFF_COMP_DATA_INTERNAL, DIFF_COMP_KEY_USER);
4627}
4628/* }}} */
4629
4630/* {{{ proto array array_diff(array arr1, array arr2 [, array ...])
4631   Returns the entries of arr1 that have values which are not present in any of the others arguments. */
4632PHP_FUNCTION(array_diff)
4633{
4634	zval *args;
4635	int argc, i;
4636	uint32_t num;
4637	HashTable exclude;
4638	zval *value;
4639	zend_string *str, *key;
4640	zend_long idx;
4641	zval dummy;
4642
4643	if (ZEND_NUM_ARGS() < 2) {
4644		php_error_docref(NULL, E_WARNING, "at least 2 parameters are required, %d given", ZEND_NUM_ARGS());
4645		return;
4646	}
4647
4648	if (zend_parse_parameters(ZEND_NUM_ARGS(), "+", &args, &argc) == FAILURE) {
4649		return;
4650	}
4651
4652	if (Z_TYPE(args[0]) != IS_ARRAY) {
4653		php_error_docref(NULL, E_WARNING, "Argument #1 is not an array");
4654		RETURN_NULL();
4655	}
4656
4657	/* count number of elements */
4658	num = 0;
4659	for (i = 1; i < argc; i++) {
4660		if (Z_TYPE(args[i]) != IS_ARRAY) {
4661			php_error_docref(NULL, E_WARNING, "Argument #%d is not an array", i + 1);
4662			RETURN_NULL();
4663		}
4664		num += zend_hash_num_elements(Z_ARRVAL(args[i]));
4665	}
4666
4667	if (num == 0) {
4668		ZVAL_COPY(return_value, &args[0]);
4669		return;
4670	}
4671
4672	ZVAL_NULL(&dummy);
4673	/* create exclude map */
4674	zend_hash_init(&exclude, num, NULL, NULL, 0);
4675	for (i = 1; i < argc; i++) {
4676		ZEND_HASH_FOREACH_VAL_IND(Z_ARRVAL(args[i]), value) {
4677			str = zval_get_string(value);
4678			zend_hash_add(&exclude, str, &dummy);
4679			zend_string_release(str);
4680		} ZEND_HASH_FOREACH_END();
4681	}
4682
4683	/* copy all elements of first array that are not in exclude set */
4684	array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL(args[0])));
4685	ZEND_HASH_FOREACH_KEY_VAL_IND(Z_ARRVAL(args[0]), idx, key, value) {
4686		str = zval_get_string(value);
4687		if (!zend_hash_exists(&exclude, str)) {
4688			if (key) {
4689				value = zend_hash_add_new(Z_ARRVAL_P(return_value), key, value);
4690			} else {
4691				value = zend_hash_index_add_new(Z_ARRVAL_P(return_value), idx, value);
4692			}
4693			zval_add_ref(value);
4694		}
4695		zend_string_release(str);
4696	} ZEND_HASH_FOREACH_END();
4697
4698	zend_hash_destroy(&exclude);
4699}
4700/* }}} */
4701
4702/* {{{ proto array array_udiff(array arr1, array arr2 [, array ...], callback data_comp_func)
4703   Returns the entries of arr1 that have values which are not present in any of the others arguments. Elements are compared by user supplied function. */
4704PHP_FUNCTION(array_udiff)
4705{
4706	php_array_diff(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_NORMAL, DIFF_COMP_DATA_USER, DIFF_COMP_KEY_INTERNAL);
4707}
4708/* }}} */
4709
4710/* {{{ proto array array_diff_assoc(array arr1, array arr2 [, array ...])
4711   Returns the entries of arr1 that have values which are not present in any of the others arguments but do additional checks whether the keys are equal */
4712PHP_FUNCTION(array_diff_assoc)
4713{
4714	php_array_diff_key(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_COMP_DATA_INTERNAL);
4715}
4716/* }}} */
4717
4718/* {{{ proto array array_diff_uassoc(array arr1, array arr2 [, array ...], callback data_comp_func)
4719   Returns the entries of arr1 that have values which are not present in any of the others arguments but do additional checks whether the keys are equal. Elements are compared by user supplied function. */
4720PHP_FUNCTION(array_diff_uassoc)
4721{
4722	php_array_diff(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_ASSOC, DIFF_COMP_DATA_INTERNAL, DIFF_COMP_KEY_USER);
4723}
4724/* }}} */
4725
4726/* {{{ proto array array_udiff_assoc(array arr1, array arr2 [, array ...], callback key_comp_func)
4727   Returns the entries of arr1 that have values which are not present in any of the others arguments but do additional checks whether the keys are equal. Keys are compared by user supplied function. */
4728PHP_FUNCTION(array_udiff_assoc)
4729{
4730	php_array_diff_key(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_COMP_DATA_USER);
4731}
4732/* }}} */
4733
4734/* {{{ proto array array_udiff_uassoc(array arr1, array arr2 [, array ...], callback data_comp_func, callback key_comp_func)
4735   Returns the entries of arr1 that have values which are not present in any of the others arguments but do additional checks whether the keys are equal. Keys and elements are compared by user supplied functions. */
4736PHP_FUNCTION(array_udiff_uassoc)
4737{
4738	php_array_diff(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_ASSOC, DIFF_COMP_DATA_USER, DIFF_COMP_KEY_USER);
4739}
4740/* }}} */
4741
4742#define MULTISORT_ORDER	0
4743#define MULTISORT_TYPE	1
4744#define MULTISORT_LAST	2
4745
4746PHPAPI int php_multisort_compare(const void *a, const void *b) /* {{{ */
4747{
4748	Bucket *ab = *(Bucket **)a;
4749	Bucket *bb = *(Bucket **)b;
4750	int r;
4751	zend_long result;
4752
4753	r = 0;
4754	do {
4755		result = ARRAYG(multisort_func)[r](&ab[r], &bb[r]);
4756		if (result != 0) {
4757			return result > 0 ? 1 : -1;
4758		}
4759		r++;
4760	} while (Z_TYPE(ab[r].val) != IS_UNDEF);
4761
4762	return 0;
4763}
4764/* }}} */
4765
4766#define MULTISORT_ABORT				\
4767	efree(ARRAYG(multisort_func));	\
4768	efree(arrays);					\
4769	RETURN_FALSE;
4770
4771static void array_bucket_p_sawp(void *p, void *q) /* {{{ */ {
4772	Bucket *t;
4773	Bucket **f = (Bucket **)p;
4774	Bucket **g = (Bucket **)q;
4775
4776	t = *f;
4777	*f = *g;
4778	*g = t;
4779}
4780/* }}} */
4781
4782/* {{{ proto bool array_multisort(array &$array1 [, mixed $array1_sort_order [, mixed $array1_sort_flags [, mixed ... ]]]
4783   Sort multiple arrays at once similar to how ORDER BY clause works in SQL */
4784PHP_FUNCTION(array_multisort)
4785{
4786	zval*			args;
4787	zval**			arrays;
4788	Bucket**		indirect;
4789	uint            idx;
4790	Bucket*			p;
4791	HashTable*		hash;
4792	int				argc;
4793	int				array_size;
4794	int				num_arrays = 0;
4795	int				parse_state[MULTISORT_LAST];   /* 0 - flag not allowed 1 - flag allowed */
4796	int				sort_order = PHP_SORT_ASC;
4797	int				sort_type  = PHP_SORT_REGULAR;
4798	int				i, k, n;
4799
4800	if (zend_parse_parameters(ZEND_NUM_ARGS(), "+", &args, &argc) == FAILURE) {
4801		return;
4802	}
4803
4804	/* Allocate space for storing pointers to input arrays and sort flags. */
4805	arrays = (zval **)ecalloc(argc, sizeof(zval *));
4806	for (i = 0; i < MULTISORT_LAST; i++) {
4807		parse_state[i] = 0;
4808	}
4809	ARRAYG(multisort_func) = (compare_func_t*)ecalloc(argc, sizeof(compare_func_t));
4810
4811	/* Here we go through the input arguments and parse them. Each one can
4812	 * be either an array or a sort flag which follows an array. If not
4813	 * specified, the sort flags defaults to PHP_SORT_ASC and PHP_SORT_REGULAR
4814	 * accordingly. There can't be two sort flags of the same type after an
4815	 * array, and the very first argument has to be an array. */
4816	for (i = 0; i < argc; i++) {
4817		zval *arg = &args[i];
4818
4819		ZVAL_DEREF(arg);
4820		if (Z_TYPE_P(arg) == IS_ARRAY) {
4821			SEPARATE_ARRAY(arg);
4822			/* We see the next array, so we update the sort flags of
4823			 * the previous array and reset the sort flags. */
4824			if (i > 0) {
4825				ARRAYG(multisort_func)[num_arrays - 1] = php_get_data_compare_func(sort_type, sort_order != PHP_SORT_ASC);
4826				sort_order = PHP_SORT_ASC;
4827				sort_type = PHP_SORT_REGULAR;
4828			}
4829			arrays[num_arrays++] = arg;
4830
4831			/* Next one may be an array or a list of sort flags. */
4832			for (k = 0; k < MULTISORT_LAST; k++) {
4833				parse_state[k] = 1;
4834			}
4835		} else if (Z_TYPE_P(arg) == IS_LONG) {
4836			switch (Z_LVAL_P(arg) & ~PHP_SORT_FLAG_CASE) {
4837				case PHP_SORT_ASC:
4838				case PHP_SORT_DESC:
4839					/* flag allowed here */
4840					if (parse_state[MULTISORT_ORDER] == 1) {
4841						/* Save the flag and make sure then next arg is not the current flag. */
4842						sort_order = Z_LVAL_P(arg) == PHP_SORT_DESC ? PHP_SORT_DESC : PHP_SORT_ASC;
4843						parse_state[MULTISORT_ORDER] = 0;
4844					} else {
4845						php_error_docref(NULL, E_WARNING, "Argument #%d is expected to be an array or sorting flag that has not already been specified", i + 1);
4846						MULTISORT_ABORT;
4847					}
4848					break;
4849
4850				case PHP_SORT_REGULAR:
4851				case PHP_SORT_NUMERIC:
4852				case PHP_SORT_STRING:
4853				case PHP_SORT_NATURAL:
4854#if HAVE_STRCOLL
4855				case PHP_SORT_LOCALE_STRING:
4856#endif
4857					/* flag allowed here */
4858					if (parse_state[MULTISORT_TYPE] == 1) {
4859						/* Save the flag and make sure then next arg is not the current flag. */
4860						sort_type = (int)Z_LVAL_P(arg);
4861						parse_state[MULTISORT_TYPE] = 0;
4862					} else {
4863						php_error_docref(NULL, E_WARNING, "Argument #%d is expected to be an array or sorting flag that has not already been specified", i + 1);
4864						MULTISORT_ABORT;
4865					}
4866					break;
4867
4868				default:
4869					php_error_docref(NULL, E_WARNING, "Argument #%d is an unknown sort flag", i + 1);
4870					MULTISORT_ABORT;
4871					break;
4872
4873			}
4874		} else {
4875			php_error_docref(NULL, E_WARNING, "Argument #%d is expected to be an array or a sort flag", i + 1);
4876			MULTISORT_ABORT;
4877		}
4878	}
4879	/* Take care of the last array sort flags. */
4880	ARRAYG(multisort_func)[num_arrays - 1] = php_get_data_compare_func(sort_type, sort_order != PHP_SORT_ASC);
4881
4882	/* Make sure the arrays are of the same size. */
4883	array_size = zend_hash_num_elements(Z_ARRVAL_P(arrays[0]));
4884	for (i = 0; i < num_arrays; i++) {
4885		if (zend_hash_num_elements(Z_ARRVAL_P(arrays[i])) != array_size) {
4886			php_error_docref(NULL, E_WARNING, "Array sizes are inconsistent");
4887			MULTISORT_ABORT;
4888		}
4889	}
4890
4891	/* If all arrays are empty we don't need to do anything. */
4892	if (array_size < 1) {
4893		efree(ARRAYG(multisort_func));
4894		efree(arrays);
4895		RETURN_TRUE;
4896	}
4897
4898	/* Create the indirection array. This array is of size MxN, where
4899	 * M is the number of entries in each input array and N is the number
4900	 * of the input arrays + 1. The last column is NULL to indicate the end
4901	 * of the row. */
4902	indirect = (Bucket **)safe_emalloc(array_size, sizeof(Bucket *), 0);
4903	for (i = 0; i < array_size; i++) {
4904		indirect[i] = (Bucket *)safe_emalloc((num_arrays + 1), sizeof(Bucket), 0);
4905	}
4906	for (i = 0; i < num_arrays; i++) {
4907		k = 0;
4908		for (idx = 0; idx < Z_ARRVAL_P(arrays[i])->nNumUsed; idx++) {
4909			p = Z_ARRVAL_P(arrays[i])->arData + idx;
4910			if (Z_TYPE(p->val) == IS_UNDEF) continue;
4911			indirect[k][i] = *p;
4912			k++;
4913		}
4914	}
4915	for (k = 0; k < array_size; k++) {
4916		ZVAL_UNDEF(&indirect[k][num_arrays].val);
4917	}
4918
4919	/* Do the actual sort magic - bada-bim, bada-boom. */
4920	zend_qsort(indirect, array_size, sizeof(Bucket *), php_multisort_compare, (swap_func_t)array_bucket_p_sawp);
4921
4922	/* Restructure the arrays based on sorted indirect - this is mostly taken from zend_hash_sort() function. */
4923	HANDLE_BLOCK_INTERRUPTIONS();
4924	for (i = 0; i < num_arrays; i++) {
4925		int repack;
4926
4927		hash = Z_ARRVAL_P(arrays[i]);
4928		hash->nNumUsed = array_size;
4929		hash->nInternalPointer = 0;
4930		repack = !(hash->u.flags & HASH_FLAG_PACKED);
4931
4932		for (n = 0, k = 0; k < array_size; k++) {
4933			hash->arData[k] = indirect[k][i];
4934			if (hash->arData[k].key == NULL) {
4935				hash->arData[k].h = n++;
4936			} else {
4937				repack = 0;
4938			}
4939		}
4940		hash->nNextFreeElement = array_size;
4941		if (repack) {
4942			zend_hash_to_packed(hash);
4943		} else {
4944			zend_hash_rehash(hash);
4945		}
4946	}
4947	HANDLE_UNBLOCK_INTERRUPTIONS();
4948
4949	/* Clean up. */
4950	for (i = 0; i < array_size; i++) {
4951		efree(indirect[i]);
4952	}
4953	efree(indirect);
4954	efree(ARRAYG(multisort_func));
4955	efree(arrays);
4956	RETURN_TRUE;
4957}
4958/* }}} */
4959
4960/* {{{ proto mixed array_rand(array input [, int num_req])
4961   Return key/keys for random entry/entries in the array */
4962PHP_FUNCTION(array_rand)
4963{
4964	zval *input;
4965	zend_long randval, num_req = 1;
4966	int num_avail;
4967	zend_string *string_key;
4968	zend_ulong num_key;
4969
4970	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a|l", &input, &num_req) == FAILURE) {
4971		return;
4972	}
4973
4974	num_avail = zend_hash_num_elements(Z_ARRVAL_P(input));
4975
4976	if (ZEND_NUM_ARGS() > 1) {
4977		if (num_req <= 0 || num_req > num_avail) {
4978			php_error_docref(NULL, E_WARNING, "Second argument has to be between 1 and the number of elements in the array");
4979			return;
4980		}
4981	}
4982
4983	/* Make the return value an array only if we need to pass back more than one result. */
4984	if (num_req > 1) {
4985		array_init_size(return_value, (uint32_t)num_req);
4986	}
4987
4988	/* We can't use zend_hash_index_find() because the array may have string keys or gaps. */
4989	ZEND_HASH_FOREACH_KEY(Z_ARRVAL_P(input), num_key, string_key) {
4990		if (!num_req) {
4991			break;
4992		}
4993
4994		randval = php_rand();
4995
4996		if ((double) (randval / (PHP_RAND_MAX + 1.0)) < (double) num_req / (double) num_avail) {
4997			/* If we are returning a single result, just do it. */
4998			if (Z_TYPE_P(return_value) != IS_ARRAY) {
4999				if (string_key) {
5000					RETURN_STR_COPY(string_key);
5001				} else {
5002					RETURN_LONG(num_key);
5003				}
5004			} else {
5005				/* Append the result to the return value. */
5006				if (string_key) {
5007					add_next_index_str(return_value, zend_string_copy(string_key));
5008				} else {
5009					add_next_index_long(return_value, num_key);
5010				}
5011			}
5012			num_req--;
5013		}
5014		num_avail--;
5015	} ZEND_HASH_FOREACH_END();
5016}
5017/* }}} */
5018
5019/* {{{ proto mixed array_sum(array input)
5020   Returns the sum of the array entries */
5021PHP_FUNCTION(array_sum)
5022{
5023	zval *input,
5024		 *entry,
5025		 entry_n;
5026
5027	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a", &input) == FAILURE) {
5028		return;
5029	}
5030
5031	ZVAL_LONG(return_value, 0);
5032
5033	ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(input), entry) {
5034		if (Z_TYPE_P(entry) == IS_ARRAY || Z_TYPE_P(entry) == IS_OBJECT) {
5035			continue;
5036		}
5037		ZVAL_COPY(&entry_n, entry);
5038		convert_scalar_to_number(&entry_n);
5039		fast_add_function(return_value, return_value, &entry_n);
5040	} ZEND_HASH_FOREACH_END();
5041}
5042/* }}} */
5043
5044/* {{{ proto mixed array_product(array input)
5045   Returns the product of the array entries */
5046PHP_FUNCTION(array_product)
5047{
5048	zval *input,
5049		 *entry,
5050		 entry_n;
5051	double dval;
5052
5053	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a", &input) == FAILURE) {
5054		return;
5055	}
5056
5057	ZVAL_LONG(return_value, 1);
5058	if (!zend_hash_num_elements(Z_ARRVAL_P(input))) {
5059		return;
5060	}
5061
5062	ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(input), entry) {
5063		if (Z_TYPE_P(entry) == IS_ARRAY || Z_TYPE_P(entry) == IS_OBJECT) {
5064			continue;
5065		}
5066		ZVAL_COPY(&entry_n, entry);
5067		convert_scalar_to_number(&entry_n);
5068
5069		if (Z_TYPE(entry_n) == IS_LONG && Z_TYPE_P(return_value) == IS_LONG) {
5070			dval = (double)Z_LVAL_P(return_value) * (double)Z_LVAL(entry_n);
5071			if ( (double)ZEND_LONG_MIN <= dval && dval <= (double)ZEND_LONG_MAX ) {
5072				Z_LVAL_P(return_value) *= Z_LVAL(entry_n);
5073				continue;
5074			}
5075		}
5076		convert_to_double(return_value);
5077		convert_to_double(&entry_n);
5078		Z_DVAL_P(return_value) *= Z_DVAL(entry_n);
5079	} ZEND_HASH_FOREACH_END();
5080}
5081/* }}} */
5082
5083/* {{{ proto mixed array_reduce(array input, mixed callback [, mixed initial])
5084   Iteratively reduce the array to a single value via the callback. */
5085PHP_FUNCTION(array_reduce)
5086{
5087	zval *input;
5088	zval args[2];
5089	zval *operand;
5090	zval result;
5091	zval retval;
5092	zend_fcall_info fci;
5093	zend_fcall_info_cache fci_cache = empty_fcall_info_cache;
5094	zval *initial = NULL;
5095	HashTable *htbl;
5096
5097	if (zend_parse_parameters(ZEND_NUM_ARGS(), "af|z", &input, &fci, &fci_cache, &initial) == FAILURE) {
5098		return;
5099	}
5100
5101
5102	if (ZEND_NUM_ARGS() > 2) {
5103		ZVAL_DUP(&result, initial);
5104	} else {
5105		ZVAL_NULL(&result);
5106	}
5107
5108	/* (zval **)input points to an element of argument stack
5109	 * the base pointer of which is subject to change.
5110	 * thus we need to keep the pointer to the hashtable for safety */
5111	htbl = Z_ARRVAL_P(input);
5112
5113	if (zend_hash_num_elements(htbl) == 0) {
5114		ZVAL_COPY_VALUE(return_value, &result);
5115		return;
5116	}
5117
5118	fci.retval = &retval;
5119	fci.param_count = 2;
5120	fci.no_separation = 0;
5121
5122	ZEND_HASH_FOREACH_VAL(htbl, operand) {
5123		ZVAL_COPY(&args[0], &result);
5124		ZVAL_COPY(&args[1], operand);
5125		fci.params = args;
5126
5127		if (zend_call_function(&fci, &fci_cache) == SUCCESS && Z_TYPE(retval) != IS_UNDEF) {
5128			zval_ptr_dtor(&args[1]);
5129			zval_ptr_dtor(&args[0]);
5130			zval_ptr_dtor(&result);
5131			ZVAL_COPY_VALUE(&result, &retval);
5132		} else {
5133			zval_ptr_dtor(&args[1]);
5134			zval_ptr_dtor(&args[0]);
5135			return;
5136		}
5137	} ZEND_HASH_FOREACH_END();
5138
5139	RETVAL_ZVAL(&result, 1, 1);
5140}
5141/* }}} */
5142
5143/* {{{ proto array array_filter(array input [, mixed callback])
5144   Filters elements from the array via the callback. */
5145PHP_FUNCTION(array_filter)
5146{
5147	zval *array;
5148	zval *operand;
5149	zval *key;
5150	zval args[2];
5151	zval retval;
5152	zend_bool have_callback = 0;
5153	zend_long use_type = 0;
5154	zend_string *string_key;
5155	zend_fcall_info fci = empty_fcall_info;
5156	zend_fcall_info_cache fci_cache = empty_fcall_info_cache;
5157	zend_ulong num_key;
5158
5159	if (zend_parse_parameters(ZEND_NUM_ARGS(), "a|fl", &array, &fci, &fci_cache, &use_type) == FAILURE) {
5160		return;
5161	}
5162
5163	array_init(return_value);
5164	if (zend_hash_num_elements(Z_ARRVAL_P(array)) == 0) {
5165		return;
5166	}
5167
5168	if (ZEND_NUM_ARGS() > 1) {
5169		have_callback = 1;
5170		fci.no_separation = 0;
5171		fci.retval = &retval;
5172		if (use_type == ARRAY_FILTER_USE_BOTH) {
5173			fci.param_count = 2;
5174			key = &args[1];
5175		} else {
5176			fci.param_count = 1;
5177			key = &args[0];
5178		}
5179	}
5180
5181	ZEND_HASH_FOREACH_KEY_VAL_IND(Z_ARRVAL_P(array), num_key, string_key, operand) {
5182		if (have_callback) {
5183			if (use_type) {
5184				/* Set up the key */
5185				if (!string_key) {
5186					ZVAL_LONG(key, num_key);
5187				} else {
5188					ZVAL_STR_COPY(key, string_key);
5189				}
5190			}
5191			if (use_type != ARRAY_FILTER_USE_KEY) {
5192				ZVAL_COPY(&args[0], operand);
5193			}
5194			fci.params = args;
5195
5196			if (zend_call_function(&fci, &fci_cache) == SUCCESS) {
5197				zval_ptr_dtor(&args[0]);
5198				if (use_type == ARRAY_FILTER_USE_BOTH) {
5199					zval_ptr_dtor(&args[1]);
5200				}
5201				if (!Z_ISUNDEF(retval)) {
5202					int retval_true = zend_is_true(&retval);
5203
5204					zval_ptr_dtor(&retval);
5205					if (!retval_true) {
5206						continue;
5207					}
5208				} else {
5209					continue;
5210				}
5211			} else {
5212				zval_ptr_dtor(&args[0]);
5213				if (use_type == ARRAY_FILTER_USE_BOTH) {
5214					zval_ptr_dtor(&args[1]);
5215				}
5216				return;
5217			}
5218		} else if (!zend_is_true(operand)) {
5219			continue;
5220		}
5221
5222		if (string_key) {
5223			operand = zend_hash_update(Z_ARRVAL_P(return_value), string_key, operand);
5224		} else {
5225			operand = zend_hash_index_update(Z_ARRVAL_P(return_value), num_key, operand);
5226		}
5227		zval_add_ref(operand);
5228	} ZEND_HASH_FOREACH_END();
5229}
5230/* }}} */
5231
5232/* {{{ proto array array_map(mixed callback, array input1 [, array input2 ,...])
5233   Applies the callback to the elements in given arrays. */
5234PHP_FUNCTION(array_map)
5235{
5236	zval *arrays = NULL;
5237	int n_arrays = 0;
5238	zval result;
5239	zend_fcall_info fci = empty_fcall_info;
5240	zend_fcall_info_cache fci_cache = empty_fcall_info_cache;
5241	int i;
5242	uint32_t k, maxlen = 0;
5243
5244#ifndef FAST_ZPP
5245	if (zend_parse_parameters(ZEND_NUM_ARGS(), "f!+", &fci, &fci_cache, &arrays, &n_arrays) == FAILURE) {
5246		return;
5247	}
5248#else
5249	ZEND_PARSE_PARAMETERS_START(2, -1)
5250		Z_PARAM_FUNC_EX(fci, fci_cache, 1, 0)
5251		Z_PARAM_VARIADIC('+', arrays, n_arrays)
5252	ZEND_PARSE_PARAMETERS_END();
5253#endif
5254
5255	RETVAL_NULL();
5256
5257	if (n_arrays == 1) {
5258		zend_ulong num_key;
5259		zend_string *str_key;
5260		zval *zv, arg;
5261
5262		if (Z_TYPE(arrays[0]) != IS_ARRAY) {
5263			php_error_docref(NULL, E_WARNING, "Argument #%d should be an array", 2);
5264			return;
5265		}
5266		maxlen = zend_hash_num_elements(Z_ARRVAL(arrays[0]));
5267
5268		/* Short-circuit: if no callback and only one array, just return it. */
5269		if (!ZEND_FCI_INITIALIZED(fci)) {
5270			ZVAL_COPY(return_value, &arrays[0]);
5271			return;
5272		}
5273
5274		array_init_size(return_value, maxlen);
5275
5276		ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL(arrays[0]), num_key, str_key, zv) {
5277			fci.retval = &result;
5278			fci.param_count = 1;
5279			fci.params = &arg;
5280			fci.no_separation = 0;
5281
5282			ZVAL_COPY(&arg, zv);
5283
5284			if (zend_call_function(&fci, &fci_cache) != SUCCESS || Z_TYPE(result) == IS_UNDEF) {
5285				zval_dtor(return_value);
5286				zval_ptr_dtor(&arg);
5287				RETURN_NULL();
5288			} else {
5289				zval_ptr_dtor(&arg);
5290			}
5291			if (str_key) {
5292				zend_hash_add_new(Z_ARRVAL_P(return_value), str_key, &result);
5293			} else {
5294				zend_hash_index_add_new(Z_ARRVAL_P(return_value), num_key, &result);
5295			}
5296		} ZEND_HASH_FOREACH_END();
5297	} else {
5298		uint32_t *array_pos = (HashPosition *)ecalloc(n_arrays, sizeof(HashPosition));
5299
5300		for (i = 0; i < n_arrays; i++) {
5301			if (Z_TYPE(arrays[i]) != IS_ARRAY) {
5302				php_error_docref(NULL, E_WARNING, "Argument #%d should be an array", i + 2);
5303				efree(array_pos);
5304				return;
5305			}
5306			if (zend_hash_num_elements(Z_ARRVAL(arrays[i])) > maxlen) {
5307				maxlen = zend_hash_num_elements(Z_ARRVAL(arrays[i]));
5308			}
5309		}
5310
5311		array_init_size(return_value, maxlen);
5312
5313		if (!ZEND_FCI_INITIALIZED(fci)) {
5314			zval zv;
5315
5316			/* We iterate through all the arrays at once. */
5317			for (k = 0; k < maxlen; k++) {
5318
5319				/* If no callback, the result will be an array, consisting of current
5320				 * entries from all arrays. */
5321				array_init_size(&result, n_arrays);
5322
5323				for (i = 0; i < n_arrays; i++) {
5324					/* If this array still has elements, add the current one to the
5325					 * parameter list, otherwise use null value. */
5326					uint32_t pos = array_pos[i];
5327					while (1) {
5328						if (pos >= Z_ARRVAL(arrays[i])->nNumUsed) {
5329							ZVAL_NULL(&zv);
5330							break;
5331						} else if (Z_TYPE(Z_ARRVAL(arrays[i])->arData[pos].val) != IS_UNDEF) {
5332							ZVAL_COPY(&zv, &Z_ARRVAL(arrays[i])->arData[pos].val);
5333							array_pos[i] = pos + 1;
5334							break;
5335						}
5336						pos++;
5337					}
5338
5339					zend_hash_next_index_insert_new(Z_ARRVAL(result), &zv);
5340				}
5341
5342				zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &result);
5343			}
5344		} else {
5345			zval *params = (zval *)safe_emalloc(n_arrays, sizeof(zval), 0);
5346
5347			/* We iterate through all the arrays at once. */
5348			for (k = 0; k < maxlen; k++) {
5349				for (i = 0; i < n_arrays; i++) {
5350					/* If this array still has elements, add the current one to the
5351					 * parameter list, otherwise use null value. */
5352					uint32_t pos = array_pos[i];
5353					while (1) {
5354						if (pos >= Z_ARRVAL(arrays[i])->nNumUsed) {
5355							ZVAL_NULL(&params[i]);
5356							break;
5357						} else if (Z_TYPE(Z_ARRVAL(arrays[i])->arData[pos].val) != IS_UNDEF) {
5358							ZVAL_COPY(&params[i], &Z_ARRVAL(arrays[i])->arData[pos].val);
5359							array_pos[i] = pos + 1;
5360							break;
5361						}
5362						pos++;
5363					}
5364				}
5365
5366				fci.retval = &result;
5367				fci.param_count = n_arrays;
5368				fci.params = params;
5369				fci.no_separation = 0;
5370
5371				if (zend_call_function(&fci, &fci_cache) != SUCCESS || Z_TYPE(result) == IS_UNDEF) {
5372					efree(array_pos);
5373					zval_dtor(return_value);
5374					for (i = 0; i < n_arrays; i++) {
5375						zval_ptr_dtor(&params[i]);
5376					}
5377					efree(params);
5378					RETURN_NULL();
5379				} else {
5380					for (i = 0; i < n_arrays; i++) {
5381						zval_ptr_dtor(&params[i]);
5382					}
5383				}
5384
5385				zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &result);
5386			}
5387
5388			efree(params);
5389		}
5390		efree(array_pos);
5391	}
5392}
5393/* }}} */
5394
5395/* {{{ proto bool array_key_exists(mixed key, array search)
5396   Checks if the given key or index exists in the array */
5397PHP_FUNCTION(array_key_exists)
5398{
5399	zval *key;					/* key to check for */
5400	HashTable *array;			/* array to check in */
5401
5402#ifndef FAST_ZPP
5403	if (zend_parse_parameters(ZEND_NUM_ARGS(), "zH", &key, &array) == FAILURE) {
5404		return;
5405	}
5406#else
5407	ZEND_PARSE_PARAMETERS_START(2, 2)
5408		Z_PARAM_ZVAL(key)
5409		Z_PARAM_ARRAY_OR_OBJECT_HT(array)
5410	ZEND_PARSE_PARAMETERS_END();
5411#endif
5412
5413	switch (Z_TYPE_P(key)) {
5414		case IS_STRING:
5415			if (zend_symtable_exists(array, Z_STR_P(key))) {
5416				RETURN_TRUE;
5417			}
5418			RETURN_FALSE;
5419		case IS_LONG:
5420			if (zend_hash_index_exists(array, Z_LVAL_P(key))) {
5421				RETURN_TRUE;
5422			}
5423			RETURN_FALSE;
5424		case IS_NULL:
5425			if (zend_hash_exists(array, ZSTR_EMPTY_ALLOC())) {
5426				RETURN_TRUE;
5427			}
5428			RETURN_FALSE;
5429
5430		default:
5431			php_error_docref(NULL, E_WARNING, "The first argument should be either a string or an integer");
5432			RETURN_FALSE;
5433	}
5434}
5435/* }}} */
5436
5437/* {{{ proto array array_chunk(array input, int size [, bool preserve_keys])
5438   Split array into chunks */
5439PHP_FUNCTION(array_chunk)
5440{
5441	int argc = ZEND_NUM_ARGS(), num_in;
5442	zend_long size, current = 0;
5443	zend_string *str_key;
5444	zend_ulong num_key;
5445	zend_bool preserve_keys = 0;
5446	zval *input = NULL;
5447	zval chunk;
5448	zval *entry;
5449
5450	if (zend_parse_parameters(argc, "al|b", &input, &size, &preserve_keys) == FAILURE) {
5451		return;
5452	}
5453	/* Do bounds checking for size parameter. */
5454	if (size < 1) {
5455		php_error_docref(NULL, E_WARNING, "Size parameter expected to be greater than 0");
5456		return;
5457	}
5458
5459	num_in = zend_hash_num_elements(Z_ARRVAL_P(input));
5460
5461	if (size > num_in) {
5462		size = num_in > 0 ? num_in : 1;
5463	}
5464
5465	array_init_size(return_value, (uint32_t)(((num_in - 1) / size) + 1));
5466
5467	ZVAL_UNDEF(&chunk);
5468
5469	ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(input), num_key, str_key, entry) {
5470		/* If new chunk, create and initialize it. */
5471		if (Z_TYPE(chunk) == IS_UNDEF) {
5472			array_init_size(&chunk, (uint32_t)size);
5473		}
5474
5475		/* Add entry to the chunk, preserving keys if necessary. */
5476		if (preserve_keys) {
5477			if (str_key) {
5478				entry = zend_hash_update(Z_ARRVAL(chunk), str_key, entry);
5479			} else {
5480				entry = zend_hash_index_update(Z_ARRVAL(chunk), num_key, entry);
5481			}
5482		} else {
5483			entry = zend_hash_next_index_insert(Z_ARRVAL(chunk), entry);
5484		}
5485		zval_add_ref(entry);
5486
5487		/* If reached the chunk size, add it to the result array, and reset the
5488		 * pointer. */
5489		if (!(++current % size)) {
5490			add_next_index_zval(return_value, &chunk);
5491			ZVAL_UNDEF(&chunk);
5492		}
5493	} ZEND_HASH_FOREACH_END();
5494
5495	/* Add the final chunk if there is one. */
5496	if (Z_TYPE(chunk) != IS_UNDEF) {
5497		add_next_index_zval(return_value, &chunk);
5498	}
5499}
5500/* }}} */
5501
5502/* {{{ proto array array_combine(array keys, array values)
5503   Creates an array by using the elements of the first parameter as keys and the elements of the second as the corresponding values */
5504PHP_FUNCTION(array_combine)
5505{
5506	HashTable *values, *keys;
5507	uint32_t pos_values = 0;
5508	zval *entry_keys, *entry_values;
5509	int num_keys, num_values;
5510
5511	if (zend_parse_parameters(ZEND_NUM_ARGS(), "hh", &keys, &values) == FAILURE) {
5512		return;
5513	}
5514
5515	num_keys = zend_hash_num_elements(keys);
5516	num_values = zend_hash_num_elements(values);
5517
5518	if (num_keys != num_values) {
5519		php_error_docref(NULL, E_WARNING, "Both parameters should have an equal number of elements");
5520		RETURN_FALSE;
5521	}
5522
5523	array_init_size(return_value, num_keys);
5524
5525	if (!num_keys) {
5526		return;
5527	}
5528
5529	ZEND_HASH_FOREACH_VAL(keys, entry_keys) {
5530		while (1) {
5531			if (pos_values >= values->nNumUsed) {
5532				break;
5533			} else if (Z_TYPE(values->arData[pos_values].val) != IS_UNDEF) {
5534				entry_values = &values->arData[pos_values].val;
5535				if (Z_TYPE_P(entry_keys) == IS_LONG) {
5536					entry_values = zend_hash_index_update(Z_ARRVAL_P(return_value),
5537						Z_LVAL_P(entry_keys), entry_values);
5538				} else {
5539					zend_string *key = zval_get_string(entry_keys);
5540					entry_values = zend_symtable_update(Z_ARRVAL_P(return_value),
5541						key, entry_values);
5542					zend_string_release(key);
5543				}
5544				zval_add_ref(entry_values);
5545				pos_values++;
5546				break;
5547			}
5548			pos_values++;
5549		}
5550	} ZEND_HASH_FOREACH_END();
5551}
5552/* }}} */
5553
5554/*
5555 * Local variables:
5556 * tab-width: 4
5557 * c-basic-offset: 4
5558 * End:
5559 * vim600: noet sw=4 ts=4 fdm=marker
5560 * vim<600: noet sw=4 ts=4
5561 */
5562