Index: uspace/lib/cpp/include/impl/list.hpp =================================================================== --- uspace/lib/cpp/include/impl/list.hpp (revision df47833d36b630392883ffb2f7f8ba212e7a0266) +++ uspace/lib/cpp/include/impl/list.hpp (revision df47833d36b630392883ffb2f7f8ba212e7a0266) @@ -0,0 +1,171 @@ +/* + * Copyright (c) 2017 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#ifndef LIBCPP_LIST +#define LIBCPP_LIST + +#include +#include +#include + +namespace cpp +{ + namespace aux + { + template + struct list_node + { + T value; + list_node* next; + list_node* prev; + }; + } + + /** + * 23.3.5, class template list: + */ + + template> + class list + { + public: + using value_type = T; + using reference = value_type&; + using const_reference = value_type&; + using allocator_type = Allocator; + + using iterator = void; + using const_iterator = void; + using size_type = void; + using difference_type = void; + + using pointer = typename allocator_traits::pointer; + using const_pointer = typename allocator_traits::const_pointer; + + using reverse_iterator = std::reverse_iterator; + using const_reverse_iterator = std::const_reverse_iterator; + + /** + * 23.3.5.2, construct/copy/destroy: + */ + + list() + : list{allocator_type{}} + { /* DUMMY BODY */ } + + explicit list(const allocator_type& alloc) + : allocator_{alloc}, head_{nullptr} + { /* DUMMY BODY */ } + + explicit list(size_type n, const allocator_type& alloc = allocator_type{}) + : allocator_{alloc}, head_{nullptr} + { + for (size_type i = 0; i < n; ++i) + { + auto node = append_new_(); + allocator_.construct(&node->value); + } + } + + list(size_type n, const value_type& val, + const allocator_type& alloc = allocator_type{}) + : allocator_{alloc}, head_{nullptr} + { + for (size_type i = 0; i < n; ++i) + { + auto node = append_new_(); + allocator_.construct(&node->value, val); + } + } + + template + list(InputIterator first, InputIterator last, + const allocator_type& alloc = allocator_type{}) + : allocator_{alloc}, head_{nullptr} + { + while (first != last) + { + auto node = append_new_(); + allocator_.construct(&node->value, *first++); + } + } + + list(const list& other) + : allocator_{other.allocator_}, head_{nullptr} + { + auto tmp = other.head_; + + while (tmp->next != other.head_) + { + auto node = append_new_(); + allocator_.construct(&node->value, tmp->value); + } + } + + list(list&& other) + { + // TODO: + } + + private: + allocator_type allocator_; + list_node* head_; + + list_node* append_new_() + { + auto node = new aux::list_node{}; + auto last = get_last_(); + + if (!last) + head_ = node; + else + { + last->next = node; + node->prev = last; + + node->next = head_; + head_->prev = node; + } + + return node; + } + + list_node* get_last_() + { + if (!head_) + return nullptr; + + auto node = head_; + + while (node->next != head_) + node = node->next; + } + }; +} + +#endif Index: uspace/lib/cpp/include/list =================================================================== --- uspace/lib/cpp/include/list (revision df47833d36b630392883ffb2f7f8ba212e7a0266) +++ uspace/lib/cpp/include/list (revision df47833d36b630392883ffb2f7f8ba212e7a0266) @@ -0,0 +1,29 @@ +/* + * Copyright (c) 2017 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include