Chromium Code Reviews| OLD | NEW |
|---|---|
| 1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 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 | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 library index.page_node_manager; | 5 library index.page_node_manager; |
| 6 | 6 |
| 7 import 'dart:collection'; | 7 import 'dart:collection'; |
| 8 import 'dart:typed_data'; | 8 import 'dart:typed_data'; |
| 9 | 9 |
| 10 import 'package:analysis_server/src/index/lru_cache.dart'; | 10 import 'package:analysis_server/src/index/lru_cache.dart'; |
| (...skipping 166 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
| 177 throw new StateError('Page $id has been already freed.'); | 177 throw new StateError('Page $id has been already freed.'); |
| 178 } | 178 } |
| 179 } | 179 } |
| 180 | 180 |
| 181 @override | 181 @override |
| 182 Uint8List read(int id) { | 182 Uint8List read(int id) { |
| 183 Uint8List page = _pages[id]; | 183 Uint8List page = _pages[id]; |
| 184 if (page == null) { | 184 if (page == null) { |
| 185 throw new StateError('Page $id does not exist.'); | 185 throw new StateError('Page $id does not exist.'); |
| 186 } | 186 } |
| 187 return page; | 187 return page; |
|
Paul Berry
2014/06/10 20:23:40
If the client is allowed to modify the page, then
scheglov
2014/06/10 20:36:55
Done.
| |
| 188 } | 188 } |
| 189 | 189 |
| 190 @override | 190 @override |
| 191 void write(int id, Uint8List page) { | 191 void write(int id, Uint8List page) { |
| 192 if (!_pages.containsKey(id)) { | 192 if (!_pages.containsKey(id)) { |
| 193 throw new StateError('Page $id does not exist.'); | 193 throw new StateError('Page $id does not exist.'); |
| 194 } | 194 } |
| 195 if (page.length != pageSizeInBytes) { | |
| 196 throw new ArgumentError('Page $id has length ${page.length}, ' | |
| 197 'but $pageSizeInBytes is expected.'); | |
| 198 } | |
| 195 _pages[id] = page; | 199 _pages[id] = page; |
| 196 } | 200 } |
| 197 } | 201 } |
| 198 | 202 |
| 199 | 203 |
| 200 /** | 204 /** |
| 201 * [PageManager] allows to allocate, read, write and free [Uint8List] pages. | 205 * [PageManager] allows to allocate, read, write and free [Uint8List] pages. |
| 202 */ | 206 */ |
| 203 abstract class PageManager { | 207 abstract class PageManager { |
| 204 /** | 208 /** |
| 205 * The size of pages provided by this [PageManager]. | 209 * The size of pages provided by this [PageManager]. |
| 206 */ | 210 */ |
| 207 int get pageSizeInBytes; | 211 int get pageSizeInBytes; |
| 208 | 212 |
| 209 /** | 213 /** |
| 210 * Allocates a new page and returns its identifier. | 214 * Allocates a new page and returns its identifier. |
| 211 */ | 215 */ |
| 212 int alloc(); | 216 int alloc(); |
| 213 | 217 |
| 214 /** | 218 /** |
| 215 * Frees the page with the given identifier. | 219 * Frees the page with the given identifier. |
| 216 */ | 220 */ |
| 217 void free(int id); | 221 void free(int id); |
| 218 | 222 |
| 219 /** | 223 /** |
| 220 * Reads the page with the given identifier and returns its content. | 224 * Reads the page with the given identifier and returns its content. |
| 225 * The client may modify this page and [write] it later. | |
| 221 */ | 226 */ |
| 222 Uint8List read(int id); | 227 Uint8List read(int id); |
| 223 | 228 |
| 224 /** | 229 /** |
| 225 * Writes the given page. | 230 * Writes the given page. |
| 226 */ | 231 */ |
| 227 void write(int id, Uint8List page); | 232 void write(int id, Uint8List page); |
| 228 } | 233 } |
| 229 | 234 |
| 230 | 235 |
| 231 /** | 236 /** |
| 232 * A [NodeManager] that keeps nodes in [PageManager]. | 237 * A [NodeManager] that keeps nodes in [PageManager]. |
| 233 */ | 238 */ |
| 234 class PageNodeManager<K, V> implements NodeManager<K, V, int> { | 239 class PageNodeManager<K, V> implements NodeManager<K, V, int> { |
| 235 static const int INDEX_OFFSET_DATA = 4; | 240 static const int _INDEX_OFFSET_DATA = 4; |
| 236 static const int INDEX_OFFSET_KEY_COUNT = 0; | 241 static const int _INDEX_OFFSET_KEY_COUNT = 0; |
| 237 static const int LEAF_OFFSET_DATA = 4; | 242 static const int _LEAF_OFFSET_DATA = 4; |
| 238 static const int LEAF_OFFSET_KEY_COUNT = 0; | 243 static const int _LEAF_OFFSET_KEY_COUNT = 0; |
| 239 | 244 |
| 240 final Set<int> _indexPages = new HashSet<int>(); | 245 final Set<int> _indexPages = new HashSet<int>(); |
| 241 Codec<K> _keyCodec; | 246 Codec<K> _keyCodec; |
| 242 final Set<int> _leafPages = new HashSet<int>(); | 247 final Set<int> _leafPages = new HashSet<int>(); |
| 243 PageManager _pageManager; | 248 PageManager _pageManager; |
| 244 Codec<V> _valueCodec; | 249 Codec<V> _valueCodec; |
| 245 | 250 |
| 246 PageNodeManager(this._pageManager, this._keyCodec, this._valueCodec); | 251 PageNodeManager(this._pageManager, this._keyCodec, this._valueCodec); |
| 247 | 252 |
| 248 @override | 253 @override |
| 249 int get maxIndexKeys { | 254 int get maxIndexKeys { |
| 250 int keySize = _keyCodec.sizeInBytes; | 255 int keySize = _keyCodec.sizeInBytes; |
| 251 int childSize = 4; | 256 int childSize = 4; |
| 252 int dataSize = _pageManager.pageSizeInBytes - INDEX_OFFSET_DATA; | 257 int dataSize = _pageManager.pageSizeInBytes - _INDEX_OFFSET_DATA; |
| 253 return (dataSize - childSize) ~/ (keySize + childSize); | 258 return (dataSize - childSize) ~/ (keySize + childSize); |
| 254 } | 259 } |
| 255 | 260 |
| 256 @override | 261 @override |
| 257 int get maxLeafKeys { | 262 int get maxLeafKeys { |
| 258 int keySize = _keyCodec.sizeInBytes; | 263 int keySize = _keyCodec.sizeInBytes; |
| 259 int valueSize = _valueCodec.sizeInBytes; | 264 int valueSize = _valueCodec.sizeInBytes; |
| 260 int dataSize = _pageManager.pageSizeInBytes - INDEX_OFFSET_DATA; | 265 int dataSize = _pageManager.pageSizeInBytes - _INDEX_OFFSET_DATA; |
| 261 return dataSize ~/ (keySize + valueSize); | 266 return dataSize ~/ (keySize + valueSize); |
| 262 } | 267 } |
| 263 | 268 |
| 264 @override | 269 @override |
| 265 int createIndex() { | 270 int createIndex() { |
| 266 int id = _pageManager.alloc(); | 271 int id = _pageManager.alloc(); |
| 267 _indexPages.add(id); | 272 _indexPages.add(id); |
| 268 return id; | 273 return id; |
| 269 } | 274 } |
| 270 | 275 |
| (...skipping 16 matching lines...) Expand all Loading... | |
| 287 return _indexPages.contains(id); | 292 return _indexPages.contains(id); |
| 288 } | 293 } |
| 289 | 294 |
| 290 @override | 295 @override |
| 291 IndexNodeData<K, int> readIndex(int id) { | 296 IndexNodeData<K, int> readIndex(int id) { |
| 292 Uint8List page = _pageManager.read(id); | 297 Uint8List page = _pageManager.read(id); |
| 293 // read header | 298 // read header |
| 294 int keyCount; | 299 int keyCount; |
| 295 { | 300 { |
| 296 ByteData data = new ByteData.view(page.buffer); | 301 ByteData data = new ByteData.view(page.buffer); |
| 297 keyCount = data.getInt32(INDEX_OFFSET_KEY_COUNT); | 302 keyCount = data.getInt32(_INDEX_OFFSET_KEY_COUNT); |
| 298 } | 303 } |
| 299 // read keys/children | 304 // read keys/children |
| 300 List<K> keys = new List<K>(); | 305 List<K> keys = new List<K>(); |
| 301 List<int> children = new List<int>(); | 306 List<int> children = new List<int>(); |
| 302 int keySize = _keyCodec.sizeInBytes; | 307 int keySize = _keyCodec.sizeInBytes; |
| 303 int offset = INDEX_OFFSET_DATA; | 308 int offset = _INDEX_OFFSET_DATA; |
| 304 for (int i = 0; i < keyCount; i++) { | 309 for (int i = 0; i < keyCount; i++) { |
| 305 // read child | 310 // read child |
| 306 { | 311 { |
| 307 ByteData byteData = new ByteData.view(page.buffer, offset); | 312 ByteData byteData = new ByteData.view(page.buffer, offset); |
| 308 int childPage = byteData.getUint32(0); | 313 int childPage = byteData.getUint32(0); |
| 309 children.add(childPage); | 314 children.add(childPage); |
| 310 offset += 4; | 315 offset += 4; |
| 311 } | 316 } |
| 312 // read key | 317 // read key |
| 313 { | 318 { |
| (...skipping 13 matching lines...) Expand all Loading... | |
| 327 return new IndexNodeData<K, int>(keys, children); | 332 return new IndexNodeData<K, int>(keys, children); |
| 328 } | 333 } |
| 329 | 334 |
| 330 @override | 335 @override |
| 331 LeafNodeData<K, V> readLeaf(int id) { | 336 LeafNodeData<K, V> readLeaf(int id) { |
| 332 Uint8List page = _pageManager.read(id); | 337 Uint8List page = _pageManager.read(id); |
| 333 // read header | 338 // read header |
| 334 int keyCount; | 339 int keyCount; |
| 335 { | 340 { |
| 336 ByteData data = new ByteData.view(page.buffer); | 341 ByteData data = new ByteData.view(page.buffer); |
| 337 keyCount = data.getInt32(LEAF_OFFSET_KEY_COUNT); | 342 keyCount = data.getInt32(_LEAF_OFFSET_KEY_COUNT); |
| 338 } | 343 } |
| 339 // read keys/children | 344 // read keys/children |
| 340 List<K> keys = new List<K>(); | 345 List<K> keys = new List<K>(); |
| 341 List<V> values = new List<V>(); | 346 List<V> values = new List<V>(); |
| 342 int keySize = _keyCodec.sizeInBytes; | 347 int keySize = _keyCodec.sizeInBytes; |
| 343 int valueSize = _valueCodec.sizeInBytes; | 348 int valueSize = _valueCodec.sizeInBytes; |
| 344 int offset = LEAF_OFFSET_DATA; | 349 int offset = _LEAF_OFFSET_DATA; |
| 345 for (int i = 0; i < keyCount; i++) { | 350 for (int i = 0; i < keyCount; i++) { |
| 346 // read key | 351 // read key |
| 347 { | 352 { |
| 348 ByteData byteData = new ByteData.view(page.buffer, offset, keySize); | 353 ByteData byteData = new ByteData.view(page.buffer, offset, keySize); |
| 349 K key = _keyCodec.decode(byteData); | 354 K key = _keyCodec.decode(byteData); |
| 350 keys.add(key); | 355 keys.add(key); |
| 351 offset += keySize; | 356 offset += keySize; |
| 352 } | 357 } |
| 353 // read value | 358 // read value |
| 354 { | 359 { |
| 355 ByteData byteData = new ByteData.view(page.buffer, offset); | 360 ByteData byteData = new ByteData.view(page.buffer, offset); |
| 356 V value = _valueCodec.decode(byteData); | 361 V value = _valueCodec.decode(byteData); |
| 357 values.add(value); | 362 values.add(value); |
| 358 offset += valueSize; | 363 offset += valueSize; |
| 359 } | 364 } |
| 360 } | 365 } |
| 361 // done | 366 // done |
| 362 return new LeafNodeData<K, V>(keys, values); | 367 return new LeafNodeData<K, V>(keys, values); |
| 363 } | 368 } |
| 364 | 369 |
| 365 @override | 370 @override |
| 366 void writeIndex(int id, IndexNodeData<K, int> data) { | 371 void writeIndex(int id, IndexNodeData<K, int> data) { |
| 367 Uint8List page = new Uint8List(_pageManager.pageSizeInBytes); | 372 Uint8List page = new Uint8List(_pageManager.pageSizeInBytes); |
| 368 // write header | 373 // write header |
| 369 int keyCount = data.keys.length; | 374 int keyCount = data.keys.length; |
| 370 { | 375 { |
| 371 ByteData byteData = new ByteData.view(page.buffer); | 376 ByteData byteData = new ByteData.view(page.buffer); |
| 372 byteData.setUint32(PageNodeManager.INDEX_OFFSET_KEY_COUNT, keyCount); | 377 byteData.setUint32(PageNodeManager._INDEX_OFFSET_KEY_COUNT, keyCount); |
| 373 } | 378 } |
| 374 // write keys/children | 379 // write keys/children |
| 375 int keySize = _keyCodec.sizeInBytes; | 380 int keySize = _keyCodec.sizeInBytes; |
| 376 int offset = PageNodeManager.INDEX_OFFSET_DATA; | 381 int offset = PageNodeManager._INDEX_OFFSET_DATA; |
| 377 for (int i = 0; i < keyCount; i++) { | 382 for (int i = 0; i < keyCount; i++) { |
| 378 // write child | 383 // write child |
| 379 { | 384 { |
| 380 ByteData byteData = new ByteData.view(page.buffer, offset); | 385 ByteData byteData = new ByteData.view(page.buffer, offset); |
| 381 byteData.setUint32(0, data.children[i]); | 386 byteData.setUint32(0, data.children[i]); |
| 382 offset += 4; | 387 offset += 4; |
| 383 } | 388 } |
| 384 // write key | 389 // write key |
| 385 { | 390 { |
| 386 ByteData byteData = new ByteData.view(page.buffer, offset, keySize); | 391 ByteData byteData = new ByteData.view(page.buffer, offset, keySize); |
| (...skipping 10 matching lines...) Expand all Loading... | |
| 397 _pageManager.write(id, page); | 402 _pageManager.write(id, page); |
| 398 } | 403 } |
| 399 | 404 |
| 400 @override | 405 @override |
| 401 void writeLeaf(int id, LeafNodeData<K, V> data) { | 406 void writeLeaf(int id, LeafNodeData<K, V> data) { |
| 402 Uint8List page = new Uint8List(_pageManager.pageSizeInBytes); | 407 Uint8List page = new Uint8List(_pageManager.pageSizeInBytes); |
| 403 // write header | 408 // write header |
| 404 int keyCount = data.keys.length; | 409 int keyCount = data.keys.length; |
| 405 { | 410 { |
| 406 ByteData byteData = new ByteData.view(page.buffer); | 411 ByteData byteData = new ByteData.view(page.buffer); |
| 407 byteData.setUint32(PageNodeManager.LEAF_OFFSET_KEY_COUNT, keyCount); | 412 byteData.setUint32(PageNodeManager._LEAF_OFFSET_KEY_COUNT, keyCount); |
| 408 } | 413 } |
| 409 // write keys/values | 414 // write keys/values |
| 410 int keySize = _keyCodec.sizeInBytes; | 415 int keySize = _keyCodec.sizeInBytes; |
| 411 int valueSize = _valueCodec.sizeInBytes; | 416 int valueSize = _valueCodec.sizeInBytes; |
| 412 int offset = PageNodeManager.LEAF_OFFSET_DATA; | 417 int offset = PageNodeManager._LEAF_OFFSET_DATA; |
| 413 for (int i = 0; i < keyCount; i++) { | 418 for (int i = 0; i < keyCount; i++) { |
| 414 // write key | 419 // write key |
| 415 { | 420 { |
| 416 ByteData byteData = new ByteData.view(page.buffer, offset, keySize); | 421 ByteData byteData = new ByteData.view(page.buffer, offset, keySize); |
| 417 _keyCodec.encode(byteData, data.keys[i]); | 422 _keyCodec.encode(byteData, data.keys[i]); |
| 418 offset += keySize; | 423 offset += keySize; |
| 419 } | 424 } |
| 420 // write value | 425 // write value |
| 421 { | 426 { |
| 422 ByteData byteData = new ByteData.view(page.buffer, offset); | 427 ByteData byteData = new ByteData.view(page.buffer, offset); |
| (...skipping 21 matching lines...) Expand all Loading... | |
| 444 @override | 449 @override |
| 445 int decode(ByteData buffer) { | 450 int decode(ByteData buffer) { |
| 446 return buffer.getUint32(0); | 451 return buffer.getUint32(0); |
| 447 } | 452 } |
| 448 | 453 |
| 449 @override | 454 @override |
| 450 void encode(ByteData buffer, int element) { | 455 void encode(ByteData buffer, int element) { |
| 451 buffer.setUint32(0, element); | 456 buffer.setUint32(0, element); |
| 452 } | 457 } |
| 453 } | 458 } |
| OLD | NEW |