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