From: Jamie Lokier <lk@tantalophile.demon.co.uk>
To: george anzinger <george@mvista.com>
Cc: Mark Salisbury <mbs@mc.com>, Ben Greear <greearb@candelatech.com>,
Horst von Brand <vonbrand@sleipnir.valparaiso.cl>,
linux-kernel@vger.kernel.org,
high-res-timers-discourse@lists.sourceforge.net
Subject: Re: No 100 HZ timer!
Date: Tue, 17 Apr 2001 21:41:23 +0200 [thread overview]
Message-ID: <20010417214123.B25583@pcep-jamie.cern.ch> (raw)
In-Reply-To: <200104131205.f3DC5KV11393@sleipnir.valparaiso.cl> <0104160841431V.01893@pc-eng24.mc.com> <3ADB45C0.E3F32257@mvista.com> <01041710225227.01893@pc-eng24.mc.com> <3ADC912A.B497B724@mvista.com>
In-Reply-To: <3ADC912A.B497B724@mvista.com>; from george@mvista.com on Tue, Apr 17, 2001 at 11:53:30AM -0700
george anzinger wrote:
> > > a.) list insertion of an arbitrary timer,
> > should be O(log(n)) at worst
> >
> > > b.) removal of canceled and expired timers, and
> > easy to make O(1)
>
> I thought this was true also, but the priority heap structure that has
> been discussed here has a O(log(n)) removal time.
Several priority queue structures support removal in O(1) time.
Perhaps you are thinking of the classic array-based heap, for
which removal is O(log n) in the general case.
-- Jamie
next prev parent reply other threads:[~2001-04-17 19:42 UTC|newest]
Thread overview: 118+ messages / expand[flat|nested] mbox.gz Atom feed top
2001-04-11 17:56 No 100 HZ timer! Bret Indrelee
2001-04-12 17:39 ` george anzinger
2001-04-12 21:19 ` Bret Indrelee
2001-04-12 22:20 ` george anzinger
2001-04-13 4:00 ` Bret Indrelee
2001-04-13 6:32 ` Ben Greear
2001-04-13 8:42 ` george anzinger
2001-04-13 10:36 ` Jamie Lokier
2001-04-13 16:07 ` george anzinger
2001-04-13 23:00 ` Jamie Lokier
2001-04-13 12:05 ` Horst von Brand
2001-04-13 21:53 ` george anzinger
2001-04-13 23:10 ` Jamie Lokier
2001-04-16 3:02 ` Ben Greear
2001-04-16 2:46 ` Jamie Lokier
2001-04-16 12:36 ` Mark Salisbury
2001-04-16 19:19 ` george anzinger
2001-04-16 20:45 ` Albert D. Cahalan
2001-04-16 21:29 ` Chris Wedgwood
2001-04-16 22:25 ` george anzinger
2001-04-16 23:57 ` Mark Salisbury
2001-04-17 0:45 ` george anzinger
2001-04-17 12:12 ` Mark Salisbury
2001-04-17 12:51 ` Mark Salisbury
2001-04-17 18:53 ` george anzinger
2001-04-17 19:41 ` Jamie Lokier [this message]
2001-04-23 8:05 ` Ulrich Windl
2001-04-23 13:22 ` Mark Salisbury
2001-04-16 2:41 ` Ben Greear
-- strict thread matches above, loose matches on Subject: below --
2001-08-01 17:22 No 100 HZ timer ! george anzinger
2001-08-01 19:34 ` Chris Friesen
2001-08-01 19:49 ` Richard B. Johnson
2001-08-01 20:08 ` Mark Salisbury
2001-08-01 20:33 ` george anzinger
2001-08-01 21:20 ` george anzinger
2001-08-02 4:28 ` Rik van Riel
2001-08-02 6:03 ` george anzinger
2001-08-02 14:39 ` Oliver Xymoron
2001-08-02 16:36 ` george anzinger
2001-08-02 17:05 ` Oliver Xymoron
2001-08-02 17:46 ` george anzinger
2001-08-02 18:41 ` Oliver Xymoron
2001-08-02 21:18 ` george anzinger
2001-08-02 22:09 ` Oliver Xymoron
2001-08-02 17:26 ` John Alvord
2001-04-12 13:14 No 100 HZ timer! Bret Indrelee
2001-04-12 12:58 No 100 HZ timer ! Mark Salisbury
2001-04-11 9:06 schwidefsky
2001-04-10 14:42 schwidefsky
2001-04-10 12:54 schwidefsky
2001-04-10 11:38 schwidefsky
2001-04-10 11:54 ` Alan Cox
2001-04-10 7:29 schwidefsky
2001-04-10 7:27 schwidefsky
2001-04-09 15:54 schwidefsky
2001-04-09 18:30 ` Jeff Dike
2001-04-09 18:19 ` Mark Salisbury
2001-04-09 20:12 ` Alan Cox
2001-04-09 20:32 ` Mark Salisbury
2001-04-09 22:31 ` Mikulas Patocka
2001-04-09 22:35 ` Alan Cox
2001-04-10 11:43 ` David Schleef
2001-04-10 12:04 ` Mikulas Patocka
2001-04-10 12:31 ` David Schleef
2001-04-10 12:34 ` Mark Salisbury
2001-04-10 14:10 ` Mikulas Patocka
2001-04-10 13:35 ` root
2001-04-10 14:22 ` Andi Kleen
2001-04-10 15:43 ` Alan Cox
2001-04-12 5:25 ` watermodem
2001-04-12 8:45 ` Jamie Lokier
2001-04-10 17:15 ` Jamie Lokier
2001-04-10 17:27 ` Alan Cox
2001-04-10 17:35 ` Jamie Lokier
2001-04-10 18:17 ` Alan Cox
2001-04-10 18:24 ` Jamie Lokier
2001-04-10 19:28 ` george anzinger
2001-04-10 20:02 ` mark salisbury
2001-04-10 22:08 ` george anzinger
2001-04-11 0:48 ` Mark Salisbury
2001-04-11 2:35 ` george anzinger
2001-04-12 0:24 ` Mark Salisbury
2001-04-11 16:11 ` Jamie Lokier
2001-04-11 16:59 ` george anzinger
2001-04-11 18:57 ` Jamie Lokier
2001-04-11 19:21 ` John Alvord
2001-04-12 8:41 ` Jamie Lokier
2001-08-01 1:08 ` george anzinger
2001-08-11 11:57 ` Pavel Machek
2001-08-14 15:59 ` Jamie Lokier
2001-08-14 16:57 ` george anzinger
2001-04-10 19:50 ` Zdenek Kabelac
2001-04-11 11:42 ` Maciej W. Rozycki
2001-04-11 16:13 ` Jamie Lokier
2001-04-12 9:51 ` Maciej W. Rozycki
2001-04-10 19:42 ` Zdenek Kabelac
2001-04-10 12:19 ` Mark Salisbury
2001-04-10 17:51 ` yodaiken
2001-04-11 18:43 ` Oliver Xymoron
2001-04-10 12:11 ` Mark Salisbury
2001-04-10 5:51 ` Andi Kleen
2001-04-10 9:33 ` Martin Mares
2001-04-10 10:00 ` Albert D. Cahalan
2001-04-10 12:14 ` Mark Salisbury
2001-04-11 5:55 ` Karim Yaghmour
2001-04-10 11:18 ` Alan Cox
2001-04-10 12:02 ` Andi Kleen
2001-04-10 12:12 ` Alan Cox
2001-04-10 12:27 ` Mark Salisbury
2001-04-10 12:32 ` Andi Kleen
2001-04-10 12:36 ` Alan Cox
2001-04-10 12:37 ` Andi Kleen
2001-04-10 18:45 ` Stephen D. Williams
2001-04-10 19:59 ` Andi Kleen
2001-04-10 12:07 ` Mark Salisbury
2001-04-10 12:45 ` Andi Kleen
2001-04-10 12:42 ` Mark Salisbury
2001-04-10 12:54 ` Andi Kleen
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20010417214123.B25583@pcep-jamie.cern.ch \
--to=lk@tantalophile.demon.co.uk \
--cc=george@mvista.com \
--cc=greearb@candelatech.com \
--cc=high-res-timers-discourse@lists.sourceforge.net \
--cc=linux-kernel@vger.kernel.org \
--cc=mbs@mc.com \
--cc=vonbrand@sleipnir.valparaiso.cl \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).