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