Common sense...

Common sense...

[chris.danx]

Hi,

What's the right thing to do in the following scenario concerning iterators
and lists?

A list is in use by three iterators, A, B and C.  A is at the position
preceding B and C, C calls the remove subroutine on that node and moves on.
The nodes iterator count which was 2 is decreased to 1.  B is the only
iterator using that node, but A wants to moves to the next position before B
exits the node (if B had exited the node prior to A calling next, there'd be
no problem).  Where does A go?  Does it go to the node at B or does it go to
the one after B?

I'd say A skips the node but I've got to go, Dinners out, and so can't
explain my thoughts on why until later!

Thanks,
Chris

Re: Common sense...

[Wes Groleau]

I'd say the iterators should be coded to prevent
more than one being on a particular node at any time.

But then you'd have hassles with concurrency.

Maybe deletion should be delayed until such time
as no other iterator is at that node.

-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau

Re: Common sense...

[chris.danx]

"Wes Groleau" <wesgroleau@despammed.com> wrote in message
news:3D25D743.9F10D353@despammed.com...
> I'd say the iterators should be coded to prevent
> more than one being on a particular node at any time.
>
> But then you'd have hassles with concurrency.

There are hassles with concurrency in allowing more than one iterator to use
the same node.  What if the only iterator holding a node releases it at the
same time as another aquires that node, and the node was marked for
deletion?  It could happen that the aquiring code is stopped a split second
before completion, the node released, and the aquisition code resumed
leading to a nutty situation.

