[PATCH 2/2] decorate: add "clear_decoration()"

@@ -35,3 +35,25 @@ the `obj`.  You cannot tell if `obj` does not appear in the hashtable
 at all, or if `obj` has decoration whose value is NULL, so if you want
 to use the decoration API for "Did I see this object?" hashtable,
 use decoration value that is _not_ NULL.
+
+Iterating
+---------
+
+`for_each_decoration(struct decoration *deco, for_each_decoration_fn fn)`
+iterates over all the entries in the hashtable, and calls `fn` on each
+entry.  The `fn` callback function takes a single `struct object_decoration`
+as its parameter, that has `base` field that points at the `obj`
+given to an earlier call to `add_decoration` and `decoration` field
+that remembers the `decoration`.
+
+Clearing
+--------
+
+`clear_decoration(struct decoration *deco, for_each_decoration_fn fn)`,
+when `fn` is not NULL, iterates over all the entries and calls the
+callback function `fn` using `for_each_decoration`, and then frees
+the memory used for the hashtable but not the `struct decoration` itself.
+
+The callback function can be used to release the resource used by
+the `decoration` the earlier `add_decoration` registered to the
+hashtable.

@@ -86,3 +86,22 @@ void *lookup_decoration(struct decoration *n, const struct object *obj)
 			j = 0;
 	}
 }
+
+void for_each_decoration(struct decoration *n, for_each_decoration_fn fn)
+{
+	int i;
+
+	for (i = 0; i < n->size; i++) {
+		struct object_decoration *entry = &n->hash[i];
+		if (!entry->base)
+			continue;
+		fn(entry);
+	}
+}
+
+void clear_decoration(struct decoration *n, for_each_decoration_fn fn)
+{
+	if (fn)
+		for_each_decoration(n, fn);
+	free(n->hash);
+}

@@ -15,4 +15,8 @@ struct decoration {
 extern void *add_decoration(struct decoration *n, const struct object *obj, void *decoration);
 extern void *lookup_decoration(struct decoration *n, const struct object *obj);
 
+typedef void (*for_each_decoration_fn)(struct object_decoration *);
+extern void for_each_decoration(struct decoration *, for_each_decoration_fn);
+extern void clear_decoration(struct decoration *, for_each_decoration_fn);
+
 #endif

@@ -506,6 +506,30 @@ struct commit *pop_commit(struct commit_list **stack)
 	return item;
 }
 
+#define QUICK_INDEGREE_LIMIT 255
+
+static inline void set_indegree(struct decoration *indegree,
+				struct commit *commit, intptr_t value)
+{
+	if (QUICK_INDEGREE_LIMIT <= value) {
+		commit->indegree = QUICK_INDEGREE_LIMIT;
+		add_decoration(indegree, &commit->object, (void *)value);
+	} else {
+		commit->indegree = value;
+	}
+}
+
+static inline intptr_t get_indegree(struct decoration *indegree,
+				    struct commit *commit)
+{
+	if (commit->indegree < QUICK_INDEGREE_LIMIT)
+		return commit->indegree;
+	else {
+		void *count = lookup_decoration(indegree, &commit->object);
+		return (int) count;
+	}
+}
+
 /*
  * Performs an in-place topological sort on the list supplied.
  */

@@ -514,15 +538,18 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 	struct commit_list *next, *orig = *list;
 	struct commit_list *work, **insert;
 	struct commit_list **pptr;
+	struct decoration id_overflow;
+	intptr_t count;
 
 	if (!orig)
 		return;
 	*list = NULL;
 
 	/* Mark them and clear the indegree */
+	memset(&id_overflow, 0, sizeof(id_overflow));
 	for (next = orig; next; next = next->next) {
 		struct commit *commit = next->item;
-		commit->indegree = 1;
+		set_indegree(&id_overflow, commit, 1);
 	}
 
 	/* update the indegree */

@@ -531,8 +558,9 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 		while (parents) {
 			struct commit *parent = parents->item;
 
-			if (parent->indegree)
-				parent->indegree++;
+			count = get_indegree(&id_overflow, parent);
+			if (count)
+				set_indegree(&id_overflow, parent, count + 1);
 			parents = parents->next;
 		}
 	}

@@ -549,7 +577,7 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 	for (next = orig; next; next = next->next) {
 		struct commit *commit = next->item;
 
-		if (commit->indegree == 1)
+		if (get_indegree(&id_overflow, commit) == 1)
 			insert = &commit_list_insert(commit, insert)->next;
 	}
 

