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.
neatogen: push queue allocation into 'bfs_bounded'
Similar to the previous commit, the callee does not care about the contents of
the queue on entry and the caller does not care about the contents of the queue
on exit. Note that in this case we need to add an extra parameter because
`bfs_bounded` did not have the queue size already.
Callers of `bfs` were constructing `Queue` objects and passing them into `bfs`.
But in all of these cases neither the callee nor the caller care about the
contents of the queue. This appears to have been an optimization to hoist
allocation of this object outside loops in callers. This is nowhere close to the
most expensive operation these locations are performing. And replicating
operations like this led to opportunities for errors like that fixed in the
prior commit. It seems a win to undo this for readability.
neatogen embed_graph: remove free of output parameter
The only call into this function passes `NULL` for the `coords` parameter.
Additionally it did not make much sense to free this pointer on behalf of the
caller. This function is not designed to be called in a loop, so if the caller
wants their passed-in parameter freed they should do it themselves prior to
calling.
projects / graphviz / log