The point of these data structures isn't to be task safe, it's for
non-concurrent use (Ada doesn't have tagged protected object yet, otherwise
I'd code them to be task safe).  Whenever concurrency is used, the
programmer should probably run a protected object over the list and code
their own iterators (which is feasible given the structure of the
collection).

> Maybe deletion should be delayed until such time
> as no other iterator is at that node.

Maybe.

Re: Common sense...

[Wes Groleau]

> > I'd say the iterators should be coded to prevent
> > more than one being on a particular node at any time.
> >
> > But then you'd have hassles with concurrency.
> 
> There are hassles with concurrency in allowing more than one iterator to use
> the same node.  What if the only iterator holding a node releases it at the

But you have even more hassles when you prevent it.

You have to ensure that the task holding the node
can't get blocked by the task waiting for the node.

-- 
Wes Groleau
http://freepages.rootsweb.com/~wgroleau

Re: Common sense...

[Jeffrey Carter]

Deleting nodes from an iterator is erroneous and should raise an
exception.

-- 
Jeff Carter
"You cheesy lot of second-hand electric donkey-bottom biters."
Monty Python & the Holy Grail

Re: Common sense...

[chris.danx]

"Jeffrey Carter" <jrcarter@acm.org> wrote in message
news:3D25E607.E59E11E2@acm.org...
> Deleting nodes from an iterator is erroneous and should raise an
> exception.

ok but how would you enforce that.  Just not support it?  That's no bother
as the iterators aren't written yet.



Chris

Re: Common sense...

[Jeffrey Carter]

"chris.danx" wrote:
> 
> "Jeffrey Carter" <jrcarter@acm.org> wrote in message
> news:3D25E607.E59E11E2@acm.org...
> > Deleting nodes from an iterator is erroneous and should raise an
> > exception.
> 
> ok but how would you enforce that.  Just not support it?  That's no bother
> as the iterators aren't written yet.

The PragmAda Reusable Components' list components' iterators will raise
an exception (Invalid_Position) if the client-supplied action deletes
the current node. This is a consequence of assigning a unique ID to each
list, marking each Position and node with the ID of the associated list,
and invalidating the ID when a node is deleted.

A simpler approach might be to add a Boolean field to the list structure
that the iterator sets True before it begins traversing the list, and
sets False when the iteration is finished. Deletion would then check
this field first, and raise the exception if it is True.

-- 
Jeff Carter
"If you think you got a nasty taunting this time,
you ain't heard nothing yet!"
Monty Python and the Holy Grail

Re: Common sense...

[chris.danx]

"Jeffrey Carter" <jrcarter@acm.org> wrote in message
news:3D26473B.581C61BC@acm.org...
> "chris.danx" wrote:
> >
> > "Jeffrey Carter" <jrcarter@acm.org> wrote in message
> > news:3D25E607.E59E11E2@acm.org...
> > > Deleting nodes from an iterator is erroneous and should raise an
> > > exception.
> >
> > ok but how would you enforce that.  Just not support it?  That's no
bother
> > as the iterators aren't written yet.
>
> The PragmAda Reusable Components' list components' iterators will raise
> an exception (Invalid_Position) if the client-supplied action deletes
> the current node. This is a consequence of assigning a unique ID to each
> list, marking each Position and node with the ID of the associated list,
> and invalidating the ID when a node is deleted.

That is similar to the method the list package uses.  Each list is assigned
an ID, each position within the list has that ID, and an exception is
generated if the ID assigned to the position and the ID of the list don't
match.  This ensures consistancy on removal of nodes.

Additionally, each node in the list holds a count of the number of iterators
and the number of objects which point to it (called positions as they
represent a position in a list).  When both counts go to zero can a node be
deallocated.  If a call to remove/delete is placed on a node, and the count
of either is not zero, the node is marked and skipped by the appropriate
subprograms (next, previous, has_next, has_previous, head, last).

I have my doubts as to whether this will be useful, some ops will be O(1) in
best case and O(n) in worst, when they would usually be O(1) in best,
average, and worst cases.   Perhaps it would be better to raise an exception
if a node held by an iterator is deallocated.  Alternatively, the node could
be marked but not deallocated until the counts both go to zero; with the
effect that any position which holds

So many choices, arghhhhhh!

Re: Common sense...

[Jeffrey Carter]

"chris.danx" wrote:
> 
> Additionally, each node in the list holds a count of the number of iterators
> and the number of objects which point to it (called positions as they
> represent a position in a list).  When both counts go to zero can a node be
> deallocated.  If a call to remove/delete is placed on a node, and the count
> of either is not zero, the node is marked and skipped by the appropriate
> subprograms (next, previous, has_next, has_previous, head, last).

Since iteration is atomic, I don't see how you can have more than one
iterator in action at once. In the presence of concurrency, you need to
have operations protected to ensure consistency; iteration would be one
of those operations.

Keeping a count of positions seems unnecessary. When a node is deleted,
any other positions pointing to it become invalid because you make the
node's ID invalid.

-- 
Jeff Carter
"I blow my nose on you."
Monty Python & the Holy Grail

Re: Common sense...

[Simon Wright]

Jeffrey Carter <jrcarter@acm.org> writes:

> Deleting nodes from an iterator is erroneous and should raise an
> exception.

That's one position, I don't see that it's the only possible one!

Re: Common sense...

[chris.danx]

Hi (again),

the packages have to be as flexible as possible, supporting both bounded and
unbounded data structures.

Which of these two alternatives do ppl feel is better?

aqua.lists.linear.doubly.bounded & aqua.lists.linear.doubly.unbounded

or

aqua.bounded.lists.linear.doubly & aqua.unbounded.lists.linear.doubly


I have no real preference!

Re: Common sense...

[Simon Wright]

"chris.danx" <spamoff.danx@ntlworld.com> writes:

> What's the right thing to do in the following scenario concerning
> iterators and lists?
> 
> A list is in use by three iterators, A, B and C.  A is at the
> position preceding B and C, C calls the remove subroutine on that
> node and moves on.  The nodes iterator count which was 2 is
> decreased to 1.  B is the only iterator using that node, but A wants
> to moves to the next position before B exits the node (if B had
> exited the node prior to A calling next, there'd be no problem).
> Where does A go?  Does it go to the node at B or does it go to the
> one after B?
> 
> I'd say A skips the node but I've got to go, Dinners out, and so
> can't explain my thoughts on why until later!

Although the BCs support some concurrency, I think it's a minefield
and you'd be better off saying DON'T DO THAT!

My (limited) experience of actually _using_ the BCs in a concurrent
situation have convinced me that no general purpose solution is going
to support every usage that your users can dream up, so don't try. I
might (depending on user response) consider deprecating[1] the
concurrency support (at least as built into the BC containers, I think
there's some value in reusable Semaphores, Monitors and Locks maybe).

Consider the comparison with file IO (files are a sort of container,
after all).

[1] Should we lobby for "pragma Deprecate" in Ada0Y ?-)

Re: Common sense...

[chris.danx]

"Simon Wright" <simon@pushface.org> wrote in message
news:x7v3cuxnycc.fsf@pushface.org...
>
> Although the BCs support some concurrency, I think it's a minefield
> and you'd be better off saying DON'T DO THAT!

I've taken your advice, concurrency is something beyond the scope of Aqua,
leaving concurrency issues to the developer who utilises Aqua in such
situations.

So far I'm 95% way through coding and testing a doubly linked list, the test
code is approaching 1000 lines and generates ~20k of data on the lists and
it's operation, while the list itself consists of 600-800 lines, most of
which is comments.  After that a stack, queue and dequeue will be added
almost immediately (and possibly a singly linked list).  Later I plan to add
support for storage pools (separate ADTs with almost the same interface as
the ADTs lacking storage pool support), bounded lists, stacks, queues,
dequeues and a vector adt.

By October, I also hope to have circular lists (and a binary tree) but there
are no promises.  Unfortunately I may not be able to accept any submissions
of code or patches since I may use these ADTs at University and this might
involve some complications (this is a foggy area, I will check with my uni
to see what the policy is and report back.  Any idea who I should speak to?
Teaching Administrator springs to mind)

Oh sod it, after all how long will it take to knock up a linked list or bst
for uni work, a day or two tops; we got 2-4 weeks in second year (maybe more
in third, depends), so if they don't allow their use, it's no problem I'll
make new ADTs!  If anyone wishes to contribute, please say so and I'll put
the current sources up today or tommorrow.  The code is GMGPL'ed.  It'd be
great if someone could work on the storage pool side as I have little or no
familiarity with them and am only casually aware of them.

I'll be away from Monday to Friday next week, so nothing will get done that
week and things will grind to a halt sometime in August as I have exams.

Regards,
Chris