thodg/libgit2/tests/core/pqueue.c
Tag
-
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.
-
tests/core/pqueue.c
-
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150
#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); }