Date: Wed, 24 Sep 1997 10:56:45 -0600 (MDT) From: Nate Williams <nate@mt.sri.com> To: "Justin T. Gibbs" <gibbs@plutotech.com> Cc: Nate Williams <nate@mt.sri.com>, current@freebsd.org Subject: Re: new timeout routines Message-ID: <199709241656.KAA12715@rocky.mt.sri.com> In-Reply-To: <199709241651.KAA23972@pluto.plutotech.com> References: <199709241644.KAA12667@rocky.mt.sri.com> <199709241651.KAA23972@pluto.plutotech.com>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709241656.KAA12715>