← Back to branch summary

~ubuntu-branches/ubuntu/vivid/emscripten/vivid

« back to all changes in this revision

Viewing changes to system/include/libcxx/__tree

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-09-20 22:44:35 UTC
  • mfrom: (4.1.1 sid)
  • Revision ID: package-import@ubuntu.com-20130920224435-apuwj4fsl3fqv1a6
Tags: 1.5.6~20130920~6010666-1
http://bugs.debian.org/723129
* New snapshot release
* Update the list of supported architectures to the same as libv8
  (Closes: #723129)
* emlibtool has been removed from upstream.
* Fix warning syntax-error-in-dep5-copyright
* Refresh of the patches

Show diffs side-by-side

added added

removed removed

Lines of Context:
system/include/libcxx/__tree
644
644
    _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT {}
645
645
 
646
646
    _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;}
647
 
    _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return &__ptr_->__value_;}
 
647
    _LIBCPP_INLINE_VISIBILITY pointer operator->() const
 
648
        {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);}
648
649
 
649
650
    _LIBCPP_INLINE_VISIBILITY
650
651
    __tree_iterator& operator++()
686
687
{
687
688
    typedef _ConstNodePtr                                         __node_pointer;
688
689
    typedef typename pointer_traits<__node_pointer>::element_type __node;
689
 
    typedef const typename __node::base                           __node_base;
 
690
    typedef typename __node::base                                 __node_base;
690
691
    typedef typename pointer_traits<__node_pointer>::template
691
692
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
692
693
            rebind<__node_base>
729
730
        : __ptr_(__p.__ptr_) {}
730
731
 
731
732
    _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;}
732
 
    _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return &__ptr_->__value_;}
 
733
    _LIBCPP_INLINE_VISIBILITY pointer operator->() const
 
734
        {return pointer_traits<pointer>::pointer_to(__ptr_->__value_);}
733
735
 
734
736
    _LIBCPP_INLINE_VISIBILITY
735
737
    __tree_const_iterator& operator++()
779
781
    typedef typename __alloc_traits::size_type       size_type;
780
782
    typedef typename __alloc_traits::difference_type difference_type;
781
783
 
782
 
    typedef __tree_node<value_type, typename __alloc_traits::void_pointer> __node;
783
 
    typedef __tree_node_base<typename __alloc_traits::void_pointer> __node_base;
 
784
    typedef typename __alloc_traits::void_pointer  __void_pointer;
 
785
 
 
786
    typedef __tree_node<value_type, __void_pointer> __node;
 
787
    typedef __tree_node_base<__void_pointer>        __node_base;
784
788
    typedef typename __alloc_traits::template
785
789
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
786
790
            rebind_alloc<__node>
790
794
                                                     __node_allocator;
791
795
    typedef allocator_traits<__node_allocator>       __node_traits;
792
796
    typedef typename __node_traits::pointer          __node_pointer;
793
 
    typedef typename __node_traits::const_pointer    __node_const_pointer;
 
797
    typedef typename __node_traits::pointer          __node_const_pointer;
794
798
    typedef typename __node_base::pointer            __node_base_pointer;
795
 
    typedef typename __node_base::const_pointer      __node_base_const_pointer;
 
799
    typedef typename __node_base::pointer            __node_base_const_pointer;
796
800
private:
797
801
    typedef typename __node_base::base __end_node_t;
798
802
    typedef typename pointer_traits<__node_pointer>::template
804
808
                                                     __end_node_ptr;
805
809
    typedef typename pointer_traits<__node_pointer>::template
806
810
#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
807
 
            rebind<const __end_node_t>
 
811
            rebind<__end_node_t>
808
812
#else
809
 
            rebind<const __end_node_t>::other
 
813
            rebind<__end_node_t>::other
810
814
#endif
811
815
                                                     __end_node_const_ptr;
812
816
 
828
832
    {
829
833
        return static_cast<__node_const_pointer>
830
834
               (
831
 
                   pointer_traits<__end_node_const_ptr>::pointer_to(__pair1_.first())
 
835
                   pointer_traits<__end_node_const_ptr>::pointer_to(const_cast<__end_node_t&>(__pair1_.first()))
832
836
               );
833
837
    }
834
838
    _LIBCPP_INLINE_VISIBILITY
865
869
        {return static_cast<__node_const_pointer>(__end_node()->__left_);}
866
870
 
867
871
    typedef __tree_iterator<value_type, __node_pointer, difference_type>             iterator;
868
 
    typedef __tree_const_iterator<value_type, __node_const_pointer, difference_type> const_iterator;
 
872
    typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator;
869
873
 
870
874
    explicit __tree(const value_compare& __comp)
