src/util.h


Log

Author Commit Date CI Message
Edward Thomson 75a4636f 2015-05-29T16:56:38 git__tolower: a tolower() that isn't dumb Some brain damaged tolower() implementations appear to want to take the locale into account, and this may require taking some insanely aggressive lock on the locale and slowing down what should be the most trivial of trivial calls for people who just want to downcase ASCII.
Jeff Hostetler d06c589f 2015-04-10T06:15:06 Add MSVC CRTDBG memory leak reporting.
Edward Thomson f1453c59 2015-02-12T12:19:37 Make our overflow check look more like gcc/clang's Make our overflow checking look more like gcc and clang's, so that we can substitute it out with the compiler instrinsics on platforms that support it. This means dropping the ability to pass `NULL` as an out parameter. As a result, the macros also get updated to reflect this as well.
Edward Thomson 190b76a6 2015-02-11T14:52:08 Introduce git__add_sizet_overflow and friends Add some helper functions to check for overflow in a type-specific manner.
Edward Thomson 8d534b47 2015-02-11T13:01:00 p_read: ensure requested len is ssize_t Ensure that the given length to `p_read` is of ssize_t and ensure that callers test the return as if it were an `ssize_t`.
Edward Thomson 2884cc42 2015-02-11T09:39:38 overflow checking: don't make callers set oom Have the ALLOC_OVERFLOW testing macros also simply set_oom in the case where a computation would overflow, so that callers don't need to.
Edward Thomson 3603cb09 2015-02-10T23:13:49 git__*allocarray: safer realloc and malloc Introduce git__reallocarray that checks the product of the number of elements and element size for overflow before allocation. Also introduce git__mallocarray that behaves like calloc, but without the `c`. (It does not zero memory, for those truly worried about every cycle.)
Edward Thomson 392702ee 2015-02-09T23:41:13 allocations: test for overflow of requested size Introduce some helper macros to test integer overflow from arithmetic and set error message appropriately.
Maks Naumov d8b5c8c3 2015-01-15T15:16:19 Remove strlen() calls from loop condition Avoid str length recalculation every iteration
Sebastian Bauer 7cf86f92 2014-12-28T10:35:26 Added AmigaOS-specific implementation of git__timer(). The clock_gettime() function is normally not available under AmigaOS, hence another solution is required. We are using now GetUpTime() that is present in current versions of this operating system.
Edward Thomson fe5f7722 2014-12-23T11:27:01 don't treat 0x85 as whitespace A byte value of 0x85 is not whitespace, we were conflating that with U+0085 (UTF8: 0xc2 0x85). This caused us to incorrectly treat valid multibyte characters like U+88C5 (UTF8: 0xe8 0xa3 0x85) as whitespace.
Vicent Marti 8e35527d 2014-12-16T13:03:02 path: Use UTF8 iteration for HFS chars
Edward Thomson a64119e3 2014-11-25T18:13:00 checkout: disallow bad paths on win32 Disallow: 1. paths with trailing dot 2. paths with trailing space 3. paths with trailing colon 4. paths that are 8.3 short names of .git folders ("GIT~1") 5. paths that are reserved path names (COM1, LPT1, etc). 6. paths with reserved DOS characters (colons, asterisks, etc) These paths would (without \\?\ syntax) be elided to other paths - for example, ".git." would be written as ".git". As a result, writing these paths literally (using \\?\ syntax) makes them hard to operate with from the shell, Windows Explorer or other tools. Disallow these.
Russell Belfer 3822d2cc 2014-08-05T15:06:45 Fix typo in timer normalization constants The effect of this would be that various update callbacks would not be made at the correct interval.
Russell Belfer 947a58c1 2014-05-30T13:19:49 Clean up the handling of large binary diffs
Russell Belfer cd424ad5 2014-04-28T16:39:53 Add GIT_STATUS_OPT_UPDATE_INDEX and use trace API This adds an option to refresh the stat cache while generating status. It also rips out the GIT_PERF stuff I had an makes use of the trace API to keep statistics about what happens during diff.
Russell Belfer 240f4af3 2014-04-28T14:04:29 Add build option for diff internal statistics
Philip Kelley 7110000d 2014-04-22T10:21:19 React to feedback for UTF-8 <-> WCHAR and reparse work
Russell Belfer 3b4c401a 2014-02-10T13:20:08 Decouple index iterator sort from index This makes the index iterator honor the GIT_ITERATOR_IGNORE_CASE and GIT_ITERATOR_DONT_IGNORE_CASE flags without modifying the index data itself. To take advantage of this, I had to export a number of the internal index entry comparison functions. I also wrote some new tests to exercise the capability.
Jacques Germishuys 8e14b47f 2014-04-10T12:42:29 Introduce git__date_rfc2822_fmt. Allows for RFC2822 date headers
Carlos Martín Nieto 24f3024f 2014-02-05T14:31:01 Split p_strlen into its own header We need this from util.h and posix.h, but the latter includes common.h which includes util.h, which means p_strlen is not defined by the time we get to git__strndup(). Split the definition on p_strlen() off into its own header so we can use it in util.h.
Carlos Martín Nieto 1e6f0ac4 2014-02-05T13:49:51 utils: don't reimplement strnlen The standard library provides a very nice strnlen function, which knows to use SSE, let's not reimplement it ourselves.
Ben Straub 816d28e7 2013-10-01T12:56:47 Mark git__timer as inline on OSX
Jameson Miller b176eded 2013-09-19T14:52:57 Initial Implementation of progress reports during push This adds the basics of progress reporting during push. While progress for all aspects of a push operation are not reported with this change, it lays the foundation to add these later. Push progress reporting can be improved in the future - and consumers of the API should just get more accurate information at that point. The main areas where this is lacking are: 1) packbuilding progress: does not report progress during deltafication, as this involves coordinating progress from multiple threads. 2) network progress: reports progress as objects and bytes are going to be written to the subtransport (instead of as client gets confirmation that they have been received by the server) and leaves out some of the bytes that are transfered as part of the push protocol. Basically, this reports the pack bytes that are written to the subtransport. It does not report the bytes sent on the wire that are received by the server. This should be a good estimate of progress (and an improvement over no progress).
nulltoken 191adce8 2013-08-27T20:00:28 vector: Teach git_vector_uniq() to free while deduplicating
Edward Thomson a1f69452 2013-08-08T12:36:11 git_strndup fix when OOM
Russell Belfer d730d3f4 2013-07-31T16:40:42 Major rename detection changes After doing further profiling, I found that a lot of time was being spent attempting to insert hashes into the file hash signature when using the rolling hash because the rolling hash approach generates a hash per byte of the file instead of one per run/line of data. To optimize this, I decided to convert back to a run-based file signature algorithm which would be more like core Git. After changing this, a number of the existing tests started to fail. In some cases, this appears to have been because the test was coded to be too specific to the particular results of the file similarity metric and in some cases there appear to have been bugs in the core rename detection code where only by the coincidence of the file similarity scoring were the expected results being generated. This renames all the variables in the core rename detection code to be more consistent and hopefully easier to follow which made it a bit easier to reason about the behavior of that code and fix the problems that I was seeing. I think it's in better shape now. There are a couple of tests now that attempt to stress test the rename detection code and they are quite slow. Most of the time is spent setting up the test data on disk and in the index. When we roll out performance improvements for index insertion, it should also speed up these tests I hope.
Russell Belfer 302a04b0 2013-06-29T12:41:39 Add accessors for refcount value
Edward Thomson e3b4a47c 2013-05-31T16:30:09 git__strcasesort_cmp: strcasecmp sorting rules but requires strict equality
yorah 3425fee6 2013-06-17T14:27:34 util: git__memzero() tweaks On Linux: fix a warning message related to the volatile qualifier (cast) On Windows: use SecureZeroMemory() On both, inline the call, so that no entry point can lead back to this "secure" memory zeroing.
Vicent Marti 6de9b2ee 2013-06-12T21:10:33 util: It's called `memzero`
Vicent Marti eb58e2d0 2013-06-12T21:05:48 Merge remote-tracking branch 'arrbee/minor-paranoia' into development
Russell Belfer 114f5a6c 2013-06-10T10:10:39 Reorganize diff and add basic diff driver This is a significant reorganization of the diff code to break it into a set of more clearly distinct files and to document the new organization. Hopefully this will make the diff code easier to understand and to extend. This adds a new `git_diff_driver` object that looks of diff driver information from the attributes and the config so that things like function content in diff headers can be provided. The full driver spec is not implemented in the commit - this is focused on the reorganization of the code and putting the driver hooks in place. This also removes a few #includes from src/repository.h that were overbroad, but as a result required extra #includes in a variety of places since including src/repository.h no longer results in pulling in the whole world.
Russell Belfer 3e9e6cda 2013-06-07T09:54:33 Add safe memset and use it This adds a `git__memset` routine that will not be optimized away and updates the places where I memset() right before a free() call to use it.
Russell Belfer d958e37a 2013-05-17T17:21:45 Fix issues with git_diff_find_similar There are a number of bugs in the rename code that only were obvious when I started testing it against large old repos with more complex patterns. (The code to do that testing is not ready to merge with libgit2, but I do plan to add more thorough tests.) This contains a significant number of changes and also tweaks the public API slightly to make emulating core git easier. Most notably, this separates the GIT_DIFF_FIND_AND_BREAK_REWRITES flag into FIND_REWRITES (which adds a self-similarity score to every modified file) and BREAK_REWRITES (which splits the modified deltas into add/remove pairs in the diff list). When you do a raw output of core git, rewrites show up as M090 or such, not at A and D output, so I wanted to be able to emulate that. Publicly, this also changes the flags to be uint16_t since we don't need values out of that range. Internally, this contains significant changes from a number of small bug fixes (like using the wrong side of the diff to decide if the object could be found in the ODB vs the workdir) to larger issues about which files can and should be compared and how the various edge cases of similarity scores should be treated. Honestly, I don't think this is the last update that will have to be made to this code, but I think this moves us closer to correct behavior and I tried to document the code so it would be easier to follow..
Linquize 0cb16fe9 2013-05-15T20:26:55 Unify whitespaces to tabs
Carlos Martín Nieto 05b17964 2013-04-21T19:26:35 Make refcounting atomic
Russell Belfer e976b56d 2013-04-15T14:27:53 Add git__compare_and_swap and use it This removes the lock from the repository object and changes the internals to use the new atomic git__compare_and_swap to update the _odb, _config, _index, and _refdb variables in a threadsafe manner.
Russell Belfer 53607868 2013-04-15T00:09:03 Further threading fixes This builds on the earlier thread safety work to make it so that setting the odb, index, refdb, or config for a repository is done in a threadsafe manner with minimized locking time. This is done by adding a lock to the repository object and using it to guard the assignment of the above listed pointers. The lock is only held to assign the pointer value. This also contains some minor fixes to the other work with pack files to reduce the time that locks are being held to and fix an apparently memory leak.
Russell Belfer 4dcd8780 2013-04-19T17:17:44 Move refdb_backend to include/git2/sys This moves most of the refdb stuff over to the include/git2/sys directory, with some minor shifts in function organization. While I was making the necessary updates, I also removed the trailing whitespace in a few files that I modified just because I was there and it was bugging me.
Russell Belfer 62beacd3 2013-03-11T16:43:58 Sorting function cleanup and MinGW fix Clean up some sorting function stuff including fixing qsort_r on MinGW, common function pointer type for comparison, and basic insertion sort implementation (which we, regrettably, fall back on for MinGW).
Russell Belfer e40f1c2d 2013-03-08T16:39:57 Make tree iterator handle icase equivalence There is a serious bug in the previous tree iterator implementation. If case insensitivity resulted in member elements being equivalent to one another, and those member elements were trees, then the children of the colliding elements would be processed in sequence instead of in a single flattened list. This meant that the tree iterator was not truly acting like a case-insensitive list. This completely reworks the tree iterator to manage lists with case insensitive equivalence classes and advance through the items in a unified manner in a single sorted frame. It is possible that at a future date we might want to update this to separate the case insensitive and case sensitive tree iterators so that the case sensitive one could be a minimal amount of code and the insensitive one would always know what it needed to do without checking flags. But there would be so much shared code between the two, that I'm not sure it that's a win. For now, this gets what we need. More tests are needed, though.
Vicent Marti 41051e3f 2013-02-20T17:09:51 signature: Shut up MSVC, you silly goose
Ben Straub 15760c59 2013-02-01T19:21:55 Use malloc rather than calloc
Ben Straub c4beee76 2013-02-01T10:00:55 Introduce git__substrdup
Philip Kelley 11d9f6b3 2013-01-27T14:17:07 Vector improvements and their fallout
Russell Belfer 851ad650 2013-01-09T16:00:16 Add payload "_r" versions of bsearch and tsort git__bsearch and git__tsort did not pass a payload through to the comparison function. This makes it impossible to implement sorted lists where the sort order depends on external data (e.g. building a secondary sort order for the entries in a tree). This commit adds git__bsearch_r and git__tsort_r versions that pass a third parameter to the cmp function of a user payload.
Edward Thomson 359fc2d2 2013-01-08T17:07:25 update copyrights
Edward Thomson 7fcec834 2012-12-11T22:31:21 fetchhead reading/iterating
Russell Belfer a277345e 2012-11-14T22:37:13 Create internal strcmp variants for function ptrs Using the builtin strcmp and strcasecmp as function pointers is problematic on win32. This adds internal implementations and divorces us from the platform linkage.
Russell Belfer 55cbd05b 2012-11-08T16:56:34 Some diff refactorings to help code reuse There are some diff functions that are useful in a rewritten checkout and this lays some groundwork for that. This contains three main things: 1. Share the function diff uses to calculate the OID for a file in the working directory (now named `git_diff__oid_for_file` 2. Add a `git_diff__paired_foreach` function to iterator over two diff lists concurrently. Convert status to use it. 3. Move all the string/prefix/index entry comparisons into function pointers inside the `git_diff_list` object so they can be switched between case sensitive and insensitive versions. This makes them easier to reuse in various functions without replicating logic. As part of this, move a couple of index functions out of diff.c and into index.c.
Philip Kelley 2364735c 2012-11-09T15:39:10 Fix implementation of strndup to not overrun
Philip Kelley ec40b7f9 2012-09-17T15:42:41 Support for core.ignorecase
yorah 02a0d651 2012-07-12T16:31:59 Add git_buf_unescape and git__unescape to unescape all characters in a string (in-place)
Vicent Martí 48bcf81d 2012-07-12T09:32:44 Merge pull request #812 from arrbee/assorted-tweaks Assorted goodies
Russell Belfer c3a875c9 2012-07-10T15:20:08 Adding unicode space to match crlf patterns Adding 0x85 to `git__isspace` since we also look for that in filter.c as a whitespace character.
nulltoken 98d6a1fd 2012-07-04T16:24:09 util: add git__isdigit()
nulltoken 494ae940 2012-07-02T17:51:02 revparse: fix parsing of date specifiers
Ben Straub 8a385c04 2012-06-06T12:25:22 Move git__date_parse declaration to util.h.
Ben Straub 56a5000d 2012-06-05T12:52:44 Merge branch 'development' into rev-parse Conflicts: src/util.h tests-clar/refs/branches/listall.c
Vicent Martí 29e948de 2012-05-10T10:38:10 global: Change parameter ordering in API Consistency is good.
Ben Straub 1ce4cc01 2012-05-15T15:41:05 Fix date.c build in msvc. Ported the win32 implementations of gmtime_r, localtime_r, and gettimeofday to be part of the posix compatibility layer, and fixed git_signature_now to use them.
Russell Belfer 41a82592 2012-05-15T14:17:39 Ranged iterators and rewritten git_status_file The goal of this work is to rewrite git_status_file to use the same underlying code as git_status_foreach. This is done in 3 phases: 1. Extend iterators to allow ranged iteration with start and end prefixes for the range of file names to be covered. 2. Improve diff so that when there is a pathspec and there is a common non-wildcard prefix of the pathspec, it will use ranged iterators to minimize excess iteration. 3. Rewrite git_status_file to call git_status_foreach_ext with a pathspec that covers just the one file being checked. Since ranged iterators underlie the status & diff implementation, this is actually fairly efficient. The workdir iterator does end up loading the contents of all the directories down to the single file, which should ideally be avoided, but it is pretty good.
Ben Straub a346992f 2012-05-10T09:47:14 Rev-parse: @{time} syntax. Ported date.c (for approxidate_careful) from git.git revision aa39b85. Trimmed out the parts we're not using.
nulltoken 9cd25d00 2012-05-09T13:21:21 util: Fix git__isspace() implementation The characters <space>, <form-feed>, <newline>, <carriage-return>, <tab>, and <vertical-tab> are part of the "space" definition. cf. http://www.kernel.org/doc/man-pages/online/pages/man5/locale.5.html
Vicent Martí 0f49200c 2012-05-09T04:37:02 msvc: Do not use `isspace` Locale-aware bullshit bitting my ass again yo
Vicent Martí 3fbcac89 2012-05-02T19:56:38 Remove old and unused error codes
Russell Belfer 25f258e7 2012-04-23T09:21:15 Moving power-of-two bit utilities into util.h
Vicent Martí dda708e7 2012-03-09T19:55:50 error-handling: On-disk config file backend Includes: - Proper error reporting when encountering syntax errors in a config file (file, line number, column). - Rewritten `config_write`, now with 99% less goto-spaghetti - Error state in `git_filebuf`: filebuf write functions no longer need to be checked for error returns. If any of the writes performed on a buffer fail, the last call to `git_filebuf_commit` or `git_filebuf_hash` will fail accordingly and set the appropiate error message. Baller!
Russell Belfer ae9e29fd 2012-03-06T16:14:31 Migrating diff to new error handling Ended up migrating a bunch of upstream functions as well including vector, attr_file, and odb in order to get this to work right.
Vicent Martí cb8a7961 2012-03-07T00:02:55 error-handling: Repository This also includes droping `git_buf_lasterror` because it makes no sense in the new system. Note that in most of the places were it has been dropped, the code needs cleanup. I.e. GIT_ENOMEM is going away, so instead it should return a generic `-1` and obviously not throw anything.
schu 905919e6 2012-02-14T20:44:22 util: add git__ishex git__ishex allows to check if a string is a hexadecimal representation. Signed-off-by: schu <schu-github@schulog.org>
schu 5e0de328 2012-02-13T17:10:24 Update Copyright header Signed-off-by: schu <schu-github@schulog.org>
Russell Belfer 83bfbdf5 2012-01-16T18:00:18 Remove poor git__removechar function Going back over this, the git__removechar function was not needed (only invoked once) and is actually mislabeled. As implemented, it really only made sense for removing backslash characters, since two of the "removed" characters in a row would include the second one -- i.e. it really implements stripping backslash-escaped strings where a backslash allows internal whitespace in a word.
Russell Belfer a51cd8e6 2012-01-16T16:58:27 Fix handling of relative paths for attrs Per issue #533, the handling of relative paths in attribute and ignore files was not right. Fixed this by pre-joining the relative path of the attribute/ignore file onto the match string when a full path match is required. Unfortunately, fixing this required a bit more code than I would have liked because I had to juggle things around so that the fnmatch parser would have sufficient information to prepend the relative path when it was needed.
Russell Belfer cfbc880d 2012-01-16T15:16:44 Patch cleanup for merge After reviewing the gitignore support with Vicent, we came up with a list of minor cleanups to prepare for merge, including: * checking git_repository_config error returns * renaming git_ignore_is_ignored and moving to status.h * fixing next_line skipping to include \r skips * commenting on where ignores are and are not included
Russell Belfer df743c7d 2012-01-09T15:37:19 Initial implementation of gitignore support Adds support for .gitignore files to git_status_foreach() and git_status_file(). This includes refactoring the gitattributes code to share logic where possible. The GIT_STATUS_IGNORED flag will now be passed in for files that are ignored (provided they are not already in the index or the head of repo).
Vicent Martí f2114d0a 2012-01-04T22:40:59 Merge remote-tracking branch 'nulltoken/topix/path_fromurl' into development Conflicts: tests-clay/clay.h tests-clay/clay_main.c
Russell Belfer bd370b14 2011-12-30T15:00:14 Improved gitattributes macro implementation This updates to implementation of gitattribute macros to be much more similar to core git (albeit not 100%) and to handle expansion of macros within macros, etc. It also cleans up the refcounting usage with macros to be much cleaner. Also, this adds a new vector function `git_vector_insert_sorted()` which allows you to maintain a sorted list as you go. In order to write that function, this changes the function `git__bsearch()` to take a somewhat different set of parameters, although the core functionality is still the same.
Russell Belfer 73b51450 2011-12-28T23:28:50 Add support for macros and cache flush API. Add support for git attribute macro definitions. Also, add support for cache flush API to clear the attribute file content cache when needed. Additionally, improved the handling of global and system files, making common utility functions in fileops and converting config and attr to both use the common functions. Adds a bunch more tests and fixed some memory leaks. Note that adding macros required me to use refcounted attribute assignment definitions, which complicated, but probably improved memory usage.
nulltoken eb8de747 2011-12-28T20:24:58 util: add git__fromhex()
Russell Belfer ee1f0b1a 2011-12-16T10:56:43 Add APIs for git attributes This adds APIs for querying git attributes. In addition to the new API in include/git2/attr.h, most of the action is in src/attr_file.[hc] which contains utilities for dealing with a single attributes file, and src/attr.[hc] which contains the implementation of the APIs that merge all applicable attributes files.
Vicent Marti b028a898 2011-11-26T08:31:57 util: Remove unused macro
Vicent Marti 03da4480 2011-11-26T08:31:15 refcount: Fix off-by one error
Vicent Marti 9462c471 2011-11-25T08:16:26 repository: Change ownership semantics The ownership semantics have been changed all over the library to be consistent. There are no more "borrowed" or duplicated references. Main changes: - `git_repository_open2` and `3` have been dropped. - Added setters and getters to hotswap all the repository owned objects: `git_repository_index` `git_repository_set_index` `git_repository_odb` `git_repository_set_odb` `git_repository_config` `git_repository_set_config` `git_repository_workdir` `git_repository_set_workdir` Now working directories/index files/ODBs and so on can be hot-swapped after creating a repository and between operations. - All these objects now have proper ownership semantics with refcounting: they all require freeing after they are no longer needed (the repository always keeps its internal reference). - Repository open and initialization has been updated to keep in mind the configuration files. Bare repositories are now always detected, and a default config file is created on init. - All the tests affected by these changes have been dropped from the old test suite and ported to the new one.
Vicent Marti 3286c408 2011-10-28T14:51:13 global: Properly use `git__` memory wrappers Ensure that all memory related functions (malloc, calloc, strdup, free, etc) are using their respective `git__` wrappers.
Vicent Marti fafd4710 2011-09-30T16:08:06 config: Proper type declarations for 64 bit ints
nulltoken ad196c6a 2011-09-21T23:17:39 config: make git_config_[get|set]_long() able to properly deal with 8 bytes wide values Should fix issue #419. Signed-off-by: nulltoken <emeric.fermas@gmail.com>
Vicent Marti 87d9869f 2011-09-19T03:34:49 Tabify everything There were quite a few places were spaces were being used instead of tabs. Try to catch them all. This should hopefully not break anything. Except for `git blame`. Oh well.
Vicent Marti bb742ede 2011-09-19T01:54:32 Cleanup legal data 1. The license header is technically not valid if it doesn't have a copyright signature. 2. The COPYING file has been updated with the different licenses used in the project. 3. The full GPLv2 header in each file annoys me.
Sebastian Schuberth 26e74c6a 2011-09-08T14:21:17 Fix some random size_t vs. int conversion warnings
Kirill A. Shutemov 932669b8 2011-08-25T14:22:57 Drop STRLEN() macros There is no need in STRLEN macros. Compilers can do this trivial optimization on its own. Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
Vicent Marti 84dd3820 2011-08-18T02:13:51 posix: Properly handle `snprintf` in all platforms
schu 31e59092 2011-08-17T15:20:43 git__strndup: immediately return NULL when ENOMEM Signed-off-by: schu <schu-github@schulog.org>
nulltoken d1f34693 2011-08-09T12:07:47 util: Add git__strcmp_cb() wrapper We don't want direct pointers to the CRT on Windows, we may get stdcall conflicts.
Vicent Marti 06c43821 2011-07-09T02:37:16 Remove unused methods The direct-writes commit left some (slow) internals methods that were no longer needed. These have been removed. Also, the Reflog code was using the old `git_signature__write`, so it has been rewritten to use a normal buffer and the new `writebuf` signature writer. It's now slightly simpler and faster.
nulltoken bdcc4611 2011-07-07T10:11:00 Fix MSVC compilation warnings
Vicent Marti de18f276 2011-07-07T01:46:20 vector: Timsort all of the things Drop the GLibc implementation of Merge Sort and replace it with Timsort. The algorithm has been tuned to work on arrays of pointers (void **), so there's no longer a need to abstract the byte-width of each element in the array. All the comparison callbacks now take pointers-to-elements, not pointers-to-pointers, so there's now one less level of dereferencing. E.g. int index_cmp(const void *a, const void *b) { - const git_index_entry *entry_a = *(const git_index_entry **)(a); + const git_index_entry *entry_a = (const git_index_entry *)(a); The result is up to a 40% speed-up when sorting vectors. Memory usage remains lineal. A new `bsearch` implementation has been added, whose callback also supplies pointer-to-elements, to uniform the Vector API again.
Kirill A. Shutemov c20ffa61 2011-07-01T00:34:23 util: introduce merge sort routine In some cases it's important to preserve order of elements with equal keys (stable sort). qsort(3) doesn't define order of elements with equal keys. git__msort() implements merge sort which is stable sort. Implementation taken from git. Function renamed git_qsort() -> git__msort(). Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
Vicent Martí f12aa9dc 2011-07-05T04:31:37 Merge pull request #300 from carlosmn/gsoc2011/master A bit of networking