gvgen: replace 'gv_stack_t' with generic list for int stack
The generic list implementation is an improvement over `gv_stack_t` in that it
is both more flexible and type safe. Migrating to it has two primary
improvements:
1. Maintaining type safety. There is now no need to cast when pushing and
popping the stack. This removes two compiler warnings and leads to shorter,
more readable code.
2. Memory reduction. On 64-bit platforms with a 32-bit int (e.g. x86-64),
`gv_stack_t` uses 8 bytes per int element for storage. In contrast, the
generic list uses 4 bytes per int.
sparse: replace 'IntStack' with generic list implementation
Apart from reducing the amount of code to maintain going forwards, this removes
several warts:
1. `IntStack_push` returned a value indicating whether it succeeded or failed.
The caller was ignoring this. We now exit on push failure.
2. `IntStack_pop` used an awkward flag-based protocol to detect an empty
stack. We now use a cleaner “is empty” guard on the pop call.
3. Iterating over all stack elements sometimes used < length and sometimes
≤ last. There were reasons for this (`SIZE_MAX` was used as a sentinel
last value, and length was calculated based on last). But it led to code
that was harder than necessary to understand at the call site.
CI: hard code platform when running './configure' on Cygwin
The Cygwin Autotools builds have begun failing in CI:
+ ./configure --prefix=/cygdrive/c/GitLab-Runner/builds/smattr/graphviz/
graphviz-7.0.5~dev.20221210.2041/build
checking build system type... config/config.guess: unable to guess system type
This script (version 2018-02-24), has failed to recognize the
operating system you are using. If your script is old, overwrite *all*
copies of config.guess and config.sub with the latest versions from:
https://git.savannah.gnu.org/gitweb/?p=config.git;a=blob_plain;f=config.guess
and
https://git.savannah.gnu.org/gitweb/?p=config.git;a=blob_plain;f=config.sub
If config/config.guess has already been updated, send the following data and any
information you think might be pertinent to config-patches@gnu.org to
provide the necessary information to handle your system.
UNAME_MACHINE = ".x86_64"
UNAME_RELEASE = "3.4.1-1.x86_64"
UNAME_SYSTEM = "CYGWIN_NT-10.0-17763"
UNAME_VERSION = "2022-12-10 19:59 UTC"
configure: error: cannot guess build type; you must specify one
config.guess is one of those scripts that is manually copy-pasted between GNU
projects. In this instance, it is the copy within Automake that is being used.
CI appears to be installing the very latest version of Automake at time of
writing (1.16.5), so upgrading Automake is not a fix here.
Cross referencing the upstream version of config.guess in Savannah¹, there have
been a lot of changes to this file since the version Automake is carrying². But
none of them jump out as something that would affect Cygwin detection in this
way.
So this commit works around the problem on our side. We hard code the guess that
`./configure` should have made. Note that this change uses the guess text from
the newer config.guess, `x86_64-pc-cygwin`, instead of the guess text from the
older version of config.guess Automake is carrying, `x86_64-unknown-cygwin`.
If this problem turns out to have a root cause in Automake and is fixed in
future, we should be able to revert this change.
¹ https://savannah.gnu.org/projects/config/
² 72 commits touching this file since the version Automake is carrying
(2018-02-24). Total diff of these commits to config.guess is 2143 lines.
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.
osage: replace clist implementation with generic list
This replaces some common/memory.h allocations with cgraph/alloc.h, but more
importantly reduces the amount of code to maintain here. Note that confusingly
the list begins with a NULL entry and is only relevant to store later if we have
accrued more than just the initial NULL.
neatogen computeScale: 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.
neatogen computeScaleXY: 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.
neatogen cAdjust: 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.
neatogen mkOverlapSet: return actual point count in 'cntp'
For reasons unclear to me, the `mkOverlapSet` function was constructing a set of
points with an implicit initial 0 point and then notifying the caller of a count
1 _less_ than the total point count. There was nothing wrong with this, but it
led to several instances of non-idiomatic follow-on code that had to account for
an array that was actually 1 longer than what its count variable said.
fdpgen: replace clist implementation with generic list
This replaces some common/memory.h allocations with cgraph/alloc.h, but more
importantly reduces the amount of code to maintain here. Note that confusingly
the list begins with a NULL entry and is only relevant to store later if we have
accrued more than just the initial NULL.
cgraph: inline 'bitarray_new' into 'bitarray_new_or_exit' and rename
All clients of this functionality were calling `bitarray_new_or_exit`. That is,
none of them could cope with failure. In the intervening time since this API was
added, several other exit-on-failure functions have sprung up. For example,
`gv_alloc`. It seems reasonable to now abbreviate this, leading to lesser code
to maintain, with the “or exit” now implicit.
This value is guaranteed to not be negative (an `int` multiplied by itself is
non-negative) and later is compared against `uint64_t` values. So this change
squashes a couple of warnings.
twopigen twopi_init_node_edge: 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.
twopigen getRankseps: 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.
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.
prune: use generalized list implementation for nodes list
This allows preserving type safety (no more `char*` casts needed). We can also
entirely remove prune’s generic list implementation which is no longer used.
prune: use generalized list implementation for attributes list
This allows preserving type safety (no more `strattr_t` casts needed) and the
list items can be managed by value (no more `gv_alloc` for the `sp` being
appended), leading to simpler code.
patchwork: use a 'size_t' for treenode children count
This also involves a cascading series of updates to other variables that are
used to interact with `n_children`. Squashes four -Wsign-conversion warnings.
patchwork layoutTree: 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.
patchwork mkTree: 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.
patchwork mkTreeNode: 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.
patchwork patchwork_init_node_edge: 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.
patchwork mkClusters: 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.
patchwork: replace clist implementation with generic list
This replaces some common/memory.h allocations with cgraph/alloc.h, but more
importantly reduces the amount of code to maintain here. Note that confusingly
the list begins with a NULL entry and is only relevant to store later if we have
accrued more than just the initial NULL.
patchwork tree_map: 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.
outline 'boxes_t' implementation into a generic list
This will allow us to avoid reimplementing variants of the same list data
structure repeatedly. It extends the boxes functions with some other useful
additions and slightly modifies the growth strategy. On first addition, a single
element is now allocated instead of 128. This seems more appropriate for a data
structure that we intend to use more pervasively.
This also replaces common/memory.h allocation that was used in boxes.h with
cgraph/alloc.h calls.
neatogen assign_digcola_levels: 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.
neatogen generateNonoverlapConstraints: 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.
neatogen initCMajVPSC: 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.
neatogen _spline_edges: 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.
neatogen makeObstacle: 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.
neatogen makeSelfArcs: 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.
neatogen newitem: 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.
neatogen make_barriers: 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.
neatogen compute_new_weights: 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.
neatogen compute_apsp_simple: 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.
We can also squash a -Wsign-conversion warning at the same time, noting that the
square of a signed number is always non-negative.
neatogen compute_apsp_dijkstra: 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.
We can also squash a -Wsign-conversion warning at the same time, noting that the
square of a signed number is always non-negative.
fix changelog entry that was entered under an older release
When rebasing 8f60584180071ab9c0f212c3f31aac1d53ed4757, I mistakenly forgot to
adjust its changelog entry for the release that had happened in the intervening
time.
ortho: push trapezoids allocation into 'construct_trapezoids'
This makes it more obvious to readers and the compiler that the value of this
on-entry to `construct_trapezoids` is unimportant and the value does not need to
be retained between the two `construct_trapezoids` calls in `partition`.
The ortho library estimated the number of trapezoid structures it would need
upfront based on the number of segments it was operating on. This estimation was
wrong. Some inputs could exceed the estimation, at which point Graphviz would
abort with an error message.
This change makes trapezoid allocation dynamic, with the trapezoid collection
being expanded on-demand as new trapezoids are needed. The number of the
trapezoids is now only constrained by how much available memory there is.
ortho: stop passing decomposition boxes size around
With the horizontal and vertical decomposition boxes being managed dynamically,
their size is already stored in the `boxes_t` struct and we can use that
instead.
ortho: manage decomposition boxes as dynamic arrays
There is now no need to predict the number of horizontal and vertical
decomposition boxes upfront. The arrays for both are expanded on-demand.
This is a step towards resolving an issue where the upfront estimated trapezoid
count is exceeded, but this is likely an optimization for most workloads where
the estimation is not exceeded. Now fewer decomposition boxes will be allocated
because we generally do not need the full count that was estimated previously.
This is not great practice, putting functions like this into a header. But this
is a stepping stone to reusing this code in lib/ortho and it seems cleaner than
trying to manage yet another set of partially exported symbols.
The number of elements in this array is no longer calculated upfront; we simply
expand the array as needed. This removes one blocker to removing calculation of
the number of trapezoids upfront.
As noted in the comment in this commit, the first element (index 0) is reserved.
I do not know the motivation for this, but various places use index > 0 to
decide if they are dealing with a real node.
ortho init_query_structure: separate assignment statements
This looks like a pure readability change, but is actually preparation for an
upcoming commit. A future commit alters `newnode` to reallocate `qs->data`.
Without the current change, there is no sequence point between the index into
`qs->data` at the start of these lines and the reallocation (in future)
performed by the function call at the end of these lines. This is undefined
behavior with respect to the C standard.
This is quite a subtle problem. I initially did not spot it and was only alerted
by failures under CentOS 7, which encountered nodes with an invalid `nodetype`.
This problem was not reproducible on any other platform, even under ASan and
UBSan. What I believe was going on here is that the combination of the C
compiler and the Glibc on CentOS 7 is the only environment we have which
accidentally leveraged this undefined behavior, by sequencing these operations
as indexing into `qs->data` and _then_ performing the reallocation, resulting in
a write to invalid heap memory.
Similar to the prior changes to `trap_t`, this is a step towards allocating
these on-demand and thus removing predictions/estimations about the total
required qnodes.
ortho: track number of trapezoids along with its array
This is an alternative to passing around `ntraps` or relying on the `TRSIZE`
computation. It is a step towards fixing an issue where the allocated number of
trapezoids is exceeded.
The diff looks large but most of this change is mechanical, migrating `tr` uses
to be aware of the new structure.
This introduces some new warnings, but the intention is to remove these in
upcoming commits as we switch to on-demand allocation.
projects / graphviz / log