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>
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>
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>
.gitignore Documentation dir

Signed-off-by: Andreas Ericsson <ae@op5.se>
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>
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>
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>
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>
.gitignore some build products and debugging by-products

Signed-off-by: Andreas Ericsson <ae@op5.se>
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>
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>
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>
lib/lnag-utils.h: Janitor fixes

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

Signed-off-by: Andreas Ericsson <ae@op5.se>
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>
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>
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>
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>
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>
lib/worker: Fix off-by-four

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

Signed-off-by: Andreas Ericsson <ae@op5.se>
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>