patch for gc of interned String

[Per Bothner]

Bryce McKinlay <bryce@albatross.co.nz> writes:

> Another problem is that in pedantic test cases which rapidly intern a lot of
> strings and forget about them, its theoretically possible to end up with long
> chains of DELETED_STRING pointers, potentially even enough to cause infinate
> looping around the table (given that DELETED_STRINGs don't count towards the
> number of strings considered to be in the table).

I can off-hand think of two fixes:

(1) _Jv_StringFindSlot could check if it has "looped around".
The is simple, but adds an extra test to he loop.

(2) Make sure there always is at least one slot that is NULL.
That will force the loop to exit.

One idea worth considering is to maintain a count of DELETED_STRING
slots.  When it gets too high, call rehash - but without growing
the hash-table.

Is this a real problem is real programs?  For pedantic test cases
we of course want correctness, but I'm not concerned about performance.

> I have a plan to fix the second problem by using buckets and a
> secondary, free-list table to resolve collisions.

Unless you are using secondary memory, or some clever "incremental
re-hash" approach, I really can't think of anything good to say about
collision resolution using chaining, at least in the traditional
approach of a per-hashtable-slot linked list.  It uses a lot more
memory than "open addressing" (Knuth's terminology) for any given
load factor, has worse locality, needs more probes, and complicates
the code.  At least that is my understanding of the situation.  I
could be wrong, or you could have in mind something more clever.
-- 
	--Per Bothner
per@bothner.com   http://www.bothner.com/~per/