util-lib: split out allocation calls into alloc-util.[ch]

util-lib: split our string related calls from util.[ch] into its own file string-util.[ch] There are more than enough calls doing string manipulations to deserve its own files, hence do something about it. This patch also sorts the #include blocks of all files that needed to be updated, according to the sorting suggestions from CODING_STYLE. Since pretty much every file needs our string manipulation functions this effectively means that most files have sorted #include blocks now. Also touches a few unrelated include files.

test: hashmap - increase number of entries for crippled hash test The purpose of testing with the crippled hash function is to cover the otherwise very unlikely codepath in bucket_calculate_dib() where it has to fall back to recomputing the hash value. This unlikely path was not covered by test-hashmap anymore after 57217c8f "test: hashmap - cripple the hash function by truncating the input rather than the output". Restore the test coverage by increasing the number of entries in the test. The number was determined empirically by checking with lcov.

hashmap: refactor hash_func All our hash functions are based on siphash24(), factor out siphash_init() and siphash24_finalize() and pass the siphash state to the hash functions rather than the hash key. This simplifies the hash functions, and in particular makes composition simpler as calling siphash24_compress() repeatedly on separate chunks of input has the same effect as first concatenating the input and then calling siphash23_compress() on the result.

test: hashmap - cripple the hash function by truncating the input rather than the output The reason for the crippled hash function is to reduce the distribution of the hash function, do this by truncating the domain rather than the range. This does introduce a change in behavoir as the range is no longer contiguous, which greatly reduces collisions. This is needed as a follow-up patch will no longer allow individual hash functions to alter the output directly.

hashmap: fix iterators to not skip entries Currently, the HASHMAP iterators stop at the first NULL entry in a hashmap. This is non-obvious and breaks users like sd-device, which legitimately store NULL values in a hashmap. Fix all the iterators by taking a pointer to the value storage, instead of returning it. The iterators now return a boolean that tells whether the end of the list was reached. Current users of HASHMAP_FOREACH() are *NOT* changed to explicitly check for NULL. If it turns out, there were users that inserted NULL into hashmaps, but didn't properly check for it during iteration, then we really want to find those and fix them.

test-hashmap: fix an assert CID#1299016

test: hashmap_put behaviour for equal keys Check string ops hashmap_put() for keys with a different pointer but the same value.

test: hashmap-plain - make coverity happy Check return value of hashmap_ensure_allocated(). CID#1250807.

test: use assert_se in test_hashmap_move

test: test a corner case in hashmap_remove_and_replace()

test: adjust max load factor in test_hashmap_many() A reimplementation of hashmaps will follow and it will use 0.8.

hashmap: allow hashmap_move() to fail It cannot fail in the current hashmap implementation, but it may fail in alternative implementations (unless a sufficiently large reservation has been placed beforehand).

test: add test for hashmap_reserve()

test: add and improve hashmap tests Test more corner cases and error states in several tests. Add new tests for: hashmap_move hashmap_remove hashmap_remove2 hashmap_remove_value hashmap_remove_and_replace hashmap_get2 hashmap_first In test_hashmap_many additionally test with an intentionally bad hash function.

test: generate tests for OrderedHashmap from Hashmap tests test-hashmap-ordered.c is generated from test-hashmap-plain.c simply by substituting "ordered_hashmap" for "hashmap" etc. In the cases where tests rely on the order of entries, a distinction between plain and ordered hashmaps is made using the ORDERED macro, which is defined only for test-hashmap-ordered.c.