summaryrefslogtreecommitdiff
path: root/string-list.c
AgeCommit message (Collapse)AuthorFilesLines
2017-10-10cleanup: fix possible overflow errors in binary searchLibravatar Derrick Stolee1-1/+1
A common mistake when writing binary search is to allow possible integer overflow by using the simple average: mid = (min + max) / 2; Instead, use the overflow-safe version: mid = min + (max - min) / 2; This translation is safe since the operation occurs inside a loop conditioned on "min < max". The included changes were found using the following git grep: git grep '/ *2;' '*.c' Making this cleanup will prevent future review friction when a new binary search is contructed based on existing code. Signed-off-by: Derrick Stolee <dstolee@microsoft.com> Reviewed-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2017-07-17use MOVE_ARRAYLibravatar René Scharfe1-5/+3
Simplify the code for moving members inside of an array and make it more robust by using the helper macro MOVE_ARRAY. It calculates the size based on the specified number of elements for us and supports NULL pointers when that number is zero. Raw memmove(3) calls with NULL can cause the compiler to (over-eagerly) optimize out later NULL checks. This patch was generated with contrib/coccinelle/array.cocci and spatch (Coccinelle). Signed-off-by: Rene Scharfe <l.s.r@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2017-05-30Merge branch 'bw/forking-and-threading'Libravatar Junio C Hamano1-0/+18
The "run-command" API implementation has been made more robust against dead-locking in a threaded environment. * bw/forking-and-threading: usage.c: drop set_error_handle() run-command: restrict PATH search to executable files run-command: expose is_executable function run-command: block signals between fork and execve run-command: add note about forking and threading run-command: handle dup2 and close errors in child run-command: eliminate calls to error handling functions in child run-command: don't die in child when duping /dev/null run-command: prepare child environment before forking string-list: add string_list_remove function run-command: use the async-signal-safe execv instead of execvp run-command: prepare command before forking t0061: run_command executes scripts without a #! line t5550: use write_script to generate post-update hook
2017-04-23Merge branch 'jh/string-list-micro-optim'Libravatar Junio C Hamano1-4/+1
The string-list API used a custom reallocation strategy that was very inefficient, instead of using the usual ALLOC_GROW() macro, which has been fixed. * jh/string-list-micro-optim: string-list: use ALLOC_GROW macro when reallocing string_list
2017-04-20string-list: add string_list_remove functionLibravatar Brandon Williams1-0/+18
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>
2017-04-15string-list: use ALLOC_GROW macro when reallocing string_listLibravatar Jeff Hostetler1-4/+1
Use ALLOC_GROW() macro when reallocing a string_list array rather than simply increasing it by 32. This is a performance optimization. During status on a very large repo and there are many changes, a significant percentage of the total run time is spent reallocing the wt_status.changes array. This change decreases the time in wt_status_collect_changes_worktree() from 125 seconds to 45 seconds on my very large repository. This produced a modest gain on my 1M file artificial repo, but broke even on linux.git. Test HEAD^^ HEAD --------------------------------------------------------------------------------------- 0005.2: read-tree status br_ballast (1000001) 8.29(5.62+2.62) 8.22(5.57+2.63) -0.8% Signed-off-by: Jeff Hostetler <jeffhost@microsoft.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2017-01-23string-list: use QSORT_S in string_list_sort()Libravatar René Scharfe1-8/+5
Pass the comparison function to cmp_items() via the context parameter of qsort_s() instead of using a global variable. That allows calling string_list_sort() from multiple parallel threads. Our qsort_s() in compat/ is slightly slower than qsort(1) from glibc 2.24 for sorting lots of lines: Test HEAD^ HEAD --------------------------------------------------------------------- 0071.2: sort(1) 0.10(0.22+0.01) 0.09(0.21+0.00) -10.0% 0071.3: string_list_sort() 0.16(0.15+0.01) 0.17(0.15+0.00) +6.3% GNU sort(1) version 8.26 is significantly faster because it uses multiple parallel threads; with the unportable option --parallel=1 it becomes slower: Test HEAD^ HEAD -------------------------------------------------------------------- 0071.2: sort(1) 0.21(0.18+0.01) 0.20(0.18+0.01) -4.8% 0071.3: string_list_sort() 0.16(0.13+0.02) 0.17(0.15+0.01) +6.3% There is some instability -- the numbers for the sort(1) check shouldn't be affected by this patch. Anyway, the performance of our qsort_s() implementation is apparently good enough, at least for this test. Signed-off-by: Rene Scharfe <l.s.r@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-09-29use QSORTLibravatar René Scharfe1-1/+1
Apply the semantic patch contrib/coccinelle/qsort.cocci to the code base, replacing calls of qsort(3) with QSORT. The resulting code is shorter and supports empty arrays with NULL pointers. Signed-off-by: Rene Scharfe <l.s.r@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2016-04-25string_list: use string-list API in unsorted_string_list_lookup()Libravatar Ralf Thielow1-4/+4
Using the string-list API in function unsorted_string_list_lookup() makes the code more readable. Signed-off-by: Ralf Thielow <ralf.thielow@gmail.com> Acked-by: Johannes Schindelin <johannes.schindelin@gmx.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-12-22Merge branch 'sb/string-list'Libravatar Junio C Hamano1-7/+1
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)
2014-12-04string_list: remove string_list_insert_at_index() from its APILibravatar Stefan Beller1-7/+1
There no longer is a caller to this function. Signed-off-by: Stefan Beller <sbeller@google.com> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-11-25sort_string_list(): rename to string_list_sort()Libravatar Michael Haggerty1-2/+2
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>
2014-09-18use REALLOC_ARRAY for changing the allocation size of arraysLibravatar René Scharfe1-2/+1
Signed-off-by: Rene Scharfe <l.s.r@web.de> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2014-07-21string-list: add string_list initializer helper functionLibravatar Tanay Abhra1-0/+6
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>
2013-01-20Merge branch 'ap/log-mailmap'Libravatar Junio C Hamano1-4/+13
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
2013-01-07string-list: allow case-insensitive string listLibravatar Junio C Hamano1-4/+13
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>
2013-01-02Merge branch 'mh/ceiling'Libravatar Junio C Hamano1-20/+0
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()
2012-11-08string_list: add a function string_list_remove_empty_items()Libravatar Michael Haggerty1-0/+9
Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu> Acked-by: Johan Herland <johan@herland.net> Signed-off-by: Jeff King <peff@peff.net>
2012-10-29string_list_longest_prefix(): remove functionLibravatar Michael Haggerty1-20/+0
This function was added in f103f95b11d087f07c0c48bf784cd9197e18f203 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>
2012-09-12string_list: add a function string_list_longest_prefix()Libravatar Michael Haggerty1-0/+20
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>
2012-09-12string_list: add a new function, string_list_remove_duplicates()Libravatar Michael Haggerty1-0/+17
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>
2012-09-12string_list: add a new function, filter_string_list()Libravatar Michael Haggerty1-0/+17
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>
2012-09-12string_list: add two new functions for splitting stringsLibravatar Michael Haggerty1-0/+53
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>
2012-09-12string_list: add function string_list_append_nodup()Libravatar Michael Haggerty1-5/+15
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>
2011-08-14string-list: Add API to remove an item from an unsorted listLibravatar Johannes Sixt1-0/+9
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>
2011-02-14string_list_append: always set util pointer to NULLLibravatar Jeff King1-0/+1
It is not immediately obvious that the util field may contain random bytes after appending an item. Especially since the string_list_insert* functions _do_ explicitly zero the util pointer. This does not appear to be a bug in any current git code, as all callers either fill in the util field immediately or never use it. However, it is worth it to be less surprising to new users of the string-list API who may expect it to be intialized to NULL. Signed-off-by: Jeff King <peff@peff.net> Signed-off-by: Junio C Hamano <gitster@pobox.com>
2010-06-27string_list: Fix argument order for string_list_appendLibravatar Julian Phillips1-1/+1
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>
2010-06-27string_list: Fix argument order for string_list_lookupLibravatar Julian Phillips1-1/+1
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>
2010-06-27string_list: Fix argument order for string_list_insert_at_indexLibravatar Julian Phillips1-3/+3
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>
2010-06-27string_list: Fix argument order for string_list_insertLibravatar Julian Phillips1-1/+1
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>
2010-06-27string_list: Fix argument order for for_each_string_listLibravatar Julian Phillips1-2/+2
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>
2010-06-27string_list: Fix argument order for print_string_listLibravatar Julian Phillips1-1/+1
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>
2010-03-24string-list: add unsorted_string_list_lookup()Libravatar Stephen Boyd1-3/+10
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>
2009-02-27string-list: new for_each_string_list() functionLibravatar Jay Soffian1-0/+10
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>
2009-02-08Add find_insert_index, insert_at_index and clear_func functions to string_listLibravatar Marius Storm-Olsen1-4/+39
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>
2008-07-21Rename path_list to string_listLibravatar Johannes Schindelin1-0/+134
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>