[cairo] Locking policy (and new cairo_hash_table interface)

Carl Worth cworth at cworth.org
Wed Jun 29 10:23:12 PDT 2005


On Wed, 29 Jun 2005 10:59:39 -0600, Keith Packard wrote:
> On Wed, 2005-06-29 at 07:21 -0700, Carl Worth wrote:
> The basic API seems fine to me. It does require two passes over the hash
> table on a miss (lookup, insert), but that doesn't seem an onerous price
> to pay for a simple API.

Yes, I thought about that a bit.

A previous version avoided two calls to compute_hash in this case,
(but still did two passes). That version was annoying in that it
forced the calling code to use a derived key object.

The internal API has a lookup function which returns the spare entry
to store into if needed. On miss, lookup could return a cookie to be
passed into insert, but the API would be a bit awkward.

We could leave the API unchanged and add a slot to the hash table for
that spare entry (along with the key). These could be written on miss
by lookup, read by insert with the same key, and cleared by any other
change to the hash table. As is, we can't make that totally safe since
the general hash code doesn't know the size of the key so it can't
make a copy. But trusting the same key pointer to have the same
contents from lookup to insert, (and documenting that carefully),
would likely be good enough for internal use.

> One thing I don't quite understand -- if the hash table isn't
> responsible for ejecting items, why are there 'delete' functions
> provided?  Isn't the caller responsible for cleaning up the removed
> objects when they call cairo_hash_table_remove?

I was leaving room in which to work for the answer below.

> Do you plan to construct a cache object on top of this simple hash
> table? Or would you leave that to per-object code?

That's the next step of course, and I wasn't sure which way to go. We
have identified two distinct uses in the implementation so far,
(caches of reference-counted objects that can be safely removed at any
point vs. caches of non-reference-counted objects where the calling
code must indicate safe times to shrink).

Either way, the hash code will need to provide some help here. This
could be a "shrink_to" function or some non-lookup accessors to
entries so that calling code could implement some sort of replacement
policy.

-Carl
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20050629/33690969/attachment.pgp


More information about the cairo mailing list