develooper Front page | perl.perl5.porters | Postings from July 2001

Re: [PATCH for discussion] new feature: clamp %hash

Thread Previous | Thread Next
From:
Jeffrey Friedl
Date:
July 20, 2001 03:17
Subject:
Re: [PATCH for discussion] new feature: clamp %hash
Message ID:
200107201016.DAA24726@ventrue.corp.yahoo.com

Arthur Bergman <arthur@contiller.se> wrote:
|> Michael G. Schwern wrote:
|> > Here's the problem.  How can I have a clamped keyset of 'foo' and
|> > 'bar' where C<exists $clamped_hash{foo}> is false?
|> 
|> [...] what you want to do is to have a prototype for a hash with the
|> keys, that is much slower since we have to compare against that
|> prototype, and that is the same has dealing with pseudohashes.

Okay, I think I've been able to solve this at very little cost.
The result is that you need not have all keys in a clamped hash,
but it's still an error to add a "non approved" key.

Access/update/iterate speed is virtually identical to non-clamped hashes.

What I've done so far is certainly not complete, but it shows the idea:

   * When an element is deleted from a clamped hash, rather than simply
     remove the whole key/value pair, I keep the key in there with a
     special placeholder value. Internally, this is distinct from undef or
     any possible scalar. (I created "PL_sv_placehold", which is similar to
     "PL_sv_undef").

   * exists(), keys(), values(), hash access, etc., all know to ignore this
     placeholder value, so for their purposes it's as if the key doesn't
     exist.

   * When attempting to add a key to a clamped hash, if the key is there
     with a placeholder value, the addition is allowed (since it's not
     really adding it -- it's there... just no one else could tell).

So, with just this added functionality, it's ugly, but you could:
     1) create your hash with all approved keys.
     2) clamp it
     3) delete keys you didn't want at the moment. This leaves them
        pre-populated in memory, but !defined() and !exists() and
        not showing up with keys() or values() or each().

This is all working now on my system, and "make test" is clean.
The diff is quite small, but I'm sure it needs some tidying up.

Of course, it would be nice to go further and provide ways to:
     * set/add/remove approved keys [can do now, but ugly]
     * query if a key is approved [can do now, but ugly]
     * query the list of all approved keys [can't do now]
     * other?

Thoughts on how to do this?

COSTS:

   MEMORY:
      * Deleting values from a clamped hash doesn't free up the memory
	and buckets associated with their keys. (To truly remove them,
        unclamp and delete).

      * Bloat of Perl's data segment by 3 words for PL_sv_placehold.

      * Bloat of one word per hash (that's per hash, not per element!), to
	hold the count of non-placeholder keys, for use by scalar(%keys)
        and others.

      * Minimal code bloat

   TIME:
     * If many deleted keys, have to transverse them while searching for
       or otherwise dealing with other keys.

     * Otherwise, effectively no time cost.


Comments?
	Jeffrey
------------------------------------------------------------------------------
Jeffrey Friedl <jfriedl@yahoo-inc.com> Yahoo! Finance http://finance.yahoo.com


Thread Previous | Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About