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.
