core workers: Remove an unused variable

Just kill the gcc warnings so we once again compile warning-free.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2084 5f96b256-904b-4d8d-8c98-d829582c6739
lib/bitmap: Fix some compiler warnings

We include string.h for memcpy() and remove the debug printf()s.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2085 5f96b256-904b-4d8d-8c98-d829582c6739
lib/bitmap: Janitor fixes

Remove debug printf()'s and s/bitmaptors/bitmaps/

Blind search and replace from 'bitvector' to 'bitmap' caused the
latter, while sloppiness caused the former.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2086 5f96b256-904b-4d8d-8c98-d829582c6739
.gitignore Documentation dir

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2087 5f96b256-904b-4d8d-8c98-d829582c6739
lib: Make all object-code compilations depend on lnag-utils.h

It sucks when that one's changed and nothing picks up on it.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2088 5f96b256-904b-4d8d-8c98-d829582c6739
lib/bitmap: Add bitmap_resize() and use it in initialization

It's nifty to be able to reuse a single bitmap instead of having
to allocate a new one for a lot of tasks. This makes it possible
to grow and shrink the bitmap dynamically to fit the needs of the
programmer.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2089 5f96b256-904b-4d8d-8c98-d829582c6739
lib/bitmap: Add bitmap_unite()

This function takes the union of two bitmaps but returns the result
in the first bitmap passed. It's incredibly useful when doing dynamic
programming and adding whole sets at a time to the same existing set.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2090 5f96b256-904b-4d8d-8c98-d829582c6739
lib/bitmap: Add the missing bitmap_clear() function

And fix up some comments while we're at it.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2091 5f96b256-904b-4d8d-8c98-d829582c6739
.gitignore some build products and debugging by-products

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2092 5f96b256-904b-4d8d-8c98-d829582c6739
lib/t-utils: Always print the name of failing tests

Previously we always bailed out if we weren't verbose, leading to
us only printing the diagnostic message when tests failed. With
this patch we always print failing tests, even if we're not verbose.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2093 5f96b256-904b-4d8d-8c98-d829582c6739
Store backups when running indent

It's highly annoying to accidentally run the indentation when one's
in the middle of something and not all braces are closed. In theory,
it would be enough to just close the braces and undo the indent,
but in practice it's not quite so simple.

With this patch, astyle at least creates backup files suffixed with
.pre-indent, which lets one easily recover from such a mistake
without having to spend several hours to do it, like I just did
(and still do...).

Thank god for git which let me get the unmodified files back in
just about notime at least.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2094 5f96b256-904b-4d8d-8c98-d829582c6739
lib/skiplist: Add accessor function to get number of items in skiplist

Since the types were made opaque, we need this in order to be able to
get the size of the skiplist at all.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2095 5f96b256-904b-4d8d-8c98-d829582c6739
lib/lnag-utils.h: Janitor fixes

Doxygen stuff, and making __attribute__ available for all library code.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2096 5f96b256-904b-4d8d-8c98-d829582c6739
lib/lnag-utils: Fix ispof2() and rup2pof2()

They weren't cryptic enough before, but with an additional tertiary
statement we get them to be completely illegible for anyone without
an advanced degree in computer science. It also makes them correct,
since we previously claimed that 0 and 1 were prime, and tried to
round up 1 to 1 when rounding to the nearest power of two.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2097 5f96b256-904b-4d8d-8c98-d829582c6739
lib/dkhash: Major fixes

We now check for and disallow duplicates in all hash tables and fix
tests accordingly. The hash function itself has been tweaked to provide
better dispersion for a superset of the default checkcommand list.
More tuning might prove useful, but we can do that if we get some real
data to test it on.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2098 5f96b256-904b-4d8d-8c98-d829582c6739
xdata/xodtemplate: Fix minor macro insanity

objects.h and xodtemplate.h previously had separate macros for which
skiplist to use for which type of objects, but the skiplists were
off by one to match, which screwed up one of my plans for improvement,
so we fix that with this obviously correct patch.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2099 5f96b256-904b-4d8d-8c98-d829582c6739
core: Optimize circular dependency checking

The previous algorithm relied on linear search through a linked list
in order to find the next likely candidate, and once to traverse the
entire list. Since dependencies are edges between two vertices and
we need all three, that meant O(n^3) behaviour in the worst case.
Unfortunately, the worst case was the usual case, since a config
where nodes constitute vertices in an acyclic graph triggered it.

The new algorithm does things differently. In a dependency tree like
this (parent->child, dep->dep or whatever):
  A - B   C
       \ /
        D
       / \
  E - F - G
     /\\
    H  H

... we look at the nodes in the following order:
A B D C G (marking all of them as OK since each is visited only once)
E F D G H F (D,G are already OK, E is marked ok, F and H are loopy)
H (which is already marked as loopy, so we don't follow it to F)

We look at each node at most once per parent, so the algorithm has
O(nx) worst-case complexity, where x is the average number of
parents. It's mathematically impossible to make that particular
code faster, which will make me sleep very soundly tonight ;)

However, since objects only ever care about stuff they depend upon,
as opposed to things that depend on them, we flip the trees upside
down and check from dependent node to depending, since that's the
store we need later. Fortunately, doing validity checks on a
directed acyclic graph works exactly the same no matter which
direction the edges have, so we can still use depth-first search
to detect cyclic paths in the dependency chains.

With an example config containing roughly 22500 servicedependencies,
we make an improvement of about 5062500% in the runtime for this
algorithm, turning 40-ish minutes into about 4 seconds. Not too bad.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2100 5f96b256-904b-4d8d-8c98-d829582c6739
xdata/xodtemplate: Remove xodtemplate_skiplist_compare_text()

The identical one in objects.c named "skiplist_compare_text()" is
the one used anyway, so this is just dead code we're cutting out.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2101 5f96b256-904b-4d8d-8c98-d829582c6739
lib/worker: Fix off-by-four

Two-by-four and off-by-one combined.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2102 5f96b256-904b-4d8d-8c98-d829582c6739
Remove useless 'nexthash' pointer from common objects

We moved to proper container classes when skiplists were implemented,
so using in-object pointers in container classes is just wrong.

Signed-off-by: Andreas Ericsson <ae@op5.se>

git-svn-id: https://nagios.svn.sourceforge.net/svnroot/nagios/nagioscore/trunk@2103 5f96b256-904b-4d8d-8c98-d829582c6739