Merge branch 'jk/commit-info-slab'

Allow adding custom information to commit objects in order to
represent unbound number of flag bits etc.

* jk/commit-info-slab:
  commit-slab: introduce a macro to define a slab for new type
  commit-slab: avoid large realloc
  commit: allow associating auxiliary info on-demand

3 files changed, 127 insertions, 10 deletions

diff --git a/commit-slab.h b/commit-slab.h
new file mode 100644
index 0000000000..7d481638af
--- /dev/null
+++ b/commit-slab.h
@@ -0,0 +1,98 @@
+#ifndef COMMIT_SLAB_H
+#define COMMIT_SLAB_H
+
+/*
+ * define_commit_slab(slabname, elemtype) creates boilerplate code to define
+ * a new struct (struct slabname) that is used to associate a piece of data
+ * of elemtype to commits, and a few functions to use that struct.
+ *
+ * After including this header file, using:
+ *
+ * define_commit_slab(indegee, int);
+ *
+ * will let you call the following functions:
+ *
+ * - int *indegree_at(struct indegree *, struct commit *);
+ *
+ *   This function locates the data associated with the given commit in
+ *   the indegree slab, and returns the pointer to it.
+ *
+ * - void init_indegree(struct indegree *);
+ *   void init_indegree_with_stride(struct indegree *, int);
+ *
+ *   Initializes the indegree slab that associates an array of integers
+ *   to each commit. 'stride' specifies how big each array is.  The slab
+ *   that id initialied by the variant without "_with_stride" associates
+ *   each commit with an array of one integer.
+ */
+
+/* allocate ~512kB at once, allowing for malloc overhead */
+#ifndef COMMIT_SLAB_SIZE
+#define COMMIT_SLAB_SIZE (512*1024-32)
+#endif
+
+#define define_commit_slab(slabname, elemtype) 				\
+									\
+struct slabname {							\
+	unsigned slab_size;						\
+	unsigned stride;						\
+	unsigned slab_count;						\
+	elemtype **slab;						\
+};									\
+static int stat_ ##slabname## realloc;					\
+									\
+static void init_ ##slabname## _with_stride(struct slabname *s,		\
+					    unsigned stride)		\
+{									\
+	unsigned int elem_size;						\
+	if (!stride)							\
+		stride = 1;						\
+	s->stride = stride;						\
+	elem_size = sizeof(struct slabname) * stride;			\
+	s->slab_size = COMMIT_SLAB_SIZE / elem_size;			\
+	s->slab_count = 0;						\
+	s->slab = NULL;							\
+}									\
+									\
+static void init_ ##slabname(struct slabname *s)			\
+{									\
+	init_ ##slabname## _with_stride(s, 1);				\
+}									\
+									\
+static void clear_ ##slabname(struct slabname *s)			\
+{									\
+	int i;								\
+	for (i = 0; i < s->slab_count; i++)				\
+		free(s->slab[i]);					\
+	s->slab_count = 0;						\
+	free(s->slab);							\
+	s->slab = NULL;							\
+}									\
+									\
+static elemtype *slabname## _at(struct slabname *s,			\
+				const struct commit *c)			\
+{									\
+	int nth_slab, nth_slot, ix;					\
+									\
+	ix = c->index * s->stride;					\
+	nth_slab = ix / s->slab_size;					\
+	nth_slot = ix % s->slab_size;					\
+									\
+	if (s->slab_count <= nth_slab) {				\
+		int i;							\
+		s->slab = xrealloc(s->slab,				\
+				   (nth_slab + 1) * sizeof(s->slab));	\
+		stat_ ##slabname## realloc++;				\
+		for (i = s->slab_count; i <= nth_slab; i++)		\
+			s->slab[i] = NULL;				\
+		s->slab_count = nth_slab + 1;				\
+	}								\
+	if (!s->slab[nth_slab])						\
+		s->slab[nth_slab] = xcalloc(s->slab_size,		\
+					    sizeof(**s->slab));		\
+	return &s->slab[nth_slab][nth_slot];				\
+}									\
+									\
+static int stat_ ##slabname## realloc
+
+#endif /* COMMIT_SLAB_H */
diff --git a/commit.c b/commit.c
index 888e02ae2f..a1096a2b5a 100644
--- a/commit.c
+++ b/commit.c
@@ -8,12 +8,14 @@
 #include "notes.h"
 #include "gpg-interface.h"
 #include "mergesort.h"
