blob: 3b7ad34e6a34e0151d6798897b1b36cb73f47fe9 [file] [log] [blame]
/*
* 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 "commit.h"
#include "hashtable.h"
#include "pqueue.h"
#include "git2/revwalk.h"
typedef struct commit_object {
git_oid oid;
uint32_t time;
unsigned int seen:1,
uninteresting:1,
topo_delay:1,
parsed:1;
unsigned short in_degree;
unsigned short out_degree;
struct commit_object **parents;
} commit_object;
typedef struct commit_list {
commit_object *item;
struct commit_list *next;
} commit_list;
struct git_revwalk {
git_repository *repo;
git_hashtable *commits;
commit_list *iterator_topo;
commit_list *iterator_rand;
commit_list *iterator_reverse;
git_pqueue iterator_time;
int (*get_next)(commit_object **, git_revwalk *);
int (*enqueue)(git_revwalk *, commit_object *);
git_vector memory_alloc;
size_t chunk_size;
unsigned walking:1;
unsigned int sorting;
};
commit_list *commit_list_insert(commit_object *item, commit_list **list_p)
{
commit_list *new_list = git__malloc(sizeof(commit_list));
new_list->item = item;
new_list->next = *list_p;
*list_p = new_list;
return new_list;
}
void commit_list_free(commit_list **list_p)
{
commit_list *list = *list_p;
while (list) {
commit_list *temp = list;
list = temp->next;
free(temp);
}
*list_p = NULL;
}
commit_object *commit_list_pop(commit_list **stack)
{
commit_list *top = *stack;
commit_object *item = top ? top->item : NULL;
if (top) {
*stack = top->next;
free(top);
}
return item;
}
static int commit_time_cmp(void *a, void *b)
{
commit_object *commit_a = (commit_object *)a;
commit_object *commit_b = (commit_object *)b;
return (commit_a->time < commit_b->time);
}
static uint32_t object_table_hash(const void *key, int hash_id)
{
uint32_t r;
git_oid *id;
id = (git_oid *)key;
memcpy(&r, id->id + (hash_id * sizeof(uint32_t)), sizeof(r));
return r;
}
#define COMMITS_PER_CHUNK 128
#define CHUNK_STEP 64
#define PARENTS_PER_COMMIT ((CHUNK_STEP - sizeof(commit_object)) / sizeof(commit_object *))
static int alloc_chunk(git_revwalk *walk)
{
void *chunk;
chunk = git__calloc(COMMITS_PER_CHUNK, CHUNK_STEP);
if (chunk == NULL)
return GIT_ENOMEM;
walk->chunk_size = 0;
return git_vector_insert(&walk->memory_alloc, chunk);
}
static commit_object *alloc_commit(git_revwalk *walk)
{
unsigned char *chunk;
if (walk->chunk_size == COMMITS_PER_CHUNK)
alloc_chunk(walk);
chunk = git_vector_get(&walk->memory_alloc, walk->memory_alloc.length - 1);
chunk += (walk->chunk_size * CHUNK_STEP);
walk->chunk_size++;
return (commit_object *)chunk;
}
static commit_object **alloc_parents(commit_object *commit, size_t n_parents)
{
if (n_parents <= PARENTS_PER_COMMIT)
return (commit_object **)((unsigned char *)commit + sizeof(commit_object));
return git__malloc(n_parents * sizeof(commit_object *));
}
static commit_object *commit_lookup(git_revwalk *walk, const git_oid *oid)
{
commit_object *commit;
if ((commit = git_hashtable_lookup(walk->commits, oid)) != NULL)
return commit;
commit = alloc_commit(walk);
if (commit == NULL)
return NULL;
git_oid_cpy(&commit->oid, oid);
if (git_hashtable_insert(walk->commits, &commit->oid, commit) < GIT_SUCCESS) {
free(commit);
return NULL;
}
return commit;
}
static int commit_quick_parse(git_revwalk *walk, commit_object *commit, git_rawobj *raw)
{
const int parent_len = STRLEN("parent ") + GIT_OID_HEXSZ + 1;
unsigned char *buffer = raw->data;
unsigned char *buffer_end = buffer + raw->len;
unsigned char *parents_start;
int i, parents = 0;
buffer += STRLEN("tree ") + GIT_OID_HEXSZ + 1;
parents_start = buffer;
while (buffer + parent_len < buffer_end && memcmp(buffer, "parent ", STRLEN("parent ")) == 0) {
parents++;
buffer += parent_len;
}
commit->parents = alloc_parents(commit, parents);
if (commit->parents == NULL)
return GIT_ENOMEM;
buffer = parents_start;
for (i = 0; i < parents; ++i) {
git_oid oid;
if (git_oid_mkstr(&oid, (char *)buffer + STRLEN("parent ")) < GIT_SUCCESS)
return GIT_EOBJCORRUPTED;
commit->parents[i] = commit_lookup(walk, &oid);
if (commit->parents[i] == NULL)
return GIT_ENOMEM;
buffer += parent_len;
}
commit->out_degree = (unsigned short)parents;
if ((buffer = memchr(buffer, '\n', buffer_end - buffer)) == NULL)
return GIT_EOBJCORRUPTED;
buffer = memchr(buffer, '>', buffer_end - buffer);
if (buffer == NULL)
return GIT_EOBJCORRUPTED;
commit->time = strtol((char *)buffer + 2, NULL, 10);
if (commit->time == 0)
return GIT_EOBJCORRUPTED;
commit->parsed = 1;
return GIT_SUCCESS;
}
static int commit_parse(git_revwalk *walk, commit_object *commit)
{
git_rawobj data;
int error;
if (commit->parsed)
return GIT_SUCCESS;
if ((error = git_odb_read(&data, walk->repo->db, &commit->oid)) < GIT_SUCCESS)
return error;
if (data.type != GIT_OBJ_COMMIT) {
git_rawobj_close(&data);
return GIT_EOBJTYPE;
}
error = commit_quick_parse(walk, commit, &data);
git_rawobj_close(&data);
return error;
}
static void mark_uninteresting(commit_object *commit)
{
unsigned short i;
assert(commit);
commit->uninteresting = 1;
for (i = 0; i < commit->out_degree; ++i)
if (!commit->parents[i]->uninteresting)
mark_uninteresting(commit->parents[i]);
}
static int process_commit(git_revwalk *walk, commit_object *commit)
{
int error;
if (commit->seen)
return GIT_SUCCESS;
commit->seen = 1;
if ((error = commit_parse(walk, commit)) < GIT_SUCCESS)
return error;
if (commit->uninteresting)
mark_uninteresting(commit);
return walk->enqueue(walk, commit);
}
static int process_commit_parents(git_revwalk *walk, commit_object *commit)
{
unsigned short i;
int error = GIT_SUCCESS;
for (i = 0; i < commit->out_degree && error == GIT_SUCCESS; ++i) {
error = process_commit(walk, commit->parents[i]);
}
return error;
}
static int push_commit(git_revwalk *walk, const git_oid *oid, int uninteresting)
{
commit_object *commit;
commit = commit_lookup(walk, oid);
if (commit == NULL)
return GIT_ENOTFOUND;
commit->uninteresting = uninteresting;
return process_commit(walk, commit);
}
int git_revwalk_push(git_revwalk *walk, const git_oid *oid)
{
assert(walk && oid);
return push_commit(walk, oid, 0);
}
int git_revwalk_hide(git_revwalk *walk, const git_oid *oid)
{
assert(walk && oid);
return push_commit(walk, oid, 1);
}
static int revwalk_enqueue_timesort(git_revwalk *walk, commit_object *commit)
{
return git_pqueue_insert(&walk->iterator_time, commit);
}
static int revwalk_enqueue_unsorted(git_revwalk *walk, commit_object *commit)
{
return commit_list_insert(commit, &walk->iterator_rand) ? GIT_SUCCESS : GIT_ENOMEM;
}
static int revwalk_next_timesort(commit_object **object_out, git_revwalk *walk)
{
int error;
commit_object *next;
while ((next = git_pqueue_pop(&walk->iterator_time)) != NULL) {
if ((error = process_commit_parents(walk, next)) < GIT_SUCCESS)
return error;
if (!next->uninteresting) {
*object_out = next;
return GIT_SUCCESS;
}
}
return GIT_EREVWALKOVER;
}
static int revwalk_next_unsorted(commit_object **object_out, git_revwalk *walk)
{
int error;
commit_object *next;
while ((next = commit_list_pop(&walk->iterator_rand)) != NULL) {
if ((error = process_commit_parents(walk, next)) < GIT_SUCCESS)
return error;
if (!next->uninteresting) {
*object_out = next;
return GIT_SUCCESS;
}
}
return GIT_EREVWALKOVER;
}
static int revwalk_next_toposort(commit_object **object_out, git_revwalk *walk)
{
commit_object *next;
unsigned short i;
for (;;) {
next = commit_list_pop(&walk->iterator_topo);
if (next == NULL)
return GIT_EREVWALKOVER;
if (next->in_degree > 0) {
next->topo_delay = 1;
continue;
}
for (i = 0; i < next->out_degree; ++i) {
commit_object *parent = next->parents[i];
if (--parent->in_degree == 0 && parent->topo_delay) {
parent->topo_delay = 0;
commit_list_insert(parent, &walk->iterator_topo);
}
}
*object_out = next;
return GIT_SUCCESS;
}
}
static int revwalk_next_reverse(commit_object **object_out, git_revwalk *walk)
{
*object_out = commit_list_pop(&walk->iterator_reverse);
return *object_out ? GIT_SUCCESS : GIT_EREVWALKOVER;
}
static int prepare_walk(git_revwalk *walk)
{
int error;
commit_object *next;
if (walk->sorting & GIT_SORT_TOPOLOGICAL) {
unsigned short i;
while ((error = walk->get_next(&next, walk)) == GIT_SUCCESS) {
for (i = 0; i < next->out_degree; ++i) {
commit_object *parent = next->parents[i];
parent->in_degree++;
}
commit_list_insert(next, &walk->iterator_topo);
}
if (error != GIT_EREVWALKOVER)
return error;
walk->get_next = &revwalk_next_toposort;
}
if (walk->sorting & GIT_SORT_REVERSE) {
while ((error = walk->get_next(&next, walk)) == GIT_SUCCESS)
commit_list_insert(next, &walk->iterator_reverse);
if (error != GIT_EREVWALKOVER)
return error;
walk->get_next = &revwalk_next_reverse;
}
walk->walking = 1;
return GIT_SUCCESS;
}
int git_revwalk_new(git_revwalk **revwalk_out, git_repository *repo)
{
git_revwalk *walk;
walk = git__malloc(sizeof(git_revwalk));
if (walk == NULL)
return GIT_ENOMEM;
memset(walk, 0x0, sizeof(git_revwalk));
walk->commits = git_hashtable_alloc(64,
object_table_hash,
(git_hash_keyeq_ptr)git_oid_cmp);
if (walk->commits == NULL) {
free(walk);
return GIT_ENOMEM;
}
git_pqueue_init(&walk->iterator_time, 8, commit_time_cmp);
git_vector_init(&walk->memory_alloc, 8, NULL);
alloc_chunk(walk);
walk->get_next = &revwalk_next_unsorted;
walk->enqueue = &revwalk_enqueue_unsorted;
walk->repo = repo;
*revwalk_out = walk;
return GIT_SUCCESS;
}
void git_revwalk_free(git_revwalk *walk)
{
unsigned int i;
if (walk == NULL)
return;
git_revwalk_reset(walk);
git_hashtable_free(walk->commits);
git_pqueue_free(&walk->iterator_time);
for (i = 0; i < walk->memory_alloc.length; ++i)
free(git_vector_get(&walk->memory_alloc, i));
git_vector_free(&walk->memory_alloc);
free(walk);
}
git_repository *git_revwalk_repository(git_revwalk *walk)
{
assert(walk);
return walk->repo;
}
void git_revwalk_sorting(git_revwalk *walk, unsigned int sort_mode)
{
assert(walk);
if (walk->walking)
git_revwalk_reset(walk);
walk->sorting = sort_mode;
if (walk->sorting & GIT_SORT_TIME) {
walk->get_next = &revwalk_next_timesort;
walk->enqueue = &revwalk_enqueue_timesort;
} else {
walk->get_next = &revwalk_next_unsorted;
walk->enqueue = &revwalk_enqueue_unsorted;
}
}
int git_revwalk_next(git_oid *oid, git_revwalk *walk)
{
int error;
commit_object *next;
assert(walk && oid);
if (!walk->walking) {
if ((error = prepare_walk(walk)) < GIT_SUCCESS)
return error;
}
error = walk->get_next(&next, walk);
if (error < GIT_SUCCESS) {
if (error == GIT_EREVWALKOVER)
git_revwalk_reset(walk);
return error;
}
git_oid_cpy(oid, &next->oid);
return GIT_SUCCESS;
}
void git_revwalk_reset(git_revwalk *walk)
{
const void *_unused;
commit_object *commit;
assert(walk);
GIT_HASHTABLE_FOREACH(walk->commits, _unused, commit,
commit->seen = 0;
commit->in_degree = 0;
commit->topo_delay = 0;
);
git_pqueue_clear(&walk->iterator_time);
commit_list_free(&walk->iterator_topo);
commit_list_free(&walk->iterator_rand);
commit_list_free(&walk->iterator_reverse);
walk->walking = 0;
}