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