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=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,93ab7fc5388e249 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-12-06 09:46:44 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!cpk-news-hub1.bbnplanet.com!news.gtei.net!newsfeed1.cidera.com!Cidera!cyclone.socal.rr.com!cyclone3.kc.rr.com!news3.kc.rr.com!typhoon.san.rr.com!not-for-mail Message-ID: <3C0FAF0C.A46BB265@san.rr.com> From: Darren New X-Mailer: Mozilla 4.77 [en] (Windows NT 5.0; U) X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: List container strawman 1.3 References: <3C0E1FA1.45A38A75@brighton.ac.uk> <%7sP7.49836$xS6.82296@www.newsranger.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Date: Thu, 06 Dec 2001 17:47:20 GMT NNTP-Posting-Host: 66.75.151.160 X-Complaints-To: abuse@rr.com X-Trace: typhoon.san.rr.com 1007660840 66.75.151.160 (Thu, 06 Dec 2001 09:47:20 PST) NNTP-Posting-Date: Thu, 06 Dec 2001 09:47:20 PST Organization: Road Runner Xref: archiver1.google.com comp.lang.ada:17519 Date: 2001-12-06T17:47:20+00:00 List-Id: Ted Dennison wrote: > The list itself will have to > keep a mini-list of iterators to support invalidating iterators whoose > pointed-to item is removed. This could be done by checking at the time of access thru the invalid iterator, rather than by checking during deletes. For efficiency, keep track in each iterator and each list head the number of deletes (or other operations that might invalidate an iterator) that have occurred. If an iterator is accessed when that counter in the iterator is smaller than the counter in the list it's iterating, run through the list (O(N)) and check if the iterator is pointing to one of the still-existant nodes. It's a performance trade-off that works well when you're doing a lot of list manipulations with few iterators per list, which I would assume is a common case. -- Darren New San Diego, CA, USA (PST). Cryptokeys on demand. You will soon read a generic fortune cookie.