[racket] empty hash tables

At Mon, 30 May 2011 04:12:00 -0400, Eli Barzilay wrote:
> 10 minutes ago, Marijn wrote:
> > while browsing both guide[1] and reference[2] for a `hash-empty?'
> > procedure I turned up with empty hands, although a few possibilities
> > for implementing it did come to mind, like using `hash-count' and
> > comparing to zero or, using `hash-iterate-first' which returns #f
> > for empty hashes but otherwise returns an integer which is an index
> > to the first element in the hash table (which sounds like hash
> > tables are implemented using arrays and an index to the underlying
> > array is returned).
> 
> Marijn clarified on #racket that his concern with `hash-count' is that
> the documentation implies that it's not a constant time operation:
> 
>   If hash is not created with 'weak, then the result is computed in
>   constant time and atomically.
> 
> And looking at the code, it seem that that justifies a primitive
> `hash-empty?'.

How would `hash-empty?' be different than `hash-count' for a weak hash
table? A traversal of the table is needed to check whether any keys
have disappeared. That is, I don't see how to make `hash-empty?' on a
weak table a constant-time operation without additional GC support.

The docs need to be fixed to talk about weak hash tables rather than
tables created with the 'weak symbol (old API), though.

> But then there's a reference to the caveats section, which might not
> be needed since there's no modification involved.  (I guess that it's
> because the table can change while it's being counted, but that would
> be an issue for other read-only operations too.)

I could fix the docs on that point --- the issue is that counting
requires a traversal --- but maybe it's better to have `hash-count'
take the lock.