Eric Blake wrote: > According to Eric Blake on 6/17/2009 12:21 PM: >> Before the rehash, about 20% of the buckets were empty. But after changing >> the >> prime factor, the hasher function scatters better, and _every single bucket_ >> is >> occupied. Which means ALL subsequent calls to hash_insert will trigger an >> overflow, rather than inserting into a bucket head. And since the resize >> checking logic in hash_rehash is only triggered after insertion into a bucket >> head, the hash table has effectively been locked into a fixed size that will >> never grow again, no matter how many hash_insert calls are made, even though >> the table is certainly exceeding the requested threshold of 20% empty >> buckets. >> Ouch. > > I'm now playing with this simple code motion patch, also available at: > http://repo.or.cz/w/gnulib/ericb.git > $ git pull git://repo.or.cz/gnulib/ericb.git master
... >>From d3edc0d1e302af613e8b56396f1f9d0bec15a264 Mon Sep 17 00:00:00 2001 > From: Eric Blake <[email protected]> > Date: Wed, 17 Jun 2009 13:01:41 -0600 > Subject: [PATCH] hash: check for resize before insertion > > * lib/hash.c (hash_insert): Check whether bucket usage exceeds > threshold before insertion, so that a pathological hash_rehash > that fills every bucket can still trigger another rehash. The patch attached to that message did not apply to gnulib, since it had bits like this: -+ if (table->overflow_size <= new_entry - table->overflow) -+ abort (); ... -- bucket->next = new_entry - table->overflow; +- bucket->next = new_entry; Did you verify that stock gnulib/hash.c can get stuck like you described?