@@ -571,7 +599,8 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 		for (parents = commit->parents; parents ; parents = parents->next) {
 			struct commit *parent = parents->item;
 
-			if (!parent->indegree)
+			count = get_indegree(&id_overflow, parent);
+			if (!count)
 				continue;
 
 			/*

@@ -579,7 +608,9 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 			 * when all their children have been emitted thereby
 			 * guaranteeing topological order.
 			 */
-			if (--parent->indegree == 1) {
+			count--;
+			set_indegree(&id_overflow, parent, count);
+			if (count == 1) {
 				if (!lifo)
 					commit_list_insert_by_date(parent, &work);
 				else

@@ -590,10 +621,11 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 		 * work_item is a commit all of whose children
 		 * have already been emitted. we can emit it now.
 		 */
-		commit->indegree = 0;
+		set_indegree(&id_overflow, commit, 0);
 		*pptr = work_item;
 		pptr = &work_item->next;
 	}
+	clear_decoration(&id_overflow, NULL);
 }
 
 /* merge-base stuff */

@@ -15,7 +15,7 @@ struct commit_list {
 struct commit {
 	struct object object;
 	void *util;
-	unsigned int indegree;
+	unsigned int indegree:8; /* see QUICK_INDEGREE_LIMIT in commit.c */
 	unsigned long date;
 	struct commit_list *parents;
 	struct tree *tree;

@@ -78,10 +78,53 @@ struct commit *lookup_commit_reference_by_name(const char *name)
 	return commit;
 }
 
+#define QUICK_ENCODING_LIMIT 254 /* offset 1, as 0 is for "no encoding" */
+
+static int quick_encoding_used;
+static struct {
+	const char *encoding;
+	size_t sz;
+} quick_encoding[QUICK_ENCODING_LIMIT];
+static struct decoration slow_encoding;
+
+static void set_commit_encoding(struct commit *item, const char *encoding, size_t sz)
+{
+	int i;
+
+	for (i = 0; i < quick_encoding_used; i++) {
+		if (sz == quick_encoding[i].sz &&
+		    !memcmp(encoding, quick_encoding[i].encoding, sz)) {
+			item->encoding = i + 1;
+			return;
+		}
+	}
+	if (i < QUICK_ENCODING_LIMIT) {
+		quick_encoding[i].sz = sz;
+		quick_encoding[i].encoding = xmemdupz(encoding, sz);
+		item->encoding = i + 1;
+		quick_encoding_used++;
+		return;
+	}
+	item->encoding = QUICK_ENCODING_LIMIT;
+	add_decoration(&slow_encoding, &item->object, xmemdupz(encoding, sz));
+}
+
+const char *get_commit_encoding(const struct commit *item)
+{
+	int i;
+
+	if (!item->encoding)
+		return NULL;
+	i = item->encoding - 1; /* offset 1 */
+	if (i < QUICK_ENCODING_LIMIT)
+		return quick_encoding[i].encoding;
+	return lookup_decoration(&slow_encoding, &item->object);
+}
+
 static void parse_commit_standard_headers(const char *buf, const char *tail,
 					  struct commit *item)
 {
-	const char *dateptr;
+	const char *ptr;
 
 	item->date = 0;
 	if (buf + 6 >= tail)

@@ -98,13 +141,24 @@ static void parse_commit_standard_headers(const char *buf, const char *tail,
 		; /* skip to the end of the e-mail */
 	if (buf >= tail)
 		return;
-	dateptr = buf;
+	ptr = buf;
+	while (buf < tail && *buf++ != '\n')
+		; /* skip to the end of the line */
+	if (buf >= tail)
+		return;
+	/* ptr < buf && buf[-1] == '\n', so strtoul will stop at buf-1 */
+	item->date = strtoul(ptr, NULL, 10);
+
+	item->encoding = 0; /* no encoding header */
+	if (memcmp(buf, "encoding ", 9))
+		return;
+	ptr = buf + 9;
 	while (buf < tail && *buf++ != '\n')
 		; /* skip to the end of the line */
 	if (buf >= tail)
 		return;
-	/* dateptr < buf && buf[-1] == '\n', so strtoul will stop at buf-1 */
-	item->date = strtoul(dateptr, NULL, 10);
+	/* buf[-1] == '\n' that is the end of encoding */
+	set_commit_encoding(item, ptr, buf - ptr);
 }
 
 static struct commit_graft **commit_graft;

@@ -16,12 +16,15 @@ struct commit {
 	struct object object;
 	void *util;
 	unsigned int indegree:8; /* see QUICK_INDEGREE_LIMIT in commit.c */
+	unsigned int encoding:8; /* see QUICK_ENCODING_LIMIT in commit.c */
 	unsigned long date;
 	struct commit_list *parents;
 	struct tree *tree;
 	char *buffer;
 };
 
+extern const char *get_commit_encoding(const struct commit *);
+
 extern int save_commit_buffer;
 extern const char *commit_type;
 

@@ -534,34 +534,6 @@ static void add_merge_info(const struct pretty_print_context *pp,
 	strbuf_addch(sb, '\n');
 }
 
-static char *get_header(const struct commit *commit, const char *msg,
-			const char *key)
-{
-	int key_len = strlen(key);
-	const char *line = msg;
-
-	while (line) {
-		const char *eol = strchr(line, '\n'), *next;
-
-		if (line == eol)
-			return NULL;
-		if (!eol) {
-			warning("malformed commit (header is missing newline): %s",
-				sha1_to_hex(commit->object.sha1));
-			eol = line + strlen(line);
-			next = NULL;
-		} else
-			next = eol + 1;
-		if (eol - line > key_len &&
-		    !strncmp(line, key, key_len) &&
-		    line[key_len] == ' ') {
-			return xmemdupz(line + key_len + 1, eol - line - key_len - 1);
-		}
-		line = next;
-	}
-	return NULL;
-}
-
 static char *replace_encoding_header(char *buf, const char *encoding)
 {
 	struct strbuf tmp = STRBUF_INIT;

@@ -598,7 +570,7 @@ char *logmsg_reencode(const struct commit *commit,
 {
 	static const char *utf8 = "UTF-8";
 	const char *use_encoding;
-	char *encoding;
+	const char *encoding;
 	char *msg = commit->buffer;
 	char *out;
 

@@ -617,7 +589,7 @@ char *logmsg_reencode(const struct commit *commit,
 
 	if (!output_encoding || !*output_encoding)
 		return msg;
-	encoding = get_header(commit, msg, "encoding");
+	encoding = get_commit_encoding(commit);
 	use_encoding = encoding ? encoding : utf8;
 	if (same_encoding(use_encoding, output_encoding)) {
 		/*

@@ -658,7 +630,6 @@ char *logmsg_reencode(const struct commit *commit,
 	if (out)
 		out = replace_encoding_header(out, output_encoding);
 
-	free(encoding);
 	/*
 	 * If the re-encoding failed, out might be NULL here; in that
 	 * case we just return the commit message verbatim.

@@ -116,8 +116,6 @@ static const char *action_name(const struct replay_opts *opts)
 	return opts->action == REPLAY_REVERT ? "revert" : "cherry-pick";
 }
 
-static char *get_encoding(const char *message);
-
 struct commit_message {
 	char *parent_label;
 	const char *label;

@@ -135,7 +133,7 @@ static int get_message(struct commit *commit, struct commit_message *out)
 
 	if (!commit->buffer)
 		return -1;
-	encoding = get_encoding(commit->buffer);
+	encoding = get_commit_encoding(commit);
 	if (!encoding)
 		encoding = "UTF-8";
 	if (!git_commit_encoding)

@@ -173,25 +171,6 @@ static void free_message(struct commit_message *msg)
 	free(msg->reencoded_message);
 }
 
-static char *get_encoding(const char *message)
-{
-	const char *p = message, *eol;
-
-	while (*p && *p != '\n') {
-		for (eol = p + 1; *eol && *eol != '\n'; eol++)
-			; /* do nothing */
-		if (!prefixcmp(p, "encoding ")) {
-			char *result = xmalloc(eol - 8 - p);
-			strlcpy(result, p + 9, eol - 8 - p);
-			return result;
-		}
-		p = eol;
-		if (*p == '\n')
-			p++;
-	}
-	return NULL;
-}
-
 static void write_cherry_pick_head(struct commit *commit, const char *pseudoref)
 {
 	const char *filename;

@@ -78,31 +78,33 @@ struct commit *lookup_commit_reference_by_name(const char *name)
 	return commit;
 }
 
-static unsigned long parse_commit_date(const char *buf, const char *tail)
+static void parse_commit_standard_headers(const char *buf, const char *tail,
+					  struct commit *item)
 {
 	const char *dateptr;
 
+	item->date = 0;
 	if (buf + 6 >= tail)
-		return 0;
+		return;
 	if (memcmp(buf, "author", 6))
-		return 0;
+		return;
 	while (buf < tail && *buf++ != '\n')
-		/* nada */;
+		; /* skip to the end of the line */
 	if (buf + 9 >= tail)
-		return 0;
+		return;
 	if (memcmp(buf, "committer", 9))
-		return 0;
+		return;
 	while (buf < tail && *buf++ != '>')
-		/* nada */;
+		; /* skip to the end of the e-mail */
 	if (buf >= tail)
-		return 0;
+		return;
 	dateptr = buf;
 	while (buf < tail && *buf++ != '\n')
-		/* nada */;
+		; /* skip to the end of the line */
 	if (buf >= tail)
-		return 0;
+		return;
 	/* dateptr < buf && buf[-1] == '\n', so strtoul will stop at buf-1 */
-	return strtoul(dateptr, NULL, 10);
+	item->date = strtoul(dateptr, NULL, 10);
 }
 
 static struct commit_graft **commit_graft;

@@ -262,6 +264,11 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s
 	if (item->object.parsed)
 		return 0;
 	item->object.parsed = 1;
+
+	/*
+	 * tree, 0-or-more parents, author and committer are required
+	 * and must appear in this order; no line folding is allowed.
+	 */
 	tail += size;
 	if (tail <= bufptr + 46 || memcmp(bufptr, "tree ", 5) || bufptr[45] != '\n')
 		return error("bogus commit object %s", sha1_to_hex(item->object.sha1));

@@ -301,8 +308,7 @@ int parse_commit_buffer(struct commit *item, const void *buffer, unsigned long s
 			pptr = &commit_list_insert(new_parent, pptr)->next;
 		}
 	}
-	item->date = parse_commit_date(bufptr, tail);
-
+	parse_commit_standard_headers(bufptr, tail, item);
 	return 0;
 }