From 39ca7b64db757c30ab6f0dc5dad63206f1d5a375 Mon Sep 17 00:00:00 2001 From: root Date: Fri, 7 Dec 2007 19:23:48 +0000 Subject: *** empty log message *** --- ev.3 | 16 ++++++++-------- ev.html | 14 ++++++++------ ev.pod | 12 +++++++----- import_libevent | 9 +++++++++ 4 files changed, 32 insertions(+), 19 deletions(-) diff --git a/ev.3 b/ev.3 index 6aaee67..dad4e52 100644 --- a/ev.3 +++ b/ev.3 @@ -2406,6 +2406,12 @@ And a \fIev_cpp.C\fR implementation file that contains libev proper and is compi In this section the complexities of (many of) the algorithms used inside libev will be explained. For complexity discussions about backends see the documentation for \f(CW\*(C`ev_default_init\*(C'\fR. +.Sp +All of the following are about amortised time: If an array needs to be +extended, libev needs to realloc and move the whole array, but this +happens asymptotically never with higher number of elements, so O(1) might +mean it might do a lengthy realloc operation in rare cases, but on average +it is much faster and asymptotically approaches constant time. .RS 4 .IP "Starting and stopping timer/periodic watchers: O(log skipped_other_timers)" 4 .IX Item "Starting and stopping timer/periodic watchers: O(log skipped_other_timers)" @@ -2418,16 +2424,10 @@ That means that for changing a timer costs less than removing/adding them as only the relative motion in the event queue has to be paid for. .IP "Starting io/check/prepare/idle/signal/child watchers: O(1)" 4 .IX Item "Starting io/check/prepare/idle/signal/child watchers: O(1)" -These just add the watcher into an array or at the head of a list. If -the array needs to be extended libev needs to realloc and move the whole -array, but this happen asymptotically less and less with more watchers, -thus amortised O(1). -.IP "Stopping check/prepare/idle watchers: O(1)" 4 -.IX Item "Stopping check/prepare/idle watchers: O(1)" -.PD 0 +These just add the watcher into an array or at the head of a list. +=item Stopping check/prepare/idle watchers: O(1) .IP "Stopping an io/signal/child watcher: O(number_of_watchers_for_this_(fd/signal/pid % \s-1EV_PID_HASHSIZE\s0))" 4 .IX Item "Stopping an io/signal/child watcher: O(number_of_watchers_for_this_(fd/signal/pid % EV_PID_HASHSIZE))" -.PD These watchers are stored in lists then need to be walked to find the correct watcher to remove. The lists are usually short (you don't usually have many watchers waiting for the same fd or signal). diff --git a/ev.html b/ev.html index 9192f32..63ddf3b 100644 --- a/ev.html +++ b/ev.html @@ -6,7 +6,7 @@ - + @@ -2241,6 +2241,11 @@ that everybody includes and which overrides some configure choices:

In this section the complexities of (many of) the algorithms used inside libev will be explained. For complexity discussions about backends see the documentation for ev_default_init.

All of the following are about amortised time: If an array needs to be +extended, libev needs to realloc and move the whole array, but this +happens asymptotically never with higher number of elements, so O(1) might +mean it might do a lengthy realloc operation in rare cases, but on average +it is much faster and asymptotically approaches constant time.

Starting and stopping timer/periodic watchers: O(log skipped_other_timers)

Starting io/check/prepare/idle/signal/child watchers: O(1)

These just add the watcher into an array or at the head of a list. If -the array needs to be extended libev needs to realloc and move the whole -array, but this happen asymptotically less and less with more watchers, -thus amortised O(1).

These just add the watcher into an array or at the head of a list. +=item Stopping check/prepare/idle watchers: O(1)

Stopping check/prepare/idle watchers: O(1)

Stopping an io/signal/child watcher: O(number_of_watchers_for_this_(fd/signal/pid % EV_PID_HASHSIZE))

These watchers are stored in lists then need to be walked to find the diff --git a/ev.pod b/ev.pod index 1af7807..14999b3 100644 --- a/ev.pod +++ b/ev.pod @@ -2257,6 +2257,12 @@ In this section the complexities of (many of) the algorithms used inside libev will be explained. For complexity discussions about backends see the documentation for C. +All of the following are about amortised time: If an array needs to be +extended, libev needs to realloc and move the whole array, but this +happens asymptotically never with higher number of elements, so O(1) might +mean it might do a lengthy realloc operation in rare cases, but on average +it is much faster and asymptotically approaches constant time. + =over 4 =item Starting and stopping timer/periodic watchers: O(log skipped_other_timers) @@ -2272,11 +2278,7 @@ as only the relative motion in the event queue has to be paid for. =item Starting io/check/prepare/idle/signal/child watchers: O(1) -These just add the watcher into an array or at the head of a list. If -the array needs to be extended libev needs to realloc and move the whole -array, but this happen asymptotically less and less with more watchers, -thus amortised O(1). - +These just add the watcher into an array or at the head of a list. =item Stopping check/prepare/idle watchers: O(1) =item Stopping an io/signal/child watcher: O(number_of_watchers_for_this_(fd/signal/pid % EV_PID_HASHSIZE)) diff --git a/import_libevent b/import_libevent index 5d205f0..a6433cc 100755 --- a/import_libevent +++ b/import_libevent @@ -1,5 +1,14 @@ #!/bin/sh +if ! [ -e evbuffer.c ]; then + echo do not run this programm unless you know what you are doing + exit 1 +fi + +# this program combines libev and libevent into a single package + +cvs update -AdP + LE=../libevent-1.4.0-beta cp $LE/evdns.h . -- cgit v1.2.3