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