From: Junio C Hamano <gitster@pobox.com>
Date: Tue, 1 Nov 2011 22:20:07 +0000 (-0700)
Subject: Merge branch 'dm/pack-objects-update'
X-Git-Tag: v1.7.8-rc1~13
X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/84a9ea90e1d704bcac9d26837dff9e3cd7609376?ds=inline;hp=-c

Merge branch 'dm/pack-objects-update'

* dm/pack-objects-update:
pack-objects: don't traverse objects unnecessarily
pack-objects: rewrite add_descendants_to_write_order() iteratively
pack-objects: use unsigned int for counter and offset values
pack-objects: mark add_to_write_order() as inline
---

84a9ea90e1d704bcac9d26837dff9e3cd7609376
diff --combined builtin/pack-objects.c
index ba3705d1de,80ab6c39f9..824ecee20b
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@@ -454,8 -454,8 +454,8 @@@ static int mark_tagged(const char *path
  	return 0;
  }
  
- static void add_to_write_order(struct object_entry **wo,
- 			       int *endp,
+ static inline void add_to_write_order(struct object_entry **wo,
+ 			       unsigned int *endp,
  			       struct object_entry *e)
  {
  	if (e->filled)
@@@ -465,32 -465,62 +465,62 @@@
  }
  
  static void add_descendants_to_write_order(struct object_entry **wo,
- 					   int *endp,
+ 					   unsigned int *endp,
  					   struct object_entry *e)
  {
- 	struct object_entry *child;
- 
- 	for (child = e->delta_child; child; child = child->delta_sibling)
- 		add_to_write_order(wo, endp, child);
- 	for (child = e->delta_child; child; child = child->delta_sibling)
- 		add_descendants_to_write_order(wo, endp, child);
+ 	int add_to_order = 1;
+ 	while (e) {
+ 		if (add_to_order) {
+ 			struct object_entry *s;
+ 			/* add this node... */
+ 			add_to_write_order(wo, endp, e);
+ 			/* all its siblings... */
+ 			for (s = e->delta_sibling; s; s = s->delta_sibling) {
+ 				add_to_write_order(wo, endp, s);
+ 			}
+ 		}
+ 		/* drop down a level to add left subtree nodes if possible */
+ 		if (e->delta_child) {
+ 			add_to_order = 1;
+ 			e = e->delta_child;
+ 		} else {
+ 			add_to_order = 0;
+ 			/* our sibling might have some children, it is next */
+ 			if (e->delta_sibling) {
+ 				e = e->delta_sibling;
+ 				continue;
+ 			}
+ 			/* go back to our parent node */
+ 			e = e->delta;
+ 			while (e && !e->delta_sibling) {
+ 				/* we're on the right side of a subtree, keep
+ 				 * going up until we can go right again */
+ 				e = e->delta;
+ 			}
+ 			if (!e) {
+ 				/* done- we hit our original root node */
+ 				return;
+ 			}
+ 			/* pass it off to sibling at this level */
+ 			e = e->delta_sibling;
+ 		}
+ 	};
  }
  
  static void add_family_to_write_order(struct object_entry **wo,
- 				      int *endp,
+ 				      unsigned int *endp,
  				      struct object_entry *e)
  {
  	struct object_entry *root;
  
  	for (root = e; root->delta; root = root->delta)
  		; /* nothing */
- 	add_to_write_order(wo, endp, root);
  	add_descendants_to_write_order(wo, endp, root);
  }
  
  static struct object_entry **compute_write_order(void)
  {
- 	int i, wo_end;
+ 	unsigned int i, wo_end, last_untagged;
  
  	struct object_entry **wo = xmalloc(nr_objects * sizeof(*wo));
  
@@@ -506,8 -536,8 +536,8 @@@
  	 * Make sure delta_sibling is sorted in the original
  	 * recency order.
  	 */
- 	for (i = nr_objects - 1; 0 <= i; i--) {
- 		struct object_entry *e = &objects[i];
+ 	for (i = nr_objects; i > 0;) {
+ 		struct object_entry *e = &objects[--i];
  		if (!e->delta)
  			continue;
  		/* Mark me as the first child */
@@@ -521,7 -551,7 +551,7 @@@
  	for_each_tag_ref(mark_tagged, NULL);
  
  	/*
- 	 * Give the commits in the original recency order until
+ 	 * Give the objects in the original recency order until
  	 * we see a tagged tip.
  	 */
  	for (i = wo_end = 0; i < nr_objects; i++) {
@@@ -529,6 -559,7 +559,7 @@@
  			break;
  		add_to_write_order(wo, &wo_end, &objects[i]);
  	}
+ 	last_untagged = i;
  
  	/*
  	 * Then fill all the tagged tips.
@@@ -541,7 -572,7 +572,7 @@@
  	/*
  	 * And then all remaining commits and tags.
  	 */
- 	for (i = 0; i < nr_objects; i++) {
+ 	for (i = last_untagged; i < nr_objects; i++) {
  		if (objects[i].type != OBJ_COMMIT &&
  		    objects[i].type != OBJ_TAG)
  			continue;
@@@ -551,7 -582,7 +582,7 @@@
  	/*
  	 * And then all the trees.
  	 */
- 	for (i = 0; i < nr_objects; i++) {
+ 	for (i = last_untagged; i < nr_objects; i++) {
  		if (objects[i].type != OBJ_TREE)
  			continue;
  		add_to_write_order(wo, &wo_end, &objects[i]);
@@@ -560,8 -591,13 +591,13 @@@
  	/*
  	 * Finally all the rest in really tight order
  	 */
- 	for (i = 0; i < nr_objects; i++)
- 		add_family_to_write_order(wo, &wo_end, &objects[i]);
+ 	for (i = last_untagged; i < nr_objects; i++) {
+ 		if (!objects[i].filled)
+ 			add_family_to_write_order(wo, &wo_end, &objects[i]);
+ 	}
+ 
+ 	if (wo_end != nr_objects)
+ 		die("ordered %u objects, expected %"PRIu32, wo_end, nr_objects);
  
  	return wo;
  }
@@@ -804,10 -840,6 +840,10 @@@ static int add_object_entry(const unsig
  		off_t offset = find_pack_entry_one(sha1, p);
  		if (offset) {
  			if (!found_pack) {
 +				if (!is_pack_valid(p)) {
 +					warning("packfile %s cannot be accessed", p->pack_name);
 +					continue;
 +				}
  				found_offset = offset;
  				found_pack = p;
  			}
@@@ -2077,9 -2109,7 +2113,9 @@@ static void show_commit(struct commit *
  	commit->object.flags |= OBJECT_ADDED;
  }
  
 -static void show_object(struct object *obj, const struct name_path *path, const char *last)
 +static void show_object(struct object *obj,
 +			const struct name_path *path, const char *last,
 +			void *data)
  {
  	char *name = path_name(path, last);