summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--commit-slab.h98
-rw-r--r--commit.c72
2 files changed, 112 insertions, 58 deletions
diff --git a/commit-slab.h b/commit-slab.h
new file mode 100644
index 0000000..7d48163
--- /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 4c05b39..f97456d 100644
--- a/commit.c
+++ b/commit.c
@@ -8,6 +8,7 @@
#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 **);
@@ -501,57 +502,12 @@ struct commit *pop_commit(struct commit_list **stack)
return item;
}
-struct commit_slab_piece {
- int buf;
-};
-
-struct commit_slab {
- int piece_size;
- int piece_count;
- struct commit_slab_piece **piece;
-};
-
-static void slab_init(struct commit_slab *s)
-{
- /* allocate ~512kB at once, allowing for malloc overhead */
- int size = (512*1024-32) / sizeof(struct commit_slab_piece);
-
- s->piece_size = size;
- s->piece_count = 0;
- s->piece = NULL;
-}
-
-static void slab_clear(struct commit_slab *s)
-{
- int i;
-
- for (i = 0; i < s->piece_count; i++)
- free(s->piece[i]);
- s->piece_count = 0;
- free(s->piece);
- s->piece = NULL;
-}
-
-static inline struct commit_slab_piece *slab_at(struct commit_slab *s,
- const struct commit *c)
-{
- int nth_piece, nth_slot;
-
- nth_piece = c->index / s->piece_size;
- nth_slot = c->index % s->piece_size;
-
- if (s->piece_count <= nth_piece) {
- int i;
+/*
+ * Topological sort support
+ */
- s->piece = xrealloc(s->piece, (nth_piece + 1) * sizeof(s->piece));
- for (i = s->piece_count; i <= nth_piece; i++)
- s->piece[i] = NULL;
- s->piece_count = nth_piece + 1;
- }
- if (!s->piece[nth_piece])
- s->piece[nth_piece] = xcalloc(s->piece_size, sizeof(**s->piece));
- return &s->piece[nth_piece][nth_slot];
-}
+/* 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.
@@ -561,18 +517,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 commit_slab indegree;
+ struct indegree_slab indegree;
if (!orig)
return;
*list = NULL;
- slab_init(&indegree);
+ init_indegree_slab(&indegree);
/* Mark them and clear the indegree */
for (next = orig; next; next = next->next) {
struct commit *commit = next->item;
- slab_at(&indegree, commit)->buf = 1;
+ *(indegree_slab_at(&indegree, commit)) = 1;
}
/* update the indegree */
@@ -580,7 +536,7 @@ 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 = &slab_at(&indegree, parent)->buf;
+ int *pi = indegree_slab_at(&indegree, parent);
if (*pi)
(*pi)++;
@@ -600,7 +556,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 (slab_at(&indegree, commit)->buf == 1)
+ if (*(indegree_slab_at(&indegree, commit)) == 1)
insert = &commit_list_insert(commit, insert)->next;
}
@@ -621,7 +577,7 @@ 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 = &slab_at(&indegree, parent)->buf;
+ int *pi = indegree_slab_at(&indegree, parent);
if (!*pi)
continue;
@@ -642,12 +598,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.
*/
- slab_at(&indegree, commit)->buf = 0;
+ *(indegree_slab_at(&indegree, commit)) = 0;
*pptr = work_item;
pptr = &work_item->next;
}
- slab_clear(&indegree);
+ clear_indegree_slab(&indegree);
}
/* merge-base stuff */