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