Re: HAMT iterator
Marc Nieper-Wißkirchen wrote:
> > - If someone creates a derivative of the HAMT, the iterator won't
> > be affected, right? ("persistence")
>
> Yes.
OK, that's one thing to document.
> > So, what is the scenario where increasing the reference count will make
> > a difference?
>
> If you have a language with GC like Lisp or Scheme, say, the hamt may
> be GC'd while the iterator is still live.
And in C, when someone calls hamt_free on the HAMT, the iterator won't be
affected. IMO, that's another thing to document (because it's unexpected).
Bruno
Re: HAMT iterator
Am So., 11. Okt. 2020 um 14:04 Uhr schrieb Bruno Haible :
>
> Marc Nieper-Wißkirchen wrote:
> > > > /* 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).
>
> Then the comment should clarify what "independent" means. I thought it
> means that both iterators (the original one and the copy) can be used
> simultaneously, as long as the HAMT does not change. Do you mean
> something broader?
> - If someone creates a derivative of the HAMT, the iterator won't
> be affected, right? ("persistence")
Yes.
> - If someone makes destructive modifications to the HAMT (through the
> *_x functions), the iterator will be affected if it has not yet
> passed the point of modification, right?
No, the iterator shouldn't be affected. (The point of modification is
not well-defined without exposing implementation details.)
> So, what is the scenario where increasing the reference count will make
> a difference?
If you have a language with GC like Lisp or Scheme, say, the hamt may
be GC'd while the iterator is still live.
Re: HAMT iterator
Am So., 11. Okt. 2020 um 14:14 Uhr schrieb Bruno Haible : [...] > > > > /* 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. That's a very good point you make. The hamt iterator has, of course, (low) bounded size, so it can (and should) be allocated on the stack.
Re: HAMT iterator
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 (, ))
> > {
> > ...
> > }
> > ...
> > }
> >
> > hamt_iterator_free ();
> >
> > > /* 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: HAMT iterator
Marc Nieper-Wißkirchen wrote:
> > > /* 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).
Then the comment should clarify what "independent" means. I thought it
means that both iterators (the original one and the copy) can be used
simultaneously, as long as the HAMT does not change. Do you mean
something broader?
- If someone creates a derivative of the HAMT, the iterator won't
be affected, right? ("persistence")
- If someone makes destructive modifications to the HAMT (through the
*_x functions), the iterator will be affected if it has not yet
passed the point of modification, right?
So, what is the scenario where increasing the reference count will make
a difference?
Bruno
Re: HAMT iterator
Am So., 11. Okt. 2020 um 13:02 Uhr schrieb Bruno Haible :
>
> Hi Marc,
>
> > 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 (, ))
> {
> ...
> }
> ...
> }
>
> hamt_iterator_free ();
>
> > /* 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).
> > /* Return true if ITER is not at the end, place the current element in
> >*ELT_PTR and move the iterator forward. Otherwise, return
> >*false. */
> > extern bool hamt_iterator_next (Hamt_iterator *iter,
> > Hamt_entry *const *elt_ptr);
>
> The 'const' here forbids assigning to *ELT_PTR.
Yes. Wrong position of const.
Re: HAMT iterator
Hi Marc,
> 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 (, ))
{
...
}
...
}
hamt_iterator_free ();
> /* 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;
> /* Return true if ITER is not at the end, place the current element in
>*ELT_PTR and move the iterator forward. Otherwise, return
>*false. */
> extern bool hamt_iterator_next (Hamt_iterator *iter,
> Hamt_entry *const *elt_ptr);
The 'const' here forbids assigning to *ELT_PTR.
Bruno
