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