diff options
| -rw-r--r-- | commit-slab.h | 98 | ||||
| -rw-r--r-- | commit.c | 72 |
2 files changed, 112 insertions, 58 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 */ @@ -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 */ |