From borg at imbei.uni-mainz.de  Mon Jan 18 13:30:51 2010
From: borg at imbei.uni-mainz.de (Andreas Borg)
Date: Mon, 18 Jan 2010 13:30:51 +0100
Subject: [Rd] Fix for bug in match()
Message-ID: <4B54547B.2010108@imbei.uni-mainz.de>

Hello all,

I posted the following bug last week:

# These calls work correctly:
match(c("A", "B", "C"), c("A","C"), incomparables=NA) # okay
match(c("A", "B", "C"), "A") # okay
match("A", c("A", "B"), incomparables=NA) # okay

# This one causes R to hang:
match(c("A", "B", "C"), "A", incomparables=NA)

I found the reason in the hash table implementation in unique.c. Values 
in the table argument of match are stored in a hash table. Incomparables 
are then removed by (potentially multiple) calls to removeEntry():

static void removeEntry(SEXP table, SEXP x, int indx, HashData *d)
{
    int i, *h;

    h = INTEGER(d->HashTable);
    i = d->hash(x, indx, d);
    while (h[i] != NIL) {
    if (d->equal(table, h[i], x, indx)) {
        h[i] = NA_INTEGER;  /* < 0, only index values are inserted */
        return;
    }
    i = (i + 1) % d->M;
    }
    h[i] = NA_INTEGER;
}

Removing a value x sets the corresponding cell to NA_INTEGER. If x is 
not element of the table, the cell where it would have been is set from 
NIL (-1) to NA_INTEGER. Therefore, subsequent calls to removeEntry() 
with values that are not element of the table can remove all initial NIL 
values from the table cells. Another call of removeEntry() or Lookup() 
then leads to an infinte loop because the condition

while (h[i] != NIL)

is never false.

As a fix, I propose to reset cells to NIL when removing values, which 
leads to the following definition:

static void removeEntry(SEXP table, SEXP x, int indx, HashData *d)
{
    int i, *h;

    h = INTEGER(d->HashTable);
    i = d->hash(x, indx, d);
    while (h[i] != NIL) {
    if (d->equal(table, h[i], x, indx)) {
        h[i] = NIL;  /* < 0, only index values are inserted */
        return;
    }
    i = (i + 1) % d->M;
    }
}

I would have submitted a patch file, but I couldn't checkout from the 
svn repository.

Cheers,

Andreas





-- 
Andreas Borg
Medizinische Informatik

UNIVERSIT?TSMEDIZIN
der Johannes Gutenberg-Universit?t
Institut f?r Medizinische Biometrie, Epidemiologie und Informatik
Obere Zahlbacher Stra?e 69, 55131 Mainz
www.imbei.uni-mainz.de

Telefon +49 (0) 6131 175062
E-Mail: borg at imbei.uni-mainz.de

Diese E-Mail enth?lt vertrauliche und/oder rechtlich gesch?tzte Informationen. Wenn Sie nicht der
richtige Adressat sind oder diese E-Mail irrt?mlich erhalten haben, informieren Sie bitte sofort den
Absender und l?schen Sie diese Mail. Das unerlaubte Kopieren sowie die unbefugte Weitergabe
dieser Mail und der darin enthaltenen Informationen ist nicht gestattet.



[Rd] Fix for bug in match()
Andreas Borg