tdb2: change to using a hash tree.
[ccan] / ccan / tdb2 / test / run-traverse.c
1 #include <ccan/tdb2/tdb.c>
2 #include <ccan/tdb2/free.c>
3 #include <ccan/tdb2/lock.c>
4 #include <ccan/tdb2/io.c>
5 #include <ccan/tdb2/hash.c>
6 #include <ccan/tdb2/check.c>
7 #include <ccan/tdb2/traverse.c>
8 #include <ccan/tap/tap.h>
9 #include "logging.h"
10
11 #define NUM_RECORDS 1000
12
13 /* We use the same seed which we saw a failure on. */
14 static uint64_t fixedhash(const void *key, size_t len, uint64_t seed, void *p)
15 {
16         return hash64_stable((const unsigned char *)key, len,
17                              *(uint64_t *)p);
18 }
19
20 static bool store_records(struct tdb_context *tdb)
21 {
22         int i;
23         struct tdb_data key = { (unsigned char *)&i, sizeof(i) };
24         struct tdb_data data = { (unsigned char *)&i, sizeof(i) };
25
26         for (i = 0; i < NUM_RECORDS; i++)
27                 if (tdb_store(tdb, key, data, TDB_REPLACE) != 0)
28                         return false;
29         return true;
30 }
31
32 struct trav_data {
33         unsigned int calls, call_limit;
34         int low, high;
35         bool mismatch;
36         bool delete;
37         enum TDB_ERROR delete_error;
38 };
39
40 static int trav(struct tdb_context *tdb, TDB_DATA key, TDB_DATA dbuf, void *p)
41 {
42         struct trav_data *td = p;
43         int val;
44
45         td->calls++;
46         if (key.dsize != sizeof(val) || dbuf.dsize != sizeof(val)
47             || memcmp(key.dptr, dbuf.dptr, key.dsize) != 0) {
48                 td->mismatch = true;
49                 return -1;
50         }
51         memcpy(&val, dbuf.dptr, dbuf.dsize);
52         if (val < td->low)
53                 td->low = val;
54         if (val > td->high)
55                 td->high = val;
56
57         if (td->delete) {
58
59                 if (tdb_delete(tdb, key) != 0) {
60                         td->delete_error = tdb_error(tdb);
61                         return -1;
62                 }
63         }
64
65         if (td->calls == td->call_limit)
66                 return 1;
67         return 0;
68 }
69
70 struct trav_grow_data {
71         unsigned int calls;
72         unsigned int num_large;
73         bool mismatch;
74         enum TDB_ERROR error;
75 };
76
77 static int trav_grow(struct tdb_context *tdb, TDB_DATA key, TDB_DATA dbuf,
78                      void *p)
79 {
80         struct trav_grow_data *tgd = p;
81         int val;
82         unsigned char buffer[128] = { 0 };
83
84         tgd->calls++;
85         if (key.dsize != sizeof(val) || dbuf.dsize < sizeof(val)
86             || memcmp(key.dptr, dbuf.dptr, key.dsize) != 0) {
87                 tgd->mismatch = true;
88                 return -1;
89         }
90
91         if (dbuf.dsize > sizeof(val))
92                 /* We must have seen this before! */
93                 tgd->num_large++;
94
95         /* Make a big difference to the database. */
96         dbuf.dptr = buffer;
97         dbuf.dsize = sizeof(buffer);
98         if (tdb_append(tdb, key, dbuf) != 0) {
99                 tgd->error = tdb_error(tdb);
100                 return -1;
101         }
102         return 0;
103 }
104
105 int main(int argc, char *argv[])
106 {
107         unsigned int i;
108         int num;
109         struct trav_data td;
110         struct trav_grow_data tgd;
111         struct tdb_context *tdb;
112         uint64_t seed = 16014841315512641303ULL;
113         int flags[] = { TDB_INTERNAL, TDB_DEFAULT, TDB_NOMMAP,
114                         TDB_INTERNAL|TDB_CONVERT, TDB_CONVERT, 
115                         TDB_NOMMAP|TDB_CONVERT };
116         union tdb_attribute hattr = { .hash = { .base = { TDB_ATTRIBUTE_HASH },
117                                                 .hash_fn = fixedhash,
118                                                 .hash_private = &seed } };
119
120         hattr.base.next = &tap_log_attr;
121
122         plan_tests(sizeof(flags) / sizeof(flags[0]) * 50 + 1);
123         for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) {
124                 tdb = tdb_open("run-traverse.tdb", flags[i],
125                                O_RDWR|O_CREAT|O_TRUNC, 0600, &hattr);
126                 ok1(tdb);
127                 if (!tdb)
128                         continue;
129
130                 ok1(tdb_traverse_read(tdb, NULL, NULL) == 0);
131                 ok1(tdb_traverse(tdb, NULL, NULL) == 0);
132
133                 ok1(store_records(tdb));
134                 num = tdb_traverse_read(tdb, NULL, NULL);
135                 ok1(num == NUM_RECORDS);
136                 num = tdb_traverse(tdb, NULL, NULL);
137                 ok1(num == NUM_RECORDS);
138
139                 /* Full traverse (read-only). */
140                 td.calls = 0;
141                 td.call_limit = UINT_MAX;
142                 td.low = INT_MAX;
143                 td.high = INT_MIN;
144                 td.mismatch = false;
145                 td.delete = false;
146
147                 num = tdb_traverse_read(tdb, trav, &td);
148                 ok1(num == NUM_RECORDS);
149                 ok1(!td.mismatch);
150                 ok1(td.calls == NUM_RECORDS);
151                 ok1(td.low == 0);
152                 ok1(td.high == NUM_RECORDS-1);
153
154                 /* Full traverse. */
155                 td.calls = 0;
156                 td.call_limit = UINT_MAX;
157                 td.low = INT_MAX;
158                 td.high = INT_MIN;
159                 td.mismatch = false;
160                 td.delete = false;
161
162                 num = tdb_traverse(tdb, trav, &td);
163                 ok1(num == NUM_RECORDS);
164                 ok1(!td.mismatch);
165                 ok1(td.calls == NUM_RECORDS);
166                 ok1(td.low == 0);
167                 ok1(td.high == NUM_RECORDS-1);
168
169                 /* Short traverse. */
170                 td.calls = 0;
171                 td.call_limit = NUM_RECORDS / 2;
172                 td.low = INT_MAX;
173                 td.high = INT_MIN;
174                 td.mismatch = false;
175                 td.delete = false;
176
177                 num = tdb_traverse(tdb, trav, &td);
178                 ok1(num == NUM_RECORDS / 2);
179                 ok1(!td.mismatch);
180                 ok1(td.calls == NUM_RECORDS / 2);
181                 ok1(td.low <= NUM_RECORDS / 2);
182                 ok1(td.high > NUM_RECORDS / 2);
183                 ok1(tdb_check(tdb, NULL, NULL) == 0);
184
185                 /* Growing traverse.  Expect failure on r/o traverse. */
186                 tgd.calls = 0;
187                 tgd.num_large = 0;
188                 tgd.mismatch = false;
189                 tgd.error = TDB_SUCCESS;
190                 num = tdb_traverse_read(tdb, trav_grow, &tgd);
191                 ok1(num == 1);
192                 ok1(tgd.error == TDB_ERR_RDONLY);
193                 ok1(tgd.calls == 1);
194                 ok1(!tgd.mismatch);
195                 ok1(tdb_check(tdb, NULL, NULL) == 0);
196
197                 /* Deleting traverse.  Expect failure on r/o traverse. */
198                 td.calls = 0;
199                 td.call_limit = UINT_MAX;
200                 td.low = INT_MAX;
201                 td.high = INT_MIN;
202                 td.mismatch = false;
203                 td.delete = true;
204                 td.delete_error = TDB_SUCCESS;
205                 num = tdb_traverse_read(tdb, trav, &td);
206                 ok1(num == 1);
207                 ok1(td.delete_error == TDB_ERR_RDONLY);
208                 ok1(!td.mismatch);
209                 ok1(td.calls == 1);
210                 ok1(td.low == td.high);
211                 ok1(tdb_check(tdb, NULL, NULL) == 0);
212
213                 /* Deleting traverse (delete everything). */
214                 td.calls = 0;
215                 td.call_limit = UINT_MAX;
216                 td.low = INT_MAX;
217                 td.high = INT_MIN;
218                 td.mismatch = false;
219                 td.delete = true;
220                 td.delete_error = TDB_SUCCESS;
221                 num = tdb_traverse(tdb, trav, &td);
222                 ok1(num == NUM_RECORDS);
223                 ok1(td.delete_error == TDB_SUCCESS);
224                 ok1(!td.mismatch);
225                 ok1(td.calls == NUM_RECORDS);
226                 ok1(td.low == 0);
227                 ok1(td.high == NUM_RECORDS - 1);
228                 ok1(tdb_check(tdb, NULL, NULL) == 0);
229
230                 /* Now it's empty! */
231                 ok1(tdb_traverse_read(tdb, NULL, NULL) == 0);
232                 ok1(tdb_traverse(tdb, NULL, NULL) == 0);
233
234                 /* Re-add. */
235                 ok1(store_records(tdb));
236                 ok1(tdb_traverse_read(tdb, NULL, NULL) == NUM_RECORDS);
237                 ok1(tdb_check(tdb, NULL, NULL) == 0);
238
239                 /* Grow.  This will cause us to be reshuffled. */
240                 tgd.calls = 0;
241                 tgd.num_large = 0;
242                 tgd.mismatch = false;
243                 tgd.error = TDB_SUCCESS;
244                 ok1(tdb_traverse(tdb, trav_grow, &tgd) > 1);
245                 ok1(tgd.error == 0);
246                 ok1(!tgd.mismatch);
247                 ok1(tdb_check(tdb, NULL, NULL) == 0);
248                 ok1(tgd.num_large < tgd.calls);
249                 diag("growing db: %u calls, %u repeats",
250                      tgd.calls, tgd.num_large);
251
252                 tdb_close(tdb);
253         }
254
255         ok1(tap_log_messages == 0);
256         return exit_status();
257 }