Re: Scheme style auto-resizing hashtable (fwd)

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

> Calling what many times?  What's wrong with this:
> 
> (define (hashtable-foreach h f)
>    (do ((i 0 (1+ i))
>         (n (hashtable-length h))
>         (v (hashtable-vector h)))
>        ((i >= n))
>      (for-each (lambda (data) (apply f (cdr data)))
>                (vector-ref v i))))
> 

I mistakenly thought iterator was something like this:

(define make-hashtab-iter
  (lambda (hashtab)
    (let* ((vec (cdr hashtab))
	   (vec-len (vector-length vec))
	   (current-index 0)
	   (bucket (vector-ref vec 0))
	   (current-entry-list (cdr bucket)))
      (lambda ()
	(if (>= current-index vec-len)
	    'done
	    (do ((pair 'done)
		 (found #f))
		((or found (>= current-index vec-len)) pair)
	      (if (not (null? current-entry-list))
		  (begin
		    (set! pair (cdar current-entry-list))
		    (set! current-entry-list (cdr current-entry-list))
		    (set! found #t))
		  (begin
		    (set! current-index (+ current-index 1))
		    (if (< current-index vec-len)
			(let ((bucket (vector-ref vec current-index)))
			  (set! current-entry-list (cdr bucket))))))))))))

that would yield a key-value entry every time it's called

guile> (define foo (make-hashtab))
guile> foo
(#(4 #f 0 0) . #((0) (0) (0) (0)))
guile> (do ((i 1 (+ i 1))) ((> i 10)) (hashtab-set! foo (/ i 2) (* i 2)))
guile> foo
(#(4 #f 3 0) . #((3 (1073741828 4.5 . 18) (4 4 . 16) (1073741824 0.5 . 2))
(3 (5
 5 . 20) (1073741825 1.5 . 6) (1 1 . 4)) (2 (1073741826 2.5 . 10) (2 2 .
8)) (2 
(1073741827 3.5 . 14) (3 3 . 12))))
guile> (define iter (make-hashtab-iter foo))
guile> (do ((i 1 (+ i 1))) ((> i 10)) (display (iter)) (newline))
(4.5 . 18)
(4 . 16)
(0.5 . 2)
(5 . 20)
(1.5 . 6)
(1 . 4)
(2.5 . 10)
(2 . 8)
(3.5 . 14)
(3 . 12)
guile> (iter)
done
guile> (iter)
done

> hash->alist (aka hashtable->list) still has to cons up the list that
> points to all the pairs in the hashtable, so it's still a lot of
> garbage - 1 cons cell for each object in the hash table.
> 

not if the pairs are the same objects, same cons cells, as the pairs in
the hashtab vector. 


> -- 
> Harvey J. Stein
> BFM Financial Research
> hjstein@bfr.co.il
> 

	Jay
	jglascoe@jay.giss.nasa.gov