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 "lib/util/tsort.h"
27 : #include "torture/torture.h"
28 : #include "torture/local/proto.h"
29 :
30 33 : static int int_cmp(int a, int b)
31 : {
32 33 : return NUMERIC_CMP(a, b);
33 : }
34 :
35 132 : static int int_cmp_p(int a, int *b)
36 : {
37 132 : int _b = *b;
38 132 : return NUMERIC_CMP(a, _b);
39 : }
40 :
41 1 : static bool test_binsearch_v(struct torture_context *tctx)
42 : {
43 1 : int array[] = { -11, -7, 0, 1, 723, 1000000};
44 1 : int misses[] = { -121, 17, -10, 10, -1, -723, 1000002};
45 1 : int i;
46 1 : int *result = NULL;
47 :
48 8 : for (i = 0; i < ARRAY_SIZE(misses); i++) {
49 26 : BINARY_ARRAY_SEARCH_V(array, ARRAY_SIZE(array),
50 : misses[i], int_cmp, result);
51 7 : torture_comment(tctx, "looking for misses[%d] == %d\n", i, misses[i]);
52 7 : torture_assert(tctx, result == NULL, "failed to miss");
53 : }
54 :
55 7 : for (i = 0; i < ARRAY_SIZE(array); i++) {
56 14 : BINARY_ARRAY_SEARCH_V(array, ARRAY_SIZE(array),
57 : array[i], int_cmp, result);
58 6 : torture_comment(tctx, "looking for array[%d] == %d, %p; got %p\n",
59 : i, array[i], &array[i], result);
60 6 : torture_assert(tctx, result == &array[i],
61 : "failed to find element");
62 : }
63 0 : return true;
64 : }
65 :
66 1 : static bool test_binsearch_gte(struct torture_context *tctx)
67 : {
68 1 : int array[] = { -11, -7, -7, -7, -1, 0, 0, 1, 723, 723, 723,
69 : 724, 724, 10000};
70 1 : size_t a_len = ARRAY_SIZE(array);
71 1 : int targets[] = { -121, -8, -7, -6, 17, -10, 10, -1, 723,
72 : 724, 725, 10002, 10000, 0, -11, 1, 11};
73 1 : int i, j, target;
74 1 : int *result = NULL, *next = NULL;
75 :
76 18 : for (i = 0; i < ARRAY_SIZE(targets); i++) {
77 17 : target = targets[i];
78 17 : torture_comment(tctx, "looking for targets[%d] %d\n",
79 : i, target);
80 :
81 100 : BINARY_ARRAY_SEARCH_GTE(array, a_len, target,
82 : int_cmp_p, result, next);
83 :
84 17 : if (result == NULL) {
85 : /* we think there is no exact match */
86 135 : for (j = 0; j < a_len; j++) {
87 126 : if (target == array[j]) {
88 0 : torture_comment(tctx,
89 : "failed to find %d\n",
90 : targets[i]);
91 126 : torture_fail(tctx,
92 : "result is wrongly NULL");
93 : }
94 : }
95 9 : if (next != NULL) {
96 8 : torture_assert(tctx, (next >= array &&
97 : next < array + a_len),
98 : "next is out of bounds");
99 :
100 8 : torture_assert(tctx, *next > target,
101 : "next <= target");
102 8 : if (target <= array[0]) {
103 1 : torture_assert(tctx, next == array,
104 : "search before start failed");
105 : }
106 8 : if (next != array) {
107 7 : torture_assert(tctx, next[-1] < target,
108 : "next[-1] >= target");
109 : }
110 : }
111 : else {
112 1 : torture_assert(tctx, array[a_len - 1] < target,
113 : "next was not found\n");
114 : }
115 : } else {
116 : /* we think we found an exact match */
117 8 : torture_assert(tctx, *result == target,
118 : "result has wrong value");
119 :
120 8 : torture_assert(tctx, (result >= array &&
121 : result < array + a_len),
122 : "result is out of bounds!");
123 :
124 8 : torture_assert(tctx, next == NULL,
125 : "next should be NULL on exact match\n");
126 8 : if (result != array) {
127 7 : torture_assert(tctx, result[-1] != target,
128 : "didn't find first target\n");
129 : }
130 : }
131 17 : if (target >= array[a_len - 1]) {
132 17 : torture_assert(tctx, next == NULL,
133 : "next is not NULL at array end\n");
134 : }
135 : }
136 :
137 : /* try again, with result and next the same pointer */
138 18 : for (i = 0; i < ARRAY_SIZE(targets); i++) {
139 17 : target = targets[i];
140 17 : torture_comment(tctx, "looking for targets[%d] %d\n",
141 : i, target);
142 :
143 100 : BINARY_ARRAY_SEARCH_GTE(array, a_len, target,
144 : int_cmp_p, result, result);
145 :
146 17 : if (result == NULL) {
147 : /* we think the target is greater than all elements */
148 1 : torture_assert(tctx, array[a_len - 1] < target,
149 : "element >= target not found\n");
150 : } else {
151 : /* we think an element is >= target */
152 16 : torture_assert(tctx, *result >= target,
153 : "result has wrong value");
154 :
155 16 : torture_assert(tctx, (result >= array &&
156 : result < array + a_len),
157 : "result is out of bounds!");
158 :
159 16 : if (result != array) {
160 17 : torture_assert(tctx, result[-1] < target,
161 : "didn't find first target\n");
162 : }
163 : }
164 : }
165 :
166 0 : return true;
167 : }
168 :
169 2338 : struct torture_suite *torture_local_util_binsearch(TALLOC_CTX *mem_ctx)
170 : {
171 2338 : struct torture_suite *suite = torture_suite_create(mem_ctx, "binsearch");
172 2338 : torture_suite_add_simple_test(suite, "binsearch_v", test_binsearch_v);
173 2338 : torture_suite_add_simple_test(suite, "binsearch_gte", test_binsearch_gte);
174 2338 : return suite;
175 : }
|
