thodg/libgit2/tests/core/pqueue.c

• Show log

  Commit

• Hash : 95fa3880
  Author :
  Date : 2016-10-28T16:07:40
  

  pqueue: resolve possible NULL pointer dereference The `git_pqueue` struct allows being fixed in its total number of entries. In this case, we simply throw away items that are inserted into the priority queue by examining wether the new item to be inserted has a higher priority than the previous smallest one. This feature somewhat contradicts our pqueue implementation in that it is allowed to not have a comparison function. In fact, we also fail to check if the comparison function is actually set in the case where we add a new item into a fully filled fixed-size pqueue. As we cannot determine which item is the smallest item in absence of a comparison function, we fix the `NULL` pointer dereference by simply dropping all new items which are about to be inserted into a full fixed-size pqueue.

Download

• tests/core/pqueue.c

• #include "clar_libgit2.h"
  #include "pqueue.h"
  
  static int cmp_ints(const void *v1, const void *v2)
  {
  	int i1 = *(int *)v1, i2 = *(int *)v2;
  	return (i1 < i2) ? -1 : (i1 > i2) ? 1 : 0;
  }
  
  void test_core_pqueue__items_are_put_in_order(void)
  {
  	git_pqueue pq;
  	int i, vals[20];
  
  	cl_git_pass(git_pqueue_init(&pq, 0, 20, cmp_ints));
  
  	for (i = 0; i < 20; ++i) {
  		if (i < 10)
  			vals[i] = 10 - i; /* 10 down to 1 */
  		else
  			vals[i] = i + 1;  /* 11 up to 20 */
  
  		cl_git_pass(git_pqueue_insert(&pq, &vals[i]));
  	}
  
  	cl_assert_equal_i(20, git_pqueue_size(&pq));
  
  	for (i = 1; i <= 20; ++i) {
  		void *p = git_pqueue_pop(&pq);
  		cl_assert(p);
  		cl_assert_equal_i(i, *(int *)p);
  	}
  
  	cl_assert_equal_i(0, git_pqueue_size(&pq));
  
  	git_pqueue_free(&pq);
  }
  
  void test_core_pqueue__interleave_inserts_and_pops(void)
  {
  	git_pqueue pq;
  	int chunk, v, i, vals[200];
  
  	cl_git_pass(git_pqueue_init(&pq, 0, 20, cmp_ints));
  
  	for (v = 0, chunk = 20; chunk <= 200; chunk += 20) {
  		/* push the next 20 */
  		for (; v < chunk; ++v) {
  			vals[v] = (v & 1) ? 200 - v : v;
  			cl_git_pass(git_pqueue_insert(&pq, &vals[v]));
  		}
  
  		/* pop the lowest 10 */
  		for (i = 0; i < 10; ++i)
  			(void)git_pqueue_pop(&pq);
  	}
  
  	cl_assert_equal_i(100, git_pqueue_size(&pq));
  
  	/* at this point, we've popped 0-99 */
  
  	for (v = 100; v < 200; ++v) {
  		void *p = git_pqueue_pop(&pq);
  		cl_assert(p);
  		cl_assert_equal_i(v, *(int *)p);
  	}
  
  	cl_assert_equal_i(0, git_pqueue_size(&pq));
  
  	git_pqueue_free(&pq);
  }
  
  void test_core_pqueue__max_heap_size(void)
  {
  	git_pqueue pq;
  	int i, vals[100];
  
  	cl_git_pass(git_pqueue_init(&pq, GIT_PQUEUE_FIXED_SIZE, 50, cmp_ints));
  
  	for (i = 0; i < 100; ++i) {
  		vals[i] = (i & 1) ? 100 - i : i;
  		cl_git_pass(git_pqueue_insert(&pq, &vals[i]));
  	}
  
  	cl_assert_equal_i(50, git_pqueue_size(&pq));
  
  	for (i = 50; i < 100; ++i) {
  		void *p = git_pqueue_pop(&pq);
  		cl_assert(p);
  		cl_assert_equal_i(i, *(int *)p);
  	}
  
  	cl_assert_equal_i(0, git_pqueue_size(&pq));
  
  	git_pqueue_free(&pq);
  }
  
  void test_core_pqueue__max_heap_size_without_comparison(void)
  {
  	git_pqueue pq;
  	int i, vals[100] = { 0 };
  
  	cl_git_pass(git_pqueue_init(&pq, GIT_PQUEUE_FIXED_SIZE, 50, NULL));
  
  	for (i = 0; i < 100; ++i)
  		cl_git_pass(git_pqueue_insert(&pq, &vals[i]));
  
  	cl_assert_equal_i(50, git_pqueue_size(&pq));
  
  	/* As we have no comparison function, we cannot make any
  	 * actual assumptions about which entries are part of the
  	 * pqueue */
  	for (i = 0; i < 50; ++i)
  		cl_assert(git_pqueue_pop(&pq));
  
  	cl_assert_equal_i(0, git_pqueue_size(&pq));
  
  	git_pqueue_free(&pq);
  }
  
  static int cmp_ints_like_commit_time(const void *a, const void *b)
  {
  	return *((const int *)a) < *((const int *)b);
  }
  
  void test_core_pqueue__interleaved_pushes_and_pops(void)
  {
  	git_pqueue pq;
  	int i, j, *val;
  	static int commands[] =
  		{ 6, 9, 8, 0, 5, 0, 7, 0, 4, 3, 0, 0, 0, 4, 0, 2, 0, 1, 0, 0, -1 };
  	static int expected[] =
  		{ 9, 8, 7, 6, 5, 4, 4, 3, 2, 1, -1 };
  
  	cl_git_pass(git_pqueue_init(&pq, 0, 10, cmp_ints_like_commit_time));
  
  	for (i = 0, j = 0; commands[i] >= 0; ++i) {
  		if (!commands[i]) {
  			cl_assert((val = git_pqueue_pop(&pq)) != NULL);
  			cl_assert_equal_i(expected[j], *val);
  			++j;
  		} else {
  			cl_git_pass(git_pqueue_insert(&pq, &commands[i]));
  		}
  	}
  
  	cl_assert_equal_i(0, git_pqueue_size(&pq));
  	git_pqueue_free(&pq);
  }
  
  

Download