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