From owner-freebsd-arch@FreeBSD.ORG Fri Mar 16 11:42:27 2007 Return-Path: X-Original-To: arch@freebsd.org Delivered-To: freebsd-arch@FreeBSD.ORG Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 33A8116A402 for ; Fri, 16 Mar 2007 11:42:27 +0000 (UTC) (envelope-from rwatson@FreeBSD.org) Received: from cyrus.watson.org (cyrus.watson.org [209.31.154.42]) by mx1.freebsd.org (Postfix) with ESMTP id 0A91D13C43E for ; Fri, 16 Mar 2007 11:42:26 +0000 (UTC) (envelope-from rwatson@FreeBSD.org) Received: from fledge.watson.org (fledge.watson.org [209.31.154.41]) by cyrus.watson.org (Postfix) with ESMTP id BB74B47454; Fri, 16 Mar 2007 06:15:28 -0500 (EST) Date: Fri, 16 Mar 2007 12:15:28 +0100 (BST) From: Robert Watson X-X-Sender: robert@fledge.watson.org To: Bakul Shah In-Reply-To: <20070315175924.68E265B49@mail.bitblocks.com> Message-ID: <20070316121449.N7579@fledge.watson.org> References: <20070315175924.68E265B49@mail.bitblocks.com> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed Cc: Yar Tikhiy , Poul-Henning Kamp , arch@freebsd.org Subject: Re: bikeshed proposal X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 16 Mar 2007 11:42:27 -0000 On Thu, 15 Mar 2007, Bakul Shah wrote: >> On Tue, Mar 13, 2007 at 09:38:05AM +0000, Poul-Henning Kamp wrote: >>> In message <39968.1173776514@critter.freebsd.dk>, Poul-Henning Kamp writes: >>>> >>>> It has always bothered me that some of the TAILQ macros need to >>>> know the struct name of the header type. >> >> Yeah, can present a challenge in understanding an >> implementation of basic data structures and related algos. :-) You thought >> that tqe_prev points to the whole entry structure when making the patch, >> didn't you? >> >> Personally, I cannot explain to myself why in the double-linked structs the >> prev member points to the next member in the previous list element and not >> to the previous list element itself. Could anybody with CS education >> explain merits of the current approach? I can only see that now we have to >> go to the element before the previous one for a pointer to the latter. >> I'm not going to dispute the current way of things, just curious. > > IIRC, the main reason is so that you don't have to know the actual type of > other things on the list. In particular the list head can be just a > next/prev ptr pair and not the entire object. This is handy, for example, > when you have a list hanging off another object -- you can remove any list > element without detaching the entire list from the parent object. The > queue.h trick is quite clever and useful. To appreciate it, try figuring > out a solution using Lisp style lists! IIRC, your typical CS education > doesn't spend much time on pragmatics. Right now, the queue(9) man page talks a bit about the relative performance of the different list types. It would be interesting to reevaluate their relative performance now that instructions are relatively cheaper, and memory access is relatively more expensive. Robert N M Watson Computer Laboratory University of Cambridge