prio-queue: use size_t rather than int for size

The alloc and nr fields of a prio-queue tell us how much memory is
allocated and used in the array. So the natural type for them is size_t,
which prevents overflow on 64-bit systems where "int" is still 32 bits.

This is unlikely to happen in practice, as we typically use it for
storing commits, and having 2^31 of those is rather a lot. But it's good
to keep our generic data structures as flexible as possible. And as we
start to enforce -Wsign-compare, it means that callers need to use
"int", too, and the problem proliferates. Let's fix it at the source.

The changes here can be put into a few groups:

  1. Changing the alloc/nr fields in the struct to size_t. This requires
     swapping out int for size_t in negotiator/skipping.c, as well as
     in prio_queue_get(), because those all iterate over the array.
     Building with -Wsign-compare complains about these.

  2. Other code that assigns or passes around indexes into the array
     (e.g., the swap() and compare() functions) won't trigger
     -Wsign-compare because we are simply truncating the values. These
     are caught by -Wconversion, but I've adjusted them here to
     future-proof us.

  3. In prio_queue_reverse() we compute "queue->nr - 1" without checking
     if anything is in the queue, which underflows now that nr is
     unsigned. We can fix that by returning early when the queue is
     empty (there is nothing to reverse).

  4. The insertion_ctr variable is currently unsigned, but can likewise
     grow (it is actually worse, because adding and removing an element
     many times will keep increasing the counter, even though "nr" does
     not). I've bumped that to size_t here, as well.

     But -Wconversion notes that computing the "cmp" result by
     subtracting the counters and assigning to "int" is a potential
     problem. And that's true even before this patch, since we use an
     unsigned counter (imagine comparing "2^32-1" and "0", which should
     be a high positive value, but instead is "-1" as a signed int).

     Since we only care about the sign (and not the magnitude) of the
     result, we could fix this by swapping out the subtraction for a
     ternary comparison. Probably the performance impact would be
     negligible, since we just called into a custom compare function and
     branched on its result anyway. But it's easy enough to do a
     branchless version by subtracting the comparison results.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

1 files changed, 2 insertions, 3 deletions

diff --git a/negotiator/skipping.c b/negotiator/skipping.c
index abedb70a48..616df6bf3a 100644
--- a/negotiator/skipping.c
+++ b/negotiator/skipping.c
@@ -134,7 +134,6 @@ static int push_parent(struct data *data, struct entry *entry,
 	struct entry *parent_entry;
 
 	if (to_push->object.flags & SEEN) {
-		int i;
 		if (to_push->object.flags & POPPED)
 			/*
 			 * The entry for this commit has already been popped,
@@ -145,7 +144,7 @@ static int push_parent(struct data *data, struct entry *entry,
 		/*
 		 * Find the existing entry and use it.
 		 */
-		for (i = 0; i < data->rev_list.nr; i++) {
+		for (size_t i = 0; i < data->rev_list.nr; i++) {
 			parent_entry = data->rev_list.array[i].data;
 			if (parent_entry->commit == to_push)
 				goto parent_found;
@@ -248,7 +247,7 @@ static int ack(struct fetch_negotiator *n, struct commit *c)
 static void release(struct fetch_negotiator *n)
 {
 	struct data *data = n->data;
-	for (int i = 0; i < data->rev_list.nr; i++)
+	for (size_t i = 0; i < data->rev_list.nr; i++)
 		free(data->rev_list.array[i].data);
 	clear_prio_queue(&data->rev_list);
 	FREE_AND_NULL(data);