[icinga-checkins] icinga.org: icinga-core/rbartels/cgi: core: use priority based event queue instead of linked lists #2876
git at icinga.org
git at icinga.org
Thu Aug 9 18:04:47 CEST 2012
Author: Michael Friedrich <michael.friedrich at univie.ac.at>
Date: Fri Jul 20 18:30:48 2012 +0200
core: use priority based event queue instead of linked lists #2876
linked lists have O(n) insertion time at worst case. In theory
this should not happen too often, as events should be scheduled
mostly after all other events that are already scheduled. Due to
linear behaviour of the algorithm this might fail.
the squeue-on-top-of-pqueue implementation introduces O(lg n)
behaviour on inserts and removal. pop() (extract next event)
will be altered from O(1) to O(lg n), but overall this will
allow a far more predictable behaviour in larger environments
where the check scheduling does not happen in a fixed interval
for all checks.
extended profiling (previous commit enables that by default,
check the wiki for information how to run profiling) is
the timed_event struct loses the last 2 members, replaced by
an sq_event and priority attribute, but since none of the famous
neb modules make use of that struct, we'll skip compatibility at
that step, since this was introduced by Nagios itsself.
this will make use of the previously introduced pqueue and squeue in
lib/ - extended tests are introduced in lib/ as well.
kudos to Andreas Ericsson for his genius ideas and code.
.gitignore | 4 +
base/checks.c | 28 ++-
base/events.c | 711 ++++++++++++++--------------------------------------
base/icinga.c | 3 +
base/utils.c | 36 +---
common/downtime.c | 31 ++--
include/downtime.h | 6 +
include/icinga.h | 22 +-
lib/Makefile.in | 51 ++++-
lib/squeue.c | 20 +--
lib/test-squeue.c | 217 ++++++++++++++++
11 files changed, 513 insertions(+), 616 deletions(-)
More information about the icinga-checkins