From owner-freebsd-current  Wed Sep 24 09:51:38 1997
Return-Path: <owner-freebsd-current>
Received: (from root@localhost)
          by hub.freebsd.org (8.8.7/8.8.7) id JAA10028
          for current-outgoing; Wed, 24 Sep 1997 09:51:38 -0700 (PDT)
Received: from pluto.plutotech.com (root@mail.plutotech.com [206.168.67.137])
          by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id JAA10023
          for <current@freebsd.org>; Wed, 24 Sep 1997 09:51:34 -0700 (PDT)
Received: from narnia.plutotech.com (narnia.plutotech.com [206.168.67.130])
	by pluto.plutotech.com (8.8.5/8.8.5) with ESMTP id KAA23972;
	Wed, 24 Sep 1997 10:51:24 -0600 (MDT)
Message-Id: <199709241651.KAA23972@pluto.plutotech.com>
X-Mailer: exmh version 2.0zeta 7/24/97
To: Nate Williams <nate@mt.sri.com>
cc: "Justin T. Gibbs" <gibbs@plutotech.com>,
        Terry Lambert <tlambert@primenet.com>, julian@whistle.com,
        bde@zeta.org.au, current@freebsd.org
Subject: Re: new timeout routines 
In-reply-to: Your message of "Wed, 24 Sep 1997 10:44:16 MDT."
             <199709241644.KAA12667@rocky.mt.sri.com> 
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Date: Wed, 24 Sep 1997 10:51:13 -0600
From: "Justin T. Gibbs" <gibbs@plutotech.com>
Sender: owner-freebsd-current@freebsd.org
X-Loop: FreeBSD.org
Precedence: bulk

>> No-one said this wasn't possible.  It just takes additional space and
>> makes untimeout's running time non-deterministic.  I decided it was
>> an unacceptable tradeoff.
>
>How do you figure?  untimeout is now the same as it was before, or
>aren't the cookies based on a hash table?

The cookie is essentially a direct pointer to the entry that needs to
be removed.  So, removal takes constant time.  In your scheme, you need
to allocate an additional hash table and add a set of links to each
callout entry so it can live both in the callwheel and in the hash
table.  Then, in untimeout, you must traverse a hash chain of indeterminate
length in order to find the entry, hence it is no longer a constant time
operation.  This wouldn't be a problem if untimeout wasn't called from
interrupt contexts, but it is.

>Nate

--
Justin T. Gibbs
===========================================
  FreeBSD: Turning PCs into workstations
===========================================