From 2cd79a3fd753af70c822c72a4a1c64b5ba510779 Mon Sep 17 00:00:00 2001 From: John Hodge Date: Sat, 31 May 2014 13:39:35 +0800 Subject: [PATCH] Usermode/libc++ - ::std::map implementation mostly --- Usermode/Libraries/libc++.so_src/Makefile | 6 +- .../libc++.so_src/exception_handling.cc | 5 +- .../libc++.so_src/exception_handling.h | 2 +- .../include_exp/_libcxx_helpers.h | 4 + .../libc++.so_src/include_exp/functional | 31 ++ .../libc++.so_src/include_exp/iterator | 2 +- .../Libraries/libc++.so_src/include_exp/map | 376 ++++++++++++++++++ .../libc++.so_src/include_exp/utility | 23 ++ .../libc++.so_src/include_exp/vector | 4 +- 9 files changed, 445 insertions(+), 8 deletions(-) create mode 100644 Usermode/Libraries/libc++.so_src/include_exp/functional create mode 100644 Usermode/Libraries/libc++.so_src/include_exp/map diff --git a/Usermode/Libraries/libc++.so_src/Makefile b/Usermode/Libraries/libc++.so_src/Makefile index c76ac434..82eaf7c2 100644 --- a/Usermode/Libraries/libc++.so_src/Makefile +++ b/Usermode/Libraries/libc++.so_src/Makefile @@ -7,7 +7,10 @@ CPPFLAGS += CFLAGS += -Wall -Werror -Wextra CXXFLAGS += -Wall -Werror -Wextra ASFLAGS += -LDFLAGS += -Map map.txt -lc +LDFLAGS += -nostdlib +PRELINK := $(CRTI) $(CRTBEGIN) $(OUTPUTDIR)/Libs/crt0S.o +LIBS += -lc $(LIBGCC_PATH) $(CRTEND) $(CRTN) +USE_CXX_LINK := yes OBJ = misc.o new.o guard.o cxxabi.o typeinfo.o OBJ += string.o @@ -15,7 +18,6 @@ OBJ += exceptions.o exception_handling.o system_error.o DEPFILES := $(OBJ:%.o=%.d) BIN = libc++.so ifeq ($(ARCHDIR),native) - OBJ := $(filter-out heap.o,$(OBJ)) BIN = libc++_acess.so endif diff --git a/Usermode/Libraries/libc++.so_src/exception_handling.cc b/Usermode/Libraries/libc++.so_src/exception_handling.cc index 1bb26daf..d5a22195 100644 --- a/Usermode/Libraries/libc++.so_src/exception_handling.cc +++ b/Usermode/Libraries/libc++.so_src/exception_handling.cc @@ -77,6 +77,7 @@ extern "C" void __cxa_free_exception(void *thrown_exception) extern "C" void __cxa_throw(void *thrown_exception, std::type_info *tinfo, void (*dest)(void*)) { ::_SysDebug("__cxa_throw(%p,%p,%p) '%s'", thrown_exception, tinfo, dest, tinfo->name()); + ::_SysDebug("- by %p", __builtin_return_address(0)); { const ::std::exception* e = reinterpret_cast(thrown_exception); ::_SysDebug("- e.what() = '%s'", e->what()); @@ -92,9 +93,9 @@ extern "C" void __cxa_throw(void *thrown_exception, std::type_info *tinfo, void memcpy(&except->unwindHeader.exception_class, "Ac20C++\0", 8); __cxa_get_globals()->uncaughtExceptions ++; - _Unwind_RaiseException(thrown_exception); + int rv = _Unwind_RaiseException(thrown_exception); - ::_SysDebug("__cxa_throw(%p,%s) :: UNCAUGHT", thrown_exception, tinfo->name()); + ::_SysDebug("__cxa_throw(%p,%s) :: UNCAUGHT %i", thrown_exception, tinfo->name(), rv); ::std::terminate(); } diff --git a/Usermode/Libraries/libc++.so_src/exception_handling.h b/Usermode/Libraries/libc++.so_src/exception_handling.h index eb65fd1d..67fcd4c9 100644 --- a/Usermode/Libraries/libc++.so_src/exception_handling.h +++ b/Usermode/Libraries/libc++.so_src/exception_handling.h @@ -57,7 +57,7 @@ extern "C" void __cxa_throw(void *thrown_exception, std::type_info *tinfo, void extern "C" void *__cxa_begin_catch(void *exceptionObject); extern "C" void __cxa_end_catch(); -extern "C" void _Unwind_RaiseException(void *thrown_exception); +extern "C" _Unwind_Reason_Code _Unwind_RaiseException(void *thrown_exception); #endif diff --git a/Usermode/Libraries/libc++.so_src/include_exp/_libcxx_helpers.h b/Usermode/Libraries/libc++.so_src/include_exp/_libcxx_helpers.h index e131c42a..0537537a 100644 --- a/Usermode/Libraries/libc++.so_src/include_exp/_libcxx_helpers.h +++ b/Usermode/Libraries/libc++.so_src/include_exp/_libcxx_helpers.h @@ -8,5 +8,9 @@ # define _CXX11_AVAIL 0 #endif +namespace _sys { +extern void debug(const char *, ...); +}; + #endif diff --git a/Usermode/Libraries/libc++.so_src/include_exp/functional b/Usermode/Libraries/libc++.so_src/include_exp/functional new file mode 100644 index 00000000..1ac05dec --- /dev/null +++ b/Usermode/Libraries/libc++.so_src/include_exp/functional @@ -0,0 +1,31 @@ +/* + * Acess2 C++ Library + * - By John Hodge (thePowersGang) + * + * functional (header) + * - Funcional programming features + */ +#ifndef _LIBCXX_FUNCTIONAL_ +#define _LIBCXX_FUNCTIONAL_ + +#include "_libcxx_helpers.h" + +namespace std { + +template +struct less +{ + bool operator() (const T& x, const T& y) const { + return x < y; + } + typedef T first_argument_type; + typedef T second_argument_type; + typedef bool result_type; +}; + +}; // namespace std + +#endif + +// vim: ft=cpp + diff --git a/Usermode/Libraries/libc++.so_src/include_exp/iterator b/Usermode/Libraries/libc++.so_src/include_exp/iterator index d96082a0..e58ab803 100644 --- a/Usermode/Libraries/libc++.so_src/include_exp/iterator +++ b/Usermode/Libraries/libc++.so_src/include_exp/iterator @@ -8,7 +8,7 @@ namespace std { struct input_iterator_tag {}; struct output_iterator_tag {}; struct forward_iterator_tag {}; -struct bidrectional_iterator_tag {}; +struct bidirectional_iterator_tag {}; struct random_access_iterator_tag {}; template diff --git a/Usermode/Libraries/libc++.so_src/include_exp/map b/Usermode/Libraries/libc++.so_src/include_exp/map new file mode 100644 index 00000000..7a1cf3e6 --- /dev/null +++ b/Usermode/Libraries/libc++.so_src/include_exp/map @@ -0,0 +1,376 @@ +/* + * Acess2 C++ Library + * - By John Hodge (thePowersGang) + * + * map (header) + * - C++'s map type + */ +#ifndef _LIBCXX_MAP_ +#define _LIBCXX_MAP_ + +#include "_libcxx_helpers.h" +#include +#include +#include +#include +#include // less + +namespace std { + +namespace _bits { + +template +class map_iterator: + public ::std::iterator< ::std::bidirectional_iterator_tag, Val > +{ + friend Map; + typedef Val value_type; + Map *m_map; + size_t m_index; +public: + map_iterator(): + m_map(0), m_index(0) + { + } + map_iterator(Map *map, typename Map::size_type ofs): + m_map(map), m_index(ofs) + { + } + map_iterator(const map_iterator& x) { + *this = x; + } + map_iterator& operator=(const map_iterator& x) { + m_map = x.m_map; + m_index = x.m_index; + return *this; + } + + map_iterator& operator++() { + m_index ++; + } + map_iterator& operator--() { + m_index --; + } + + bool operator==(const map_iterator& x) const { + return m_index == x.m_index; + } + bool operator!=(const map_iterator& x) const { + return !(*this == x); + } + value_type& operator*() { + return m_map->m_items[m_index]; + } + value_type* operator->() { + return &m_map->m_items[m_index]; + } +}; + +} // namespace _bits + +template , class Alloc=allocator > > +class map +{ + typedef map this_type; +public: + typedef Key key_type; + typedef T mapped_type; + typedef pair value_type; + typedef Compare key_compare; + typedef Alloc allocator_type; + typedef typename allocator_type::reference reference; + typedef typename allocator_type::const_reference const_reference; + typedef typename allocator_type::pointer pointer; + typedef typename allocator_type::const_pointer const_pointer; + typedef _bits::map_iterator iterator; + typedef _bits::map_iterator const_iterator; + typedef size_t size_type; + +private: + friend class ::std::_bits::map_iterator; + friend class ::std::_bits::map_iterator; + + key_compare m_comp; + allocator_type m_alloc; + value_type* m_items; // sorted array + size_type m_size; + size_type m_capacity; + +public: + map(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()): + m_comp(comp), + m_alloc(alloc), + m_items(0), m_size(0), m_capacity(0) + { + } + template + map(InputInterator first, InputInterator last): + map() + { + insert(first, last); + } + map(const map& x): + map(x.m_comp, x.m_alloc) + { + *this = x; + } + ~map() { + clear(); + reserve(0); + } + map& operator=(const map& x) { + clear(); + reserve(x.m_size); + for( size_type i = 0; i < x.m_size; i ++ ) { + emplace_hint( end(), x.m_items[i] ); + } + return *this; + } + + // Iterators + iterator begin() { + return iterator(this, 0); + } + const_iterator begin() const { + return const_iterator(this, 0); + } + iterator end() { + return iterator(this, m_size); + } + const_iterator end() const { + return const_iterator(this, m_size); + } + #if _CXX11_AVAIL + const_iterator cbegin() const { + return const_iterator(this, 0); + } + const_iterator cend() const { + return const_iterator(this, m_size); + } + #endif + //reverse_iterator rbegin(); + //const_reverse_iterator rbegin() const; + //const_reverse_iterator crbegin() const; + //reverse_iterator rend(); + //const reverse_iterator rend() const; + //const reverse_iterator crend() const; + + // Capacity + bool empty() const { + return m_size == 0; + } + size_type size() const { + return m_size; + } + size_type max_size() const { + return (size_type)-1 / sizeof(value_type); + } + + // Element access + mapped_type& operator[](const key_type& k) { + iterator it = upper_bound(k); + if( it == end() || m_comp(k, it->first) ) { // if k < it->first, no match + insert_at(it.m_index, value_type(k,mapped_type()) ); + ++ it; + } + return it->second; + } + #if _CXX11_AVAIL + mapped_type& at(const key_type& k) { + iterator it = lower_bound(k); + if( it == end() || m_comp(it->first, k) ) + throw ::std::out_of_range("::std:map::at"); + return it->second; + } + const mapped_type& at(const key_type& k) const { + iterator it = lower_bound(k); + if( it == end() || m_comp(it->first, k) ) + throw ::std::out_of_range("::std:map::at"); + return it->second; + } + #endif + + // Modifiers + // - insert + pair insert(const value_type& val); + iterator insert(iterator position, const value_type& val); + template + void insert(InputInterator first, InputInterator last); + // - erase + void erase(iterator position); + size_type erase(const key_type& k); + void erase(iterator first, iterator last); + // - swap + void swap(map& x); + // - clear + void clear() { + for( size_type i = 0; i < m_size; i ++ ) { + m_alloc.destroy( &m_items[i] ); + } + m_size = 0; + } + // - emplace + #if _CXX11_AVAIL + template + pair emplace(Args&&... args) { + return emplace_hint(begin(), args...); + } + template + pair emplace_hint(iterator position, Args&&... args); + #endif + + // TODO: Observers + + // Operators + iterator find(const key_type& k) { + iterator it = lower_bound(k); + if( it == end() || m_comp(it->first, k) ) // if it->first < k + return end(); + return it; + } + const_iterator find(const key_type& k) const { + const_iterator it = lower_bound(k); + if( it == end() || m_comp(it->first, k) ) // if it->first < k + return end(); + return it; + } + size_type count(const key_type& k) { + if( find(k) == end() ) + return 0; + return 1; + } + iterator lower_bound(const key_type& k) { + size_type idx; + if( _search(k, idx) ) { + // found, return direct iterator + return iterator(this, idx); + } + else { + // not found, return iterator to before + if( idx == 0 ) return begin(); + return iterator(this, idx-1); + } + } + const_iterator lower_bound(const key_type& k) const { + size_type idx; + if( _search(k, idx) ) { + // found, return direct iterator + return iterator(this, idx); + } + else { + // not found, return iterator to before + if( idx == 0 ) return begin(); + return iterator(this, idx-1); + } + } + iterator upper_bound(const key_type& k) { + size_type idx; + _search(k, idx); + // idx == item or just after it + return iterator(this, idx); + } + const_iterator upper_bound(const key_type& k) const { + size_type idx; + _search(k, idx); + return const_iterator(this, idx); + } + pair equal_range(const key_type& k); + pair equal_range(const key_type& k) const; + +private: + // Change reservation to fit 'n' items + // - NOTE: Will also resize down + void reserve(size_type n) { + n = (n + 31) & ~31; + if( n > max_size() ) + throw ::std::length_error("::std::map::reserve"); + if( n != m_capacity ) + { + auto new_area = m_alloc.allocate(n); + for( size_type i = 0; i < m_size && i < n; i ++ ) + m_alloc.construct(&new_area[i], m_items[i]); + for( size_type i = n; i < m_size; i ++ ) + m_alloc.destroy( &m_items[i] ); + m_alloc.deallocate(m_items, m_capacity); + m_items = new_area; + m_capacity = n; + if(m_size > n) + m_size = n; + } + } + // Returns the index above or equal to 'k' + // - TODO: Reimplement as a binary search + bool _search(const key_type& k, size_type &pos_out) const { + #if 0 + size_type pos = m_size / 2; + size_type step = m_size / 4; + while( step > 0 ) { + const key_type& item_key = m_items[pos].first; + if( m_comp(item_key, k) ) + pos += step; + else if( m_comp(k, item_key) ) + pos -= step; + else { + pos_out = pos; + return true; + } + step /= 2; + } + pos_out = pos; + return false; + #else + for( size_type pos = 0; pos < m_size; pos ++ ) + { + const key_type& item_key = m_items[pos].first; + if( m_comp(item_key, k) ) { + continue; + } + else if( m_comp(k, item_key) ) { + pos_out = pos; + return false; + } + else { + pos_out = pos; + return true; + } + } + pos_out = m_size; + return false; + #endif + } + void insert_at(size_type ofs, const value_type& val) { + //assert( ofs == 0 || m_comp(m_items[ofs-1].first, val.first) ); + //assert( ofs == m_size || m_comp(m_items[ofs].first, val.first) ); + ::_sys::debug("map::insert_at(%i,)", ofs); + // Resize up + reserve( m_size + 1 ); + // Move following items up + shift_items(&m_items[ofs], &m_items[ofs+1], m_size-ofs); + // Construct new item + m_alloc.construct(&m_items[ofs], val); + m_size ++; + } + void shift_items(value_type *start, value_type *end, size_type count) { + if( start < end ) { + for( size_type i = count; i --; ) { + #if _CXX11_AVAIL && 0 + m_alloc.construct(&end[i], ::std::move(start[i])); + #else + m_alloc.construct(&end[i], start[i]); + m_alloc.destroy(&start[i]); + #endif + } + } + else { + for( size_type i = 0; i < count; i ++ ) { + } + } + } +}; + +} // namespace std + +#endif + +// vim: ft=cpp + diff --git a/Usermode/Libraries/libc++.so_src/include_exp/utility b/Usermode/Libraries/libc++.so_src/include_exp/utility index 9b7957c5..b3e40c53 100644 --- a/Usermode/Libraries/libc++.so_src/include_exp/utility +++ b/Usermode/Libraries/libc++.so_src/include_exp/utility @@ -37,7 +37,21 @@ public: second(b) { } + pair(const pair& pr): + first(pr.first), + second(pr.second) + { + } + pair(pair&& pr): + first(pr.first), second(pr.second) + { + } // operator = is implicit + pair& operator=(const pair& x) { + first = x.first; + second = x.second; + return *this; + } }; template @@ -58,6 +72,15 @@ template T&& forward(typename remove_reference::type&& arg) noexcept { return static_cast(arg); } + +template +typename remove_reference::type&& move( T&& t) noexcept { + return static_cast::type&&>(t); +} +//template +//constexpr typename ::std::remove_reference::type&& move( T&& t) noexcept { +// return static_cast::type&&>(t); +//} #endif }; // namespace std diff --git a/Usermode/Libraries/libc++.so_src/include_exp/vector b/Usermode/Libraries/libc++.so_src/include_exp/vector index 30bd207c..426fd57b 100644 --- a/Usermode/Libraries/libc++.so_src/include_exp/vector +++ b/Usermode/Libraries/libc++.so_src/include_exp/vector @@ -2,8 +2,8 @@ * Acess2 C++ Library * - By John Hodge (thePowersGang) * - * string (header) - * - C++'s String type + * vector (header) + * - C++'s vector (dynamic array) type */ #ifndef _LIBCXX_VECTOR_ #define _LIBCXX_VECTOR_ -- 2.20.1