Date: Wed, 24 Sep 1997 10:51:13 -0600 From: "Justin T. Gibbs" <gibbs@plutotech.com> 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 Message-ID: <199709241651.KAA23972@pluto.plutotech.com> In-Reply-To: Your message of "Wed, 24 Sep 1997 10:44:16 MDT." <199709241644.KAA12667@rocky.mt.sri.com>
next in thread | previous in thread | raw e-mail | index | archive | help
>> 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 ===========================================
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709241651.KAA23972>