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