+#include "commit-slab.h"
 
 static struct commit_extra_header *read_commit_extra_header_lines(const char *buf, size_t len, const char **);
 
 int save_commit_buffer = 1;
 
 const char *commit_type = "commit";
+static int commit_count;
 
 static struct commit *check_commit(struct object *obj,
 				   const unsigned char *sha1,
@@ -58,8 +60,11 @@ struct commit *lookup_commit_or_die(const unsigned char *sha1, const char *ref_n
 struct commit *lookup_commit(const unsigned char *sha1)
 {
 	struct object *obj = lookup_object(sha1);
-	if (!obj)
-		return create_object(sha1, OBJ_COMMIT, alloc_commit_node());
+	if (!obj) {
+		struct commit *c = alloc_commit_node();
+		c->index = commit_count++;
+		return create_object(sha1, OBJ_COMMIT, c);
+	}
 	if (!obj->type)
 		obj->type = OBJ_COMMIT;
 	return check_commit(obj, sha1, 0);
@@ -507,6 +512,13 @@ struct commit *pop_commit(struct commit_list **stack)
 }
 
 /*
+ * Topological sort support
+ */
+
+/* count number of children that have not been emitted */
+define_commit_slab(indegree_slab, int);
+
+/*
  * Performs an in-place topological sort on the list supplied.
  */
 void sort_in_topological_order(struct commit_list ** list, int lifo)
@@ -514,15 +526,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 indegree_slab indegree;
 
 	if (!orig)
 		return;
 	*list = NULL;
 
+	init_indegree_slab(&indegree);
+
 	/* Mark them and clear the indegree */
 	for (next = orig; next; next = next->next) {
 		struct commit *commit = next->item;
-		commit->indegree = 1;
+		*(indegree_slab_at(&indegree, commit)) = 1;
 	}
 
 	/* update the indegree */
@@ -530,9 +545,10 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 		struct commit_list * parents = next->item->parents;
 		while (parents) {
 			struct commit *parent = parents->item;
+			int *pi = indegree_slab_at(&indegree, parent);
 
-			if (parent->indegree)
-				parent->indegree++;
+			if (*pi)
+				(*pi)++;
 			parents = parents->next;
 		}
 	}
@@ -549,7 +565,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 (*(indegree_slab_at(&indegree, commit)) == 1)
 			insert = &commit_list_insert(commit, insert)->next;
 	}
 
@@ -570,8 +586,9 @@ void sort_in_topological_order(struct commit_list ** list, int lifo)
 		commit = work_item->item;
 		for (parents = commit->parents; parents ; parents = parents->next) {
 			struct commit *parent = parents->item;
+			int *pi = indegree_slab_at(&indegree, parent);
 
-			if (!parent->indegree)
+			if (!*pi)
 				continue;
 
 			/*
@@ -579,7 +596,7 @@ 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) {
+			if (--(*pi) == 1) {
 				if (!lifo)
 					commit_list_insert_by_date(parent, &work);
 				else
@@ -590,10 +607,12 @@ 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;
+		*(indegree_slab_at(&indegree, commit)) = 0;
 		*pptr = work_item;
 		pptr = &work_item->next;
 	}
+
+	clear_indegree_slab(&indegree);
 }
 
 /* merge-base stuff */
diff --git a/commit.h b/commit.h
index 6e9c7cd9d5..350472114b 100644
--- a/commit.h
+++ b/commit.h
@@ -15,7 +15,7 @@ struct commit_list {
 struct commit {
 	struct object object;
 	void *util;
-	unsigned int indegree;
+	unsigned int index;
 	unsigned long date;
 	struct commit_list *parents;
 	struct tree *tree;