It is sometimes useful to reduce the size of a `string_list`'s list of
items without having to re-allocate them. For example, doing the
following:
struct strbuf buf = STRBUF_INIT;
struct string_list parts = STRING_LIST_INIT_NO_DUP;
while (strbuf_getline(&buf, stdin) != EOF) {
parts.nr = 0;
string_list_split_in_place(&parts, buf.buf, ":", -1);
/* ... */
}
string_list_clear(&parts, 0);
is preferable over calling `string_list_clear()` on every iteration of
the loop. This is because `string_list_clear()` causes us free our
existing `items` array. This means that every time we call
`string_list_split_in_place()`, the string-list internals re-allocate
the same size array.
Since in the above example we do not care about the individual parts
after processing each line, it is much more efficient to pretend that
there aren't any elements in the `string_list` by setting `list->nr` to
0 while leaving the list of elements allocated as-is.
This allows `string_list_split_in_place()` to overwrite any existing
entries without needing to free and re-allocate them.
However, setting `list->nr` manually is not safe in all instances. There
are a couple of cases worth worrying about:
- If the `string_list` is initialized with `strdup_strings`,
truncating the list can lead to overwriting strings which are
allocated elsewhere. If there aren't any other pointers to those
strings other than the ones inside of the `items` array, they will
become unreachable and leak.
(We could ourselves free the truncated items between
string_list->items[nr] and `list->nr`, but no present or future
callers would benefit from this additional complexity).
- If the given `nr` is larger than the current value of `list->nr`,
we'll trick the `string_list` into a state where it thinks there are
more items allocated than there actually are, which can lead to
undefined behavior if we try to read or write those entries.
Guard against both of these by introducing a helper function which
guards assignment of `list->nr` against each of the above conditions.
Co-authored-by: Jeff King <peff@peff.net>
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Enhance `string_list_split_in_place()` to accept multiple characters as
delimiters instead of a single character.
Instead of using `strchr(2)` to locate the first occurrence of the given
delimiter character, `string_list_split_in_place_multi()` uses
`strcspn(2)` to move past the initial segment of characters comprised of
any characters in the delimiting set.
When only a single delimiting character is provided, `strpbrk(2)` (which
is implemented with `strcspn(2)`) has equivalent performance to
`strchr(2)`. Modern `strcspn(2)` implementations treat an empty
delimiter or the singleton delimiter as a special case and fall back to
calling strchrnul(). Both glibc[1] and musl[2] implement `strcspn(2)`
this way.
This change is one step to removing `strtok(2)` from the tree. Note that
`string_list_split_in_place()` is not a strict replacement for
`strtok()`, since it will happily turn sequential delimiter characters
into empty entries in the resulting string_list. For example:
string_list_split_in_place(&xs, "foo:;:bar:;:baz", ":;", -1)
would yield a string list of:
["foo", "", "", "bar", "", "", "baz"]
Callers that wish to emulate the behavior of strtok(2) more directly
should call `string_list_remove_empty_items()` after splitting.
To avoid regressions for the new multi-character delimter cases, update
t0063 in this patch as well.
[1]: https://sourceware.org/git/?p=glibc.git;a=blob;f=string/strcspn.c;hb=glibc-2.37#l35
[2]: https://git.musl-libc.org/cgit/musl/tree/src/string/strcspn.c?h=v1.2.3#n11
Signed-off-by: Taylor Blau <me@ttaylorr.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
The for_each_string_list_item() macro takes a string_list and
automatically constructs a for loop to iterate over its contents. This
macro will segfault if the list is non-NULL.
We cannot change the macro to be careful around NULL values because
there are many callers that use the address of a local variable, which
will never be NULL and will cause compile errors with -Werror=address.
For now, leave a documentation comment to try to avoid mistakes in the
future where a caller does not check for a NULL list.
Signed-off-by: Derrick Stolee <derrickstolee@github.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Change the "nr" and "alloc" members of "struct string_list" to use
"size_t" instead of "nr". On some platforms the size of an "unsigned
int" will be smaller than a "size_t", e.g. a 32 bit unsigned v.s. 64
bit unsigned. As "struct string_list" is a generic API we use in a lot
of places this might cause overflows.
As one example: code in "refs.c" keeps track of the number of refs
with a "size_t", and auxiliary code in builtin/remote.c in
get_ref_states() appends those to a "struct string_list".
While we're at it split the "nr" and "alloc" in string-list.h across
two lines, which is the case for most such struct member
declarations (e.g. in "strbuf.h" and "strvec.h").
Changing e.g. "int i" to "size_t i" in run_and_feed_hook() isn't
strictly necessary, and there are a lot more cases where we'll use a
local "int", "unsigned int" etc. variable derived from the "nr" in the
"struct string_list". But in that case as well as
add_wrapped_shortlog_msg() in builtin/shortlog.c we need to adjust the
printf format referring to "nr" anyway, so let's also change the other
variables referring to it.
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Remove this function left over to accommodate in-flight changes, see
770fedaf9f (string-list.[ch]: add a string_list_init_{nodup,dup}(),
2021-07-01) for the recent change to add
"string_list_init_{nodup,dup}()" initializers.
There was only one user of the API left in remote-curl.c. I don't know
why I didn't include this change to remote-curl.c in
bc40dfb10a (string-list.h users: change to use *_{nodup,dup}(),
2021-07-01), perhaps I just missed it.
In any case, let's change that one user to use the new API, as of
writing this there are no in-flight changes that use, so this seems
like a good time to drop this before we get any new users of this
compatibility API.
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
In order to use the new "memcpy() a 'blank' struct on the stack"
pattern for string_list_init(), and to make the macro initialization
consistent with the function initialization introduce two new
string_list_init_{nodup,dup}() functions. These are like the old
string_list_init() when called with a false and true second argument,
respectively.
I think this not only makes things more consistent, but also easier to
read. I often had to lookup what the ", 0)" or ", 1)" in these
invocations meant, now it's right there in the function name, and
corresponds to the macros.
A subsequent commit will convert existing API users to this pattern,
but as this is a very common API let's leave a compatibility function
in place for later removal. This intermediate state also proves that
the compatibility function works.
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Move *_INIT macros I'll use in a subsequent commits to designated
initializers. This isn't required for those follow-up changes, but
since next commits will change things in this area, let's use the
modern pattern over the old one while we're at it.
Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
In commit 1959bf6430 (string_list API: document what "sorted" means,
2012-09-17), Documentation/technical/api-string-list.txt was updated to
specify that strcmp() was used for sorting. In commit 8dd5afc926
(string-list: allow case-insensitive string list, 2013-01-07), a cmp
member was added to struct string_list to allow callers to specify an
alternative comparison function, but api-string-list.txt was not
updated. In commit 4f665f2cf3 (string-list.h: move documentation from
Documentation/api/ into header, 2017-09-26), the now out-dated
api-string-list.txt documentation was moved into string-list.h. Update
the docs to reflect the configurability of sorting.
Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
In previous patches, extern was mechanically removed from function
declarations without care to formatting, causing parameter lists to be
misaligned. Manually format changed sections such that the parameter
lists should be realigned.
Viewing this patch with 'git diff -w' should produce no output.
Signed-off-by: Denton Liu <liu.denton@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
There has been a push to remove extern from function declarations.
Remove some instances of "extern" for function declarations which are
caught by Coccinelle. Note that Coccinelle has some difficulty with
processing functions with `__attribute__` or varargs so some `extern`
declarations are left behind to be dealt with in a future patch.
This was the Coccinelle patch used:
@@
type T;
identifier f;
@@
- extern
T f(...);
and it was run with:
$ git ls-files \*.{c,h} |
grep -v ^compat/ |
xargs spatch --sp-file contrib/coccinelle/noextern.cocci --in-place
Files under `compat/` are intentionally excluded as some are directly
copied from external sources and we should avoid churning them as much
as possible.
Signed-off-by: Denton Liu <liu.denton@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
A removal of this helper function was proposed 3 years ago [1]; the
function was never used since it was introduced in 2006 back then,
and there is no new callers since. Now time has proven we really do
not need the function.
[1] https://public-inbox.org/git/1421343725-3973-1-git-send-email-kuleshovmail@gmail.com/
Signed-off-by: Stefan Beller <sbeller@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
This mirrors commit 'bdfdaa497 ("strbuf.h: integrate api-strbuf.txt
documentation, 2015-01-16") which did the same for strbuf.h:
* API documentation uses /** */ to set it apart from other comments.
* Function names were stripped from the comments.
* Ordering of the header was adjusted to follow the one from the text
file.
* Edited some existing comments from string-list.h for consistency.
Signed-off-by: Han-Wen Nienhuys <hanwen@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
If you pass a newly initialized or newly cleared `string_list` to
`for_each_string_list_item()`, then the latter does
for (
item = (list)->items; /* NULL */
item < (list)->items + (list)->nr; /* NULL + 0 */
++item)
Even though this probably works almost everywhere, it is undefined
behavior, and it could plausibly cause highly-optimizing compilers to
misbehave. C99 section 6.5.6 paragraph 8 explains:
If both the pointer operand and the result point to elements
of the same array object, or one past the last element of the
array object, the evaluation shall not produce an overflow;
otherwise, the behavior is undefined.
and (6.3.2.3.3) a null pointer does not point to anything.
Guard the loop with a NULL check to make the intent crystal clear to
even the most pedantic compiler. A suitably clever compiler could let
the NULL check only run in the first iteration, but regardless, this
overhead is likely to be dwarfed by the work to be done on each item.
This problem was noticed by Coverity.
[jn: using a NULL check instead of a placeholder empty list;
fleshed out the commit message based on mailing list discussion]
Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Teach string-list to be able to remove a string from a sorted
'struct string_list'.
Signed-off-by: Brandon Williams <bmwill@google.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
API simplification.
* sb/string-list:
string_list: remove string_list_insert_at_index() from its API
mailmap: use higher level string list functions
string_list: document string_list_(insert,lookup)
The new name is more consistent with the names of other
string_list-related functions.
Suggested-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
The string-list API has STRING_LIST_INIT_* macros to be used
to define variables with initializers, but lacks functions
to initialize an uninitialized piece of memory to be used as
a string-list at the run-time.
Introduce `string_list_init()` function for that.
Signed-off-by: Tanay Abhra <tanayabh@gmail.com>
Reviewed-by: Matthieu Moy <Matthieu.Moy@imag.fr>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
STRING_LIST_INIT_{NODUP,DUP} initializers list values only
for earlier structure members, relying on the usual
convention in C that the omitted members are initailized to
0, i.e. the former is expanded to the latter:
struct string_list l = STRING_LIST_INIT_DUP;
struct string_list l = { NULL, 0, 0, 1 };
and the last member that is not mentioned (i.e. 'cmp') is
initialized to NULL.
While there is nothing wrong in this construct, spelling out
all the values where the macros are defined will serve also
as a documentation, so let's do so.
Signed-off-by: Tanay Abhra <tanayabh@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Teach commands in the "log" family to optionally pay attention to
the mailmap.
* ap/log-mailmap:
log --use-mailmap: optimize for cases without --author/--committer search
log: add log.mailmap configuration option
log: grep author/committer using mailmap
test: add test for --use-mailmap option
log: add --use-mailmap option
pretty: use mailmap to display username and email
mailmap: add mailmap structure to rev_info and pp
mailmap: simplify map_user() interface
mailmap: remove email copy and length limitation
Use split_ident_line to parse author and committer
string-list: allow case-insensitive string list
Some string list needs to be searched case insensitively, and for
that to work correctly, the string needs to be sorted case
insensitively from the beginning.
Allow a custom comparison function to be defined on a string list
instance and use it throughout in place of strcmp().
Signed-off-by: Junio C Hamano <gitster@pobox.com>
An element on GIT_CEILING_DIRECTORIES list that does not name the
real path to a directory (i.e. a symbolic link) could have caused
the GIT_DIR discovery logic to escape the ceiling.
* mh/ceiling:
string_list_longest_prefix(): remove function
setup_git_directory_gently_1(): resolve symlinks in ceiling paths
longest_ancestor_length(): require prefix list entries to be normalized
longest_ancestor_length(): take a string_list argument for prefixes
longest_ancestor_length(): use string_list_split()
Introduce new function real_path_if_valid()
real_path_internal(): add comment explaining use of cwd
Introduce new static function real_path_internal()
This function was added in f103f95b11 in
the erroneous expectation that it would be used in the
reimplementation of longest_ancestor_length(). But it turned out to
be easier to use a function specialized for comparing path prefixes
(i.e., one that knows about slashes and root paths) than to prepare
the paths in such a way that a generic string prefix comparison
function can be used. So delete string_list_longest_prefix() and its
documentation and test cases.
Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Jeff King <peff@peff.net>
Add a function that finds the longest string from a string_list that
is a prefix of a given string.
Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Add a function that deletes duplicate entries from a sorted
string_list.
Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
This function allows entries that don't match a specified criterion to
be discarded from a string_list while preserving the order of the
remaining entries.
Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Add two new functions, string_list_split() and
string_list_split_in_place(). These split a string into a string_list
on a separator character. The first makes copies of the substrings
(leaving the input string untouched) and the second splits the
original string in place, overwriting the separator characters with
NULs and referring to the original string's memory.
These functions are similar to the strbuf_split_*() functions except
that they work with the more powerful string_list interface.
Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Add a new function that appends a string to a string_list without
copying it. This can be used to pass ownership of an already-copied
string to a string_list that has strdup_strings set.
Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Teach the string-list API how to remove an entry in O(1) runtime by
moving the last entry to the vacated spot. As such, the routine works
only for unsorted lists.
Signed-off-by: Johannes Sixt <j6t@kdbg.org>
Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
In a struct definitions, unlike functions, the prevailing style is for
the opening brace to go on the same line as the struct name, like so:
struct foo {
int bar;
char *baz;
};
Indeed, grepping for 'struct [a-z_]* {$' yields about 5 times as many
matches as 'struct [a-z_]*$'.
Linus sayeth:
Heretic people all over the world have claimed that this inconsistency
is ... well ... inconsistent, but all right-thinking people know that
(a) K&R are _right_ and (b) K&R are right.
Signed-off-by: Jonathan Nieder <jrnieder@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
This is more lightweight than a call to for_each_string_list function with
callback function and a cookie argument.
Signed-off-by: Alex Riesen <raa.lkml@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Update the definition and callers of string_list_append to use the
string_list as the first argument. This helps make the string_list
API easier to use by being more consistent.
Signed-off-by: Julian Phillips <julian@quantumfyre.co.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Update the definition and callers of string_list_lookup to use the
string_list as the first argument. This helps make the string_list
API easier to use by being more consistent.
Signed-off-by: Julian Phillips <julian@quantumfyre.co.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Update the definition and callers of string_list_insert_at_index to
use the string_list as the first argument. This helps make the
string_list API easier to use by being more consistent.
Signed-off-by: Julian Phillips <julian@quantumfyre.co.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Update the definition and callers of string_list_insert to use the
string_list as the first argument. This helps make the string_list
API easier to use by being more consistent.
Signed-off-by: Julian Phillips <julian@quantumfyre.co.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Update the definition and callers of for_each_string_list to use the
string_list as the first argument. This helps make the string_list
API easier to use by being more consistent.
Signed-off-by: Julian Phillips <julian@quantumfyre.co.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Update the definition and callers of print_string_list to use the
string_list as the first argument. This helps make the API easier to
use by being more consistent.
Signed-off-by: Julian Phillips <julian@quantumfyre.co.uk>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Sometimes users need to lookup a string in an unsorted string_list. In
that case they should use this function instead of the version for
sorted strings.
Signed-off-by: Stephen Boyd <bebarino@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Add a convenience function for iterating over a string_list's items via
a callback.
Signed-off-by: Jay Soffian <jaysoffian@gmail.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
string_list_find_insert_index() and string_list_insert_at_index()
enables you to see if an item is in the string_list, and to
insert at the appropriate index in the list, if not there.
This is usefull if you need to manipulate an existing item,
if present, and insert a new item if not.
Future mailmap code will use this construct to enable
complex (old_name, old_email) -> (new_name, new_email)
lookups.
The string_list_clear_func() allows to call a custom
cleanup function on each item in a string_list, which is
useful is the util member points to a complex structure.
Signed-off-by: Marius Storm-Olsen <marius@trolltech.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
The name path_list was correct for the first usage of that data structure,
but it really is a general-purpose string list.
$ perl -i -pe 's/path-list/string-list/g' $(git grep -l path-list)
$ perl -i -pe 's/path_list/string_list/g' $(git grep -l path_list)
$ git mv path-list.h string-list.h
$ git mv path-list.c string-list.c
$ perl -i -pe 's/has_path/has_string/g' $(git grep -l has_path)
$ perl -i -pe 's/path/string/g' string-list.[ch]
$ git mv Documentation/technical/api-path-list.txt \
Documentation/technical/api-string-list.txt
$ perl -i -pe 's/strdup_paths/strdup_strings/g' $(git grep -l strdup_paths)
... and then fix all users of string-list to access the member "string"
instead of "path".
Documentation/technical/api-string-list.txt needed some rewrapping, too.
Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Taylor Blau