Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // -*- C++ -*-
  2.  
  3. // Copyright (C) 2005-2013 Free Software Foundation, Inc.
  4. //
  5. // This file is part of the GNU ISO C++ Library.  This library is free
  6. // software; you can redistribute it and/or modify it under the terms
  7. // of the GNU General Public License as published by the Free Software
  8. // Foundation; either version 3, or (at your option) any later
  9. // version.
  10.  
  11. // This library is distributed in the hope that it will be useful, but
  12. // WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14. // General Public License for more details.
  15.  
  16. // Under Section 7 of GPL version 3, you are granted additional
  17. // permissions described in the GCC Runtime Library Exception, version
  18. // 3.1, as published by the Free Software Foundation.
  19.  
  20. // You should have received a copy of the GNU General Public License and
  21. // a copy of the GCC Runtime Library Exception along with this program;
  22. // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23. // <http://www.gnu.org/licenses/>.
  24.  
  25. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26.  
  27. // Permission to use, copy, modify, sell, and distribute this software
  28. // is hereby granted without fee, provided that the above copyright
  29. // notice appears in all copies, and that both that copyright notice
  30. // and this permission notice appear in supporting documentation. None
  31. // of the above authors, nor IBM Haifa Research Laboratories, make any
  32. // representation about the suitability of this software for any
  33. // purpose. It is provided "as is" without express or implied
  34. // warranty.
  35.  
  36. /**
  37.  * @file container_base_dispatch.hpp
  38.  * Contains associative container dispatching.
  39.  */
  40.  
  41. #ifndef PB_DS_ASSOC_CNTNR_BASE_DS_DISPATCHER_HPP
  42. #define PB_DS_ASSOC_CNTNR_BASE_DS_DISPATCHER_HPP
  43.  
  44. #include <ext/typelist.h>
  45.  
  46. #define PB_DS_ASSERT_VALID(X)                                           \
  47.   _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);)
  48.  
  49. #define PB_DS_DEBUG_VERIFY(_Cond)                                       \
  50.   _GLIBCXX_DEBUG_VERIFY_AT(_Cond,                                       \
  51.                            _M_message(#_Cond" assertion from %1;:%2;")  \
  52.                            ._M_string(__FILE__)._M_integer(__LINE__)    \
  53.                            ,__file,__line)
  54.  
  55. #define PB_DS_CHECK_KEY_EXISTS(_Key)                                    \
  56.   _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(_Key, __FILE__, __LINE__);)
  57.  
  58. #define PB_DS_CHECK_KEY_DOES_NOT_EXIST(_Key)                            \
  59.   _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(_Key,        \
  60.                                                            __FILE__, __LINE__);)
  61.  
  62. #define PB_DS_DATA_TRUE_INDICATOR
  63. #define PB_DS_V2F(X) (X).first
  64. #define PB_DS_V2S(X) (X).second
  65. #define PB_DS_EP2VP(X)& ((X)->m_value)
  66. #include <ext/pb_ds/detail/list_update_map_/lu_map_.hpp>
  67. #include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp>
  68. #include <ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp>
  69. #include <ext/pb_ds/detail/splay_tree_/splay_tree_.hpp>
  70. #include <ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp>
  71. #include <ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp>
  72. #include <ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp>
  73. #include <ext/pb_ds/detail/pat_trie_/pat_trie_.hpp>
  74. #undef PB_DS_DATA_TRUE_INDICATOR
  75. #undef PB_DS_V2F
  76. #undef PB_DS_V2S
  77. #undef PB_DS_EP2VP
  78.  
  79. #define PB_DS_DATA_FALSE_INDICATOR
  80. #define PB_DS_V2F(X) (X)
  81. #define PB_DS_V2S(X) Mapped_Data()
  82. #define PB_DS_EP2VP(X)& ((X)->m_value.first)
  83. #include <ext/pb_ds/detail/list_update_map_/lu_map_.hpp>
  84. #include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp>
  85. #include <ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp>
  86. #include <ext/pb_ds/detail/splay_tree_/splay_tree_.hpp>
  87. #include <ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp>
  88. #include <ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp>
  89. #include <ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp>
  90. #include <ext/pb_ds/detail/pat_trie_/pat_trie_.hpp>
  91. #undef PB_DS_DATA_FALSE_INDICATOR
  92. #undef PB_DS_V2F
  93. #undef PB_DS_V2S
  94. #undef PB_DS_EP2VP
  95.  
  96. #undef PB_DS_CHECK_KEY_DOES_NOT_EXIST
  97. #undef PB_DS_CHECK_KEY_EXISTS
  98. #undef PB_DS_DEBUG_VERIFY
  99. #undef PB_DS_ASSERT_VALID
  100.  
  101. namespace __gnu_pbds
  102. {
  103. namespace detail
  104. {
  105.   /// Specialization for list-update map.
  106.   template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl>
  107.     struct container_base_dispatch<Key, Mapped, _Alloc, list_update_tag,
  108.                                    Policy_Tl>
  109.     {
  110.     private:
  111.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>       at0;
  112.       typedef typename at0::type                                at0t;
  113.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1>       at1;
  114.       typedef typename at1::type                                at1t;
  115.  
  116.     public:
  117.       /// Dispatched type.
  118.       typedef lu_map<Key, Mapped, at0t, _Alloc, at1t>   type;
  119.     };
  120.  
  121.   /// Specialization for list-update set.
  122.   template<typename Key, typename _Alloc, typename Policy_Tl>
  123.     struct container_base_dispatch<Key, null_type, _Alloc, list_update_tag,
  124.                                    Policy_Tl>
  125.     {
  126.     private:
  127.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>       at0;
  128.       typedef typename at0::type                                at0t;
  129.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1>       at1;
  130.       typedef typename at1::type                                at1t;
  131.  
  132.     public:
  133.       /// Dispatched type.
  134.       typedef lu_set<Key, null_type, at0t, _Alloc, at1t> type;
  135.     };
  136.  
  137.   /// Specialization for PATRICIA trie map.
  138.   template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl>
  139.   struct container_base_dispatch<Key, Mapped, _Alloc, pat_trie_tag, Policy_Tl>
  140.     {
  141.     private:
  142.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1>       at1;
  143.       typedef typename at1::type                                at1t;
  144.  
  145.     public:
  146.       typedef pat_trie_map<Key, Mapped, at1t, _Alloc>           type;
  147.     };
  148.  
  149.   /// Specialization for PATRICIA trie set.
  150.   template<typename Key, typename _Alloc, typename Policy_Tl>
  151.     struct container_base_dispatch<Key, null_type, _Alloc, pat_trie_tag,
  152.                                    Policy_Tl>
  153.     {
  154.     private:
  155.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1>       at1;
  156.       typedef typename at1::type                                at1t;
  157.  
  158.     public:
  159.       /// Dispatched type.
  160.       typedef pat_trie_set<Key, null_type, at1t, _Alloc> type;
  161.     };
  162.  
  163.   /// Specialization for R-B tree map.
  164.   template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl>
  165.     struct container_base_dispatch<Key, Mapped, _Alloc, rb_tree_tag, Policy_Tl>
  166.     {
  167.     private:
  168.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>       at0;
  169.       typedef typename at0::type                                at0t;
  170.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1>       at1;
  171.       typedef typename at1::type                                at1t;
  172.  
  173.     public:
  174.       /// Dispatched type.
  175.       typedef rb_tree_map<Key, Mapped, at0t, at1t, _Alloc>      type;
  176.     };
  177.  
  178.   /// Specialization for R-B tree set.
  179.   template<typename Key, typename _Alloc, typename Policy_Tl>
  180.     struct container_base_dispatch<Key, null_type, _Alloc, rb_tree_tag,
  181.                                    Policy_Tl>
  182.     {
  183.     private:
  184.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>       at0;
  185.       typedef typename at0::type                                at0t;
  186.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1>       at1;
  187.       typedef typename at1::type                                at1t;
  188.  
  189.     public:
  190.       typedef rb_tree_set<Key, null_type, at0t, at1t, _Alloc> type;
  191.     };
  192.  
  193.   /// Specialization splay tree map.
  194.   template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl>
  195.   struct container_base_dispatch<Key, Mapped, _Alloc, splay_tree_tag,
  196.                                    Policy_Tl>
  197.     {
  198.     private:
  199.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>       at0;
  200.       typedef typename at0::type                                at0t;
  201.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1>       at1;
  202.       typedef typename at1::type                                at1t;
  203.  
  204.     public:
  205.       /// Dispatched type.
  206.       typedef splay_tree_map<Key, Mapped, at0t, at1t, _Alloc>   type;
  207.     };
  208.  
  209.   /// Specialization splay tree set.
  210.   template<typename Key, typename _Alloc, typename Policy_Tl>
  211.     struct container_base_dispatch<Key, null_type, _Alloc, splay_tree_tag,
  212.                                    Policy_Tl>
  213.     {
  214.     private:
  215.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>       at0;
  216.       typedef typename at0::type                                at0t;
  217.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1>       at1;
  218.       typedef typename at1::type                                at1t;
  219.  
  220.     public:
  221.       /// Dispatched type.
  222.       typedef splay_tree_set<Key, null_type, at0t, at1t, _Alloc> type;
  223.   };
  224.  
  225.     /// Specialization ordered-vector tree map.
  226.   template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl>
  227.     struct container_base_dispatch<Key, Mapped, _Alloc, ov_tree_tag, Policy_Tl>
  228.     {
  229.     private:
  230.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>       at0;
  231.       typedef typename at0::type                                at0t;
  232.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1>       at1;
  233.       typedef typename at1::type                                at1t;
  234.  
  235.     public:
  236.       /// Dispatched type.
  237.       typedef ov_tree_map<Key, Mapped, at0t, at1t, _Alloc>      type;
  238.   };
  239.  
  240.     /// Specialization ordered-vector tree set.
  241.   template<typename Key, typename _Alloc, typename Policy_Tl>
  242.     struct container_base_dispatch<Key, null_type, _Alloc, ov_tree_tag,
  243.                                    Policy_Tl>
  244.     {
  245.     private:
  246.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>       at0;
  247.       typedef typename at0::type                                at0t;
  248.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1>       at1;
  249.       typedef typename at1::type                                at1t;
  250.  
  251.     public:
  252.       /// Dispatched type.
  253.       typedef ov_tree_set<Key, null_type, at0t, at1t, _Alloc> type;
  254.   };
  255.  
  256.     /// Specialization colision-chaining hash map.
  257.   template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl>
  258.     struct container_base_dispatch<Key, Mapped, _Alloc, cc_hash_tag, Policy_Tl>
  259.     {
  260.     private:
  261.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>       at0;
  262.       typedef typename at0::type                                at0t;
  263.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1>       at1;
  264.       typedef typename at1::type                                at1t;
  265.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2>       at2;
  266.       typedef typename at2::type                                at2t;
  267.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3>       at3;
  268.       typedef typename at3::type                                at3t;
  269.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4>       at4;
  270.       typedef typename at4::type                                at4t;
  271.  
  272.     public:
  273.       /// Dispatched type.
  274.       typedef cc_ht_map<Key, Mapped, at0t, at1t, _Alloc,
  275.                         at3t::value, at4t, at2t>                type;
  276.   };
  277.  
  278.     /// Specialization colision-chaining hash set.
  279.   template<typename Key, typename _Alloc, typename Policy_Tl>
  280.     struct container_base_dispatch<Key, null_type, _Alloc, cc_hash_tag,
  281.                                    Policy_Tl>
  282.     {
  283.     private:
  284.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>       at0;
  285.       typedef typename at0::type                                at0t;
  286.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1>       at1;
  287.       typedef typename at1::type                                at1t;
  288.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2>       at2;
  289.       typedef typename at2::type                                at2t;
  290.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3>       at3;
  291.       typedef typename at3::type                                at3t;
  292.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4>       at4;
  293.       typedef typename at4::type                                at4t;
  294.  
  295.     public:
  296.       /// Dispatched type.
  297.       typedef cc_ht_set<Key, null_type, at0t, at1t, _Alloc,
  298.                                  at3t::value, at4t, at2t>       type;
  299.   };
  300.  
  301.     /// Specialization general-probe hash map.
  302.   template<typename Key, typename Mapped, typename _Alloc, typename Policy_Tl>
  303.     struct container_base_dispatch<Key, Mapped, _Alloc, gp_hash_tag, Policy_Tl>
  304.     {
  305.     private:
  306.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>       at0;
  307.       typedef typename at0::type                                at0t;
  308.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1>       at1;
  309.       typedef typename at1::type                                at1t;
  310.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2>       at2;
  311.       typedef typename at2::type                                at2t;
  312.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3>       at3;
  313.       typedef typename at3::type                                at3t;
  314.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4>       at4;
  315.       typedef typename at4::type                                at4t;
  316.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 5>       at5;
  317.       typedef typename at5::type                                at5t;
  318.  
  319.     public:
  320.       /// Dispatched type.
  321.       typedef gp_ht_map<Key, Mapped, at0t, at1t, _Alloc,
  322.                         at3t::value, at4t, at5t, at2t>          type;
  323.   };
  324.  
  325.     /// Specialization general-probe hash set.
  326.   template<typename Key, typename _Alloc, typename Policy_Tl>
  327.     struct container_base_dispatch<Key, null_type, _Alloc, gp_hash_tag,
  328.                                    Policy_Tl>
  329.     {
  330.     private:
  331.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>       at0;
  332.       typedef typename at0::type                                at0t;
  333.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1>       at1;
  334.       typedef typename at1::type                                at1t;
  335.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2>       at2;
  336.       typedef typename at2::type                                at2t;
  337.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3>       at3;
  338.       typedef typename at3::type                                at3t;
  339.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4>       at4;
  340.       typedef typename at4::type                                at4t;
  341.       typedef __gnu_cxx::typelist::at_index<Policy_Tl, 5>       at5;
  342.       typedef typename at5::type                                at5t;
  343.  
  344.     public:
  345.       /// Dispatched type.
  346.       typedef gp_ht_set<Key, null_type, at0t, at1t, _Alloc,
  347.                         at3t::value, at4t, at5t, at2t>          type;
  348.   };
  349. } // namespace detail
  350. } // namespace __gnu_pbds
  351.  
  352. #endif
  353.