871
875
        _NOEXCEPT_(
1102
1106
 
1103
1107
    __node_pointer __detach();
1104
1108
    static __node_pointer __detach(__node_pointer);
 
1109
 
 
1110
    template <class, class, class, class> friend class _LIBCPP_TYPE_VIS map;
 
1111
    template <class, class, class, class> friend class _LIBCPP_TYPE_VIS multimap;
1105
1112
};
1106
1113
 
1107
1114
template <class _Tp, class _Compare, class _Allocator>
1161
1168
{
1162
1169
    if (__cache->__parent_ == nullptr)
1163
1170
        return nullptr;
1164
 
    if (__tree_is_left_child(__cache))
 
1171
    if (__tree_is_left_child(static_cast<__node_base_pointer>(__cache)))
1165
1172
    {
1166
1173
        __cache->__parent_->__left_ = nullptr;
1167
1174
        __cache = static_cast<__node_pointer>(__cache->__parent_);
1294
1301
        __begin_node() = __end_node();
1295
1302
    else
1296
1303
    {
1297
 
        __end_node()->__left_->__parent_ = __end_node();
 
1304
        __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1298
1305
        __t.__begin_node() = __t.__end_node();
1299
1306
        __t.__end_node()->__left_ = nullptr;
1300
1307
        __t.size() = 0;
1314
1321
        {
1315
1322
            __begin_node() = __t.__begin_node();
1316
1323
            __end_node()->__left_ = __t.__end_node()->__left_;
1317
 
            __end_node()->__left_->__parent_ = __end_node();
 
1324
            __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1318
1325
            size() = __t.size();
1319
1326
            __t.__begin_node() = __t.__end_node();
1320
1327
            __t.__end_node()->__left_ = nullptr;
1342
1349
        __begin_node() = __end_node();
1343
1350
    else
1344
1351
    {
1345
 
        __end_node()->__left_->__parent_ = __end_node();
 
1352
        __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1346
1353
        __t.__begin_node() = __t.__end_node();
1347
1354
        __t.__end_node()->__left_ = nullptr;
1348
1355
        __t.size() = 0;
1447
1454
    if (size() == 0)
1448
1455
        __begin_node() = __end_node();
1449
1456
    else
1450
 
        __end_node()->__left_->__parent_ = __end_node();
 
1457
        __end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__end_node());
1451
1458
    if (__t.size() == 0)
1452
1459
        __t.__begin_node() = __t.__end_node();
1453
1460
    else
1454
 
        __t.__end_node()->__left_->__parent_ = __t.__end_node();
 
1461
        __t.__end_node()->__left_->__parent_ = static_cast<__node_base_pointer>(__t.__end_node());
1455
1462
}
1456
1463
 
1457
1464
template <class _Tp, class _Compare, class _Allocator>
1483
1490
                    __nd = static_cast<__node_pointer>(__nd->__right_);
1484
1491
                else
1485
1492
                {
1486
 
                    __parent = __nd;
 
1493
                    __parent = static_cast<__node_base_pointer>(__nd);
1487
1494
                    return __parent->__right_;
1488
1495
                }
1489
1496
            }
1493
1500
                    __nd = static_cast<__node_pointer>(__nd->__left_);
1494
1501
                else
1495
1502
                {
1496
 
                    __parent = __nd;
 
1503
                    __parent = static_cast<__node_base_pointer>(__nd);
1497
1504
                    return __parent->__left_;
1498
1505
                }
1499
1506
            }
1500
1507
        }
1501
1508
    }
1502
 
    __parent = __end_node();
 
1509
    __parent = static_cast<__node_base_pointer>(__end_node());
1503
1510
    return __parent->__left_;
1504
1511
}
1505
1512
 
1522
1529
                    __nd = static_cast<__node_pointer>(__nd->__left_);
1523
1530
                else
1524
1531
                {
1525
 
                    __parent = __nd;
 
1532
                    __parent = static_cast<__node_base_pointer>(__nd);
1526
1533
                    return __parent->__left_;
1527
1534
                }
1528
1535
            }
1532
1539
                    __nd = static_cast<__node_pointer>(__nd->__right_);
1533
1540
                else
1534
1541
                {
1535
 
                    __parent = __nd;
 
1542
                    __parent = static_cast<__node_base_pointer>(__nd);
1536
1543
                    return __parent->__right_;
1537
1544
                }
1538
1545
            }
1539
1546
        }
1540
1547
    }
1541
 
    __parent = __end_node();
 
1548
    __parent = static_cast<__node_base_pointer>(__end_node());
1542
1549
    return __parent->__left_;
1543
1550
}
1544
1551
 
1563
1570
            // *prev(__hint) <= __v <= *__hint
