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