From owner-freebsd-current Tue Jul 2 15:44:34 2002 Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.FreeBSD.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 20AC837B400 for ; Tue, 2 Jul 2002 15:44:32 -0700 (PDT) Received: from scaup.mail.pas.earthlink.net (scaup.mail.pas.earthlink.net [207.217.120.49]) by mx1.FreeBSD.org (Postfix) with ESMTP id B9E6B43E09 for ; Tue, 2 Jul 2002 15:44:31 -0700 (PDT) (envelope-from tlambert2@mindspring.com) Received: from pool0523.cvx22-bradley.dialup.earthlink.net ([209.179.200.13] helo=mindspring.com) by scaup.mail.pas.earthlink.net with esmtp (Exim 3.33 #1) id 17PWNo-00054m-00; Tue, 02 Jul 2002 18:44:29 -0400 Message-ID: <3D222CA4.80865822@mindspring.com> Date: Tue, 02 Jul 2002 15:43:48 -0700 From: Terry Lambert X-Mailer: Mozilla 4.7 [en]C-CCK-MCD {Sony} (Win98; U) X-Accept-Language: en MIME-Version: 1.0 To: Garrett Wollman Cc: Jonathan Lemon , current@FreeBSD.ORG Subject: Re: additional queue macro References: <20020702095402.D1020@prism.flugsvamp.com> <200207021654.g62Gs67R090813@khavrinen.lcs.mit.edu> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-freebsd-current@FreeBSD.ORG Precedence: bulk List-ID: List-Archive: (Web Archive) List-Help: (List Instructions) List-Subscribe: List-Unsubscribe: X-Loop: FreeBSD.ORG Garrett Wollman wrote: > < said: > > Essentially, this provides a traversal of the tailq that is safe > > from element removal, while being simple to drop in to those sections > > of the code that need updating, as evidenced in the patch below. > > The queue macros always guaranteed that traversal was safe in the > presence of deletions. Julian's change is erroneous and should be > reverted for compatibility with the other implementations of queue(3). Reverting the change won't guarantee safety. In particular, in the remove case, the dereference of the "next" pointer in the removed element is highly dependent on what you do with the removed element. If you bzero it, then you will have a hell of a time dereferencing the pointer correctly. The plan only works correctly where the queue element fields themselves are type-stable (i.e. they do not get reused to link them onto another queue, and they do not get reused for other purposes, or zeroed or filled in with WITNESS or INVARIANTS test values), and if the elements themselves are allocated out of type-stable memory, as part of maintaining that guarantee. The iterator macros are ugly, in that they imply certain semantics, namely that they will work with the other macros that do element manipulations. This turns out not to be true, in the delete case. You could also come up with a failure scenario for tail insertion, or for head insertion, depending on your assumptions about whether or not an insertion while in the loop would result in the loop also doing work on an element, e.g.: loop do_work_on_element(cur_element) if (new_element > cur_element) insert(new_element) ...whether or not the work gets done on the inserted element depends on the insertion method. -- Terry To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-current" in the body of the message