From: Linus Torvalds <torvalds@linux-foundation.org>
To: undisclosed-recipients:;
Subject: [PATCH 2/5] Make 'traverse_tree()' use linked structure rather than 'const char *base'
Date: Wed, 5 Mar 2008 18:59:29 -0800 [thread overview]
Message-ID: <71685f79add8cb0982d74745cf3277fc2287c306.1204777699.git.torvalds@linux-foundation.org> (raw)
In-Reply-To: <cover.1204777699.git.torvalds@linux-foundation.org>
This makes the calling convention a bit less obvious, but a lot more
flexible. Instead of allocating and extending a new 'base' string, we
just link the top-most name into a linked list of the 'info' structure
when traversing a subdirectory, and we can generate the basename by
following the list.
Perhaps even more importantly, the linked list of info structures also
gives us a place to naturally save off other information than just the
directory name.
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
merge-tree.c | 51 +++++++++++++++++++++++++++------------------------
tree-walk.c | 35 +++++++++++++++++++++++++++++++++--
tree-walk.h | 20 ++++++++++++++++++--
3 files changed, 78 insertions(+), 28 deletions(-)
diff --git a/merge-tree.c b/merge-tree.c
index e083246..a3511b7 100644
--- a/merge-tree.c
+++ b/merge-tree.c
@@ -168,7 +168,13 @@ static struct merge_list *create_entry(unsigned stage, unsigned mode, const unsi
return res;
}
-static void resolve(const char *base, struct name_entry *branch1, struct name_entry *result)
+static char *traverse_path(const struct traverse_info *info, const struct name_entry *n)
+{
+ char *path = xmalloc(traverse_path_len(info, n) + 1);
+ return make_traverse_path(path, info, n);
+}
+
+static void resolve(const struct traverse_info *info, struct name_entry *branch1, struct name_entry *result)
{
struct merge_list *orig, *final;
const char *path;
@@ -177,7 +183,7 @@ static void resolve(const char *base, struct name_entry *branch1, struct name_en
if (!branch1)
return;
- path = xstrdup(mkpath("%s%s", base, result->path));
+ path = traverse_path(info, result);
orig = create_entry(2, branch1->mode, branch1->sha1, path);
final = create_entry(0, result->mode, result->sha1, path);
@@ -186,9 +192,8 @@ static void resolve(const char *base, struct name_entry *branch1, struct name_en
add_merge_entry(final);
}
-static int unresolved_directory(const char *base, struct name_entry n[3])
+static int unresolved_directory(const struct traverse_info *info, struct name_entry n[3])
{
- int baselen, pathlen;
char *newbase;
struct name_entry *p;
struct tree_desc t[3];
@@ -204,13 +209,7 @@ static int unresolved_directory(const char *base, struct name_entry n[3])
}
if (!S_ISDIR(p->mode))
return 0;
- baselen = strlen(base);
- pathlen = tree_entry_len(p->path, p->sha1);
- newbase = xmalloc(baselen + pathlen + 2);
- memcpy(newbase, base, baselen);
- memcpy(newbase + baselen, p->path, pathlen);
- memcpy(newbase + baselen + pathlen, "/", 2);
-
+ newbase = traverse_path(info, p);
buf0 = fill_tree_descriptor(t+0, n[0].sha1);
buf1 = fill_tree_descriptor(t+1, n[1].sha1);
buf2 = fill_tree_descriptor(t+2, n[2].sha1);
@@ -224,7 +223,7 @@ static int unresolved_directory(const char *base, struct name_entry n[3])
}
-static struct merge_list *link_entry(unsigned stage, const char *base, struct name_entry *n, struct merge_list *entry)
+static struct merge_list *link_entry(unsigned stage, const struct traverse_info *info, struct name_entry *n, struct merge_list *entry)
{
const char *path;
struct merge_list *link;
@@ -234,17 +233,17 @@ static struct merge_list *link_entry(unsigned stage, const char *base, struct na
if (entry)
path = entry->path;
else
- path = xstrdup(mkpath("%s%s", base, n->path));
+ path = traverse_path(info, n);
link = create_entry(stage, n->mode, n->sha1, path);
link->link = entry;
return link;
}
-static void unresolved(const char *base, struct name_entry n[3])
+static void unresolved(const struct traverse_info *info, struct name_entry n[3])
{
struct merge_list *entry = NULL;
- if (unresolved_directory(base, n))
+ if (unresolved_directory(info, n))
return;
/*
@@ -252,9 +251,9 @@ static void unresolved(const char *base, struct name_entry n[3])
* list has the stages in order - link_entry adds new
* links at the front.
*/
- entry = link_entry(3, base, n + 2, entry);
- entry = link_entry(2, base, n + 1, entry);
- entry = link_entry(1, base, n + 0, entry);
+ entry = link_entry(3, info, n + 2, entry);
+ entry = link_entry(2, info, n + 1, entry);
+ entry = link_entry(1, info, n + 0, entry);
add_merge_entry(entry);
}
@@ -288,36 +287,40 @@ static void unresolved(const char *base, struct name_entry n[3])
* The successful merge rules are the same as for the three-way merge
* in git-read-tree.
*/
-static void threeway_callback(int n, unsigned long mask, struct name_entry *entry, const char *base)
+static void threeway_callback(int n, unsigned long mask, struct name_entry *entry, struct traverse_info *info)
{
/* Same in both? */
if (same_entry(entry+1, entry+2)) {
if (entry[0].sha1) {
- resolve(base, NULL, entry+1);
+ resolve(info, NULL, entry+1);
return;
}
}
if (same_entry(entry+0, entry+1)) {
if (entry[2].sha1 && !S_ISDIR(entry[2].mode)) {
- resolve(base, entry+1, entry+2);
+ resolve(info, entry+1, entry+2);
return;
}
}
if (same_entry(entry+0, entry+2)) {
if (entry[1].sha1 && !S_ISDIR(entry[1].mode)) {
- resolve(base, NULL, entry+1);
+ resolve(info, NULL, entry+1);
return;
}
}
- unresolved(base, entry);
+ unresolved(info, entry);
}
static void merge_trees(struct tree_desc t[3], const char *base)
{
- traverse_trees(3, t, base, threeway_callback);
+ struct traverse_info info;
+
+ setup_traverse_info(&info, base);
+ info.fn = threeway_callback;
+ traverse_trees(3, t, &info);
}
static void *get_tree_descriptor(struct tree_desc *desc, const char *rev)
diff --git a/tree-walk.c b/tree-walk.c
index 142205d..f9f7d22 100644
--- a/tree-walk.c
+++ b/tree-walk.c
@@ -104,7 +104,38 @@ int tree_entry(struct tree_desc *desc, struct name_entry *entry)
return 1;
}
-void traverse_trees(int n, struct tree_desc *t, const char *base, traverse_callback_t callback)
+void setup_traverse_info(struct traverse_info *info, const char *base)
+{
+ int pathlen = strlen(base);
+
+ memset(info, 0, sizeof(*info));
+ if (pathlen && base[pathlen-1] == '/')
+ pathlen--;
+ info->pathlen = pathlen ? pathlen + 1 : 0;
+ info->name.path = base;
+ info->name.sha1 = (void *)(base + pathlen + 1);
+}
+
+char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n)
+{
+ int len = tree_entry_len(n->path, n->sha1);
+ int pathlen = info->pathlen;
+
+ path[pathlen + len] = 0;
+ for (;;) {
+ memcpy(path + pathlen, n->path, len);
+ if (!pathlen)
+ break;
+ path[--pathlen] = '/';
+ n = &info->name;
+ len = tree_entry_len(n->path, n->sha1);
+ info = info->prev;
+ pathlen -= len;
+ }
+ return path;
+}
+
+void traverse_trees(int n, struct tree_desc *t, struct traverse_info *info)
{
struct name_entry *entry = xmalloc(n*sizeof(*entry));
@@ -150,7 +181,7 @@ void traverse_trees(int n, struct tree_desc *t, const char *base, traverse_callb
}
entry_clear(entry + i);
}
- callback(n, mask, entry, base);
+ info->fn(n, mask, entry, info);
}
free(entry);
}
diff --git a/tree-walk.h b/tree-walk.h
index db0fbdc..7c4ae64 100644
--- a/tree-walk.h
+++ b/tree-walk.h
@@ -33,10 +33,26 @@ int tree_entry(struct tree_desc *, struct name_entry *);
void *fill_tree_descriptor(struct tree_desc *desc, const unsigned char *sha1);
-typedef void (*traverse_callback_t)(int n, unsigned long mask, struct name_entry *entry, const char *base);
+struct traverse_info;
+typedef void (*traverse_callback_t)(int n, unsigned long mask, struct name_entry *entry, struct traverse_info *);
+void traverse_trees(int n, struct tree_desc *t, struct traverse_info *info);
-void traverse_trees(int n, struct tree_desc *t, const char *base, traverse_callback_t callback);
+struct traverse_info {
+ struct traverse_info *prev;
+ struct name_entry name;
+ int pathlen;
+
+ traverse_callback_t fn;
+ void *data;
+};
int get_tree_entry(const unsigned char *, const char *, unsigned char *, unsigned *);
+extern char *make_traverse_path(char *path, const struct traverse_info *info, const struct name_entry *n);
+extern void setup_traverse_info(struct traverse_info *info, const char *base);
+
+static inline int traverse_path_len(const struct traverse_info *info, const struct name_entry *n)
+{
+ return info->pathlen + tree_entry_len(n->path, n->sha1);
+}
#endif
--
1.5.4.3.452.g67136
next prev parent reply other threads:[~2008-03-06 4:37 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2008-03-06 4:28 [PATCH 0/5] Split-up "unpack_trees()" cleanup series Linus Torvalds
2008-03-06 2:25 ` [PATCH 1/5] Add 'df_name_compare()' helper function Linus Torvalds
2008-03-06 13:03 ` David Kastrup
2008-03-06 15:58 ` Linus Torvalds
2008-03-06 21:50 ` David Kastrup
2008-03-06 2:59 ` Linus Torvalds [this message]
2008-03-06 3:44 ` [PATCH 3/5] Add return value to 'traverse_tree()' callback Linus Torvalds
2008-03-06 4:06 ` [PATCH 4/5] Make 'traverse_trees()' traverse conflicting DF entries in parallel Linus Torvalds
2008-03-06 4:15 ` [PATCH 5/5] Move 'unpack_trees()' over to 'traverse_trees()' interface Linus Torvalds
2008-03-06 4:51 ` [PATCH 0/5] Split-up "unpack_trees()" cleanup series Linus Torvalds
2008-03-07 0:13 ` Daniel Barkalow
2008-03-07 2:04 ` Linus Torvalds
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: http://vger.kernel.org/majordomo-info.html
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=71685f79add8cb0982d74745cf3277fc2287c306.1204777699.git.torvalds@linux-foundation.org \
--to=torvalds@linux-foundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://80x24.org/mirrors/git.git
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).