• R/O
  • SSH
  • HTTPS

yash: 提交


Commit MetaInfo

修訂4078 (tree)
時間2020-09-20 21:50:30
作者magicant

Log Message

wglob: Remove duplicates in linear time complexity

The previous algorithm had square time complexity

Change Summary

差異

--- yash/trunk/path.c (revision 4077)
+++ yash/trunk/path.c (revision 4078)
@@ -620,6 +620,8 @@
620620 __attribute__((nonnull(1)));
621621 static int wglob_sortcmp(const void *v1, const void *v2)
622622 __attribute__((pure,nonnull));
623+static size_t remove_dups(void **array)
624+ __attribute__((pure,nonnull));
623625
624626 /* A wide string version of `glob'.
625627 * Adds all pathnames that matches the specified pattern to the specified list.
@@ -666,12 +668,7 @@
666668 wglob_sortcmp);
667669
668670 /* 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);
675672 }
676673 }
677674 return !is_interrupted();
@@ -961,7 +958,26 @@
961958 return wcscoll(*(const wchar_t *const *) v1, *(const wchar_t *const *) v2);
962959 }
963960
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;
964968
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+
965981 /********** Built-ins **********/
966982
967983 static wchar_t *canonicalize_path(const wchar_t *path)
Show on old repository browser