thodg/libgit2/src/index.c

• Show log

  Commit

• Hash : 68535125
  Author :
  Date : 2010-07-09T20:19:56
  

  Add support for git index files The new 'git_index' structure is an in-memory representation of a git index on disk; the 'git_index_entry' structures represent each one of the file entries on the index. The following calls for index instantiation have been added: git_index_alloc(): instantiate a new index structure git_index_free(): free an existing index git_index_clear(): clear all the entires in an existing file The following calls for index reading and writing have been added: git_index_read(): update the contents of the index structure from its file on disk. Internally implemented through: git_index__parse() Index files are stored on disk in network byte order; all integer fields inside them are properly converted to the machine's byte order when loading them in memory. The parsing engine also distinguishes between normal index entries and extended entries with 2 extra bytes of flags. The 'TREE' extension for index entries is also loaded into memory: Tree caches stored in Index files are loaded into the 'git_index_tree' structure pointed by the 'tree' pointer inside 'git_index'. 'index->tree' points to the root node of the tree cache; the full tree can be traversed through each of the node's 'tree->children'. Index files can be written back to disk through: git_index_write(): atomic writing of existing index objects backed by internal method git_index__write() The following calls for entry manipulation have been added: git_index_add(): insert an empty entry to the index git_index_find(): search an entry by its path name git_index__append(): appends a new index entry to the end of the list, resizing the entries array if required New index entries are always inserted at the end of the array; since the index entries must be sorted for it to be internally consistent, the index object is only sorted once, and if required, before accessing the whole entriea array (e.g. before writing to disk, before traversing, etc). git_index__remove_pos(): remove an index entry in a specific position git_index__sort(): sort the entries in the array by path name The entries array is sorted stably and in place using an insertion sort, which ought to be the most efficient approach since the entries array is always mostly-sorted. Signed-off-by: Vicent Marti <tanoku@gmail.com>

Download

• src/index.c

