insert_store_hash_fn_imps.hpp revision 169691
1109508Sobrien// -*- C++ -*- 226925Smsmith 3109508Sobrien// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 426925Smsmith// 526925Smsmith// This file is part of the GNU ISO C++ Library. This library is free 626925Smsmith// software; you can redistribute it and/or modify it under the terms 726925Smsmith// of the GNU General Public License as published by the Free Software 826925Smsmith// Foundation; either version 2, or (at your option) any later 926925Smsmith// version. 1026925Smsmith 1126925Smsmith// This library is distributed in the hope that it will be useful, but 1226925Smsmith// WITHOUT ANY WARRANTY; without even the implied warranty of 1326925Smsmith// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1426925Smsmith// General Public License for more details. 1526925Smsmith 1626925Smsmith// You should have received a copy of the GNU General Public License 1726925Smsmith// along with this library; see the file COPYING. If not, write to 1826925Smsmith// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 1926925Smsmith// MA 02111-1307, USA. 2026925Smsmith 2126925Smsmith// As a special exception, you may use this file as part of a free 2226925Smsmith// software library without restriction. Specifically, if other files 2326925Smsmith// instantiate templates or use macros or inline functions from this 2426925Smsmith// file, or you compile this file and link it with other files to 2526925Smsmith// produce an executable, this file does not by itself cause the 2626925Smsmith// resulting executable to be covered by the GNU General Public 2726925Smsmith// License. This exception does not however invalidate any other 2826925Smsmith// reasons why the executable file might be covered by the GNU General 2950476Speter// Public License. 3048794Snik 31109508Sobrien// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32206622Suqs 3379531Sru// Permission to use, copy, modify, sell, and distribute this software 3426925Smsmith// is hereby granted without fee, provided that the above copyright 3526925Smsmith// notice appears in all copies, and that both that copyright notice 3626925Smsmith// and this permission notice appear in supporting documentation. None 3726925Smsmith// of the above authors, nor IBM Haifa Research Laboratories, make any 3826925Smsmith// representation about the suitability of this software for any 3926925Smsmith// purpose. It is provided "as is" without express or implied 4026925Smsmith// warranty. 4159460Sphantom 4259460Sphantom/** 4326925Smsmith * @file insert_store_hash_fn_imps.hpp 4484306Sru * Contains implementations of gp_ht_map_'s find related functions, 4526925Smsmith * when the hash value is stored. 4626925Smsmith */ 47109508Sobrien 4826925SmsmithPB_DS_CLASS_T_DEC 4926925Smsmithinline typename PB_DS_CLASS_C_DEC::comp_hash 5026925SmsmithPB_DS_CLASS_C_DEC:: 5126925Smsmithfind_ins_pos(const_key_reference r_key, true_type) 52249912Seadler{ 5326925Smsmith _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) 5426925Smsmith comp_hash pos_hash_pair = ranged_probe_fn_base::operator()(r_key); 5526925Smsmith 5626925Smsmith size_type i; 5726925Smsmith 5826925Smsmith /* The insertion position is initted to a non-legal value to indicate 5926925Smsmith * that it has not been initted yet. 60108040Sru */ 6126925Smsmith size_type ins_pos = m_num_e; 6226925Smsmith resize_base::notify_insert_search_start(); 6326925Smsmith for (i = 0; i < m_num_e; ++i) 6426925Smsmith { 6526925Smsmith const size_type pos = ranged_probe_fn_base::operator()(r_key, pos_hash_pair.second, i); 6626925Smsmith 6726925Smsmith entry* const p_e = m_entries + pos; 6826925Smsmith switch(p_e->m_stat) 6926925Smsmith { 70108040Sru case empty_entry_status: 7126925Smsmith { 72108040Sru resize_base::notify_insert_search_end(); 7326925Smsmith _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);) 74108040Sru 75108040Sru return ((ins_pos == m_num_e) ? 7626925Smsmith std::make_pair(pos, pos_hash_pair.second) : 77108040Sru std::make_pair(ins_pos, pos_hash_pair.second)); 7826925Smsmith } 7926925Smsmith break; 8026925Smsmith case erased_entry_status: 8126925Smsmith if (ins_pos == m_num_e) 8226925Smsmith ins_pos = pos; 8326925Smsmith break; 8426925Smsmith case valid_entry_status: 8526925Smsmith if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), p_e->m_hash, 86109508Sobrien r_key, pos_hash_pair.second)) 87109508Sobrien { 88109508Sobrien resize_base::notify_insert_search_end(); 89109508Sobrien _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);) 9026925Smsmith return std::make_pair(pos, pos_hash_pair.second); 9126925Smsmith } 92108040Sru break; 9367967Sasmodai default: 94108040Sru _GLIBCXX_DEBUG_ASSERT(0); 9526925Smsmith }; 9626925Smsmith resize_base::notify_insert_search_collision(); 97108040Sru } 9826925Smsmith resize_base::notify_insert_search_end(); 99108040Sru if (ins_pos == m_num_e) 10026925Smsmith __throw_insert_error(); 10126925Smsmith return std::make_pair(ins_pos, pos_hash_pair.second); 10226925Smsmith} 103108040Sru 10426925SmsmithPB_DS_CLASS_T_DEC 105108040Sruinline std::pair<typename PB_DS_CLASS_C_DEC::point_iterator, bool> 10626925SmsmithPB_DS_CLASS_C_DEC:: 107108040Sruinsert_imp(const_reference r_val, true_type) 10826925Smsmith{ 109109508Sobrien const_key_reference r_key = PB_DS_V2F(r_val); 110111285Sru comp_hash pos_hash_pair = find_ins_pos(r_key, 11126925Smsmith traits_base::m_store_extra_indicator); 11226925Smsmith 113108040Sru _GLIBCXX_DEBUG_ASSERT(pos_hash_pair.first < m_num_e); 11426925Smsmith entry_pointer p_e =& m_entries[pos_hash_pair.first]; 115108040Sru if (p_e->m_stat == valid_entry_status) 116141851Sru { 11726925Smsmith _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key)); 11826925Smsmith return std::make_pair(&p_e->m_value, false); 11926925Smsmith } 12026925Smsmith 121109508Sobrien _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key)); 122109508Sobrien return std::make_pair(insert_new_imp(r_val, pos_hash_pair), true); 123109508Sobrien} 124109508Sobrien 125109508Sobrien