INSTALL_MASK: index patterns anchored with leading slash (bug 675826)

For scalability, use a tree structure to index patterns that are
anchored with a leading slash.

Patterns anchored with leading slash are indexed by leading non-glob
components, making it possible to minimize the number of fnmatch
calls. For example:

  /foo*/bar -> {'.': ['/foo*/bar']}

  /foo/bar* -> {'foo': {'.': ['/foo/bar*']}}

  /foo/bar/ -> {'foo': {'bar': {'.': ['/foo/bar/']}}}

Signed-off-by: Zac Medico <>
(cherry picked from commit eb2674c1c2d84b2c9e9923e1c1666cb7a596c36c)

TEST=ran `build_image --board=betty base test`

Change-Id: Icf0ec621a3f68b2502d03d932bf7077d7ffd7464
Tested-by: Will Bradley <>
Commit-Ready: Mike Frysinger <>
Legacy-Commit-Queue: Commit Bot <>
Reviewed-by: Chris McDonald <>
Reviewed-by: Mike Frysinger <>
Reviewed-by: Allen Webb <>
Reviewed-by: Alex Klein <>
2 files changed