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