diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/commit.c | 295 | ||||
| -rw-r--r-- | src/commit.h | 44 | ||||
| -rw-r--r-- | src/git/commit.h | 24 | ||||
| -rw-r--r-- | src/git/common.h | 10 | ||||
| -rw-r--r-- | src/git/odb.h | 1 | ||||
| -rw-r--r-- | src/git/repository.h | 60 | ||||
| -rw-r--r-- | src/git/revwalk.h | 66 | ||||
| -rw-r--r-- | src/git/tag.h | 23 | ||||
| -rw-r--r-- | src/git/tree.h | 21 | ||||
| -rw-r--r-- | src/hashtable.c (renamed from src/revobject.c) | 186 | ||||
| -rw-r--r-- | src/hashtable.h | 51 | ||||
| -rw-r--r-- | src/repository.c | 143 | ||||
| -rw-r--r-- | src/repository.h | 25 | ||||
| -rw-r--r-- | src/revobject.h | 52 | ||||
| -rw-r--r-- | src/revwalk.c | 444 | ||||
| -rw-r--r-- | src/revwalk.h | 58 | ||||
| -rw-r--r-- | src/tag.c | 33 | ||||
| -rw-r--r-- | src/tag.h | 6 | ||||
| -rw-r--r-- | src/tree.c | 49 | ||||
| -rw-r--r-- | src/tree.h | 4 |
20 files changed, 871 insertions, 724 deletions
diff --git a/src/commit.c b/src/commit.c index 4199e8e9c..1ffbc72ca 100644 --- a/src/commit.c +++ b/src/commit.c @@ -27,6 +27,7 @@ #include "commit.h" #include "revwalk.h" #include "git/odb.h" +#include "git/repository.h" #define COMMIT_PRINT(commit) {\ char oid[41]; oid[40] = 0;\ @@ -34,9 +35,23 @@ printf("Oid: %s | In degree: %d | Time: %u\n", oid, commit->in_degree, commit->commit_time);\ } +static void clear_parents(git_commit *commit) +{ + git_commit_parents *node, *next_node; + + node = commit->parents; + while (node) { + next_node = node->next; + free(node); + node = next_node; + } + + commit->parents = NULL; +} + void git_commit__free(git_commit *commit) { - git_commit_list_clear(&commit->parents, 0); + clear_parents(commit); if (commit->odb_open) git_obj_close(&commit->odb_object); @@ -53,47 +68,12 @@ const git_oid *git_commit_id(git_commit *c) return &c->object.id; } -void git_commit__mark_uninteresting(git_commit *commit) -{ - git_commit_node *parents; - - if (commit == NULL) - return; - - parents = commit->parents.head; - - commit->uninteresting = 1; - - while (parents) { - parents->commit->uninteresting = 1; - parents = parents->next; - } -} - -git_commit *git_commit_parse(git_revpool *pool, const git_oid *id) -{ - git_commit *commit = NULL; - - if ((commit = git_commit_lookup(pool, id)) == NULL) - return NULL; - - if (git_commit__parse_basic(commit) < 0) - goto error_cleanup; - - return commit; - -error_cleanup: - /* FIXME: do not free; the commit is owned by the revpool */ - free(commit); - return NULL; -} - int git_commit__parse(git_commit *commit, unsigned int parse_flags, int close_db_object) { int error = 0; if (!commit->odb_open) { - error = git_odb_read(&commit->odb_object, commit->object.pool->db, &commit->object.id); + error = git_odb_read(&commit->odb_object, commit->object.repo->db, &commit->object.id); if (error < 0) return error; @@ -133,32 +113,9 @@ int git_commit__parse_basic(git_commit *commit) return 0; } -git_commit *git_commit_lookup(git_revpool *pool, const git_oid *id) +git_commit *git_commit_lookup(git_repository *repo, const git_oid *id) { - git_commit *commit = NULL; - - if (pool == NULL) - return NULL; - - commit = (git_commit *)git_revpool_table_lookup(pool->objects, id); - if (commit != NULL) - return commit; - - commit = git__malloc(sizeof(git_commit)); - - if (commit == NULL) - return NULL; - - memset(commit, 0x0, sizeof(git_commit)); - - /* Initialize parent object */ - git_oid_cpy(&commit->object.id, id); - commit->object.pool = pool; - commit->object.type = GIT_OBJ_COMMIT; - - git_revpool_table_insert(pool->objects, (git_revpool_object *)commit); - - return commit; + return (git_commit *)git_repository_lookup(repo, id, GIT_OBJ_COMMIT); } int git__parse_person(git_person *person, char **buffer_out, @@ -257,30 +214,31 @@ int git_commit__parse_buffer(git_commit *commit, void *data, size_t len, unsigne return GIT_EOBJCORRUPTED; if (parse_flags & GIT_COMMIT_TREE) - commit->tree = git_tree_lookup(commit->object.pool, &oid); + commit->tree = git_tree_lookup(commit->object.repo, &oid); /* * TODO: commit grafts! */ if (parse_flags & GIT_COMMIT_PARENTS) - git_commit_list_clear(&commit->parents, 0); + clear_parents(commit); while (git__parse_oid(&oid, &buffer, buffer_end, "parent ") == 0) { git_commit *parent; + git_commit_parents *node; if ((parse_flags & GIT_COMMIT_PARENTS) == 0) continue; - if ((parent = git_commit_lookup(commit->object.pool, &oid)) == NULL) + if ((parent = git_commit_lookup(commit->object.repo, &oid)) == NULL) return GIT_ENOTFOUND; - /* Inherit uninteresting flag */ - if (commit->uninteresting) - parent->uninteresting = 1; - - if (git_commit_list_push_back(&commit->parents, parent) < 0) + if ((node = git__malloc(sizeof(git_commit_parents))) == NULL) return GIT_ENOMEM; + + node->commit = parent; + node->next = commit->parents; + commit->parents = node; } if (git__parse_person(&person, &buffer, buffer_end, "author ") < 0) @@ -391,200 +349,3 @@ const char *git_commit_message_short(git_commit *commit) git_commit__parse(commit, GIT_COMMIT_MESSAGE_SHORT, 0); return commit->message_short; } - - - -int git_commit_list_push_back(git_commit_list *list, git_commit *commit) -{ - git_commit_node *node = NULL; - - node = git__malloc(sizeof(git_commit_list)); - - if (node == NULL) - return GIT_ENOMEM; - - node->commit = commit; - node->next = NULL; - node->prev = list->tail; - - if (list->tail == NULL) { - list->head = list->tail = node; - } else { - list->tail->next = node; - list->tail = node; - } - - list->size++; - return 0; -} - -int git_commit_list_push_front(git_commit_list *list, git_commit *commit) -{ - git_commit_node *node = NULL; - - node = git__malloc(sizeof(git_commit_list)); - - if (node == NULL) - return GIT_ENOMEM; - - node->commit = commit; - node->next = list->head; - node->prev = NULL; - - if (list->head == NULL) { - list->head = list->tail = node; - } else { - list->head->prev = node; - list->head = node; - } - - list->size++; - return 0; -} - - -git_commit *git_commit_list_pop_back(git_commit_list *list) -{ - git_commit_node *node; - git_commit *commit; - - if (list->tail == NULL) - return NULL; - - node = list->tail; - list->tail = list->tail->prev; - if (list->tail == NULL) - list->head = NULL; - - commit = node->commit; - free(node); - - list->size--; - - return commit; -} - -git_commit *git_commit_list_pop_front(git_commit_list *list) -{ - git_commit_node *node; - git_commit *commit; - - if (list->head == NULL) - return NULL; - - node = list->head; - list->head = list->head->next; - if (list->head == NULL) - list->tail = NULL; - - commit = node->commit; - free(node); - - list->size--; - - return commit; -} - -void git_commit_list_clear(git_commit_list *list, int free_commits) -{ - git_commit_node *node, *next_node; - - node = list->head; - while (node) { - if (free_commits) - free(node->commit); - - next_node = node->next; - free(node); - node = next_node; - } - - list->head = list->tail = NULL; - list->size = 0; -} - -void git_commit_list_timesort(git_commit_list *list) -{ - git_commit_node *p, *q, *e; - int in_size, p_size, q_size, merge_count, i; - - if (list->head == NULL) - return; - - in_size = 1; - - do { - p = list->head; - list->tail = NULL; - merge_count = 0; - - while (p != NULL) { - merge_count++; - q = p; - p_size = 0; - q_size = in_size; - - for (i = 0; i < in_size && q; ++i, q = q->next) - p_size++; - - while (p_size > 0 || (q_size > 0 && q)) { - - if (p_size == 0) - e = q, q = q->next, q_size--; - - else if (q_size == 0 || q == NULL || - p->commit->commit_time >= q->commit->commit_time) - e = p, p = p->next, p_size--; - - else - e = q, q = q->next, q_size--; - - if (list->tail != NULL) - list->tail->next = e; - else - list->head = e; - - e->prev = list->tail; - list->tail = e; - } - - p = q; - } - - list->tail->next = NULL; - in_size *= 2; - - } while (merge_count > 1); -} - -void git_commit_list_toposort(git_commit_list *list) -{ - git_commit *commit; - git_commit_list topo; - memset(&topo, 0x0, sizeof(git_commit_list)); - - while ((commit = git_commit_list_pop_back(list)) != NULL) { - git_commit_node *p; - - if (commit->in_degree > 0) { - commit->topo_delay = 1; - continue; - } - - for (p = commit->parents.head; p != NULL; p = p->next) { - p->commit->in_degree--; - - if (p->commit->in_degree == 0 && p->commit->topo_delay) { - p->commit->topo_delay = 0; - git_commit_list_push_back(list, p->commit); - } - } - - git_commit_list_push_back(&topo, commit); - } - - list->head = topo.head; - list->tail = topo.tail; - list->size = topo.size; -} - diff --git a/src/commit.h b/src/commit.h index 028c83712..60e1d1115 100644 --- a/src/commit.h +++ b/src/commit.h @@ -3,26 +3,10 @@ #include "git/commit.h" #include "tree.h" -#include "revobject.h" +#include "repository.h" #include <time.h> -struct git_commit_node { - struct git_commit *commit; - - struct git_commit_node *next; - struct git_commit_node *prev; -}; - -struct git_commit_list { - struct git_commit_node *head; - struct git_commit_node *tail; - size_t size; -}; - -typedef struct git_commit_list git_commit_list; -typedef struct git_commit_node git_commit_node; - #define GIT_COMMIT_TREE (1 << 1) #define GIT_COMMIT_PARENTS (1 << 2) #define GIT_COMMIT_AUTHOR (1 << 3) @@ -32,12 +16,17 @@ typedef struct git_commit_node git_commit_node; #define GIT_COMMIT_MESSAGE_SHORT (1 << 7) #define GIT_COMMIT_FOOTERS (1 << 8) +typedef struct git_commit_parents { + git_commit *commit; + struct git_commit_parents *next; +} git_commit_parents; + struct git_commit { - git_revpool_object object; + git_repository_object object; git_obj odb_object; time_t commit_time; - git_commit_list parents; + git_commit_parents *parents; git_tree *tree; git_person *author; @@ -46,13 +35,8 @@ struct git_commit { char *message; char *message_short; - unsigned short in_degree; unsigned basic_parse:1, - odb_open:1, - seen:1, - uninteresting:1, - topo_delay:1, - flags:25; + odb_open:1; }; void git_commit__free(git_commit *c); @@ -64,15 +48,5 @@ void git_commit__mark_uninteresting(git_commit *commit); int git__parse_oid(git_oid *oid, char **buffer_out, const char *buffer_end, const char *header); int git__parse_person(git_person *person, char **buffer_out, const char *buffer_end, const char *header); -int git_commit_list_push_back(git_commit_list *list, git_commit *commit); -int git_commit_list_push_front(git_commit_list *list, git_commit *commit); - -git_commit *git_commit_list_pop_back(git_commit_list *list); -git_commit *git_commit_list_pop_front(git_commit_list *list); - -void git_commit_list_clear(git_commit_list *list, int free_commits); - -void git_commit_list_timesort(git_commit_list *list); -void git_commit_list_toposort(git_commit_list *list); #endif diff --git a/src/git/commit.h b/src/git/commit.h index 89f0929c9..56243c5be 100644 --- a/src/git/commit.h +++ b/src/git/commit.h @@ -4,6 +4,7 @@ #include "common.h" #include "oid.h" #include "tree.h" +#include "repository.h" /** * @file git/commit.h @@ -18,31 +19,16 @@ GIT_BEGIN_DECL typedef struct git_commit git_commit; /** - * Locate a reference to a commit without loading it. + * Lookup a commit object from a repository. * The generated commit object is owned by the revision - * pool and shall not be freed by the user. + * repo and shall not be freed by the user. * - * @param pool the pool to use when locating the commit. + * @param repo the repo to use when locating the commit. * @param id identity of the commit to locate. If the object is * an annotated tag it will be peeled back to the commit. * @return the commit; NULL if the commit could not be created */ -GIT_EXTERN(git_commit *) git_commit_lookup(git_revpool *pool, const git_oid *id); - -/** - * Locate a reference to a commit, and try to load and parse it it from - * the commit cache or the object database. - * The generated commit object is owned by the revision - * pool and shall not be freed by the user. - * - * @param pool the pool to use when parsing/caching the commit. - * @param id identity of the commit to locate. If the object is - * an annotated tag it will be peeled back to the commit. - * @return the commit; NULL if the commit does not exist in the - * pool's git_odb, or if the commit is present but is - * too malformed to be parsed successfully. - */ -GIT_EXTERN(git_commit *) git_commit_parse(git_revpool *pool, const git_oid *id); +GIT_EXTERN(git_commit *) git_commit_lookup(git_repository *repo, const git_oid *id); /** * Get the id of a commit. diff --git a/src/git/common.h b/src/git/common.h index 09972aade..b43f4ee01 100644 --- a/src/git/common.h +++ b/src/git/common.h @@ -85,8 +85,14 @@ GIT_BEGIN_DECL -/** A revision traversal pool. */ -typedef struct git_revpool git_revpool; +/** + * Representation of an existing git repository, + * including all its object contents + */ +typedef struct git_repository git_repository; + +/* Representation of a generic object in a repository */ +typedef struct git_repository_object git_repository_object; /** Parsed representation of a person */ typedef struct git_person { diff --git a/src/git/odb.h b/src/git/odb.h index 58b932645..5d105ba70 100644 --- a/src/git/odb.h +++ b/src/git/odb.h @@ -35,6 +35,7 @@ GIT_EXTERN(void) git_odb_close(git_odb *db); /** Basic type (loose or packed) of any Git object. */ typedef enum { + GIT_OBJ_ANY = -2, /**< Object can be any of the following */ GIT_OBJ_BAD = -1, /**< Object is invalid. */ GIT_OBJ__EXT1 = 0, /**< Reserved for future use. */ GIT_OBJ_COMMIT = 1, /**< A commit object. */ diff --git a/src/git/repository.h b/src/git/repository.h new file mode 100644 index 000000000..3b6981d50 --- /dev/null +++ b/src/git/repository.h @@ -0,0 +1,60 @@ +#ifndef INCLUDE_git_repository_h__ +#define INCLUDE_git_repository_h__ + +#include "common.h" +#include "odb.h" +#include "commit.h" + +/** + * @file git/repository.h + * @brief Git revision object management routines + * @defgroup git_repository Git revision object management routines + * @ingroup Git + * @{ + */ +GIT_BEGIN_DECL + +/** + * Allocate a new repository object. + * + * TODO: specify the repository's path instead + * of its object database + * + * @param odb an existing object database to back the repo + * @return the new repository handle; NULL on error + */ +GIT_EXTERN(git_repository *) git_repository_alloc(git_odb *odb); + + +/** + * Lookup a reference to one of the objects in the repostory. + * + * The generated reference is owned by the repository and + * should not be freed by the user. + * The generated reference should be cast back to the + * expected type; e.g. + * + * git_commit *c = (git_commit *) + * git_repository_lookup(repo, id, GIT_OBJ_COMMIT); + * + * The 'type' parameter must match the type of the object + * in the odb; the method will fail otherwise. + * The special value 'GIT_OBJ_ANY' may be passed to let + * the method guess the object's type. + * + * @param repo the repository to look up the object + * @param id the unique identifier for the object + * @param type the type of the object + * @return a reference to the object + */ +GIT_EXTERN(git_repository_object *) git_repository_lookup(git_repository *repo, const git_oid *id, git_otype type); + +/** + * Free a previously allocated repository + * @param repo repository handle to close. If NULL nothing occurs. + */ +GIT_EXTERN(void) git_repository_free(git_repository *repo); + +/** @} */ +GIT_END_DECL +#endif diff --git a/src/git/revwalk.h b/src/git/revwalk.h index 7aa92d44a..842503dea 100644 --- a/src/git/revwalk.h +++ b/src/git/revwalk.h @@ -15,87 +15,87 @@ GIT_BEGIN_DECL /** - * Sort the revpool contents in no particular ordering; + * Sort the repository contents in no particular ordering; * this sorting is arbritary, implementation-specific * and subject to change at any time. - * This is the default sorting for new revision pools. + * This is the default sorting for new walkers. */ -#define GIT_RPSORT_NONE (0) +#define GIT_SORT_NONE (0) /** - * Sort the revpool contents in topological order + * Sort the repository contents in topological order * (parents before children); this sorting mode * can be combined with time sorting. */ -#define GIT_RPSORT_TOPOLOGICAL (1 << 0) +#define GIT_SORT_TOPOLOGICAL (1 << 0) /** - * Sort the revpool contents by commit time; + * Sort the repository contents by commit time; * this sorting mode can be combined with * topological sorting. */ -#define GIT_RPSORT_TIME (1 << 1) +#define GIT_SORT_TIME (1 << 1) /** - * Iterate through the revpool contents in reverse + * Iterate through the repository contents in reverse * order; this sorting mode can be combined with * any of the above. */ -#define GIT_RPSORT_REVERSE (1 << 2) +#define GIT_SORT_REVERSE (1 << 2) + +typedef struct git_revwalk git_revwalk; /** - * Allocate a new revision traversal pool. - * - * The configuration is copied during allocation. Changes - * to the configuration after allocation do not affect the pool - * returned by this function. Callers may safely free the - * passed configuration after the function completes. + * Allocate a new revision walker to iterate through a repo. * - * @param db the database objects are read from. - * @return the new traversal handle; NULL if memory is exhausted. + * @param repo the repo to walk through + * @return the new walker handle; NULL if memory is exhausted. */ -GIT_EXTERN(git_revpool *) gitrp_alloc(git_odb *db); +GIT_EXTERN(git_revwalk *) git_revwalk_alloc(git_repository *repo); /** - * Reset the traversal machinary for reuse. - * @param pool traversal handle to reset. + * Reset the walking machinary for reuse. + * @param walker handle to reset. */ -GIT_EXTERN(void) gitrp_reset(git_revpool *pool); +GIT_EXTERN(void) git_revwalk_reset(git_revwalk *walker); /** - * Mark an object to start traversal from. - * @param pool the pool being used for the traversal. + * Mark a commit to start traversal from. + * The commit object must belong to the repo which is being walked through. + * + * @param walker the walker being used for the traversal. * @param commit the commit to start from. */ -GIT_EXTERN(int) gitrp_push(git_revpool *pool, git_commit *commit); +GIT_EXTERN(int) git_revwalk_push(git_revwalk *walk, git_commit *commit); /** * Mark a commit (and its ancestors) uninteresting for the output. - * @param pool the pool being used for the traversal. + * @param walker the walker being used for the traversal. * @param commit the commit that will be ignored during the traversal */ -GIT_EXTERN(int) gitrp_hide(git_revpool *pool, git_commit *commit); +GIT_EXTERN(int) git_revwalk_hide(git_revwalk *walk, git_commit *commit); /** * Get the next commit from the revision traversal. - * @param pool the pool to pop the commit from. + * @param walk the walker to pop the commit from. * @return next commit; NULL if there is no more output. */ -GIT_EXTERN(git_commit *) gitrp_next(git_revpool *pool); +GIT_EXTERN(git_commit *) git_revwalk_next(git_revwalk *walk); /** * Change the sorting mode when iterating through the - * revision pool's contents. - * @param pool the pool being used for the traversal. + * repository's contents. + * Changing the sorting mode resets the walker. + * @param walk the walker being used for the traversal. * @param sort_mode combination of GIT_RPSORT_XXX flags */ -GIT_EXTERN(void) gitrp_sorting(git_revpool *pool, unsigned int sort_mode); +GIT_EXTERN(void) git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode); /** * Free a revwalk previously allocated. - * @param pool traversal handle to close. If NULL nothing occurs. + * @param walk traversal handle to close. If NULL nothing occurs. */ -GIT_EXTERN(void) gitrp_free(git_revpool *pool); +GIT_EXTERN(void) git_revwalk_free(git_revwalk *walk); /** @} */ GIT_END_DECL diff --git a/src/git/tag.h b/src/git/tag.h index 509d2f047..d94083b11 100644 --- a/src/git/tag.h +++ b/src/git/tag.h @@ -4,6 +4,7 @@ #include "common.h" #include "oid.h" #include "tree.h" +#include "repository.h" /** * @file git/tag.h @@ -18,29 +19,15 @@ GIT_BEGIN_DECL typedef struct git_tag git_tag; /** - * Locate a reference to a tag without loading it. + * Lookup a tag object from the repository. * The generated tag object is owned by the revision - * pool and shall not be freed by the user. + * repo and shall not be freed by the user. * - * @param pool the pool to use when locating the tag. + * @param repo the repo to use when locating the tag. * @param id identity of the tag to locate. * @return the tag; NULL if the tag could not be created */ -GIT_EXTERN(git_tag *) git_tag_lookup(git_revpool *pool, const git_oid *id); - -/** - * Locate a reference to a tag, and try to load and parse it it from - * the object cache or the object database. - * The generated tag object is owned by the revision - * pool and shall not be freed by the user. - * - * @param pool the pool to use when parsing/caching the tag. - * @param id identity of the tag to locate. - * @return the tag; NULL if the tag does not exist in the - * pool's git_odb, or if the tag is present but is - * too malformed to be parsed successfully. - */ -GIT_EXTERN(git_tag *) git_tag_parse(git_revpool *pool, const git_oid *id); +GIT_EXTERN(git_tag *) git_tag_lookup(git_repository *repo, const git_oid *id); /** * Get the id of a tag. diff --git a/src/git/tree.h b/src/git/tree.h index 9a4973ba6..95b233009 100644 --- a/src/git/tree.h +++ b/src/git/tree.h @@ -3,6 +3,7 @@ #include "common.h" #include "oid.h" +#include "repository.h" /** * @file git/tree.h @@ -17,27 +18,15 @@ GIT_BEGIN_DECL typedef struct git_tree git_tree; /** - * Locate a reference to a tree without loading it. + * Lookup a tree object from the repository. * The generated tree object is owned by the revision - * pool and shall not be freed by the user. + * repo and shall not be freed by the user. * - * @param pool the pool to use when locating the tree. + * @param repo the repo to use when locating the tree. * @param id identity of the tree to locate. * @return the tree; NULL if the tree could not be created */ -GIT_EXTERN(git_tree *) git_tree_lookup(git_revpool *pool, const git_oid *id); - -/** - * Locate a reference to a tree object and parse its - * contents. - * The generated tree object is owned by the revision - * pool and shall not be freed by the user. - * - * @param pool the pool to use when locating the tree. - * @param id identity of the tree to locate. - * @return the tree; NULL if the tree could not be created - */ -GIT_EXTERN(git_tree *) git_tree_parse(git_revpool *pool, const git_oid *id); +GIT_EXTERN(git_tree *) git_tree_lookup(git_repository *repo, const git_oid *id); /** * Get the id of a tree. diff --git a/src/revobject.c b/src/hashtable.c index 47d75e047..4006a8714 100644 --- a/src/revobject.c +++ b/src/hashtable.c @@ -24,25 +24,55 @@ */ #include "common.h" -#include "revobject.h" +#include "repository.h" +#include "commit.h" +static const int default_table_size = 32; static const double max_load_factor = 0.65; -static unsigned int git_revpool_table__hash(const git_oid *id) +static void hashtable_resize(git_hashtable *table) { - unsigned int r; - memcpy(&r, id->id, sizeof(r)); - return r; + git_hashtable_node **new_nodes; + unsigned int new_size, i; + + assert(table); + + new_size = (table->size_mask + 1) * 2; + + new_nodes = git__malloc(new_size * sizeof(git_hashtable_node *)); + if (new_nodes == NULL) + return; + + memset(new_nodes, 0x0, new_size * sizeof(git_hashtable_node *)); + + for (i = 0; i <= table->size_mask; ++i) { + git_hashtable_node *n; + unsigned int index; + + while ((n = table->nodes[i]) != NULL) { + table->nodes[i] = n->next; + index = n->hash & (new_size - 1); + n->next = new_nodes[index]; + new_nodes[index] = n; + } + } + + free(table->nodes); + table->nodes = new_nodes; + table->size_mask = (new_size - 1); + table->max_count = (unsigned int)(new_size * max_load_factor); } -git_revpool_table *git_revpool_table_create(unsigned int min_size) +git_hashtable *git_hashtable_alloc(unsigned int min_size, + git_hash_ptr hash, + git_hash_keyeq_ptr key_eq) { - git_revpool_table *table; unsigned int i; + git_hashtable *table; - table = git__malloc(sizeof(*table)); + assert(hash && key_eq); - if (table == NULL) + if ((table = git__malloc(sizeof(git_hashtable))) == NULL) return NULL; /* round up size to closest power of 2 */ @@ -57,7 +87,10 @@ git_revpool_table *git_revpool_table_create(unsigned int min_size) table->count = 0; table->max_count = (unsigned int)((min_size + 1) * max_load_factor); - table->nodes = git__malloc((min_size + 1) * sizeof(git_revpool_node *)); + table->hash = hash; + table->key_equal = key_eq; + + table->nodes = git__malloc((min_size + 1) * sizeof(git_hashtable_node *)); if (table->nodes == NULL) { free(table); @@ -70,48 +103,78 @@ git_revpool_table *git_revpool_table_create(unsigned int min_size) return table; } -int git_revpool_table_insert(git_revpool_table *table, git_revpool_object *object) +void git_hashtable_clear(git_hashtable *table) { - git_revpool_node *node; - unsigned int index, hash; + unsigned int index; + + assert(table); + + for (index = 0; index <= table->size_mask; ++index) { + git_hashtable_node *node, *next_node; + + node = table->nodes[index]; + while (node != NULL) { + next_node = node->next; + free(node); + node = next_node; + } + + table->nodes[index] = NULL; + } + + table->count = 0; +} + +void git_hashtable_free(git_hashtable *table) +{ + assert(table); - if (table == NULL) - return GIT_ERROR; + git_hashtable_clear(table); + free(table->nodes); + free(table); +} + + +int git_hashtable_insert(git_hashtable *table, const void *key, void *value) +{ + git_hashtable_node *node; + uint32_t index, hash; + + assert(table); if (table->count + 1 > table->max_count) - git_revpool_table_resize(table); + hashtable_resize(table); - node = git__malloc(sizeof(git_revpool_node)); + node = git__malloc(sizeof(git_hashtable_node)); if (node == NULL) return GIT_ENOMEM; - hash = git_revpool_table__hash(&object->id); + hash = table->hash(key); index = (hash & table->size_mask); - node->object = object; + node->object = value; node->hash = hash; node->next = table->nodes[index]; table->nodes[index] = node; table->count++; - return 0; + return GIT_SUCCESS; } -git_revpool_object *git_revpool_table_lookup(git_revpool_table *table, const git_oid *id) +void *git_hashtable_lookup(git_hashtable *table, const void *key) { - git_revpool_node *node; - unsigned int index, hash; + git_hashtable_node *node; + uint32_t index, hash; - if (table == NULL) - return NULL; + assert(table); - hash = git_revpool_table__hash(id); + hash = table->hash(key); index = (hash & table->size_mask); node = table->nodes[index]; while (node != NULL) { - if (node->hash == hash && git_oid_cmp(id, &node->object->id) == 0) + if (node->hash == hash && table->key_equal(node->object, key)) return node->object; node = node->next; @@ -120,60 +183,13 @@ git_revpool_object *git_revpool_table_lookup(git_revpool_table *table, const git return NULL; } -void git_revpool_table_resize(git_revpool_table *table) -{ - git_revpool_node **new_nodes; - unsigned int new_size, i; - - new_size = (table->size_mask + 1) * 2; - - new_nodes = git__malloc(new_size * sizeof(git_revpool_node *)); - if (new_nodes == NULL) - return; - - memset(new_nodes, 0x0, new_size * sizeof(git_revpool_node *)); - - for (i = 0; i <= table->size_mask; ++i) { - git_revpool_node *n; - unsigned int index; - - while ((n = table->nodes[i]) != NULL) { - table->nodes[i] = n->next; - index = n->hash & (new_size - 1); - n->next = new_nodes[index]; - new_nodes[index] = n; - } - } - - free(table->nodes); - table->nodes = new_nodes; - table->size_mask = (new_size - 1); - table->max_count = (unsigned int)(new_size * max_load_factor); -} -void git_revpool_table_free(git_revpool_table *table) +void git_hashtable_iterator_init(git_hashtable *table, git_hashtable_iterator *it) { - unsigned int index; - - for (index = 0; index <= table->size_mask; ++index) { - git_revpool_node *node, *next_node; - - node = table->nodes[index]; - while (node != NULL) { - next_node = node->next; - free(node); - node = next_node; - } - } - - free(table->nodes); - free(table); -} + assert(table && it); -void git_revpool_tableit_init(git_revpool_table *table, git_revpool_tableit *it) -{ - memset(it, 0x0, sizeof(git_revpool_tableit)); + memset(it, 0x0, sizeof(git_hashtable_iterator)); it->nodes = table->nodes; it->current_node = NULL; @@ -181,9 +197,11 @@ void git_revpool_tableit_init(git_revpool_table *table, git_revpool_tableit *it) it->size = table->size_mask + 1; } -git_revpool_object *git_revpool_tableit_next(git_revpool_tableit *it) +void *git_hashtable_iterator_next(git_hashtable_iterator *it) { - git_revpool_node *next = NULL; + git_hashtable_node *next = NULL; + + assert(it); while (it->current_node == NULL) { if (it->current_pos >= it->size) @@ -198,13 +216,3 @@ git_revpool_object *git_revpool_tableit_next(git_revpool_tableit *it) return next->object; } -git_revpool_object *git_revpool_tableit_nextfilter(git_revpool_tableit *it, git_otype type) -{ - git_revpool_object *obj; - - do { - obj = git_revpool_tableit_next(it); - } while (obj != NULL && obj->type != type); - - return obj; -} diff --git a/src/hashtable.h b/src/hashtable.h new file mode 100644 index 000000000..622a260e1 --- /dev/null +++ b/src/hashtable.h @@ -0,0 +1,51 @@ +#ifndef INCLUDE_hashtable_h__ +#define INCLUDE_hashtable_h__ + +#include "git/common.h" +#include "git/oid.h" +#include "git/odb.h" + + +typedef uint32_t (*git_hash_ptr)(const void *); +typedef int (*git_hash_keyeq_ptr)(void *obj, const void *obj_key); + +struct git_hashtable_node { + void *object; + uint32_t hash; + struct git_hashtable_node *next; +}; + +struct git_hashtable { + struct git_hashtable_node **nodes; + + unsigned int size_mask; + unsigned int count; + unsigned int max_count; + + git_hash_ptr hash; + git_hash_keyeq_ptr key_equal; +}; + +struct git_hashtable_iterator { + struct git_hashtable_node **nodes; + struct git_hashtable_node *current_node; + unsigned int current_pos; + unsigned int size; +}; + +typedef struct git_hashtable_node git_hashtable_node; +typedef struct git_hashtable git_hashtable; +typedef struct git_hashtable_iterator git_hashtable_iterator; + +git_hashtable *git_hashtable_alloc(unsigned int min_size, + git_hash_ptr hash, + git_hash_keyeq_ptr key_eq); +int git_hashtable_insert(git_hashtable *h, const void *key, void *value); +void *git_hashtable_lookup(git_hashtable *h, const void *key); +void git_hashtable_free(git_hashtable *h); +void git_hashtable_clear(git_hashtable *h); + +void *git_hashtable_iterator_next(git_hashtable_iterator *it); +void git_hashtable_iterator_init(git_hashtable *h, git_hashtable_iterator *it); + +#endif diff --git a/src/repository.c b/src/repository.c new file mode 100644 index 000000000..dd5b5f70f --- /dev/null +++ b/src/repository.c @@ -0,0 +1,143 @@ +/* + * This file is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License, version 2, + * as published by the Free Software Foundation. + * + * In addition to the permissions in the GNU General Public License, + * the authors give you unlimited permission to link the compiled + * version of this file into combinations with other programs, + * and to distribute those combinations without any restriction + * coming from the use of this file. (The General Public License + * restrictions do apply in other respects; for example, they cover + * modification of the file, and distribution when not linked into + * a combined executable.) + * + * This file is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; see the file COPYING. If not, write to + * the Free Software Foundation, 51 Franklin Street, Fifth Floor, + * Boston, MA 02110-1301, USA. + */ + +#include "common.h" +#include "repository.h" +#include "commit.h" +#include "tag.h" + +static const int default_table_size = 32; +static const double max_load_factor = 0.65; + +uint32_t git_repository_object_hash(const void *key) +{ + uint32_t r; + git_oid *id; + + id = (git_oid *)key; + memcpy(&r, id->id, sizeof(r)); + return r; +} + +int git_repository_object_haskey(void *object, const void *key) +{ + git_repository_object *obj; + git_oid *oid; + + obj = (git_repository_object *)object; + oid = (git_oid *)key; + + return (git_oid_cmp(oid, &obj->id) == 0); +} + +git_repository *git_repository_alloc(git_odb *odb) +{ + git_repository *repo = git__malloc(sizeof(git_repository)); + if (!repo) + return NULL; + + memset(repo, 0x0, sizeof(git_repository)); + + repo->objects = git_hashtable_alloc( + default_table_size, + git_repository_object_hash, + git_repository_object_haskey); + + if (repo->objects == NULL) { + free(repo); + return NULL; + } + + repo->db = odb; /* TODO: create ODB manually! */ + + return repo; +} + +void git_repository_free(git_repository *repo) +{ + git_hashtable_iterator it; + git_repository_object *object; + + git_hashtable_iterator_init(repo->objects, &it); + + while ((object = (git_repository_object *) + git_hashtable_iterator_next(&it)) != NULL) { + + switch (object->type) { + case GIT_OBJ_COMMIT: + git_commit__free((git_commit *)object); + break; + + case GIT_OBJ_TREE: + git_tree__free((git_tree *)object); + break; + + case GIT_OBJ_TAG: + git_tag__free((git_tag *)object); + break; + + default: + free(object); + break; + } + } + + git_hashtable_free(repo->objects); + /* TODO: free odb */ + free(repo); +} + +git_repository_object *git_repository_lookup(git_repository *repo, const git_oid *id, git_otype type) +{ + git_repository_object *object = NULL; + git_obj obj_file; + + assert(repo); + + object = git_hashtable_lookup(repo->objects, id); + if (object != NULL) + return object; + + if (git_odb_read(&obj_file, repo->db, id) < 0 || + (type != GIT_OBJ_ANY && type != obj_file.type)) + return NULL; + + object = git__malloc(sizeof(git_commit)); + + if (object == NULL) + return NULL; + + memset(object, 0x0, sizeof(git_commit)); + + /* Initialize parent object */ + git_oid_cpy(&object->id, id); + object->repo = repo; + object->type = obj_file.type; + + git_hashtable_insert(repo->objects, &object->id, object); + git_obj_close(&obj_file); + + return object; +} diff --git a/src/repository.h b/src/repository.h new file mode 100644 index 000000000..5db598765 --- /dev/null +++ b/src/repository.h @@ -0,0 +1,25 @@ +#ifndef INCLUDE_repository_h__ +#define INCLUDE_repository_h__ + +#include "git/common.h" +#include "git/oid.h" +#include "git/odb.h" +#include "git/repository.h" + +#include "hashtable.h" + +struct git_repository_object { + git_oid id; + git_repository *repo; + git_otype type; +}; + +struct git_repository { + git_odb *db; + git_hashtable *objects; +}; + +int git_repository__insert(git_repository *repo, git_repository_object *obj); +git_repository_object *git_repository__lookup(git_repository *repo, const git_oid *id); + +#endif diff --git a/src/revobject.h b/src/revobject.h deleted file mode 100644 index d76d8a639..000000000 --- a/src/revobject.h +++ /dev/null @@ -1,52 +0,0 @@ -#ifndef INCLUDE_objecttable_h__ -#define INCLUDE_objecttable_h__ - -#include "git/common.h" -#include "git/oid.h" -#include "git/odb.h" - -struct git_revpool_object { - git_oid id; - git_revpool *pool; - git_otype type; -}; - -struct git_revpool_node { - struct git_revpool_object *object; - unsigned int hash; - struct git_revpool_node *next; -}; - -struct git_revpool_table { - struct git_revpool_node **nodes; - - unsigned int size_mask; - unsigned int count; - unsigned int max_count; -}; - -struct git_revpool_tableit { - struct git_revpool_node **nodes; - struct git_revpool_node *current_node; - unsigned int current_pos; - unsigned int size; -}; - - -typedef struct git_revpool_node git_revpool_node; -typedef struct git_revpool_object git_revpool_object; -typedef struct git_revpool_table git_revpool_table; -typedef struct git_revpool_tableit git_revpool_tableit; - -git_revpool_table *git_revpool_table_create(unsigned int min_size); -int git_revpool_table_insert(git_revpool_table *table, git_revpool_object *object); -git_revpool_object *git_revpool_table_lookup(git_revpool_table *table, const git_oid *id); -void git_revpool_table_resize(git_revpool_table *table); -void git_revpool_table_free(git_revpool_table *table); - - -git_revpool_object *git_revpool_tableit_next(git_revpool_tableit *it); -git_revpool_object *git_revpool_tableit_nextfilter(git_revpool_tableit *it, git_otype type); -void git_revpool_tableit_init(git_revpool_table *table, git_revpool_tableit *it); - -#endif diff --git a/src/revwalk.c b/src/revwalk.c index d4627ae2e..ca008849a 100644 --- a/src/revwalk.c +++ b/src/revwalk.c @@ -26,187 +26,417 @@ #include "common.h" #include "commit.h" #include "revwalk.h" +#include "hashtable.h" -static const int default_table_size = 32; +uint32_t git_revwalk_commit_hash(const void *key) +{ + uint32_t r; + git_commit *commit; -git_revpool *gitrp_alloc(git_odb *db) + commit = (git_commit *)key; + memcpy(&r, commit->object.id.id, sizeof(r)); + return r; +} + +int git_revwalk_commit_haskey(void *object, const void *key) { - git_revpool *walk = git__malloc(sizeof(*walk)); - if (!walk) + git_revwalk_commit *walk_commit; + git_commit *commit_object; + + walk_commit = (git_revwalk_commit *)object; + commit_object = (git_commit *)key; + + return (walk_commit->commit_object == commit_object); +} + + +git_revwalk *git_revwalk_alloc(git_repository *repo) +{ + git_revwalk *walk; + + walk = git__malloc(sizeof(git_revwalk)); + if (walk == NULL) return NULL; - memset(walk, 0x0, sizeof(git_revpool)); + memset(walk, 0x0, sizeof(git_revwalk)); - walk->objects = git_revpool_table_create(default_table_size); + walk->commits = git_hashtable_alloc(64, + git_revwalk_commit_hash, + git_revwalk_commit_haskey); + + if (walk->commits == NULL) { + free(walk); + return NULL; + } - walk->db = db; + walk->repo = repo; return walk; } -void gitrp_free(git_revpool *walk) +void git_revwalk_free(git_revwalk *walk) { - git_revpool_object *obj; - git_revpool_tableit it; + git_revwalk_reset(walk); + git_hashtable_free(walk->commits); + free(walk); +} - git_commit_list_clear(&(walk->iterator), 0); - git_commit_list_clear(&(walk->roots), 0); +void git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode) +{ + if (walk->walking) + return; - git_revpool_tableit_init(walk->objects, &it); + walk->sorting = sort_mode; + git_revwalk_reset(walk); +} - while ((obj = git_revpool_tableit_next(&it)) != NULL) { - switch (obj->type) { +static git_revwalk_commit *commit_to_walkcommit(git_revwalk *walk, git_commit *commit_object) +{ + git_revwalk_commit *commit; - case GIT_OBJ_COMMIT: - git_commit__free((git_commit *)obj); - break; + commit = (git_revwalk_commit *)git_hashtable_lookup(walk->commits, commit_object); - case GIT_OBJ_TREE: - git_tree__free((git_tree *)obj); - break; + if (commit != NULL) + return commit; - default: - free(obj); - break; - } + if (!commit_object->basic_parse) { + if (git_commit__parse_basic(commit_object) < 0) + return NULL; } - git_revpool_table_free(walk->objects); + commit = git__malloc(sizeof(git_revwalk_commit)); + if (commit == NULL) + return NULL; - free(walk); + memset(commit, 0x0, sizeof(git_revwalk_commit)); + + commit->commit_object = commit_object; + + git_hashtable_insert(walk->commits, commit_object, commit); + + return commit; } -void gitrp_sorting(git_revpool *pool, unsigned int sort_mode) +static git_revwalk_commit *insert_commit(git_revwalk *walk, git_commit *commit_object) { - if (pool->walking) - return; + git_revwalk_commit *commit; + git_commit_parents *parents; + + assert(walk && commit_object); + + if (commit_object->object.repo != walk->repo || walk->walking) + return NULL; + + commit = commit_to_walkcommit(walk, commit_object); + if (commit == NULL) + return NULL; - pool->sorting = sort_mode; - gitrp_reset(pool); + if (commit->seen) + return commit; + + commit->seen = 1; + + assert(commit->commit_object->basic_parse); + + for (parents = commit->commit_object->parents; parents != NULL; parents = parents->next) { + git_revwalk_commit *parent; + + if ((parent = commit_to_walkcommit(walk, parents->commit)) == NULL) + return NULL; + + parent = insert_commit(walk, parents->commit); + if (parent == NULL) + return NULL; + + parent->in_degree++; + + git_revwalk_list_push_back(&commit->parents, parent); + } + + if (git_revwalk_list_push_back(&walk->iterator, commit)) + return NULL; + + return commit; } -int gitrp_push(git_revpool *pool, git_commit *commit) +int git_revwalk_push(git_revwalk *walk, git_commit *commit) { - if (commit == NULL || commit->seen) - return GIT_ENOTFOUND; + return insert_commit(walk, commit) ? GIT_SUCCESS : GIT_ERROR; +} - if (commit->object.pool != pool || pool->walking) - return GIT_ERROR; +static void mark_uninteresting(git_revwalk_commit *commit) +{ + git_revwalk_listnode *parent; + + if (commit == NULL) + return; - if (!commit->basic_parse) { - int error = git_commit__parse_basic(commit); + commit->uninteresting = 1; + parent = commit->parents.head; - if (error < 0) - return error; + while (parent) { + mark_uninteresting(parent->walk_commit); + parent = parent->next; } +} + +int git_revwalk_hide(git_revwalk *walk, git_commit *commit) +{ + git_revwalk_commit *hide; + + hide = insert_commit(walk, commit); + if (hide == NULL) + return GIT_ERROR; - /* - * Sanity check: make sure that if the commit - * has been manually marked as uninteresting, - * all the parent commits are too. - */ - if (commit->uninteresting) - git_commit__mark_uninteresting(commit); + mark_uninteresting(hide); + return GIT_SUCCESS; +} - if (git_commit_list_push_back(&pool->roots, commit) < 0) - return GIT_ENOMEM; - return 0; +static void prepare_walk(git_revwalk *walk) +{ + if (walk->sorting & GIT_SORT_TIME) + git_revwalk_list_timesort(&walk->iterator); + + if (walk->sorting & GIT_SORT_TOPOLOGICAL) + git_revwalk_list_toposort(&walk->iterator); + + if (walk->sorting & GIT_SORT_REVERSE) + walk->next = &git_revwalk_list_pop_back; + else + walk->next = &git_revwalk_list_pop_front; + + walk->walking = 1; } -int gitrp_hide(git_revpool *pool, git_commit *commit) +git_commit *git_revwalk_next(git_revwalk *walk) { - if (pool->walking) - return GIT_ERROR; + git_revwalk_commit *next; - git_commit__mark_uninteresting(commit); - return gitrp_push(pool, commit); + if (!walk->walking) + prepare_walk(walk); + + while ((next = walk->next(&walk->iterator)) != NULL) { + if (!next->uninteresting) + return next->commit_object; + } + + /* No commits left to iterate */ + git_revwalk_reset(walk); + return NULL; } -int gitrp__enroot(git_revpool *pool, git_commit *commit) +void git_revwalk_reset(git_revwalk *walk) { - int error; - git_commit_node *parents; + git_hashtable_iterator it; + git_revwalk_commit *commit; - if (commit->seen) - return 0; + git_hashtable_iterator_init(walk->commits, &it); - if (!commit->basic_parse) { - error = git_commit__parse_basic(commit); - if (error < 0) - return error; + while ((commit = (git_revwalk_commit *) + git_hashtable_iterator_next(&it)) != NULL) { + git_revwalk_list_clear(&commit->parents); + free(commit); } - commit->seen = 1; + git_hashtable_clear(walk->commits); + git_revwalk_list_clear(&walk->iterator); + walk->walking = 0; +} + + + + + + +int git_revwalk_list_push_back(git_revwalk_list *list, git_revwalk_commit *commit) +{ + git_revwalk_listnode *node = NULL; + + node = git__malloc(sizeof(git_revwalk_listnode)); + + if (node == NULL) + return GIT_ENOMEM; - for (parents = commit->parents.head; parents != NULL; parents = parents->next) { - parents->commit->in_degree++; + node->walk_commit = commit; + node->next = NULL; + node->prev = list->tail; - error = gitrp__enroot(pool, parents->commit); - if (error < 0) - return error; + if (list->tail == NULL) { + list->head = list->tail = node; + } else { + list->tail->next = node; + list->tail = node; } - if (git_commit_list_push_back(&pool->iterator, commit)) + list->size++; + return 0; +} + +int git_revwalk_list_push_front(git_revwalk_list *list, git_revwalk_commit *commit) +{ + git_revwalk_listnode *node = NULL; + + node = git__malloc(sizeof(git_revwalk_listnode)); + + if (node == NULL) return GIT_ENOMEM; + node->walk_commit = commit; + node->next = list->head; + node->prev = NULL; + + if (list->head == NULL) { + list->head = list->tail = node; + } else { + list->head->prev = node; + list->head = node; + } + + list->size++; return 0; } -void gitrp__prepare_walk(git_revpool *pool) + +git_revwalk_commit *git_revwalk_list_pop_back(git_revwalk_list *list) { - git_commit_node *it; + git_revwalk_listnode *node; + git_revwalk_commit *commit; - for (it = pool->roots.head; it != NULL; it = it->next) - gitrp__enroot(pool, it->commit); + if (list->tail == NULL) + return NULL; - if (pool->sorting & GIT_RPSORT_TIME) - git_commit_list_timesort(&pool->iterator); + node = list->tail; + list->tail = list->tail->prev; + if (list->tail == NULL) + list->head = NULL; - if (pool->sorting & GIT_RPSORT_TOPOLOGICAL) - git_commit_list_toposort(&pool->iterator); + commit = node->walk_commit; + free(node); - if (pool->sorting & GIT_RPSORT_REVERSE) - pool->next_commit = &git_commit_list_pop_back; - else - pool->next_commit = &git_commit_list_pop_front; + list->size--; - pool->walking = 1; + return commit; } -git_commit *gitrp_next(git_revpool *pool) +git_revwalk_commit *git_revwalk_list_pop_front(git_revwalk_list *list) { - git_commit *next; + git_revwalk_listnode *node; + git_revwalk_commit *commit; + + if (list->head == NULL) + return NULL; - if (!pool->walking) - gitrp__prepare_walk(pool); + node = list->head; + list->head = list->head->next; + if (list->head == NULL) + list->tail = NULL; - while ((next = pool->next_commit(&pool->iterator)) != NULL) { - if (!next->uninteresting) - return next; + commit = node->walk_commit; + free(node); + + list->size--; + + return commit; +} + +void git_revwalk_list_clear(git_revwalk_list *list) +{ + git_revwalk_listnode *node, *next_node; + + node = list->head; + while (node) { + next_node = node->next; + free(node); + node = next_node; } - /* No commits left to iterate */ - gitrp_reset(pool); - return NULL; + list->head = list->tail = NULL; + list->size = 0; } -void gitrp_reset(git_revpool *pool) +void git_revwalk_list_timesort(git_revwalk_list *list) { - git_commit *commit; - git_revpool_tableit it; + git_revwalk_listnode *p, *q, *e; + int in_size, p_size, q_size, merge_count, i; + + if (list->head == NULL) + return; + + in_size = 1; + + do { + p = list->head; + list->tail = NULL; + merge_count = 0; + + while (p != NULL) { + merge_count++; + q = p; + p_size = 0; + q_size = in_size; + + for (i = 0; i < in_size && q; ++i, q = q->next) + p_size++; + + while (p_size > 0 || (q_size > 0 && q)) { - git_revpool_tableit_init(pool->objects, &it); + if (p_size == 0) + e = q, q = q->next, q_size--; - while ((commit = - (git_commit *)git_revpool_tableit_nextfilter( - &it, GIT_OBJ_COMMIT)) != NULL) { + else if (q_size == 0 || q == NULL || + p->walk_commit->commit_object->commit_time >= + q->walk_commit->commit_object->commit_time) + e = p, p = p->next, p_size--; + + else + e = q, q = q->next, q_size--; + + if (list->tail != NULL) + list->tail->next = e; + else + list->head = e; + + e->prev = list->tail; + list->tail = e; + } + + p = q; + } + + list->tail->next = NULL; + in_size *= 2; + + } while (merge_count > 1); +} + +void git_revwalk_list_toposort(git_revwalk_list *list) +{ + git_revwalk_commit *commit; + git_revwalk_list topo; + memset(&topo, 0x0, sizeof(git_revwalk_list)); + + while ((commit = git_revwalk_list_pop_back(list)) != NULL) { + git_revwalk_listnode *p; + + if (commit->in_degree > 0) { + commit->topo_delay = 1; + continue; + } + + for (p = commit->parents.head; p != NULL; p = p->next) { + p->walk_commit->in_degree--; + + if (p->walk_commit->in_degree == 0 && p->walk_commit->topo_delay) { + p->walk_commit->topo_delay = 0; + git_revwalk_list_push_back(list, p->walk_commit); + } + } - commit->seen = 0; - commit->topo_delay = 0; - commit->in_degree = 0; + git_revwalk_list_push_back(&topo, commit); } - git_commit_list_clear(&pool->iterator, 0); - pool->walking = 0; + list->head = topo.head; + list->tail = topo.tail; + list->size = topo.size; } diff --git a/src/revwalk.h b/src/revwalk.h index 270eb8c6b..d97e5ce8c 100644 --- a/src/revwalk.h +++ b/src/revwalk.h @@ -5,21 +5,63 @@ #include "git/revwalk.h" #include "commit.h" +#include "repository.h" +#include "hashtable.h" -struct git_revpool { - git_odb *db; +struct git_revwalk_commit; - git_commit_list iterator; - git_commit *(*next_commit)(git_commit_list *); +typedef struct git_revwalk_listnode { + struct git_revwalk_commit *walk_commit; + struct git_revwalk_listnode *next; + struct git_revwalk_listnode *prev; +} git_revwalk_listnode; - git_commit_list roots; - git_revpool_table *objects; +typedef struct git_revwalk_list { + struct git_revwalk_listnode *head; + struct git_revwalk_listnode *tail; + size_t size; +} git_revwalk_list; + + +struct git_revwalk_commit { + + git_commit *commit_object; + git_revwalk_list parents; + + unsigned short in_degree; + unsigned seen:1, + uninteresting:1, + topo_delay:1, + flags:25; +}; + +typedef struct git_revwalk_commit git_revwalk_commit; + +struct git_revwalk { + git_repository *repo; + + git_hashtable *commits; + git_revwalk_list iterator; + + git_revwalk_commit *(*next)(git_revwalk_list *); unsigned walking:1; unsigned int sorting; }; -void gitrp__prepare_walk(git_revpool *pool); -int gitrp__enroot(git_revpool *pool, git_commit *commit); + +void git_revwalk__prepare_walk(git_revwalk *walk); +int git_revwalk__enroot(git_revwalk *walk, git_commit *commit); + +int git_revwalk_list_push_back(git_revwalk_list *list, git_revwalk_commit *commit); +int git_revwalk_list_push_front(git_revwalk_list *list, git_revwalk_commit *obj); + +git_revwalk_commit *git_revwalk_list_pop_back(git_revwalk_list *list); +git_revwalk_commit *git_revwalk_list_pop_front(git_revwalk_list *list); + +void git_revwalk_list_clear(git_revwalk_list *list); + +void git_revwalk_list_timesort(git_revwalk_list *list); +void git_revwalk_list_toposort(git_revwalk_list *list); #endif /* INCLUDE_revwalk_h__ */ @@ -28,7 +28,7 @@ #include "tag.h" #include "revwalk.h" #include "git/odb.h" - +#include "git/repository.h" void git_tag__free(git_tag *tag) { @@ -43,7 +43,7 @@ const git_oid *git_tag_id(git_tag *t) return &t->object.id; } -const git_revpool_object *git_tag_target(git_tag *t) +const git_repository_object *git_tag_target(git_tag *t) { if (t->target) return t->target; @@ -183,7 +183,7 @@ int git_tag__parse(git_tag *tag) int error = 0; git_obj odb_object; - error = git_odb_read(&odb_object, tag->object.pool->db, &tag->object.id); + error = git_odb_read(&odb_object, tag->object.repo->db, &tag->object.id); if (error < 0) return error; @@ -199,30 +199,7 @@ cleanup: return error; } -git_tag *git_tag_lookup(git_revpool *pool, const git_oid *id) +git_tag *git_tag_lookup(git_repository *repo, const git_oid *id) { - git_tag *tag = NULL; - - if (pool == NULL) - return NULL; - - tag = (git_tag *)git_revpool_table_lookup(pool->objects, id); - if (tag != NULL) - return tag; - - tag = git__malloc(sizeof(git_tag)); - - if (tag == NULL) - return NULL; - - memset(tag, 0x0, sizeof(git_tag)); - - /* Initialize parent object */ - git_oid_cpy(&tag->object.id, id); - tag->object.pool = pool; - tag->object.type = GIT_OBJ_TAG; - - git_revpool_table_insert(pool->objects, (git_revpool_object *)tag); - - return tag; + return (git_tag *)git_repository_lookup(repo, id, GIT_OBJ_TAG); } @@ -2,12 +2,12 @@ #define INCLUDE_tag_h__ #include "git/tag.h" -#include "revobject.h" +#include "repository.h" struct git_tag { - git_revpool_object object; + git_repository_object object; - git_revpool_object *target; + git_repository_object *target; git_otype type; char *tag_name; git_person *tagger; diff --git a/src/tree.c b/src/tree.c index 47b027322..15603e7a9 100644 --- a/src/tree.c +++ b/src/tree.c @@ -27,6 +27,7 @@ #include "commit.h" #include "revwalk.h" #include "tree.h" +#include "git/repository.h" void git_tree__free(git_tree *tree) { @@ -38,51 +39,9 @@ const git_oid *git_tree_id(git_tree *tree) return &tree->object.id; } -git_tree *git_tree_lookup(git_revpool *pool, const git_oid *id) +git_tree *git_tree_lookup(git_repository *repo, const git_oid *id) { - git_tree *tree = NULL; - - if (pool == NULL) - return NULL; - - tree = (git_tree *)git_revpool_table_lookup(pool->objects, id); - if (tree != NULL) - return tree; - - tree = git__malloc(sizeof(git_tree)); - - if (tree == NULL) - return NULL; - - memset(tree, 0x0, sizeof(git_tree)); - - /* Initialize parent object */ - git_oid_cpy(&tree->object.id, id); - tree->object.pool = pool; - tree->object.type = GIT_OBJ_TREE; - - git_revpool_table_insert(pool->objects, (git_revpool_object *)tree); - - return tree; -} - - -git_tree *git_tree_parse(git_revpool *pool, const git_oid *id) -{ - git_tree *tree = NULL; - - if ((tree = git_tree_lookup(pool, id)) == NULL) - return NULL; - - if (git_tree__parse(tree) < 0) - goto error_cleanup; - - return tree; - -error_cleanup: - /* FIXME: do not free; the tree is owned by the revpool */ - free(tree); - return NULL; + return (git_tree *)git_repository_lookup(repo, id, GIT_OBJ_TREE); } int git_tree__parse(git_tree *tree) @@ -93,7 +52,7 @@ int git_tree__parse(git_tree *tree) git_obj odb_object; char *buffer, *buffer_end; - error = git_odb_read(&odb_object, tree->object.pool->db, &tree->object.id); + error = git_odb_read(&odb_object, tree->object.repo->db, &tree->object.id); if (error < 0) return error; diff --git a/src/tree.h b/src/tree.h index 373345663..f21668586 100644 --- a/src/tree.h +++ b/src/tree.h @@ -2,7 +2,7 @@ #define INCLUDE_tree_h__ #include <git/tree.h> -#include "revobject.h" +#include "repository.h" struct git_tree_entry { @@ -16,7 +16,7 @@ struct git_tree_entry { typedef struct git_tree_entry git_tree_entry; struct git_tree { - git_revpool_object object; + git_repository_object object; size_t byte_size; git_tree_entry *entries; |