function assoc_delete may not work

[GoogleCodeExporter]

When delete item, assoc_delete need to rebuild h_next for related keys.
However, I think the existing code for 1.4.0 will not work like that, it
should change like this:

void assoc_delete(const char *key, const size_t nkey) {
    item **before = _hashitem_before(key, nkey);

    if (*before) {
        item *nxt;
        hash_items--;
        /* The DTrace probe cannot be triggered as the last instruction
         * due to possible tail-optimization by the compiler
         */
        MEMCACHED_ASSOC_DELETE(key, nkey, hash_items);
        nxt = (*before)->h_next;
        (*before)->h_next = 0;   /* probably pointless, but whatever. */
-        *before = nxt;
+        (*before)->h_next = nxt->h_next;
        return;
    }
    /* Note:  we never actually get here.  the callers don't delete things
       they can't find. */
    assert(*before != 0);
}

Original issue reported on code.google.com by phyhwf on 29 Aug 2009 at 4:59

[GoogleCodeExporter]

Can you supply a test for this?

Original comment by dsalli...@gmail.com on 29 Aug 2009 at 6:24

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

Sorry. I can not supply a test. The reason is that this happens only when hash 
has
collisions. I can not find such hash keys at the moment. 

But I read the code, and I think it has problem. That dose not make sense.

Original comment by phyhwf on 29 Aug 2009 at 6:40

[GoogleCodeExporter]

Good question. I was puzzled by these codes yesterday. However, they are right. 
Let
me explain this, please.

Assumme the item which should be deleted is "key_item", its predecessor item is
"before_item", its successor item is "after_item", after_item may be NULL.

See function "_hashitem_before", the variable "before" in these codes is 
actually
&(before_item.h_next). So 

nxt = (*before)->h_next; => nxt = *(&(before_item.h_next))->h_next; => nxt =
before_item.h_next->h_next; => nxt = key_item->h_next; => nxt = &after_item;

(*before)->h_next = 0; => ... => key_item->h_next = 0.

 *before = nxt; => ... => before_item.h_next = nxt; => before_item.h_next = &after_item;

You see, fiannly before_item.h_next = &after_item, key_item has been removed 
from the
item list.

Original comment by xiedep...@gmail.com on 29 Aug 2009 at 6:43

[GoogleCodeExporter]

Thanks very much for your explanation. I misunderstood the func 
_hashitem_before,
which I thought it return  &(&before_item). 

Original comment by phyhwf on 29 Aug 2009 at 8:07

[GoogleCodeExporter]

Reporter misunderstood some of the hash table code, closing.

Original comment by dorma...@rydia.net on 29 Aug 2009 at 10:27

• Changed state: Invalid