From owner-freebsd-current  Wed Sep 24 09:56:52 1997
Return-Path: <owner-freebsd-current>
Received: (from root@localhost)
          by hub.freebsd.org (8.8.7/8.8.7) id JAA10319
          for current-outgoing; Wed, 24 Sep 1997 09:56:52 -0700 (PDT)
Received: from ns.mt.sri.com (SRI-56K-FR.mt.net [206.127.65.42])
          by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id JAA10314
          for <current@freebsd.org>; Wed, 24 Sep 1997 09:56:49 -0700 (PDT)
Received: from rocky.mt.sri.com (rocky.mt.sri.com [206.127.76.100])
	by ns.mt.sri.com (8.8.7/8.8.7) with ESMTP id KAA01636;
	Wed, 24 Sep 1997 10:56:46 -0600 (MDT)
Received: (from nate@localhost) by rocky.mt.sri.com (8.7.5/8.7.3) id KAA12715; Wed, 24 Sep 1997 10:56:45 -0600 (MDT)
Date: Wed, 24 Sep 1997 10:56:45 -0600 (MDT)
Message-Id: <199709241656.KAA12715@rocky.mt.sri.com>
From: Nate Williams <nate@mt.sri.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
To: "Justin T. Gibbs" <gibbs@plutotech.com>
Cc: Nate Williams <nate@mt.sri.com>, current@freebsd.org
Subject: Re: new timeout routines 
In-Reply-To: <199709241651.KAA23972@pluto.plutotech.com>
References: <199709241644.KAA12667@rocky.mt.sri.com>
	<199709241651.KAA23972@pluto.plutotech.com>
X-Mailer: VM 6.29 under 19.15 XEmacs Lucid
Sender: owner-freebsd-current@freebsd.org
X-Loop: FreeBSD.org
Precedence: bulk

Justin T. Gibbs writes:
> >> 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.

So far so good.  (It would be the same length as the number of callouts,
or something like it.)

> In your scheme, you need
> to allocate an additional hash table

So far so good.

> and add a set of links to each
> callout entry so it can live both in the callwheel and in the hash
> table.

Huh?  Why?  The hash table contains a direct pointer to the entry which
is the same as the cookie.  Then, it's the exact same code used with
the cookie solution, but w/out requiring changes to the code and
drivers.

No traversing the hash chain (assuming a perfect hash, which should be
pretty easy), and things are still constant time.

Seems pretty obvious/simple to me.


Nate