Google Git
Sign in
googlers / jrn / git / 4e09cf2acf00c63848c365479c61d80af62eceba
commit4e09cf2acf00c63848c365479c61d80af62eceba[log] [tgz]
authorDavid Turner <dturner@twopensource.com>Mon Aug 31 22:13:10 2015 -0400
committerJunio C Hamano <gitster@pobox.com>Tue Sep 01 10:37:38 2015 -0700
tree814365371ed1ed3a1d019e31b5d4db7e77973ba5
parent0701530c2663f82ff4b678de27db4c61f8b3092f [diff]
path: optimize common dir checking

Instead of a linear search over common_list to check whether
a path is common, use a trie.  The trie search operates on
path prefixes, and handles excludes.

Signed-off-by: David Turner <dturner@twopensource.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
2 files changed
tree: 814365371ed1ed3a1d019e31b5d4db7e77973ba5
  1. block-sha1/
  2. builtin/
  3. compat/
  4. contrib/
  5. Documentation/
  6. ewah/
  7. git-gui/
  8. gitk-git/
  9. gitweb/
  10. mergetools/
  11. perl/
  12. po/
  13. ppc/
  14. t/
  15. templates/
  16. vcs-svn/
  17. xdiff/
  18. RelNotes ⇨ Documentation/RelNotes/2.6.0.txt
  19. .gitattributes
  20. .gitignore
  21. .mailmap
  22. abspath.c
  23. aclocal.m4
  24. advice.c
  25. advice.h
  26. alias.c
  27. alloc.c
  28. archive-tar.c
  29. archive-zip.c
  30. archive.c
  31. archive.h
  32. argv-array.c
  33. argv-array.h
  34. attr.c
  35. attr.h
  36. base85.c
  37. bisect.c
  38. bisect.h
  39. blob.c
  40. blob.h
  41. branch.c
  42. branch.h
  43. builtin.h
  44. bulk-checkin.c
  45. bulk-checkin.h
  46. bundle.c
  47. bundle.h
  48. cache-tree.c
  49. cache-tree.h
  50. cache.h
  51. check-builtins.sh
  52. check-racy.c
  53. check_bindir
  54. color.c
  55. color.h
  56. column.c
  57. column.h
  58. combine-diff.c
  59. command-list.txt
  60. commit-slab.h
  61. commit.c
  62. commit.h
  63. config.c
  64. config.mak.in
  65. config.mak.uname
  66. configure.ac
  67. connect.c
  68. connect.h
  69. connected.c
  70. connected.h
  71. convert.c
  72. convert.h
  73. copy.c
  74. COPYING
  75. credential-cache--daemon.c
  76. credential-cache.c
  77. credential-store.c
  78. credential.c
  79. credential.h
  80. csum-file.c
  81. csum-file.h
  82. ctype.c
  83. daemon.c
  84. date.c
  85. decorate.c
  86. decorate.h
  87. delta.h
  88. diff-delta.c
  89. diff-lib.c
  90. diff-no-index.c
  91. diff.c
  92. diff.h
  93. diffcore-break.c
  94. diffcore-delta.c
  95. diffcore-order.c
  96. diffcore-pickaxe.c
  97. diffcore-rename.c
  98. diffcore.h
  99. dir.c
  100. dir.h
  101. editor.c
  102. entry.c
  103. environment.c
  104. exec_cmd.c
  105. exec_cmd.h
  106. fast-import.c
  107. fetch-pack.c
  108. fetch-pack.h
  109. fmt-merge-msg.h
  110. fsck.c
  111. fsck.h
  112. generate-cmdlist.perl
  113. gettext.c
  114. gettext.h
  115. git-add--interactive.perl
  116. git-archimport.perl
  117. git-bisect.sh
  118. git-compat-util.h
  119. git-cvsexportcommit.perl
  120. git-cvsimport.perl
  121. git-cvsserver.perl
  122. git-difftool--helper.sh
  123. git-difftool.perl
  124. git-filter-branch.sh
  125. git-instaweb.sh
  126. git-merge-octopus.sh
  127. git-merge-one-file.sh
  128. git-merge-resolve.sh
  129. git-mergetool--lib.sh
  130. git-mergetool.sh
  131. git-p4.py
  132. git-parse-remote.sh
  133. git-quiltimport.sh
  134. git-rebase--am.sh
  135. git-rebase--interactive.sh
  136. git-rebase--merge.sh
  137. git-rebase.sh
  138. git-relink.perl
  139. git-remote-testgit.sh
  140. git-request-pull.sh
  141. git-send-email.perl
  142. git-sh-i18n.sh
  143. git-sh-setup.sh
  144. git-stash.sh
  145. git-submodule.sh
  146. git-svn.perl
  147. GIT-VERSION-GEN
  148. git-web--browse.sh
  149. git.c
  150. git.rc
  151. git.spec.in
  152. gpg-interface.c
  153. gpg-interface.h
  154. graph.c
  155. graph.h
  156. grep.c
  157. grep.h
  158. hashmap.c
  159. hashmap.h
  160. help.c
  161. help.h
  162. hex.c
  163. http-backend.c
  164. http-fetch.c
  165. http-push.c
  166. http-walker.c
  167. http.c
  168. http.h
  169. ident.c
  170. imap-send.c
  171. INSTALL
  172. khash.h
  173. kwset.c
  174. kwset.h
  175. levenshtein.c
  176. levenshtein.h
  177. LGPL-2.1
  178. line-log.c
  179. line-log.h
  180. line-range.c
  181. line-range.h
  182. list-objects.c
  183. list-objects.h
  184. ll-merge.c
  185. ll-merge.h
  186. lockfile.c
  187. lockfile.h
  188. log-tree.c
  189. log-tree.h
  190. mailmap.c
  191. mailmap.h
  192. Makefile
  193. match-trees.c
  194. merge-blobs.c
  195. merge-blobs.h
  196. merge-recursive.c
  197. merge-recursive.h
  198. merge.c
  199. mergesort.c
  200. mergesort.h
  201. name-hash.c
  202. notes-cache.c
  203. notes-cache.h
  204. notes-merge.c
  205. notes-merge.h
  206. notes-utils.c
  207. notes-utils.h
  208. notes.c
  209. notes.h
  210. object.c
  211. object.h
  212. pack-bitmap-write.c
  213. pack-bitmap.c
  214. pack-bitmap.h
  215. pack-check.c
  216. pack-objects.c
  217. pack-objects.h
  218. pack-revindex.c
  219. pack-revindex.h
  220. pack-write.c
  221. pack.h
  222. pager.c
  223. parse-options-cb.c
  224. parse-options.c
  225. parse-options.h
  226. patch-delta.c
  227. patch-ids.c
  228. patch-ids.h
  229. path.c
  230. pathspec.c
  231. pathspec.h
  232. pkt-line.c
  233. pkt-line.h
  234. preload-index.c
  235. pretty.c
  236. prio-queue.c
  237. prio-queue.h
  238. progress.c
  239. progress.h
  240. prompt.c
  241. prompt.h
  242. quote.c
  243. quote.h
  244. reachable.c
  245. reachable.h
  246. read-cache.c
  247. README
  248. ref-filter.c
  249. ref-filter.h
  250. reflog-walk.c
  251. reflog-walk.h
  252. refs.c
  253. refs.h
  254. remote-curl.c
  255. remote-testsvn.c
  256. remote.c
  257. remote.h
  258. replace_object.c
  259. rerere.c
  260. rerere.h
  261. resolve-undo.c
  262. resolve-undo.h
  263. revision.c
  264. revision.h
  265. run-command.c
  266. run-command.h
  267. send-pack.c
  268. send-pack.h
  269. sequencer.c
  270. sequencer.h
  271. server-info.c
  272. setup.c
  273. sh-i18n--envsubst.c
  274. sha1-array.c
  275. sha1-array.h
  276. sha1-lookup.c
  277. sha1-lookup.h
  278. sha1_file.c
  279. sha1_name.c
  280. shallow.c
  281. shell.c
  282. shortlog.h
  283. show-index.c
  284. sideband.c
  285. sideband.h
  286. sigchain.c
  287. sigchain.h
  288. split-index.c
  289. split-index.h
  290. strbuf.c
  291. strbuf.h
  292. streaming.c
  293. streaming.h
  294. string-list.c
  295. string-list.h
  296. submodule.c
  297. submodule.h
  298. symlinks.c
  299. tag.c
  300. tag.h
  301. tar.h
  302. tempfile.c
  303. tempfile.h
  304. test-chmtime.c
  305. test-config.c
  306. test-ctype.c
  307. test-date.c
  308. test-delta.c
  309. test-dump-cache-tree.c
  310. test-dump-split-index.c
  311. test-dump-untracked-cache.c
  312. test-genrandom.c
  313. test-hashmap.c
  314. test-index-version.c
  315. test-line-buffer.c
  316. test-match-trees.c
  317. test-mergesort.c
  318. test-mktemp.c
  319. test-parse-options.c
  320. test-path-utils.c
  321. test-prio-queue.c
  322. test-read-cache.c
  323. test-regex.c
  324. test-revision-walking.c
  325. test-run-command.c
  326. test-scrap-cache-tree.c
  327. test-sha1-array.c
  328. test-sha1.c
  329. test-sha1.sh
  330. test-sigchain.c
  331. test-string-list.c
  332. test-subprocess.c
  333. test-svn-fe.c
  334. test-urlmatch-normalization.c
  335. test-wildmatch.c
  336. thread-utils.c
  337. thread-utils.h
  338. trace.c
  339. trace.h
  340. trailer.c
  341. trailer.h
  342. transport-helper.c
  343. transport.c
  344. transport.h
  345. tree-diff.c
  346. tree-walk.c
  347. tree-walk.h
  348. tree.c
  349. tree.h
  350. unicode_width.h
  351. unimplemented.sh
  352. unix-socket.c
  353. unix-socket.h
  354. unpack-trees.c
  355. unpack-trees.h
  356. update_unicode.sh
  357. upload-pack.c
  358. url.c
  359. url.h
  360. urlmatch.c
  361. urlmatch.h
  362. usage.c
  363. userdiff.c
  364. userdiff.h
  365. utf8.c
  366. utf8.h
  367. varint.c
  368. varint.h
  369. version.c
  370. version.h
  371. versioncmp.c
  372. walker.c
  373. walker.h
  374. wildmatch.c
  375. wildmatch.h
  376. wrap-for-bin.sh
  377. wrapper.c
  378. write_or_die.c
  379. ws.c
  380. wt-status.c
  381. wt-status.h
  382. xdiff-interface.c
  383. xdiff-interface.h
  384. zlib.c