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