[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: HAMT iterator
From: |
Bruno Haible |
Subject: |
Re: HAMT iterator |
Date: |
Sun, 11 Oct 2020 14:14:11 +0200 |
User-agent: |
KMail/5.1.3 (Linux/4.4.0-189-generic; KDE/5.18.0; x86_64; ; ) |
Marc Nieper-Wißkirchen wrote:
> > > I am going to implement the following iterator API as well:
> > >
> > > /* An alternative interface to iterating through the entry of a hamt
> > > that does not make use of a higher-order function like
> > > hamt_do_while uses the opaque Hamt_iterator type. */
> > > typedef struct hamt_iterator Hamt_iterator;
> > >
> > > /* Return a newly created iterator for HAMT. */
> > > extern Hamt_iterator *hamt_iterator_create (const Hamt *hamt);
> >
> > The pointer return here is overkill. A prototype
> >
> > extern Hamt_iterator hamt_iterator_create (const Hamt *hamt);
> >
> > is sufficient, because the way such an iterator is used is:
> >
> > Hamt_iterator iter = hamt_iterator_create (hamt);
> >
> > for (...)
> > {
> > ...
> > Hamt_entry *elt;
> > if (hamt_iterator_next (&iter, &elt))
> > {
> > ...
> > }
> > ...
> > }
> >
> > hamt_iterator_free (&iter);
> >
> > > /* Return an independent copy of ITER that is initially in the same
> > > state. */
> > > extern Hamt_iterator *hamt_iterator_copy (Hamt_iterator *iter);
> >
> > Then a copy function is not needed, because the user's program can do
> >
> > Hamt_iterator iter_clone = iter;
>
> The hamt itself has to be copied (to increase the reference counter).
Whether copying an iterator can be done by assignment or requires a function
call, is of second importance.
The more important point I wanted to make: Does allocating an iterator
require a (heap) memory allocation?
If you iterate with do_while, no memory allocation is needed, because all
information is stored on the stack, between the various function calls.
If you iterate with hamt_iterator_create, and the Hamt_iterator type
has bounded size (I guess it will not require more than 15 pointers and
13 indices), it can be stored on the caller's stack.
Bruno
- Re: [New module] Persistent Hash Array Mapped Tries (HAMTs), (continued)
- Re: [New module] Persistent Hash Array Mapped Tries (HAMTs), Marc Nieper-Wißkirchen, 2020/10/10
- Re: [New module] Persistent Hash Array Mapped Tries (HAMTs), Marc Nieper-Wißkirchen, 2020/10/10
- 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 <=
- Re: HAMT iterator, Marc Nieper-Wißkirchen, 2020/10/11
- Re: HAMT iterators, Bruno Haible, 2020/10/11
- 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