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