[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
- Re: [New module] Persistent Hash Array Mapped Tries (HAMTs), (continued)
- Re: [New module] Persistent Hash Array Mapped Tries (HAMTs), Bruno Haible, 2020/10/10
- Re: [New module] Persistent Hash Array Mapped Tries (HAMTs), Marc Nieper-Wißkirchen, 2020/10/11
- Re: [New module] Persistent Hash Array Mapped Tries (HAMTs), Marc Nieper-Wißkirchen, 2020/10/11
- Re: HAMT iterator, Bruno Haible, 2020/10/11
- Re: HAMT iterator, Marc Nieper-Wißkirchen, 2020/10/11
- Re: HAMT iterator, Bruno Haible, 2020/10/11
- Re: HAMT iterator, Marc Nieper-Wißkirchen, 2020/10/11
- Re: HAMT iterator, Bruno Haible, 2020/10/11
- Re: HAMT iterator, Bruno Haible, 2020/10/11
- Re: HAMT iterator, Marc Nieper-Wißkirchen, 2020/10/11
- Re: HAMT iterators,
Bruno Haible <=
- Re: HAMT iterators, Marc Nieper-Wißkirchen, 2020/10/11
- Re: HAMT iterators, Bruno Haible, 2020/10/11
- Re: out-of-memory handling, Bruno Haible, 2020/10/11
- Re: out-of-memory handling, Marc Nieper-Wißkirchen, 2020/10/11
- Re: out-of-memory handling, Bruno Haible, 2020/10/11
- Re: out-of-memory handling, Marc Nieper-Wißkirchen, 2020/10/11
- Re: HAMT for gl_set and gl_map, Bruno Haible, 2020/10/11
- Re: [New module] Persistent Hash Array Mapped Tries (HAMTs), Marc Nieper-Wißkirchen, 2020/10/11
- Re: Draft #3 (with iterators), Marc Nieper-Wißkirchen, 2020/10/11
- Re: Draft #3 (with iterators), Bruno Haible, 2020/10/11