Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(102)

Issues Search
    My Issues | Starred     Open | Closed | All

Side by Side Diff: pkg/analysis_server/test/index/page_node_manager_test.dart

Issue 365193004: Move Index and IndexStore implementations into Engine. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Created 6 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« pkg/analysis_server/pubspec.yaml ('K') | « pkg/analysis_server/test/index/lru_cache_test.dart ('k') | pkg/analysis_server/test/index/store/codec_test.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file
2 // for details. All rights reserved. Use of this source code is governed by a
3 // BSD-style license that can be found in the LICENSE file.
4
5 library test.index.page_node_manager;
6
7 import 'dart:math';
8 import 'dart:typed_data';
9
10 import 'package:analysis_server/src/index/b_plus_tree.dart';
11 import 'package:analysis_server/src/index/page_node_manager.dart';
12 import 'package:typed_mock/typed_mock.dart';
13 import 'package:unittest/unittest.dart';
14
15 import '../reflective_tests.dart';
16
17
18 main() {
19 groupSep = ' | ';
20 group('_CachingNodeManagerTest', () {
21 runReflectiveTests(_CachingNodeManagerTest);
22 });
23 group('FixedStringCodecTest', () {
24 runReflectiveTests(_FixedStringCodecTest);
25 });
26 group('MemoryPageManager', () {
27 runReflectiveTests(_MemoryPageManagerTest);
28 });
29 group('PageNodeManager', () {
30 runReflectiveTests(_PageNodeManagerTest);
31 });
32 group('Uint32CodecTest', () {
33 runReflectiveTests(_Uint32CodecTest);
34 });
35 test('B+ tree with PageNodeManager', _treeWithPageNodeManager);
36 }
37
38
39 int _intComparator(int a, int b) => a - b;
40
41
42 /**
43 * A stress test for [BPlusTree] using [PageNodeManager].
44 */
45 _treeWithPageNodeManager() {
46 int pageSize = 256;
47 MemoryPageManager pageManager = new MemoryPageManager(pageSize);
48 NodeManager<int, String, int> nodeManager = new PageNodeManager<int, String>(
49 pageManager, Uint32Codec.INSTANCE, new FixedStringCodec(7));
50 // NodeManager<int, String, int> nodeManager = new MemoryNodeManager();
51 BPlusTree<int, String, int> tree = new BPlusTree(_intComparator, nodeManager);
52 int maxKey = 1000000;
53 int tryCount = 1000;
54 Set<int> keys = new Set<int>();
55 {
56 Random random = new Random(37);
57 for (int i = 0; i < tryCount; i++) {
58 int key = random.nextInt(maxKey);
59 keys.add(key);
60 tree.insert(key, 'V$key');
61 }
62 }
63 // find every
64 for (int key in keys) {
65 expect(tree.find(key), 'V$key');
66 }
67 // remove random keys
68 {
69 Random random = new Random(37);
70 for (int key in new Set<int>.from(keys)) {
71 if (random.nextBool()) {
72 keys.remove(key);
73 expect(tree.remove(key), 'V$key');
74 }
75 }
76 }
77 // find every remaining key
78 for (int key in keys) {
79 expect(tree.find(key), 'V$key');
80 }
81 }
82
83
84 @ReflectiveTestCase()
85 class _CachingNodeManagerTest {
86 _NodeManagerMock<int, String, int> delegate = new _NodeManagerMock<int,
87 String, int>();
88 NodeManager<int, String, int> manager;
89
90 void setUp() {
91 when(delegate.writeIndex).thenReturn((key, value) {
92 delegate.writeIndex(key, value);
93 });
94 when(delegate.writeLeaf).thenReturn((key, value) {
95 delegate.writeLeaf(key, value);
96 });
97 manager = new CachingNodeManager<int, String, int>(delegate, 4, 4);
98 resetInteractions(delegate);
99 }
100
101 void test_createIndex() {
102 when(delegate.createIndex()).thenReturn(77);
103 expect(manager.createIndex(), 77);
104 }
105
106 void test_createLeaf() {
107 when(delegate.createLeaf()).thenReturn(99);
108 expect(manager.createLeaf(), 99);
109 }
110
111 void test_delete() {
112 manager.delete(42);
113 verify(delegate.delete(42)).once();
114 }
115
116 void test_isIndex() {
117 when(delegate.isIndex(1)).thenReturn(true);
118 when(delegate.isIndex(2)).thenReturn(false);
119 expect(manager.isIndex(1), isTrue);
120 expect(manager.isIndex(2), isFalse);
121 }
122
123 void test_maxIndexKeys() {
124 when(delegate.maxIndexKeys).thenReturn(42);
125 expect(manager.maxIndexKeys, 42);
126 }
127
128 void test_maxLeafKeys() {
129 when(delegate.maxLeafKeys).thenReturn(42);
130 expect(manager.maxLeafKeys, 42);
131 }
132
133 void test_readIndex_cache_whenRead() {
134 var data = new IndexNodeData<int, int>([1, 2], [10, 20, 30]);
135 when(delegate.readIndex(2)).thenReturn(data);
136 expect(manager.readIndex(2), data);
137 verify(delegate.readIndex(2)).once();
138 resetInteractions(delegate);
139 // we just read "2", so it should be cached
140 manager.readIndex(2);
141 verify(delegate.readIndex(2)).never();
142 }
143
144 void test_readIndex_cache_whenWrite() {
145 var data = new IndexNodeData<int, int>([1, 2], [10, 20, 30]);
146 manager.writeIndex(2, data);
147 expect(manager.readIndex(2), data);
148 verify(delegate.readLeaf(2)).never();
149 // delete, forces request to the delegate
150 manager.delete(2);
151 manager.readIndex(2);
152 verify(delegate.readIndex(2)).once();
153 }
154
155 void test_readIndex_delegate() {
156 var data = new IndexNodeData<int, int>([1, 2], [10, 20, 30]);
157 when(delegate.readIndex(2)).thenReturn(data);
158 expect(manager.readIndex(2), data);
159 }
160
161 void test_readLeaf_cache_whenRead() {
162 var data = new LeafNodeData<int, String>([1, 2, 3], ['A', 'B', 'C']);
163 when(delegate.readLeaf(2)).thenReturn(data);
164 expect(manager.readLeaf(2), data);
165 verify(delegate.readLeaf(2)).once();
166 resetInteractions(delegate);
167 // we just read "2", so it should be cached
168 manager.readLeaf(2);
169 verify(delegate.readLeaf(2)).never();
170 }
171
172 void test_readLeaf_cache_whenWrite() {
173 var data = new LeafNodeData<int, String>([1, 2, 3], ['A', 'B', 'C']);
174 manager.writeLeaf(2, data);
175 expect(manager.readLeaf(2), data);
176 verify(delegate.readLeaf(2)).never();
177 // delete, forces request to the delegate
178 manager.delete(2);
179 manager.readLeaf(2);
180 verify(delegate.readLeaf(2)).once();
181 }
182
183 void test_readLeaf_delegate() {
184 var data = new LeafNodeData<int, String>([1, 2, 3], ['A', 'B', 'C']);
185 when(delegate.readLeaf(2)).thenReturn(data);
186 expect(manager.readLeaf(2), data);
187 }
188
189 void test_writeIndex() {
190 var data = new IndexNodeData<int, int>([1], [10, 20]);
191 manager.writeIndex(1, data);
192 manager.writeIndex(2, data);
193 manager.writeIndex(3, data);
194 manager.writeIndex(4, data);
195 manager.writeIndex(1, data);
196 verifyZeroInteractions(delegate);
197 // only 4 nodes can be cached, 5-th one cause write to the delegate
198 manager.writeIndex(5, data);
199 verify(delegate.writeIndex(2, data)).once();
200 }
201
202 void test_writeLeaf() {
203 var data = new LeafNodeData<int, String>([1, 2], ['A', 'B']);
204 manager.writeLeaf(1, data);
205 manager.writeLeaf(2, data);
206 manager.writeLeaf(3, data);
207 manager.writeLeaf(4, data);
208 manager.writeLeaf(1, data);
209 verifyZeroInteractions(delegate);
210 // only 4 nodes can be cached, 5-th one cause write to the delegate
211 manager.writeLeaf(5, data);
212 verify(delegate.writeLeaf(2, data)).once();
213 }
214 }
215
216
217 @ReflectiveTestCase()
218 class _FixedStringCodecTest {
219 ByteData buffer;
220 Uint8List bytes = new Uint8List(2 + 2 * 4);
221 FixedStringCodec codec = new FixedStringCodec(4);
222
223 void setUp() {
224 buffer = new ByteData.view(bytes.buffer);
225 }
226
227 test_empty() {
228 // encode
229 codec.encode(buffer, '');
230 expect(bytes, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]);
231 // decode
232 expect(codec.decode(buffer), '');
233 }
234
235 test_fourChars() {
236 // encode
237 codec.encode(buffer, 'ABCD');
238 expect(bytes, [0, 4, 0, 65, 0, 66, 0, 67, 0, 68]);
239 // decode
240 expect(codec.decode(buffer), 'ABCD');
241 }
242
243 test_russian() {
244 // encode
245 codec.encode(buffer, 'ЩУКА');
246 expect(bytes, [0, 4, 4, 41, 4, 35, 4, 26, 4, 16]);
247 // decode
248 expect(codec.decode(buffer), 'ЩУКА');
249 }
250
251 test_tooManyChars() {
252 expect(() {
253 codec.encode(buffer, 'ABCDE');
254 }, throws);
255 }
256
257 test_twoChars() {
258 // encode
259 codec.encode(buffer, 'AB');
260 expect(bytes, [0, 2, 0, 65, 0, 66, 0, 0, 0, 0]);
261 // decode
262 expect(codec.decode(buffer), 'AB');
263 }
264 }
265
266
267 @ReflectiveTestCase()
268 class _MemoryPageManagerTest {
269 static const PAGE_SIZE = 8;
270 MemoryPageManager manager = new MemoryPageManager(PAGE_SIZE);
271
272 test_alloc() {
273 int idA = manager.alloc();
274 int idB = manager.alloc();
275 expect(idB, isNot(idA));
276 }
277
278 test_free() {
279 int id = manager.alloc();
280 manager.free(id);
281 // double free
282 expect(() {
283 manager.free(id);
284 }, throws);
285 }
286
287 test_read() {
288 int id = manager.alloc();
289 Uint8List page = manager.read(id);
290 expect(page.length, PAGE_SIZE);
291 }
292
293 test_read_doesNotExist() {
294 expect(() {
295 manager.read(0);
296 }, throws);
297 }
298
299 test_write() {
300 int id = manager.alloc();
301 // do write
302 {
303 Uint8List page = new Uint8List(PAGE_SIZE);
304 page[3] = 42;
305 manager.write(id, page);
306 }
307 // now read
308 {
309 Uint8List page = manager.read(id);
310 expect(page.length, PAGE_SIZE);
311 expect(page[3], 42);
312 }
313 }
314
315 test_write_doesNotExist() {
316 expect(() {
317 Uint8List page = new Uint8List(PAGE_SIZE);
318 manager.write(42, page);
319 }, throws);
320 }
321
322 test_write_invalidLength() {
323 int id = manager.alloc();
324 Uint8List page = new Uint8List(0);
325 expect(() {
326 manager.write(id, page);
327 }, throws);
328 }
329 }
330
331
332
333 class _NodeManagerMock<K, V, N> extends TypedMock implements NodeManager<K, V,
334 N> {
335 noSuchMethod(Invocation invocation) => super.noSuchMethod(invocation);
336 }
337
338
339
340 @ReflectiveTestCase()
341 class _PageNodeManagerTest {
342 static const Codec KEY_CODEC = Uint32Codec.INSTANCE;
343 static const int PAGE_SIZE = 128;
344 static const Codec VALUE_CODEC = const FixedStringCodec(4);
345
346 PageNodeManager<int, String> nodeManager;
347 MemoryPageManager pageManager = new MemoryPageManager(PAGE_SIZE);
348
349 setUp() {
350 nodeManager = new PageNodeManager<int, String>(pageManager, KEY_CODEC,
351 VALUE_CODEC);
352 }
353
354 test_index_createDelete() {
355 int id = nodeManager.createIndex();
356 expect(nodeManager.isIndex(id), isTrue);
357 // do delete
358 nodeManager.delete(id);
359 expect(nodeManager.isIndex(id), isFalse);
360 }
361
362 test_index_readWrite() {
363 int id = nodeManager.createIndex();
364 expect(nodeManager.isIndex(id), isTrue);
365 // write
366 {
367 var keys = [1, 2];
368 var children = [10, 20, 30];
369 nodeManager.writeIndex(id, new IndexNodeData<int, int>(keys, children));
370 }
371 // check the page
372 {
373 Uint8List page = pageManager.read(id);
374 expect(page, [0, 0, 0, 2, 0, 0, 0, 10, 0, 0, 0, 1, 0, 0, 0, 20, 0, 0, 0,
375 2, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
376 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0,
377 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0,
378 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0,
379 0, 0]);
380 }
381 // read
382 {
383 IndexNodeData<int, int> data = nodeManager.readIndex(id);
384 expect(data.keys, [1, 2]);
385 expect(data.children, [10, 20, 30]);
386 }
387 }
388
389 test_leaf_readWrite() {
390 int id = nodeManager.createLeaf();
391 expect(nodeManager.isIndex(id), isFalse);
392 // write
393 {
394 var keys = [1, 2, 3];
395 var children = ['A', 'BB', 'CCC'];
396 nodeManager.writeLeaf(id, new LeafNodeData<int, String>(keys, children));
397 }
398 // check the page
399 {
400 Uint8List page = pageManager.read(id);
401 expect(page, [0, 0, 0, 3, 0, 0, 0, 1, 0, 1, 0, 65, 0, 0, 0, 0, 0, 0, 0, 0,
402 0, 2, 0, 2, 0, 66, 0, 66, 0, 0, 0, 0, 0, 0, 0, 3, 0, 3, 0, 67, 0, 67, 0, 67, 0,
403 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0,
404 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0,
405 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0,
406 0, 0]);
407 }
408 // read
409 {
410 LeafNodeData<int, String> data = nodeManager.readLeaf(id);
411 expect(data.keys, [1, 2, 3]);
412 expect(data.values, ['A', 'BB', 'CCC']);
413 }
414 }
415 }
416
417 @ReflectiveTestCase()
418 class _Uint32CodecTest {
419 ByteData buffer;
420 Uint8List bytes = new Uint8List(4);
421 Uint32Codec codec = Uint32Codec.INSTANCE;
422
423 void setUp() {
424 buffer = new ByteData.view(bytes.buffer);
425 }
426
427 test_all() {
428 // encode
429 codec.encode(buffer, 42);
430 expect(bytes, [0, 0, 0, 42]);
431 // decode
432 expect(codec.decode(buffer), 42);
433 }
434 }
OLDNEW
« pkg/analysis_server/pubspec.yaml ('K') | « pkg/analysis_server/test/index/lru_cache_test.dart ('k') | pkg/analysis_server/test/index/store/codec_test.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698