[v2,05/10] cache-tree: implement cache_tree_find_path()

Commit Message

Derrick Stolee May 19, 2022, 5:52 p.m. UTC

From: Derrick Stolee <[e-mail]>

Given a 'struct cache_tree', it may be beneficial to navigate directly
to a node within that corresponds to a given path name. Create
cache_tree_find_path() for this function. It returns NULL when no such
path exists.

The implementation is adapted from do_invalidate_path() which does a
similar search but also modifies the nodes it finds along the way.

This new method is not currently used, but will be in an upcoming
change.

Signed-off-by: Derrick Stolee <[e-mail]>
---
 cache-tree.c | 24 ++++++++++++++++++++++++
 cache-tree.h |  2 ++
 2 files changed, 26 insertions(+)

Comments

Junio C Hamano May 19, 2022, 8:14 p.m. UTC | #1

"Derrick Stolee via GitGitGadget" <[e-mail]> writes:

> +struct cache_tree *cache_tree_find_path(struct cache_tree *it, const char *path)
> +{
> +	const char *slash;
> +	int namelen;
> +	struct cache_tree_sub *down;
> +
> +	if (!it)
> +		return NULL;
> +	slash = strchrnul(path, '/');
> +	namelen = slash - path;
> +	it->entry_count = -1;
> +	if (!*slash) {
> +		int pos;
> +		pos = cache_tree_subtree_pos(it, path, namelen);
> +		if (0 <= pos)
> +			return it->down[pos]->cache_tree;
> +		return NULL;
> +	}
> +	down = find_subtree(it, path, namelen, 0);
> +	if (down)
> +		return cache_tree_find_path(down->cache_tree, slash + 1);
> +	return NULL;
> +}

The tail recursion (and the one in the orginal) may want to be
trivially converted to iteration with "goto".

It is somewhat surprising that we didn't have any external interface
to expose a sub-part of the cache_tree at all so far.  It may be
because the API was so well designed that the abstraction did not
have to be exposed.  I dunno.

> diff --git a/cache-tree.h b/cache-tree.h
> index 8efeccebfc9..f75f8e74dcd 100644
> --- a/cache-tree.h
> +++ b/cache-tree.h
> @@ -29,6 +29,8 @@ struct cache_tree_sub *cache_tree_sub(struct cache_tree *, const char *);
>  
>  int cache_tree_subtree_pos(struct cache_tree *it, const char *path, int pathlen);
>  
> +struct cache_tree *cache_tree_find_path(struct cache_tree *it, const char *path);
> +
>  void cache_tree_write(struct strbuf *, struct cache_tree *root);
>  struct cache_tree *cache_tree_read(const char *buffer, unsigned long size);

Derrick Stolee May 20, 2022, 6:13 p.m. UTC | #2

On 5/19/2022 4:14 PM, Junio C Hamano wrote:
> "Derrick Stolee via GitGitGadget" <[e-mail]> writes:
> 
>> +struct cache_tree *cache_tree_find_path(struct cache_tree *it, const char *path)
>> +{
>> +	const char *slash;
>> +	int namelen;
>> +	struct cache_tree_sub *down;
>> +
>> +	if (!it)
>> +		return NULL;
>> +	slash = strchrnul(path, '/');
>> +	namelen = slash - path;
>> +	it->entry_count = -1;
>> +	if (!*slash) {
>> +		int pos;
>> +		pos = cache_tree_subtree_pos(it, path, namelen);
>> +		if (0 <= pos)
>> +			return it->down[pos]->cache_tree;
>> +		return NULL;
>> +	}
>> +	down = find_subtree(it, path, namelen, 0);
>> +	if (down)
>> +		return cache_tree_find_path(down->cache_tree, slash + 1);
>> +	return NULL;
>> +}
> 
> The tail recursion (and the one in the orginal) may want to be
> trivially converted to iteration with "goto".

Good idea!
 
> It is somewhat surprising that we didn't have any external interface
> to expose a sub-part of the cache_tree at all so far.  It may be
> because the API was so well designed that the abstraction did not
> have to be exposed.  I dunno.

I think the abstraction definitely fit the shape of its consumers
pretty perfectly. I wonder if having a method like this will make
us think of new ways to use the cache tree for other things.

Thanks,
-Stolee

Patch

diff --git a/cache-tree.c b/cache-tree.c
index 6752f69d515..23893a7b113 100644
--- a/cache-tree.c
+++ b/cache-tree.c
@@ -100,6 +100,30 @@  struct cache_tree_sub *cache_tree_sub(struct cache_tree *it, const char *path)
 	return find_subtree(it, path, pathlen, 1);
 }
 
+struct cache_tree *cache_tree_find_path(struct cache_tree *it, const char *path)
+{
+	const char *slash;
+	int namelen;
+	struct cache_tree_sub *down;
+
+	if (!it)
+		return NULL;
+	slash = strchrnul(path, '/');
+	namelen = slash - path;
+	it->entry_count = -1;
+	if (!*slash) {
+		int pos;
+		pos = cache_tree_subtree_pos(it, path, namelen);
+		if (0 <= pos)
+			return it->down[pos]->cache_tree;
+		return NULL;
+	}
+	down = find_subtree(it, path, namelen, 0);
+	if (down)
+		return cache_tree_find_path(down->cache_tree, slash + 1);
+	return NULL;
+}
+
 static int do_invalidate_path(struct cache_tree *it, const char *path)
 {
 	/* a/b/c
diff --git a/cache-tree.h b/cache-tree.h
index 8efeccebfc9..f75f8e74dcd 100644
--- a/cache-tree.h
+++ b/cache-tree.h
@@ -29,6 +29,8 @@  struct cache_tree_sub *cache_tree_sub(struct cache_tree *, const char *);
 
 int cache_tree_subtree_pos(struct cache_tree *it, const char *path, int pathlen);
 
+struct cache_tree *cache_tree_find_path(struct cache_tree *it, const char *path);
+
 void cache_tree_write(struct strbuf *, struct cache_tree *root);
 struct cache_tree *cache_tree_read(const char *buffer, unsigned long size);