weak-map.ss: a hash-table with weak keys

_weak-map.ss_: a hash-table with weak keys
----------------------------------------

Danny Yoo (dyoo@hkn.eecs.berkeley.edu / dyoo@wpi.edu)


_weak-map_ provides a hash-table-like structure that holds its keys
weakly.  If the only references to a key are weak ones, the associated
item will be removed from the map.  This behavior is useful for
implementing things like object caches.


As a full-disclosure thing: most of this isn't really my code, as it comes
almost straight out of the mzscheme reference manual, in the section
on Ephemerons:

http://download.plt-scheme.org/doc/360/html/mzscheme/mzscheme-Z-H-13.html#node_sec_13.2

I've added a few more functions to the API and made WEAK-MAP-GET's
interface more similar to HASH-TABLE-GET.


Quick Example
=============

    > (require (planet "weak-map.ss" ("dyoo" "weak-map.plt")))
    > (define m (make-weak-map))
    > (define message "hello")
    >
    > (weak-map-put! m message message)
    > (weak-map-get m message)
    "hello"
    > (weak-map-map m list)
    (("hello" "world"))
    >
    > (weak-map-get m "ice cream")
    weak-map-get: no value found for key ice cream
    > (weak-map-get m "ice cream" #f)
    #f
    > (weak-map-get m "ice cream" (lambda () "munchy"))
    "munchy"
    >
    > (collect-garbage)
    > (weak-map-map m list)
    (("hello" "hello"))
    >
    > (set! message #f)
    > (collect-garbage)
    > (weak-map-map m list)
    ()

    
Modules
=======

   _weak-map_ :      an implementation of weak-maps.
   
   _string-intern_ : an example use of weak-map to implement interned
                     string tables.

                     
API for weak-map.ss
===================

> make-weak-map: ['equal] -> weak-map
Creates a weak-map.  If the 'equal flag is provides, then keys
are compared by equal?.


> weak-map-get: weak-map key [failure-thunk-or-value] -> void
Returns the value in the weak-map that's associated to the key.

If the key cannot be found and failure-thunk-or-value isnt' provided,
then we raise an error.  If failure-thunk-or-value is a procedure, we
apply it with no argument and return its value.  Otherwise, we just
return it.


> weak-map-put!: weak-map key value -> void
Maps the key to the value, overwriting any preexisting value.


> weak-map-for-each: weak-map proc -> void
Applies the procedure to each key-value pair in the weak-map.  proc
should take two arguments, the key and value, respectively.


> weak-map-map: weak-map proc -> (listof any)
Applies the procedure to each key-value pair in the weak-map, and
collects the results as a list.  proc should take two arguments, the
key and value, respectively.




Another Example: _string-intern.ss_
===================================

Here's a more substantial example of a weak-map: the following
function implements a _string-intern_:

    (define string-intern
      (let ([sema (make-semaphore 1)]
            [m (make-weak-map 'equal)])
        (lambda (s)
          (semaphore-wait sema)
          (let ([result
                 (weak-map-get
                  m s
                  (lambda ()
                    (let ([immutable-s (string->immutable-string s)])
                      (weak-map-put! m immutable-s immutable-s)
                      immutable-s)))])
            (semaphore-post sema)
            result))))
  
Here, we use the 'equal flag to compare keys by equality.


Since this might be useful, _string-intern.ss_ is also included
with this package.

Example with string-intern
==========================

    > (require (planet "string-intern.ss" ("dyoo" "weak-map.plt")))
    > (eq? (string-intern "hello") (string-intern (string-append "h" "ello")))
    #t

    
API for string_intern.ss
========================

> string-intern: string -> immutable-string
Given a string, returns an immutable string.  If two strings that
come out of string-intern are equal?, then they are also guaranteed
to be eq?.