Everything

php

array_intersect_key

php.internals

Cristiano Duarte

22 years ago

Hi all,

I needed to intersect an array with database records indexed by the primary
key, with an array with keys and there is no php function that will do it
internally.
The database array looks like:
$records = array ( 2587 => array('Name', 'Address', 'zip'), ...);

And the array with PKS:
$pks = array_flip(array ( 234, 897, 2587, 6788));

And the intersection would be:
$result = array_intersect_key($records, $pks);

This last action should be done 10.000 times or more, so a pure PHP
implementation takes too long, then I made the following patch to PHP-5.0.0
and PHP-4.3.8 that implements the intersection only comparing the array
keys.

If someone would like to commit it, maybe it would be useful to other users.

Regards,

Cristiano Duarte


***********************Patch for PHP 5.0.0


--- array.c     2004-07-11 18:15:04.000000000 -0300
+++ /home/aluno/php-5.0.0-new/ext/standard/array.c      2004-07-20
13:58:47.000000000 -0300
@@ -84,6 +84,7 @@

#define INTERSECT_NORMAL               0
#define INTERSECT_ASSOC                        1
+#define INTERSECT_KEY                  2
#define INTERSECT_COMP_DATA_INTERNAL 0
#define INTERSECT_COMP_DATA_USER     1
#define INTERSECT_COMP_KEY_INTERNAL  0
@@ -2797,7 +2798,8 @@
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);
return;
}
-       } else if (behavior == INTERSECT_ASSOC) {
+       } else if ((behavior == INTERSECT_ASSOC)
+                       ||(behavior == INTERSECT_KEY)) {
intersect_key_compare_func = array_key_compare;
if (data_compare_type == INTERSECT_COMP_DATA_INTERNAL
&&
@@ -2910,7 +2912,7 @@
*list = NULL;
if (behavior == INTERSECT_NORMAL) {
zend_qsort((void *) lists[i], hash->nNumOfElements, sizeof(Bucket *),
intersect_data_compare_func TSRMLS_CC);
-               } else if (behavior == INTERSECT_ASSOC) {
+               } else if ((behavior == INTERSECT_ASSOC) || (behavior == INTERSECT_KEY))
{
zend_qsort((void *) lists[i], hash->nNumOfElements, sizeof(Bucket *),
intersect_key_compare_func TSRMLS_CC);
}
}
@@ -2926,7 +2928,8 @@

/* go through the lists and look for common values */
while (*ptrs[0]) {
-               if (behavior == INTERSECT_ASSOC
+               if ((behavior == INTERSECT_ASSOC
+                       || behavior == INTERSECT_KEY)
&&
key_compare_type == INTERSECT_COMP_KEY_USER) {

@@ -2938,11 +2941,11 @@
while (*ptrs[i] && (0 < (c = intersect_data_compare_func(ptrs[0],
ptrs[i] TSRMLS_CC)))) {
ptrs[i]++;
}
-                       } else if (behavior == INTERSECT_ASSOC) {
+                       } else if (behavior == INTERSECT_ASSOC || behavior == INTERSECT_KEY) {
while (*ptrs[i] && (0 < (c = intersect_key_compare_func(ptrs[0],
ptrs[i] TSRMLS_CC)))) {
ptrs[i]++;
}
-                               if (!c && *ptrs[i]) { /* this means that ptrs[i] is not NULL so we can
compare */
+                               if ((!c && *ptrs[i]) && (behavior == INTERSECT_ASSOC)) { /* this means
that ptrs[i] is not NULL so we can compare */
/* and "c==0" is from last operation */
if (data_compare_type == INTERSECT_COMP_DATA_USER) {
BG(user_compare_func_name) = args[arr_argc];
@@ -2996,7 +2999,7 @@
if (0 <= intersect_data_compare_func(ptrs[0], ptrs[i] TSRMLS_CC)) {
break;
}
-                               } else if (behavior == INTERSECT_ASSOC) {
+                               } else if (behavior == INTERSECT_ASSOC || behavior == INTERSECT_KEY) {
/* no need of looping because indexes are unique */
break;
}
@@ -3012,7 +3015,7 @@
if (intersect_data_compare_func(ptrs[0]-1, ptrs[0] TSRMLS_CC)) {
break;
}
-                               } else if (behavior == INTERSECT_ASSOC) {
+                               } else if (behavior == INTERSECT_ASSOC || behavior == INTERSECT_KEY) {
/* no need of looping because indexes are unique */
break;
}
@@ -3053,6 +3056,25 @@

/* {{{ proto array array_intersect_assoc(array arr1, array arr2 [,
array ...])
Returns the entries of arr1 that have values which are present in all
the other arguments. Keys are used to do more restrictive check */
+PHP_FUNCTION(array_intersect_key)
+{
+       php_array_intersect(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_KEY,
+                               INTERSECT_COMP_DATA_INTERNAL, INTERSECT_COMP_KEY_INTERNAL);
+}
+/* }}} */
+
+
+/* {{{ proto array array_uintersect_assoc(array arr1, array arr2 [,
array ...], callback data_compare_func)
+   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. */
+PHP_FUNCTION(array_uintersect_key)
+{
+       php_array_intersect(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_KEY,
+                               INTERSECT_COMP_DATA_INTERNAL, INTERSECT_COMP_KEY_USER);
+}
+/* }}} */
+
+/* {{{ proto array array_intersect_assoc(array arr1, array arr2 [,
array ...])
+   Returns the entries of arr1 that have values which are present in all
the other arguments. Keys are used to do more restrictive check */
PHP_FUNCTION(array_intersect_assoc)
{
php_array_intersect(INTERNAL_FUNCTION_PARAM_PASSTHRU, INTERSECT_ASSOC,
--- basic_functions.c   2004-06-27 18:49:47.000000000 -0300
+++ /home/aluno/php-5.0.0-new/ext/standard/basic_functions.c    2004-07-20
14:15:00.000000000 -0300
@@ -780,6 +780,8 @@
PHP_FE(array_unique,                                                                                                    NULL)
PHP_FE(array_intersect,                                                                                                 NULL)
PHP_FE(array_uintersect,                                                                                                NULL)
+       PHP_FE(array_intersect_key,                                                                                             NULL)
+       PHP_FE(array_uintersect_key,                                                                                            NULL)
PHP_FE(array_intersect_assoc,                                                                                   NULL)
PHP_FE(array_uintersect_assoc,                                                                                  NULL)
PHP_FE(array_intersect_uassoc,                                                                                  NULL)
--- php_array.h 2004-01-08 15:32:51.000000000 -0200
+++ /home/aluno/php-5.0.0-new/ext/standard/php_array.h  2004-07-20
14:15:21.000000000 -0300
@@ -77,6 +77,8 @@
PHP_FUNCTION(array_unique);
PHP_FUNCTION(array_intersect);
PHP_FUNCTION(array_uintersect);
+PHP_FUNCTION(array_intersect_key);
+PHP_FUNCTION(array_uintersect_key);
PHP_FUNCTION(array_intersect_assoc);
PHP_FUNCTION(array_uintersect_assoc);
PHP_FUNCTION(array_intersect_uassoc);


***********************Patch for PHP 4.3.8

--- array.c     2004-04-01 16:07:01.000000000 -0300
+++ /home/aluno/php-4.3.8-new/ext/standard/array.c      2004-07-20
14:06:48.000000000 -0300
@@ -81,6 +81,7 @@

#define INTERSECT_NORMAL               0
#define INTERSECT_ASSOC                        1
+#define INTERSECT_KEY                  2

PHP_MINIT_FUNCTION(array)
{
@@ -2579,7 +2580,7 @@
*list = NULL;
if (behavior == INTERSECT_NORMAL) {
zend_qsort((void *) lists[i], hash->nNumOfElements, sizeof(Bucket *),
array_data_compare TSRMLS_CC);
-               } else if (behavior == INTERSECT_ASSOC) {
+               } else if ((behavior == INTERSECT_ASSOC) || (behavior == INTERSECT_KEY))
{
zend_qsort((void *) lists[i], hash->nNumOfElements, sizeof(Bucket *),
array_key_compare TSRMLS_CC);
}
}
@@ -2594,17 +2595,20 @@
if (behavior == INTERSECT_NORMAL) {
while (*ptrs[i] && (0 < (c = array_data_compare(ptrs[0], ptrs[i]
TSRMLS_CC))))
ptrs[i]++;
-                       } else if (behavior == INTERSECT_ASSOC) {
+                       } else if ((behavior == INTERSECT_ASSOC)
+                                       || (behavior == INTERSECT_KEY)) {
while (*ptrs[i] && (0 < (c = array_key_compare(ptrs[0], ptrs[i]
TSRMLS_CC))))
ptrs[i]++;
-                               if (!c && *ptrs[i]) { /* this means that ptrs[i] is not NULL so we can
compare */
-                                               /* and "c==0" is from last operation */
-                                       if (array_data_compare(ptrs[0], ptrs[i] TSRMLS_CC) != 0) {
-                                               c = 1;
-                                               /* we are going to the break */
-                                       } else {
-                                               /* continue looping */
-                                       }
+                               if (behavior == INTERSECT_ASSOC) {
+                                       if (!c && *ptrs[i]) { /* this means that ptrs[i] is not NULL so we can
compare */
+                                                       /* and "c==0" is from last operation */
+                                               if (array_data_compare(ptrs[0], ptrs[i] TSRMLS_CC) != 0) {
+                                                       c = 1;
+                                                       /* we are going to the break */
+                                               } else {
+                                                       /* continue looping */
+                                               }
+                                       }
}
}
if (!*ptrs[i]) {
@@ -2639,7 +2643,8 @@
if (behavior == INTERSECT_NORMAL) {
if (0 <= array_data_compare(ptrs[0], ptrs[i] TSRMLS_CC))
break;
-                               } else if (behavior == INTERSECT_ASSOC) {
+                               } else if ((behavior == INTERSECT_ASSOC)
+                                               || (behavior == INTERSECT_KEY)) {
/* no need of looping because indexes are unique */
break;
}
@@ -2653,7 +2658,8 @@
if (behavior == INTERSECT_NORMAL) {
if (array_data_compare(ptrs[0]-1, ptrs[0] TSRMLS_CC))
break;
-                               } else if (behavior == INTERSECT_ASSOC) {
+                               } else if ((behavior == INTERSECT_ASSOC)
+                                               || (behavior == INTERSECT_KEY)) {
/* no need of looping because indexes are unique */
break;
}
@@ -2688,6 +2694,15 @@
/* }}} */


+/* {{{ proto array array_intersect_key(array arr1, array arr2 [,
array ...])
+   Returns the entries of arr1 that have keys which are present in all the
other arguments. */
+PHP_FUNCTION(array_intersect_key)
+{
+        php_array_intersect(INTERNAL_FUNCTION_PARAM_PASSTHRU,
INTERSECT_KEY);
+}
+/* }}} */
+
+
static void php_array_diff(INTERNAL_FUNCTION_PARAMETERS, int behavior)
{
zval ***args = NULL;
--- basic_functions.c   2004-05-24 14:02:31.000000000 -0300
+++ /home/aluno/php-4.3.8-new/ext/standard/basic_functions.c    2004-07-20
14:11:50.000000000 -0300
@@ -838,6 +838,7 @@
PHP_FE(array_rand,                                                                                                              NULL)
PHP_FE(array_unique,                                                                                                    NULL)
PHP_FE(array_intersect,                                                                                                 NULL)
+       PHP_FE(array_intersect_key,                                                                                                     NULL)
PHP_FE(array_intersect_assoc,                                                                                                   NULL)
PHP_FE(array_diff,                                                                                                              NULL)
PHP_FE(array_diff_assoc,                                                                                                                NULL)
--- php_array.h 2002-12-31 14:35:32.000000000 -0200
+++ /home/aluno/php-4.3.8-new/ext/standard/php_array.h  2004-07-20
14:04:38.000000000 -0300
@@ -75,6 +75,7 @@
PHP_FUNCTION(array_rand);
PHP_FUNCTION(array_unique);
PHP_FUNCTION(array_intersect);
+PHP_FUNCTION(array_intersect_key);
PHP_FUNCTION(array_intersect_assoc);
PHP_FUNCTION(array_diff);
PHP_FUNCTION(array_diff_assoc);

Jason Garber

22 years ago

Hello Cristiano,

First, I'd like to say that a function of this type sounds useful.
It's one that I've wanted for some time, particularly for verifying
that an array has the correct keys when it is passed as a function
parameter.

If I understand what you are doing correctly, the same thing can be
accomplished by:

array_intersect(array_keys($records), array(234, 567, 890, 123))

However, I agree that array_diff_key() and array_intersect_key()
would be significantly useful functions to add to the core.

--
Best regards,
Jason                            mailto:jason@ionzoft.com

Tuesday, July 20, 2004, 3:16:20 PM, you wrote:

CD> Hi all,

CD> I needed to intersect an array with database records indexed by the primary
CD> key, with an array with keys and there is no php function that will do it
CD> internally.
CD> The database array looks like:
CD> $records = array ( 2587 => array('Name', 'Address', 'zip'), ...);

Andrey Hristov

22 years ago

is "make test" showing problems? (i am just currious).
I will try to review the patch later today (atm i am sick).

andrey

Cristiano Duarte wrote:

Lukas Smith

22 years ago

Andrey Hristov wrote:

> is "make test" showing problems? (i am just currious).
> I will try to review the patch later today (atm i am sick).

Which also reminds me that we still dont have a function to merge a
multi dimensional array without messing with the array structures (which
array_merge_recursive() does if it finds any overlap).

http://bugs.php.net/bug.php?id=6911

regards,
Lukas Smith

Cristiano Duarte

22 years ago

Andrey Hristov wrote:

> is "make test" showing problems? (i am just currious).
> I will try to review the patch later today (atm i am sick).

Nope. Make test shows the same errors before and after the patch.

I decided to attach the patch since it will keep tabs...

Cristiano Duarte

Andrey Hristov

22 years ago

Hallo Cristiano,
these 2 function will be added to HEAD in few minutes. I see that the
patch is kind of trivial and won't hurt anything :) (INTERSECT_KEY
is just INTERSECT_ASSOC but no data comparison performed).
I will add also array_diff_key() and array_diff_ukey()

cheers,
andrey

P.S.
Andi: I think the changes are minimal, so is it possible to merge into 5_0 ?

Cristiano Duarte wrote:

Cristiano Duarte

22 years ago

Andrey Hristov wrote:

>   Hallo Cristiano,
> these 2 function will be added to HEAD in few minutes. I see that the
> patch is kind of trivial and won't hurt anything :) (INTERSECT_KEY
> is just INTERSECT_ASSOC but no data comparison performed).
> I will add also array_diff_key() and array_diff_ukey()

I have added these already. :-)

Cristiano Duarte

Andrey Hristov

22 years ago

Well, i think I have found a buggie (not related to these functions and I want to
investigate it). Thus I will delay the commit.

Cristiano Duarte wrote:

> Andrey Hristov wrote:
>
>
>>  Hallo Cristiano,
>>these 2 function will be added to HEAD in few minutes. I see that the
>>patch is kind of trivial and won't hurt anything :) (INTERSECT_KEY
>>is just INTERSECT_ASSOC but no data comparison performed).
>>I will add also array_diff_key() and array_diff_ukey()
>
> I have added these already. :-)

I see :)

andrey

Cristiano Duarte

22 years ago

Andrey Hristov wrote:

>   Hallo Cristiano,
> these 2 function will be added to HEAD in few minutes. I see that the
> patch is kind of trivial and won't hurt anything :) (INTERSECT_KEY
> is just INTERSECT_ASSOC but no data comparison performed).
> I will add also array_diff_key() and array_diff_ukey()

I changed the function name from array_udiff_key to array_diff_ukey.
Is this ok ? Patch attached.

Cristiano Duarte

Andrey Hristov

22 years ago

Cristiano Duarte wrote:

> Andrey Hristov wrote:
>
>
>>  Hallo Cristiano,
>>these 2 function will be added to HEAD in few minutes. I see that the
>>patch is kind of trivial and won't hurt anything :) (INTERSECT_KEY
>>is just INTERSECT_ASSOC but no data comparison performed).
>>I will add also array_diff_key() and array_diff_ukey()
>
> I changed the function name from array_udiff_key to array_diff_ukey.
> Is this ok ? Patch attached.
>

Well, my patch for array_diff_key() and array_diff_ukey() looked like yours
but when writing the regression tests I spotted a bug. I thought it is not related
to the new functions. After some testing I found the problem and it was related
to array_diff_*key(). I have placed a comment in the source at about line 3364.

cheers,
andrey

Andi Gutmans

22 years ago

I suggest to make those #define's bit flags and then change:
} else if (behavior == INTERSECT_ASSOC || behavior == INTERSECT_KEY)
to
(behavior & (INTERSECT|INTERSECT_KEY))

Change:

>>  #define INTERSECT_NORMAL               0
>>  #define INTERSECT_ASSOC                        1
>>+#define INTERSECT_KEY                  2

to:

>>  #define INTERSECT_NORMAL               (1 << 0)
>>  #define INTERSECT_ASSOC                (1 << 1)
>>+#define INTERSECT_KEY                  (1 << 2)

If he patch is clean it's fine with me. It doesn't look like it'll break
anything old.

At 07:08 PM 7/21/2004 +0000, Andrey Hristov wrote:

Andrey Hristov

22 years ago

Andi Gutmans wrote:

> I suggest to make those #define's bit flags and then change:
> } else if (behavior == INTERSECT_ASSOC || behavior == INTERSECT_KEY)
> to
> (behavior & (INTERSECT|INTERSECT_KEY))
>

This idea came to my mind too. I have already commited a working version without
bitflags but in the next days I will rework it to use them.

andrey