[icinga-checkins] icinga.org: icinga-core/mfriedrich/cgis: core: use priority based event queue instead of linked lists #2876

git at icinga.org git at icinga.org
Wed Aug 1 03:00:46 CEST 2012


Module: icinga-core
Branch: mfriedrich/cgis
Commit: 3e89a677909ebf3523a90047c8ca3b56a2cce8db
URL:    https://git.icinga.org/?p=icinga-core.git;a=commit;h=3e89a677909ebf3523a90047c8ca3b56a2cce8db

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
heavily required!!!

https://wiki.icinga.org/display/Dev/Profiling

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.

refs #2876

---

 .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(-)

Diff:   https://git.icinga.org/?p=icinga-core.git;a=commitdiff;h=3e89a677909ebf3523a90047c8ca3b56a2cce8db




More information about the icinga-checkins mailing list