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