• /*
   * 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 <stddef.h>
  
  #include "common.h"
  #include "index.h"
  #include "hash.h"
  #include "git/odb.h"
  
  #define entry_padding(type, len) (8 - ((offsetof(type, path) + (len)) & 0x7))
  #define short_entry_padding(len) entry_padding(struct entry_short, len)
  #define long_entry_padding(len) entry_padding(struct entry_long, len)
  
  #define entry_size(type,len) ((offsetof(type, path) + (len) + 8) & ~7)
  #define short_entry_size(len) entry_size(struct entry_short, len)
  #define long_entry_size(len) entry_size(struct entry_long, len)
  
  #define minimal_entry_size (offsetof(struct entry_short, path))
  
  static const char INDEX_HEADER_SIG[] = {'D', 'I', 'R', 'C'};
  static const char INDEX_EXT_TREECACHE_SIG[] = {'T', 'R', 'E', 'E'};
  
  static const size_t INDEX_FOOTER_SIZE = GIT_OID_RAWSZ;
  static const size_t INDEX_HEADER_SIZE = 12;
  
  static const unsigned int INDEX_VERSION_NUMBER = 2;
  
  struct index_header {
  	uint32_t signature;
  	uint32_t version;
  	uint32_t entry_count;
  };
  
  struct index_extension {
  	char signature[4];
  	uint32_t extension_size;
  };
  
  struct entry_short {
  	git_index_time ctime;
  	git_index_time mtime;
  	uint32_t dev;
  	uint32_t ino;
  	uint32_t mode;
  	uint32_t uid;
  	uint32_t gid;
  	uint32_t file_size;
  	git_oid oid;
  	uint16_t flags;
  	char path[1]; /* arbritrary length */
  };
  
  struct entry_long {
  	git_index_time ctime;
  	git_index_time mtime;
  	uint32_t dev;
  	uint32_t ino;
  	uint32_t mode;
  	uint32_t uid;
  	uint32_t gid;
  	uint32_t file_size;
  	git_oid oid;
  	uint16_t flags;
  	uint16_t flags_extended;
  	char path[1]; /* arbritrary length */
  };
  
  /* local declarations */
  static size_t read_extension(git_index *index, const char *buffer, size_t buffer_size);
  static size_t read_entry(git_index_entry *dest, const void *buffer, size_t buffer_size);
  static int read_header(struct index_header *dest, const void *buffer);
  
  static int read_tree(git_index *index, const char *buffer, size_t buffer_size);
  static git_index_tree *read_tree_internal(const char **, const char *, git_index_tree *);
  
  
  git_index *git_index_alloc(const char *index_path)
  {
  	git_index *index;
  
  	if (index_path == NULL)
  		return NULL;
  
  	index = git__malloc(sizeof(git_index));
  	if (index == NULL)
  		return NULL;
  
  	memset(index, 0x0, sizeof(git_index));
  
  	index->index_file_path = git__strdup(index_path);
  	if (index->index_file_path == NULL) {
  		free(index);
  		return NULL;
  	}
  
  	/* Check if index file is stored on disk already */
  	if (gitfo_exists(index->index_file_path) == 0)
  		index->on_disk = 1;
  
  	return index;
  }
  
  void git_index_clear(git_index *index)
  {
  	unsigned int i;
  	for (i = 0; i < index->entry_count; ++i)
  		free(index->entries[i].path);
  
  	index->entry_count = 0;
  	index->last_modified = 0;
  	index->sorted = 1;
  
  	git_index_tree__free(index->tree);
  	index->tree = NULL;
  }
  
  void git_index_free(git_index *index)
  {
  	git_index_clear(index);
  	free(index->entries);
  	index->entries = NULL;
  	free(index->index_file_path);
  	free(index);
  }
  
  
  int git_index_read(git_index *index)
  {
  	struct stat indexst;
  	int error = 0;
  
  	if (index->index_file_path == NULL)
  		return GIT_ERROR;
  
  	if (!index->on_disk || gitfo_exists(index->index_file_path) < 0) {
  		git_index_clear(index);
  		index->on_disk = 0;
  		return 0;
  	}
  
  	if (gitfo_stat(index->index_file_path, &indexst) < 0)
  		return GIT_EOSERR;
  
  	if (indexst.st_mtime != index->last_modified) {
  
  		gitfo_buf buffer;
  
  		if (gitfo_read_file(&buffer, index->index_file_path) < 0)
  			return GIT_EOSERR;
  
  		git_index_clear(index);
  		error = git_index__parse(index, buffer.data, buffer.len);
  
  		if (error == 0)
  			index->last_modified = indexst.st_mtime;
  
  		gitfo_free_buf(&buffer);
  	}
  
  	return error;
  }
  
  int git_index_write(git_index *index)
  {
  	git_filelock file;
  	struct stat indexst;
  
  	if (!index->sorted)
  		git_index__sort(index);
  
  	if (git_filelock_init(&file, index->index_file_path) < 0)
  		return GIT_EOSERR;
  
  	if (git_filelock_lock(&file, 0) < 0)
  		return GIT_EOSERR;
  
  	if (git_index__write(index, &file) < 0) {
  		git_filelock_unlock(&file);
  		return GIT_EOSERR;
  	}
  
  	if (git_filelock_commit(&file) < 0)
  		return GIT_EOSERR;
  
  	if (gitfo_stat(index->index_file_path, &indexst) == 0) {
  		index->last_modified = indexst.st_mtime;
  		index->on_disk = 1;
  	}
  
  	return 0;
  }
  
  int git_index_add(git_index *index, const char *filename, int stage)
  {
  	git_index_entry entry;
  	size_t path_length;
  
  	memset(&entry, 0x0, sizeof(git_index_entry));
  
  	path_length = strlen(filename);
  
  	if (path_length < GIT_IDXENTRY_NAMEMASK)
  		entry.flags |= path_length;
  	else
  		entry.flags |= path_length;
  
  	if (stage < 0 || stage > 3)
  		return GIT_ERROR;
  
  	entry.flags |= (stage << GIT_IDXENTRY_STAGESHIFT);
  
  	entry.path = git__strdup(filename);
  
  	return git_index__append(index, &entry);
  }
  
  void git_index__sort(git_index *index)
  {
  	git_index_entry pivot;
  	int i, j;
  
  	if (index->sorted)
  		return;
  
  	for (i = 1; i < (int)index->entry_count; ++i) {
  
  		memcpy(&pivot, &index->entries[i], sizeof(git_index_entry));
  		j = i - 1;
  
  		while (j >= 0 && strcmp(pivot.path, index->entries[j].path) < 0) {
  			memcpy(&index->entries[j + 1], &index->entries[j], sizeof(git_index_entry));
  			j = j - 1;
  		}
  
  		memcpy(&index->entries[j + 1], &pivot, sizeof(git_index_entry));
  	}
  
  	index->sorted = 1;
  }
  
  int git_index__append(git_index *index, const git_index_entry *source_entry)
  {
  	git_index_entry *offset;
  
  	/* Resize the entries array */
  	if (index->entry_count + 1 > index->entries_size) {
  		git_index_entry *new_entries;
  		size_t new_size;
  
  		new_size = (unsigned int)(index->entries_size * 1.5f);
  		if ((new_entries = git__malloc(new_size * sizeof(git_index_entry))) == NULL)
  			return GIT_ENOMEM;
  
  		memcpy(new_entries, index->entries, index->entry_count * sizeof(git_index_entry));
  		free(index->entries);
  
  		index->entries_size = new_size;
  		index->entries = new_entries;
  	}
  
  	offset = &index->entries[index->entry_count];
  	index->entry_count++;
  
  	memcpy(offset, source_entry, sizeof(git_index_entry));
  	index->sorted = 0;
  
  	return 0;
  }
  
  int git_index__remove_pos(git_index *index, unsigned int position)
  {
  	git_index_entry *offset;
  	size_t copy_size;
  
  	offset = &index->entries[position];
  	index->entry_count--;
  	copy_size = (index->entry_count - position) * sizeof(git_index_entry);
  
  	memcpy(offset, offset + sizeof(git_index_entry), copy_size);
  
  	return 0;
  }
  
  int git_index_find(git_index *index, const char *path)
  {
  	int low = 0, high = index->entry_count;
  
  	if (!index->sorted)
  		git_index__sort(index);
  
  	while (low < high) {
  		int mid = (low + high) >> 1;
  		int cmp = strcmp(path, index->entries[mid].path);
  
  		if (cmp < 0)
  			high = mid;
  
  		else if (cmp == 0) {
  
  			while (mid > 0 && strcmp(path, index->entries[mid - 1].path) == 0)
  				mid--;
  
  			return mid;
  
  		} else
  			low = mid + 1;
  	}
  
  	return GIT_ENOTFOUND; /* NOT FOUND */
  }
  
  void git_index_tree__free(git_index_tree *tree)
  {
  	unsigned int i;
  
  	if (tree == NULL)
  		return;
  
  	for (i = 0; i < tree->children_count; ++i)
  		git_index_tree__free(tree->children[i]);
  
  	free(tree->name);
  	free(tree->children);
  	free(tree);
  }
  
  static git_index_tree *read_tree_internal(
  		const char **buffer_in, const char *buffer_end, git_index_tree *parent)
  {
  	git_index_tree *tree;
  	const char *name_start, *buffer;
  
  	if ((tree = git__malloc(sizeof(git_index_tree))) == NULL)
  		return NULL;
  
  	memset(tree, 0x0, sizeof(git_index_tree));
  	tree->parent = parent;
  
  	buffer = name_start = *buffer_in;
  
  	if ((buffer = memchr(buffer, '\0', buffer_end - buffer)) == NULL)
  		goto error_cleanup;
  
  	/* NUL-terminated tree name */
  	tree->name = git__strdup(name_start);
  	if (++buffer >= buffer_end)
  		goto error_cleanup;
  
  	/* Blank-terminated ASCII decimal number of entries in this tree */
  	tree->entries = strtol(buffer, (char **)&buffer, 10);
  	if (*buffer != ' ' || ++buffer >= buffer_end)
  		goto error_cleanup;
  
  	 /* Number of children of the tree, newline-terminated */
  	tree->children_count = strtol(buffer, (char **)&buffer, 10);
  	if (*buffer != '\n' || ++buffer >= buffer_end)
  		goto error_cleanup;
  
  	/* 160-bit SHA-1 for this tree and it's children */
  	if (buffer + GIT_OID_RAWSZ > buffer_end)
  		goto error_cleanup;
  
  	git_oid_mkraw(&tree->oid, (const unsigned char *)buffer);
  	buffer += GIT_OID_RAWSZ;
  
  	/* Parse children: */
  	if (tree->children_count > 0) {
  		unsigned int i;
  
  		tree->children = git__malloc(tree->children_count * sizeof(git_index_tree *));
  		if (tree->children == NULL)
  			goto error_cleanup;
  
  		for (i = 0; i < tree->children_count; ++i) {
  			tree->children[i] = read_tree_internal(&buffer, buffer_end, tree);
  
  			if (tree->children[i] == NULL)
  				goto error_cleanup;
  		}
  	}
  
  	*buffer_in = buffer;
  	return tree;
  
  error_cleanup:
  	git_index_tree__free(tree);
  	return NULL;
  }
  
  static int read_tree(git_index *index, const char *buffer, size_t buffer_size)
  {
  	const char *buffer_end = buffer + buffer_size;
  
  	index->tree = read_tree_internal(&buffer, buffer_end, NULL);
  	return (index->tree != NULL && buffer == buffer_end) ? 0 : GIT_EOBJCORRUPTED;
  }
  
  static size_t read_entry(git_index_entry *dest, const void *buffer, size_t buffer_size)
  {
  	size_t path_length, entry_size;
  	uint16_t flags_raw;
  	const char *path_ptr;
  	const struct entry_short *source;
  
  	if (INDEX_FOOTER_SIZE + minimal_entry_size > buffer_size)
  		return 0;
  
  	source = (const struct entry_short *)(buffer);
  
  	dest->ctime.seconds = ntohl(source->ctime.seconds);
  	dest->ctime.nanoseconds = ntohl(source->ctime.nanoseconds);
  	dest->mtime.seconds = ntohl(source->mtime.seconds);
  	dest->mtime.nanoseconds = ntohl(source->mtime.nanoseconds);
  	dest->dev = ntohl(source->dev);
  	dest->ino = ntohl(source->ino);
  	dest->mode = ntohl(source->mode);
  	dest->uid = ntohl(source->uid);
  	dest->gid = ntohl(source->gid);
  	dest->file_size = ntohl(source->file_size);
  	git_oid_cpy(&dest->oid, &source->oid);
  	dest->flags = ntohs(source->flags);
  
  	if (dest->flags & GIT_IDXENTRY_EXTENDED) {
  		struct entry_long *source_l = (struct entry_long *)source;
  		path_ptr = source_l->path;
  
  		flags_raw = ntohs(source_l->flags_extended);
  		memcpy(&dest->flags_extended, &flags_raw, 2);
  	} else
  		path_ptr = source->path;
  
  	path_length = dest->flags & GIT_IDXENTRY_NAMEMASK;
  
  	/* if this is a very long string, we must find its
  	 * real length without overflowing */
  	if (path_length == 0xFFF) {
  		const char *path_end;
  
  		path_end = memchr(path_ptr, '\0', buffer_size);
  		if (path_end == NULL)
  			return 0;
  
  		path_length = path_end - path_ptr;
  	}
  
  	if (dest->flags & GIT_IDXENTRY_EXTENDED)
  		entry_size = long_entry_size(path_length);
  	else
  		entry_size = short_entry_size(path_length);
  
  	if (INDEX_FOOTER_SIZE + entry_size > buffer_size)
  		return 0;
  
  	dest->path = git__strdup(path_ptr);
  
  	return entry_size;
  }
  
  static int read_header(struct index_header *dest, const void *buffer)
  {
  	const struct index_header *source;
  	source = (const struct index_header *)(buffer);
  
  	dest->signature = source->signature;
  	if (memcmp(&dest->signature, INDEX_HEADER_SIG, 4) != 0)
  		return GIT_EOBJCORRUPTED;
  
  	dest->version = ntohl(source->version);
  	if (dest->version != INDEX_VERSION_NUMBER)
  		return GIT_EOBJCORRUPTED;
  
  	dest->entry_count = ntohl(source->entry_count);
  	return 0;
  }
  
  static size_t read_extension(git_index *index, const char *buffer, size_t buffer_size)
  {
  	const struct index_extension *source;
  	struct index_extension dest;
  	size_t total_size;
  
  	source = (const struct index_extension *)(buffer);
  
  	memcpy(dest.signature, source->signature, 4);
  	dest.extension_size = ntohl(source->extension_size);
  
  	total_size = dest.extension_size + sizeof(struct index_extension);
  
  	if (buffer_size - total_size < INDEX_FOOTER_SIZE)
  		return 0;
  
  	/* optional extension */
  	if (dest.signature[0] >= 'A' && dest.signature[0] <= 'Z') {
  		/* tree cache */
  		if (memcmp(dest.signature, INDEX_EXT_TREECACHE_SIG, 4) == 0) {
  
  			if (read_tree(index, buffer + 8, dest.extension_size) < 0)
  				return 0;
  		}
  	} else {
  		/* we cannot handle non-ignorable extensions;
  		 * in fact they aren't even defined in the standard */
  		return 0;
  	}
  
  	return total_size;
  }
  
  int git_index__parse(git_index *index, const char *buffer, size_t buffer_size)
  {
  	unsigned int i;
  	struct index_header header;
  	git_oid checksum_calculated, checksum_expected;
  
  #define seek_forward(_increase) { \
  	if (_increase >= buffer_size) \
  		return GIT_EOBJCORRUPTED; \
  	buffer += _increase; \
  	buffer_size -= _increase;\
  }
  
  	if (buffer_size < INDEX_HEADER_SIZE + INDEX_FOOTER_SIZE)
  		return GIT_EOBJCORRUPTED;
  
  	/* Precalculate the SHA1 of the files's contents -- we'll match it to
  	 * the provided SHA1 in the footer */
  	git_hash_buf(&checksum_calculated, (const void *)buffer, buffer_size - INDEX_FOOTER_SIZE);
  
  	/* Parse header */
  	if (read_header(&header, buffer) < 0)
  		return GIT_EOBJCORRUPTED;
  
  	seek_forward(INDEX_HEADER_SIZE);
  
  	index->entry_count = header.entry_count;
  
  	/* If there is already a entires array, reuse it if it can hold all the
  	 * entries. If not, free and reallocate */
  	if (index->entry_count > index->entries_size) {
  		free(index->entries);
  		index->entries_size = (uint32_t)(index->entry_count * 1.3f);
  		index->entries = git__malloc(index->entries_size * sizeof(git_index_entry));
  	}
  
  	/* Parse all the entries */
  	for (i = 0; i < index->entry_count && buffer_size > INDEX_FOOTER_SIZE; ++i) {
  		size_t entry_size;
  		entry_size = read_entry(&index->entries[i], buffer, buffer_size);
  
  		/* 0 bytes read means an object corruption */
  		if (entry_size == 0)
  			return GIT_EOBJCORRUPTED;
  
  		seek_forward(entry_size);
  	}
  
  	/* There's still space for some extensions! */
  	while (buffer_size > INDEX_FOOTER_SIZE) {
  		size_t extension_size;
  
  		extension_size = read_extension(index, buffer, buffer_size);
  
  		/* see if we have read any bytes from the extension */
  		if (extension_size == 0)
  			return GIT_EOBJCORRUPTED;
  
  		seek_forward(extension_size);
  	}
  
  	if (buffer_size != INDEX_FOOTER_SIZE)
  		return GIT_EOBJCORRUPTED;
  
  	/* 160-bit SHA-1 over the content of the index file before this checksum. */
  	git_oid_mkraw(&checksum_expected, (const unsigned char *)buffer);
  
  	if (git_oid_cmp(&checksum_calculated, &checksum_expected) != 0)
  		return GIT_EOBJCORRUPTED;
  
  #undef seek_forward
  
  	return 0;
  }
  
  int git_index__write(git_index *index, git_filelock *file)
  {
  	static const char NULL_BYTES[] = {0, 0, 0, 0, 0, 0, 0, 0};
  
  	int error = 0;
  	unsigned int i;
  
  	git_hash_ctx *digest;
  	git_oid hash_final;
  
  	if (index == NULL || file == NULL || !file->is_locked)
  		return GIT_ERROR;
  
  	if ((digest = git_hash_new_ctx()) == NULL)
  		return GIT_ERROR;
  
  #define WRITE_WORD(_word) {\
  	uint32_t network_word = htonl((_word));\
  	git_filelock_write(file, &network_word, 4);\
  	git_hash_update(digest, &network_word, 4);\
  }
  
  #define WRITE_SHORT(_shrt) {\
  	uint16_t network_shrt = htons((_shrt));\
  	git_filelock_write(file, &network_shrt, 2);\
  	git_hash_update(digest, &network_shrt, 2);\
  }
  
  #define WRITE_BYTES(_bytes, _n) {\
  	git_filelock_write(file, _bytes, _n);\
  	git_hash_update(digest, _bytes, _n);\
  }
  
  	WRITE_BYTES(INDEX_HEADER_SIG, 4);
  
  	WRITE_WORD(INDEX_VERSION_NUMBER);
  	WRITE_WORD(index->entry_count);
  
  	for (i = 0; i < index->entry_count; ++i) {
  		git_index_entry *entry;
  		size_t path_length, padding;
  
  		entry = &index->entries[i];
  		path_length = strlen(entry->path);
  
  		WRITE_WORD(entry->ctime.seconds);
  		WRITE_WORD(entry->ctime.nanoseconds);
  		WRITE_WORD(entry->mtime.seconds);
  		WRITE_WORD(entry->mtime.nanoseconds);
  		WRITE_WORD(entry->dev);
  		WRITE_WORD(entry->ino);
  		WRITE_WORD(entry->mode);
  		WRITE_WORD(entry->uid);
  		WRITE_WORD(entry->gid);
  		WRITE_WORD(entry->file_size);
  		WRITE_BYTES(entry->oid.id, GIT_OID_RAWSZ);
  		WRITE_SHORT(entry->flags);
  
  		if (entry->flags & GIT_IDXENTRY_EXTENDED) {
  			WRITE_SHORT(entry->flags_extended);
  			padding = long_entry_padding(path_length);
  		} else
  			padding = short_entry_padding(path_length);
  
  		WRITE_BYTES(entry->path, path_length);
  		WRITE_BYTES(NULL_BYTES, padding);
  	}
  
  #undef WRITE_WORD
  #undef WRITE_BYTES
  #undef WRITE_SHORT
  #undef WRITE_FLAGS
  
  	/* TODO: write extensions (tree cache) */
  
  	git_hash_final(&hash_final, digest);
  	git_hash_free_ctx(digest);
  	git_filelock_write(file, hash_final.id, GIT_OID_RAWSZ);
  
  	return error;
  }
  

Download