Re: [New module] Persistent Hash Array Mapped Tries (HAMTs)

[Bruno Haible]

Hi Marc,

> It implements a persistent version of Phil Bagwell's HAMTs, which has
> been popularized by Clojure. HAMTs can be used when a persistent
> (functional/pure) version of a data structure akin to hash tables is
> needed. For example, the dynamic environment of a (possibly
> multi-threaded) Lisp or Scheme can be modeled with persistent HAMTs.

It is exciting to see such a datastructure with various application domains [1]
in Gnulib!

I haven't read through it line by line; nevertheless a couple of comments:

  - +/* The public interface is documented in the file hamt.c.

    This is not good. As a user of the module, I would want to read *only*
    hamt.h and know how to use the public interface. In other words, hamt.h
    should have the functions' comments.

  - "Each
    updating operation returns a new hamt, which shares structure with
    the original one."
    So, after calling hamt_insert or hamt_delete, which function should I call
    to delete the original Hamt without affecting the new one? (In order to
    avoid accumulating pieces of old Hamts in memory.)

  - "The GL_HAMT_THREAD_SAFE flag is set if the implementation of hamts
    is thread-safe as long as two threads do not simultaneously access
    the same hamt."
    I don't understand this sentence. Isn't the guarantee that
    "is thread-safe as long as two threads do not simultaneously access
    the same hamt" trivial? And what you want to achieve through the use
    of _Atomic is that it is thread-safe *also* when two threads access
    the same hamt?

Bruno

[1] http://infoscience.epfl.ch/record/64398/files/idealhashtrees.pdf