Changeset 3a06cc6 in mainline
- Timestamp:
- 2018-07-05T21:41:20Z (7 years ago)
- Branches:
- lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
- Children:
- 6e93323
- Parents:
- 9475faf
- git-author:
- Dzejrou <dzejrou@…> (2018-04-08 18:39:07)
- git-committer:
- Dzejrou <dzejrou@…> (2018-07-05 21:41:20)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
uspace/lib/cpp/include/impl/deque.hpp
r9475faf r3a06cc6 1 1 /* 2 * Copyright (c) 201 7Jaroslav Jindrak2 * Copyright (c) 2018 Jaroslav Jindrak 3 3 * All rights reserved. 4 4 * … … 31 31 32 32 #include <initializer_list> 33 #include <iterator> 33 34 #include <memory> 34 35 35 36 namespace std 36 37 { 38 template<class T, class Allocator = allocator<T>> 39 class deque; 37 40 38 41 namespace aux … … 41 44 class deque_iterator 42 45 { 43 // TODO: implement 46 using size_type = typename std::deque<T, Allocator>::size_type; 47 using value_type = typename std::deque<T, Allocator>::value_type; 48 using difference_type = size_type; 49 50 public: 51 deque_iterator(deque<T, Allocator>* deq, size_type idx) 52 : deq_{deq}, idx_{idx} 53 { /* DUMMY BODY */ } 54 55 private: 56 deque<T, Allocator>* deq_; 57 size_type idx_; 44 58 }; 45 59 … … 55 69 */ 56 70 57 template<class T, class Allocator = allocator<T>>71 template<class T, class Allocator> 58 72 class deque 59 73 { … … 83 97 84 98 explicit deque(const allocator_type& alloc) 85 { 86 // TODO: implement 99 : allocator_{alloc}, front_bucket_idx_{bucket_size_}, 100 back_bucket_idx_{0}, front_bucket_{default_front_}, 101 back_bucket_{default_back_}, bucket_count_{default_bucket_count_}, 102 bucket_capacity_{default_bucket_capacity_}, size_{}, data_{} 103 { 104 init_(); 87 105 } 88 106 … … 130 148 ~deque() 131 149 { 132 // TODO: implement150 fini_(); 133 151 } 134 152 … … 236 254 size_type size() const noexcept 237 255 { 238 // TODO: implement256 return size_; 239 257 } 240 258 … … 261 279 bool empty() const noexcept 262 280 { 263 // TODO: implement281 return size_ == size_type{}; 264 282 } 265 283 266 284 reference operator[](size_type idx) 267 285 { 268 // TODO: implement269 } 270 271 const_reference operator[](size_type idx) 272 { 273 // TODO: implement286 return data_[get_bucket_index_(idx)][get_element_index_(idx)]; 287 } 288 289 const_reference operator[](size_type idx) const 290 { 291 return data_[get_bucket_index_(idx)][get_element_index_(idx)]; 274 292 } 275 293 … … 279 297 } 280 298 281 const_reference at(size_type idx) 299 const_reference at(size_type idx) const 282 300 { 283 301 // TODO: implement … … 328 346 void push_front(const value_type& value) 329 347 { 330 // TODO: implement 348 if (front_bucket_idx_ == 0) 349 add_new_bucket_front_(); 350 351 data_[front_bucket_][--front_bucket_idx_] = value; 352 ++size_; 331 353 } 332 354 333 355 void push_front(value_type&& value) 334 356 { 335 // TODO: implement 357 if (front_bucket_idx_ == 0) 358 add_new_bucket_front_(); 359 360 data_[front_bucket_][--front_bucket_idx_] = forward<value_type>(value); 361 ++size_; 336 362 } 337 363 338 364 void push_back(const value_type& value) 339 365 { 340 // TODO: implement 366 data_[back_bucket_][back_bucket_idx_++] = value; 367 ++size_; 368 369 if (back_bucket_idx_ >= bucket_size_) 370 add_new_bucket_back_(); 341 371 } 342 372 343 373 void push_back(value_type&& value) 344 374 { 345 // TODO: implement 375 data_[back_bucket_][back_bucket_idx_++] = forward<value_type>(value); 376 ++size_; 377 378 if (back_bucket_idx_ >= bucket_size_) 379 add_new_bucket_back_(); 346 380 } 347 381 … … 374 408 void pop_back() 375 409 { 376 // TODO: implement 410 if (empty()) 411 return; 412 413 if (back_bucket_idx_ == 0) 414 { // Means we gotta pop data_[front_bucket_][bucket_size_ - 1]! 415 if (data_[back_bucket_]) 416 allocator_.deallocate(data_[back_bucket_], bucket_size_); 417 418 --back_bucket_; 419 back_bucket_idx_ = bucket_size_ - 1; 420 } 421 else 422 --back_bucket_idx_; 423 424 allocator_.destroy(&data_[back_bucket_][back_bucket_idx_]); 425 --size_; 377 426 } 378 427 379 428 void pop_front() 380 429 { 381 // TODO: implement 430 if (empty()) 431 return; 432 433 if (front_bucket_idx_ >= bucket_size_) 434 { // Means we gotta pop data_[front_bucket_][0]! 435 if (data_[front_bucket_]) 436 allocator_.deallocate(data_[front_bucket_], bucket_size_); 437 438 ++front_bucket_; 439 front_bucket_idx_ = 1; 440 441 allocator_.destroy(&data_[front_bucket_][0]); 442 } 443 else 444 { 445 allocator_.destroy(&data_[front_bucket_][front_bucket_idx_]); 446 447 ++front_bucket_idx_; 448 } 449 450 --size_; 382 451 } 383 452 … … 387 456 } 388 457 389 iterator erase r(cosnt_iteterator first, const_iterator last)458 iterator erase(const_iterator first, const_iterator last) 390 459 { 391 460 // TODO: implement … … 400 469 void clear() noexcept 401 470 { 402 // TODO: implement 403 } 404 405 private: 471 fini_(); 472 473 front_bucket_ = default_front_; 474 back_bucket_ = default_back_; 475 bucket_count_ = default_bucket_count_; 476 bucket_capacity_ = default_bucket_capacity_; 477 size_ = size_type{}; 478 479 init_(); 480 } 481 482 /* private: */ 406 483 allocator_type allocator_; 407 484 485 /** 486 * Note: In our implementation, front_bucket_idx_ 487 * points at the first element and back_bucket_idx_ 488 * points at the one past last element. Because of this, 489 * some operations may be done in inverse order 490 * depending on the side they are applied to. 491 */ 408 492 size_type front_bucket_idx_; 409 493 size_type back_bucket_idx_; 494 size_type front_bucket_; 495 size_type back_bucket_; 410 496 411 497 static constexpr size_type bucket_size_{16}; 498 static constexpr size_type default_bucket_count_{2}; 499 static constexpr size_type default_bucket_capacity_{4}; 500 static constexpr size_type default_front_{1}; 501 static constexpr size_type default_back_{2}; 412 502 413 503 size_type bucket_count_; 414 504 size_type bucket_capacity_; 505 size_type size_{}; 415 506 416 507 value_type** data_; 508 509 void init_() 510 { 511 data_ = new value_type*[bucket_capacity_]; 512 513 for (size_type i = front_bucket_; i <= back_bucket_; ++i) 514 data_[i] = allocator_.allocate(bucket_size_); 515 } 516 517 void fini_() 518 { 519 for (size_type i = front_bucket_; i <= back_bucket_; ++i) 520 allocator_.deallocate(data_[i], bucket_size_); 521 522 delete[] data_; 523 data_ = nullptr; 524 } 525 526 bool has_bucket_space_back_() const 527 { 528 return back_bucket_ < bucket_capacity_ - 1; 529 } 530 531 bool has_bucket_space_front_() const 532 { 533 return front_bucket_ > 0; 534 } 535 536 void add_new_bucket_back_() 537 { 538 if (!has_bucket_space_back_()) 539 expand_(); 540 541 ++back_bucket_; 542 data_[back_bucket_] = allocator_.allocate(bucket_size_); 543 back_bucket_idx_ = size_type{}; 544 } 545 546 void add_new_bucket_front_() 547 { 548 if (!has_bucket_space_front_()) 549 expand_(); 550 551 --front_bucket_; 552 data_[front_bucket_] = allocator_.allocate(bucket_size_); 553 front_bucket_idx_ = bucket_size_; 554 } 555 556 void expand_() 557 { 558 bucket_capacity_ *= 2; 559 value_type** new_data = new value_type*[bucket_capacity_]; 560 561 size_type new_front = bucket_capacity_ / 4; 562 size_type new_back = bucket_capacity_ - bucket_capacity_ / 4 - 1; 563 564 for (size_type i = new_front, j = front_bucket_; i <= new_back; ++i, ++j) 565 new_data[i] = move(data_[j]); 566 std::swap(data_, new_data); 567 568 delete[] new_data; 569 front_bucket_ = new_front; 570 back_bucket_ = new_back; 571 } 572 573 size_type get_bucket_index_(size_type idx) const 574 { 575 if (idx < elements_in_front_bucket_()) 576 return front_bucket_; 577 578 idx -= elements_in_front_bucket_(); 579 return idx / bucket_size_ + front_bucket_ + 1; 580 } 581 582 size_type get_element_index_(size_type idx) const 583 { 584 if (idx < elements_in_front_bucket_()) 585 return bucket_size_ - elements_in_front_bucket_() + idx; 586 587 idx -= elements_in_front_bucket_(); 588 return idx % bucket_size_; 589 } 590 591 size_type elements_in_front_bucket_() const 592 { 593 return bucket_size_ - front_bucket_idx_; 594 } 417 595 }; 418 596 … … 421 599 { 422 600 // TODO: implement 601 return false; 423 602 } 424 603 … … 427 606 { 428 607 // TODO: implement 429 } 430 431 template<class T, class Allocator> 432 bool operator=!(const deque<T, Allocator>& lhs, const deque<T, Allocator>& rhs) 608 return false; 609 } 610 611 template<class T, class Allocator> 612 bool operator!=(const deque<T, Allocator>& lhs, const deque<T, Allocator>& rhs) 433 613 { 434 614 // TODO: implement 615 return false; 435 616 } 436 617 … … 439 620 { 440 621 // TODO: implement 622 return false; 441 623 } 442 624 … … 445 627 { 446 628 // TODO: implement 629 return false; 447 630 } 448 631 … … 451 634 { 452 635 // TODO: implement 636 return false; 453 637 } 454 638
Note:
See TracChangeset
for help on using the changeset viewer.