tdb2: change to using a hash tree.
[ccan] / ccan / tdb2 / test / run-13-delete.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/tap/tap.h>
8 #include "logging.h"
9
10 /* We rig the hash so adjacent-numbered records always clash. */
11 static uint64_t clash(const void *key, size_t len, uint64_t seed, void *priv)
12 {
13         return ((uint64_t)*(unsigned int *)key)
14                 << (64 - TDB_TOPLEVEL_HASH_BITS - 1);
15 }
16
17 /* We use the same seed which we saw a failure on. */
18 static uint64_t fixedhash(const void *key, size_t len, uint64_t seed, void *p)
19 {
20         return hash64_stable((const unsigned char *)key, len,
21                              *(uint64_t *)p);
22 }
23
24 static bool store_records(struct tdb_context *tdb)
25 {
26         int i;
27         struct tdb_data key = { (unsigned char *)&i, sizeof(i) };
28         struct tdb_data data = { (unsigned char *)&i, sizeof(i) };
29
30         for (i = 0; i < 1000; i++) {
31                 if (tdb_store(tdb, key, data, TDB_REPLACE) != 0)
32                         return false;
33                 if (tdb_fetch(tdb, key).dsize != data.dsize)
34                         return false;
35         }
36         return true;
37 }
38
39 static void test_val(struct tdb_context *tdb, uint64_t val)
40 {
41         uint64_t v;
42         struct tdb_data key = { (unsigned char *)&v, sizeof(v) };
43         struct tdb_data data = { (unsigned char *)&v, sizeof(v) };
44
45         /* Insert an entry, then delete it. */
46         v = val;
47         /* Delete should fail. */
48         ok1(tdb_delete(tdb, key) == -1);
49         ok1(tdb_error(tdb) == TDB_ERR_NOEXIST);
50         ok1(tdb_check(tdb, NULL, NULL) == 0);
51
52         /* Insert should succeed. */
53         ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
54         ok1(tdb_check(tdb, NULL, NULL) == 0);
55
56         /* Delete should succeed. */
57         ok1(tdb_delete(tdb, key) == 0);
58         ok1(tdb_check(tdb, NULL, NULL) == 0);
59
60         /* Re-add it, then add collision. */
61         ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
62         v = val + 1;
63         ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
64         ok1(tdb_check(tdb, NULL, NULL) == 0);
65
66         /* Can find both? */
67         ok1(tdb_fetch(tdb, key).dsize == data.dsize);
68         v = val;
69         ok1(tdb_fetch(tdb, key).dsize == data.dsize);
70
71         /* Delete second one. */
72         v = val + 1;
73         ok1(tdb_delete(tdb, key) == 0);
74         ok1(tdb_check(tdb, NULL, NULL) == 0);
75
76         /* Re-add */
77         ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
78         ok1(tdb_check(tdb, NULL, NULL) == 0);
79
80         /* Now, try deleting first one. */
81         v = val;
82         ok1(tdb_delete(tdb, key) == 0);
83         ok1(tdb_check(tdb, NULL, NULL) == 0);
84
85         /* Can still find second? */
86         v = val + 1;
87         ok1(tdb_fetch(tdb, key).dsize == data.dsize);
88
89         /* Now, this will be ideally placed. */
90         v = val + 2;
91         ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
92         ok1(tdb_check(tdb, NULL, NULL) == 0);
93
94         /* This will collide with both. */
95         v = val;
96         ok1(tdb_store(tdb, key, data, TDB_INSERT) == 0);
97
98         /* We can still find them all, right? */
99         ok1(tdb_fetch(tdb, key).dsize == data.dsize);
100         v = val + 1;
101         ok1(tdb_fetch(tdb, key).dsize == data.dsize);
102         v = val + 2;
103         ok1(tdb_fetch(tdb, key).dsize == data.dsize);
104
105         /* And if we delete val + 1, that val + 2 should not move! */
106         v = val + 1;
107         ok1(tdb_delete(tdb, key) == 0);
108         ok1(tdb_check(tdb, NULL, NULL) == 0);
109
110         v = val;
111         ok1(tdb_fetch(tdb, key).dsize == data.dsize);
112         v = val + 2;
113         ok1(tdb_fetch(tdb, key).dsize == data.dsize);
114
115         /* Delete those two, so we are empty. */
116         ok1(tdb_delete(tdb, key) == 0);
117         v = val;
118         ok1(tdb_delete(tdb, key) == 0);
119
120         ok1(tdb_check(tdb, NULL, NULL) == 0);
121 }
122
123 int main(int argc, char *argv[])
124 {
125         unsigned int i, j;
126         struct tdb_context *tdb;
127         uint64_t seed = 16014841315512641303ULL;
128         union tdb_attribute clash_hattr
129                 = { .hash = { .base = { TDB_ATTRIBUTE_HASH },
130                               .hash_fn = clash } };
131         union tdb_attribute fixed_hattr
132                 = { .hash = { .base = { TDB_ATTRIBUTE_HASH },
133                               .hash_fn = fixedhash,
134                               .hash_private = &seed } };
135         int flags[] = { TDB_INTERNAL, TDB_DEFAULT, TDB_NOMMAP,
136                         TDB_INTERNAL|TDB_CONVERT, TDB_CONVERT,
137                         TDB_NOMMAP|TDB_CONVERT };
138         /* These two values gave trouble before. */
139         int vals[] = { 755, 837 };
140
141         clash_hattr.base.next = &tap_log_attr;
142         fixed_hattr.base.next = &tap_log_attr;
143
144         plan_tests(sizeof(flags) / sizeof(flags[0])
145                    * (32 * 3 + 5 + sizeof(vals)/sizeof(vals[0])*2) + 1);
146         for (i = 0; i < sizeof(flags) / sizeof(flags[0]); i++) {
147                 tdb = tdb_open("run-13-delete.tdb", flags[i],
148                                O_RDWR|O_CREAT|O_TRUNC, 0600, &clash_hattr);
149                 ok1(tdb);
150                 if (!tdb)
151                         continue;
152
153                 /* Check start of hash table. */
154                 test_val(tdb, 0);
155
156                 /* Check end of hash table. */
157                 test_val(tdb, -1ULL);
158
159                 /* Check mixed bitpattern. */
160                 test_val(tdb, 0x123456789ABCDEF0ULL);
161
162                 ok1(!tdb_has_locks(tdb));
163                 tdb_close(tdb);
164
165                 /* Deleting these entries in the db gave problems. */
166                 tdb = tdb_open("run-13-delete.tdb", flags[i],
167                                O_RDWR|O_CREAT|O_TRUNC, 0600, &fixed_hattr);
168                 ok1(tdb);
169                 if (!tdb)
170                         continue;
171
172                 ok1(store_records(tdb));
173                 ok1(tdb_check(tdb, NULL, NULL) == 0);
174                 for (j = 0; j < sizeof(vals)/sizeof(vals[0]); j++) {
175                         struct tdb_data key;
176
177                         key.dptr = (unsigned char *)&vals[j];
178                         key.dsize = sizeof(vals[j]);
179                         ok1(tdb_delete(tdb, key) == 0);
180                         ok1(tdb_check(tdb, NULL, NULL) == 0);
181                 }
182                 tdb_close(tdb);
183         }
184
185         ok1(tap_log_messages == 0);
186         return exit_status();
187 }