Re: Scheme style auto-resizing hashtable (fwd)

[Jay Glascoe <jglascoe@jay.giss.nasa.gov>]

On 24 Oct 1998, Rob Browning wrote:

> I think it's been mentioned, but some way to get a list of the keys
> would be quite helpful, perhaps a hash->keys, hash->alist, or even a
> make-hash-iterator function.

hash->keys could be written in Scheme like this

(define hash->keys
  (lambda (mytab)
    ;; maybe do some type-checking here
    (let* ((vec (cdr mytab))
	   (vec-len (vector-length vec)))
      (do ((keys '())
	   (i 0 (+ i 1))
	   (bucket (vector-ref vec 0) (vector-ref vec i)))
	  ((>= i vec-len) keys)
	(do ((entry-list (cdr bucket) (cdr entry-list)))
	    ((null? entry-list))
	  (let* ((entry (car entry-list))
		 (pair (cdr entry))
		 (key (car pair)))
	    (set! keys (cons key keys))))))))

(forgive the imperative style, I never seem to get by
without at least one "!"   ;)

in C it would look like this

static SCM
hash2keys(SCM mytab)
{
    SCM vec = SCM_CDR(mytab);
    /* maybe to do some type-checking here */
    long vec_len = SCM_LENGTH(vec);
    SCM *vec_elts = SCM_VELTS(vec);

    SCM keys = SCM_EOL;

    for (i = 0; i < vec_len; ++i)
    {
	SCM bucket = vec_elts[i];
	SCM entry_list;
	for (entry_list = SCM_CDR(bucket);
	     entry_list != SCM_EOL;
	     entry_list = SCM_CDR(entry_list))
	{
	    SCM entry = SCM_CAR(entry_list); 
	    SCM pair = SCM_CDR(entry);
	    SCM key = SCM_CDR(pair);
	    keys = scm_cons(key, keys);
	}
    }
    
    return keys;
}

a "hash->alist" would be very similar to hash->keys (instead of cons'ing
key onto keys, you would cons "pair" onto keys). "make-hash-iterator" I
could write in Scheme using closures, but in C?, I don't know.  I think
the Guile C library does provide some sort of closure creation thingy, but
I haven't studied it yet.

> There are times when I need to iterate over all the elements of a hash
> table (after some long processing step), and with the current code I
> can't see a (clean) way to do it.  Of these three approaches, the
> iterator approach would be more memory efficient, but probably a mess
> otherwise.

Perl hackers and Pythoneers seem to get by pretty well with just the
"hash->keys" approach.  But hey, this is Scheme, I imagine I'll wind up
throwing in 10 gajillion different procedures to operate on hash tables,
and the more required arguments, the better ;)

> -- 
> Rob Browning <rlb@cs.utexas.edu> PGP=E80E0D04F521A094 532B97F5D64E3930
> 

	Jay
	jglascoe@jay.giss.nasa.gov