From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=unavailable autolearn_force=no version=3.4.4 Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!feeder.eternal-september.org!nntp-feed.chiark.greenend.org.uk!ewrotcd!newsfeed.xs3.de!io.xs3.de!news.jacob-sparre.dk!franka.jacob-sparre.dk!pnx.dk!.POSTED.rrsoftware.com!not-for-mail From: "Randy Brukardt" Newsgroups: comp.lang.ada Subject: Re: Ada.Containers and concurrent modification exception. Date: Mon, 24 Sep 2018 16:47:47 -0500 Organization: JSA Research & Innovation Message-ID: References: <64f5bbad-2f06-4ea9-aa33-8c66e9cbb2a5@googlegroups.com> Injection-Date: Mon, 24 Sep 2018 21:47:48 -0000 (UTC) Injection-Info: franka.jacob-sparre.dk; posting-host="rrsoftware.com:24.196.82.226"; logging-data="12852"; mail-complaints-to="news@jacob-sparre.dk" X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2900.5931 X-RFC2646: Format=Flowed; Original X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.7246 Xref: reader02.eternal-september.org comp.lang.ada:54415 Date: 2018-09-24T16:47:47-05:00 List-Id: wrote in message news:b41ee5c2-3000-442f-93cf-67116eac833a@googlegroups.com... ???????, 22 ???????? 2018 ?., 2:27:59 UTC+3 ???????????? Randy Brukardt ???????: >> And it would be wrong: deleting a node from the Map only invalidates >> cursors >> that point at that node, not cursors that point at other nodes in the >> Map. >> Those can continue to be used (for instance, if stored in another >> container) >> until their nodes or the map as a whole are deleted. > >You missed the point, perhaps because I choose obscure names for >properties. Sorry. No, I understood the point quite well. It doesn't work. Consider the following Ada pseudo-code (which you ought to be able to understand regardless of any language barrier): M : Map; R1, R2 : Cursor; M.Insert (..., R1); -- Insert a record saving the cursor. Mod counter = 1. M.Insert (..., R2); -- Mod counter = 2. M.Delete (R1); -- Oops, cursor is invalid, container was modifed since it was created -- but this must work. ... Element (R2) ...; -- Oops, cursor is invalid, container was modifed since it was created, but this must work. ... Element (R1) ...; -- Cursor is invalid, OK to have raise an error here. The important point is that a cursor remains valid until either the container as a whole or the element it designated is deleted. Thus, if you were to use some sort of counter implementation, it has to be per-node (that is, per-element). In addition, some container operations (especially with lists) allow moving nodes from one container to another, so the counter has to be global to all of the containers of a particular type. This brings tasking issues into it. Unlikely Dmitry, I think this check can be done usefully, *but* it can't be done in a way which is 100% accurate. False positives (that is, errors in correct cases) cannot be tolerated, so it necessarily has to be conservative. ... >> when a container is destroyed and a new one created in the same location >It will be created with zero number of modifications. If iterator will have >zero number >of modifications too, nothing wrong happens (just because container is >empty), >otherwise exception will be raised. As noted above, the counter has to be per-element and global to all containers of a given type (at least for some types of containers). So resetting for each container doesn't work. >> It also could fail if the counter wrapped arround >Why? We just need to check if the value of Known_Modifications in iterator >... We're not talking about "iterators", we're talking about cursors. Iterators have the tampering check (an iterator being an active structure that iterates, a for loop being the basic example), which does indeed work like this. (And that is mandated.) Cursors are references, rather similar to access values in Ada. They live individually. >...is equal to the value of Actual_Modifications in container. It is the >reason why I called >they both a State - an unique number that reflects a number of container's >modifications. >And on a 32-bit machine we have a 4_294_967_296 modifications before a >wrap. Remember, this check has to be per-element, as detailed above. Then consider a long-lived program (like a web server, which may run weeks or months) and a data structure that might be modified thousands of times per second. I agree that this is not very likely, but a check based on such a counter cannot detect all possible errors -- 99.9999% perhaps, but that is not a appropriate answer to a requirement. (And it will be much less effective if the memory is returned to the system when nodes are deleted.) >Of course, there is a possibility of check failure exists, but it has very >low probability. Too high in my view to consider it a solution for cursor checks. Especially as they cannot be effective once the memory of the designated node is reclaimed. (For the Janus/Ada implementation, we will delay reclaimation among other tricks to maximize detection, but it's far from perfect.) Randy.