wglob: Remove duplicates in linear time complexity
The previous algorithm had square time complexity
@@ -620,6 +620,8 @@ | ||
620 | 620 | __attribute__((nonnull(1))); |
621 | 621 | static int wglob_sortcmp(const void *v1, const void *v2) |
622 | 622 | __attribute__((pure,nonnull)); |
623 | +static size_t remove_dups(void **array) | |
624 | + __attribute__((pure,nonnull)); | |
623 | 625 | |
624 | 626 | /* A wide string version of `glob'. |
625 | 627 | * Adds all pathnames that matches the specified pattern to the specified list. |
@@ -666,12 +668,7 @@ | ||
666 | 668 | wglob_sortcmp); |
667 | 669 | |
668 | 670 | /* remove duplicates */ |
669 | - for (size_t i = list->length; --i > listbase; ) { | |
670 | - if (wcscmp(list->contents[i], list->contents[i-1]) == 0) { | |
671 | - free(list->contents[i]); | |
672 | - pl_remove(list, i, 1); | |
673 | - } | |
674 | - } | |
671 | + list->length -= remove_dups(list->contents + listbase); | |
675 | 672 | } |
676 | 673 | } |
677 | 674 | return !is_interrupted(); |
@@ -961,7 +958,26 @@ | ||
961 | 958 | return wcscoll(*(const wchar_t *const *) v1, *(const wchar_t *const *) v2); |
962 | 959 | } |
963 | 960 | |
961 | +/* Given a NULL-terminated array of pointers to wide strings, removes its | |
962 | + * elements so that no adjacent elements compare equal. The removed elements are | |
963 | + * freed in this function. Returns the number of removed elements. */ | |
964 | +size_t remove_dups(void **array) | |
965 | +{ | |
966 | + if (array[0] == NULL) | |
967 | + return 0; | |
964 | 968 | |
969 | + size_t in = 1, out = 0; | |
970 | + for (; array[in] != NULL; in++) { | |
971 | + if (wcscmp(array[in], array[out]) == 0) | |
972 | + free(array[in]); | |
973 | + else | |
974 | + array[++out] = array[in]; | |
975 | + } | |
976 | + array[++out] = NULL; | |
977 | + return in - out; | |
978 | +} | |
979 | + | |
980 | + | |
965 | 981 | /********** Built-ins **********/ |
966 | 982 | |
967 | 983 | static wchar_t *canonicalize_path(const wchar_t *path) |