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