1564
1571
            if (__hint.__ptr_->__left_ == nullptr)
1565
1572
            {
1566
 
                __parent = const_cast<__node_pointer&>(__hint.__ptr_);
 
1573
                __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
1567
1574
                return __parent->__left_;
1568
1575
            }
1569
1576
            else
1570
1577
            {
1571
 
                __parent = const_cast<__node_pointer&>(__prior.__ptr_);
 
1578
                __parent = static_cast<__node_base_pointer>(__prior.__ptr_);
1572
1579
                return __parent->__right_;
1573
1580
            }
1574
1581
        }
1600
1607
                    __nd = static_cast<__node_pointer>(__nd->__left_);
1601
1608
                else
1602
1609
                {
1603
 
                    __parent = __nd;
 
1610
                    __parent = static_cast<__node_base_pointer>(__nd);
1604
1611
                    return __parent->__left_;
1605
1612
                }
1606
1613
            }
1610
1617
                    __nd = static_cast<__node_pointer>(__nd->__right_);
1611
1618
                else
1612
1619
                {
1613
 
                    __parent = __nd;
 
1620
                    __parent = static_cast<__node_base_pointer>(__nd);
1614
1621
                    return __parent->__right_;
1615
1622
                }
1616
1623
            }
1617
1624
            else
1618
1625
            {
1619
 
                __parent = __nd;
 
1626
                __parent = static_cast<__node_base_pointer>(__nd);
1620
1627
                return __parent;
1621
1628
            }
1622
1629
        }
1623
1630
    }
1624
 
    __parent = __end_node();
 
1631
    __parent = static_cast<__node_base_pointer>(__end_node());
1625
1632
    return __parent->__left_;
1626
1633
}
1627
1634
 
1648
1655
            // *prev(__hint) < __v < *__hint
1649
1656
            if (__hint.__ptr_->__left_ == nullptr)
1650
1657
            {
1651
 
                __parent = const_cast<__node_pointer&>(__hint.__ptr_);
 
1658
                __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
1652
1659
                return __parent->__left_;
1653
1660
            }
1654
1661
            else
1655
1662
            {
1656
 
                __parent = const_cast<__node_pointer&>(__prior.__ptr_);
 
1663
                __parent = static_cast<__node_base_pointer>(__prior.__ptr_);
1657
1664
                return __parent->__right_;
1658
1665
            }
1659
1666
        }
1669
1676
            // *__hint < __v < *_VSTD::next(__hint)
1670
1677
            if (__hint.__ptr_->__right_ == nullptr)
1671
1678
            {
1672
 
                __parent = const_cast<__node_pointer&>(__hint.__ptr_);
 
1679
                __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
1673
1680
                return __parent->__right_;
1674
1681
            }
1675
1682
            else
1676
1683
            {
1677
 
                __parent = const_cast<__node_pointer&>(__next.__ptr_);
 
1684
                __parent = static_cast<__node_base_pointer>(__next.__ptr_);
1678
1685
                return __parent->__left_;
1679
1686
            }
1680
1687
        }
1682
1689
        return __find_equal(__parent, __v);
1683
1690
    }
1684
1691
    // else __v == *__hint
1685
 
    __parent = const_cast<__node_pointer&>(__hint.__ptr_);
 
1692
    __parent = static_cast<__node_base_pointer>(__hint.__ptr_);
1686
1693
    return __parent;
1687
1694
}
1688
1695
 
1729
1736
    bool __inserted = false;
1730
1737
    if (__child == nullptr)
1731
1738
    {
1732
 
        __insert_node_at(__parent, __child, __h.get());
 
1739
        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1733
1740
        __r = __h.release();
1734
1741
        __inserted = true;
1735
1742
    }
1747
1754
    __node_pointer __r = static_cast<__node_pointer>(__child);
1748
1755
    if (__child == nullptr)
1749
1756
    {
1750
 
        __insert_node_at(__parent, __child, __h.get());
 
1757
        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1751
1758
        __r = __h.release();
1752
1759
    }
1753
1760
    return iterator(__r);
1761
1768
    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1762
1769
    __node_base_pointer __parent;
1763
1770
    __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_);
1764
 
    __insert_node_at(__parent, __child, __h.get());
 
1771
    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1765
1772
    return iterator(static_cast<__node_pointer>(__h.release()));
1766
1773
}
1767
1774
 
1774
1781
    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1775
1782
    __node_base_pointer __parent;
1776
1783
    __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_);
1777
 
    __insert_node_at(__parent, __child, __h.get());
 
1784
    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1778
1785
    return iterator(static_cast<__node_pointer>(__h.release()));
1779
1786
}
1780
1787
 
