bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: HAMT iterators


From: Bruno Haible
Subject: Re: HAMT iterators
Date: Sun, 11 Oct 2020 12:29:21 +0200
User-agent: KMail/5.1.3 (Linux/4.4.0-189-generic; KDE/5.18.0; x86_64; ; )

Hi Marc,

> >          You can see that there is an initial function call 
> > HASH-TABLE-ITERATOR
> >          upfront, and then a function call to HASH-TABLE-ITERATE in each 
> > round
> >          of the loop.
> >
> >          This principle makes it possible to iterate e.g. through a hash 
> > table
> >          and a list in parallel.
> 
> In Scheme, it is even more relevant because you have call/cc so any
> iteration can be suspended and restored any number of times.
> 
> I thought this could be solved by storing a "next" pointer in the
> payload but this doesn't work with hamts sharing entries... So I will
> add some iterator interface as well. Preferably one that can also be
> used to implement Hamts in Scheme.

The recursion across hamt_do_while / entry_do_while / subtrie_do_while /
bucket_do_while builds up a stack whose essential contents is a set of
indices, each at most 5 bits large, with a total of SIZE_WIDTH bits.
In other words, the iterator object can be a

struct
  {
    const Hamt *hamt;
    size_t position;
    int depth;
    const Hamt_entry *entry;
  };

where during the iteration
  - hamt stays unmodified,
  - position is incremented by some amount at each round,
  - depth is the recursion depth.
  - entry is a cache of hamt->nodes[(position >> 59) & 31][(position >> 54) & 
31]...
    with depth-1 indexing operations, and is changed at each round,

HASH-TABLE-ITERATOR sets position, depth, entry to point to the first entry.
HASH-TABLE-ITERATE works as follows:
  - in a bucket, it increments position and fetches the next entry of the 
bucket,
  - if the bucket is done, it decreases depth and goes to
    hamt->nodes[(position >> 59) & 31][(position >> 54) & 31]... (with depth-1
    indexing operations) until it finds a subtrie that is not yet done,
    then it increases depth, entry to point to the first entry in that subtrie.

If done this way, the iterator will fit into the gl_set_iterator_t and
gl_map_iterator_t that we already have in gl_set.h and gl_map.h.

Bruno




reply via email to

[Prev in Thread] Current Thread [Next in Thread]