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. _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
