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