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.
`qtree_level_optimizer` would be optionally allocated based on
`n >= ctrl->quadtree_size` but then would only be freed if `USE_QT` was set.
`USE_QT` is always false (it will be removed in an upcoming commit), so this
clean up never runs. This seems latent; I suspect the branch that allocates
`qtree_level_optimizer` is unreachable because this function appears to have
been copy-pasted from one of the other variants in this file with little regard
to how much of it is dead code. But it still seems wise to fix this issue.
sfdpgen check_int_array_size: 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.
sfdpgen check_real_array_size: 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.
remove unused 'PLATFORMSDKINCLUDE_ESCAPED' build system variable
This was using syntax incompatible with POSIX /bin/sh. But the last use of this
was removed in bd879b4583b32e4d13e4b36bea0c20f530fbca0c, so lets just remove it.
projects / graphviz / log