| 203 | }; |
| 204 | |
| 205 | void testBePlusTree() |
| 206 | { |
| 207 | MallocAllocator temp; |
| 208 | printf("Test Firebird::BePlusTree\n"); |
| 209 | |
| 210 | printf("Fill array with test data (%d items)...", (int)TEST_ITEMS); |
| 211 | Vector<int, TEST_ITEMS> v; |
| 212 | int n = 0; |
| 213 | FB_SIZE_T i; |
| 214 | for (i = 0; i < TEST_ITEMS; i++) { |
| 215 | n = n * 45578 - 17651; |
| 216 | // Fill it with quasi-random values in range 0...TEST_ITEMS-1 |
| 217 | v.add(((i + n) % TEST_ITEMS + TEST_ITEMS) / 2); |
| 218 | } |
| 219 | printf(" DONE\n"); |
| 220 | |
| 221 | printf("Create two trees and fill them with test data: "); |
| 222 | BePlusTree<Test, int, MallocAllocator, Test, |
| 223 | DefaultComparator<int> > tree1(&temp); |
| 224 | BePlusTree<Test, int, MallocAllocator, Test, |
| 225 | DefaultComparator<int> > tree2(&temp); |
| 226 | int cnt1 = 0, cnt2 = 0; |
| 227 | for (i = 0; i < v.getCount(); i++) |
| 228 | { |
| 229 | if (tree1.locate(locEqual, v[i])) |
| 230 | tree1.current().count++; |
| 231 | else { |
| 232 | Test t; |
| 233 | t.value = v[i]; |
| 234 | t.count = 1; |
| 235 | if (!tree1.add(t)) |
| 236 | fb_assert(false); |
| 237 | cnt1++; |
| 238 | } |
| 239 | if (tree2.locate(locEqual, v[i])) |
| 240 | tree2.current().count++; |
| 241 | else { |
| 242 | Test t; |
| 243 | t.value = v[i]; |
| 244 | t.count = 1; |
| 245 | if (!tree2.add(t)) |
| 246 | fb_assert(false); |
| 247 | cnt2++; |
| 248 | } |
| 249 | } |
| 250 | printf(" DONE\n"); |
| 251 | |
| 252 | bool passed = true; |
| 253 | |
| 254 | printf("Empty trees verifying fastRemove() result: "); |
| 255 | for (i = 0; i < v.getCount()-1; i++) |
| 256 | { |
| 257 | if (!tree1.getLast()) |
| 258 | passed = false; |
| 259 | tree1.current().count--; |
| 260 | if (!tree1.current().count) |
| 261 | if (tree1.fastRemove()) |
| 262 | passed = false; |