Making this a `double` seems to have been a mistake. Only `int` values are ever
stored into this field and it is only ever compared against `int` values.
Autotools: discover libANN manually if ann.pc is missing
On Debian and Debian derivatives (e.g. Ubuntu) the libann and libann-dev
packages ship without an ann.pc file to support `pkg-config`. As a result of
this, `pkg-config` cannot find libANN and concludes it is not installed.
This change teaches the Autotools build system how to discover libANN manually
if the `pkg-config` technique fails. Note that we need to use `AC_CHECK_FILE`
instead of `AC_CHECK_HEADER` because libANN is in C++.
Similar to the prior situation with Windows platforms, the CMake build on macOS
was failing the long chain test due to insufficient stack reservation. This
change applies the same increase there. Note that there is no need to adjust the
Autotools build, which seems to handle this test case fine on all platforms.
This repairs the long chain test after it was previously inadvertently broken.
Technically going to 32MB is not necessary on all platforms; in release mode,
the MS Build built Graphviz can handle this example with only a 16MB stack. But
it seems simpler to uniformly go to 32MB on all Windows platforms. In a 64-bit
address space, 32MB is trivial and we could even adjust this limit higher in
future. Note that this is the reserved size, not the committed size.
fdpgen mkClusters: use cgraph wrappers for allocation
The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
fdpgen deriveGraph: use cgraph wrapper for allocation
The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
Without tracing the code, it was challenging to see that `K2` was always being
set consistently to evaluate to `K * K`. We can remove this complexity by
simply removing the parameter entirely and computing it on-demand.
Without tracing the code, it was challenging to see that `Ht2` was always being
set consistently to evaluate to `Ht * Ht`. We can remove this complexity by
simply removing the parameter entirely and computing it on-demand.
Without tracing the code, it was challenging to see that `Wd2` was always being
set consistently to evaluate to `Wd * Wd`. We can remove this complexity by
simply removing the parameter entirely and computing it on-demand.
This parameter was only being set conditionally, based on whether `useGrid` was
set, making it look as if the incorrect default value of `0` was being used in
some cases. By tracing the code, it was possible to see the only usage of
`T_Cell2` was under exactly the same conditions as which it was set, making the
use safe. We can remove this complexity by simply removing the parameter
entirely and computing it on-demand.
When hitting either of the error conditions in the loop, the next iteration
would be begun without clearing or freeing the object list. The next call to
`objectList` would overwrite the still-allocated previous object list and it
would be lost.
circogen circomps: use cgraph wrapper for allocation
The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
circogen: replace CDT 'deglist' with a generic list
Apart from de-duplicating some code, this has the following notable effects:
1. The list of nodes is now stored as a contiguous array rather than a linked
list, improving performance characteristics.
2. The list no longer stores degrees, only node pointers. While the code using
this list does modify node degrees, it does not seem to modify the degree
of any node while it is present in the list. So looking up a node’s degree
through the node itself saves some memory overhead.
3. Nodes are inserted into the list and _then_ the list is sorted, rather than
maintaining an always-sorted list. This is a slight performance
improvement.
4. The list is sorted by degree _descending_ now instead of ascending. This
enables operating on the list as a stack, making the pop operation more
efficient.
Using `circo -Tsvg -o /dev/null swedish-flag.dot` on the example attached to
#1718, we have the following:
cgraph: add remove-by-value functionality to the generic list
Note that this assumes elements can be compared using `memcmp` which is not true
for most aggregates. It is the responsibility of the caller to avoid using this
with types that cannot be compared in this way.
cgraph: add sorting functionality to the generic list
Note that this implementation needed to guard the call to `qsort` with a check
that the list is non-empty. UBSan considers passing `NULL` as the first
parameter to `qsort` undefined behavior, even when `nmemb` is 0. I do not know
why this is. I cannot find any text in `qsort` references or ISO C99 to justify
this. But it is simple enough to avoid.
Similarly, passing 0 as `size` causes out-of-bounds accesses in Glibc’s `qsort`.
It is possible there is some text in ISO C99 regarding sizes that indirectly
implies this value must be non-zero. For this implementation, we rely on this
macro never being instantiated with a 0-sized type. It is possible 0-sized types
themselves are impossible without C++’s Empty Base Optimization. I only stumbled
across this quirk of `qsort` by accidentally swapping the `size` and `nmemb`
parameters.
sparse get_or_alloc_force_qt: use cgraph wrapper for allocation
The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
sparse DoubleLinkedList_new: use cgraph wrapper for allocation
The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
sparse SingleLinkedList_new: use cgraph wrapper for allocation
The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
When removing Python 2 support, the discovery paths that checked for the Python
interpreter as `python` were retained to support older distros in the Red Hat
ecosystem where Python 3 goes by the name `python`. All currently supported
distros use the name `python3`, so this code is no longer needed.
projects / graphviz / log