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