Line data Source code
1 : /*
2 : Unix SMB/CIFS implementation.
3 :
4 : Tests for binsearch.h macros.
5 :
6 : Copyright Catalyst IT 2016.
7 :
8 : Written by Douglas Bagnall <douglas.bagnall@catalyst.net.nz>
9 :
10 : This program is free software; you can redistribute it and/or modify
11 : it under the terms of the GNU General Public License as published by
12 : the Free Software Foundation; either version 3 of the License, or
13 : (at your option) any later version.
14 :
15 : This program is distributed in the hope that it will be useful,
16 : but WITHOUT ANY WARRANTY; without even the implied warranty of
17 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 : GNU General Public License for more details.
19 :
20 : You should have received a copy of the GNU General Public License
21 : along with this program. If not, see <http://www.gnu.org/licenses/>.
22 : */
23 :
24 : #include "includes.h"
25 : #include "lib/util/binsearch.h"
26 : #include "torture/torture.h"
27 : #include "torture/local/proto.h"
28 :
29 0 : static int int_cmp(int a, int b)
30 : {
31 0 : return a - b;
32 : }
33 :
34 0 : static int int_cmp_p(int a, int *b)
35 : {
36 0 : return a - *b;
37 : }
38 :
39 0 : static bool test_binsearch_v(struct torture_context *tctx)
40 : {
41 0 : int array[] = { -11, -7, 0, 1, 723, 1000000};
42 0 : int misses[] = { -121, 17, -10, 10, -1, -723, 1000002};
43 : int i;
44 0 : int *result = NULL;
45 :
46 0 : for (i = 0; i < ARRAY_SIZE(misses); i++) {
47 0 : BINARY_ARRAY_SEARCH_V(array, ARRAY_SIZE(array),
48 : misses[i], int_cmp, result);
49 0 : torture_comment(tctx, "looking for misses[%d] == %d\n", i, misses[i]);
50 0 : torture_assert(tctx, result == NULL, "failed to miss");
51 : }
52 :
53 0 : for (i = 0; i < ARRAY_SIZE(array); i++) {
54 0 : BINARY_ARRAY_SEARCH_V(array, ARRAY_SIZE(array),
55 : array[i], int_cmp, result);
56 0 : torture_comment(tctx, "looking for array[%d] == %d, %p; got %p\n",
57 : i, array[i], &array[i], result);
58 0 : torture_assert(tctx, result == &array[i],
59 : "failed to find element");
60 : }
61 0 : return true;
62 : }
63 :
64 0 : static bool test_binsearch_gte(struct torture_context *tctx)
65 : {
66 0 : int array[] = { -11, -7, -7, -7, -1, 0, 0, 1, 723, 723, 723,
67 : 724, 724, 10000};
68 0 : size_t a_len = ARRAY_SIZE(array);
69 0 : int targets[] = { -121, -8, -7, -6, 17, -10, 10, -1, 723,
70 : 724, 725, 10002, 10000, 0, -11, 1, 11};
71 : int i, j, target;
72 0 : int *result = NULL, *next = NULL;
73 :
74 0 : for (i = 0; i < ARRAY_SIZE(targets); i++) {
75 0 : target = targets[i];
76 0 : torture_comment(tctx, "looking for targets[%d] %d\n",
77 : i, target);
78 :
79 0 : BINARY_ARRAY_SEARCH_GTE(array, a_len, target,
80 : int_cmp_p, result, next);
81 :
82 0 : if (result == NULL) {
83 : /* we think there is no exact match */
84 0 : for (j = 0; j < a_len; j++) {
85 0 : if (target == array[j]) {
86 0 : torture_comment(tctx,
87 : "failed to find %d\n",
88 : targets[i]);
89 0 : torture_fail(tctx,
90 : "result is wrongly NULL");
91 : }
92 : }
93 0 : if (next != NULL) {
94 0 : torture_assert(tctx, (next >= array &&
95 : next < array + a_len),
96 : "next is out of bounds");
97 :
98 0 : torture_assert(tctx, *next > target,
99 : "next <= target");
100 0 : if (target <= array[0]) {
101 0 : torture_assert(tctx, next == array,
102 : "search before start failed");
103 : }
104 0 : if (next != array) {
105 0 : torture_assert(tctx, next[-1] < target,
106 : "next[-1] >= target");
107 : }
108 : }
109 : else {
110 0 : torture_assert(tctx, array[a_len - 1] < target,
111 : "next was not found\n");
112 : }
113 : } else {
114 : /* we think we found an exact match */
115 0 : torture_assert(tctx, *result == target,
116 : "result has wrong value");
117 :
118 0 : torture_assert(tctx, (result >= array &&
119 : result < array + a_len),
120 : "result is out of bounds!");
121 :
122 0 : torture_assert(tctx, next == NULL,
123 : "next should be NULL on exact match\n");
124 0 : if (result != array) {
125 0 : torture_assert(tctx, result[-1] != target,
126 : "didn't find first target\n");
127 : }
128 : }
129 0 : if (target >= array[a_len - 1]) {
130 0 : torture_assert(tctx, next == NULL,
131 : "next is not NULL at array end\n");
132 : }
133 : }
134 :
135 : /* try again, with result and next the same pointer */
136 0 : for (i = 0; i < ARRAY_SIZE(targets); i++) {
137 0 : target = targets[i];
138 0 : torture_comment(tctx, "looking for targets[%d] %d\n",
139 : i, target);
140 :
141 0 : BINARY_ARRAY_SEARCH_GTE(array, a_len, target,
142 : int_cmp_p, result, result);
143 :
144 0 : if (result == NULL) {
145 : /* we think the target is greater than all elements */
146 0 : torture_assert(tctx, array[a_len - 1] < target,
147 : "element >= target not found\n");
148 : } else {
149 : /* we think an element is >= target */
150 0 : torture_assert(tctx, *result >= target,
151 : "result has wrong value");
152 :
153 0 : torture_assert(tctx, (result >= array &&
154 : result < array + a_len),
155 : "result is out of bounds!");
156 :
157 0 : if (result != array) {
158 0 : torture_assert(tctx, result[-1] < target,
159 : "didn't find first target\n");
160 : }
161 : }
162 : }
163 :
164 0 : return true;
165 : }
166 :
167 964 : struct torture_suite *torture_local_util_binsearch(TALLOC_CTX *mem_ctx)
168 : {
169 964 : struct torture_suite *suite = torture_suite_create(mem_ctx, "binsearch");
170 964 : torture_suite_add_simple_test(suite, "binsearch_v", test_binsearch_v);
171 964 : torture_suite_add_simple_test(suite, "binsearch_gte", test_binsearch_gte);
172 964 : return suite;
173 : }
|