1812
1819
    __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v));
1813
1820
    __node_base_pointer __parent;
1814
1821
    __node_base_pointer& __child = __find_leaf_high(__parent, __h->__value_);
1815
 
    __insert_node_at(__parent, __child, __h.get());
 
1822
    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1816
1823
    return iterator(__h.release());
1817
1824
}
1818
1825
 
1824
1831
    __node_holder __h = __construct_node(_VSTD::forward<_Vp>(__v));
1825
1832
    __node_base_pointer __parent;
1826
1833
    __node_base_pointer& __child = __find_leaf(__p, __parent, __h->__value_);
1827
 
    __insert_node_at(__parent, __child, __h.get());
 
1834
    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1828
1835
    return iterator(__h.release());
1829
1836
}
1830
1837
 
1854
1861
    if (__child == nullptr)
1855
1862
    {
1856
1863
        __node_holder __h = __construct_node(__v);
1857
 
        __insert_node_at(__parent, __child, __h.get());
 
1864
        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1858
1865
        __r = __h.release();
1859
1866
        __inserted = true;
1860
1867
    }
1871
1878
    if (__child == nullptr)
1872
1879
    {
1873
1880
        __node_holder __h = __construct_node(__v);
1874
 
        __insert_node_at(__parent, __child, __h.get());
 
1881
        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1875
1882
        __r = __h.release();
1876
1883
    }
1877
1884
    return iterator(__r);
1884
1891
    __node_base_pointer __parent;
1885
1892
    __node_base_pointer& __child = __find_leaf_high(__parent, __v);
1886
1893
    __node_holder __h = __construct_node(__v);
1887
 
    __insert_node_at(__parent, __child, __h.get());
 
1894
    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1888
1895
    return iterator(__h.release());
1889
1896
}
1890
1897
 
1895
1902
    __node_base_pointer __parent;
1896
1903
    __node_base_pointer& __child = __find_leaf(__p, __parent, __v);
1897
1904
    __node_holder __h = __construct_node(__v);
1898
 
    __insert_node_at(__parent, __child, __h.get());
 
1905
    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1899
1906
    return iterator(__h.release());
1900
1907
}
1901
1908
 
1909
1916
    bool __inserted = false;
1910
1917
    if (__child == nullptr)
1911
1918
    {
1912
 
        __insert_node_at(__parent, __child, __nd);
 
1919
        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
1913
1920
        __r = __nd;
1914
1921
        __inserted = true;
1915
1922
    }
1926
1933
    __node_pointer __r = static_cast<__node_pointer>(__child);
1927
1934
    if (__child == nullptr)
1928
1935
    {
1929
 
        __insert_node_at(__parent, __child, __nd);
 
1936
        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
1930
1937
        __r = __nd;
1931
1938
    }
1932
1939
    return iterator(__r);
1938
1945
{
1939
1946
    __node_base_pointer __parent;
1940
1947
    __node_base_pointer& __child = __find_leaf_high(__parent, __nd->__value_);
1941
 
    __insert_node_at(__parent, __child, __nd);
 
1948
    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
1942
1949
    return iterator(__nd);
1943
1950
}
1944
1951
 
1949
1956
{
1950
1957
    __node_base_pointer __parent;
1951
1958
    __node_base_pointer& __child = __find_leaf(__p, __parent, __nd->__value_);
1952
 
    __insert_node_at(__parent, __child, __nd);
 
1959
    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
1953
1960
    return iterator(__nd);
1954
1961
}
1955
1962
 
1957
1964
typename __tree<_Tp, _Compare, _Allocator>::iterator
1958
1965
__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
1959
1966
{
1960
 
    __node_pointer __np = const_cast<__node_pointer>(__p.__ptr_);
 
1967
    __node_pointer __np = __p.__ptr_;
1961
1968
    iterator __r(__np);
1962
1969
    ++__r;
1963
1970
    if (__begin_node() == __np)
1977
1984
{
1978
1985
    while (__f != __l)
1979
1986
        __f = erase(__f);
1980
 
    return iterator(const_cast<__node_pointer>(__l.__ptr_));
 
1987
    return iterator(__l.__ptr_);
1981
1988
}
1982
1989
 
1983
1990
template <class _Tp, class _Compare, class _Allocator>
2264
2271
typename __tree<_Tp, _Compare, _Allocator>::__node_holder
2265
2272
__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT
2266
2273
{
2267
 
    __node_pointer __np = const_cast<__node_pointer>(__p.__ptr_);
 
2274
    __node_pointer __np = __p.__ptr_;
2268
2275
    if (__begin_node() == __np)
2269
2276
    {
2270
2277
        if (__np->__right_ != nullptr)