--- libev/ev.html 2007/12/07 19:15:39 1.66 +++ libev/ev.html 2007/12/07 19:23:48 1.67 @@ -6,7 +6,7 @@ - +
@@ -2241,6 +2241,11 @@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.
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)
These watchers are stored in lists then need to be walked to find the