1/*
2   +----------------------------------------------------------------------+
3   | PHP Version 5                                                        |
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 "php_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_INT_CONSTANT("EXTR_OVERWRITE", EXTR_OVERWRITE, CONST_CS | CONST_PERSISTENT);
103    REGISTER_INT_CONSTANT("EXTR_SKIP", EXTR_SKIP, CONST_CS | CONST_PERSISTENT);
104    REGISTER_INT_CONSTANT("EXTR_PREFIX_SAME", EXTR_PREFIX_SAME, CONST_CS | CONST_PERSISTENT);
105    REGISTER_INT_CONSTANT("EXTR_PREFIX_ALL", EXTR_PREFIX_ALL, CONST_CS | CONST_PERSISTENT);
106    REGISTER_INT_CONSTANT("EXTR_PREFIX_INVALID", EXTR_PREFIX_INVALID, CONST_CS | CONST_PERSISTENT);
107    REGISTER_INT_CONSTANT("EXTR_PREFIX_IF_EXISTS", EXTR_PREFIX_IF_EXISTS, CONST_CS | CONST_PERSISTENT);
108    REGISTER_INT_CONSTANT("EXTR_IF_EXISTS", EXTR_IF_EXISTS, CONST_CS | CONST_PERSISTENT);
109    REGISTER_INT_CONSTANT("EXTR_REFS", EXTR_REFS, CONST_CS | CONST_PERSISTENT);
110
111    REGISTER_INT_CONSTANT("SORT_ASC", PHP_SORT_ASC, CONST_CS | CONST_PERSISTENT);
112    REGISTER_INT_CONSTANT("SORT_DESC", PHP_SORT_DESC, CONST_CS | CONST_PERSISTENT);
113
114    REGISTER_INT_CONSTANT("SORT_REGULAR", PHP_SORT_REGULAR, CONST_CS | CONST_PERSISTENT);
115    REGISTER_INT_CONSTANT("SORT_NUMERIC", PHP_SORT_NUMERIC, CONST_CS | CONST_PERSISTENT);
116    REGISTER_INT_CONSTANT("SORT_STRING", PHP_SORT_STRING, CONST_CS | CONST_PERSISTENT);
117    REGISTER_INT_CONSTANT("SORT_LOCALE_STRING", PHP_SORT_LOCALE_STRING, CONST_CS | CONST_PERSISTENT);
118    REGISTER_INT_CONSTANT("SORT_NATURAL", PHP_SORT_NATURAL, CONST_CS | CONST_PERSISTENT);
119    REGISTER_INT_CONSTANT("SORT_FLAG_CASE", PHP_SORT_FLAG_CASE, CONST_CS | CONST_PERSISTENT);
120
121    REGISTER_INT_CONSTANT("CASE_LOWER", CASE_LOWER, CONST_CS | CONST_PERSISTENT);
122    REGISTER_INT_CONSTANT("CASE_UPPER", CASE_UPPER, CONST_CS | CONST_PERSISTENT);
123
124    REGISTER_INT_CONSTANT("COUNT_NORMAL", COUNT_NORMAL, CONST_CS | CONST_PERSISTENT);
125    REGISTER_INT_CONSTANT("COUNT_RECURSIVE", COUNT_RECURSIVE, CONST_CS | CONST_PERSISTENT);
126
127    REGISTER_INT_CONSTANT("ARRAY_FILTER_USE_BOTH", ARRAY_FILTER_USE_BOTH, CONST_CS | CONST_PERSISTENT);
128    REGISTER_INT_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(php_int_t sort_type TSRMLS_DC) /* {{{ */
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 TSRMLS_DC) /* {{{ */
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_INT(&first, f->h);
186    } else {
187        ZVAL_STR(&first, f->key);
188    }
189
190    if (s->key == 0) {
191        ZVAL_INT(&second, s->h);
192    } else {
193        ZVAL_STR(&second, s->key);
194    }
195
196    if (ARRAYG(compare_func)(&result, &first, &second TSRMLS_CC) == FAILURE) {
197        return 0;
198    }
199
200    if (EXPECTED(Z_TYPE(result) == IS_INT)) {
201        return ZEND_NORMALIZE_BOOL(Z_IVAL(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_int(&result));
207}
208/* }}} */
209
210static int php_array_reverse_key_compare(const void *a, const void *b TSRMLS_DC) /* {{{ */
211{
212    return php_array_key_compare(a, b TSRMLS_CC) * -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    php_int_t sort_type = PHP_SORT_REGULAR;
222
223    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a/|i", &array, &sort_type) == FAILURE) {
224        RETURN_FALSE;
225    }
226
227    php_set_compare_func(sort_type TSRMLS_CC);
228
229    if (zend_hash_sort(Z_ARRVAL_P(array), zend_qsort, php_array_reverse_key_compare, 0 TSRMLS_CC) == 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    php_int_t sort_type = PHP_SORT_REGULAR;
242
243    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a/|i", &array, &sort_type) == FAILURE) {
244        RETURN_FALSE;
245    }
246
247    php_set_compare_func(sort_type TSRMLS_CC);
248
249    if (zend_hash_sort(Z_ARRVAL_P(array), zend_qsort, php_array_key_compare, 0 TSRMLS_CC) == FAILURE) {
250        RETURN_FALSE;
251    }
252    RETURN_TRUE;
253}
254/* }}} */
255
256PHPAPI php_int_t php_count_recursive(zval *array, php_int_t mode TSRMLS_DC) /* {{{ */
257{
258    php_int_t 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 TSRMLS_CC, 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 TSRMLS_CC);
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    php_int_t mode = COUNT_NORMAL;
292    php_int_t cnt;
293    zval *element;
294
295#ifndef FAST_ZPP
296    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "z|i", &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_INT(mode)
304    ZEND_PARSE_PARAMETERS_END();
305#endif
306
307    switch (Z_TYPE_P(array)) {
308        case IS_NULL:
309            RETURN_INT(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 TSRMLS_CC);
317                } ZEND_HASH_FOREACH_END();
318            }
319            RETURN_INT(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_INT(1);
328                if (SUCCESS == Z_OBJ_HT(*array)->count_elements(array, &Z_IVAL_P(return_value) TSRMLS_CC)) {
329                    return;
330                }
331            }
332#ifdef HAVE_SPL
333            /* if not and the object implements Countable we call its count() method */
334            if (Z_OBJ_HT_P(array)->get_class_entry && instanceof_function(Z_OBJCE_P(array), spl_ce_Countable TSRMLS_CC)) {
335                zend_call_method_with_0_params(array, NULL, NULL, "count", &retval);
336                if (Z_TYPE(retval) != IS_UNDEF) {
337                    RETVAL_INT(zval_get_int(&retval));
338                    zval_ptr_dtor(&retval);
339                }
340                return;
341            }
342#endif
343        }
344        default:
345            RETURN_INT(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 TSRMLS_DC) /* {{{ */
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 TSRMLS_CC) == FAILURE) {
378        return 0;
379    }
380
381    if (EXPECTED(Z_TYPE(result) == IS_INT)) {
382        return ZEND_NORMALIZE_BOOL(Z_IVAL(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_int(&result));
388}
389/* }}} */
390
391static int php_array_reverse_data_compare(const void *a, const void *b TSRMLS_DC) /* {{{ */
392{
393    return php_array_data_compare(a, b TSRMLS_CC) * -1;
394}
395/* }}} */
396
397static int php_array_natural_general_compare(const void *a, const void *b, int fold_case TSRMLS_DC) /* {{{ */
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    STR_RELEASE(str1);
407    STR_RELEASE(str2);
408    return result;
409}
410/* }}} */
411
412static int php_array_natural_compare(const void *a, const void *b TSRMLS_DC) /* {{{ */
413{
414    return php_array_natural_general_compare(a, b, 0 TSRMLS_CC);
415}
416/* }}} */
417
418static int php_array_natural_case_compare(const void *a, const void *b TSRMLS_DC) /* {{{ */
419{
420    return php_array_natural_general_compare(a, b, 1 TSRMLS_CC);
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() TSRMLS_CC, "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 TSRMLS_CC) == FAILURE) {
434            return;
435        }
436    } else {
437        if (zend_hash_sort(Z_ARRVAL_P(array), zend_qsort, php_array_natural_compare, 0 TSRMLS_CC) == 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    php_int_t sort_type = PHP_SORT_REGULAR;
468
469    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a/|i", &array, &sort_type) == FAILURE) {
470        RETURN_FALSE;
471    }
472
473    php_set_compare_func(sort_type TSRMLS_CC);
474
475    if (zend_hash_sort(Z_ARRVAL_P(array), zend_qsort, php_array_data_compare, 0 TSRMLS_CC) == 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    php_int_t sort_type = PHP_SORT_REGULAR;
488
489    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a/|i", &array, &sort_type) == FAILURE) {
490        RETURN_FALSE;
491    }
492
493    php_set_compare_func(sort_type TSRMLS_CC);
494
495    if (zend_hash_sort(Z_ARRVAL_P(array), zend_qsort, php_array_reverse_data_compare, 0 TSRMLS_CC) == 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    php_int_t sort_type = PHP_SORT_REGULAR;
508
509    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a/|i", &array, &sort_type) == FAILURE) {
510        RETURN_FALSE;
511    }
512
513    php_set_compare_func(sort_type TSRMLS_CC);
514
515    if (zend_hash_sort(Z_ARRVAL_P(array), zend_qsort, php_array_data_compare, 1 TSRMLS_CC) == 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    php_int_t sort_type = PHP_SORT_REGULAR;
528
529    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a/|i", &array, &sort_type) == FAILURE) {
530        RETURN_FALSE;
531    }
532
533    php_set_compare_func(sort_type TSRMLS_CC);
534
535    if (zend_hash_sort(Z_ARRVAL_P(array), zend_qsort, php_array_reverse_data_compare, 1 TSRMLS_CC) == FAILURE) {
536        RETURN_FALSE;
537    }
538    RETURN_TRUE;
539}
540/* }}} */
541
542static int php_array_user_compare(const void *a, const void *b TSRMLS_DC) /* {{{ */
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) TSRMLS_CC) == SUCCESS && Z_TYPE(retval) != IS_UNDEF) {
560        php_int_t ret = zval_get_int(&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 TSRMLS_CC)) { \
576        php_error_docref(NULL TSRMLS_CC, 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() TSRMLS_CC, "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 attemts 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 TSRMLS_CC) == FAILURE) {
629        RETVAL_FALSE;
630    } else {
631        if (refcount > Z_REFCOUNT_P(array)) {
632            php_error_docref(NULL TSRMLS_CC, 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() TSRMLS_CC, "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 attemts 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 TSRMLS_CC) == FAILURE) {
674        RETVAL_FALSE;
675    } else {
676        if (refcount > Z_REFCOUNT_P(array)) {
677            php_error_docref(NULL TSRMLS_CC, 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 TSRMLS_DC) /* {{{ */
693{
694    Bucket *f;
695    Bucket *s;
696    zval args[2];
697    zval retval;
698    php_int_t 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_INT(&args[0], f->h);
708    } else {
709        ZVAL_STR(&args[0], STR_COPY(f->key));
710    }
711    if (s->key == NULL) {
712        ZVAL_INT(&args[1], s->h);
713    } else {
714        ZVAL_STR(&args[1], STR_COPY(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) TSRMLS_CC) == SUCCESS && Z_TYPE(retval) != IS_UNDEF) {
722        result = zval_get_int(&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;
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() TSRMLS_CC, "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 attemts 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 TSRMLS_CC) == FAILURE) {
762        RETVAL_FALSE;
763    } else {
764        if (refcount > Z_REFCOUNT_P(array)) {
765            php_error_docref(NULL TSRMLS_CC, 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() TSRMLS_CC, "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() TSRMLS_CC, "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() TSRMLS_CC, "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() TSRMLS_CC, "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() TSRMLS_CC, "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() TSRMLS_CC, "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() TSRMLS_CC, "+", &args, &argc) == FAILURE) {
969        return;
970    }
971
972    php_set_compare_func(PHP_SORT_REGULAR TSRMLS_CC);
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 TSRMLS_CC, 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 TSRMLS_CC)) != NULL) {
983                RETVAL_ZVAL_FAST(result);
984            } else {
985                php_error_docref(NULL TSRMLS_CC, 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 TSRMLS_CC);
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() TSRMLS_CC, "+", &args, &argc) == FAILURE) {
1016        return;
1017    }
1018
1019    php_set_compare_func(PHP_SORT_REGULAR TSRMLS_CC);
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 TSRMLS_CC, 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 TSRMLS_CC)) != NULL) {
1030                RETVAL_ZVAL_FAST(result);
1031            } else {
1032                php_error_docref(NULL TSRMLS_CC, 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 TSRMLS_CC);
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 TSRMLS_DC) /* {{{ */
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 TSRMLS_CC, 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 TSRMLS_CC);
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) TSRMLS_CC) == 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() TSRMLS_CC, "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 TSRMLS_CC);
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() TSRMLS_CC, "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 TSRMLS_CC);
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 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          res;                  /* comparison result */
1233    php_uint_t num_idx;
1234    zend_string *str_idx;
1235    zend_bool strict = 0;       /* strict comparison or not */
1236
1237#ifndef FAST_ZPP
1238    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "za|b", &value, &array, &strict) == FAILURE) {
1239        return;
1240    }
1241#else
1242    ZEND_PARSE_PARAMETERS_START(2, 3)
1243        Z_PARAM_ZVAL(value)
1244        Z_PARAM_ARRAY(array)
1245        Z_PARAM_OPTIONAL
1246        Z_PARAM_BOOL(strict)
1247    ZEND_PARSE_PARAMETERS_END();
1248#endif
1249
1250    if (strict) {
1251        ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {
1252            ZVAL_DEREF(entry);
1253            is_identical_function(&res, value, entry TSRMLS_CC);
1254            if (Z_TYPE(res) == IS_TRUE) {
1255                if (behavior == 0) {
1256                    RETURN_TRUE;
1257                } else {
1258                    if (str_idx) {
1259                        RETVAL_STR(STR_COPY(str_idx));
1260                    } else {
1261                        RETVAL_INT(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(&res, value, entry TSRMLS_CC)) {
1270                if (behavior == 0) {
1271                    RETURN_TRUE;
1272                } else {
1273                    if (str_idx) {
1274                        RETVAL_STR(STR_COPY(str_idx));
1275                    } else {
1276                        RETVAL_INT(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, int var_name_len) /* {{{ */
1305{
1306    int i, ch;
1307
1308    if (!var_name || !var_name_len) {
1309        return 0;
1310    }
1311
1312    /* These are allowed as first char: [a-zA-Z_\x7f-\xff] */
1313    ch = (int)((unsigned char *)var_name)[0];
1314    if (var_name[0] != '_' &&
1315        (ch < 65  /* A    */ || /* Z    */ ch > 90)  &&
1316        (ch < 97  /* a    */ || /* z    */ ch > 122) &&
1317        (ch < 127 /* 0x7f */ || /* 0xff */ ch > 255)
1318    ) {
1319        return 0;
1320    }
1321
1322    /* And these as the rest: [a-zA-Z0-9_\x7f-\xff] */
1323    if (var_name_len > 1) {
1324        for (i = 1; i < var_name_len; i++) {
1325            ch = (int)((unsigned char *)var_name)[i];
1326            if (var_name[i] != '_' &&
1327                (ch < 48  /* 0    */ || /* 9    */ ch > 57)  &&
1328                (ch < 65  /* A    */ || /* Z    */ ch > 90)  &&
1329                (ch < 97  /* a    */ || /* z    */ ch > 122) &&
1330                (ch < 127 /* 0x7f */ || /* 0xff */ ch > 255)
1331            ) {
1332                return 0;
1333            }
1334        }
1335    }
1336    return 1;
1337}
1338/* }}} */
1339
1340PHPAPI int php_prefix_varname(zval *result, zval *prefix, char *var_name, int var_name_len, zend_bool add_underscore TSRMLS_DC) /* {{{ */
1341{
1342    ZVAL_NEW_STR(result, STR_ALLOC(Z_STRSIZE_P(prefix) + (add_underscore ? 1 : 0) + var_name_len, 0));
1343    memcpy(Z_STRVAL_P(result), Z_STRVAL_P(prefix), Z_STRSIZE_P(prefix));
1344
1345    if (add_underscore) {
1346        Z_STRVAL_P(result)[Z_STRSIZE_P(prefix)] = '_';
1347    }
1348
1349    memcpy(Z_STRVAL_P(result) + Z_STRSIZE_P(prefix) + (add_underscore ? 1 : 0), var_name, var_name_len + 1);
1350
1351    return SUCCESS;
1352}
1353/* }}} */
1354
1355/* {{{ proto int extract(array var_array [, int extract_type [, string prefix]])
1356   Imports variables into symbol table from an array */
1357PHP_FUNCTION(extract)
1358{
1359    zval *var_array, *prefix = NULL;
1360    php_int_t extract_type = EXTR_OVERWRITE;
1361    zval *entry;
1362    zend_string *var_name;
1363    php_uint_t num_key;
1364    int var_exists, count = 0;
1365    int extract_refs = 0;
1366    zend_array *symbol_table;
1367
1368    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a/|iz/", &var_array, &extract_type, &prefix) == FAILURE) {
1369        return;
1370    }
1371
1372    extract_refs = (extract_type & EXTR_REFS);
1373    extract_type &= 0xff;
1374
1375    if (extract_type < EXTR_OVERWRITE || extract_type > EXTR_IF_EXISTS) {
1376        php_error_docref(NULL TSRMLS_CC, E_WARNING, "Invalid extract type");
1377        return;
1378    }
1379
1380    if (extract_type > EXTR_SKIP && extract_type <= EXTR_PREFIX_IF_EXISTS && ZEND_NUM_ARGS() < 3) {
1381        php_error_docref(NULL TSRMLS_CC, E_WARNING, "specified extract type requires the prefix parameter");
1382        return;
1383    }
1384
1385    if (prefix) {
1386        convert_to_string(prefix);
1387        if (Z_STRSIZE_P(prefix) && !php_valid_var_name(Z_STRVAL_P(prefix), Z_STRSIZE_P(prefix))) {
1388            php_error_docref(NULL TSRMLS_CC, E_WARNING, "prefix is not a valid identifier");
1389            return;
1390        }
1391    }
1392
1393    symbol_table = zend_rebuild_symbol_table(TSRMLS_C);
1394
1395    ZEND_HASH_FOREACH_KEY_VAL_IND(Z_ARRVAL_P(var_array), num_key, var_name, entry) {
1396        zval final_name;
1397
1398        ZVAL_NULL(&final_name);
1399        var_exists = 0;
1400
1401        if (var_name) {
1402            var_exists = zend_hash_exists_ind(&symbol_table->ht, var_name);
1403        } else if (extract_type == EXTR_PREFIX_ALL || extract_type == EXTR_PREFIX_INVALID) {
1404            zval num;
1405
1406            ZVAL_INT(&num, num_key);
1407            convert_to_string(&num);
1408            php_prefix_varname(&final_name, prefix, Z_STRVAL(num), Z_STRSIZE(num), 1 TSRMLS_CC);
1409            zval_dtor(&num);
1410        } else {
1411            continue;
1412        }
1413
1414        switch (extract_type) {
1415            case EXTR_IF_EXISTS:
1416                if (!var_exists) break;
1417                /* break omitted intentionally */
1418
1419            case EXTR_OVERWRITE:
1420                /* GLOBALS protection */
1421                if (var_exists && var_name->len == sizeof("GLOBALS")-1 && !strcmp(var_name->val, "GLOBALS")) {
1422                    break;
1423                }
1424                if (var_exists && var_name->len == sizeof("this")-1  && !strcmp(var_name->val, "this") && EG(scope) && EG(scope)->name->len != 0) {
1425                    break;
1426                }
1427                ZVAL_STR(&final_name, STR_COPY(var_name));
1428                break;
1429
1430            case EXTR_PREFIX_IF_EXISTS:
1431                if (var_exists) {
1432                    php_prefix_varname(&final_name, prefix, var_name->val, var_name->len, 1 TSRMLS_CC);
1433                }
1434                break;
1435
1436            case EXTR_PREFIX_SAME:
1437                if (!var_exists && var_name->len != 0) {
1438                    ZVAL_STR(&final_name, STR_COPY(var_name));
1439                }
1440                /* break omitted intentionally */
1441
1442            case EXTR_PREFIX_ALL:
1443                if (Z_TYPE(final_name) == IS_NULL && var_name->len != 0) {
1444                    php_prefix_varname(&final_name, prefix, var_name->val, var_name->len, 1 TSRMLS_CC);
1445                }
1446                break;
1447
1448            case EXTR_PREFIX_INVALID:
1449                if (Z_TYPE(final_name) == IS_NULL) {
1450                    if (!php_valid_var_name(var_name->val, var_name->len)) {
1451                        php_prefix_varname(&final_name, prefix, var_name->val, var_name->len, 1 TSRMLS_CC);
1452                    } else {
1453                        ZVAL_STR(&final_name, STR_COPY(var_name));
1454                    }
1455                }
1456                break;
1457
1458            default:
1459                if (!var_exists) {
1460                    ZVAL_STR(&final_name, STR_COPY(var_name));
1461                }
1462                break;
1463        }
1464
1465        if (Z_TYPE(final_name) != IS_NULL && php_valid_var_name(Z_STRVAL(final_name), Z_STRSIZE(final_name))) {
1466            if (extract_refs) {
1467                zval *orig_var;
1468
1469                ZVAL_MAKE_REF(entry);
1470                Z_ADDREF_P(entry);
1471
1472                if ((orig_var = zend_hash_find(&symbol_table->ht, Z_STR(final_name))) != NULL) {
1473                    if (Z_TYPE_P(orig_var) == IS_INDIRECT) {
1474                        orig_var = Z_INDIRECT_P(orig_var);
1475                    }
1476                    zval_ptr_dtor(orig_var);
1477                    ZVAL_COPY_VALUE(orig_var, entry);
1478                } else {
1479                    zend_hash_update(&symbol_table->ht, Z_STR(final_name), entry);
1480                }
1481            } else {
1482                if (Z_REFCOUNTED_P(entry)) Z_ADDREF_P(entry);
1483                zend_set_local_var(Z_STR(final_name), entry, 1 TSRMLS_CC);
1484            }
1485            count++;
1486        }
1487        zval_dtor(&final_name);
1488    } ZEND_HASH_FOREACH_END();
1489
1490    RETURN_INT(count);
1491}
1492/* }}} */
1493
1494static void php_compact_var(HashTable *eg_active_symbol_table, zval *return_value, zval *entry TSRMLS_DC) /* {{{ */
1495{
1496    zval *value_ptr, data;
1497
1498    ZVAL_DEREF(entry);
1499    if (Z_TYPE_P(entry) == IS_STRING) {
1500        if ((value_ptr = zend_hash_find_ind(eg_active_symbol_table, Z_STR_P(entry))) != NULL) {
1501            ZVAL_DUP(&data, value_ptr);
1502            zend_hash_update(Z_ARRVAL_P(return_value), Z_STR_P(entry), &data);
1503        }
1504    } else if (Z_TYPE_P(entry) == IS_ARRAY) {
1505        if ((Z_ARRVAL_P(entry)->u.v.nApplyCount > 1)) {
1506            php_error_docref(NULL TSRMLS_CC, E_WARNING, "recursion detected");
1507            return;
1508        }
1509
1510        if (ZEND_HASH_APPLY_PROTECTION(Z_ARRVAL_P(entry))) {
1511            Z_ARRVAL_P(entry)->u.v.nApplyCount++;
1512        }
1513        ZEND_HASH_FOREACH_VAL_IND(Z_ARRVAL_P(entry), value_ptr) {
1514            php_compact_var(eg_active_symbol_table, return_value, value_ptr TSRMLS_CC);
1515        } ZEND_HASH_FOREACH_END();
1516        if (ZEND_HASH_APPLY_PROTECTION(Z_ARRVAL_P(entry))) {
1517            Z_ARRVAL_P(entry)->u.v.nApplyCount--;
1518        }
1519    }
1520}
1521/* }}} */
1522
1523/* {{{ proto array compact(mixed var_names [, mixed ...])
1524   Creates a hash containing variables and their values */
1525PHP_FUNCTION(compact)
1526{
1527    zval *args = NULL;  /* function arguments array */
1528    int num_args, i;
1529    zend_array *symbol_table;
1530
1531    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "+", &args, &num_args) == FAILURE) {
1532        return;
1533    }
1534
1535    symbol_table = zend_rebuild_symbol_table(TSRMLS_C);
1536
1537    /* compact() is probably most used with a single array of var_names
1538       or multiple string names, rather than a combination of both.
1539       So quickly guess a minimum result size based on that */
1540    if (ZEND_NUM_ARGS() == 1 && Z_TYPE(args[0]) == IS_ARRAY) {
1541        array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL(args[0])));
1542    } else {
1543        array_init_size(return_value, ZEND_NUM_ARGS());
1544    }
1545
1546    for (i=0; i<ZEND_NUM_ARGS(); i++) {
1547        php_compact_var(&symbol_table->ht, return_value, &args[i] TSRMLS_CC);
1548    }
1549}
1550/* }}} */
1551
1552/* {{{ proto array array_fill(int start_key, int num, mixed val)
1553   Create an array containing num elements starting with index start_key each initialized to val */
1554PHP_FUNCTION(array_fill)
1555{
1556    zval *val;
1557    php_int_t start_key, num;
1558
1559    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "iiz", &start_key, &num, &val) == FAILURE) {
1560        return;
1561    }
1562
1563    if (num < 0) {
1564        php_error_docref(NULL TSRMLS_CC, E_WARNING, "Number of elements can't be negative");
1565        RETURN_FALSE;
1566    }
1567
1568    /* allocate an array for return */
1569    array_init_size(return_value, num);
1570
1571    if (num == 0) {
1572        return;
1573    }
1574
1575    num--;
1576    zend_hash_index_update(Z_ARRVAL_P(return_value), start_key, val);
1577    zval_add_ref(val);
1578
1579    while (num--) {
1580        if (zend_hash_next_index_insert(Z_ARRVAL_P(return_value), val) != NULL) {
1581            zval_add_ref(val);
1582        } else {
1583            zval_dtor(return_value);
1584            php_error_docref(NULL TSRMLS_CC, E_WARNING, "Cannot add element to the array as the next element is already occupied");
1585            RETURN_FALSE;
1586        }
1587    }
1588}
1589/* }}} */
1590
1591/* {{{ proto array array_fill_keys(array keys, mixed val)
1592   Create an array using the elements of the first parameter as keys each initialized to val */
1593PHP_FUNCTION(array_fill_keys)
1594{
1595    zval *keys, *val, *entry;
1596
1597    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "az", &keys, &val) == FAILURE) {
1598        return;
1599    }
1600
1601    /* Initialize return array */
1602    array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(keys)));
1603
1604    ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(keys), entry) {
1605        ZVAL_DEREF(entry);
1606        if (Z_TYPE_P(entry) == IS_INT) {
1607            zval_add_ref(val);
1608            zend_hash_index_update(Z_ARRVAL_P(return_value), Z_IVAL_P(entry), val);
1609        } else {
1610            zend_string *key = zval_get_string(entry);
1611
1612            zval_add_ref(val);
1613            zend_symtable_update(Z_ARRVAL_P(return_value), key, val);
1614
1615            STR_RELEASE(key);
1616        }
1617    } ZEND_HASH_FOREACH_END();
1618}
1619/* }}} */
1620
1621/* {{{ proto array range(mixed low, mixed high[, int step])
1622   Create an array containing the range of integers or characters from low to high (inclusive) */
1623PHP_FUNCTION(range)
1624{
1625    zval *zlow, *zhigh, *zstep = NULL, tmp;
1626    int err = 0, is_step_double = 0;
1627    double step = 1.0;
1628
1629    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zz|z", &zlow, &zhigh, &zstep) == FAILURE) {
1630        RETURN_FALSE;
1631    }
1632
1633    if (zstep) {
1634        if (Z_TYPE_P(zstep) == IS_DOUBLE ||
1635            (Z_TYPE_P(zstep) == IS_STRING && is_numeric_string(Z_STRVAL_P(zstep), Z_STRSIZE_P(zstep), NULL, NULL, 0) == IS_DOUBLE)
1636        ) {
1637            is_step_double = 1;
1638        }
1639
1640        step = zval_get_double(zstep);
1641
1642        /* We only want positive step values. */
1643        if (step < 0.0) {
1644            step *= -1;
1645        }
1646    }
1647
1648    /* Initialize the return_value as an array. */
1649    array_init(return_value);
1650
1651    /* If the range is given as strings, generate an array of characters. */
1652    if (Z_TYPE_P(zlow) == IS_STRING && Z_TYPE_P(zhigh) == IS_STRING && Z_STRSIZE_P(zlow) >= 1 && Z_STRSIZE_P(zhigh) >= 1) {
1653        int type1, type2;
1654        unsigned char low, high;
1655        php_int_t lstep = (php_int_t) step;
1656
1657        type1 = is_numeric_string(Z_STRVAL_P(zlow), Z_STRSIZE_P(zlow), NULL, NULL, 0);
1658        type2 = is_numeric_string(Z_STRVAL_P(zhigh), Z_STRSIZE_P(zhigh), NULL, NULL, 0);
1659
1660        if (type1 == IS_DOUBLE || type2 == IS_DOUBLE || is_step_double) {
1661            goto double_str;
1662        } else if (type1 == IS_INT || type2 == IS_INT) {
1663            goto long_str;
1664        }
1665
1666        low = (unsigned char)Z_STRVAL_P(zlow)[0];
1667        high = (unsigned char)Z_STRVAL_P(zhigh)[0];
1668
1669        if (low > high) {       /* Negative Steps */
1670            if (lstep <= 0) {
1671                err = 1;
1672                goto err;
1673            }
1674            for (; low >= high; low -= (unsigned int)lstep) {
1675                if (CG(one_char_string)[low]) {
1676                    ZVAL_INT_STR(&tmp, CG(one_char_string)[low]);
1677                } else {
1678                    ZVAL_STRINGL(&tmp, (char*)&low, 1);
1679                }
1680                zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &tmp);
1681                if (((signed int)low - lstep) < 0) {
1682                    break;
1683                }
1684            }
1685        } else if (high > low) {    /* Positive Steps */
1686            if (lstep <= 0) {
1687                err = 1;
1688                goto err;
1689            }
1690            for (; low <= high; low += (unsigned int)lstep) {
1691                if (CG(one_char_string)[low]) {
1692                    ZVAL_INT_STR(&tmp, CG(one_char_string)[low]);
1693                } else {
1694                    ZVAL_STRINGL(&tmp, (char*)&low, 1);
1695                }
1696                zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &tmp);
1697                if (((signed int)low + lstep) > 255) {
1698                    break;
1699                }
1700            }
1701        } else {
1702            if (CG(one_char_string)[low]) {
1703                ZVAL_INT_STR(&tmp, CG(one_char_string)[low]);
1704            } else {
1705                ZVAL_STRINGL(&tmp, (char*)&low, 1);
1706            }
1707            zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &tmp);
1708        }
1709
1710    } else if (Z_TYPE_P(zlow) == IS_DOUBLE || Z_TYPE_P(zhigh) == IS_DOUBLE || is_step_double) {
1711        double low, high, value;
1712        php_int_t i;
1713double_str:
1714        low = zval_get_double(zlow);
1715        high = zval_get_double(zhigh);
1716        i = 0;
1717
1718        Z_TYPE_INFO(tmp) = IS_DOUBLE;
1719        if (low > high) {       /* Negative steps */
1720            if (low - high < step || step <= 0) {
1721                err = 1;
1722                goto err;
1723            }
1724
1725            for (value = low; value >= (high - DOUBLE_DRIFT_FIX); value = low - (++i * step)) {
1726                Z_DVAL(tmp) = value;
1727                zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &tmp);
1728            }
1729        } else if (high > low) {    /* Positive steps */
1730            if (high - low < step || step <= 0) {
1731                err = 1;
1732                goto err;
1733            }
1734
1735            for (value = low; value <= (high + DOUBLE_DRIFT_FIX); value = low + (++i * step)) {
1736                Z_DVAL(tmp) = value;
1737                zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &tmp);
1738            }
1739        } else {
1740            Z_DVAL(tmp) = low;
1741            zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &tmp);
1742        }
1743    } else {
1744        double low, high;
1745        php_int_t lstep;
1746long_str:
1747        low = zval_get_double(zlow);
1748        high = zval_get_double(zhigh);
1749        lstep = (php_int_t) step;
1750
1751        Z_TYPE_INFO(tmp) = IS_INT;
1752        if (low > high) {       /* Negative steps */
1753            if (low - high < lstep || lstep <= 0) {
1754                err = 1;
1755                goto err;
1756            }
1757            for (; low >= high; low -= lstep) {
1758                Z_IVAL(tmp) = (php_int_t)low;
1759                zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &tmp);
1760            }
1761        } else if (high > low) {    /* Positive steps */
1762            if (high - low < lstep || lstep <= 0) {
1763                err = 1;
1764                goto err;
1765            }
1766            for (; low <= high; low += lstep) {
1767                Z_IVAL(tmp) = (php_int_t)low;
1768                zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &tmp);
1769            }
1770        } else {
1771            Z_IVAL(tmp) = (php_int_t)low;
1772            zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &tmp);
1773        }
1774    }
1775err:
1776    if (err) {
1777        php_error_docref(NULL TSRMLS_CC, E_WARNING, "step exceeds the specified range");
1778        zval_dtor(return_value);
1779        RETURN_FALSE;
1780    }
1781}
1782/* }}} */
1783
1784static void php_array_data_shuffle(zval *array TSRMLS_DC) /* {{{ */
1785{
1786    uint idx;
1787    Bucket *p, temp;
1788    HashTable *hash;
1789    int j, n_elems, rnd_idx, n_left;
1790
1791    n_elems = zend_hash_num_elements(Z_ARRVAL_P(array));
1792
1793    if (n_elems < 1) {
1794        return;
1795    }
1796
1797    hash = Z_ARRVAL_P(array);
1798    n_left = n_elems;
1799
1800    if (hash->nNumUsed != hash->nNumOfElements) {
1801        for (j = 0, idx = 0; idx < hash->nNumUsed; idx++) {
1802            p = hash->arData + idx;
1803            if (Z_TYPE(p->val) == IS_UNDEF) continue;
1804            if (j != idx) {
1805                hash->arData[j] = *p;
1806            }
1807            j++;
1808        }
1809    }
1810    while (--n_left) {
1811        rnd_idx = php_rand(TSRMLS_C);
1812        RAND_RANGE(rnd_idx, 0, n_left, PHP_RAND_MAX);
1813        if (rnd_idx != n_left) {
1814            temp = hash->arData[n_left];
1815            hash->arData[n_left] = hash->arData[rnd_idx];
1816            hash->arData[rnd_idx] = temp;
1817        }
1818    }
1819
1820    HANDLE_BLOCK_INTERRUPTIONS();
1821    hash->nNumUsed = n_elems;
1822    hash->nInternalPointer = 0;
1823
1824    for (j = 0; j < n_elems; j++) {
1825        p = hash->arData + j;
1826        if (p->key && !IS_INTERNED(p->key)) {
1827            STR_RELEASE(p->key);
1828        }
1829        p->h = j;
1830        p->key = NULL;
1831    }
1832    hash->nNextFreeElement = n_elems;
1833    if (!(hash->u.flags & HASH_FLAG_PACKED)) {
1834        zend_hash_to_packed(hash);
1835    }
1836    HANDLE_UNBLOCK_INTERRUPTIONS();
1837}
1838/* }}} */
1839
1840/* {{{ proto bool shuffle(array array_arg)
1841   Randomly shuffle the contents of an array */
1842PHP_FUNCTION(shuffle)
1843{
1844    zval *array;
1845
1846    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a/", &array) == FAILURE) {
1847        RETURN_FALSE;
1848    }
1849
1850    php_array_data_shuffle(array TSRMLS_CC);
1851
1852    RETURN_TRUE;
1853}
1854/* }}} */
1855
1856PHPAPI HashTable* php_splice(HashTable *in_hash, int offset, int length, zval *list, int list_count, HashTable *removed) /* {{{ */
1857{
1858    HashTable   *out_hash = NULL;   /* Output hashtable */
1859    int          num_in,            /* Number of entries in the input hashtable */
1860                 pos,               /* Current position in the hashtable */
1861                 i;                 /* Loop counter */
1862    uint         idx;
1863    Bucket      *p;                 /* Pointer to hash bucket */
1864    zval        *entry;             /* Hash entry */
1865
1866    /* If input hash doesn't exist, we have nothing to do */
1867    if (!in_hash) {
1868        return NULL;
1869    }
1870
1871    /* Get number of entries in the input hash */
1872    num_in = zend_hash_num_elements(in_hash);
1873
1874    /* Clamp the offset.. */
1875    if (offset > num_in) {
1876        offset = num_in;
1877    } else if (offset < 0 && (offset = (num_in + offset)) < 0) {
1878        offset = 0;
1879    }
1880
1881    /* ..and the length */
1882    if (length < 0) {
1883        length = num_in - offset + length;
1884    } else if (((unsigned)offset + (unsigned)length) > (unsigned)num_in) {
1885        length = num_in - offset;
1886    }
1887
1888    /* Create and initialize output hash */
1889    ALLOC_HASHTABLE(out_hash);
1890    zend_hash_init(out_hash, (length > 0 ? num_in - length : 0) + list_count, NULL, ZVAL_PTR_DTOR, 0);
1891
1892    /* Start at the beginning of the input hash and copy entries to output hash until offset is reached */
1893    for (pos = 0, idx = 0; pos < offset && idx < in_hash->nNumUsed; idx++) {
1894        p = in_hash->arData + idx;
1895        if (Z_TYPE(p->val) == IS_UNDEF) continue;
1896        pos++;
1897        /* Get entry and increase reference count */
1898        entry = &p->val;
1899        if (Z_REFCOUNTED_P(entry)) {
1900            Z_ADDREF_P(entry);
1901        }
1902
1903        /* Update output hash depending on key type */
1904        if (p->key == NULL) {
1905            zend_hash_next_index_insert(out_hash, entry);
1906        } else {
1907            zend_hash_update(out_hash, p->key, entry);
1908        }
1909    }
1910
1911    /* If hash for removed entries exists, go until offset+length and copy the entries to it */
1912    if (removed != NULL) {
1913        for ( ; pos < offset + length && idx < in_hash->nNumUsed; idx++) {
1914            p = in_hash->arData + idx;
1915            if (Z_TYPE(p->val) == IS_UNDEF) continue;
1916            pos++;
1917            entry = &p->val;
1918            if (Z_REFCOUNTED_P(entry)) {
1919                Z_ADDREF_P(entry);
1920            }
1921            if (p->key == NULL) {
1922                zend_hash_next_index_insert(removed, entry);
1923            } else {
1924                zend_hash_update(removed, p->key, entry);
1925            }
1926        }
1927    } else { /* otherwise just skip those entries */
1928        for ( ; pos < offset + length && idx < in_hash->nNumUsed; pos++, idx++);
1929    }
1930
1931    /* If there are entries to insert.. */
1932    if (list != NULL) {
1933        /* ..for each one, create a new zval, copy entry into it and copy it into the output hash */
1934        for (i = 0; i < list_count; i++) {
1935            entry = &list[i];
1936            if (Z_REFCOUNTED_P(entry)) Z_ADDREF_P(entry);
1937            zend_hash_next_index_insert(out_hash, entry);
1938        }
1939    }
1940
1941    /* Copy the remaining input hash entries to the output hash */
1942    for ( ; idx < in_hash->nNumUsed ; idx++) {
1943        p = in_hash->arData + idx;
1944        if (Z_TYPE(p->val) == IS_UNDEF) continue;
1945        entry = &p->val;
1946        if (Z_REFCOUNTED_P(entry)) {
1947            Z_ADDREF_P(entry);
1948        }
1949        if (p->key == NULL) {
1950            zend_hash_next_index_insert(out_hash, entry);
1951        } else {
1952            zend_hash_update(out_hash, p->key, entry);
1953        }
1954    }
1955
1956    zend_hash_internal_pointer_reset(out_hash);
1957    return out_hash;
1958}
1959/* }}} */
1960
1961/* {{{ proto int array_push(array stack, mixed var [, mixed ...])
1962   Pushes elements onto the end of the array */
1963PHP_FUNCTION(array_push)
1964{
1965    zval   *args,       /* Function arguments array */
1966           *stack,      /* Input array */
1967            new_var;    /* Variable to be pushed */
1968    int i,              /* Loop counter */
1969        argc;           /* Number of function arguments */
1970
1971
1972    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a/+", &stack, &args, &argc) == FAILURE) {
1973        return;
1974    }
1975
1976    /* For each subsequent argument, make it a reference, increase refcount, and add it to the end of the array */
1977    for (i = 0; i < argc; i++) {
1978        ZVAL_COPY(&new_var, &args[i]);
1979
1980        if (zend_hash_next_index_insert(Z_ARRVAL_P(stack), &new_var) == NULL) {
1981            if (Z_REFCOUNTED(new_var)) Z_DELREF(new_var);
1982            php_error_docref(NULL TSRMLS_CC, E_WARNING, "Cannot add element to the array as the next element is already occupied");
1983            RETURN_FALSE;
1984        }
1985    }
1986
1987    /* Clean up and return the number of values in the stack */
1988    RETVAL_INT(zend_hash_num_elements(Z_ARRVAL_P(stack)));
1989}
1990/* }}} */
1991
1992/* {{{ void _phpi_pop(INTERNAL_FUNCTION_PARAMETERS, int off_the_end) */
1993static void _phpi_pop(INTERNAL_FUNCTION_PARAMETERS, int off_the_end)
1994{
1995    zval *stack,    /* Input stack */
1996         *val;      /* Value to be popped */
1997    zend_string *key = NULL;
1998    php_uint_t index;
1999
2000#ifndef FAST_ZPP
2001    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a/", &stack) == FAILURE) {
2002        return;
2003    }
2004#else
2005    ZEND_PARSE_PARAMETERS_START(1, 1)
2006        Z_PARAM_ARRAY_EX(stack, 0, 1)
2007    ZEND_PARSE_PARAMETERS_END();
2008#endif
2009
2010    if (zend_hash_num_elements(Z_ARRVAL_P(stack)) == 0) {
2011        return;
2012    }
2013
2014    /* Get the first or last value and copy it into the return value */
2015    if (off_the_end) {
2016        zend_hash_internal_pointer_end(Z_ARRVAL_P(stack));
2017        while (1) {
2018            val = zend_hash_get_current_data(Z_ARRVAL_P(stack));
2019            if (!val) {
2020                return;
2021            } else if (Z_TYPE_P(val) == IS_INDIRECT) {
2022                val = Z_INDIRECT_P(val);
2023                if (Z_TYPE_P(val) == IS_UNDEF) {
2024                    zend_hash_move_backwards(Z_ARRVAL_P(stack));
2025                    continue;
2026                }
2027            }
2028            break;
2029        }
2030    } else {
2031        zend_hash_internal_pointer_reset(Z_ARRVAL_P(stack));
2032        while (1) {
2033            val = zend_hash_get_current_data(Z_ARRVAL_P(stack));
2034            if (!val) {
2035                return;
2036            } else if (Z_TYPE_P(val) == IS_INDIRECT) {
2037                val = Z_INDIRECT_P(val);
2038                if (Z_TYPE_P(val) == IS_UNDEF) {
2039                    zend_hash_move_forward(Z_ARRVAL_P(stack));
2040                    continue;
2041                }
2042            }
2043            break;
2044        }
2045    }
2046    RETVAL_ZVAL_FAST(val);
2047
2048    /* Delete the first or last value */
2049    zend_hash_get_current_key(Z_ARRVAL_P(stack), &key, &index, 0);
2050    if (key && Z_ARRVAL_P(stack) == &EG(symbol_table).ht) {
2051        zend_delete_global_variable(key TSRMLS_CC);
2052    } else if (key) {
2053        zend_hash_del(Z_ARRVAL_P(stack), key);
2054    } else {
2055        zend_hash_index_del(Z_ARRVAL_P(stack), index);
2056    }
2057
2058    /* If we did a shift... re-index like it did before */
2059    if (!off_the_end) {
2060        unsigned int k = 0;
2061        int should_rehash = 0;
2062        uint idx;
2063        Bucket *p;
2064
2065        for (idx = 0; idx < Z_ARRVAL_P(stack)->nNumUsed; idx++) {
2066            p = Z_ARRVAL_P(stack)->arData + idx;
2067            if (Z_TYPE(p->val) == IS_UNDEF) continue;
2068            if (p->key == NULL) {
2069                if (p->h != k) {
2070                    p->h = k++;
2071                    should_rehash = 1;
2072                } else {
2073                    k++;
2074                }
2075            }
2076        }
2077        Z_ARRVAL_P(stack)->nNextFreeElement = k;
2078        if (should_rehash) {
2079            if (Z_ARRVAL_P(stack)->u.flags & HASH_FLAG_PACKED) {
2080                zend_hash_packed_to_hash(Z_ARRVAL_P(stack));
2081            } else {
2082                zend_hash_rehash(Z_ARRVAL_P(stack));
2083            }
2084        }
2085    } else if (!key && Z_ARRVAL_P(stack)->nNextFreeElement > 0 && index >= Z_ARRVAL_P(stack)->nNextFreeElement - 1) {
2086        Z_ARRVAL_P(stack)->nNextFreeElement = Z_ARRVAL_P(stack)->nNextFreeElement - 1;
2087    }
2088
2089    zend_hash_internal_pointer_reset(Z_ARRVAL_P(stack));
2090}
2091/* }}} */
2092
2093/* {{{ proto mixed array_pop(array stack)
2094   Pops an element off the end of the array */
2095PHP_FUNCTION(array_pop)
2096{
2097    _phpi_pop(INTERNAL_FUNCTION_PARAM_PASSTHRU, 1);
2098}
2099/* }}} */
2100
2101/* {{{ proto mixed array_shift(array stack)
2102   Pops an element off the beginning of the array */
2103PHP_FUNCTION(array_shift)
2104{
2105    _phpi_pop(INTERNAL_FUNCTION_PARAM_PASSTHRU, 0);
2106}
2107/* }}} */
2108
2109/* {{{ proto int array_unshift(array stack, mixed var [, mixed ...])
2110   Pushes elements onto the beginning of the array */
2111PHP_FUNCTION(array_unshift)
2112{
2113    zval   *args,           /* Function arguments array */
2114           *stack;          /* Input stack */
2115    HashTable *new_hash;    /* New hashtable for the stack */
2116    HashTable  old_hash;
2117    int argc;               /* Number of function arguments */
2118
2119    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a/+", &stack, &args, &argc) == FAILURE) {
2120        return;
2121    }
2122
2123    /* Use splice to insert the elements at the beginning. Destroy old
2124     * hashtable and replace it with new one */
2125    new_hash = php_splice(Z_ARRVAL_P(stack), 0, 0, &args[0], argc, NULL);
2126    old_hash = *Z_ARRVAL_P(stack);
2127    *Z_ARRVAL_P(stack) = *new_hash;
2128    FREE_HASHTABLE(new_hash);
2129    zend_hash_destroy(&old_hash);
2130
2131    /* Clean up and return the number of elements in the stack */
2132    RETVAL_INT(zend_hash_num_elements(Z_ARRVAL_P(stack)));
2133}
2134/* }}} */
2135
2136/* {{{ proto array array_splice(array input, int offset [, int length [, array replacement]])
2137   Removes the elements designated by offset and length and replace them with supplied array */
2138PHP_FUNCTION(array_splice)
2139{
2140    zval *array,                /* Input array */
2141         *repl_array = NULL,    /* Replacement array */
2142         *repl = NULL;          /* Replacement elements */
2143    HashTable *new_hash = NULL, /* Output array's hash */
2144              *rem_hash = NULL; /* Removed elements' hash */
2145    HashTable  old_hash;
2146    uint    idx;
2147    Bucket *p;                  /* Bucket used for traversing hash */
2148    php_int_t   i,
2149            offset,
2150            length = 0,
2151            repl_num = 0;       /* Number of replacement elements */
2152    int     num_in;             /* Number of elements in the input array */
2153
2154    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a/i|iz/", &array, &offset, &length, &repl_array) == FAILURE) {
2155        return;
2156    }
2157
2158    num_in = zend_hash_num_elements(Z_ARRVAL_P(array));
2159
2160    if (ZEND_NUM_ARGS() < 3) {
2161        length = num_in;
2162    }
2163
2164    if (ZEND_NUM_ARGS() == 4) {
2165        /* Make sure the last argument, if passed, is an array */
2166        convert_to_array(repl_array);
2167
2168        /* Create the array of replacement elements */
2169        repl_num = zend_hash_num_elements(Z_ARRVAL_P(repl_array));
2170        repl = (zval *)safe_emalloc(repl_num, sizeof(zval), 0);
2171        for (idx = 0, i = 0; idx < Z_ARRVAL_P(repl_array)->nNumUsed; idx++) {
2172            p = Z_ARRVAL_P(repl_array)->arData + idx;
2173            if (Z_TYPE(p->val) == IS_UNDEF) continue;
2174            ZVAL_COPY_VALUE(&repl[i++], &p->val);
2175        }
2176    }
2177
2178    /* Don't create the array of removed elements if it's not going
2179     * to be used; e.g. only removing and/or replacing elements */
2180    if (USED_RET()) {
2181        int size = length;
2182
2183        /* Clamp the offset.. */
2184        if (offset > num_in) {
2185            offset = num_in;
2186        } else if (offset < 0 && (offset = (num_in + offset)) < 0) {
2187            offset = 0;
2188        }
2189
2190        /* ..and the length */
2191        if (length < 0) {
2192            size = num_in - offset + length;
2193        } else if (((php_uint_t) offset + (php_uint_t) length) > (unsigned) num_in) {
2194            size = num_in - offset;
2195        }
2196
2197        /* Initialize return value */
2198        array_init_size(return_value, size > 0 ? size : 0);
2199        rem_hash = Z_ARRVAL_P(return_value);
2200    }
2201
2202    /* Perform splice */
2203    new_hash = php_splice(Z_ARRVAL_P(array), offset, length, repl, repl_num, rem_hash);
2204
2205    /* Replace input array's hashtable with the new one */
2206    old_hash = *Z_ARRVAL_P(array);
2207    *Z_ARRVAL_P(array) = *new_hash;
2208    FREE_HASHTABLE(new_hash);
2209    zend_hash_destroy(&old_hash);
2210
2211    /* Clean up */
2212    if (ZEND_NUM_ARGS() == 4) {
2213        efree(repl);
2214    }
2215}
2216/* }}} */
2217
2218/* {{{ proto array array_slice(array input, int offset [, int length [, bool preserve_keys]])
2219   Returns elements specified by offset and length */
2220PHP_FUNCTION(array_slice)
2221{
2222    zval     *input,        /* Input array */
2223             *z_length = NULL, /* How many elements to get */
2224             *entry;        /* An array entry */
2225    php_int_t    offset,        /* Offset to get elements from */
2226             length = 0;
2227    zend_bool preserve_keys = 0; /* Whether to preserve keys while copying to the new array or not */
2228    int      num_in,        /* Number of elements in the input array */
2229             pos;           /* Current position in the array */
2230    zend_string *string_key;
2231    php_uint_t num_key;
2232
2233#ifndef FAST_ZPP
2234    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "ai|zb", &input, &offset, &z_length, &preserve_keys) == FAILURE) {
2235        return;
2236    }
2237#else
2238    ZEND_PARSE_PARAMETERS_START(2, 4)
2239        Z_PARAM_ARRAY(input)
2240        Z_PARAM_INT(offset)
2241        Z_PARAM_OPTIONAL
2242        Z_PARAM_ZVAL(z_length)
2243        Z_PARAM_BOOL(preserve_keys)
2244    ZEND_PARSE_PARAMETERS_END();
2245#endif
2246
2247    /* Get number of entries in the input hash */
2248    num_in = zend_hash_num_elements(Z_ARRVAL_P(input));
2249
2250    /* We want all entries from offset to the end if length is not passed or is null */
2251    if (ZEND_NUM_ARGS() < 3 || Z_TYPE_P(z_length) == IS_NULL) {
2252        length = num_in;
2253    } else {
2254        length = zval_get_int(z_length);
2255    }
2256
2257    /* Clamp the offset.. */
2258    if (offset > num_in) {
2259        array_init(return_value);
2260        return;
2261    } else if (offset < 0 && (offset = (num_in + offset)) < 0) {
2262        offset = 0;
2263    }
2264
2265    /* ..and the length */
2266    if (length < 0) {
2267        length = num_in - offset + length;
2268    } else if (((php_uint_t) offset + (php_uint_t) length) > (unsigned) num_in) {
2269        length = num_in - offset;
2270    }
2271
2272    /* Initialize returned array */
2273    array_init_size(return_value, length > 0 ? length : 0);
2274
2275    if (length <= 0) {
2276        return;
2277    }
2278
2279    /* Start at the beginning and go until we hit offset */
2280    pos = 0;
2281    ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(input), num_key, string_key, entry) {
2282        pos++;
2283        if (pos <= offset) {
2284            continue;
2285        }
2286        if (pos > offset + length) {
2287            break;
2288        }
2289
2290        /* Copy elements from input array to the one that's returned */
2291        zval_add_ref(entry);
2292
2293        if (string_key) {
2294            zend_hash_add_new(Z_ARRVAL_P(return_value), string_key, entry);
2295        } else {
2296            if (preserve_keys) {
2297                zend_hash_index_add_new(Z_ARRVAL_P(return_value), num_key, entry);
2298            } else {
2299                zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), entry);
2300            }
2301        }
2302    } ZEND_HASH_FOREACH_END();
2303}
2304/* }}} */
2305
2306PHPAPI int php_array_merge(HashTable *dest, HashTable *src, int recursive TSRMLS_DC) /* {{{ */
2307{
2308    zval *src_entry, *dest_entry;
2309    zend_string *string_key;
2310
2311    if (recursive) {
2312        ZEND_HASH_FOREACH_STR_KEY_VAL(src, string_key, src_entry) {
2313            if (string_key) {
2314                if ((dest_entry = zend_hash_find(dest, string_key)) != NULL) {
2315                    zval *src_zval = src_entry;
2316                    zval *dest_zval = dest_entry;
2317                    HashTable *thash;
2318                    zval tmp;
2319                    int ret;
2320
2321                    ZVAL_DEREF(src_zval);
2322                    ZVAL_DEREF(dest_zval);
2323                    thash = Z_TYPE_P(dest_zval) == IS_ARRAY ? Z_ARRVAL_P(dest_zval) : NULL;
2324                    if ((thash && thash->u.v.nApplyCount > 1) || (src_entry == dest_entry && Z_ISREF_P(dest_entry) && (Z_REFCOUNT_P(dest_entry) % 2))) {
2325                        php_error_docref(NULL TSRMLS_CC, E_WARNING, "recursion detected");
2326                        return 0;
2327                    }
2328
2329                    if (Z_ISREF_P(dest_entry)) {
2330                        if (Z_REFCOUNT_P(dest_entry) == 1) {
2331                            ZVAL_UNREF(dest_entry);
2332                        } else {
2333                            Z_DELREF_P(dest_entry);
2334                            ZVAL_DUP(dest_entry, dest_zval);
2335                        }
2336                        dest_zval = dest_entry;
2337                    } else {
2338                        SEPARATE_ZVAL(dest_zval);
2339                    }
2340
2341                    if (Z_TYPE_P(dest_zval) == IS_NULL) {
2342                        convert_to_array_ex(dest_zval);
2343                        add_next_index_null(dest_zval);
2344                    } else {
2345                        convert_to_array_ex(dest_zval);
2346                    }
2347                    ZVAL_UNDEF(&tmp);
2348                    if (Z_TYPE_P(src_zval) == IS_OBJECT) {
2349                        ZVAL_DUP(&tmp, src_zval);
2350                        convert_to_array(&tmp);
2351                        src_zval = &tmp;
2352                    }
2353                    if (Z_TYPE_P(src_zval) == IS_ARRAY) {
2354                        if (thash && ZEND_HASH_APPLY_PROTECTION(thash)) {
2355                            thash->u.v.nApplyCount++;
2356                        }
2357                        ret = php_array_merge(Z_ARRVAL_P(dest_zval), Z_ARRVAL_P(src_zval), 1 TSRMLS_CC);
2358                        if (thash && ZEND_HASH_APPLY_PROTECTION(thash)) {
2359                            thash->u.v.nApplyCount--;
2360                        }
2361                        if (!ret) {
2362                            return 0;
2363                        }
2364                    } else {
2365                        if (Z_REFCOUNTED_P(src_entry)) {
2366                            Z_ADDREF_P(src_entry);
2367                        }
2368                        zend_hash_next_index_insert(Z_ARRVAL_P(dest_zval), src_zval);
2369                    }
2370                    zval_ptr_dtor(&tmp);
2371                } else {
2372                    if (Z_REFCOUNTED_P(src_entry)) {
2373                        Z_ADDREF_P(src_entry);
2374                    }
2375                    zend_hash_add_new(dest, string_key, src_entry);
2376                }
2377            } else {
2378                if (Z_REFCOUNTED_P(src_entry)) {
2379                    Z_ADDREF_P(src_entry);
2380                }
2381                zend_hash_next_index_insert_new(dest, src_entry);
2382            }
2383        } ZEND_HASH_FOREACH_END();
2384    } else {
2385        ZEND_HASH_FOREACH_STR_KEY_VAL(src, string_key, src_entry) {
2386            if (string_key) {
2387                if (Z_REFCOUNTED_P(src_entry)) {
2388                    Z_ADDREF_P(src_entry);
2389                }
2390                zend_hash_update(dest, string_key, src_entry);
2391            } else {
2392                if (Z_REFCOUNTED_P(src_entry)) {
2393                    Z_ADDREF_P(src_entry);
2394                }
2395                zend_hash_next_index_insert_new(dest, src_entry);
2396            }
2397        } ZEND_HASH_FOREACH_END();
2398    }
2399    return 1;
2400}
2401/* }}} */
2402
2403PHPAPI int php_array_replace_recursive(HashTable *dest, HashTable *src TSRMLS_DC) /* {{{ */
2404{
2405    zval *src_entry, *dest_entry, *src_zval, *dest_zval;
2406    zend_string *string_key;
2407    php_uint_t num_key;
2408    int ret;
2409
2410    ZEND_HASH_FOREACH_KEY_VAL(src, num_key, string_key, src_entry) {
2411        src_zval = src_entry;
2412        ZVAL_DEREF(src_zval);
2413        if (string_key) {
2414            if (Z_TYPE_P(src_zval) != IS_ARRAY ||
2415                (dest_entry = zend_hash_find(dest, string_key)) == NULL ||
2416                (Z_TYPE_P(dest_entry) != IS_ARRAY &&
2417                 (!Z_ISREF_P(dest_entry) || Z_TYPE_P(Z_REFVAL_P(dest_entry)) != IS_ARRAY))) {
2418
2419                if (Z_REFCOUNTED_P(src_entry)) {
2420                    Z_ADDREF_P(src_entry);
2421                }
2422                zend_hash_update(dest, string_key, src_entry);
2423
2424                continue;
2425            }
2426        } else {
2427            if (Z_TYPE_P(src_zval) != IS_ARRAY ||
2428                (dest_entry = zend_hash_index_find(dest, num_key)) == NULL ||
2429                (Z_TYPE_P(dest_entry) != IS_ARRAY &&
2430                 (!Z_ISREF_P(dest_entry) || Z_TYPE_P(Z_REFVAL_P(dest_entry)) != IS_ARRAY))) {
2431
2432                if (Z_REFCOUNTED_P(src_entry)) {
2433                    Z_ADDREF_P(src_entry);
2434                }
2435                zend_hash_index_update(dest, num_key, src_entry);
2436
2437                continue;
2438            }
2439        }
2440
2441        dest_zval = dest_entry;
2442        ZVAL_DEREF(dest_zval);
2443        if (Z_ARRVAL_P(dest_zval)->u.v.nApplyCount > 1 ||
2444            Z_ARRVAL_P(src_zval)->u.v.nApplyCount > 1 ||
2445            (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))) {
2446            php_error_docref(NULL TSRMLS_CC, E_WARNING, "recursion detected");
2447            return 0;
2448        }
2449        SEPARATE_ZVAL(dest_zval);
2450
2451        if (ZEND_HASH_APPLY_PROTECTION(Z_ARRVAL_P(dest_zval))) {
2452            Z_ARRVAL_P(dest_zval)->u.v.nApplyCount++;
2453        }
2454        if (ZEND_HASH_APPLY_PROTECTION(Z_ARRVAL_P(src_zval))) {
2455            Z_ARRVAL_P(src_zval)->u.v.nApplyCount++;
2456        }
2457
2458        ret = php_array_replace_recursive(Z_ARRVAL_P(dest_zval), Z_ARRVAL_P(src_zval) TSRMLS_CC);
2459
2460        if (ZEND_HASH_APPLY_PROTECTION(Z_ARRVAL_P(dest_zval))) {
2461            Z_ARRVAL_P(dest_zval)->u.v.nApplyCount--;
2462        }
2463        if (ZEND_HASH_APPLY_PROTECTION(Z_ARRVAL_P(src_zval))) {
2464            Z_ARRVAL_P(src_zval)->u.v.nApplyCount--;
2465        }
2466
2467        if (!ret) {
2468            return 0;
2469        }
2470    } ZEND_HASH_FOREACH_END();
2471
2472    return 1;
2473}
2474/* }}} */
2475
2476static void php_array_merge_or_replace_wrapper(INTERNAL_FUNCTION_PARAMETERS, int recursive, int replace) /* {{{ */
2477{
2478    zval *args = NULL;
2479    int argc, i, init_size = 0;
2480
2481#ifndef FAST_ZPP
2482    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "+", &args, &argc) == FAILURE) {
2483        return;
2484    }
2485#else
2486    ZEND_PARSE_PARAMETERS_START(1, -1)
2487        Z_PARAM_VARIADIC('+', args, argc)
2488    ZEND_PARSE_PARAMETERS_END();
2489#endif
2490
2491    for (i = 0; i < argc; i++) {
2492        zval *arg = args + i;
2493
2494        ZVAL_DEREF(arg);
2495        if (Z_TYPE_P(arg) != IS_ARRAY) {
2496            php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument #%d is not an array", i + 1);
2497            RETURN_NULL();
2498        } else {
2499            int num = zend_hash_num_elements(Z_ARRVAL_P(arg));
2500
2501            if (num > init_size) {
2502                init_size = num;
2503            }
2504        }
2505    }
2506
2507    array_init_size(return_value, init_size);
2508
2509    for (i = 0; i < argc; i++) {
2510        zval *arg = args + i;
2511
2512        ZVAL_DEREF(arg);
2513        if (!replace) {
2514            php_array_merge(Z_ARRVAL_P(return_value), Z_ARRVAL_P(arg), recursive TSRMLS_CC);
2515        } else if (recursive && i > 0) { /* First array will be copied directly instead */
2516            php_array_replace_recursive(Z_ARRVAL_P(return_value), Z_ARRVAL_P(arg) TSRMLS_CC);
2517        } else {
2518            zend_hash_merge(Z_ARRVAL_P(return_value), Z_ARRVAL_P(arg), zval_add_ref, 1);
2519        }
2520    }
2521}
2522/* }}} */
2523
2524/* {{{ proto array array_merge(array arr1, array arr2 [, array ...])
2525   Merges elements from passed arrays into one array */
2526PHP_FUNCTION(array_merge)
2527{
2528    php_array_merge_or_replace_wrapper(INTERNAL_FUNCTION_PARAM_PASSTHRU, 0, 0);
2529}
2530/* }}} */
2531
2532/* {{{ proto array array_merge_recursive(array arr1, array arr2 [, array ...])
2533   Recursively merges elements from passed arrays into one array */
2534PHP_FUNCTION(array_merge_recursive)
2535{
2536    php_array_merge_or_replace_wrapper(INTERNAL_FUNCTION_PARAM_PASSTHRU, 1, 0);
2537}
2538/* }}} */
2539
2540/* {{{ proto array array_replace(array arr1, array arr2 [, array ...])
2541   Replaces elements from passed arrays into one array */
2542PHP_FUNCTION(array_replace)
2543{
2544    php_array_merge_or_replace_wrapper(INTERNAL_FUNCTION_PARAM_PASSTHRU, 0, 1);
2545}
2546/* }}} */
2547
2548/* {{{ proto array array_replace_recursive(array arr1, array arr2 [, array ...])
2549   Recursively replaces elements from passed arrays into one array */
2550PHP_FUNCTION(array_replace_recursive)
2551{
2552    php_array_merge_or_replace_wrapper(INTERNAL_FUNCTION_PARAM_PASSTHRU, 1, 1);
2553}
2554/* }}} */
2555
2556/* {{{ proto array array_keys(array input [, mixed search_value[, bool strict]])
2557   Return just the keys from the input array, optionally only for the specified search_value */
2558PHP_FUNCTION(array_keys)
2559{
2560    zval *input,                /* Input array */
2561         *search_value = NULL,  /* Value to search for */
2562         *entry,                /* An entry in the input array */
2563           res,                 /* Result of comparison */
2564           new_val;             /* New value */
2565    int    add_key;             /* Flag to indicate whether a key should be added */
2566    zend_bool strict = 0;       /* do strict comparison */
2567    php_uint_t num_idx;
2568    zend_string *str_idx;
2569    int (*is_equal_func)(zval *, zval *, zval * TSRMLS_DC) = is_equal_function;
2570
2571#ifndef FAST_ZPP
2572    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a|zb", &input, &search_value, &strict) == FAILURE) {
2573        return;
2574    }
2575#else
2576    ZEND_PARSE_PARAMETERS_START(1, 3)
2577        Z_PARAM_ARRAY(input)
2578        Z_PARAM_OPTIONAL
2579        Z_PARAM_ZVAL(search_value)
2580        Z_PARAM_BOOL(strict)
2581    ZEND_PARSE_PARAMETERS_END();
2582#endif
2583
2584    if (strict) {
2585        is_equal_func = is_identical_function;
2586    }
2587
2588    /* Initialize return array */
2589    if (search_value != NULL) {
2590        array_init(return_value);
2591    } else {
2592        array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(input)));
2593    }
2594    add_key = 1;
2595
2596    /* Go through input array and add keys to the return array */
2597    ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(input), num_idx, str_idx, entry) {
2598        if (search_value != NULL) {
2599            is_equal_func(&res, search_value, entry TSRMLS_CC);
2600            add_key = zval_is_true(&res);
2601        }
2602
2603        if (add_key) {
2604            if (str_idx) {
2605                ZVAL_STR(&new_val, STR_COPY(str_idx));
2606            } else {
2607                ZVAL_INT(&new_val, num_idx);
2608            }
2609            zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &new_val);
2610        }
2611    } ZEND_HASH_FOREACH_END();
2612}
2613/* }}} */
2614
2615/* {{{ proto array array_values(array input)
2616   Return just the values from the input array */
2617PHP_FUNCTION(array_values)
2618{
2619    zval     *input,        /* Input array */
2620             *entry;        /* An entry in the input array */
2621
2622    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a", &input) == FAILURE) {
2623        return;
2624    }
2625
2626    /* Initialize return array */
2627    array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(input)));
2628
2629    /* Go through input array and add values to the return array */
2630    ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(input), entry) {
2631        zval_add_ref(entry);
2632        zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), entry);
2633    } ZEND_HASH_FOREACH_END();
2634}
2635/* }}} */
2636
2637/* {{{ proto array array_count_values(array input)
2638   Return the value as key and the frequency of that value in input as value */
2639PHP_FUNCTION(array_count_values)
2640{
2641    zval    *input,     /* Input array */
2642            *entry,     /* An entry in the input array */
2643            *tmp;
2644    HashTable *myht;
2645
2646    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a", &input) == FAILURE) {
2647        return;
2648    }
2649
2650    /* Initialize return array */
2651    array_init(return_value);
2652
2653    /* Go through input array and add values to the return array */
2654    myht = Z_ARRVAL_P(input);
2655    ZEND_HASH_FOREACH_VAL(myht, entry) {
2656        if (Z_TYPE_P(entry) == IS_INT) {
2657            if ((tmp = zend_hash_index_find(Z_ARRVAL_P(return_value), Z_IVAL_P(entry))) == NULL) {
2658                zval data;
2659                ZVAL_INT(&data, 1);
2660                zend_hash_index_update(Z_ARRVAL_P(return_value), Z_IVAL_P(entry), &data);
2661            } else {
2662                Z_IVAL_P(tmp)++;
2663            }
2664        } else if (Z_TYPE_P(entry) == IS_STRING) {
2665            if ((tmp = zend_symtable_find(Z_ARRVAL_P(return_value), Z_STR_P(entry))) == NULL) {
2666                zval data;
2667                ZVAL_INT(&data, 1);
2668                zend_symtable_update(Z_ARRVAL_P(return_value), Z_STR_P(entry), &data);
2669            } else {
2670                Z_IVAL_P(tmp)++;
2671            }
2672        } else {
2673            php_error_docref(NULL TSRMLS_CC, E_WARNING, "Can only count STRING and INTEGER values!");
2674        }
2675    } ZEND_HASH_FOREACH_END();
2676}
2677/* }}} */
2678
2679/* {{{ array_column_param_helper
2680 * Specialized conversion rules for array_column() function
2681 */
2682static inline
2683zend_bool array_column_param_helper(zval *param,
2684                                    const char *name TSRMLS_DC) {
2685    switch (Z_TYPE_P(param)) {
2686        case IS_DOUBLE:
2687            convert_to_int_ex(param);
2688            /* fallthrough */
2689        case IS_INT:
2690            return 1;
2691
2692        case IS_OBJECT:
2693            convert_to_string_ex(param);
2694            /* fallthrough */
2695        case IS_STRING:
2696            return 1;
2697
2698        default:
2699            php_error_docref(NULL TSRMLS_CC, E_WARNING, "The %s key should be either a string or an integer", name);
2700            return 0;
2701    }
2702}
2703
2704/* {{{ proto array array_column(array input, mixed column_key[, mixed index_key])
2705   Return the values from a single column in the input array, identified by the
2706   value_key and optionally indexed by the index_key */
2707PHP_FUNCTION(array_column)
2708{
2709    zval *zcolumn = NULL, *zkey = NULL, *data;
2710    HashTable *arr_hash;
2711    zval *zcolval = NULL, *zkeyval = NULL;
2712    HashTable *ht;
2713
2714    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "hz!|z!", &arr_hash, &zcolumn, &zkey) == FAILURE) {
2715        return;
2716    }
2717
2718    if ((zcolumn && !array_column_param_helper(zcolumn, "column" TSRMLS_CC)) ||
2719        (zkey && !array_column_param_helper(zkey, "index" TSRMLS_CC))) {
2720        RETURN_FALSE;
2721    }
2722
2723    array_init(return_value);
2724    ZEND_HASH_FOREACH_VAL(arr_hash, data) {
2725        if (Z_TYPE_P(data) != IS_ARRAY) {
2726            /* Skip elemens which are not sub-arrays */
2727            continue;
2728        }
2729        ht = Z_ARRVAL_P(data);
2730
2731        if (!zcolumn) {
2732            /* NULL column ID means use entire subarray as data */
2733            zcolval = data;
2734
2735            /* Otherwise, skip if the value doesn't exist in our subarray */
2736        } else if ((Z_TYPE_P(zcolumn) == IS_STRING) &&
2737            ((zcolval = zend_hash_find(ht, Z_STR_P(zcolumn))) == NULL)) {
2738            continue;
2739        } else if ((Z_TYPE_P(zcolumn) == IS_INT) &&
2740            ((zcolval = zend_hash_index_find(ht, Z_IVAL_P(zcolumn))) == NULL)) {
2741            continue;
2742        }
2743
2744        /* Failure will leave zkeyval alone which will land us on the final else block below
2745         * which is to append the value as next_index
2746         */
2747        if (zkey && (Z_TYPE_P(zkey) == IS_STRING)) {
2748            zkeyval = zend_hash_find(ht, Z_STR_P(zkey));
2749        } else if (zkey && (Z_TYPE_P(zkey) == IS_INT)) {
2750            zkeyval = zend_hash_index_find(ht, Z_IVAL_P(zkey));
2751        }
2752
2753        if (Z_REFCOUNTED_P(zcolval)) {
2754            Z_ADDREF_P(zcolval);
2755        }
2756        if (zkeyval && Z_TYPE_P(zkeyval) == IS_STRING) {
2757            zend_symtable_update(Z_ARRVAL_P(return_value), Z_STR_P(zkeyval), zcolval);
2758        } else if (zkeyval && Z_TYPE_P(zkeyval) == IS_INT) {
2759            add_index_zval(return_value, Z_IVAL_P(zkeyval), zcolval);
2760        } else if (zkeyval && Z_TYPE_P(zkeyval) == IS_OBJECT) {
2761            SEPARATE_ZVAL(zkeyval);
2762            convert_to_string(zkeyval);
2763            zend_symtable_update(Z_ARRVAL_P(return_value), Z_STR_P(zkeyval), zcolval);
2764        } else {
2765            add_next_index_zval(return_value, zcolval);
2766        }
2767    } ZEND_HASH_FOREACH_END();
2768}
2769/* }}} */
2770
2771/* {{{ proto array array_reverse(array input [, bool preserve keys])
2772   Return input as a new array with the order of the entries reversed */
2773PHP_FUNCTION(array_reverse)
2774{
2775    zval     *input,                /* Input array */
2776             *entry;                /* An entry in the input array */
2777    zend_string *string_key;
2778    php_uint_t    num_key;
2779    zend_bool preserve_keys = 0;    /* whether to preserve keys */
2780
2781    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a|b", &input, &preserve_keys) == FAILURE) {
2782        return;
2783    }
2784
2785    /* Initialize return array */
2786    array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(input)));
2787
2788    ZEND_HASH_REVERSE_FOREACH_KEY_VAL(Z_ARRVAL_P(input), num_key, string_key, entry) {
2789        zval_add_ref(entry);
2790
2791        if (string_key) {
2792            zend_hash_add_new(Z_ARRVAL_P(return_value), string_key, entry);
2793        } else {
2794            if (preserve_keys) {
2795                zend_hash_index_add_new(Z_ARRVAL_P(return_value), num_key, entry);
2796            } else {
2797                zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), entry);
2798            }
2799        }
2800    } ZEND_HASH_FOREACH_END();
2801}
2802/* }}} */
2803
2804/* {{{ proto array array_pad(array input, int pad_size, mixed pad_value)
2805   Returns a copy of input array padded with pad_value to size pad_size */
2806PHP_FUNCTION(array_pad)
2807{
2808    zval  *input;       /* Input array */
2809    zval  *pad_value;   /* Padding value obviously */
2810    zval  *pads;        /* Array to pass to splice */
2811    HashTable *new_hash;/* Return value from splice */
2812    HashTable  old_hash;
2813    php_int_t pad_size;     /* Size to pad to */
2814    php_int_t pad_size_abs; /* Absolute value of pad_size */
2815    php_int_t input_size;       /* Size of the input array */
2816    php_int_t num_pads;     /* How many pads do we need */
2817    int do_pad;         /* Whether we should do padding at all */
2818    int i;
2819
2820    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "aiz", &input, &pad_size, &pad_value) == FAILURE) {
2821        return;
2822    }
2823
2824    /* Do some initial calculations */
2825    input_size = zend_hash_num_elements(Z_ARRVAL_P(input));
2826    pad_size_abs = ZEND_ABS(pad_size);
2827    if (pad_size_abs < 0) {
2828        php_error_docref(NULL TSRMLS_CC, E_WARNING, "You may only pad up to 1048576 elements at a time");
2829        zval_dtor(return_value);
2830        RETURN_FALSE;
2831    }
2832    do_pad = (input_size >= pad_size_abs) ? 0 : 1;
2833
2834    /* Copy the original array */
2835    RETVAL_ZVAL(input, 1, 0);
2836
2837    /* If no need to pad, no need to continue */
2838    if (!do_pad) {
2839        return;
2840    }
2841
2842    /* Populate the pads array */
2843    num_pads = pad_size_abs - input_size;
2844    if (num_pads > Z_I(1048576)) {
2845        php_error_docref(NULL TSRMLS_CC, E_WARNING, "You may only pad up to 1048576 elements at a time");
2846        zval_dtor(return_value);
2847        RETURN_FALSE;
2848    }
2849    pads = (zval *)safe_emalloc(num_pads, sizeof(zval), 0);
2850    for (i = 0; i < num_pads; i++) {
2851        ZVAL_COPY_VALUE(&pads[i], pad_value);
2852    }
2853
2854    /* Pad on the right or on the left */
2855    if (pad_size > 0) {
2856        new_hash = php_splice(Z_ARRVAL_P(return_value), input_size, 0, pads, num_pads, NULL);
2857    } else {
2858        new_hash = php_splice(Z_ARRVAL_P(return_value), 0, 0, pads, num_pads, NULL);
2859    }
2860
2861    /* Copy the result hash into return value */
2862    old_hash = *Z_ARRVAL_P(return_value);
2863    *Z_ARRVAL_P(return_value) = *new_hash;
2864    FREE_HASHTABLE(new_hash);
2865    zend_hash_destroy(&old_hash);
2866
2867    /* Clean up */
2868    efree(pads);
2869}
2870/* }}} */
2871
2872/* {{{ proto array array_flip(array input)
2873   Return array with key <-> value flipped */
2874PHP_FUNCTION(array_flip)
2875{
2876    zval *array, *entry, data;
2877    php_uint_t num_idx;
2878    zend_string *str_idx;
2879
2880    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a", &array) == FAILURE) {
2881        return;
2882    }
2883
2884    array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(array)));
2885
2886    ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_idx, str_idx, entry) {
2887        if (Z_TYPE_P(entry) == IS_INT) {
2888            if (str_idx) {
2889                ZVAL_STR(&data, STR_COPY(str_idx));
2890            } else {
2891                ZVAL_INT(&data, num_idx);
2892            }
2893            zend_hash_index_update(Z_ARRVAL_P(return_value), Z_IVAL_P(entry), &data);
2894        } else if (Z_TYPE_P(entry) == IS_STRING) {
2895            if (str_idx) {
2896                ZVAL_STR(&data, STR_COPY(str_idx));
2897            } else {
2898                ZVAL_INT(&data, num_idx);
2899            }
2900            zend_symtable_update(Z_ARRVAL_P(return_value), Z_STR_P(entry), &data);
2901        } else {
2902            php_error_docref(NULL TSRMLS_CC, E_WARNING, "Can only flip STRING and INTEGER values!");
2903        }
2904    } ZEND_HASH_FOREACH_END();
2905}
2906/* }}} */
2907
2908/* {{{ proto array array_change_key_case(array input [, int case=CASE_LOWER])
2909   Retuns an array with all string keys lowercased [or uppercased] */
2910PHP_FUNCTION(array_change_key_case)
2911{
2912    zval *array, *entry;
2913    zend_string *string_key;
2914    zend_string *new_key;
2915    php_uint_t num_key;
2916    php_int_t change_to_upper=0;
2917
2918    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a|i", &array, &change_to_upper) == FAILURE) {
2919        return;
2920    }
2921
2922    array_init_size(return_value, zend_hash_num_elements(Z_ARRVAL_P(array)));
2923
2924    ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_key, string_key, entry) {
2925        zval_add_ref(entry);
2926
2927        if (!string_key) {
2928            zend_hash_index_update(Z_ARRVAL_P(return_value), num_key, entry);
2929        } else {
2930            new_key = STR_INIT(string_key->val, string_key->len, 0);
2931            if (change_to_upper) {
2932                php_strtoupper(new_key->val, new_key->len);
2933            } else {
2934                php_strtolower(new_key->val, new_key->len);
2935            }
2936            zend_hash_update(Z_ARRVAL_P(return_value), new_key, entry);
2937            STR_RELEASE(new_key);
2938        }
2939    } ZEND_HASH_FOREACH_END();
2940}
2941/* }}} */
2942
2943/* {{{ proto array array_unique(array input [, int sort_flags])
2944   Removes duplicate values from array */
2945PHP_FUNCTION(array_unique)
2946{
2947    zval *array;
2948    uint idx;
2949    Bucket *p;
2950    struct bucketindex {
2951        Bucket b;
2952        unsigned int i;
2953    };
2954    struct bucketindex *arTmp, *cmpdata, *lastkept;
2955    unsigned int i;
2956    php_int_t sort_type = PHP_SORT_STRING;
2957
2958    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a|i", &array, &sort_type) == FAILURE) {
2959        return;
2960    }
2961
2962    php_set_compare_func(sort_type TSRMLS_CC);
2963
2964    ZVAL_NEW_ARR(return_value);
2965    zend_array_dup(Z_ARRVAL_P(return_value), Z_ARRVAL_P(array));
2966
2967    if (Z_ARRVAL_P(array)->nNumOfElements <= 1) {   /* nothing to do */
2968        return;
2969    }
2970
2971    /* create and sort array with pointers to the target_hash buckets */
2972    arTmp = (struct bucketindex *) pemalloc((Z_ARRVAL_P(array)->nNumOfElements + 1) * sizeof(struct bucketindex), Z_ARRVAL_P(array)->u.flags & HASH_FLAG_PERSISTENT);
2973    if (!arTmp) {
2974        zval_dtor(return_value);
2975        RETURN_FALSE;
2976    }
2977    for (i = 0, idx = 0; idx < Z_ARRVAL_P(array)->nNumUsed; idx++) {
2978        p = Z_ARRVAL_P(array)->arData + idx;
2979        if (Z_TYPE(p->val) == IS_UNDEF) continue;
2980        if (Z_TYPE(p->val) == IS_INDIRECT && Z_TYPE_P(Z_INDIRECT(p->val)) == IS_UNDEF) continue;
2981        arTmp[i].b = *p;
2982        arTmp[i].i = i;
2983        i++;
2984    }
2985    ZVAL_UNDEF(&arTmp[i].b.val);
2986    zend_qsort((void *) arTmp, i, sizeof(struct bucketindex), php_array_data_compare TSRMLS_CC);
2987
2988    /* go through the sorted array and delete duplicates from the copy */
2989    lastkept = arTmp;
2990    for (cmpdata = arTmp + 1; Z_TYPE(cmpdata->b.val) != IS_UNDEF; cmpdata++) {
2991        if (php_array_data_compare(lastkept, cmpdata TSRMLS_CC)) {
2992            lastkept = cmpdata;
2993        } else {
2994            if (lastkept->i > cmpdata->i) {
2995                p = &lastkept->b;
2996                lastkept = cmpdata;
2997            } else {
2998                p = &cmpdata->b;
2999            }
3000            if (p->key == NULL) {
3001                zend_hash_index_del(Z_ARRVAL_P(return_value), p->h);
3002            } else {
3003                if (Z_ARRVAL_P(return_value) == &EG(symbol_table).ht) {
3004                    zend_delete_global_variable(p->key TSRMLS_CC);
3005                } else {
3006                    zend_hash_del(Z_ARRVAL_P(return_value), p->key);
3007                }
3008            }
3009        }
3010    }
3011    pefree(arTmp, Z_ARRVAL_P(array)->u.flags & HASH_FLAG_PERSISTENT);
3012}
3013/* }}} */
3014
3015static int zval_compare(zval *a, zval *b TSRMLS_DC) /* {{{ */
3016{
3017    zval result;
3018    zval *first;
3019    zval *second;
3020
3021    first = a;
3022    second = b;
3023
3024    if (Z_TYPE_P(first) == IS_INDIRECT) {
3025        first = Z_INDIRECT_P(first);
3026    }
3027    if (Z_TYPE_P(second) == IS_INDIRECT) {
3028        second = Z_INDIRECT_P(second);
3029    }
3030    if (string_compare_function(&result, first, second TSRMLS_CC) == FAILURE) {
3031        return 0;
3032    }
3033
3034    if (Z_TYPE(result) == IS_DOUBLE) {
3035        return ZEND_NORMALIZE_BOOL(Z_DVAL(result));
3036    }
3037
3038    convert_to_int(&result);
3039    return ZEND_NORMALIZE_BOOL(Z_IVAL(result));
3040}
3041/* }}} */
3042
3043static int zval_user_compare(zval *a, zval *b TSRMLS_DC) /* {{{ */
3044{
3045    zval args[2];
3046    zval retval;
3047
3048    if (Z_TYPE_P(a) == IS_INDIRECT) {
3049        a = Z_INDIRECT_P(a);
3050    }
3051    if (Z_TYPE_P(b) == IS_INDIRECT) {
3052        b = Z_INDIRECT_P(b);
3053    }
3054
3055    ZVAL_COPY_VALUE(&args[0], a);
3056    ZVAL_COPY_VALUE(&args[1], b);
3057
3058    BG(user_compare_fci).param_count = 2;
3059    BG(user_compare_fci).params = args;
3060    BG(user_compare_fci).retval = &retval;
3061    BG(user_compare_fci).no_separation = 0;
3062
3063    if (zend_call_function(&BG(user_compare_fci), &BG(user_compare_fci_cache) TSRMLS_CC) == SUCCESS && Z_TYPE(retval) != IS_UNDEF) {
3064        php_int_t ret = zval_get_int(&retval);
3065        zval_ptr_dtor(&retval);
3066        return ret < 0 ? -1 : ret > 0 ? 1 : 0;;
3067    } else {
3068        return 0;
3069    }
3070}
3071/* }}} */
3072
3073static void php_array_intersect_key(INTERNAL_FUNCTION_PARAMETERS, int data_compare_type) /* {{{ */
3074{
3075    uint idx;
3076    Bucket *p;
3077    int argc, i;
3078    zval *args;
3079    int (*intersect_data_compare_func)(zval *, zval * TSRMLS_DC) = NULL;
3080    zend_bool ok;
3081    zval *val, *data;
3082    int req_args;
3083    char *param_spec;
3084
3085    /* Get the argument count */
3086    argc = ZEND_NUM_ARGS();
3087    if (data_compare_type == INTERSECT_COMP_DATA_USER) {
3088        /* INTERSECT_COMP_DATA_USER - array_uintersect_assoc() */
3089        req_args = 3;
3090        param_spec = "+f";
3091        intersect_data_compare_func = zval_user_compare;
3092    } else {
3093        /*  INTERSECT_COMP_DATA_NONE - array_intersect_key()
3094            INTERSECT_COMP_DATA_INTERNAL - array_intersect_assoc() */
3095        req_args = 2;
3096        param_spec = "+";
3097
3098        if (data_compare_type == INTERSECT_COMP_DATA_INTERNAL) {
3099            intersect_data_compare_func = zval_compare;
3100        }
3101    }
3102
3103    if (argc < req_args) {
3104        php_error_docref(NULL TSRMLS_CC, E_WARNING, "at least %d parameters are required, %d given", req_args, argc);
3105        return;
3106    }
3107
3108    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, param_spec, &args, &argc, &BG(user_compare_fci), &BG(user_compare_fci_cache)) == FAILURE) {
3109        return;
3110    }
3111
3112    for (i = 0; i < argc; i++) {
3113        if (Z_TYPE(args[i]) != IS_ARRAY) {
3114            php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument #%d is not an array", i + 1);
3115            RETURN_NULL();
3116        }
3117    }
3118
3119    array_init(return_value);
3120
3121    for (idx = 0; idx < Z_ARRVAL(args[0])->nNumUsed; idx++) {
3122        p = Z_ARRVAL(args[0])->arData + idx;
3123        val = &p->val;
3124        if (Z_TYPE_P(val) == IS_UNDEF) continue;
3125        if (Z_ISREF_P(val) && Z_REFCOUNT_P(val) == 1) {
3126            ZVAL_UNREF(val);
3127        }
3128        if (p->key == NULL) {
3129            ok = 1;
3130            for (i = 1; i < argc; i++) {
3131                if ((data = zend_hash_index_find(Z_ARRVAL(args[i]), p->h)) == NULL ||
3132                    (intersect_data_compare_func &&
3133                    intersect_data_compare_func(val, data TSRMLS_CC) != 0)
3134                ) {
3135                    ok = 0;
3136                    break;
3137                }
3138            }
3139            if (ok) {
3140                if (Z_REFCOUNTED_P(val)) {
3141                    Z_ADDREF_P(val);
3142                }
3143                zend_hash_index_update(Z_ARRVAL_P(return_value), p->h, val);
3144            }
3145        } else {
3146            ok = 1;
3147            for (i = 1; i < argc; i++) {
3148                if ((data = zend_hash_find(Z_ARRVAL(args[i]), p->key)) == NULL ||
3149                    (intersect_data_compare_func &&
3150                    intersect_data_compare_func(val, data TSRMLS_CC) != 0)
3151                ) {
3152                    ok = 0;
3153                    break;
3154                }
3155            }
3156            if (ok) {
3157                if (Z_REFCOUNTED_P(val)) {
3158                    Z_ADDREF_P(val);
3159                }
3160                zend_hash_update(Z_ARRVAL_P(return_value), p->key, val);
3161            }
3162        }
3163    }
3164}
3165/* }}} */
3166
3167static void php_array_intersect(INTERNAL_FUNCTION_PARAMETERS, int behavior, int data_compare_type, int key_compare_type) /* {{{ */
3168{
3169    zval *args = NULL;
3170    HashTable *hash;
3171    int arr_argc, i, c = 0;
3172    uint idx;
3173    Bucket **lists, *list, **ptrs, *p;
3174    int req_args;
3175    char *param_spec;
3176    zend_fcall_info fci1, fci2;
3177    zend_fcall_info_cache fci1_cache = empty_fcall_info_cache, fci2_cache = empty_fcall_info_cache;
3178    zend_fcall_info *fci_key = NULL, *fci_data;
3179    zend_fcall_info_cache *fci_key_cache = NULL, *fci_data_cache;
3180    PHP_ARRAY_CMP_FUNC_VARS;
3181
3182    int (*intersect_key_compare_func)(const void *, const void * TSRMLS_DC);
3183    int (*intersect_data_compare_func)(const void *, const void * TSRMLS_DC);
3184
3185    if (behavior == INTERSECT_NORMAL) {
3186        intersect_key_compare_func = php_array_key_compare;
3187
3188        if (data_compare_type == INTERSECT_COMP_DATA_INTERNAL) {
3189            /* array_intersect() */
3190            req_args = 2;
3191            param_spec = "+";
3192            intersect_data_compare_func = php_array_data_compare;
3193        } else if (data_compare_type == INTERSECT_COMP_DATA_USER) {
3194            /* array_uintersect() */
3195            req_args = 3;
3196            param_spec = "+f";
3197            intersect_data_compare_func = php_array_user_compare;
3198        } else {
3199            php_error_docref(NULL TSRMLS_CC, E_WARNING, "data_compare_type is %d. This should never happen. Please report as a bug", data_compare_type);
3200            return;
3201        }
3202
3203        if (ZEND_NUM_ARGS() < req_args) {
3204            php_error_docref(NULL TSRMLS_CC, E_WARNING, "at least %d parameters are required, %d given", req_args, ZEND_NUM_ARGS());
3205            return;
3206        }
3207
3208        if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, param_spec, &args, &arr_argc, &fci1, &fci1_cache) == FAILURE) {
3209            return;
3210        }
3211        fci_data = &fci1;
3212        fci_data_cache = &fci1_cache;
3213
3214    } else if (behavior & INTERSECT_ASSOC) { /* triggered also when INTERSECT_KEY */
3215        /* INTERSECT_KEY is subset of INTERSECT_ASSOC. When having the former
3216         * no comparison of the data is done (part of INTERSECT_ASSOC) */
3217        intersect_key_compare_func = php_array_key_compare;
3218
3219        if (data_compare_type == INTERSECT_COMP_DATA_INTERNAL && key_compare_type == INTERSECT_COMP_KEY_INTERNAL) {
3220            /* array_intersect_assoc() or array_intersect_key() */
3221            req_args = 2;
3222            param_spec = "+";
3223            intersect_key_compare_func = php_array_key_compare;
3224            intersect_data_compare_func = php_array_data_compare;
3225        } else if (data_compare_type == INTERSECT_COMP_DATA_USER && key_compare_type == INTERSECT_COMP_KEY_INTERNAL) {
3226            /* array_uintersect_assoc() */
3227            req_args = 3;
3228            param_spec = "+f";
3229            intersect_key_compare_func = php_array_key_compare;
3230            intersect_data_compare_func = php_array_user_compare;
3231            fci_data = &fci1;
3232            fci_data_cache = &fci1_cache;
3233        } else if (data_compare_type == INTERSECT_COMP_DATA_INTERNAL && key_compare_type == INTERSECT_COMP_KEY_USER) {
3234            /* array_intersect_uassoc() or array_intersect_ukey() */
3235            req_args = 3;
3236            param_spec = "+f";
3237            intersect_key_compare_func = php_array_user_key_compare;
3238            intersect_data_compare_func = php_array_data_compare;
3239            fci_key = &fci1;
3240            fci_key_cache = &fci1_cache;
3241        } else if (data_compare_type == INTERSECT_COMP_DATA_USER && key_compare_type == INTERSECT_COMP_KEY_USER) {
3242            /* array_uintersect_uassoc() */
3243            req_args = 4;
3244            param_spec = "+ff";
3245            intersect_key_compare_func = php_array_user_key_compare;
3246            intersect_data_compare_func = php_array_user_compare;
3247            fci_data = &fci1;
3248            fci_data_cache = &fci1_cache;
3249            fci_key = &fci2;
3250            fci_key_cache = &fci2_cache;
3251        } else {
3252            php_error_docref(NULL TSRMLS_CC, 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);
3253            return;
3254        }
3255
3256        if (ZEND_NUM_ARGS() < req_args) {
3257            php_error_docref(NULL TSRMLS_CC, E_WARNING, "at least %d parameters are required, %d given", req_args, ZEND_NUM_ARGS());
3258            return;
3259        }
3260
3261        if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, param_spec, &args, &arr_argc, &fci1, &fci1_cache, &fci2, &fci2_cache) == FAILURE) {
3262            return;
3263        }
3264
3265    } else {
3266        php_error_docref(NULL TSRMLS_CC, E_WARNING, "behavior is %d. This should never happen. Please report as a bug", behavior);
3267        return;
3268    }
3269
3270    PHP_ARRAY_CMP_FUNC_BACKUP();
3271
3272    /* for each argument, create and sort list with pointers to the hash buckets */
3273    lists = (Bucket **)safe_emalloc(arr_argc, sizeof(Bucket *), 0);
3274    ptrs = (Bucket **)safe_emalloc(arr_argc, sizeof(Bucket *), 0);
3275    php_set_compare_func(PHP_SORT_STRING TSRMLS_CC);
3276
3277    if (behavior == INTERSECT_NORMAL && data_compare_type == INTERSECT_COMP_DATA_USER) {
3278        BG(user_compare_fci) = *fci_data;
3279        BG(user_compare_fci_cache) = *fci_data_cache;
3280    } else if (behavior & INTERSECT_ASSOC && key_compare_type == INTERSECT_COMP_KEY_USER) {
3281        BG(user_compare_fci) = *fci_key;
3282        BG(user_compare_fci_cache) = *fci_key_cache;
3283    }
3284
3285    for (i = 0; i < arr_argc; i++) {
3286        if (Z_TYPE(args[i]) != IS_ARRAY) {
3287            php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument #%d is not an array", i + 1);
3288            arr_argc = i; /* only free up to i - 1 */
3289            goto out;
3290        }
3291        hash = Z_ARRVAL(args[i]);
3292        list = (Bucket *) pemalloc((hash->nNumOfElements + 1) * sizeof(Bucket), hash->u.flags & HASH_FLAG_PERSISTENT);
3293        if (!list) {
3294            PHP_ARRAY_CMP_FUNC_RESTORE();
3295
3296            efree(ptrs);
3297            efree(lists);
3298            RETURN_FALSE;
3299        }
3300        lists[i] = list;
3301        ptrs[i] = list;
3302        for (idx = 0; idx < hash->nNumUsed; idx++) {
3303            p = hash->arData + idx;
3304            if (Z_TYPE(p->val) == IS_UNDEF) continue;
3305            *list++ = *p;
3306        }
3307        ZVAL_UNDEF(&list->val);
3308        if (behavior == INTERSECT_NORMAL) {
3309            zend_qsort((void *) lists[i], hash->nNumOfElements, sizeof(Bucket), intersect_data_compare_func TSRMLS_CC);
3310        } else if (behavior & INTERSECT_ASSOC) { /* triggered also when INTERSECT_KEY */
3311            zend_qsort((void *) lists[i], hash->nNumOfElements, sizeof(Bucket), intersect_key_compare_func TSRMLS_CC);
3312        }
3313    }
3314
3315    /* copy the argument array */
3316    RETVAL_ZVAL(&args[0], 1, 0);
3317    if (Z_ARRVAL_P(return_value) == &EG(symbol_table).ht) {
3318        HashTable *old_ht = Z_ARRVAL_P(return_value);
3319
3320        ZVAL_NEW_ARR(return_value);
3321        zend_array_dup(Z_ARRVAL_P(return_value), old_ht);
3322    }
3323
3324    /* go through the lists and look for common values */
3325    while (Z_TYPE(ptrs[0]->val) != IS_UNDEF) {
3326        if ((behavior & INTERSECT_ASSOC) /* triggered also when INTERSECT_KEY */
3327            &&
3328            key_compare_type == INTERSECT_COMP_KEY_USER) {
3329
3330            BG(user_compare_fci) = *fci_key;
3331            BG(user_compare_fci_cache) = *fci_key_cache;
3332        }
3333
3334        for (i = 1; i < arr_argc; i++) {
3335            if (behavior & INTERSECT_NORMAL) {
3336                while (Z_TYPE(ptrs[i]->val) != IS_UNDEF && (0 < (c = intersect_data_compare_func(ptrs[0], ptrs[i] TSRMLS_CC)))) {
3337                    ptrs[i]++;
3338                }
3339            } else if (behavior & INTERSECT_ASSOC) { /* triggered also when INTERSECT_KEY */
3340                while (Z_TYPE(ptrs[i]->val) != IS_UNDEF && (0 < (c = intersect_key_compare_func(ptrs[0], ptrs[i] TSRMLS_CC)))) {
3341                    ptrs[i]++;
3342                }
3343                if ((!c && Z_TYPE(ptrs[i]->val) != IS_UNDEF) && (behavior == INTERSECT_ASSOC)) { /* only when INTERSECT_ASSOC */
3344                    /* this means that ptrs[i] is not NULL so we can compare
3345                     * and "c==0" is from last operation
3346                     * in this branch of code we enter only when INTERSECT_ASSOC
3347                     * since when we have INTERSECT_KEY compare of data is not wanted. */
3348                    if (data_compare_type == INTERSECT_COMP_DATA_USER) {
3349                        BG(user_compare_fci) = *fci_data;
3350                        BG(user_compare_fci_cache) = *fci_data_cache;
3351                    }
3352                    if (intersect_data_compare_func(ptrs[0], ptrs[i] TSRMLS_CC) != 0) {
3353                        c = 1;
3354                        if (key_compare_type == INTERSECT_COMP_KEY_USER) {
3355                            BG(user_compare_fci) = *fci_key;
3356                            BG(user_compare_fci_cache) = *fci_key_cache;
3357                            /* When KEY_USER, the last parameter is always the callback */
3358                        }
3359                        /* we are going to the break */
3360                    } else {
3361                        /* continue looping */
3362                    }
3363                }
3364            }
3365            if (Z_TYPE(ptrs[i]->val) == IS_UNDEF) {
3366                /* delete any values corresponding to remains of ptrs[0] */
3367                /* and exit because they do not present in at least one of */
3368                /* the other arguments */
3369                for (;;) {
3370                    p = ptrs[0]++;
3371                    if (Z_TYPE(p->val) == IS_UNDEF) {
3372                        goto out;
3373                    }
3374                    if (p->key == NULL) {
3375                        zend_hash_index_del(Z_ARRVAL_P(return_value), p->h);
3376                    } else {
3377                        zend_hash_del(Z_ARRVAL_P(return_value), p->key);
3378                    }
3379                }
3380            }
3381            if (c) /* here we get if not all are equal */
3382                break;
3383            ptrs[i]++;
3384        }
3385        if (c) {
3386            /* Value of ptrs[0] not in all arguments, delete all entries */
3387            /* with value < value of ptrs[i] */
3388            for (;;) {
3389                p = ptrs[0];
3390                if (p->key == NULL) {
3391                    zend_hash_index_del(Z_ARRVAL_P(return_value), p->h);
3392                } else {
3393                    zend_hash_del(Z_ARRVAL_P(return_value), p->key);
3394                }
3395                if (Z_TYPE((++ptrs[0])->val) == IS_UNDEF) {
3396                    goto out;
3397                }
3398                if (behavior == INTERSECT_NORMAL) {
3399                    if (0 <= intersect_data_compare_func(ptrs[0], ptrs[i] TSRMLS_CC)) {
3400                        break;
3401                    }
3402                } else if (behavior & INTERSECT_ASSOC) { /* triggered also when INTERSECT_KEY */
3403                    /* no need of looping because indexes are unique */
3404                    break;
3405                }
3406            }
3407        } else {
3408            /* ptrs[0] is present in all the arguments */
3409            /* Skip all entries with same value as ptrs[0] */
3410            for (;;) {
3411                if (Z_TYPE((++ptrs[0])->val) == IS_UNDEF) {
3412                    goto out;
3413                }
3414                if (behavior == INTERSECT_NORMAL) {
3415                    if (intersect_data_compare_func(ptrs[0] - 1, ptrs[0] TSRMLS_CC)) {
3416                        break;
3417                    }
3418                } else if (behavior & INTERSECT_ASSOC) { /* triggered also when INTERSECT_KEY */
3419                    /* no need of looping because indexes are unique */
3420                    break;
3421                }
3422            }
3423        }
3424    }
3425out:
3426    for (i = 0; i < arr_argc; i++) {
3427        hash = Z_ARRVAL(args[i]);
3428        pefree(lists[i], hash->u.flags & HASH_FLAG_PERSISTENT);
3429    }
3430
3431    PHP_ARRAY_CMP_FUNC_RESTORE();
3432
3433    efree(ptrs);
3434    efree(lists);
3435}
3436/* }}} */
3437
3438/* {{{ proto array array_intersect_key(array arr1, array arr2 [, array ...])
3439   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. */
3440PHP_FUNCTION(array_intersect_key)
3441{
3442    php_array_intersect_key(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_COMP_DATA_NONE);
3443}
3444/* }}} */
3445
3446/* {{{ proto array array_intersect_ukey(array arr1, array arr2 [, array ...], callback key_compare_func)
3447   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. */
3448PHP_FUNCTION(array_intersect_ukey)
3449{
3450    php_array_intersect(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_KEY, INTERSECT_COMP_DATA_INTERNAL, INTERSECT_COMP_KEY_USER);
3451}
3452/* }}} */
3453
3454/* {{{ proto array array_intersect(array arr1, array arr2 [, array ...])
3455   Returns the entries of arr1 that have values which are present in all the other arguments */
3456PHP_FUNCTION(array_intersect)
3457{
3458    php_array_intersect(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_NORMAL, INTERSECT_COMP_DATA_INTERNAL, INTERSECT_COMP_KEY_INTERNAL);
3459}
3460/* }}} */
3461
3462/* {{{ proto array array_uintersect(array arr1, array arr2 [, array ...], callback data_compare_func)
3463   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. */
3464PHP_FUNCTION(array_uintersect)
3465{
3466    php_array_intersect(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_NORMAL, INTERSECT_COMP_DATA_USER, INTERSECT_COMP_KEY_INTERNAL);
3467}
3468/* }}} */
3469
3470/* {{{ proto array array_intersect_assoc(array arr1, array arr2 [, array ...])
3471   Returns the entries of arr1 that have values which are present in all the other arguments. Keys are used to do more restrictive check */
3472PHP_FUNCTION(array_intersect_assoc)
3473{
3474    php_array_intersect_key(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_COMP_DATA_INTERNAL);
3475}
3476/* }}} */
3477
3478/* {{{ proto array array_intersect_uassoc(array arr1, array arr2 [, array ...], callback key_compare_func) U
3479   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. */
3480PHP_FUNCTION(array_intersect_uassoc)
3481{
3482    php_array_intersect(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_ASSOC, INTERSECT_COMP_DATA_INTERNAL, INTERSECT_COMP_KEY_USER);
3483}
3484/* }}} */
3485
3486/* {{{ proto array array_uintersect_assoc(array arr1, array arr2 [, array ...], callback data_compare_func) U
3487   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. */
3488PHP_FUNCTION(array_uintersect_assoc)
3489{
3490    php_array_intersect_key(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_COMP_DATA_USER);
3491}
3492/* }}} */
3493
3494/* {{{ proto array array_uintersect_uassoc(array arr1, array arr2 [, array ...], callback data_compare_func, callback key_compare_func)
3495   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. */
3496PHP_FUNCTION(array_uintersect_uassoc)
3497{
3498    php_array_intersect(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_ASSOC, INTERSECT_COMP_DATA_USER, INTERSECT_COMP_KEY_USER);
3499}
3500/* }}} */
3501
3502static void php_array_diff_key(INTERNAL_FUNCTION_PARAMETERS, int data_compare_type) /* {{{ */
3503{
3504    uint idx;
3505    Bucket *p;
3506    int argc, i;
3507    zval *args;
3508    int (*diff_data_compare_func)(zval *, zval * TSRMLS_DC) = NULL;
3509    zend_bool ok;
3510    zval *val, *data;
3511
3512    /* Get the argument count */
3513    argc = ZEND_NUM_ARGS();
3514    if (data_compare_type == DIFF_COMP_DATA_USER) {
3515        if (argc < 3) {
3516            php_error_docref(NULL TSRMLS_CC, E_WARNING, "at least 3 parameters are required, %d given", ZEND_NUM_ARGS());
3517            return;
3518        }
3519        if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "+f", &args, &argc, &BG(user_compare_fci), &BG(user_compare_fci_cache)) == FAILURE) {
3520            return;
3521        }
3522        diff_data_compare_func = zval_user_compare;
3523    } else {
3524        if (argc < 2) {
3525            php_error_docref(NULL TSRMLS_CC, E_WARNING, "at least 2 parameters are required, %d given", ZEND_NUM_ARGS());
3526            return;
3527        }
3528        if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "+", &args, &argc) == FAILURE) {
3529            return;
3530        }
3531        if (data_compare_type == DIFF_COMP_DATA_INTERNAL) {
3532            diff_data_compare_func = zval_compare;
3533        }
3534    }
3535
3536    for (i = 0; i < argc; i++) {
3537        if (Z_TYPE(args[i]) != IS_ARRAY) {
3538            php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument #%d is not an array", i + 1);
3539            RETURN_NULL();
3540        }
3541    }
3542
3543    array_init(return_value);
3544
3545    for (idx = 0; idx < Z_ARRVAL(args[0])->nNumUsed; idx++) {
3546        p = Z_ARRVAL(args[0])->arData + idx;
3547        val = &p->val;
3548        if (Z_TYPE_P(val) == IS_UNDEF) continue;
3549        if (Z_ISREF_P(val) && Z_REFCOUNT_P(val) == 1) {
3550            ZVAL_UNREF(val);
3551        }
3552        if (p->key == NULL) {
3553            ok = 1;
3554            for (i = 1; i < argc; i++) {
3555                if ((data = zend_hash_index_find(Z_ARRVAL(args[i]), p->h)) != NULL &&
3556                    (!diff_data_compare_func ||
3557                    diff_data_compare_func(val, data TSRMLS_CC) == 0)
3558                ) {
3559                    ok = 0;
3560                    break;
3561                }
3562            }
3563            if (ok) {
3564                if (Z_REFCOUNTED_P(val)) {
3565                    Z_ADDREF_P(val);
3566                }
3567                zend_hash_index_update(Z_ARRVAL_P(return_value), p->h, val);
3568            }
3569        } else {
3570            ok = 1;
3571            for (i = 1; i < argc; i++) {
3572                if ((data = zend_hash_find(Z_ARRVAL(args[i]), p->key)) != NULL &&
3573                    (!diff_data_compare_func ||
3574                    diff_data_compare_func(val, data TSRMLS_CC) == 0)
3575                ) {
3576                    ok = 0;
3577                    break;
3578                }
3579            }
3580            if (ok) {
3581                if (Z_REFCOUNTED_P(val)) {
3582                    Z_ADDREF_P(val);
3583                }
3584                zend_hash_update(Z_ARRVAL_P(return_value), p->key, val);
3585            }
3586        }
3587    }
3588}
3589/* }}} */
3590
3591static void php_array_diff(INTERNAL_FUNCTION_PARAMETERS, int behavior, int data_compare_type, int key_compare_type) /* {{{ */
3592{
3593    zval *args = NULL;
3594    HashTable *hash;
3595    int arr_argc, i, c;
3596    uint idx;
3597    Bucket **lists, *list, **ptrs, *p;
3598    int req_args;
3599    char *param_spec;
3600    zend_fcall_info fci1, fci2;
3601    zend_fcall_info_cache fci1_cache = empty_fcall_info_cache, fci2_cache = empty_fcall_info_cache;
3602    zend_fcall_info *fci_key = NULL, *fci_data;
3603    zend_fcall_info_cache *fci_key_cache = NULL, *fci_data_cache;
3604    PHP_ARRAY_CMP_FUNC_VARS;
3605
3606    int (*diff_key_compare_func)(const void *, const void * TSRMLS_DC);
3607    int (*diff_data_compare_func)(const void *, const void * TSRMLS_DC);
3608
3609    if (behavior == DIFF_NORMAL) {
3610        diff_key_compare_func = php_array_key_compare;
3611
3612        if (data_compare_type == DIFF_COMP_DATA_INTERNAL) {
3613            /* array_diff */
3614            req_args = 2;
3615            param_spec = "+";
3616            diff_data_compare_func = php_array_data_compare;
3617        } else if (data_compare_type == DIFF_COMP_DATA_USER) {
3618            /* array_udiff */
3619            req_args = 3;
3620            param_spec = "+f";
3621            diff_data_compare_func = php_array_user_compare;
3622        } else {
3623            php_error_docref(NULL TSRMLS_CC, E_WARNING, "data_compare_type is %d. This should never happen. Please report as a bug", data_compare_type);
3624            return;
3625        }
3626
3627        if (ZEND_NUM_ARGS() < req_args) {
3628            php_error_docref(NULL TSRMLS_CC, E_WARNING, "at least %d parameters are required, %d given", req_args, ZEND_NUM_ARGS());
3629            return;
3630        }
3631
3632        if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, param_spec, &args, &arr_argc, &fci1, &fci1_cache) == FAILURE) {
3633            return;
3634        }
3635        fci_data = &fci1;
3636        fci_data_cache = &fci1_cache;
3637
3638    } else if (behavior & DIFF_ASSOC) { /* triggered also if DIFF_KEY */
3639        /* DIFF_KEY is subset of DIFF_ASSOC. When having the former
3640         * no comparison of the data is done (part of DIFF_ASSOC) */
3641
3642        if (data_compare_type == DIFF_COMP_DATA_INTERNAL && key_compare_type == DIFF_COMP_KEY_INTERNAL) {
3643            /* array_diff_assoc() or array_diff_key() */
3644            req_args = 2;
3645            param_spec = "+";
3646            diff_key_compare_func = php_array_key_compare;
3647            diff_data_compare_func = php_array_data_compare;
3648        } else if (data_compare_type == DIFF_COMP_DATA_USER && key_compare_type == DIFF_COMP_KEY_INTERNAL) {
3649            /* array_udiff_assoc() */
3650            req_args = 3;
3651            param_spec = "+f";
3652            diff_key_compare_func = php_array_key_compare;
3653            diff_data_compare_func = php_array_user_compare;
3654            fci_data = &fci1;
3655            fci_data_cache = &fci1_cache;
3656        } else if (data_compare_type == DIFF_COMP_DATA_INTERNAL && key_compare_type == DIFF_COMP_KEY_USER) {
3657            /* array_diff_uassoc() or array_diff_ukey() */
3658            req_args = 3;
3659            param_spec = "+f";
3660            diff_key_compare_func = php_array_user_key_compare;
3661            diff_data_compare_func = php_array_data_compare;
3662            fci_key = &fci1;
3663            fci_key_cache = &fci1_cache;
3664        } else if (data_compare_type == DIFF_COMP_DATA_USER && key_compare_type == DIFF_COMP_KEY_USER) {
3665            /* array_udiff_uassoc() */
3666            req_args = 4;
3667            param_spec = "+ff";
3668            diff_key_compare_func = php_array_user_key_compare;
3669            diff_data_compare_func = php_array_user_compare;
3670            fci_data = &fci1;
3671            fci_data_cache = &fci1_cache;
3672            fci_key = &fci2;
3673            fci_key_cache = &fci2_cache;
3674        } else {
3675            php_error_docref(NULL TSRMLS_CC, 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);
3676            return;
3677        }
3678
3679        if (ZEND_NUM_ARGS() < req_args) {
3680            php_error_docref(NULL TSRMLS_CC, E_WARNING, "at least %d parameters are required, %d given", req_args, ZEND_NUM_ARGS());
3681            return;
3682        }
3683
3684        if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, param_spec, &args, &arr_argc, &fci1, &fci1_cache, &fci2, &fci2_cache) == FAILURE) {
3685            return;
3686        }
3687
3688    } else {
3689        php_error_docref(NULL TSRMLS_CC, E_WARNING, "behavior is %d. This should never happen. Please report as a bug", behavior);
3690        return;
3691    }
3692
3693    PHP_ARRAY_CMP_FUNC_BACKUP();
3694
3695    /* for each argument, create and sort list with pointers to the hash buckets */
3696    lists = (Bucket **)safe_emalloc(arr_argc, sizeof(Bucket *), 0);
3697    ptrs = (Bucket **)safe_emalloc(arr_argc, sizeof(Bucket *), 0);
3698    php_set_compare_func(PHP_SORT_STRING TSRMLS_CC);
3699
3700    if (behavior == DIFF_NORMAL && data_compare_type == DIFF_COMP_DATA_USER) {
3701        BG(user_compare_fci) = *fci_data;
3702        BG(user_compare_fci_cache) = *fci_data_cache;
3703    } else if (behavior & DIFF_ASSOC && key_compare_type == DIFF_COMP_KEY_USER) {
3704        BG(user_compare_fci) = *fci_key;
3705        BG(user_compare_fci_cache) = *fci_key_cache;
3706    }
3707
3708    for (i = 0; i < arr_argc; i++) {
3709        if (Z_TYPE(args[i]) != IS_ARRAY) {
3710            php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument #%d is not an array", i + 1);
3711            arr_argc = i; /* only free up to i - 1 */
3712            goto out;
3713        }
3714        hash = Z_ARRVAL(args[i]);
3715        list = (Bucket *) pemalloc((hash->nNumOfElements + 1) * sizeof(Bucket), hash->u.flags & HASH_FLAG_PERSISTENT);
3716        if (!list) {
3717            PHP_ARRAY_CMP_FUNC_RESTORE();
3718
3719            efree(ptrs);
3720            efree(lists);
3721            RETURN_FALSE;
3722        }
3723        lists[i] = list;
3724        ptrs[i] = list;
3725        for (idx = 0; idx < hash->nNumUsed; idx++) {
3726            p = hash->arData + idx;
3727            if (Z_TYPE(p->val) == IS_UNDEF) continue;
3728            *list++ = *p;
3729        }
3730        ZVAL_UNDEF(&list->val);
3731        if (behavior == DIFF_NORMAL) {
3732            zend_qsort((void *) lists[i], hash->nNumOfElements, sizeof(Bucket), diff_data_compare_func TSRMLS_CC);
3733        } else if (behavior & DIFF_ASSOC) { /* triggered also when DIFF_KEY */
3734            zend_qsort((void *) lists[i], hash->nNumOfElements, sizeof(Bucket), diff_key_compare_func TSRMLS_CC);
3735        }
3736    }
3737
3738    /* copy the argument array */
3739    RETVAL_ZVAL(&args[0], 1, 0);
3740    if (Z_ARRVAL_P(return_value) == &EG(symbol_table).ht) {
3741        HashTable *old_ht = Z_ARRVAL_P(return_value);
3742
3743        ZVAL_NEW_ARR(return_value);
3744        zend_array_dup(Z_ARRVAL_P(return_value), old_ht);
3745    }
3746
3747    /* go through the lists and look for values of ptr[0] that are not in the others */
3748    while (Z_TYPE(ptrs[0]->val) != IS_UNDEF) {
3749        if ((behavior & DIFF_ASSOC) /* triggered also when DIFF_KEY */
3750            &&
3751            key_compare_type == DIFF_COMP_KEY_USER
3752        ) {
3753            BG(user_compare_fci) = *fci_key;
3754            BG(user_compare_fci_cache) = *fci_key_cache;
3755        }
3756        c = 1;
3757        for (i = 1; i < arr_argc; i++) {
3758            Bucket *ptr = ptrs[i];
3759            if (behavior == DIFF_NORMAL) {
3760                while (Z_TYPE(ptrs[i]->val) != IS_UNDEF && (0 < (c = diff_data_compare_func(ptrs[0], ptrs[i] TSRMLS_CC)))) {
3761                    ptrs[i]++;
3762                }
3763            } else if (behavior & DIFF_ASSOC) { /* triggered also when DIFF_KEY */
3764                while (Z_TYPE(ptr->val) != IS_UNDEF && (0 != (c = diff_key_compare_func(ptrs[0], ptr TSRMLS_CC)))) {
3765                    ptr++;
3766                }
3767            }
3768            if (!c) {
3769                if (behavior == DIFF_NORMAL) {
3770                    if (Z_TYPE(ptrs[i]->val) != IS_UNDEF) {
3771                        ptrs[i]++;
3772                    }
3773                    break;
3774                } else if (behavior == DIFF_ASSOC) {  /* only when DIFF_ASSOC */
3775                    /* In this branch is execute only when DIFF_ASSOC. If behavior == DIFF_KEY
3776                     * data comparison is not needed - skipped. */
3777                    if (Z_TYPE(ptr->val) != IS_UNDEF) {
3778                        if (data_compare_type == DIFF_COMP_DATA_USER) {
3779                            BG(user_compare_fci) = *fci_data;
3780                            BG(user_compare_fci_cache) = *fci_data_cache;
3781                        }
3782                        if (diff_data_compare_func(ptrs[0], ptr TSRMLS_CC) != 0) {
3783                            /* the data is not the same */
3784                            c = -1;
3785                            if (key_compare_type == DIFF_COMP_KEY_USER) {
3786                                BG(user_compare_fci) = *fci_key;
3787                                BG(user_compare_fci_cache) = *fci_key_cache;
3788                            }
3789                        } else {
3790                            break;
3791                            /* we have found the element in other arrays thus we don't want it
3792                             * in the return_value -> delete from there */
3793                        }
3794                    }
3795                } else if (behavior == DIFF_KEY) { /* only when DIFF_KEY */
3796                    /* the behavior here differs from INTERSECT_KEY in php_intersect
3797                     * since in the "diff" case we have to remove the entry from
3798                     * return_value while when doing intersection the entry must not
3799                     * be deleted. */
3800                    break; /* remove the key */
3801                }
3802            }
3803        }
3804        if (!c) {
3805            /* ptrs[0] in one of the other arguments */
3806            /* delete all entries with value as ptrs[0] */
3807            for (;;) {
3808                p = ptrs[0];
3809                if (p->key == NULL) {
3810                    zend_hash_index_del(Z_ARRVAL_P(return_value), p->h);
3811                } else {
3812                    zend_hash_del(Z_ARRVAL_P(return_value), p->key);
3813                }
3814                if (Z_TYPE((++ptrs[0])->val) == IS_UNDEF) {
3815                    goto out;
3816                }
3817                if (behavior == DIFF_NORMAL) {
3818                    if (diff_data_compare_func(ptrs[0] - 1, ptrs[0] TSRMLS_CC)) {
3819                        break;
3820                    }
3821                } else if (behavior & DIFF_ASSOC) { /* triggered also when DIFF_KEY */
3822                    /* in this case no array_key_compare is needed */
3823                    break;
3824                }
3825            }
3826        } else {
3827            /* ptrs[0] in none of the other arguments */
3828            /* skip all entries with value as ptrs[0] */
3829            for (;;) {
3830                if (Z_TYPE((++ptrs[0])->val) == IS_UNDEF) {
3831                    goto out;
3832                }
3833                if (behavior == DIFF_NORMAL) {
3834                    if (diff_data_compare_func(ptrs[0] - 1, ptrs[0] TSRMLS_CC)) {
3835                        break;
3836                    }
3837                } else if (behavior & DIFF_ASSOC) { /* triggered also when DIFF_KEY */
3838                    /* in this case no array_key_compare is needed */
3839                    break;
3840                }
3841            }
3842        }
3843    }
3844out:
3845    for (i = 0; i < arr_argc; i++) {
3846        hash = Z_ARRVAL(args[i]);
3847        pefree(lists[i], hash->u.flags & HASH_FLAG_PERSISTENT);
3848    }
3849
3850    PHP_ARRAY_CMP_FUNC_RESTORE();
3851
3852    efree(ptrs);
3853    efree(lists);
3854}
3855/* }}} */
3856
3857/* {{{ proto array array_diff_key(array arr1, array arr2 [, array ...])
3858   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. */
3859PHP_FUNCTION(array_diff_key)
3860{
3861    php_array_diff_key(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_COMP_DATA_NONE);
3862}
3863/* }}} */
3864
3865/* {{{ proto array array_diff_ukey(array arr1, array arr2 [, array ...], callback key_comp_func)
3866   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. */
3867PHP_FUNCTION(array_diff_ukey)
3868{
3869    php_array_diff(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_KEY, DIFF_COMP_DATA_INTERNAL, DIFF_COMP_KEY_USER);
3870}
3871/* }}} */
3872
3873/* {{{ proto array array_diff(array arr1, array arr2 [, array ...])
3874   Returns the entries of arr1 that have values which are not present in any of the others arguments. */
3875PHP_FUNCTION(array_diff)
3876{
3877    php_array_diff(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_NORMAL, DIFF_COMP_DATA_INTERNAL, DIFF_COMP_KEY_INTERNAL);
3878}
3879/* }}} */
3880
3881/* {{{ proto array array_udiff(array arr1, array arr2 [, array ...], callback data_comp_func)
3882   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. */
3883PHP_FUNCTION(array_udiff)
3884{
3885    php_array_diff(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_NORMAL, DIFF_COMP_DATA_USER, DIFF_COMP_KEY_INTERNAL);
3886}
3887/* }}} */
3888
3889/* {{{ proto array array_diff_assoc(array arr1, array arr2 [, array ...])
3890   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 */
3891PHP_FUNCTION(array_diff_assoc)
3892{
3893    php_array_diff_key(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_COMP_DATA_INTERNAL);
3894}
3895/* }}} */
3896
3897/* {{{ proto array array_diff_uassoc(array arr1, array arr2 [, array ...], callback data_comp_func)
3898   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. */
3899PHP_FUNCTION(array_diff_uassoc)
3900{
3901    php_array_diff(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_ASSOC, DIFF_COMP_DATA_INTERNAL, DIFF_COMP_KEY_USER);
3902}
3903/* }}} */
3904
3905/* {{{ proto array array_udiff_assoc(array arr1, array arr2 [, array ...], callback key_comp_func)
3906   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. */
3907PHP_FUNCTION(array_udiff_assoc)
3908{
3909    php_array_diff_key(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_COMP_DATA_USER);
3910}
3911/* }}} */
3912
3913/* {{{ proto array array_udiff_uassoc(array arr1, array arr2 [, array ...], callback data_comp_func, callback key_comp_func)
3914   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. */
3915PHP_FUNCTION(array_udiff_uassoc)
3916{
3917    php_array_diff(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_ASSOC, DIFF_COMP_DATA_USER, DIFF_COMP_KEY_USER);
3918}
3919/* }}} */
3920
3921#define MULTISORT_ORDER 0
3922#define MULTISORT_TYPE  1
3923#define MULTISORT_LAST  2
3924
3925PHPAPI int php_multisort_compare(const void *a, const void *b TSRMLS_DC) /* {{{ */
3926{
3927    Bucket *ab = *(Bucket **)a;
3928    Bucket *bb = *(Bucket **)b;
3929    int r;
3930    int result = 0;
3931    zval temp;
3932
3933    r = 0;
3934    do {
3935        php_set_compare_func(ARRAYG(multisort_flags)[MULTISORT_TYPE][r] TSRMLS_CC);
3936
3937        ARRAYG(compare_func)(&temp, &ab[r].val, &bb[r].val TSRMLS_CC);
3938        result = ARRAYG(multisort_flags)[MULTISORT_ORDER][r] * Z_IVAL(temp);
3939        if (result != 0) {
3940            return result;
3941        }
3942        r++;
3943    } while (Z_TYPE(ab[r].val) != IS_UNDEF);
3944
3945    return result;
3946}
3947/* }}} */
3948
3949#define MULTISORT_ABORT                     \
3950    for (k = 0; k < MULTISORT_LAST; k++)    \
3951        efree(ARRAYG(multisort_flags)[k]);  \
3952    efree(arrays);                          \
3953    RETURN_FALSE;
3954
3955/* {{{ 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]], ...])
3956   Sort multiple arrays at once similar to how ORDER BY clause works in SQL */
3957PHP_FUNCTION(array_multisort)
3958{
3959    zval*           args;
3960    zval**          arrays;
3961    Bucket**        indirect;
3962    uint            idx;
3963    Bucket*         p;
3964    HashTable*      hash;
3965    int             argc;
3966    int             array_size;
3967    int             num_arrays = 0;
3968    int             parse_state[MULTISORT_LAST];   /* 0 - flag not allowed 1 - flag allowed */
3969    int             sort_order = PHP_SORT_ASC;
3970    int             sort_type  = PHP_SORT_REGULAR;
3971    int             i, k, n;
3972
3973    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "+", &args, &argc) == FAILURE) {
3974        return;
3975    }
3976
3977    /* Allocate space for storing pointers to input arrays and sort flags. */
3978    arrays = (zval **)ecalloc(argc, sizeof(zval *));
3979    for (i = 0; i < MULTISORT_LAST; i++) {
3980        parse_state[i] = 0;
3981        ARRAYG(multisort_flags)[i] = (int *)ecalloc(argc, sizeof(int));
3982    }
3983
3984    /* Here we go through the input arguments and parse them. Each one can
3985     * be either an array or a sort flag which follows an array. If not
3986     * specified, the sort flags defaults to PHP_SORT_ASC and PHP_SORT_REGULAR
3987     * accordingly. There can't be two sort flags of the same type after an
3988     * array, and the very first argument has to be an array. */
3989    for (i = 0; i < argc; i++) {
3990        zval *arg = &args[i];
3991
3992        ZVAL_DEREF(arg);
3993        if (Z_TYPE_P(arg) == IS_ARRAY) {
3994            if (Z_IMMUTABLE_P(arg)) {
3995                zval_copy_ctor(arg);
3996            }
3997            /* We see the next array, so we update the sort flags of
3998             * the previous array and reset the sort flags. */
3999            if (i > 0) {
4000                ARRAYG(multisort_flags)[MULTISORT_ORDER][num_arrays - 1] = sort_order;
4001                ARRAYG(multisort_flags)[MULTISORT_TYPE][num_arrays - 1] = sort_type;
4002                sort_order = PHP_SORT_ASC;
4003                sort_type = PHP_SORT_REGULAR;
4004            }
4005            arrays[num_arrays++] = arg;
4006
4007            /* Next one may be an array or a list of sort flags. */
4008            for (k = 0; k < MULTISORT_LAST; k++) {
4009                parse_state[k] = 1;
4010            }
4011        } else if (Z_TYPE_P(arg) == IS_INT) {
4012            switch (Z_IVAL_P(arg) & ~PHP_SORT_FLAG_CASE) {
4013                case PHP_SORT_ASC:
4014                case PHP_SORT_DESC:
4015                    /* flag allowed here */
4016                    if (parse_state[MULTISORT_ORDER] == 1) {
4017                        /* Save the flag and make sure then next arg is not the current flag. */
4018                        sort_order = Z_IVAL(args[i]) == PHP_SORT_DESC ? -1 : 1;
4019                        parse_state[MULTISORT_ORDER] = 0;
4020                    } else {
4021                        php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument #%d is expected to be an array or sorting flag that has not already been specified", i + 1);
4022                        MULTISORT_ABORT;
4023                    }
4024                    break;
4025
4026                case PHP_SORT_REGULAR:
4027                case PHP_SORT_NUMERIC:
4028                case PHP_SORT_STRING:
4029                case PHP_SORT_NATURAL:
4030#if HAVE_STRCOLL
4031                case PHP_SORT_LOCALE_STRING:
4032#endif
4033                    /* flag allowed here */
4034                    if (parse_state[MULTISORT_TYPE] == 1) {
4035                        /* Save the flag and make sure then next arg is not the current flag. */
4036                        sort_type = Z_IVAL(args[i]);
4037                        parse_state[MULTISORT_TYPE] = 0;
4038                    } else {
4039                        php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument #%d is expected to be an array or sorting flag that has not already been specified", i + 1);
4040                        MULTISORT_ABORT;
4041                    }
4042                    break;
4043
4044                default:
4045                    php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument #%d is an unknown sort flag", i + 1);
4046                    MULTISORT_ABORT;
4047                    break;
4048
4049            }
4050        } else {
4051            php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument #%d is expected to be an array or a sort flag", i + 1);
4052            MULTISORT_ABORT;
4053        }
4054    }
4055    /* Take care of the last array sort flags. */
4056    ARRAYG(multisort_flags)[MULTISORT_ORDER][num_arrays - 1] = sort_order;
4057    ARRAYG(multisort_flags)[MULTISORT_TYPE][num_arrays - 1] = sort_type;
4058
4059    /* Make sure the arrays are of the same size. */
4060    array_size = zend_hash_num_elements(Z_ARRVAL_P(arrays[0]));
4061    for (i = 0; i < num_arrays; i++) {
4062        if (zend_hash_num_elements(Z_ARRVAL_P(arrays[i])) != array_size) {
4063            php_error_docref(NULL TSRMLS_CC, E_WARNING, "Array sizes are inconsistent");
4064            MULTISORT_ABORT;
4065        }
4066    }
4067
4068    /* If all arrays are empty we don't need to do anything. */
4069    if (array_size < 1) {
4070        for (k = 0; k < MULTISORT_LAST; k++) {
4071            efree(ARRAYG(multisort_flags)[k]);
4072        }
4073        efree(arrays);
4074        RETURN_TRUE;
4075    }
4076
4077    /* Create the indirection array. This array is of size MxN, where
4078     * M is the number of entries in each input array and N is the number
4079     * of the input arrays + 1. The last column is NULL to indicate the end
4080     * of the row. */
4081    indirect = (Bucket **)safe_emalloc(array_size, sizeof(Bucket *), 0);
4082    for (i = 0; i < array_size; i++) {
4083        indirect[i] = (Bucket *)safe_emalloc((num_arrays + 1), sizeof(Bucket), 0);
4084    }
4085    for (i = 0; i < num_arrays; i++) {
4086        k = 0;
4087        for (idx = 0; idx < Z_ARRVAL_P(arrays[i])->nNumUsed; idx++) {
4088            p = Z_ARRVAL_P(arrays[i])->arData + idx;
4089            if (Z_TYPE(p->val) == IS_UNDEF) continue;
4090            indirect[k][i] = *p;
4091            k++;
4092        }
4093    }
4094    for (k = 0; k < array_size; k++) {
4095        ZVAL_UNDEF(&indirect[k][num_arrays].val);
4096    }
4097
4098    /* Do the actual sort magic - bada-bim, bada-boom. */
4099    zend_qsort(indirect, array_size, sizeof(Bucket *), php_multisort_compare TSRMLS_CC);
4100
4101    /* Restructure the arrays based on sorted indirect - this is mostly taken from zend_hash_sort() function. */
4102    HANDLE_BLOCK_INTERRUPTIONS();
4103    for (i = 0; i < num_arrays; i++) {
4104        int repack;
4105
4106        hash = Z_ARRVAL_P(arrays[i]);
4107        hash->nNumUsed = array_size;
4108        hash->nInternalPointer = 0;
4109        repack = !(hash->u.flags & HASH_FLAG_PACKED);
4110
4111        for (n = 0, k = 0; k < array_size; k++) {
4112            hash->arData[k] = indirect[k][i];
4113            if (hash->arData[k].key == NULL) {
4114                hash->arData[k].h = n++;
4115            } else {
4116                repack = 0;
4117            }
4118        }
4119        hash->nNextFreeElement = array_size;
4120        if (repack) {
4121            zend_hash_to_packed(hash);
4122        }
4123    }
4124    HANDLE_UNBLOCK_INTERRUPTIONS();
4125
4126    /* Clean up. */
4127    for (i = 0; i < array_size; i++) {
4128        efree(indirect[i]);
4129    }
4130    efree(indirect);
4131    for (k = 0; k < MULTISORT_LAST; k++) {
4132        efree(ARRAYG(multisort_flags)[k]);
4133    }
4134    efree(arrays);
4135    RETURN_TRUE;
4136}
4137/* }}} */
4138
4139/* {{{ proto mixed array_rand(array input [, int num_req])
4140   Return key/keys for random entry/entries in the array */
4141PHP_FUNCTION(array_rand)
4142{
4143    zval *input;
4144    php_int_t randval, num_req = 1;
4145    int num_avail;
4146    zend_string *string_key;
4147    php_uint_t num_key;
4148
4149    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a|i", &input, &num_req) == FAILURE) {
4150        return;
4151    }
4152
4153    num_avail = zend_hash_num_elements(Z_ARRVAL_P(input));
4154
4155    if (ZEND_NUM_ARGS() > 1) {
4156        if (num_req <= 0 || num_req > num_avail) {
4157            php_error_docref(NULL TSRMLS_CC, E_WARNING, "Second argument has to be between 1 and the number of elements in the array");
4158            return;
4159        }
4160    }
4161
4162    /* Make the return value an array only if we need to pass back more than one result. */
4163    if (num_req > 1) {
4164        array_init_size(return_value, num_req);
4165    }
4166
4167    /* We can't use zend_hash_index_find() because the array may have string keys or gaps. */
4168    ZEND_HASH_FOREACH_KEY(Z_ARRVAL_P(input), num_key, string_key) {
4169        if (!num_req) {
4170            break;
4171        }
4172
4173        randval = php_rand(TSRMLS_C);
4174
4175        if ((double) (randval / (PHP_RAND_MAX + 1.0)) < (double) num_req / (double) num_avail) {
4176            /* If we are returning a single result, just do it. */
4177            if (Z_TYPE_P(return_value) != IS_ARRAY) {
4178                if (string_key) {
4179                    RETURN_STR(STR_COPY(string_key));
4180                } else {
4181                    RETURN_INT(num_key);
4182                }
4183            } else {
4184                /* Append the result to the return value. */
4185                if (string_key) {
4186                    add_next_index_str(return_value, STR_COPY(string_key));
4187                } else {
4188                    add_next_index_int(return_value, num_key);
4189                }
4190            }
4191            num_req--;
4192        }
4193        num_avail--;
4194    } ZEND_HASH_FOREACH_END();
4195}
4196/* }}} */
4197
4198/* {{{ proto mixed array_sum(array input)
4199   Returns the sum of the array entries */
4200PHP_FUNCTION(array_sum)
4201{
4202    zval *input,
4203         *entry,
4204         entry_n;
4205
4206    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a", &input) == FAILURE) {
4207        return;
4208    }
4209
4210    ZVAL_INT(return_value, 0);
4211
4212    ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(input), entry) {
4213        if (Z_TYPE_P(entry) == IS_ARRAY || Z_TYPE_P(entry) == IS_OBJECT) {
4214            continue;
4215        }
4216        ZVAL_DUP(&entry_n, entry);
4217        convert_scalar_to_number(&entry_n TSRMLS_CC);
4218        fast_add_function(return_value, return_value, &entry_n TSRMLS_CC);
4219    } ZEND_HASH_FOREACH_END();
4220}
4221/* }}} */
4222
4223/* {{{ proto mixed array_product(array input)
4224   Returns the product of the array entries */
4225PHP_FUNCTION(array_product)
4226{
4227    zval *input,
4228         *entry,
4229         entry_n;
4230    double dval;
4231
4232    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a", &input) == FAILURE) {
4233        return;
4234    }
4235
4236    ZVAL_INT(return_value, 1);
4237    if (!zend_hash_num_elements(Z_ARRVAL_P(input))) {
4238        return;
4239    }
4240
4241    ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(input), entry) {
4242        if (Z_TYPE_P(entry) == IS_ARRAY || Z_TYPE_P(entry) == IS_OBJECT) {
4243            continue;
4244        }
4245        ZVAL_DUP(&entry_n, entry);
4246        convert_scalar_to_number(&entry_n TSRMLS_CC);
4247
4248        if (Z_TYPE(entry_n) == IS_INT && Z_TYPE_P(return_value) == IS_INT) {
4249            dval = (double)Z_IVAL_P(return_value) * (double)Z_IVAL(entry_n);
4250            if ( (double)PHP_INT_MIN <= dval && dval <= (double)PHP_INT_MAX ) {
4251                Z_IVAL_P(return_value) *= Z_IVAL(entry_n);
4252                continue;
4253            }
4254        }
4255        convert_to_double(return_value);
4256        convert_to_double(&entry_n);
4257        Z_DVAL_P(return_value) *= Z_DVAL(entry_n);
4258    } ZEND_HASH_FOREACH_END();
4259}
4260/* }}} */
4261
4262/* {{{ proto mixed array_reduce(array input, mixed callback [, mixed initial])
4263   Iteratively reduce the array to a single value via the callback. */
4264PHP_FUNCTION(array_reduce)
4265{
4266    zval *input;
4267    zval args[2];
4268    zval *operand;
4269    zval result;
4270    zval retval;
4271    zend_fcall_info fci;
4272    zend_fcall_info_cache fci_cache = empty_fcall_info_cache;
4273    zval *initial = NULL;
4274    HashTable *htbl;
4275
4276    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "af|z", &input, &fci, &fci_cache, &initial) == FAILURE) {
4277        return;
4278    }
4279
4280
4281    if (ZEND_NUM_ARGS() > 2) {
4282        ZVAL_DUP(&result, initial);
4283    } else {
4284        ZVAL_NULL(&result);
4285    }
4286
4287    /* (zval **)input points to an element of argument stack
4288     * the base pointer of which is subject to change.
4289     * thus we need to keep the pointer to the hashtable for safety */
4290    htbl = Z_ARRVAL_P(input);
4291
4292    if (zend_hash_num_elements(htbl) == 0) {
4293        RETURN_ZVAL(&result, 1, 1);
4294    }
4295
4296    fci.retval = &retval;
4297    fci.param_count = 2;
4298    fci.no_separation = 0;
4299
4300    ZEND_HASH_FOREACH_VAL(htbl, operand) {
4301        ZVAL_COPY(&args[0], &result);
4302        ZVAL_COPY(&args[1], operand);
4303        fci.params = args;
4304
4305        if (zend_call_function(&fci, &fci_cache TSRMLS_CC) == SUCCESS && Z_TYPE(retval) != IS_UNDEF) {
4306            zval_ptr_dtor(&args[1]);
4307            zval_ptr_dtor(&args[0]);
4308            zval_ptr_dtor(&result);
4309            ZVAL_COPY_VALUE(&result, &retval);
4310        } else {
4311            zval_ptr_dtor(&args[1]);
4312            zval_ptr_dtor(&args[0]);
4313            php_error_docref(NULL TSRMLS_CC, E_WARNING, "An error occurred while invoking the reduction callback");
4314            return;
4315        }
4316    } ZEND_HASH_FOREACH_END();
4317
4318    RETVAL_ZVAL(&result, 1, 1);
4319}
4320/* }}} */
4321
4322/* {{{ proto array array_filter(array input [, mixed callback])
4323   Filters elements from the array via the callback. */
4324PHP_FUNCTION(array_filter)
4325{
4326    zval *array;
4327    zval *operand;
4328    zval args[2];
4329    zval retval;
4330    zend_bool have_callback = 0;
4331    php_int_t use_type = 0;
4332    zend_string *string_key;
4333    zend_fcall_info fci = empty_fcall_info;
4334    zend_fcall_info_cache fci_cache = empty_fcall_info_cache;
4335    php_uint_t num_key;
4336
4337    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "a|fi", &array, &fci, &fci_cache, &use_type) == FAILURE) {
4338        return;
4339    }
4340
4341    array_init(return_value);
4342    if (zend_hash_num_elements(Z_ARRVAL_P(array)) == 0) {
4343        return;
4344    }
4345
4346    if (ZEND_NUM_ARGS() > 1) {
4347        have_callback = 1;
4348        fci.no_separation = 0;
4349        fci.retval = &retval;
4350        fci.param_count = 1;
4351    }
4352
4353    ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(array), num_key, string_key, operand) {
4354        if (have_callback) {
4355            if (use_type) {
4356                /* Set up the key */
4357                if (!string_key) {
4358                    if (use_type == ARRAY_FILTER_USE_BOTH) {
4359                        fci.param_count = 2;
4360                        ZVAL_INT(&args[1], num_key);
4361                    } else if (use_type == ARRAY_FILTER_USE_KEY) {
4362                        ZVAL_INT(&args[0], num_key);
4363                    }
4364                } else {
4365                    if (use_type == ARRAY_FILTER_USE_BOTH) {
4366                        ZVAL_STR(&args[1], STR_COPY(string_key));
4367                    } else if (use_type == ARRAY_FILTER_USE_KEY) {
4368                        ZVAL_STR(&args[0], STR_COPY(string_key));
4369                    }
4370                }
4371            }
4372            if (use_type != ARRAY_FILTER_USE_KEY) {
4373                ZVAL_COPY(&args[0], operand);
4374            }
4375            fci.params = args;
4376
4377            if (zend_call_function(&fci, &fci_cache TSRMLS_CC) == SUCCESS) {
4378                zval_ptr_dtor(&args[0]);
4379                if (use_type == ARRAY_FILTER_USE_BOTH) {
4380                    zval_ptr_dtor(&args[1]);
4381                }
4382                if (!Z_ISUNDEF(retval)) {
4383                    int retval_true = zend_is_true(&retval TSRMLS_CC);
4384
4385                    zval_ptr_dtor(&retval);
4386                    if (!retval_true) {
4387                        continue;
4388                    }
4389                } else {
4390                    continue;
4391                }
4392            } else {
4393                zval_ptr_dtor(&args[0]);
4394                if (use_type == ARRAY_FILTER_USE_BOTH) {
4395                    zval_ptr_dtor(&args[1]);
4396                }
4397                php_error_docref(NULL TSRMLS_CC, E_WARNING, "An error occurred while invoking the filter callback");
4398                return;
4399            }
4400        } else if (!zend_is_true(operand TSRMLS_CC)) {
4401            continue;
4402        }
4403
4404        zval_add_ref(operand);
4405        if (string_key) {
4406            zend_hash_update(Z_ARRVAL_P(return_value), string_key, operand);
4407        } else {
4408            zend_hash_index_update(Z_ARRVAL_P(return_value), num_key, operand);
4409        }
4410    } ZEND_HASH_FOREACH_END();
4411}
4412/* }}} */
4413
4414/* {{{ proto array array_map(mixed callback, array input1 [, array input2 ,...])
4415   Applies the callback to the elements in given arrays. */
4416PHP_FUNCTION(array_map)
4417{
4418    zval *arrays = NULL;
4419    int n_arrays = 0;
4420    zval result;
4421    zend_fcall_info fci = empty_fcall_info;
4422    zend_fcall_info_cache fci_cache = empty_fcall_info_cache;
4423    int i, k, maxlen = 0;
4424
4425#ifndef FAST_ZPP
4426    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "f!+", &fci, &fci_cache, &arrays, &n_arrays) == FAILURE) {
4427        return;
4428    }
4429#else
4430    ZEND_PARSE_PARAMETERS_START(2, -1)
4431        Z_PARAM_FUNC_EX(fci, fci_cache, 1, 0)
4432        Z_PARAM_VARIADIC('+', arrays, n_arrays)
4433    ZEND_PARSE_PARAMETERS_END();
4434#endif
4435
4436    RETVAL_NULL();
4437
4438    if (n_arrays == 1) {
4439        php_uint_t num_key;
4440        zend_string *str_key;
4441        zval *zv, arg;
4442
4443        if (Z_TYPE(arrays[0]) != IS_ARRAY) {
4444            php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument #%d should be an array", 2);
4445            return;
4446        }
4447        maxlen = zend_hash_num_elements(Z_ARRVAL(arrays[0]));
4448
4449        /* Short-circuit: if no callback and only one array, just return it. */
4450        if (!ZEND_FCI_INITIALIZED(fci)) {
4451            RETVAL_ZVAL(&arrays[0], 1, 0);
4452            return;
4453        }
4454
4455        array_init_size(return_value, maxlen);
4456
4457        ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL(arrays[0]), num_key, str_key, zv) {
4458            fci.retval = &result;
4459            fci.param_count = 1;
4460            fci.params = &arg;
4461            fci.no_separation = 0;
4462
4463            ZVAL_COPY(&arg, zv);
4464
4465            if (zend_call_function(&fci, &fci_cache TSRMLS_CC) != SUCCESS || Z_TYPE(result) == IS_UNDEF) {
4466                php_error_docref(NULL TSRMLS_CC, E_WARNING, "An error occurred while invoking the map callback");
4467                zval_dtor(return_value);
4468                zval_ptr_dtor(&arg);
4469                RETURN_NULL();
4470            } else {
4471                zval_ptr_dtor(&arg);
4472            }
4473            if (str_key) {
4474                zend_hash_add_new(Z_ARRVAL_P(return_value), str_key, &result);
4475            } else {
4476                zend_hash_index_add_new(Z_ARRVAL_P(return_value), num_key, &result);
4477            }
4478        } ZEND_HASH_FOREACH_END();
4479    } else {
4480        zend_uint *array_pos = (HashPosition *)ecalloc(n_arrays, sizeof(HashPosition));
4481
4482        for (i = 0; i < n_arrays; i++) {
4483            if (Z_TYPE(arrays[i]) != IS_ARRAY) {
4484                php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument #%d should be an array", i + 2);
4485                efree(array_pos);
4486                return;
4487            }
4488            if (zend_hash_num_elements(Z_ARRVAL(arrays[i])) > maxlen) {
4489                maxlen = zend_hash_num_elements(Z_ARRVAL(arrays[i]));
4490            }
4491        }
4492
4493        array_init_size(return_value, maxlen);
4494
4495        if (!ZEND_FCI_INITIALIZED(fci)) {
4496            zval zv;
4497
4498            /* We iterate through all the arrays at once. */
4499            for (k = 0; k < maxlen; k++) {
4500
4501                /* If no callback, the result will be an array, consisting of current
4502                 * entries from all arrays. */
4503                array_init_size(&result, n_arrays);
4504
4505                for (i = 0; i < n_arrays; i++) {
4506                    /* If this array still has elements, add the current one to the
4507                     * parameter list, otherwise use null value. */
4508                    zend_uint pos = array_pos[i];
4509                    while (1) {
4510                        if (pos >= Z_ARRVAL(arrays[i])->nNumUsed) {
4511                            ZVAL_NULL(&zv);
4512                            break;
4513                        } else if (Z_TYPE(Z_ARRVAL(arrays[i])->arData[pos].val) != IS_UNDEF) {
4514                            ZVAL_COPY(&zv, &Z_ARRVAL(arrays[i])->arData[pos].val);
4515                            array_pos[i] = pos + 1;
4516                            break;
4517                        }
4518                        pos++;
4519                    }
4520
4521                    zend_hash_next_index_insert_new(Z_ARRVAL(result), &zv);
4522                }
4523
4524                zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &result);
4525            }
4526        } else {
4527            zval *params = (zval *)safe_emalloc(n_arrays, sizeof(zval), 0);
4528
4529            /* We iterate through all the arrays at once. */
4530            for (k = 0; k < maxlen; k++) {
4531                for (i = 0; i < n_arrays; i++) {
4532                    /* If this array still has elements, add the current one to the
4533                     * parameter list, otherwise use null value. */
4534                    zend_uint pos = array_pos[i];
4535                    while (1) {
4536                        if (pos >= Z_ARRVAL(arrays[i])->nNumUsed) {
4537                            ZVAL_NULL(&params[i]);
4538                            break;
4539                        } else if (Z_TYPE(Z_ARRVAL(arrays[i])->arData[pos].val) != IS_UNDEF) {
4540                            ZVAL_COPY(&params[i], &Z_ARRVAL(arrays[i])->arData[pos].val);
4541                            array_pos[i] = pos + 1;
4542                            break;
4543                        }
4544                        pos++;
4545                    }
4546                }
4547
4548                fci.retval = &result;
4549                fci.param_count = n_arrays;
4550                fci.params = params;
4551                fci.no_separation = 0;
4552
4553                if (zend_call_function(&fci, &fci_cache TSRMLS_CC) != SUCCESS || Z_TYPE(result) == IS_UNDEF) {
4554                    php_error_docref(NULL TSRMLS_CC, E_WARNING, "An error occurred while invoking the map callback");
4555                    efree(array_pos);
4556                    zval_dtor(return_value);
4557                    for (i = 0; i < n_arrays; i++) {
4558                        zval_ptr_dtor(&params[i]);
4559                    }
4560                    efree(params);
4561                    RETURN_NULL();
4562                } else {
4563                    for (i = 0; i < n_arrays; i++) {
4564                        zval_ptr_dtor(&params[i]);
4565                    }
4566                }
4567
4568                zend_hash_next_index_insert_new(Z_ARRVAL_P(return_value), &result);
4569            }
4570
4571            efree(params);
4572        }
4573        efree(array_pos);
4574    }
4575}
4576/* }}} */
4577
4578/* {{{ proto bool array_key_exists(mixed key, array search)
4579   Checks if the given key or index exists in the array */
4580PHP_FUNCTION(array_key_exists)
4581{
4582    zval *key;                  /* key to check for */
4583    HashTable *array;           /* array to check in */
4584
4585#ifndef FAST_ZPP
4586    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "zH", &key, &array) == FAILURE) {
4587        return;
4588    }
4589#else
4590    ZEND_PARSE_PARAMETERS_START(2, 2)
4591        Z_PARAM_ZVAL(key)
4592        Z_PARAM_ARRAY_OR_OBJECT_HT(array)
4593    ZEND_PARSE_PARAMETERS_END();
4594#endif
4595
4596    switch (Z_TYPE_P(key)) {
4597        case IS_STRING:
4598            if (zend_symtable_exists(array, Z_STR_P(key))) {
4599                RETURN_TRUE;
4600            }
4601            RETURN_FALSE;
4602        case IS_INT:
4603            if (zend_hash_index_exists(array, Z_IVAL_P(key))) {
4604                RETURN_TRUE;
4605            }
4606            RETURN_FALSE;
4607        case IS_NULL:
4608            if (zend_hash_exists(array, STR_EMPTY_ALLOC())) {
4609                RETURN_TRUE;
4610            }
4611            RETURN_FALSE;
4612
4613        default:
4614            php_error_docref(NULL TSRMLS_CC, E_WARNING, "The first argument should be either a string or an integer");
4615            RETURN_FALSE;
4616    }
4617}
4618/* }}} */
4619
4620/* {{{ proto array array_chunk(array input, int size [, bool preserve_keys])
4621   Split array into chunks */
4622PHP_FUNCTION(array_chunk)
4623{
4624    int argc = ZEND_NUM_ARGS(), num_in;
4625    php_int_t size, current = 0;
4626    zend_string *str_key;
4627    php_uint_t num_key;
4628    zend_bool preserve_keys = 0;
4629    zval *input = NULL;
4630    zval chunk;
4631    zval *entry;
4632
4633    if (zend_parse_parameters(argc TSRMLS_CC, "ai|b", &input, &size, &preserve_keys) == FAILURE) {
4634        return;
4635    }
4636    /* Do bounds checking for size parameter. */
4637    if (size < 1) {
4638        php_error_docref(NULL TSRMLS_CC, E_WARNING, "Size parameter expected to be greater than 0");
4639        return;
4640    }
4641
4642    num_in = zend_hash_num_elements(Z_ARRVAL_P(input));
4643
4644    if (size > num_in) {
4645        size = num_in > 0 ? num_in : 1;
4646    }
4647
4648    array_init_size(return_value, ((num_in - 1) / size) + 1);
4649
4650    ZVAL_UNDEF(&chunk);
4651
4652    ZEND_HASH_FOREACH_KEY_VAL(Z_ARRVAL_P(input), num_key, str_key, entry) {
4653        /* If new chunk, create and initialize it. */
4654        if (Z_TYPE(chunk) == IS_UNDEF) {
4655            array_init_size(&chunk, size);
4656        }
4657
4658        /* Add entry to the chunk, preserving keys if necessary. */
4659        zval_add_ref(entry);
4660
4661        if (preserve_keys) {
4662            if (str_key) {
4663                zend_hash_update(Z_ARRVAL(chunk), str_key, entry);
4664            } else {
4665                add_index_zval(&chunk, num_key, entry);
4666            }
4667        } else {
4668            add_next_index_zval(&chunk, entry);
4669        }
4670
4671        /* If reached the chunk size, add it to the result array, and reset the
4672         * pointer. */
4673        if (!(++current % size)) {
4674            add_next_index_zval(return_value, &chunk);
4675            ZVAL_UNDEF(&chunk);
4676        }
4677    } ZEND_HASH_FOREACH_END();
4678
4679    /* Add the final chunk if there is one. */
4680    if (Z_TYPE(chunk) != IS_UNDEF) {
4681        add_next_index_zval(return_value, &chunk);
4682    }
4683}
4684/* }}} */
4685
4686/* {{{ proto array array_combine(array keys, array values)
4687   Creates an array by using the elements of the first parameter as keys and the elements of the second as the corresponding values */
4688PHP_FUNCTION(array_combine)
4689{
4690    zval *values, *keys;
4691    zend_uint pos_values = 0;
4692    zval *entry_keys, *entry_values;
4693    int num_keys, num_values;
4694
4695    if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "aa", &keys, &values) == FAILURE) {
4696        return;
4697    }
4698
4699    num_keys = zend_hash_num_elements(Z_ARRVAL_P(keys));
4700    num_values = zend_hash_num_elements(Z_ARRVAL_P(values));
4701
4702    if (num_keys != num_values) {
4703        php_error_docref(NULL TSRMLS_CC, E_WARNING, "Both parameters should have an equal number of elements");
4704        RETURN_FALSE;
4705    }
4706
4707    array_init_size(return_value, num_keys);
4708
4709    if (!num_keys) {
4710        return;
4711    }
4712
4713    ZEND_HASH_FOREACH_VAL(Z_ARRVAL_P(keys), entry_keys) {
4714        while (1) {
4715            if (pos_values >= Z_ARRVAL_P(values)->nNumUsed) {
4716                break;
4717            } else if (Z_TYPE(Z_ARRVAL_P(values)->arData[pos_values].val) != IS_UNDEF) {
4718                entry_values = &Z_ARRVAL_P(values)->arData[pos_values].val;
4719                if (Z_TYPE_P(entry_keys) == IS_INT) {
4720                    zval_add_ref(entry_values);
4721                    add_index_zval(return_value, Z_IVAL_P(entry_keys), entry_values);
4722                } else {
4723                    zend_string *key = zval_get_string(entry_keys);
4724
4725                    zval_add_ref(entry_values);
4726                    zend_symtable_update(Z_ARRVAL_P(return_value), key, entry_values);
4727                    STR_RELEASE(key);
4728                }
4729                pos_values++;
4730                break;
4731            }
4732            pos_values++;
4733        }
4734    } ZEND_HASH_FOREACH_END();
4735}
4736/* }}} */
4737
4738/*
4739 * Local variables:
4740 * tab-width: 4
4741 * c-basic-offset: 4
4742 * End:
4743 * vim600: noet sw=4 ts=4 fdm=marker
4744 * vim<600: noet sw=4 ts=4
4745 */
4746