cgraph: pass destructor as a macro parameter instead of struct member
This smoothes down a number of rough edges in the generic list implementation:
1. No need to noisily cast e.g. `free` as a destructor at the initialization
site.
2. The generic list struct is reduced by the size of a function pointer. This
is not significant when a list is used entirely locally as the compiler can
destructure this type as an optimization. But when passing objects of this
type between functions, this can help.
3. Some functions like free of the generic list zeroed the structure, losing
the destructor. This could be improved by retaining it, but it seemed
simpler to remove the opportunity for this confusion altogether.
An alternative to creating the new `DEFINE_LIST_WITH_DTOR` macro would be to
implement `DEFINE_LIST` as a variadic macro, taking an optional third parameter.
However the gymnastics required to achieve this in C99 (search the internet for
macro argument counting) make it not worth it.
common parse_style: remove static backing buffer for 'ps_xb'
There seems little value retaining this when it adds complication and was a
contributing factor in the bug just fixed. This potentially slightly degrades
performance (initial style use results in a heap allocation), but is unlikely to
be measurable and should be regained back if we implement Small String
Optimization on `agxbuf`.
fix out-of-bounds memory reads with large 'style' strings
Parsing a large style would acquire pointers into the `agxbuf` it wrote into,
but then go on to append more data to the buffer, potentially triggering a
reallocation thus leaving those prior pointers dangling. Later attempts to
access the style would read from these (now invalid) pointers. This bug has
existed since the very first commit of Graphviz.
Note that this change does nothing to alter the NUL-separated-string design of
the return value of `parse_style`. This still remains because some callers rely
on it, despite it being known as problematic.
common printTok: remove use of 'agxbstart' to access agxbuf data
Reaching into something that is notionally the internals of the `agxbuf` type
was causing some complications in upcoming changes. Specifically, the lifetime
of the pointer returned from `agxbstart` makes it error prone. Any operation
that appends more data to the `agxbuf` must conservatively be assumed to
invalidate a pointer previously returned from `agxbstart`.
Although this instance was not retaining the returned pointer, the `agxbstart`
interface seems dangerous to provide given that it is difficult to use safely.
By removing its sole use here, we clear the way for its removal in future.
This new phrasing is potentially less efficient, as data is now extracted from
the buffer and then written back into the same buffer. However (1) a good
contemporary compiler will inline all calls and realize the accumulated
operation on the buffer is a no-op and (2) this is debug code, so performance is
not critical.
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.